Answers.Body: <p>I think a useful piece of information to answer this question is a representation of the safe and optimal policies that can be learned on the cliff grid world. SARSA learns the safe path while Q-learning (and on the long run also Expected SARSA) learns the optimal path.
  The reason lies in how the different algorithms select the next action.</p>
  <p><a href="https://i.sstatic.net/Keq0R.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Keq0R.png" alt="enter image description here" /></a></p>
  <p>&quot;<em>shouldn't Q-learning be at greater risk of diverging Q values since in it's update, we maximise over actions</em>&quot;</p>
  <p>This is actually the reason why Q-learning doesn't suffer of divergence issues in this simple world. Choosing always the action that maximize the reward is what allows Q-learning to learn <em>directly</em> the optimal policy. And you can see it on the graphs, the learning rate alpha doesn't really affect the final performance in the 50k runs case.</p>
  <p>The same logic applies to Expected SARSA. Remember that SARSA choose a random action, while Expected SARSA take the reward expected value into account, which makes Expected SARSA closer to Q-learning than SARSA itself.</p>
  <p>-SARSA <span class="math-container">$$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}) + \alpha((r_{t+1}) + \gamma max_{a} Q(s_{t+1}, a) - Q(s_{t}, a_{t}))
  $$</span>
  -Expected SARSA <span class="math-container">$$Q(s_{t}, a_{t}) + \alpha((r_{t+1}) + \gamma \sum_{a} \pi(a | s_{t+1}) Q(s_{t+1}, a) - Q(s_{t}, a_{t}))
  $$</span></p>
  <p>This still doesn't explain why SARSA fails with high learning rates though. To answer that we just need to combine in a different light what we already said:</p>
  <ul>
  <li>SARSA is not designed to depend on high future rewards</li>
  <li>SARSA prefers policies that minimize risks</li>
  </ul>
  <p>Combine these 2 points with a high learning rate, and it's not hard to imagine an agent struggling to learn that there is a goal cell G after the cliff, cause the high learning rate keeps giving high value to each random move action that keep the agent in the grid. Unfortunately for the agent, moving randomly gives you rewards but it also increase the chances of falling into the cliff. A small learning rate on the other hand push down the value of each action that simply keep you in the grid, and gives more change to SARSA to learn that the action of going down in the cell up to the bottom right corner is actually the real deal.</p>
  <p>Hope this gives a bit more clarity, I suggest to maybe try to use some of the umpteenth noteboooks out there to visualize the policies learned by the algorithms, which is much more insightful than simply looking at graphs, even though is understandable that authors focus on the latter.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-03T12:51:53.307Z
Answers.Text: "and on the long run also Expected SARSA" $\rightarrow$ Expected SARSA is learning the safe path from the graphs (scoring around -20), because there is no decay of $\epsilon$ in the experiment. It won't learn the optimal path in the long run in this experiment. The fixed $\epsilon$ is also evident in Q-learning's results. If $\epsilon$ were to decay, then Expected SARSA and Q-learning would end up with identical performance on the optimal policy. But that's not what the comparison is trying to show.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-03T11:59:07.303Z
Answers.LastActivityDate: 2021-11-03T12:05:42.533Z
Answers.LastEditDate: 2021-11-03T12:05:42.533Z
Answers.UserDisplayName: Edoardo Guerriero
Body: <p>In figure 6.3 (shown below) from Reinforcement Learning: An Introduction (second edition) by Sutton and Barto, SARSA is shown to perform worse asymptotically (after 100k episodes) than in the interim (after 100 episodes) for larger values of alpha (alpha &gt; 0.9). The graph is for the cliff walking gridworld example whose description is also given (from the paper by van Seijen et al).</p>
  <p><a href="https://i.sstatic.net/GDH0C.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GDH0C.png" alt="Cliff Walking" /></a></p>
  <p><a href="https://i.sstatic.net/h5d6p.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/h5d6p.png" alt="Figure 6.3 Sutton and Barto (second edition)" /></a></p>
  <p>As the image mentions, the image is taken from a paper by van Seijen and others titled &quot;A Theoretical and Empirical Analysis of Expected Sarsa&quot;. In the image below from the van Seijen paper from Section VII A Discussion, the authors mention that the reason for the better interim performance of SARSA as compared to its asymptotic performance for larger values of alpha, is the divergence of Q-values. The authors, however, fail to mention the reason for the divergence.</p>
  <p><a href="https://i.sstatic.net/h82Gb.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/h82Gb.png" alt="van Seijen et al's explanantion" /></a></p>
  <p>What would be the reason that SARSA diverges but not Expected SARSA or Q-learning?</p>
  <p>According to me, SARSA might have a higher variance than Expected SARSA, but it should behave, on average, the same as Expected SARSA.</p>
  <p>Additionally, shouldn't Q-learning be at greater risk of diverging Q values since, in its update, we maximise over actions (and I have in fact seen a <a href="https://datascience.stackexchange.com/questions/22163/why-does-q-learning-diverge">number</a> of <a href="https://arxiv.org/abs/1903.08894" rel="nofollow noreferrer">instances</a> where there is a problem of diverging Q values in DQNs)?</p>
  <p>The <a href="https://arxiv.org/abs/1107.4606" rel="nofollow noreferrer">majority</a> of <a href="https://link.springer.com/chapter/10.1007/978-3-540-30115-8_44" rel="nofollow noreferrer">papers</a> I have looked at only talk about the problem from the function approximation perspective.</p>
  
