<p>If we write the pseudo-code for the SARSA algorithm we first initialise our hyper-parameters etc. and then initialise <span class="math-container">$S_t$</span>, which we use to choose <span class="math-container">$A_t$</span> from our policy <span class="math-container">$\pi(a|s)$</span>. Then for each <span class="math-container">$t$</span> in the episode we do the following:</p>
<ol>
<li>Take action <span class="math-container">$A_t$</span> and observe <span class="math-container">$R_{t+1}$</span>, <span class="math-container">$S_{t+1}$</span></li>
<li>Choose <span class="math-container">$A_{t+1}$</span> using <span class="math-container">$S_{t+1}$</span> in our policy</li>
<li><span class="math-container">$Q(S_t, A_t) = Q(S_t, A_t) + \alpha [R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t, A_t)]$</span></li>
</ol>
<p>Now, in Q-learning we replace <span class="math-container">$Q(S_{t+1},A_{t+1})$</span> in line 3 with <span class="math-container">$\max_aQ(S_{t+1},a)$</span>. Recall that in SARSA we chose our <span class="math-container">$A_{t+1}$</span> using our policy <span class="math-container">$\pi$</span> - if our policy is greedy with respect to the action value function then this simply means the policy is <span class="math-container">$\pi(a|s) = \text{argmax}_aQ(s,a)$</span> which is exactly how we choose our weight update in Q-learning.</p>
<p>To answer the question - <strong>no</strong>, they are not <em>always</em> the same algorithm.</p>
<p>Consider where we transition from <span class="math-container">$s$</span> to <span class="math-container">$s'$</span> where <span class="math-container">$s'=s$</span>. I will outline the updates for SARSA and Q-learning indexing the <span class="math-container">$Q$</span> functions with <span class="math-container">$t$</span> to demonstrate the difference.</p>
<p>For each case, I will assume we are at the start of the episode, as this is the easiest way to illustrate the difference. Note that actions denoted by <span class="math-container">$A_i$</span> are for actions taken explicitly in the environment -- in the Q-Learning update the <span class="math-container">$\max$</span> action that is chosen for the update is not executed in the environment, the action taken in the environment is chosen by the policy after the update has happened.</p>
<p><strong>SARSA</strong></p>
<ol>
<li>We initialise <span class="math-container">$S_0 = s$</span> and choose <span class="math-container">$A_0 = \text{argmax}_a Q_0(s,a)$</span></li>
<li>Take action <span class="math-container">$A_0$</span> and observe <span class="math-container">$R_{1}$</span> and <span class="math-container">$S_{1} = s' = s$</span>.</li>
<li>Choose action <span class="math-container">$A_{1} = \text{argmax}_aQ_{0}(s,a)$</span></li>
<li><span class="math-container">$Q_{1}(S_0,A_0) = Q_0(S_0,A_0) + \alpha [R_{1} + \gamma Q_0(s,A_1) - Q_0(S_0,A_0)]$</span></li>
</ol>
<p><strong>Q-Learning</strong></p>
<ol>
<li>Initialise <span class="math-container">$S_0 = s$</span></li>
<li>Choose action <span class="math-container">$A_0 = \text{argmax}_aQ_0(s,a)$</span>, observe <span class="math-container">$R_{1}, S_{1} = s' = s$</span></li>
<li><span class="math-container">$Q_{1}(S_0,A_0) = Q_0(S_0,A_0) + \alpha [R_{1} + \gamma \max_aQ_0(s,a) - Q_0(S_0,A_0)]$</span></li>
<li>Choose action <span class="math-container">$A_1 = \text{argmax}_aQ_1(s,a)$</span></li>
</ol>
<p>As you can see the next action for the updates in SARSA (line 4) and Q-learning (line 3) are taken with respect to the same <span class="math-container">$Q$</span> function, <em>but the key difference is that the actual next action taken in <span class="math-container">$Q$</span>-learning is taken with respect to the updated <span class="math-container">$Q$</span>-function</em>.</p>
<p>The key for understanding this edge case is that when we transition into the same state, <strong>the Q-Learning update will update the Q-function before choosing <span class="math-container">$A_1$</span></strong>. I have indexed actions and Q-functions by the episode step - hopefully, it makes sense why I have done this for the Q-functions as, usually, this would not make sense, but, because we have two successive states that are the same, it is okay.</p>

