1
$\begingroup$

I have a question about how to update the Q-function in Q-learning and SARSA. Here (What are the differences between SARSA and Q-learning?) the following updating formulas are given:

Q-Learning

$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a))$$

SARSA

$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma Q(s',a') - Q(s,a))$$

How can we calculate the $Q(s', a')$ in both SARSA and Q-learning for updating the Q-function? After having taken an action $a$ at state $s$, we get the reward $r$, which we can observe. But we cannot observe $Q(s',a')$ from the environment as far as I see it.

Can anyone maybe think about a comprehensive example where you can see how it is done (or a link to a website)?

$\endgroup$
3
  • $\begingroup$ I have deleted my answer as it did not answer your question. Reading the first few chapters of Sutton&Barto may help you a lot, it covers the details that you are currently studying. A free version, provided by one of the authors, can be found at incompleteideas.net/book/RLbook2020.pdf $\endgroup$ Dec 16, 2021 at 18:07
  • $\begingroup$ Can you explain why the deleted answer doesn't answer your question? Did you understand that, when performing the update in SARSA, we do not really compute $Q(s', a')$, but we just use the estimate that we have saved in our table or neural network $Q$? If you understand that, then what's your question? Having said that, there are 2 questions. If you wanted to consider your doubts clarified only if people answer the 2 questions, that's not good. You should ask the other question about the example in another post. $\endgroup$
    – nbro
    Dec 18, 2021 at 9:23
  • $\begingroup$ @nbro: Thanks for your comment.You wrote "Did you understand that, when performing the update in SARSA, we do not really compute $Q(s′,a′)$, but we just use the estimate that we have saved in our table or neural network Q?" --> Actually I do not understand this. How can we estimate $Q(s′,a′)$? After having taken an action $a$ at state $s$, we get the reward $r$, which we can observe. But now my question is how to derive $Q(s′,a′)$ out of it? As far as I understand $Q(s′,a′)$ is the Q value of the next state $s'$. When we are at time $t$ how can we estimate the value of time $t+1$? $\endgroup$
    – PeterBe
    Dec 20, 2021 at 10:14

1 Answer 1

1
$\begingroup$

It seems that your problem is that you think that we must know the true value of $Q(s', a')$ in order to perform the SARSA update. This is not the case! SARSA is a reinforcement learning algorithm, not a supervised learning algorithm (although you can also view RL as a form of SL).

If you are familiar with supervised learning (SL), then you know that, to train a model, you need the ground-truth labels. The typical SL example is that of binary classification of dogs and cats. So, you are given an image of a dog or cat $x$, you pass it to your neural network $f$, which produces a prediction $\hat{y} = f(x)$. Now, if $x$ is a dog but $\hat{y}$ is cat, the neural network $f$ made a mistake. So, we need to change the weights of this model so that $\hat{y} = \text{dog}$ when $x$ is an image of a dog (of course, this reasoning also applies to the case when $x$ is an image of a cat). A typical way to solve this problem in SL is to use a loss function that computes some notion of distance between $\hat{y}$ (the prediction) and $y$ (the true label). The usual loss function, in this case, is the binary cross-entropy, but you don't need to know the details now.

In reinforcement learning, you don't really have ground-truth labels, but you have experience, which is just the tuples $\langle s_t, a_t, r_{t+1}, s_{t+1} \rangle $, where

  • $s_t$ is the state of the agent/environment at time step $t$
  • $a_t$ is the action that the agent takes at time step $t$ in state $s_t$
  • $r_{t+1}$ is the reward the agent receives after having taken action $a_t$ in $s_t$; this reward indicates how good that action is, but it doesn't tell whether you took the correct/optimal (or ground-truth) action or not (this is the main difference between reinforcement learning and supervised learning!)
  • $s_{t+1}$ is the state the agent ends up in after having taken $a_t$ in $s_t$.

Now, in reinforcement learning, there are many problems that you may want to solve. However, the main goal of an RL agent is to maximize expected reward in the long run (known also as expected return), so you could say that your objective function is $$\mathbb{E} \left[ \sum_{t=0}^\infty R_t \right],$$ where $G = \sum_{t=0}^\infty R_t$ is the so-called return (i.e. the cumulative reward or reward in the long run). The goal is to maximize this expectation.

