10 · Temporal-difference learning
TD(0) is the central idea of RL: update V(s) after EVERY step using a one-step bootstrap V(s) ← V(s) + α(r + γV(s′) − V(s)). It learns online, without waiting for the episode to end.
TD(0) updates V(s) after a single step using a bootstrapped target: V(s) ← V(s) + α·(r + γ·V(s′) − V(s)). The bracket is the TD error — the gap between what you predicted and what one step of reality plus your own next-state guess say.
Without this:
Without TD you must wait for full episodes (MC), can't learn from continuing tasks, and can't fuse experience with your own current value estimates — the engine behind Q-learning, Sarsa and the value head of every deep-RL agent.
Monte Carlo waits patiently until an episode ends, then uses the complete return G_t as its learning target. Temporal-difference (TD) learning is impatient — and that impatience is the single most important idea in RL.
The trick is bootstrapping: instead of waiting for the full return, TD replaces the unseen tail of the episode with its own current estimate of the next state's value. Start from the Bellman-style identity V(s) = E[r + γ·V(s′)]. The quantity r + γ·V(s′) — a single observed reward plus the discounted value estimate of the state you actually landed in — is the TD target. After every step the agent nudges V(s) toward that target:
V(s) ← V(s) + α · ( r + γ·V(s′) − V(s) )
The bracketed quantity δ = r + γ·V(s′) − V(s) is the TD error: how surprised you are, comparing your old prediction V(s) against one step of real reward plus your guess for the next state. α is the learning rate (step size).
This is called TD(0) (one-step lookahead). It is online (updates mid-episode, after every transition), it works on continuing non-terminating tasks, and it is model-free like MC — it still only calls step(), never P or R. The price is bias: early on, V(s′) is wrong, so the target is biased toward your own mistakes. The payoff is dramatically lower variance: one reward plus one value estimate is far less noisy than a whole episode's worth of random rewards. This bias-variance trade-off is the heart of why TD usually learns faster than MC in practice.
Python (in browser)
TD(0): after every step, V(s) ← V(s) + α(r + γV(s′) − V(s)). The whole value table slides toward the true values 1/6…5/6 while episodes are still running.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
To feel the difference, compare MC and TD head-to-head on the same walk with the same constant step size α. MC updates each visited state toward the full episode return; TD updates each state toward a one-step bootstrap. Watch how MC's estimates jump around more between runs (high variance) while TD's settle more smoothly — even though TD's early estimates are slightly biased by its own bad guesses.
In one sentence: MC has zero bias but high variance; TD adds a little bias (bootstrapping on its own estimates) but slashes variance and learns online. That trade is why TD-style updates power Sarsa, Q-learning, and the value heads of deep-RL agents you'll meet next.
Python (in browser)
MC vs TD(0) head-to-head: same α and episode budget. TD's lower spread (std) across seeds illustrates its lower-variance, online updates.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
The same TD(0) idea with a neural network: minimise the squared TD error r + γV(s′) − V(s). The tabular update is one gradient step on this loss.
What is the TD(0) target used to update V(s) after observing reward r and next state s′?
- TD(0) updates V(s) after every step toward a bootstrapped target: V(s) ← V(s) + α(r + γV(s′) − V(s)); the bracket is the TD error.
- TD is online and works on continuing tasks (no episode end required); MC is episodic and uses the full return — both are model-free (only step()).
- Bias-variance trade: MC is unbiased but high-variance; TD adds bias by bootstrapping on its own estimates but has much lower variance and usually learns faster.
The TD error drives Sarsa, Q-learning, and the value/critic networks in DQN, A2C and PPO — minimising squared TD error is the value-learning loss of essentially every deep-RL agent.
If you remove it: Without bootstrapping you are stuck with full-episode Monte Carlo: no online learning, no continuing tasks, and far noisier value estimates.