CC BY-SA 4.0
2020-12-06T12:24:24.103Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/116995/discussion-on-answer-by-david-ireland-are-q-learning-and-sarsa-the-same-when-act).
nbro
CC BY-SA 4.0
2020-05-11T13:31:00.277Z
2020-12-06T12:26:10.680Z
2020-12-06T12:26:10.680Z
David
<p>SARSA:
<span class="math-container">$$Q(S_t,A_t)=Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$$</span>
Q-Learning
<span class="math-container">$$Q(S_t,A_t)=Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\max Q(S_{t+1},a)-Q(S_t,A_t)]$$</span></p>
<p>Consider the following case:
For both SARSA and Q-Learning we'll randomly select <span class="math-container">$a_1$</span>, when <span class="math-container">$t=1, t=2$</span>, and assume <span class="math-container">$\alpha R_2 &gt; 0$</span></p>
<p>SARSA
At <span class="math-container">$t=2$</span> to determine <span class="math-container">$Q(S_3,A_3)$</span> since it's greedy it'll choose <span class="math-container">$s_1,a_1$</span> and the recalculate <span class="math-container">$Q(s_1,a_1)$</span>
<span class="math-container">$$\def\arraystretch{1.5}
   \begin{array}{|c|c|c|}\hline
   (t,s,a, R) &amp; Q(s_1,a_1) &amp; Q(s_1,a_2) \\ \hline
&amp; 0 &amp; 0 \\ \hline
   (1,s_1,a_1, R_2) &amp; \alpha R_2 &amp; 0\\ \hline
   (2,s_1,a_1, R_3) &amp; \alpha R_2 + \alpha R_3 +\alpha^2\gamma R_2 -\alpha^2R_2&amp; 0   \\\hline
   (3,s_1,a_1, R_4) &amp;  &amp; 0\\ \hline
\end{array}$$</span></p>
<p>Q-Learning, at <span class="math-container">$t=2$</span> to determine <span class="math-container">$Q(S_3,A_3)$</span>, it'll first evaluate the policies so inorder to pick <span class="math-container">$Q(s_1,a_1)$</span>
<span class="math-container">$$\alpha R_2 + \alpha R_3 +\alpha^2\gamma R_2 -\alpha^2R_2 &gt; 0$$</span>
<span class="math-container">$$R_2 + R_3 +\alpha\gamma R_2 -\alpha R_2 &gt; 0$$</span>
<span class="math-container">$$-R_2(-1-\alpha\gamma + \alpha) + R_3 &gt; 0$$</span>
<span class="math-container">$$R_3 &gt; R_2(\alpha-\alpha\gamma-1)$$</span></p>
<p><span class="math-container">$$\def\arraystretch{1.5}
   \begin{array}{|c|c|c|}\hline
   (t,s,a) &amp; Q(s_1,a_1) &amp; Q(s_1,a_2) \\ \hline
&amp; 0 &amp; 0 \\ \hline
   (1,s_1,a_1, R_2) &amp; \alpha R_2 &amp; 0\\ \hline
   (2,s_1,a_1, R_3) &amp; \alpha R_2 + \alpha R_3 +\alpha^2\gamma R_2 -\alpha^2R_2&amp; 0   \\\hline
   (3,s_1,a_1, R_4) &amp;  &amp;   \\\hline
\end{array}$$</span></p>

