THE TEMPORAL-DIFFERENCE LEARNING

Update a guess toward a later guess — before the final outcome ever arrives, and with no model of the world. TD(0) nudges each state value along the error δ = r + γV(s′) − V(s). The true value function is exactly the point where that error vanishes in expectation. This panel computes it live on a bounded random walk and proves the fixed point.

source Sutton, R. S. — Learning to Predict by the Methods of Temporal Differences, Machine Learning 3 (1988), 9–44 · DOI 10.1007/BF00115009 · AMBER (classic behind publisher; no open arXiv id). Rendered, not quoted.

■ Blue Team · builds & defends
3

THE MODEL

A Markov Reward Process: the bounded random walk. Five non-terminal states 1…5. From state i the walk steps to i−1 or i+1, each with probability ½. Hitting 0 ends the episode with reward 0; hitting 6 ends it with reward 1. All other rewards are 0, γ = 1.

By symmetry the true value Vπ(i) = i/6 — the probability of exiting on the right. No policy, no actions: pure prediction of the future return.

V(s) ← V(s) + α·δ,   δ = r + γ·V(s′) − V(s)
5

THE LINEAGE

Descends from the-bellman-equation — but learned from samples. Bellman writes V(s) = E[r + γV(s′)]; a dynamic-programming sweep needs the full transition model. TD keeps the same fixed point and throws the model away.

The new idea is bootstrapping: you may correct a prediction using your own later prediction V(s′), before the episode's true outcome is known. Credit flows between successive guesses, not from the final result.

7

THE WITNESS

Live re-check: at V = Vπ, the maximum expected TD error over all states must be ≈ 0. If Red's tamper (window 6) drops the bootstrap term, this witness recomputes and catches it.

witness idle…
◆ The Machine
4
in ▼

DATA IN

The MRP above, plus an optimistic init V(1…5) = 0.5, step size α = 0.1, and a fixed-seed stream of sampled episodes (seed 12345, mulberry32). No true values are given to the learner.

booting…
0
● lit

THE PANEL — TD(0) live

Sampled transitions and their live TD errors δ. Each row nudges V(s) toward r + γV(s′):

booting…

Estimates after 200 episodes vs. the true Vπ(i)=i/6:

booting…
8
out ▼

DATA OUT

verifying…

result pending selfcheck…

▲ Red Team · attacks & breaks
1
wall

THE ADVERSARY

TD(0) is biased for finite α and finite data: it chases a moving bootstrap target, so early estimates inherit the error of their own neighbours. It converges to Vπ only in expectation, under decaying step sizes (Robbins–Monro), not from any single run.

With function approximation and off-policy sampling, the same bootstrap can diverge — Baird's counterexample. Here (tabular, on-policy) it is safe, but the wall is real: the fixed point exists only where E[δ]=0.

2

THE GRAVEYARD

  • "TD waits for the outcome, like Monte Carlo." → It updates every step from the next prediction; the outcome need not arrive.
  • "You need the transition probabilities." → TD is model-free — it samples s′ instead of averaging over it.
  • "Any V that fits the data is the answer." → Only Vπ makes the expected error zero at every state simultaneously.
6

THE TAMPER

The disclosed planted void: drop the bootstrap term so δ = r − V(s), ignoring γV(s′). The true V is no longer a fixed point — E[δ]≠0 — and the witness in window 7 must catch it.