Sutton and Barto call temporal-difference (TD) learning "one of the central and novel ideas of reinforcement learning". It combines the best of the two previous approaches: like Monte Carlo, it learns directly from experience without a model; like dynamic programming, it bootstraps — updating estimates from other estimates — so it can learn after every step, without waiting for an episode to finish.
The TD(0) update#
After observing a transition $(S_t, A_t, R_{t+1}, S_{t+1})$, update the value of $S_t$ towards the TD target $R_{t+1} + \gamma V(S_{t+1})$:
The TD error $\delta_t$ measures the surprise: the difference between what we predicted and a better-informed estimate one step later.
Compare the targets:
| Method | Target for $V(S_t)$ | Needs model? | Bootstraps? |
|---|---|---|---|
| Dynamic programming | $\mathbb{E}[R_{t+1} + \gamma V(S_{t+1})]$ | Yes | Yes |
| Monte Carlo | $G_t$ (actual full return) | No | No |
| TD(0) | $R_{t+1} + \gamma V(S_{t+1})$ (one sample) | No | Yes |
Driving home: an intuition#
Sutton's example: you estimate your drive home will take 30 minutes. You leave work late and hit rain, and at the highway you revise your estimate to 40 minutes. Monte Carlo would wait until you arrive home to update your original estimate. TD updates immediately based on the new prediction — you do not need to reach the end to learn that leaving late in rain means a longer journey.
Bias and variance#
- MC targets are unbiased but high-variance (they sum many random rewards).
- TD targets have much lower variance (one reward plus an estimate) but are biased while $V$ is inaccurate.
In practice TD methods usually learn faster than MC on many problems, and they work for continuing (non-episodic) tasks. Under standard conditions (tabular values, appropriately decaying step sizes), TD(0) converges to $V^\pi$.
The random walk example#
import numpy as np
# 5 non-terminal states A..E in a row; start in C; step left/right with equal probability.
# Reward +1 on exiting right, 0 otherwise. True values: 1/6, 2/6, ..., 5/6.
true_v = np.arange(1, 6) / 6
def episode(rng):
s, traj = 2, []
while 0 <= s <= 4:
s2 = s + (1 if rng.random() < 0.5 else -1)
r = 1.0 if s2 == 5 else 0.0
traj.append((s, r, s2)); s = s2
return traj
def run(method, alpha, episodes=100, seed=0):
rng, V = np.random.default_rng(seed), np.full(5, 0.5)
for _ in range(episodes):
traj = episode(rng)
if method == "td":
for s, r, s2 in traj:
target = r + (V[s2] if 0 <= s2 <= 4 else 0.0)
V[s] += alpha * (target - V[s])
else: # every-visit Monte Carlo
G = traj[-1][1] # only the final reward is non-zero
for s, _, _ in traj:
V[s] += alpha * (G - V[s])
return np.sqrt(np.mean((V - true_v) ** 2))
for alpha in [0.05, 0.1]:
td = np.mean([run("td", alpha, seed=i) for i in range(50)])
mc = np.mean([run("mc", alpha, seed=i) for i in range(50)])
print(f"alpha={alpha}: RMS error TD={td:.3f} MC={mc:.3f}")n-step TD#
Between one-step TD and full Monte Carlo lies a spectrum. The n-step return uses $n$ real rewards and then bootstraps:
$n = 1$ is TD(0); $n = \infty$ is Monte Carlo. Intermediate $n$ often works best, balancing bias and variance.
TD(λ) and eligibility traces#
Instead of choosing one $n$, TD(λ) averages all n-step returns with weights $(1 - \lambda)\lambda^{n-1}$ — the λ-return. It can be implemented efficiently online with eligibility traces: each state keeps a decaying memory of how recently and frequently it was visited,
so each TD error updates all recently visited states — propagating credit backwards quickly. $\lambda = 0$ gives TD(0); $\lambda = 1$ approximates Monte Carlo. The same idea appears in modern deep RL as Generalised Advantage Estimation (GAE), used by PPO.
TD learning and the brain#
In the 1990s, Schultz, Dayan and Montague found that the firing of dopamine neurons in monkeys resembles a TD error: dopamine responds to unexpected rewards, shifts to predictive cues after learning, and dips when an expected reward is omitted. TD learning thus became one of the most successful computational theories in neuroscience.