Answers.Body: <p>The main difference between the two is that Q-learning is an <em>off policy</em> algorithm. That is, we learn about an policy that is different to the one we choose to make actions. To see this, lets look at the update rule. </p>
  
  <h2>Q-Learning</h2>
  
  <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>
  
  <h2>SARSA</h2>
  
  <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>In SARSA we chose our <span class="math-container">$a'$</span> according to what our policy tells us to do when we are in state <span class="math-container">$s'$</span>, so the policy we are learning about is also the policy that we choose to make our actions. </p>
  
  <p>In Q-learning, we learn about the greedy policy whilst following some other policy, such as <span class="math-container">$\epsilon$</span>-greedy. This is because when we transition into state <span class="math-container">$s'$</span> our TD-target becomes the maximum Q-value for whichever state we end up in, <span class="math-container">$s'$</span>, where the max is taken over the actions. </p>
  
  <p>Once we have actually updated our Q-function and we need to choose an action to take in <span class="math-container">$s'$</span>, we do so from the policy we are using to generate our actions from -- thus we are learning about the greedy policy whilst following some other policy, hence <em>off policy</em>. In SARSA when we move into <span class="math-container">$s'$</span> our TD-target is chosen by the Q-value for the state we transition into and then the action we would choose based on our policy. </p>
  
  <blockquote>
    <p>Within the Q-learning episode loop the <span class="math-container">$a$</span> value is not updated, is an update made to <span class="math-container">$a$</span> during Q-learning?</p>
  </blockquote>
  
  <p>It will be, because the policy we use to choose our actions is ensured to explore sufficiently around all of the state-action pairs and so it is guaranteed to be encountered at some point. </p>
  
  <blockquote>
    <p>Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.</p>
  </blockquote>
  
  <p>It is not an <span class="math-container">$\arg \max$</span>, it is a <span class="math-container">$\max$</span>. This is defined as 
  <span class="math-container">$$\max_x f(x) = \{f(x) | \forall y\; : f(y) \leq f(x) \}$$</span></p>
  
  <blockquote>
    <p>Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step</p>
  </blockquote>
  
  <p>Kind of - the action that you chose for your TD-target in SARSA becomes the next action that you consider in the next step of the episode. This is natural because essentially you are in state <span class="math-container">$s$</span>, you take action <span class="math-container">$a$</span> and observe a new state <span class="math-container">$s'$</span>, at which point you can use your policy to see which action you <em>will</em> take, call this <span class="math-container">$a'$</span>, and then perform the SARSA update, and then execute that action in the environment. </p>
  
  <blockquote>
    <p>Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy? </p>
  </blockquote>
  
  <p>Yes, any policy can be used although you want to choose a policy that allows sufficient exploration of the state-space.</p>
  
  <blockquote>
    <p>Q learning does not utilise the next state-action pair in performing
    the td update, it just utilises the next state and current action,
    this is given in the algorithm definition as <span class="math-container">$Q(S',a)$</span> what is <span class="math-container">$a$</span> in
    this case ?</p>
  </blockquote>
  
  <p>in the algorithm it actually has <span class="math-container">$\max_a Q(S',a)$</span>, which if you refer back to my earlier definition of what the <span class="math-container">$\max$</span> operator does, should answer this question. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-16T13:07:26.333Z
Answers.Text: "It is not an argmax, it is a max." thanks for pointing this out, I mixed up taking the arg max in the function epsilon greedy with the calculation of the updated Sarsa Q value .
Answers.UserDisplayName: blue-sky
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-09T13:49:02.720Z
Answers.Text: When you say "In SARSA we chose our $a'$ according to what our policy tells us to do when we are in state $s'$, so the policy we are learning about is also the policy that we choose to make our actions.". It's important to note that this is definitely **not** clear only from the update rule of SARSA, because the update rule in SARSA doesn't tell you anything about how the actions $a$ and $a'$ are chosen from the corresponding states. You need to explicitly say it. In Q-learning, this is less of a problem, one can understand that the max "represents the target policy".
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-09T13:49:05.140Z
Answers.Text: What you need to clarify here (which you try to do) is that the behavior policy, such as $\epsilon$-greedy, is used to pick up the tuples $(s, a)$ for which you update $Q(s, a)$ in both the Q-learning and SARSA. The difference is that in SARSA you also use $\epsilon$-greedy (or any other behaviour policy that you used before to select $a$ from $s$) to take action $a'$ from $s'$ (as opposed to just select the greedy action, as in Q-learning).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-09T13:54:43.203Z
Answers.Text: In my opinion, the best way to understand the difference between SARSA and Q-learning is really to read the [pseudocode of both algorithms](https://www.cse.unsw.edu.au/~cs9417ml/RL1/algorithms.html) (actually provided in the question), and not just the update rules, which are not self-explanatory, as I am trying to say.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-15T19:17:49.857Z
Answers.LastActivityDate: 2020-06-15T19:28:32.940Z
Answers.LastEditDate: 2020-06-15T19:28:32.940Z
Answers.UserDisplayName: David
Body: <p>From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series), are the following definitions:</p>
  
  <p><a href="https://i.sstatic.net/PIJ5B.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PIJ5B.png" alt="enter image description here"></a></p>
  
  <p><a href="https://i.sstatic.net/qwGI3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qwGI3.png" alt="enter image description here"></a></p>
  
  <p>To aid my learning of RL and gain an intuition, I'm focusing on the differences between some algorithms. I've selected <code>Sarsa (on-policy TD control) for estimating Q ≈ q *</code> and <code>Q-learning (off-policy TD control) for estimating π ≈ π *</code>.</p>
  
  <p>For conciseness I'll refer to <code>Sarsa (on-policy TD control) for estimating Q ≈ q *</code> and <code>Q-learning (off-policy TD control) for estimating π ≈ π *</code> as Sarsa and Q-learning respectively.</p>
  
  <p>Are my following assertions correct?</p>
  
  <p>The primary differences are how the Q values are updated.</p>
  
  <p>Sarsa Q value update:
  <span class="math-container">$ Q ( S, A ) ← Q ( S, A ) + α [ R + \gamma Q ( S ′ , A ′ ) − Q ( S, A ) ] $</span></p>
  
  <p>Q-learning Q value update:
  <span class="math-container">$ Q ( S, A ) ← Q ( S, A ) + α [ R + \gamma \max_a Q ( S ′ , a ) − Q ( S, A ) ] $</span></p>
  
  <p>Sarsa, in performing the td update subtracts the discounted Q value of the next state and action, S', A' from the Q value of the current state and action S, A. 
  Q-learning, on the other hand, takes the discounted difference between the max action value for the Q value of the next state and current action S', a.  Within the Q-learning episode loop the <span class="math-container">$a$</span> value is not updated, is an update made to <span class="math-container">$a$</span> during Q-learning? </p>
  
  <p>Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step</p>
  
  <p>Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.</p>
  
  <p>Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy?
  Q learning does not utilise the next state-action pair in performing the td update, it just utilises the next state and current action, this is given in the algorithm definition as  <span class="math-container">$ Q ( S ′ , a ) $</span> what is <span class="math-container">$a$</span> in this case ?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-15T19:13:31.930Z
Comments.Text: [here](https://ai.stackexchange.com/questions/21044/are-q-learning-and-sarsa-the-same-when-action-selection-is-greedy/21070#21070) is an answer that shows when the two are (almost) the same.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-18T13:32:59.877Z
Comments.Text: Hi. Please, next time, ask one question per post. Here you're asking too many questions. When you have multiple questions, ask each of them in its separate post, even though they are related. This helps answerers to focus on a single problem, so it facilitates the life of everyone that reads the posts. Please, read [our on-topic page](https://ai.stackexchange.com/help/on-topic) to understand the ideal question we are looking for.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><comparison><q-learning><sarsa>
Title: What are the differences between SARSA and Q-learning?
UserDisplayName: blue-sky
ThreadText: # What are the differences between SARSA and Q-learning?
  
  (Asked by: username_0 on 2020-06-15)
  
  From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series), are the following definitions:
  
  [![enter image description here](https://i.sstatic.net/PIJ5B.png)](https://i.sstatic.net/PIJ5B.png)
  
  [![enter image description here](https://i.sstatic.net/qwGI3.png)](https://i.sstatic.net/qwGI3.png)
  
  To aid my learning of RL and gain an intuition, I'm focusing on the differences between some algorithms. I've selected `Sarsa (on-policy TD control) for estimating Q ≈ q *` and `Q-learning (off-policy TD control) for estimating π ≈ π *`.
  
  For conciseness I'll refer to `Sarsa (on-policy TD control) for estimating Q ≈ q *` and `Q-learning (off-policy TD control) for estimating π ≈ π *` as Sarsa and Q-learning respectively.
  
  Are my following assertions correct?
  
  The primary differences are how the Q values are updated.
  
  Sarsa Q value update:
  $ Q ( S, A ) ← Q ( S, A ) + α [ R + \gamma Q ( S ′ , A ′ ) − Q ( S, A ) ] $
  
  Q-learning Q value update:
  $ Q ( S, A ) ← Q ( S, A ) + α [ R + \gamma \max\_a Q ( S ′ , a ) − Q ( S, A ) ] $
  
  Sarsa, in performing the td update subtracts the discounted Q value of the next state and action, S', A' from the Q value of the current state and action S, A.
  Q-learning, on the other hand, takes the discounted difference between the max action value for the Q value of the next state and current action S', a. Within the Q-learning episode loop the $a$ value is not updated, is an update made to $a$ during Q-learning?
  
  Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step
  
  Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.
  
  Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy?
  Q learning does not utilise the next state-action pair in performing the td update, it just utilises the next state and current action, this is given in the algorithm definition as $ Q ( S ′ , a ) $ what is $a$ in this case ?
  
  **Tags:** reinforcement-learning, comparison, q-learning, sarsa
  
  > **Comments:**
  > **username_1**: [here](https://ai.stackexchange.com/questions/21044/are-q-learning-and-sarsa-the-same-when-action-selection-is-greedy/21070#21070) is an answer that shows when the two are (almost) the same.  
  > **username_2**: Hi. Please, next time, ask one question per post. Here you're asking too many questions. When you have multiple questions, ask each of them in its separate post, even though they are related. This helps answerers to focus on a single problem, so it facilitates the life of everyone that reads the posts. Please, read [our on-topic page](https://ai.stackexchange.com/help/on-topic) to understand the ideal question we are looking for.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-15. Score: 2 | Accepted answer
  
  The main difference between the two is that Q-learning is an *off policy* algorithm. That is, we learn about an policy that is different to the one we choose to make actions. To see this, lets look at the update rule.
  
  ## 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))$$
  
  In SARSA we chose our $a'$ according to what our policy tells us to do when we are in state $s'$, so the policy we are learning about is also the policy that we choose to make our actions.
  
  In Q-learning, we learn about the greedy policy whilst following some other policy, such as $\epsilon$-greedy. This is because when we transition into state $s'$ our TD-target becomes the maximum Q-value for whichever state we end up in, $s'$, where the max is taken over the actions.
  
  Once we have actually updated our Q-function and we need to choose an action to take in $s'$, we do so from the policy we are using to generate our actions from -- thus we are learning about the greedy policy whilst following some other policy, hence *off policy*. In SARSA when we move into $s'$ our TD-target is chosen by the Q-value for the state we transition into and then the action we would choose based on our policy.
  
  > Within the Q-learning episode loop the $a$ value is not updated, is an update made to $a$ during Q-learning?
  
  It will be, because the policy we use to choose our actions is ensured to explore sufficiently around all of the state-action pairs and so it is guaranteed to be encountered at some point.
  
  > Sarsa, unlike Q-learning, does not include the arg max as part of the update to Q value.
  
  It is not an $\arg \max$, it is a $\max$. This is defined as
  $$\max\_x f(x) = \{f(x) | \forall y\; : f(y) \leq f(x) \}$$
  
  > Sarsa, unlike Q-learning, the current action is assigned to the next action at the end of each episode step. Q-learning does not assign the current action to the next action at the end of each episode step
  
  Kind of - the action that you chose for your TD-target in SARSA becomes the next action that you consider in the next step of the episode. This is natural because essentially you are in state $s$, you take action $a$ and observe a new state $s'$, at which point you can use your policy to see which action you *will* take, call this $a'$, and then perform the SARSA update, and then execute that action in the environment.
  
  > Sarsa and Q learning in choosing the initial action for each episode both use a "policy derived from Q", as an example, the epsilon greedy policy is given in the algorithm definition. But any policy could be used here instead of epsilon greedy?
  
  Yes, any policy can be used although you want to choose a policy that allows sufficient exploration of the state-space.
  
  > Q learning does not utilise the next state-action pair in performing
  > the td update, it just utilises the next state and current action,
  > this is given in the algorithm definition as $Q(S',a)$ what is $a$ in
  > this case ?
  
  in the algorithm it actually has $\max\_a Q(S',a)$, which if you refer back to my earlier definition of what the $\max$ operator does, should answer this question.
  
  > **Comments:**
  > **username_0**: "It is not an argmax, it is a max." thanks for pointing this out, I mixed up taking the arg max in the function epsilon greedy with the calculation of the updated Sarsa Q value .  
  > **username_2**: When you say "In SARSA we chose our $a'$ according to what our policy tells us to do when we are in state $s'$, so the policy we are learning about is also the policy that we choose to make our actions.". It's important to note that this is definitely **not** clear only from the update rule of SARSA, because the update rule in SARSA doesn't tell you anything about how the actions $a$ and $a'$ are chosen from the corresponding states. You need to explicitly say it. In Q-learning, this is less of a problem, one can understand that the max "represents the target policy".  
  > **username_2**: What you need to clarify here (which you try to do) is that the behavior policy, such as $\epsilon$-greedy, is used to pick up the tuples $(s, a)$ for which you update $Q(s, a)$ in both the Q-learning and SARSA. The difference is that in SARSA you also use $\epsilon$-greedy (or any other behaviour policy that you used before to select $a$ from $s$) to take action $a'$ from $s'$ (as opposed to just select the greedy action, as in Q-learning).  
  > **username_2**: In my opinion, the best way to understand the difference between SARSA and Q-learning is really to read the [pseudocode of both algorithms](https://www.cse.unsw.edu.au/~cs9417ml/RL1/algorithms.html) (actually provided in the question), and not just the update rules, which are not self-explanatory, as I am trying to say.  
  
  ---
  
  