Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-06T12:24:24.103Z
Answers.Text: 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).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-11T13:31:00.277Z
Answers.LastActivityDate: 2020-12-06T12:26:10.680Z
Answers.LastEditDate: 2020-12-06T12:26:10.680Z
Answers.UserDisplayName: David
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-16T16:33:38.007Z
Answers.LastActivityDate: 2024-04-16T16:33:38.007Z
Answers.UserDisplayName: Elliott de Launay
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-03T15:00:55.527Z
Comments.Text: This question is possibly a duplicate of https://stackoverflow.com/questions/32846262/are-q-learning-and-sarsa-with-greedy-selection-equivalent.
Comments.UserDisplayName: willtryagain
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-23T10:11:54.287Z
Comments.Text: @willtryagain The question on Stack Overflow is off-topic there.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><comparison><q-learning><sarsa><greedy-policy>
Title: Are Q-learning and SARSA the same when action selection is greedy?
UserDisplayName: hyuj
ThreadText: # 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-username_3-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}$$
  
  
  ---
  
  