Why would SARSA diverge (but not Expected SARSA or Q-learning)?

Question

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).

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.

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 of instances where there is a problem of diverging Q values in DQNs)?

The majority of papers I have looked at only talk about the problem from the function approximation perspective.

Answer 1

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.

"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.