Chapter 6 — Temporal-Difference Learning, explained.

Halfway through a two-hour delivery run, Asha sees the robot repeatedly enter the same queue. Monte Carlo says: wait until the delivery ends, calculate the return, then learn. That is too late—the robot has already repeated the mistake. But the next state is informative now: if the queue state is known to be poor, the previous turn should become less attractive immediately. Temporal-difference learning makes one prediction learn from the prediction that follows it.

01 TD prediction from the return recursion

Monte Carlo targets the complete return G_t. The return identity says G_t=R_t+1+γG_t+1. TD(0) replaces unknown G_t+1 with the current estimate V(S_t+1):

The target R+γV(S′) is a one-step backup. It is sampled because the environment supplies one transition, and bootstrapped because it contains a learned estimate. No transition model or terminal wait is needed.

02 The TD error as moving surprise

δ is the discrepancy between the old prediction and a one-step-improved prediction. Positive δ means the transition was better than expected; negative δ means worse. If values were exactly self-consistent for π, expected δ conditioned on each state would be zero.

For Asha, V(before queue)=12, reward for the turn is −1, V(queue)=7, and γ=.9. The target is 5.3 and δ=−6.7. With α=.1, the previous state drops to 11.33 immediately.

03 Why TD can outperform Monte Carlo

TD learns online and applies to continuing tasks. It often has lower variance because randomness after the next state is summarized by V rather than included in the target. It also propagates useful estimates before terminal rewards arrive.

The price is bias: an inaccurate V(S′) contaminates the target. Yet under tabular on-policy conditions TD(0) converges to v_π. Batch TD and batch MC reveal different inductive assumptions: MC fits observed returns; TD finds values consistent with the maximum-likelihood Markov model implied by observed transitions.

The random-walk example shows TD often reaches lower RMS prediction error per episode across appropriate step sizes. This is empirical efficiency, not a universal theorem that TD always beats MC.

04 Sarsa: on-policy TD control

Replace V with Q and include the next action selected by the same policy:

The five variables S,A,R,S′,A′ give Sarsa its name. The algorithm chooses A′—often ε-greedily—before updating, so its target reflects exploratory behavior. It evaluates and improves the policy actually used.

Terminal transitions use Q(terminal,·)=0. Step order matters in implementation: observe S, choose A, step, observe R,S′, choose A′ unless terminal, update, then shift S←S′ and A←A′.

05 Q-learning: off-policy control

Q-learning's target assumes greedy continuation, regardless of which action behavior selects next. The target policy is greedy; behavior can remain ε-greedy for coverage. In the tabular setting with adequate visits and step sizes, Q converges to q_*.

Off-policy does not mean the behavior data are ignored. The experienced S,A,R,S′ still come from behavior; only the bootstrap continuation uses the greedy target.

06 Cliff walking: Sarsa and Q-learning disagree for a reason

In the cliff grid, the shortest path runs beside cells with −100 reward. Q-learning learns the greedy optimal path because its target assumes no exploratory mistake next. During ε-greedy training, occasional random moves fall off the cliff.

Sarsa evaluates that same ε-greedy behavior, so states near the cliff include the risk of future exploration. It learns a longer safe route with better online reward. If exploration is later removed, Q-learning's route may be better. The algorithms optimize different policies during learning.

07 Expected Sarsa and the bias–variance choice

Expected Sarsa replaces the sampled A′ with its exact expectation under π. Given current Q, it removes variance caused by selecting the next action, though transition and reward randomness remain. It can use larger step sizes reliably in some tasks.

If π is greedy, Expected Sarsa becomes Q-learning. If π is the behavior policy, it is on-policy; if expectation uses a different target, it is off-policy. The backup equation, not the name alone, tells the alignment.

08 Maximization bias, Double Q, and afterstates

The maximum of noisy estimates is positively biased: even if every true action value is zero, the largest sample estimate tends to be above zero. Q-learning both selects and evaluates using the same Q values, so noise can reinforce overestimation.

Double Q-learning maintains Q₁ and Q₂. To update Q₁, use Q₁ to select argmax and Q₂ to evaluate it; reverse roles when updating Q₂. Independent errors reduce selection-induced bias.

An afterstate is the deterministic state immediately after the agent acts but before environment randomness. In board games, many different state–action pairs create the same board afterstate. Learning its value shares experience and removes redundant action representations.

09 Questions master's students should answer

10 Key takeaways

• TD combines sampled transitions with bootstrapped targets, learning online without a model.
• δ=R+γV(S′)−V(S) is a one-step prediction error carrying new information backward.
• Sarsa evaluates its exploratory behavior; Q-learning targets greedy continuation off-policy.
• Cliff walking demonstrates an objective difference, not a universal ranking.
• Expected Sarsa trades a small action expectation computation for reduced target variance.
• Maximization of noisy values causes positive bias; Double Q separates selection and evaluation.
• Afterstates share value across actions that produce the same deterministic intermediate result.

11 Wrapping up and source trail

Asha can now learn during a delivery, but one-step TD moves information only one transition at a time. Chapter 7, n-step bootstrapping, opens the continuum between TD and Monte Carlo: observe several rewards, then bootstrap.

These are independent companion notes written in original language. Primary references: the authors' book page, the author-hosted open-access draft, the MIT Press edition page, and the official contents.