SARSA: The On-Policy Algorithm That Learns to Play It Safe

The core idea: bootstrap off the action you're actually going to take

SARSA is a temporal-difference (TD) control algorithm. It estimates the action-value function Q(s, a) — the expected discounted return from taking action a in state s and following the current policy thereafter — and improves the policy by acting greedily (mostly) with respect to those estimates. Like all TD methods it bootstraps: it updates an estimate toward a target built from another estimate, rather than waiting for a full Monte-Carlo return.

The whole algorithm lives in one update rule. After the agent observes the transition (S, A, R, S′) and then chooses its next action A′ from its policy, it applies:

Q(S,A) ← Q(S,A) + α·[ R + γ·Q(S′,A′) − Q(S,A) ]

The bracketed term is the TD error δ = R + γ·Q(S′,A′) − Q(S,A). The quintuple (S, A, R, S′, A′) is exactly what the update consumes — hence the name. The on-policy invariant is the load-bearing detail: the A′ inside the target is the same action the agent will execute on the next step, drawn from the same ε-greedy behavior policy the agent is following. SARSA therefore evaluates and improves the policy it actually uses, exploration and all. Q-learning, by contrast, replaces Q(S′,A′) with max_a Q(S′,a) — the value of the greedy action, which it may never take — and so learns about a different policy than the one generating its data.

How it works, step by step

Tabular SARSA maintains a table Q[s][a] and runs the classic generalized-policy-iteration loop, interleaving evaluation and improvement on every single step:

• Initialize Q(s, a) arbitrarily for all s, a (often 0, or optimistically high to encourage exploration); set Q(terminal, ·) = 0.
• Per episode: observe start state S; choose A from S using a policy derived from Q (e.g. ε-greedy: argmax with prob 1−ε, random with prob ε).
• Per step: take action A, observe reward R and next state S′.
• Choose the next action A′ from S′ using the same ε-greedy policy — this sampling is what makes it on-policy.
• Apply the update Q(S,A) ← Q(S,A) + α·[R + γ·Q(S′,A′) − Q(S,A)].
• Advance: S ← S′, A ← A′. Repeat until S is terminal.

The critical ordering detail that trips up implementers: you must select A′ before the update and then reuse it as the action for the next iteration. If you resample a fresh action after updating, you've broken the on-policy coupling and are computing garbage. Here is the inner loop in pseudocode:

A ← ε_greedy(Q, S)
while S is not terminal:
    R, S′ ← env.step(A)
    A′ ← ε_greedy(Q, S′)          # sample the ACTUAL next action
    δ  ← R + γ·Q[S′][A′] − Q[S][A]
    Q[S][A] ← Q[S][A] + α·δ
    S, A ← S′, A′                  # carry A′ forward — do not resample

Complexity analysis

Per-step time: O(1) for the update itself — a single array read, an arithmetic combination, and a write. The only non-constant cost is action selection: computing argmax over the action set for ε-greedy is O(|A|). SARSA calls it once per step (Q-learning also does the argmax once for its max target plus once for action selection, but asymptotically both are O(|A|) per step). So a full run of E episodes averaging L steps each is O(E·L·|A|) time — and if |A| is small and fixed, effectively O(E·L).

Space: O(|S|·|A|) for the dense Q-table, independent of episode count. This is the binding constraint. Cliff Walking's 48 states × 4 actions = 192 entries is trivial; but the table grows with the product of the state and action cardinalities, and for continuous or high-dimensional states it becomes intractable — the curse of dimensionality. That is precisely why function approximation (linear features, tile coding, or neural nets in Deep SARSA) replaces the table, trading exactness for O(d) parameters where d ≪ |S|·|A|.

Convergence. Tabular SARSA converges to the optimal action-value Q* with probability 1 under two conditions: (1) the Robbins–Monro step-size schedule Σαₜ = ∞ and Σαₜ² < ∞, and (2) the policy is GLIE — Greedy in the Limit with Infinite Exploration — meaning every state-action pair is visited infinitely often and the policy becomes greedy asymptotically (e.g. ε decaying as 1/t). Under a fixed ε, SARSA converges instead to the optimal ε-greedy policy — the best policy that is still forced to explore — which is exactly why it stays off the cliff.

The trade-off: why on-policy learns a safer policy

The Cliff Walking result (Sutton & Barto, Example 6.6) is the textbook demonstration and worth internalizing. With fixed ε = 0.1:

• Q-learning bootstraps off max_a Q(S′,a), which assumes it will act greedily next. So it values the cliff-edge path at its optimal cost and walks it. But during training, ε-forced random actions occasionally send it over the edge for −100. Its online reward is poor even as its learned greedy policy is optimal.
• SARSA bootstraps off the action it will really take — which, 10% of the time, is a random step. States adjacent to the cliff therefore inherit the risk of a random plunge into their Q-values. SARSA learns those cells are dangerous given how it actually behaves and routes around them, earning a higher online return.

The takeaway: SARSA optimizes the policy it executes; Q-learning optimizes the policy it will eventually execute once exploration stops. When learning happens online in the real world and mistakes are expensive — a robot near a ledge, a trading system, a live recommender — SARSA's conservatism is a feature, not a bug. When you can train in a safe simulator and only deploy the final greedy policy, Q-learning's directness usually wins. As ε → 0 the two algorithms' targets coincide and both converge to Q*.

Where SARSA is used, and its close relatives

SARSA is a foundational algorithm in every RL curriculum and library — it appears in Sutton & Barto's Reinforcement Learning: An Introduction as the archetypal on-policy TD control method, and reference implementations ship in teaching frameworks and gymnasium/OpenAI-Gym tutorials. In practice it shows up wherever online, risk-sensitive control matters and where you want the value function to reflect the exploratory behavior actually deployed. Its important variants:

• Expected SARSA — replaces the sampled Q(S′,A′) with the expectation Σₐ π(a|S′)Q(S′,a) over the policy. This eliminates the variance from randomly sampling A′, so it learns faster and more stably at the cost of O(|A|) per update. With a greedy target policy it becomes Q-learning — the two are the same algorithm viewed through different target policies.
• SARSA(λ) — adds eligibility traces, a decaying memory (parameter λ ∈ [0,1]) of recently visited state-action pairs, so a single TD error updates many prior states at once. It interpolates between one-step SARSA (λ=0) and Monte-Carlo control (λ=1), typically accelerating credit assignment dramatically. Space grows to O(|S|·|A|) for the trace vector.
• n-step SARSA — looks n rewards ahead before bootstrapping, trading bias for variance between TD(0) and Monte Carlo.
• Deep SARSA — swaps the table for a neural network Q(s, a; θ), updated by gradient descent on the on-policy TD error; the on-policy target sidesteps some of the deadly-triad instabilities that plague off-policy DQN.

Pitfalls, edge cases, and common bugs

SARSA looks like a two-line change to Q-learning, and that resemblance breeds subtle errors:

• Resampling A′ after the update. The single most common bug. You must carry the A′ you used in the target forward as the next step's action. Sampling a fresh action instead silently converts the algorithm into a broken hybrid that is neither correct SARSA nor Q-learning.
• Wrong terminal handling. On a terminal transition there is no A′; the target must be just R (equivalently Q(terminal, ·) ≡ 0). Bootstrapping off a nonzero terminal value corrupts every state that reaches the goal — a bug that quietly ruins convergence.
• Fixed ε forever. With constant ε, SARSA converges to the optimal ε-greedy policy, not to Q*. If you actually want optimal control you must satisfy GLIE by decaying ε (and typically α) over time. Many students report SARSA "underperforms" when they simply never annealed exploration.
• Learning rate too high. Because SARSA's target contains a randomly sampled A′, its target has higher variance than Q-learning's deterministic max. A large α amplifies that noise and can cause divergence or oscillation; this is exactly the variance Expected SARSA removes.
• Function approximation instability. Even though on-policy learning is safer than off-policy, combining bootstrapping with non-linear approximation still risks the deadly triad; monitor the TD error and use small, decaying step sizes.

SARSA vs Q-learning vs Expected SARSA — the on-policy/off-policy axis and its consequences

Property	SARSA	Q-learning	Expected SARSA
Policy class	On-policy	Off-policy	Off- or on-policy
TD target	R + γ·Q(S′,A′)	R + γ·max_a Q(S′,a)	R + γ·Σ π(a|S′)Q(S′,a)
Uses A′ sampled?	Yes (the actual next action)	No (max over actions)	No (expectation over π)
Update cost	O(1)	O(|A|) for the max	O(|A|) for the sum
Converges to	π-optimal (safe under ε)	Optimal Q* directly	Same as Q-learning target
Variance	Higher (samples A′)	Lower (deterministic max)	Lowest (averages out A′)