CC BY-SA 4.0
2024-04-16T16:33:38.007Z
2024-04-16T16:33:38.007Z
Elliott de Launay
<p>I'm currently studying reinforcement learning and I'm having difficulties with question 6.12 in Sutton and Barto's book.</p>

<p>Suppose action selection is greedy. Is Q-learning then exactly the same algorithm as SARSA? Will they make exactly the same action selections and weight updates?</p>

<p>I think it's true, because the main difference between the two is when the agent explores, and following the greedy policy it never explores, but I am not sure.</p>

CC BY-SA 4.0
2021-10-03T15:00:55.527Z
This question is possibly a duplicate of https://stackoverflow.com/questions/32846262/are-q-learning-and-sarsa-with-greedy-selection-equivalent.
willtryagain
CC BY-SA 4.0
2022-01-23T10:11:54.287Z
@willtryagain The question on Stack Overflow is off-topic there.
nbro
<reinforcement-learning><comparison><q-learning><sarsa><greedy-policy>
Are Q-learning and SARSA the same when action selection is greedy?
hyuj
# Are Q-learning and SARSA the same when action selection is greedy?

(Asked by: username_0 on 2020-05-10)

I'm currently studying reinforcement learning and I'm having difficulties with question 6.12 in Sutton and Barto's book.

Suppose action selection is greedy. Is Q-learning then exactly the same algorithm as SARSA? Will they make exactly the same action selections and weight updates?

I think it's true, because the main difference between the two is when the agent explores, and following the greedy policy it never explores, but I am not sure.

**Tags:** reinforcement-learning, comparison, q-learning, sarsa, greedy-policy

> **Comments:**
> **username_1**: This question is possibly a duplicate of https://stackoverflow.com/questions/32846262/are-q-learning-and-sarsa-with-greedy-selection-equivalent.  
> **username_2**: @username_1 The question on Stack Overflow is off-topic there.  

---

## 2 answers

### Answer by username_3 on 2020-05-11. Score: 8

If we write the pseudo-code for the SARSA algorithm we first initialise our hyper-parameters etc. and then initialise $S\_t$, which we use to choose $A\_t$ from our policy $\pi(a|s)$. Then for each $t$ in the episode we do the following:

1. Take action $A\_t$ and observe $R\_{t+1}$, $S\_{t+1}$
2. Choose $A\_{t+1}$ using $S\_{t+1}$ in our policy
3. $Q(S\_t, A\_t) = Q(S\_t, A\_t) + \alpha [R\_{t+1} + \gamma Q(S\_{t+1},A\_{t+1}) - Q(S\_t, A\_t)]$

Now, in Q-learning we replace $Q(S\_{t+1},A\_{t+1})$ in line 3 with $\max\_aQ(S\_{t+1},a)$. Recall that in SARSA we chose our $A\_{t+1}$ using our policy $\pi$ - if our policy is greedy with respect to the action value function then this simply means the policy is $\pi(a|s) = \text{argmax}\_aQ(s,a)$ which is exactly how we choose our weight update in Q-learning.

To answer the question - **no**, they are not *always* the same algorithm.

Consider where we transition from $s$ to $s'$ where $s'=s$. I will outline the updates for SARSA and Q-learning indexing the $Q$ functions with $t$ to demonstrate the difference.

For each case, I will assume we are at the start of the episode, as this is the easiest way to illustrate the difference. Note that actions denoted by $A\_i$ are for actions taken explicitly in the environment -- in the Q-Learning update the $\max$ action that is chosen for the update is not executed in the environment, the action taken in the environment is chosen by the policy after the update has happened.

**SARSA**

1. We initialise $S\_0 = s$ and choose $A\_0 = \text{argmax}\_a Q\_0(s,a)$
2. Take action $A\_0$ and observe $R\_{1}$ and $S\_{1} = s' = s$.
3. Choose action $A\_{1} = \text{argmax}\_aQ\_{0}(s,a)$
4. $Q\_{1}(S\_0,A\_0) = Q\_0(S\_0,A\_0) + \alpha [R\_{1} + \gamma Q\_0(s,A\_1) - Q\_0(S\_0,A\_0)]$

