Learn the value of the policy you actually play — exploration and all. The update reads state, action, reward, state, action: it bootstraps on a′, the action the ε-greedy policy is really about to take, not on the best action it could have taken. Down the center, data flows: the transition goes in, the on-policy TD update fires, the evaluated value comes out. The blue team builds and defends it; the red team tries to turn it into something it is not.
source Rummery & Niranjan, On-line Q-learning Using Connectionist Systems, Cambridge Univ. Eng. Dept. tech report CUED/F-INFENG/TR 166 (1994) — mi.eng.cam.ac.uk/reports/…/rummery_tr166 AMBER tech report, no DOI/arXiv. Rendered, not quoted.
One rule, computed live, never looked up:
Q(s,a) ← Q(s,a) + α [ r + γ Q(s′,a′) − Q(s,a) ]
a′ is the action the behavior policy actually selects in s′ — so the target carries the cost of exploration. Its fixed point is Qπ: the true value of the policy being followed, since at Q=Qπ the expected TD error is exactly 0.
Contrast Q-learning, which bootstraps on maxa Q(s′,a) — the best action, whether or not you take it. That difference is the whole sphere.
SARSA is the on-policy twin of the-q-learning. Same skeleton — a TD backup on a Q-table — but the bootstrap differs by a single term.
the-q-learning learns the greedy value no matter what it does; SARSA learns the value of what it truly plays, exploration included. On a cliff, Q-learning walks the edge and occasionally falls; SARSA learns the safer path because it accounts for its own ε-slips. One sphere is the other's premise.
The blue team's live check: re-solve Qπ and Q* from scratch and confirm the on-policy fixed point holds to 1e−9. If red swaps the bootstrap to max, this badge is where it shows.
A tiny deterministic MDP (a 2-step corridor, γ=0.9). State 2 is terminal. Each move feeds the engine a full tuple (s, a, r, s′, a′):
| s | a | → s′ | r |
|---|---|---|---|
| 0 | back | 0 | −1 |
| 0 | fwd | 1 | 0 |
| 1 | back | 0 | 0 |
| 1 | fwd | 2 □ | +10 |
Optimal is fwd→fwd. The hinge is a′: an ε-greedy player sometimes takes back in state 1, and SARSA must value that. Feed the tuple into the panel below.
Both targets are computed live from Qπ on the spot — the on-policy target uses your chosen a′, the off-policy target uses maxa. Never looked up.
What the machine produces, proven: the exact on-policy value Qπ of the ε-greedy policy (solved from the linear Bellman system) beside the optimal Q* (value iteration). At ε=0 they coincide; at ε>0 they part — the price of exploration, valued honestly.
| cell | Qπ(ε) | Q* | SARSA sim |
|---|
It also inherits every tabular limit — no generalization, deadly-triad instability once you add function approximation and bootstrapping (which is exactly why TR 166 pairs it with a neural net). SARSA is not the answer; it is the honest evaluation of the policy in your hand.
"SARSA and Q-learning converge to the same thing." Cut. Only when ε→0. At ε=0.5 here, Qπ(0,fwd)≈8.31 vs Q*=9 — computed in the panel, not asserted.
"SARSA is off-policy too, just slower." Cut. The defining difference is the bootstrap: a′ (followed) vs max (greedy). Swap it and it stops evaluating your policy — that is the tamper in window 6.
"The name is an acronym for the algorithm's inventor." Kept, corrected. SARSA = the tuple (s,a,r,s′,a′); coined by Rich Sutton, from Rummery & Niranjan's "modified connectionist Q-learning."
The red team's move: silently swap the bootstrap Q(s′,a′) for maxa Q(s′,a) — turning SARSA into off-policy Q-learning. It looks identical; it no longer evaluates the policy you follow. The witness (window 7) is watching.
Swap the bootstrap to max and the on-policy fixed-point residual at Qπ jumps off zero — the witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.