SARSA, Expected SARSA, and TD(λ): The Classical Foundations of Temporal-Difference Control

TL;DR

Before DQN, before Rainbow, there was SARSA — the on-policy sibling of Q-learning, which updates toward the value of the action actually taken next rather than the best possible action. Expected SARSA reduces variance by averaging over all next actions weighted by their probability under the policy instead of sampling just one. TD(λ), combined with eligibility traces, generalizes both one-step TD updates and full Monte Carlo returns into a single tunable spectrum, propagating a reward signal backward through recently visited states in one pass instead of waiting for repeated bootstrapping. These are the classical building blocks every deep RL method in the companion Q-learning and actor-critic articles on this site inherits its update rules from.

The On-Policy TD Control Lineage

graph LR
    A[SARSA] --> B[Expected SARSA: average over next actions]
    B --> C[TD-lambda + Eligibility Traces: tunable credit horizon]

    style C fill:#6366f1,color:#fff

Problem Statement

Q-learning is off-policy: its update bootstraps off max_a Q(s', a), the value of the greedy action, regardless of what the agent actually does next. That’s powerful, but it means Q-learning’s target doesn’t reflect the actual behavior policy — including its exploration. Sometimes you want a control algorithm whose value estimates match the policy actually being followed, exploration noise and all. That’s what SARSA and its variants provide, and TD(λ) provides an orthogonal upgrade: how far into the future should a single update look before bootstrapping?

SARSA: On-Policy TD Control

SARSA takes its name from the quintuple it needs for an update: State, Action, Reward, next State, next Action. Unlike Q-learning’s max, it bootstraps off the value of the action the policy actually takes next:

def sarsa_update(Q, s, a, r, s_next, a_next, alpha=0.1, gamma=0.99):
    td_target = r + gamma * Q[s_next][a_next]     # actual next action, not the max
    td_error = td_target - Q[s][a]
    Q[s][a] += alpha * td_error
    return Q

Because it’s on-policy, SARSA learns the value of the policy it’s actually following — including the risk introduced by its own exploration. The textbook illustration is the “cliff walking” gridworld: SARSA learns a safer, longer path away from a cliff edge because it accounts for the chance that epsilon-greedy exploration might randomly step off the edge near it, while Q-learning’s greedy bootstrap learns the optimal-but-riskier path hugging the cliff, since it never accounts for its own exploration noise in the target.

Expected SARSA: Averaging Away Sampling Noise

SARSA’s target depends on whichever single next action happened to be sampled, which adds variance on top of the environment’s own randomness. Expected SARSA replaces that one sample with the full expectation over the policy’s action distribution:

def expected_sarsa_update(Q, s, a, r, s_next, policy_probs, alpha=0.1, gamma=0.99):
    expected_next_value = sum(policy_probs[a2] * Q[s_next][a2] for a2 in Q[s_next])
    td_target = r + gamma * expected_next_value
    td_error = td_target - Q[s][a]
    Q[s][a] += alpha * td_error
    return Q

This is strictly lower-variance than SARSA for the same on-policy guarantee, at the cost of a sum over the action space each update — cheap for small discrete action spaces, and it elegantly unifies with Q-learning: if you make the policy fully greedy, Expected SARSA’s target collapses exactly to Q-learning’s max.

TD(λ) and Eligibility Traces: How Far Should an Update Look?

One-step TD methods (SARSA, Q-learning as usually presented) bootstrap after a single step; Monte Carlo methods wait for a full episode’s actual return. TD(λ) interpolates between these two extremes with a single parameter λ ∈ [0, 1], using eligibility traces — a decaying memory of which states were recently visited — so a single reward, when it arrives, can update all recently visited states in one pass rather than propagating backward one slow update at a time.

def sarsa_lambda_update(Q, eligibility, s, a, r, s_next, a_next, alpha=0.1, gamma=0.99, lam=0.9):
    td_error = r + gamma * Q[s_next][a_next] - Q[s][a]
    eligibility[s][a] += 1   # mark this state-action as "responsible" for what happens next

    for state in Q:
        for action in Q[state]:
            Q[state][action] += alpha * td_error * eligibility[state][action]
            eligibility[state][action] *= gamma * lam   # decay traces every step

    return Q, eligibility

λ = 0 recovers plain one-step SARSA (only the most recent state-action gets updated); λ = 1 recovers a Monte-Carlo-like update where credit flows all the way back through an entire episode. Intermediate values trade off the low variance of bootstrapping against the low bias of waiting for real returns — and critically, TD(λ) gets this trade-off without needing to wait until an episode ends, since the eligibility trace lets a single reward retroactively update every recently visited state immediately.

Comparison Table

Applications

• Safety-conscious control problems — SARSA’s on-policy accounting for exploration risk is preferable whenever the training policy’s actual (not idealized) behavior matters, such as robotics where the exploring policy runs on real hardware.
• Classical game-playing agents — TD(λ) was the algorithm behind TD-Gammon, one of the earliest and most influential successful applications of RL, which reached near-expert backgammon play.
• Any tabular or small-state RL problem — these methods remain the simplest, most interpretable starting point for a new RL problem before reaching for function approximation.
• Foundational teaching and debugging tool — because these updates are simple enough to trace by hand, they’re the standard way to sanity-check that a more complex deep RL implementation’s core update logic is correct.

Key Learnings

1. On-policy vs. off-policy is a design choice with real consequences, not just a technical footnote. SARSA’s willingness to account for its own exploration risk in its value estimates, versus Q-learning’s assumption of eventual greedy behavior, changes what “optimal” even means during training.
2. Eligibility traces solve the “how far back should credit propagate” problem in one clean mechanism. Rather than choosing a fixed n-step horizon (as in the multi-step Q-learning extension covered in the companion Rainbow article), TD(λ) provides a continuously tunable dial via a single decay parameter.
3. Every deep RL method on this site is a descendant of these update rules. DQN’s TD target is Q-learning’s; the actor-critic family’s critic loss is a TD update; understanding SARSA and TD(λ) by hand is what makes the deep variants’ design choices legible rather than arbitrary.

References

• Rummery, G., Niranjan, M. (1994). On-Line Q-Learning Using Connectionist Systems. Technical Report, Cambridge University Engineering Department.
• Sutton, R. (1988). Learning to Predict by the Methods of Temporal Differences. Machine Learning, 3.
• Tesauro, G. (1995). Temporal Difference Learning and TD-Gammon. Communications of the ACM, 38(3).