Why does SARSA learn a safe inland route while Q-learning hugs the cliff edge under the same epsilon-greedy exploration?

## The grid The cliff-walk is a small rectangular gridworld. Start is the bottom-left cell, goal the bottom-right, and the cells between them along the bottom row are **cliff**: entering one yields a reward of -100 and sends the agent straight back to start. Every other move yields -1, so the agent is being asked to reach the goal in as few steps as possible. The agent moves up, down, left or right, and acts epsilon-greedily: the current best action with probability `1 - epsilon`, a uniformly random action otherwise. The genuinely optimal path — the one that maximises return if you can execute your intentions perfectly — is to step up once, walk straight along the row directly above the cliff, and drop into the goal. Any inland detour costs extra -1 steps. ## What each method learns, and why **Q-learning.** Its target is `r + gamma * max_a' Q(s',a')`. Standing in a cell beside the cliff, the maximum is taken over the actions a *greedy* agent would consider best, and a greedy agent never walks into a -100 cell. The occasional exploratory fall does produce a real update — the specific pair (edge cell, step-down) is punished — but the value of the *good* actions in that cell is computed as if the agent will behave perfectly from the next step onward. So the edge cells retain high value, and Q-learning converges to the optimal action values `Q*` and the cliff-edge policy. **SARSA.** Its target is `r + gamma * Q(s',a')`, where `a'` is the action the epsilon-greedy policy actually selects. In an edge cell, with probability roughly `epsilon / 4` that action is the step into the cliff. That means the *value of being in an edge cell at all* absorbs a share of the -100, because the value being bootstrapped is the value of continuing to behave epsilon-greedily. Propagate that back a few cells and the inland route — one or two rows away from the cliff, where a random step is harmless — comes out ahead. SARSA is not being timid by construction; it is correctly evaluating a policy that fumbles a fraction of its moves. ## Neither one is wrong They answer different questions: - Q-learning answers "what is the best possible policy?" Its answer is right, and it is right even though the data was collected by a clumsy agent. - SARSA answers "what is my current, exploring agent worth, and how should it behave?" Its answer is also right, for that agent. The measurable consequence during training is the reverse of what people expect: **SARSA earns more reward per episode online than Q-learning**, because Q-learning keeps walking the edge and keeps falling in. The agent with the better learned policy has the worse learning experience. ## Which one do you ship? The decision hinges on how the agent is executed after training: - If exploration is switched off and you deploy the greedy policy, Q-learning's answer is the one you want, and SARSA's conservative route is needlessly long. In that setup you can also just decay epsilon toward zero during SARSA training: as exploration vanishes, the value being evaluated approaches the greedy one and SARSA converges to the same edge path. - If randomness persists at execution time — actuators that occasionally miss, a policy deliberately kept stochastic, an agent that keeps learning in the field — then SARSA's values are the honest description of what you will actually get, and its route is the better bet. - If a single fall is catastrophic rather than merely -100, the argument stops being about which value is more accurate: you should not be learning against a live cliff at all, and you would take the conservative policy regardless of the mathematics. ## A distinction that catches people out The safe-versus-optimal split is caused by **randomness in action selection**, not by randomness in the environment. If the grid had wind that pushed the agent sideways with some probability, that stochasticity sits inside the MDP's transitions, and *both* methods account for it in expectation — Q-learning's `Q*` would already price in the chance of being blown off the edge. Only the exploration noise is treated differently by the two targets. Candidates who blur these two sources of randomness usually reach the right conclusion for the wrong reason. ## Cheap diagnostics If you suspect this effect in your own agent, compare the greedy policy extracted from the table against the average return actually collected per episode. A method whose learned policy looks excellent while its online return is poor is telling you exactly this story: the values describe a policy the agent is not currently running.