Temporal-Difference Learning

If you are forced to name the one idea that is most central to reinforcement learning — the idea that is novel to the field rather than borrowed from statistics or control theory — it is temporal-difference learning. Sutton & Barto say exactly this, and the rest of the book will keep proving them right: TD is the learning rule inside Q-learning, DQN, actor-critic, TD3, SAC, and the value heads of AlphaZero and MuZero. Whatever you end up doing in RL, you will be doing TD.

The idea fits in a sentence: update your prediction toward a better prediction, without waiting to see how things actually end. Monte Carlo waits for the true return; TD notices that one step later you have one real reward in hand plus a prediction from the next state — and that this combination, reward plus discounted next prediction, is already a better-informed estimate than the one you started with. Learn from it now. This chapter develops that idea into prediction (TD(0)) and control (SARSA, Q-learning, Expected SARSA), proves what can be proven about convergence, diagnoses the maximization bias that quietly corrupts Q-learning (and later DQN), and runs the classic cliff-walking experiment where the on-policy/off-policy distinction stops being philosophy and starts costing reward.

1. TD Prediction: Learning a Guess from a Guess

We estimate $V^\pi$ from experience generated by π. Recall the two updates we own so far, written as the same template. Monte Carlo, with target = the actual return:

available only at episode's end. Dynamic programming, with target = the model's one-step expectation over all successors: available immediately but requiring $p$. TD(0) takes the structure of DP's target and the sampling of MC: one real step, then bootstrap —

The bracketed quantity is the TD error,

the discrepancy between the value you predicted at time $t$ and the one-step-later revision of that prediction. It is the single most recurring symbol in the rest of this book — the advantage estimates of Chapter 11 are sums of these; the "surprise" driving dopamine-neuron models in neuroscience is this quantity, almost literally.

Why is the TD target legitimate? Because the Bellman equation says its expectation is exactly right:

If the values we bootstrap from were correct, the TD update would be an unbiased nudge toward the truth. They are not correct during learning — that is the "learning a guess from a guess" gamble, and the bias it introduces is real: the TD target $R_{t+1} + \gamma V(S_{t+1})$ is biased by whatever error currently lives in $V(S_{t+1})$. In exchange, its variance is tiny compared to $G_t$'s: one reward and one transition's worth of noise, versus the accumulated randomness of an entire trajectory. TD trades bias for variance. Nearly every algorithmic choice in modern RL is a position taken on this trade.

Sutton's driving-home example makes the psychology vivid. Leaving the office you predict 30 minutes home; reaching your car in the rain you revise to 40. Monte Carlo insists you wait until you are home to learn anything — then adjusts "leaving the office" toward the actual 43 minutes. TD adjusts "leaving the office" toward "40, as predicted in the rain" the moment you reach the car. You do not need to arrive home to know the office estimate was too sunny: the revision itself is information, and TD consumes it immediately. Now the punchline that separates the methods: suppose traffic then miraculously clears and you arrive in 35. MC would have taught "office → 35" — but the rain-soaked car moment was really a 40-minute situation on average; you just got lucky afterward. TD's within-trajectory revision can be more accurate than the noisy final outcome. Hold that intuition; Section 3 makes it a theorem about batch learning.

2. Why TD Wins: the Practical Case

Before theory, the operational advantages that made TD the field's default:

• Online and incremental. TD learns after every step, from every step, with $\mathcal{O}(1)$ work and memory. No waiting for termination — so continuing tasks (servers, thermostats, market makers) are learnable at all, and long-episode tasks don't starve early states of updates.
• Low variance targets. One reward plus one bootstrap versus a whole trajectory of noise. In stochastic environments this is decisive: MC's per-update signal degrades with horizon; TD's does not.
• It propagates knowledge. When one state's value improves, every state that transitions into it inherits the improvement on its next visit — value flows backward through the state graph one step per visit, precisely the asynchronous DP picture of Chapter 4 with samples in place of sweeps. MC has no such propagation: each state must independently accumulate its own returns.