In practice, what you do is ESTIMATE a so-called (state-action or just action) value function. In the case of SARSA, it's defined as $q: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$, where $\mathcal{S}$ and $\mathcal{A}$ are respectively the set of states and actions of the environment (aka MDP).

Why do you want to estimate a value function? In the case of $q$ (so SARSA and Q-learning), $q(s, a)$, for some $s \in \mathcal{S}$ and $a \in \mathcal{A}$, is defined as the expected cumulative reward that you will get from taking action $a$ in the state $s$. So, if you know that you will get more reward by taking action $a_1$ rather than action $a_2$ in state $s$, then $q(s, a_1) > q(s, a_2)$, so you will take action $a_1$ when in state $s$. In fact, you can also define $q(s, a)$ as follows $q(s, a) = \mathbb{E}\left[ G \mid s, a \right]$, where $G$ is our cumulative reward, aka return (for simplicity, I ignore a few details).

HOWEVER, we do not (usually) know $q$. That's why we need Q-learning and SARSA, i.e. to estimate the state-action value function. So, in SARSA, you know $s'$ and $a'$ (read the pseudocode!), but we do not know the true value of $q(s', a')$. So, you say, but then why do we use it in the update of SARSA?

The reason is: initially, SARSA uses possibly wrong estimates of $q$ to learn $q$ itself. We denote these estimates with the capital letter $Q$. So, we don't know the true value of $a'$ in $s'$. Or, more precisely, at the beginning of SARSA, if $q$ is implemented as a 2d array (or matrix), then $Q[s', a']$ is not a good estimate of the true value of $a'$ in state $s'$, i.e. $q(s', a')$. In other words, $Q[s', a'] \approx q(s', a')$.

Now, you ask: why can we use a possibly wrong estimate, $Q(s', a')$, to compute $Q(s, a)$ (another estimate)? The idea of using possibly wrong estimates of the state-value function to update other estimates of the value function is present in all temporal-difference algorithms (including Q-learning): this is called bootstrapping. However, the specific reason why tabular SARSA converges to the true estimates is a different (although related) story (more info here).

Now, if you didn't understand this answer, then you really need to pick up a book and read it carefully from the beginning. It takes time to understand RL at the beginning, but then it becomes easy. The most common textbook for RL is Reinforcement Learning: An Introduction by Sutton and Barto. You can find other books here.

$\endgroup$
4
  • $\begingroup$ Thanks a lot for this answer and your effort. I really appreciate it. Actually I understand everything until the estimation of the $Q$ by using bootstrapping. This is also the core of my question (and the problem is not as you assumed that I "think that we must know the true value of $Q(s′,a′)$ "). Where do we get these possibly wrong estimate, $Q(s′,a′)$, to compute $Q(s,a)$ from. I know that in TD learning you don't wait until the full reward at the end but you get a reward after every time step. But what I don't understand is how I can estimate or calculate the $Q(s′,a′)$ values $\endgroup$
    – PeterBe
    Dec 20, 2021 at 14:07
  • $\begingroup$ @PeterBe Let's say that you have 2 states and 2 actions. So, you can represent $Q$ as $2 \times 2$ matrix. So far, do you understand? Now, in SARSA, we initialise this matrix randomly. So, $Q[s', a']$ is initially a random number. So, this "estimates" are random numbers at the beginning. Then they are updated using the SARSA algorithm, the more experience (aka tuples) we get. Do you understand now?! If you don't understand this, read the book. Alternatively, just simulate the SARSA algorithm yourself. Take a $2 \times 2$ matrix and simulate it by hand. $\endgroup$
    – nbro
    Dec 20, 2021 at 14:09
  • $\begingroup$ Thanks for the comment nbro. I think I need to have a look at an example to see how it fully works (before I can simulate it on my own). But with your comment I can at least somehow imagine how it works. So I accepted and upvoted your answer. $\endgroup$
    – PeterBe
    Dec 20, 2021 at 14:35
  • 1
    $\begingroup$ @PeterBe Feel free to ask another separate question like "Given a 2x2 matrix that represents Q (so there are 2 states and 2 actions), can you simulate how SARSA would update the values of Q". Maybe, before asking, this question, try to do it yourself and tell us where you are stuck. $\endgroup$
    – nbro
    Dec 20, 2021 at 14:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .