Temporal-Difference Learning: TD(0), SARSA, and Q-Learning

Where we are. Monte Carlo (Chapter 3) waited for a full episode to terminate, then averaged the realized return — unbiased, but high-variance and episodic-only. Dynamic programming (Chapters 1–2) never sampled at all; it bootstrapped each value from other current estimates through the model. Temporal-difference learning is the missing synthesis: sample one transition like Monte Carlo, and bootstrap from the current estimate like dynamic programming. The result learns online, from a single step, with no model and no wait for the episode to end. Its load-bearing object is the TD error $\delta_t = R_{t+1} + \discount V(S_{t+1}) - V(S_t)$ — a one-sample estimate of the Bellman residual.

The TD(0) update

Given a single transition $(S_t, R_{t+1}, S_{t+1})$ generated under $\policy$, TD(0) nudges the value of the visited state toward a bootstrapped target:

with step size $\alpha \in (0,1]$. Compare the three targets we have now for the same quantity $\valuefn_\policy(S_t)$: Monte Carlo uses the full sampled return $G_t$ (no bootstrap, needs the episode to end); dynamic programming uses the model expectation $(\bellman^\policy V)(S_t)$ (full bootstrap, needs the model); TD(0) uses $R_{t+1} + \discount V(S_{t+1})$ — one sampled successor plus a bootstrap off the current estimate.

TD(0) as a stochastic Euler step

Why should nudging toward a bootstrapped (hence biased, while $V \ne \valuefn_\policy$) target converge to the right answer? Because in expectation the nudge is a Bellman-operator step.

Read the deterministic part as a forward-Euler step on the ODE $\dot V = \bellman^\policy V - V$, whose unique equilibrium is the fixed point $\bellman^\policy \valuefn_\policy = \valuefn_\policy$ — that is, $\valuefn_\policy$.

SARSA: on-policy control

Prediction estimates $\valuefn_\policy$; control needs action-values. SARSA forms the same TD error on $Q$ from the quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ — its namesake — where $A_{t+1}$ is the action the agent actually takes next under its (typically $\varepsilon$-greedy) policy:

Because the bootstrap uses the value of the sampled next action, SARSA is on-policy: it evaluates and improves the very policy it follows. Interleaving this evaluation with $\varepsilon$-greedy improvement is generalized policy iteration (Chapter 1) driven by sampled errors; under GLIE (greedy in the limit with infinite exploration — $\varepsilon \to 0$ slowly) it converges to $\optqfn$.

Q-learning: off-policy control

Q-learning Watkins & Dayan (1992) changes one symbol — the next action is replaced by the greedy one:

That $\max$ makes the target the sampled optimality backup, so Q-learning learns $\optqfn$ directly while behaving by any sufficiently exploratory policy — it is off-policy. Watkins and Dayan proved $Q \to \optqfn$ with probability one under the Robbins–Monro step sizes and infinite visits to every state–action pair. The contrast with SARSA is exactly the contrast between the two operators of Chapter 1, now on action-values.

On-policy vs off-policy: the cliff

The split is not academic. On the cliff-walking gridworld — a corridor whose bottom edge is a cliff that costs a large penalty and resets the agent — an optimal agent walks right along the cliff’s lip, the shortest path. Q-learning, estimating $\optqfn$, learns exactly that risky-optimal route. SARSA, estimating $\qfn_\policy$ for the $\varepsilon$-greedy policy it actually follows, accounts for the fact that exploration will occasionally step it off the cliff, so it prefers a safer path one row up.

n-step TD and the bias–variance dial

TD(0) and Monte Carlo are the endpoints of one family. The $n$-step return $G_{t:t+n} = R_{t+1} + \discount R_{t+2} + \cdots + \discount^{n-1}R_{t+n} + \discount^{n} V(S_{t+n})$ bootstraps after $n$ sampled rewards; $n=1$ is TD(0), $n=\infty$ is Monte Carlo. Larger $n$ samples more (higher variance, less bootstrap bias); smaller $n$ bootstraps more (lower variance, more bias while $V$ is wrong). Intermediate $n$ — and its geometric average TD($\lambda$) — usually beats both endpoints, the bias–variance dial made adjustable.

The dynamic-programming bridge

Temporal-difference learning closes a loop opened in Chapter 2. Real-time DP applied asynchronous Bellman backups along trajectories, but using the model expectation $\sum_{s'}\transition(s'\mid s,a)$. Replace that expectation with a single sampled successor and the deterministic backup becomes the stochastic TD update — RTDP’s “Monte-Carlo cousin,” promised in Chapter 2, is precisely Q-learning. The three methods now form a clean table on two axes:

• Dynamic programming — bootstrap, no sample (model expectation, full sweep).
• Monte Carlo — sample, no bootstrap (full return, episode end).
• Temporal difference — sample and bootstrap (one transition, online).

All three chase the same fixed point of the same $\discount$-contraction; they differ only in how much they sample and how much they bootstrap.

What’s next