The cost — bias from bootstrapping off wrong estimates — is usually worth paying, with two exceptions worth flagging now: when the state representation badly violates the Markov property, bootstrapping compounds representation error while MC remains honest (Chapter 5's scorecard); and when combined with function approximation and off-policy data, bootstrapping is one leg of the deadly triad (Chapter 9). TD's bias is a loan; mostly it's cheap credit, occasionally it's the subprime kind.

3. What TD(0) Converges To

Asymptotic convergence. For a fixed policy π, tabular TD(0) converges to $V^\pi$ with probability 1, provided every state is visited infinitely often and the step sizes obey the Robbins–Monro conditions from Chapter 2 ($\sum \alpha = \infty$, $\sum \alpha^2$ finite). The engine of the proof is by now familiar: the expected TD update is an affine map whose linear part is $\gamma P^\pi$ — a γ-contraction (Chapter 4) — so the noisy iteration is a stochastic approximation to a contraction fixed-point iteration, and the general theorems of stochastic approximation (Jaakkola, Jordan & Singh 1994; Tsitsiklis 1994) deliver almost-sure convergence to the unique fixed point, $V^\pi$. Bias from bootstrapping is transient, not permanent.

Finite-batch behavior — the more instructive fact. Take a fixed batch of episodes and train to convergence on it, replaying the batch until updates vanish. Batch MC and batch TD(0) converge to different answers, and the difference is a fingerprint of what each method fundamentally is. Sutton & Barto's Example 6.4 ("You are the Predictor") is the minimal case: eight episodes over two states A and B — A appeared once, transitioning to B with reward 0; B's episodes ended with reward 1 six times out of eight. Everyone agrees $V(B) = 6/8$. But $V(A)$?

• Batch MC says $V(A) = 0$: the only episode through A returned 0, and MC minimizes squared error against observed returns. On the training data, this is the best possible fit.
• Batch TD says $V(A) = 6/8$: A led to B, and B is worth 6/8. TD converges to the value function of the maximum-likelihood MDP — the model whose transition and reward estimates are the batch's empirical frequencies — solved exactly. This is called the certainty-equivalence estimate.

Which is right? For predicting future data generated by the same Markov process: TD, and it is not close. MC's answer treats the A-episode's outcome as A's own property; TD recognizes A's outcome flowed through B and pools B's eight episodes of evidence into A's estimate. TD exploits the Markov structure; MC ignores it. This is the honest statement of TD's advantage — not "less variance" as a vague slogan, but implicitly building and solving the empirical model, at $\mathcal{O}(1)$ cost per step, without ever storing it.

4. SARSA: On-Policy TD Control

Control, as always, is GPI: evaluate with TD, improve with ε-greedy. For model-free improvement we need action values, so run TD(0) on $Q$ along the transition $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ — the quintuple that names the algorithm:

$A_{t+1}$ is the action the policy actually takes next — SARSA evaluates the ε-greedy policy it is following, exploration warts and all, and improves it by re-greedifying $Q$. It is on-policy: the learned $Q$ is $Q^\pi$ for the current behavior, converging (under Robbins–Monro steps plus a GLIE schedule — "greedy in the limit with infinite exploration," e.g. $\epsilon_t \to 0$ slowly; Singh et al. 2000) to $Q^*$.

The practical signature of on-policy learning: SARSA's values price in the exploration. If ε-greedy occasionally stumbles into a pit, states near the pit look bad to SARSA — because for the policy actually being run, they are bad. This makes SARSA "cautious," an anthropomorphism the cliff experiment in Section 7 will cash out precisely.

5. Q-Learning: Off-Policy TD Control

Watkins' 1989 algorithm, arguably the single most important in RL's history, changes one symbol:

The bootstrap uses the best next action, not the taken one. Squint and you will recognize the target as a sampled Bellman optimality backup (Chapter 4's value iteration), where SARSA's was a sampled Bellman expectation backup. Q-learning learns $Q^*$ directly, regardless of what policy generates the data — the behavior can be ε-greedy, uniform random, a human demonstrator, or a replay buffer of stale experience, and the fixed point is still $Q^*$. Convergence needs only that every pair is updated infinitely often, plus step-size conditions (Watkins & Dayan 1992; Tsitsiklis 1994).

Pause on something remarkable: Chapter 5's off-policy learning required importance-sampling ratios, with their exploding variance. Where did the ratios go? Two answers, both illuminating. Mechanically: the correction was needed to fix the distribution of actions the policy takes downstream; Q-learning's target replaces the sampled downstream action with an explicit max — no downstream sampling under the wrong policy ever enters, so nothing needs reweighting. (The transition $S_{t+1} \sim p(\cdot \mid S_t, A_t)$ is on-distribution no matter who chose $A_t$ — dynamics don't care who's asking.) Structurally: one-step targets only ever query the current $(s,a)$ — off-policy corrections are only needed for multi-step constructions, which is exactly the complication Chapter 7 takes up. This free pass is why off-policy deep RL (DQN and descendants) is built on the one-step Q-learning backup.

Expected SARSA interpolates the remaining gap — replace the max (or the sample) with the policy's own expectation:

It deletes the variance of sampling $A_{t+1}$ at the cost of a sum over actions, dominates SARSA empirically at any fixed α (van Seijen et al., 2009), and generalizes both neighbors: with π the greedy policy, the expectation is the max and Expected SARSA is Q-learning. One family, three members, distinguished only by what stands in for the next action's value.

6. Maximization Bias and Double Q-Learning

Q-learning has a congenital defect, invisible in its convergence theorem (which is asymptotic) and expensive in its finite-sample life. The target contains $\max_{a'} Q(S_{t+1}, a')$ — a max over estimates. But for any random estimates,

(Jensen's inequality: the max is convex). Noise inflates the max: with many actions whose true values are equal, the max of the noisy estimates sits roughly one noise-standard-deviation above the truth, because the max selects the luckiest error. Using one set of samples both to choose the best action and to evaluate it means the selection systematically harvests upward noise. This is maximization bias, and it feeds on itself: inflated next-state values become inflated targets become inflated values one step earlier.

Sutton & Barto's Example 6.7 shows it biting: from a start state, action right ends the episode with reward 0; action left leads to a state with many available actions, each terminating with reward drawn from $\mathcal{N}(-0.1, 1)$. Truth: left is worth $-0.1$, strictly worse. But among many noisy zero-ish estimates, the max is reliably positive early on, so Q-learning spends its youth preferring the worse action, unlearning the preference only slowly as estimates sharpen.

Double Q-learning (van Hasselt, 2010) severs the correlation with two independent tables $Q_1, Q_2$. On each step, flip a coin; if it lands on $Q_1$:

and symmetrically. $Q_1$ chooses; $Q_2$ evaluates. Since $Q_2$'s noise is independent of $Q_1$'s argmax selection, the luckiest-error harvest stops: if $Q_1$'s argmax landed on an action only because of upward noise, $Q_2$'s independent estimate of that action is unbiased, and the expected evaluation is no longer inflated (it becomes, if anything, slightly pessimistic — Exercise 6.6). On Example 6.7, the pathology vanishes almost entirely. File this mechanism carefully: the same disease reappears in DQN at scale, and the same cure — decoupling selection from evaluation, there via the target network — becomes Double DQN, one line of code worth several hundred Atari points (Chapter 10). TD3's twin critics (Chapter 13) are the same idea a third time.

7. Worked Example: Cliff Walking

The canonical experiment where on-policy vs. off-policy becomes visceral (S&B Example 6.6). A 4×12 gridworld: start bottom-left, goal bottom-right, and the entire bottom edge between them is a cliff — stepping in costs −100 and teleports you back to start. Every other step costs −1. The optimal path skims one row above the cliff (return −13); a safe path arcs along the top (return −17). Agents are ε-greedy with ε = 0.1, fixed.

import numpy as np
 
H, W = 4, 12
START, GOAL = (3, 0), (3, 11)
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]          # N, S, W, E
 
def step(s, a):
    r, c = s
    dr, dc = ACTIONS[a]
    nr, nc = min(max(r + dr, 0), H - 1), min(max(c + dc, 0), W - 1)
    if nr == 3 and 0 < nc < 11:                        # fell off the cliff
        return START, -100.0, False
    return (nr, nc), -1.0, (nr, nc) == GOAL
 
def eps_greedy(Q, s, eps, rng):
    if rng.random() < eps:
        return rng.integers(4)
    q = Q[s]
    return int(rng.choice(np.flatnonzero(q == q.max())))
 
def train(algo, episodes=500, alpha=0.5, eps=0.1, gamma=1.0, seed=0):
    rng = np.random.default_rng(seed)
    Q = {(r, c): np.zeros(4) for r in range(H) for c in range(W)}
    returns = np.zeros(episodes)
    for ep in range(episodes):
        s = START
        a = eps_greedy(Q, s, eps, rng)
        done, G = False, 0.0
        while not done:
            s2, r, done = step(s, a)
            G += r
            a2 = eps_greedy(Q, s2, eps, rng)
            if algo == "sarsa":
                target = 0.0 if done else Q[s2][a2]    # the action we WILL take
            else:                                      # q-learning
                target = 0.0 if done else Q[s2].max()  # the best action
            Q[s][a] += alpha * (r + gamma * target - Q[s][a])
            s, a = s2, a2
        returns[ep] = G
    return Q, returns
 
_, r_sarsa = train("sarsa")
_, r_q     = train("qlearn")
print(f"SARSA      avg return, last 100 eps: {r_sarsa[-100:].mean():.1f}")
print(f"Q-learning avg return, last 100 eps: {r_q[-100:].mean():.1f}")

The result reproduces one of the most quoted plots in RL. Q-learning learns the optimal cliff-edge path — its $Q$ converges toward $Q^*$, which knows nothing of ε — yet earns worse online return (≈ −60 per episode late in training vs. SARSA's ≈ −25 with the seed above), because its ε-exploration, executed while walking the very edge it planned, keeps pitching it into the cliff. SARSA learns the longer, safer path: since its values price in its own exploration, cliff-adjacent states are correctly assessed as dangerous for an ε-greedy walker, and the policy detours. Neither is "better": Q-learning answers "what is optimal?", SARSA answers "what is best to actually do, given how I behave?" — and if you anneal ε to zero, both converge to the optimal path. The distinction — the value of the target policy vs. the value of the behavior — is worth internalizing here, in a 48-state grid, because exactly this gap reappears at scale as offline RL's central difficulty (Chapter 17): a learned "optimal" policy whose execution differs from the data-collecting behavior can walk off cliffs the data never charted.

8. Summary

• TD(0): $V(S_t) \leftarrow V(S_t) + \alpha\,\delta_t$ with $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ — update a prediction toward a one-step-later, better-informed prediction. Legitimized by the Bellman equation; biased during learning; drastically lower variance than MC; online and incremental.
• Tabular TD(0) converges to $V^\pi$ w.p. 1 under Robbins–Monro steps and persistent visitation; the mechanism is stochastic approximation of a γ-contraction.
• On a fixed batch, TD converges to the certainty-equivalence solution — the exact values of the empirical MDP — while MC fits observed returns. TD exploits Markov structure; MC survives its absence.
• SARSA (on-policy) backs up the action actually taken; converges to $Q^*$ under GLIE. Its values price in exploration — hence "cautious."
• Q-learning (off-policy) backs up the max: sampled value iteration, learning $Q^*$ from any sufficiently exploratory data, no importance sampling needed at one step. Expected SARSA backs up the policy expectation and contains both as special cases.
• $\E[\max]$ ≥ $\max \E$: using one noisy estimate to both select and evaluate inflates values — maximization bias. Double Q-learning decouples selection ($Q_1$) from evaluation ($Q_2$); the cure recurs as Double DQN and TD3.
• Cliff walking: Q-learning finds the optimal path but earns less while learning; SARSA optimizes what it actually runs. Target-vs-behavior value gaps preview offline RL.

9. Papers & Further Reading

• Sutton, "Learning to Predict by the Methods of Temporal Differences" (Machine Learning, 1988) — doi.org/10.1007/BF00115009. The founding paper: TD(λ), the driving example's logic, and the first convergence results. Still readable, still worth it.
• Watkins, Learning from Delayed Rewards (PhD thesis, Cambridge, 1989) — cs.rhul.ac.uk/~chrisw/thesis.html — and Watkins & Dayan, "Q-learning" (Machine Learning, 1992) — doi.org/10.1007/BF00992698. The algorithm and its convergence proof.
• Rummery & Niranjan, "On-Line Q-Learning Using Connectionist Systems" (Cambridge tech report CUED/F-INFENG/TR 166, 1994) — semanticscholar.org. SARSA's debut (they called it "modified Q-learning"; Sutton supplied the acronym).
• Jaakkola, Jordan & Singh, "On the Convergence of Stochastic Iterative Dynamic Programming Algorithms" (Neural Computation, 1994) — doi.org/10.1162/neco.1994.6.6.1185 — and Tsitsiklis, "Asynchronous Stochastic Approximation and Q-learning" (Machine Learning, 1994) — doi.org/10.1007/BF00993306. The stochastic-approximation machinery behind every convergence claim in this chapter.
• Singh, Jaakkola, Littman & Szepesvári, "Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms" (Machine Learning, 2000) — doi.org/10.1023/A:1007678930559. GLIE, and SARSA's convergence to optimality.
• van Seijen, van Hasselt, Whiteson & Wiering, "A Theoretical and Empirical Analysis of Expected Sarsa" (IEEE ADPRL, 2009) — doi.org/10.1109/ADPRL.2009.4927542. Expected SARSA's variance advantage, formalized.
• van Hasselt, "Double Q-learning" (NeurIPS, 2010) — papers.nips.cc. Maximization bias and the double estimator; the direct parent of Double DQN.

10. Exercises

6.1 (understand) In the driving example, list the sequence of TD updates (state, old estimate, target, direction of change) for the trajectory: office (30) → car in rain (40) → highway clear (35) → home in 43 actual minutes, with α = 1. Then give the MC updates. Which estimates end up different and why?

6.2 (understand) SARSA's target uses $A_{t+1}$ sampled from the current policy; Expected SARSA uses the exact expectation. Both have the same fixed point for a fixed policy. In what precise sense is Expected SARSA "SARSA with variance removed," and what does it cost per update? For $\lvert \mathcal{A} \rvert = 2$ vs. $\lvert \mathcal{A} \rvert = 10^6$, which would you run?

6.3 (derive) Show that the TD(0) expected update over states is $V \leftarrow V + \alpha D (\mathcal{T}^\pi V - V)$ where $D$ is the diagonal matrix of state-visitation probabilities. Conclude that for tabular representations with all states visited, the unique fixed point is $V^\pi$ — and note (for Chapter 9) that $D$'s presence will matter enormously once approximation couples the states.

6.4 (derive) Prove $\E[\max_i X_i] \ge \max_i \E[X_i]$ for random variables $X_1, \dots, X_n$, and compute the bias exactly for two i.i.d. $\mathcal{N}(0, \sigma^2)$ estimates: $\E[\max(X_1, X_2)] = \sigma/\sqrt{\pi}$. What does this predict about how maximization bias scales with the number of actions and with estimate noise (i.e., with $1/\sqrt{N}$)?

6.5 (derive) Q-learning's target for a terminal transition is just $R_{t+1}$. Show that if timeout-truncated episodes are treated as terminal, the fixed point of the resulting update is the value function of a different MDP — one where the world genuinely ends at the time limit — and construct a two-state example where the greedy policies of the two MDPs differ.

6.6 (derive) In Double Q-learning, show that the evaluation $\E\left[Q_2(s, a^*)\right]$ with $a^* = \argmax_a Q_1(s, a)$ is not upward biased, and construct a small example where it is strictly downward biased. (Hint: $Q_1$'s argmax can select a truly-best action whose $Q_2$ estimate happens to be low — but never harvests $Q_2$'s upward noise.)

6.7 (implement) Run the cliff-walking code. Reproduce the online-return comparison, then: (a) plot the greedy policies of both algorithms as arrow grids and verify SARSA's detour; (b) anneal ε → 0 over 5,000 episodes and show both converge to the optimal path; (c) add Expected SARSA and place its curve relative to both.

6.8 (implement) Windy gridworld (S&B Example 6.5): 7×10 grid, an upward wind of strength (0,0,0,1,1,1,2,2,1,0) per column displacing the agent. Solve with SARSA. Then add king's moves (8 actions) and a ninth "no-op" action and report how the optimal episode length changes — a small taste of how action-space design changes a problem.

6.9 (implement) Build the maximization-bias MDP of Example 6.7 with $k$ arms at the left state. For $k \in \{1, 2, 10, 100\}$, plot the fraction of runs choosing left over episodes for Q-learning vs. Double Q-learning. Check the scaling you predicted in Exercise 6.4.

6.10 (research) TD's certainty-equivalence property (Section 3) was proved for the batch setting. Online TD with replay (as in DQN) sits between pure-online and batch. Formulate a precise conjecture about what online-TD-with-infinite-replay converges to, and design (on paper) an experiment on the You-are-the-Predictor MDP that would falsify it. Then consider: does prioritized replay (Chapter 10) change the answer? (This seemingly innocent question — "what distribution do replayed backups follow?" — is an open thread through Chapters 9, 10, and 17.)