Answers.Body: <p>It seems that your problem is that you think that we must know the true value of <span class="math-container">$Q(s', a')$</span> in order to perform the SARSA update. This is <strong>not</strong> the case! SARSA is a reinforcement learning algorithm, not a supervised learning algorithm (<a href="https://ai.stackexchange.com/a/14168/2444">although you can also view RL as a form of SL</a>).</p>
  <p>If you are familiar with <strong>supervised learning (SL)</strong>, then you know that, to train a model, you need the <strong>ground-truth labels</strong>. The typical SL example is that of binary classification of dogs and cats. So, you are given an image of a dog or cat <span class="math-container">$x$</span>, you pass it to your neural network <span class="math-container">$f$</span>, which produces a prediction <span class="math-container">$\hat{y} = f(x)$</span>. Now, if <span class="math-container">$x$</span> is a dog but <span class="math-container">$\hat{y}$</span> is cat, the neural network <span class="math-container">$f$</span> made a mistake. So, we need to change the weights of this model so that <span class="math-container">$\hat{y} = \text{dog}$</span> when <span class="math-container">$x$</span> is an image of a dog (of course, this reasoning also applies to the case when <span class="math-container">$x$</span> 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 <span class="math-container">$\hat{y}$</span> (the prediction) and <span class="math-container">$y$</span> (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.</p>
  <p>In <strong>reinforcement learning</strong>, you don't really have ground-truth labels, but you have <strong>experience</strong>, which is just the tuples <span class="math-container">$\langle s_t, a_t, r_{t+1}, s_{t+1} \rangle $</span>, where</p>
  <ul>
  <li><span class="math-container">$s_t$</span> is the state of the agent/environment at time step <span class="math-container">$t$</span></li>
  <li><span class="math-container">$a_t$</span> is the action that the agent takes at time step <span class="math-container">$t$</span> in state <span class="math-container">$s_t$</span></li>
  <li><span class="math-container">$r_{t+1}$</span> is the reward the agent receives after having taken action <span class="math-container">$a_t$</span> in <span class="math-container">$s_t$</span>; this reward indicates how good that action is, but it doesn't tell whether you took the <strong>correct/optimal</strong> (or ground-truth) action or not (this is the main difference between reinforcement learning and supervised learning!)</li>
  <li><span class="math-container">$s_{t+1}$</span> is the state the agent ends up in after having taken <span class="math-container">$a_t$</span> in <span class="math-container">$s_t$</span>.</li>
  </ul>
  <p>Now, in reinforcement learning, there are many problems that you may want to solve. However, the main goal of an RL agent is to <strong>maximize expected reward in the long run</strong> (known also as <strong>expected return</strong>), so you could say that your objective function is <span class="math-container">$$\mathbb{E} \left[ \sum_{t=0}^\infty R_t \right],$$</span>
  where <span class="math-container">$G = \sum_{t=0}^\infty R_t$</span> is the so-called <strong>return</strong> (i.e. the cumulative reward or reward in the long run). The goal is to maximize this expectation.</p>
  <p>In practice, what you do is <strong>ESTIMATE</strong> a so-called (state-action or just action) <strong>value function</strong>. In the case of SARSA, it's defined as <span class="math-container">$q: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$</span>, where <span class="math-container">$\mathcal{S}$</span> and <span class="math-container">$\mathcal{A}$</span> are respectively the set of states and actions of the environment (aka MDP).</p>
  <p>Why do you want to estimate a value function? In the case of <span class="math-container">$q$</span> (so SARSA and Q-learning), <span class="math-container">$q(s, a)$</span>, for some <span class="math-container">$s \in \mathcal{S}$</span> and <span class="math-container">$a \in \mathcal{A}$</span>, is defined as the <strong>expected cumulative reward</strong> that you will get from taking action <span class="math-container">$a$</span> in the state <span class="math-container">$s$</span>. So, if you know that you will get more reward by taking action <span class="math-container">$a_1$</span> rather than action <span class="math-container">$a_2$</span> in state <span class="math-container">$s$</span>, then <span class="math-container">$q(s, a_1) &gt; q(s, a_2)$</span>, so you will take action <span class="math-container">$a_1$</span> when in state <span class="math-container">$s$</span>. In fact, you can also define <span class="math-container">$q(s, a)$</span> as follows <span class="math-container">$q(s, a) = \mathbb{E}\left[ G \mid s, a \right]$</span>, where <span class="math-container">$G$</span> is our cumulative reward, aka return (for simplicity, I ignore a few details).</p>
  <p>HOWEVER, <strong>we do not (usually) know <span class="math-container">$q$</span></strong>. That's why we need Q-learning and SARSA, i.e. to <strong>estimate</strong> the state-action value function. So, in SARSA, you know <span class="math-container">$s'$</span> and <span class="math-container">$a'$</span> (read the pseudocode!), but we do not know the <strong>true</strong> value of <span class="math-container">$q(s', a')$</span>. So, you say, but then why do we use it in the update of SARSA?</p>
  <p>The reason is: initially, SARSA uses possibly wrong estimates of <span class="math-container">$q$</span> to learn <span class="math-container">$q$</span> itself. We denote these estimates with the capital letter <span class="math-container">$Q$</span>. So, we don't know the true value of <span class="math-container">$a'$</span> in <span class="math-container">$s'$</span>. Or, more precisely, at the beginning of SARSA, if <span class="math-container">$q$</span> is implemented as a 2d array (or matrix), then <span class="math-container">$Q[s', a']$</span> is not a good estimate of the true value of <span class="math-container">$a'$</span> in state <span class="math-container">$s'$</span>, i.e. <span class="math-container">$q(s', a')$</span>. In other words, <span class="math-container">$Q[s', a'] \approx q(s', a')$</span>.</p>
  <p>Now, you ask: why can we use a possibly wrong estimate, <span class="math-container">$Q(s', a')$</span>, to compute <span class="math-container">$Q(s, a)$</span> (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 <strong>bootstrapping</strong>. However, the specific reason why tabular SARSA converges to the true estimates is a different (although related) story (more info <a href="https://ai.stackexchange.com/a/18280/2444">here</a>).</p>
  <p>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 <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a> by Sutton and Barto. You can find other books <a href="https://ai.stackexchange.com/q/22010/2444">here</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-20T14:07:12.473Z
Answers.Text: 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
Answers.UserDisplayName: PeterBe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-20T14:09:00.797Z
Answers.Text: @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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-20T14:35:36.233Z
Answers.Text: 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.
Answers.UserDisplayName: PeterBe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-20T14:36:54.857Z
Answers.Text: @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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-20T10:53:52.580Z
Answers.LastActivityDate: 2021-12-20T11:34:37.297Z
Answers.LastEditDate: 2021-12-20T11:34:37.297Z
Answers.UserDisplayName: nbro
Body: <p>I have a question about how to update the Q-function in Q-learning and SARSA. Here (<a href="https://ai.stackexchange.com/questions/21910/what-are-the-differences-between-sarsa-and-q-learning">What are the differences between SARSA and Q-learning?</a>) the following updating formulas are given:</p>
  <h3>Q-Learning</h3>
  <p><span class="math-container">$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a))$$</span></p>
  <h3>SARSA</h3>
  <p><span class="math-container">$$Q(s,a) = Q(s,a) + \alpha (R_{t+1} + \gamma Q(s',a') - Q(s,a))$$</span></p>
  <p>How can we calculate the <span class="math-container">$Q(s', a')$</span> in both SARSA and Q-learning for updating the Q-function? After having taken an action <span class="math-container">$a$</span> at state <span class="math-container">$s$</span>, we get the reward <span class="math-container">$r$</span>, which we can observe. But we cannot observe <span class="math-container">$Q(s',a')$</span> from the environment as far as I see it.</p>
  <p>Can anyone maybe think about a comprehensive example where you can see how it is done (or a link to a website)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-16T18:07:14.970Z
Comments.Text: 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 http://incompleteideas.net/book/RLbook2020.pdf
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-18T09:23:11.617Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-20T10:14:39.747Z
Comments.Text: @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$?
Comments.UserDisplayName: PeterBe
Tags: <reinforcement-learning><q-learning><sarsa><bootstrapping>
Title: How is $Q(s', a')$ calculated in SARSA and Q-Learning?
UserDisplayName: PeterBe
ThreadText: # How is $Q(s', a')$ calculated in SARSA and Q-Learning?
  
  (Asked by: username_0 on 2021-12-15)
  
  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?](https://ai.stackexchange.com/questions/21910/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)?
  
  **Tags:** reinforcement-learning, q-learning, sarsa, bootstrapping
  > **Comments:**
  > **username_1**: 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 http://incompleteideas.net/book/RLbook2020.pdf  
  > **username_2**: 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.  
  > **username_0**: @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$?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-12-20. Score: 1 | Accepted answer
  
  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](https://ai.stackexchange.com/a/14168/2444)).
  
  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](https://ai.stackexchange.com/a/18280/2444)).
  
  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](http://incompleteideas.net/book/RLbook2020.pdf) by Sutton and Barto. You can find other books [here](https://ai.stackexchange.com/q/22010/2444).
  
  > **Comments:**
  > **username_0**: 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  
  > **username_2**: @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.  
  > **username_0**: 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.  
  > **username_2**: @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.  
  
  ---
  
  