Temporal Difference — Q-Learning & SARSA

Monte Carlo works, but it makes two expensive demands: it needs episodes that terminate, and it won't update anything until the final return is in. Run a 1,000-step episode and MC waits all 1,000 steps before touching a single value. That's high-variance, low-bias, and slow in practice.

Dynamic programming has the opposite profile. Its backups are zero-variance and bootstrapped, but only because it assumes a known model of the environment, which most real problems don't hand you.

Temporal difference (TD) learning splits the difference. From a single transition (s, a, r, s'), form a one-step target r + γ V(s') and nudge V(s) toward it. No model needed. No complete episodes needed. You do pick up bias from using an approximate V on the right-hand side, but variance drops dramatically compared to MC, and updates start from step one.

This is the pivot modern RL turns on: DQN, A2C, PPO, SAC, all of it. The rest of Phase 9 is layers of function approximation and tricks stacked on top of the one-step TD update you're about to write in this lesson.

The TD(0) update for V:

V(s) ← V(s) + α [r + γ V(s') - V(s)]

The bracketed quantity is the TD error, δ = r + γ V(s') - V(s), the online analogue of G_t - V(s_t) in MC. Convergence needs α to satisfy the Robbins-Monro conditions (Σ α = ∞, Σ α² < ∞) with every state visited infinitely often.

Q-learning. An off-policy TD method for control:

Q(s, a) ← Q(s, a) + α [r + γ max_{a'} Q(s', a') - Q(s, a)]

The max assumes the greedy policy gets followed from s' onward, no matter what action the agent actually takes. That decoupling is what lets Q-learning learn Q* while the agent keeps exploring via ε-greedy. Mnih et al. (2015) turned this exact idea into deep Q-learning on Atari (Lesson 05).

SARSA. An on-policy TD method:

Q(s, a) ← Q(s, a) + α [r + γ Q(s', a') - Q(s, a)]

The name comes from the tuple it consumes: (s, a, r, s', a'). SARSA plugs in the action a' the agent actually takes next, not the greedy argmax. It converges to Q^π for whatever ε-greedy π is currently running, which becomes Q* only in the limit ε → 0.

The cliff-walking difference. On the classic cliff-walking task, where falling off the cliff costs a reward of -100, Q-learning learns the optimal path right along the cliff edge and occasionally eats the penalty during exploration. SARSA learns a safer path one step back from the edge, because it bakes exploration noise directly into its Q-value. Train both long enough and they converge to the same optimum as ε → 0. What matters in practice is deployment: if exploration is still happening once the agent goes live, SARSA's caution shows.

Expected SARSA. Replace Q(s', a') with its expected value under π:

Q(s, a) ← Q(s, a) + α [r + γ Σ_{a'} π(a'|s') Q(s', a') - Q(s, a)]

Lower variance than SARSA, since there's no sample of a' to add noise, with the same on-policy target. It's the default in most modern textbooks for that reason.

n-step TD and TD(λ). You can interpolate between TD(0) and MC just by waiting n steps before bootstrapping: n=1 is TD, n=∞ is MC. TD(λ) averages over every n with geometric weights (1-λ)λ^{n-1}. Most deep RL sits somewhere between n=3 and n=20.

Step 1: SARSA on ε-greedy policy

def sarsa(env, episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})
 
    def choose(s):
        if random() < epsilon:
            return choice(ACTIONS)
        return max(Q[s], key=Q[s].get)
 
    for _ in range(episodes):
        s = env.reset()
        a = choose(s)
        while True:
            s_next, r, done = env.step(s, a)
            a_next = choose(s_next) if not done else None
            target = r + (gamma * Q[s_next][a_next] if not done else 0.0)
            Q[s][a] += alpha * (target - Q[s][a])
            if done:
                break
            s, a = s_next, a_next
    return Q

Eight lines, and the only difference from Q-learning is the target line.

Step 2: Q-learning

def q_learning(env, episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})
    for _ in range(episodes):
        s = env.reset()
        while True:
            a = choose(s, Q, epsilon)
            s_next, r, done = env.step(s, a)
            target = r + (gamma * max(Q[s_next].values()) if not done else 0.0)
            Q[s][a] += alpha * (target - Q[s][a])
            if done:
                break
            s = s_next
    return Q

The max decouples target from behavior. That single symbol is the whole difference between on-policy and off-policy.

Step 3: learning curves

Track mean return per 100 episodes. Q-learning converges faster on the simple deterministic GridWorld; SARSA is the more conservative learner on cliff-walking. On the 4×4 GridWorld in code/main.py, both land near-optimal after roughly 2,000 episodes at α=0.1, ε=0.1.

Step 4: compare to DP truth

Run value iteration (Lesson 02) to get Q*, then check max_{s,a} |Q_learned(s,a) - Q*(s,a)|. A healthy tabular TD agent lands within ~0.5 of Q* on the 4×4 GridWorld after 10,000 episodes.

• Initial Q values matter. Optimistic init (Q = 0 for a negative-reward task) encourages exploration. Pessimistic init can trap a greedy policy forever.
• α schedule. Constant α is fine for non-stationary problems. Decaying α_n = 1/n gives convergence in theory, but it's too slow in practice, so pin α in [0.05, 0.3] and watch the learning curve instead.
• ε schedule. Start high (ε=1.0) and decay to ε=0.05. "GLIE" (greedy in the limit with infinite exploration) is the convergence condition you're aiming for.
• Max bias in Q-learning. The max operator is biased upward whenever Q is noisy, which leads to overestimation. Hasselt's Double Q-learning (used by DDQN in Lesson 05) fixes this with two Q tables.
• Non-terminating episodes. TD can learn without terminals, but you need to either cap steps or handle the bootstrap correctly at the cap. The standard move: treat the cap as non-terminal and keep bootstrapping.
• State hashing. If states are tuples or tensors, use a hashable key: a tuple, not a list, and floats rounded rather than raw.

The 2026 TD landscape:

Ninety percent of the "RL" you'll read about in 2026 papers is some elaboration of Q-learning or SARSA. Get the tabular update into your fingers before you go looking for the fancier version.

Save as outputs/skill-td-agent.md:

---
name: td-agent
description: Pick between Q-learning, SARSA, Expected SARSA for a tabular or small-feature RL task.
version: 1.0.0
phase: 9
lesson: 4
tags: [rl, td-learning, q-learning, sarsa]
---
 
Given a tabular or small-feature environment, output:
 
1. Algorithm. Q-learning / SARSA / Expected SARSA / n-step variant. One-sentence reason tied to on-policy vs off-policy and variance.
2. Hyperparameters. α, γ, ε, decay schedule.
3. Initialization. Q_0 value (optimistic vs zero) and justification.
4. Convergence diagnostic. Target learning curve, `|Q - Q*|` check if DP is possible.
5. Deployment caveat. How will exploration behave at inference? Is SARSA's conservatism needed?
 
Refuse to apply tabular TD to state spaces > 10⁶. Refuse to ship a Q-learning agent without a max-bias caveat. Flag any agent trained with ε held at 1.0 throughout (no exploitation phase).

1. Easy. Implement Q-learning and SARSA on the 4×4 GridWorld. Plot learning curves (mean return per 100 episodes) for 2,000 episodes. Who converges faster?
2. Medium. Build a cliff-walking environment (4×12, last row is the cliff with reward -100 and reset to start). Compare Q-learning and SARSA final policies. Screenshot the paths each takes. Which is closer to the cliff?
3. Hard. Implement Double Q-learning. On a noisy-reward GridWorld (Gaussian noise σ=5 added to per-step reward), show Q-learning overestimates V*(0,0) by a meaningful amount while Double Q-learning does not.

• Watkins & Dayan (1992). Q-learning: the original paper and convergence proof.
• Sutton & Barto (2018). Ch. 6: Temporal-Difference Learning: TD(0), SARSA, Q-learning, Expected SARSA.
• Hasselt (2010). Double Q-learning: the fix for maximization bias.
• Seijen, Hasselt, Whiteson, Wiering (2009). A Theoretical and Empirical Analysis of Expected SARSA: the motivation behind Expected SARSA.
• Rummery & Niranjan (1994). On-line Q-learning using connectionist systems: the paper that coined SARSA, back when it was still called "modified connectionist Q-learning."
• Sutton & Barto (2018). Ch. 7: n-step Bootstrapping: generalizes TD(0) to TD(n), the path from Q-learning to eligibility traces and, later, GAE in PPO.