Tags: <reinforcement-learning><q-learning><sutton-barto><sarsa><expected-sarsa>
Title: Why would SARSA diverge (but not Expected SARSA or Q-learning)?
UserDisplayName: Quantum Sphinx
ThreadText: # Why would SARSA diverge (but not Expected SARSA or Q-learning)?
  
  (Asked by: username_0 on 2021-11-03)
  
  In figure 6.3 (shown below) from Reinforcement Learning: An Introduction (second edition) by Sutton and Barto, SARSA is shown to perform worse asymptotically (after 100k episodes) than in the interim (after 100 episodes) for larger values of alpha (alpha > 0.9). The graph is for the cliff walking gridworld example whose description is also given (from the paper by van Seijen et al).
  
  [![Cliff Walking](https://i.sstatic.net/GDH0C.png)](https://i.sstatic.net/GDH0C.png)
  
  [![Figure 6.3 Sutton and Barto (second edition)](https://i.sstatic.net/h5d6p.png)](https://i.sstatic.net/h5d6p.png)
  
  As the image mentions, the image is taken from a paper by van Seijen and others titled "A Theoretical and Empirical Analysis of Expected Sarsa". In the image below from the van Seijen paper from Section VII A Discussion, the authors mention that the reason for the better interim performance of SARSA as compared to its asymptotic performance for larger values of alpha, is the divergence of Q-values. The authors, however, fail to mention the reason for the divergence.
  
  [![van Seijen et al's explanantion](https://i.sstatic.net/h82Gb.png)](https://i.sstatic.net/h82Gb.png)
  
  What would be the reason that SARSA diverges but not Expected SARSA or Q-learning?
  
  According to me, SARSA might have a higher variance than Expected SARSA, but it should behave, on average, the same as Expected SARSA.
  
  Additionally, shouldn't Q-learning be at greater risk of diverging Q values since, in its update, we maximise over actions (and I have in fact seen a [number](https://datascience.stackexchange.com/questions/22163/why-does-q-learning-diverge) of [instances](https://arxiv.org/abs/1903.08894) where there is a problem of diverging Q values in DQNs)?
  
  The [majority](https://arxiv.org/abs/1107.4606) of [papers](https://link.springer.com/chapter/10.1007/978-3-540-30115-8_44) I have looked at only talk about the problem from the function approximation perspective.
  
  **Tags:** reinforcement-learning, q-learning, sutton-barto, sarsa, expected-sarsa
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-11-03. Score: 2
  
  I think a useful piece of information to answer this question is a representation of the safe and optimal policies that can be learned on the cliff grid world. SARSA learns the safe path while Q-learning (and on the long run also Expected SARSA) learns the optimal path.
  The reason lies in how the different algorithms select the next action.
  
  [![enter image description here](https://i.sstatic.net/Keq0R.png)](https://i.sstatic.net/Keq0R.png)
  
  "*shouldn't Q-learning be at greater risk of diverging Q values since in it's update, we maximise over actions*"
  
  This is actually the reason why Q-learning doesn't suffer of divergence issues in this simple world. Choosing always the action that maximize the reward is what allows Q-learning to learn *directly* the optimal policy. And you can see it on the graphs, the learning rate alpha doesn't really affect the final performance in the 50k runs case.
  
  The same logic applies to Expected SARSA. Remember that SARSA choose a random action, while Expected SARSA take the reward expected value into account, which makes Expected SARSA closer to Q-learning than SARSA itself.
  
  -SARSA $$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}) + \alpha((r\_{t+1}) + \gamma max\_{a} Q(s\_{t+1}, a) - Q(s\_{t}, a\_{t}))
  $$
  -Expected SARSA $$Q(s\_{t}, a\_{t}) + \alpha((r\_{t+1}) + \gamma \sum\_{a} \pi(a | s\_{t+1}) Q(s\_{t+1}, a) - Q(s\_{t}, a\_{t}))
  $$
  
  This still doesn't explain why SARSA fails with high learning rates though. To answer that we just need to combine in a different light what we already said:
  
  * SARSA is not designed to depend on high future rewards
  * SARSA prefers policies that minimize risks
  
  Combine these 2 points with a high learning rate, and it's not hard to imagine an agent struggling to learn that there is a goal cell G after the cliff, cause the high learning rate keeps giving high value to each random move action that keep the agent in the grid. Unfortunately for the agent, moving randomly gives you rewards but it also increase the chances of falling into the cliff. A small learning rate on the other hand push down the value of each action that simply keep you in the grid, and gives more change to SARSA to learn that the action of going down in the cell up to the bottom right corner is actually the real deal.
  
  Hope this gives a bit more clarity, I suggest to maybe try to use some of the umpteenth noteboooks out there to visualize the policies learned by the algorithms, which is much more insightful than simply looking at graphs, even though is understandable that authors focus on the latter.
  
  > **Comments:**
  > **username_2**: "and on the long run also Expected SARSA" $\rightarrow$ Expected SARSA is learning the safe path from the graphs (scoring around -20), because there is no decay of $\epsilon$ in the experiment. It won't learn the optimal path in the long run in this experiment. The fixed $\epsilon$ is also evident in Q-learning's results. If $\epsilon$ were to decay, then Expected SARSA and Q-learning would end up with identical performance on the optimal policy. But that's not what the comparison is trying to show.  
  
  ---
  
  