Why no falling off cliff in SARSA for the example in Sutton-Barto?

Sutton-Barto, page 132:

The graph to the right shows the performance of the Sarsa and Qlearning methods with "-greedy action selection, " = 0.1. After an initial transient, Q-learning learns values for the optimal policy, that which travels right along the edge of the cli↵. Unfortunately, this results in its occasionally falling o↵ the cli↵ because of the "-greedy action selection. Sarsa, on the other hand, takes the action selection into account and learns the longer but safer path through the upper part of the grid.

SARSA is also using $$\epsilon$$-greedy and hence falling off cliff may happen with the same reasoning done for the Q-learning. I did not understand why this (falling off cliff) does not happen in SARSA.

I think the point here is that Q-learning may learn the optimal policy or value function faster. The optimal policy is to choose actions that are close to the cliff, but, during learning, to behave, you still use the $$\epsilon$$-greedy policy which is based on the (near-)optimal value function, so you may occasionally fall off the cliff. SARSA may learn a different value function, which during learning doesn't make the agent fall off the cliff as often. If we were not learning, and Q-learning had found the optimal policy, it would always act greedily, so it would not fall off the cliff (assuming the optimal policy doesn't do that).

• Can you explain or rephrase the last sentence ? "If we were not learning, and Q-learning had found the optimal policy, it would always act greedily, so it would not fall off the cliff (assuming the optimal policy doesn't do that). " Commented May 6 at 15:25
• @DSPinfinity After learning, Q-learning will not use the $\epsilon$-greedy policy to behave but it will use a deterministic policy derived from $q(s, a)$ that it's learned. That deterministic policy is simply $a^* = \text{argmax}_a q(s, a)$, i.e. it chooses the greedy action. If Q-learning has learned the optimal $q$, then it has also learned the optimal policy. Now, that optimal policy should not take actions that make you fall off the cliff, because that's probably not optimal, but it will take actions that are close to the cliff (because we know that's the optimal policy).
– nbro
Commented May 6 at 16:13
• @DSPinfinity Yes, $\epsilon$-greedy is used to select actions, but only during learning. Q-learning is a learning algorithm, i.e. it's trying to learn a value function $q$, from which you can derive the policy, which is not the behaviour policy you use during learning, but is the greedy policy with respect to $q$, i.e. $a^* = \text{argmax} q(s, a)$. So, after learning, you will not be using the $\epsilon$-greedy but $a^* = \text{argmax} q(s, a)$, which is the target policy and it's optimal if the learned $q$ is also optimal, assuming finite MDPs.
– nbro
Commented May 7 at 0:37
• So, the reason why you use $\epsilon$-greedy during learning, instead of the target policy, is because, during learning, $q$ is typically not optimal (at least at the beginning of learning), so you need to explore (i.e. sometimes randomly choose actions) and sometimes you need to exploit (i.e. choose the best action according to your current estimate of $q$). This is one of the most important concepts in RL: the exploration-exploitation tradeoff.
– nbro
Commented May 7 at 0:46
• So, you can't just use a greedy (deterministic) policy during learning, because $q$ may not be optimal, and you shouldn't use a stochastic policy after learning in finite MDPs if the learned $q$ is optimal, because there's a known result in RL that says that there's at least one optimal policy that is deterministic in finite MDPs. If you don't know the difference between stochastic and deterministic policies, see ai.stackexchange.com/q/12274/2444
– nbro
Commented May 7 at 0:46