Why Q-Learning Falls Off the Cliff More Than SARSA
The classic "Cliff Walking" gridworld: an agent starts at one corner of a grid and must reach a goal in the opposite corner. A row of cells along the bottom edge is a cliff — stepping into it gives a reward of -100 and sends the agent back to start. Every other step costs -1. The shortest path runs directly along the cliff edge; a longer, safer path stays one row away from it.
You train two agents on this task with the same \varepsilon-greedy exploration schedule (\varepsilon = 0.1 throughout, never annealed): one with tabular Q-learning, one with tabular SARSA. Both eventually converge to stable value estimates.
During training itself — while \varepsilon-greedy exploration is still active and both agents are still occasionally taking random actions — which agent earns the higher average reward per episode?
SARSA — it accounts for exploration risk in its value estimates.
Q-learning's update bootstraps off \max_{a'} Q(s',a') — the value of the best action in the next state, regardless of what the \varepsilon-greedy policy will actually do next. This makes it learn the value of the greedy, edge-hugging path as if the agent will always act optimally from here on. It converges to exactly that: the shortest route, one cell from the cliff.
SARSA's update instead bootstraps off Q(s', a'_{\text{actual}}) — the value of whatever action the behavior policy genuinely takes next, including its \varepsilon chance of a random step. Hugging the cliff edge under a policy that occasionally acts randomly means an occasional random step is a plunge into the cliff. SARSA's value estimates price that risk in, so it learns to prefer the safer, longer path one row further away — objectively "sub-optimal" for a purely greedy policy, but genuinely better for the exploring policy that is actually running.
The result, reported in Sutton & Barto's original treatment of this exact experiment: Q-learning converges to the optimal (edge-hugging) policy, but during training — with \varepsilon-greedy exploration still on — it falls off the cliff often enough that its online reward per episode is lower than SARSA's. SARSA never learns the "objectively optimal" path at all, and outperforms Q-learning on the metric that actually matters while training is happening.
The general lesson: off-policy learning (Q-learning) optimizes for "value under the greedy policy," which is what you deploy at the end, not what generates the data along the way — on-policy learning (SARSA) optimizes for the policy that's actually running right now. If online performance during learning matters (a robot that can't afford to fall off cliffs while training), that argues for on-policy methods, or for annealing \varepsilon toward zero so the two converge in behavior.
Share this question