• Week 5 replaces the value table with a parametric approximator $V_\theta$. Bootstrapping (this chapter), off-policy data (Q-learning), and function approximation together form the deadly triad — the first place the clean contraction story breaks, because approximation moves the fixed point itself.

Exercises

1. (Derive) Show $\E_\policy[\delta_t \mid S_t = s] = (\bellman^\policy V)(s) - V(s)$ for any $V$, and conclude TD(0) is a stochastic step toward $\valuefn_\policy$ (Prop. 4.1).

   Solution

   $\E_\policy[\delta_t\mid S_t=s] = \E_\policy[R_{t+1}+\discount V(S_{t+1})\mid S_t=s] - V(s) = \sum_a\policy(a\mid s)\sum_{s',r}\transition(s',r\mid s,a)[r+\discount V(s')] - V(s) = (\bellman^\policy V)(s) - V(s)$. The expected update is therefore $V(s) + \alpha[(\bellman^\policy V)(s) - V(s)]$, a damped step of the $\discount$-contraction whose fixed point is $\valuefn_\policy$.

2. (Prove) Show the expected Q-learning target is $(\bellmanopt Q)(s,a)$ and the expected SARSA target is $(\bellman^\policy Q)(s,a)$, hence their fixed points are $\optqfn$ and $\qfn_\policy$ (Prop. 4.2).

   Solution

   Averaging over $(S_{t+1},R_{t+1})\sim\transition(\cdot\mid s,a)$: Q-learning’s $\max_{a'}Q(S_{t+1},a')$ gives $\sum_{s',r}\transition[r+\discount\max_{a'}Q(s',a')] = (\bellmanopt Q)(s,a)$. SARSA additionally averages $A_{t+1}\sim\policy(\cdot\mid S_{t+1})$, giving $\sum_{s',r}\transition[r+\discount\sum_{a'}\policy(a'\mid s')Q(s',a')] = (\bellman^\policy Q)(s,a)$. The fixed points follow from the contraction of each operator.

3. (Compute) With $\discount = 0.9$, $\alpha = 0.1$, current $V(s)=2$, observed $R_{t+1}=1$, $V(s')=3$: compute $\delta_t$ and the updated $V(s)$.

   Solution

   $\delta_t = 1 + 0.9\cdot 3 - 2 = 1.7$; $V(s)\leftarrow 2 + 0.1\cdot 1.7 = 2.17$. The same numbers drive a SARSA or Q-learning update with $Q(s',\cdot)$ in place of $V(s')$ (the sampled-action value for SARSA, the max for Q-learning).

4. (Implement) In the companion, verify TD(0) converges to the analytic $\valuefn_\policy$ on the random walk; that Q-learning (GLIE) recovers the optimal cliff-edge policy while SARSA settles on the safer, slightly longer route; and that at a fixed $\varepsilon$ Q-learning’s start-state value is at least SARSA’s.

   Solution

   See experiments/python/week04/test_td.py: TD(0) matches dp.policy_evaluation within a sampling tolerance; Q-learning’s greedy policy attains the optimal start-state value from dp.value_iteration while SARSA’s greedy is a sensible but suboptimal goal-reaching route (the safe path), so the off-policy greedy value is $\ge$ the on-policy one; and the fixed-$\varepsilon$ start-state estimate of Q-learning is $\ge$ SARSA’s — the optimism/realism gap.

5. (Extend) Sweep $n$ in $n$-step TD on the random walk and reproduce the characteristic U-shaped error-vs-$n$ curve (an intermediate $n$ beats both TD(0) and Monte Carlo).

   Solution

   Bootstrapping bias falls with $n$ while sampling variance rises; the sum is minimized at intermediate $n$. The qualitative U-curve over $n$ (for a fixed $\alpha$) is the standard Sutton & Barto result; the companion’s --nstep sweep reproduces it.

Companion code

The Week-4 companion lives at experiments/python/week04/ and reuses earlier weeks: the random walk from Week 3 (randomwalk.py) for prediction, and the Week-1 dp solvers as the exact oracle for both prediction and control.

• cliffwalk.py — a self-contained cliff-walking MDP (the Sutton & Barto Example 6.6 layout: a cliff row that penalizes and resets) as a generic (P, R) array pair, so $\optvaluefn$ and the optimal policy come from dp.value_iteration.
• td.py — the transition sampler plus td0_prediction, sarsa, and q_learning, all operating on a generic (P, R, terminals), with optional GLIE schedules (visit-count step sizes, decaying $\varepsilon$). Pure NumPy.
• test_td.py — mathematical-correctness tests: TD(0) converges to the analytic $\valuefn_\policy$; under GLIE Q-learning recovers the optimal start-state value while SARSA learns the safer, slightly longer route; and Q-learning’s fixed-$\varepsilon$ start value is at least SARSA’s (the cliff’s on-/off-policy gap).

# core algorithms + correctness tests (pure NumPy, no Gymnasium needed)
PYTHONPATH=. pytest experiments/python/week04/test_td.py -q

# worked SARSA-vs-Q-learning comparison on the cliff (prints both learned paths)
PYTHONPATH=. python experiments/python/week04/cliffwalk.py