**Q-Learning**

1. Initialise $S\_0 = s$
2. Choose action $A\_0 = \text{argmax}\_aQ\_0(s,a)$, observe $R\_{1}, S\_{1} = s' = s$
3. $Q\_{1}(S\_0,A\_0) = Q\_0(S\_0,A\_0) + \alpha [R\_{1} + \gamma \max\_aQ\_0(s,a) - Q\_0(S\_0,A\_0)]$
4. Choose action $A\_1 = \text{argmax}\_aQ\_1(s,a)$

As you can see the next action for the updates in SARSA (line 4) and Q-learning (line 3) are taken with respect to the same $Q$ function, *but the key difference is that the actual next action taken in $Q$-learning is taken with respect to the updated $Q$-function*.

The key for understanding this edge case is that when we transition into the same state, **the Q-Learning update will update the Q-function before choosing $A\_1$**. I have indexed actions and Q-functions by the episode step - hopefully, it makes sense why I have done this for the Q-functions as, usually, this would not make sense, but, because we have two successive states that are the same, it is okay.

> **Comments:**
> **username_2**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/116995/discussion-on-answer-by-david-ireland-are-q-learning-and-sarsa-the-same-when-act).  

---

### Answer by username_4 on 2024-04-16. Score: 0

SARSA:
$$Q(S\_t,A\_t)=Q(S\_t,A\_t)+\alpha[R\_{t+1}+\gamma Q(S\_{t+1},A\_{t+1})-Q(S\_t,A\_t)]$$
Q-Learning
$$Q(S\_t,A\_t)=Q(S\_t,A\_t)+\alpha[R\_{t+1}+\gamma\max Q(S\_{t+1},a)-Q(S\_t,A\_t)]$$

Consider the following case:
For both SARSA and Q-Learning we'll randomly select $a\_1$, when $t=1, t=2$, and assume $\alpha R\_2 > 0$

SARSA
At $t=2$ to determine $Q(S\_3,A\_3)$ since it's greedy it'll choose $s\_1,a\_1$ and the recalculate $Q(s\_1,a\_1)$
$$\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
(t,s,a, R) & Q(s\_1,a\_1) & Q(s\_1,a\_2) \\ \hline
& 0 & 0 \\ \hline
(1,s\_1,a\_1, R\_2) & \alpha R\_2 & 0\\ \hline
(2,s\_1,a\_1, R\_3) & \alpha R\_2 + \alpha R\_3 +\alpha^2\gamma R\_2 -\alpha^2R\_2& 0 \\\hline
(3,s\_1,a\_1, R\_4) & & 0\\ \hline
\end{array}$$

Q-Learning, at $t=2$ to determine $Q(S\_3,A\_3)$, it'll first evaluate the policies so inorder to pick $Q(s\_1,a\_1)$
$$\alpha R\_2 + \alpha R\_3 +\alpha^2\gamma R\_2 -\alpha^2R\_2 > 0$$
$$R\_2 + R\_3 +\alpha\gamma R\_2 -\alpha R\_2 > 0$$
$$-R\_2(-1-\alpha\gamma + \alpha) + R\_3 > 0$$
$$R\_3 > R\_2(\alpha-\alpha\gamma-1)$$

$$\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
(t,s,a) & Q(s\_1,a\_1) & Q(s\_1,a\_2) \\ \hline
& 0 & 0 \\ \hline
(1,s\_1,a\_1, R\_2) & \alpha R\_2 & 0\\ \hline
(2,s\_1,a\_1, R\_3) & \alpha R\_2 + \alpha R\_3 +\alpha^2\gamma R\_2 -\alpha^2R\_2& 0 \\\hline
(3,s\_1,a\_1, R\_4) & & \\\hline
\end{array}$$


---

