Cliff Walking is Sutton & Barto's classic gridworld for comparing on-policy and off-policy temporal-difference control. A 4×12 grid has a start cell, a goal cell, and a row of "cliff" cells between them. Every step costs −1 reward; stepping into the cliff costs −100 and teleports the agent back to start (the episode continues). Both agents use ε-greedy action selection over the same four moves (up/down/left/right).
Q-Learning (off-policy TD control):
Q(s,a) ← Q(s,a) + α·[ r + γ·max_a' Q(s',a') − Q(s,a) ]
SARSA (on-policy TD control):
Q(s,a) ← Q(s,a) + α·[ r + γ·Q(s',a') − Q(s,a) ]
where a' is the action ε-greedy policy actually takes next
The difference is subtle but produces famously different behaviour: Q-Learning bootstraps off the greedy next action regardless of what the exploring policy will actually do, so it learns the value of the optimal (risky) path hugging the cliff edge — but because it still explores with ε-greedy during training, it occasionally falls off, which shows up as a lower (more negative) total training reward. SARSA bootstraps off the action its own ε-greedy policy will really take, so it "knows" it might slip near the cliff and learns a longer, safer route further away. Watch the two heat-maps and policy-arrow fields diverge as episodes accumulate, and the reward curves below each grid show SARSA converging to a smoother, higher per-episode return during training even though its final learned path is longer than Q-Learning's.
- ε (exploration) — probability of taking a random action instead of the greedy one. Raise it to see both agents fall off the cliff more often.
- α (learning rate) — how much each TD error updates a Q-value. Higher α learns faster but noisier.
- γ (discount) — how much future reward matters relative to immediate reward.
- Policy arrows — for every non-terminal cell, the arrow points toward argmax_a Q(s,a): each agent's currently-greedy action from that cell.
- Reset agents — clears both Q-tables and restarts both agents at episode 0.