Temporal-Difference Convergence

Temporal-difference methods learn values from one-step surprises instead of full episodes, and with decaying steps those noisy updates settle on the true values.

Noisy one-step updates wobble around the true value and tighten onto it as the step size decays

Why Does This Exist?

Monte Carlo learning waits until an episode ends to update, which is slow when episodes run long. Temporal-difference methods update after every step using the current guess for the rest, which is fast but sounds circular: learning a guess from the same guess. Early practitioners worried the bootstrap would compound its own errors.

Convergence theory resolves the circle. TD(0) is a noisy contraction whose noise has zero mean, so averaging over visits washes the noise out while the contraction pulls toward truth. This page states the conditions and traces one numeric run.

The one idea you need first

The TD error at a transition $s \to s'$ with reward $r$ is $\delta = r + \gamma V(s') - V(s)$ : the surprise between the one-step lookahead and the current estimate. TD(0) moves $V(s)$ a little along $\delta$ . When $\delta$ averages to zero everywhere, $V$ satisfies Bellman's equation. Markov chains supply the sampling picture.

Think of It Like This

Adjusting a recipe one taste at a time

You are perfecting a soup but cannot wait until the final serving to judge. After each added ingredient you taste and nudge the seasoning, using your current sense of the final flavor as the reference. Early guesses mislead, but the errors point in different directions each round and cancel.

The taste gap is the TD error, the shrinking spoonfuls are decaying step sizes, and the finished flavor is the true value. Where the analogy stops: soup tasting has no discount factor, while TD weights near surprises more than distant ones through $\gamma$ .

How It Actually Works

Tabular TD(0) updates the visited state only:

V_{t+1}(s) = V_t(s) + \alpha_t(s) \, \delta_t, \quad \delta_t = r + \gamma V_t(s') - V_t(s)

In plain words: $\alpha_t$ is today's learning rate for $s$ , and $\delta_t$ mixes a real sample $(r, s')$ with the current guess $V_t(s')$ . Taking expectations over the sample recovers the exact Bellman backup plus zero-mean noise. The contraction pulls the mean toward $V^*$ , while the Robbins-Monro steps $\sum \alpha = \infty$ , $\sum \alpha^2 < \infty$ (for example $\alpha_t = 1/t$ ) visit enough yet damp noise.

With linear function approximation, TD converges to a different fixed point (the projected Bellman point), and with nonlinear nets it can diverge, which is why target networks and clipping exist.

Worked example

One state with true value $V^* = 10$ , $\gamma = 0$ for clarity so each sample is just a noisy reward: samples $12, 8, 11, 9$ . Start $V_0 = 0$ , steps $\alpha_t = 1/(t+1)$ .

$t=0$ : $\delta = 12 - 0 = 12$ , $V_1 = 0 + 1.0 \times 12 = 12$ . $t=1$ : $\delta = 8 - 12 = -4$ , $V_2 = 12 + 0.5(-4) = 10$ . $t=2$ : $\delta = 11 - 10 = 1$ , $V_3 = 10 + 0.333(1) \approx 10.333$ . $t=3$ : $\delta = 9 - 10.333 = -1.333$ , $V_4 = 10.333 + 0.25(-1.333) = 10.0$ . Four samples land exactly on 10, and later steps move less because $\alpha$ shrinks.

Code

1samples = [12.0, 8.0, 11.0, 9.0]2v = 0.03for t, r in enumerate(samples):4    alpha = 1.0 / (t + 1)  # Robbins-Monro: sums diverge, squares converge5    v = v + alpha * (r - v)  # TD error with gamma 06print(v)  # -> 10.0

The printout matches the hand trace. Change the steps to constant $0.5$ and the final value overshoots to $10.25$ , showing what the decay buys.

Watch Out For

Constant steps that never settle

A fixed $\alpha = 0.1$ keeps full sensitivity to late noise, so values orbit the truth instead of landing. The symptom is a healthy-looking early curve that plateaus into permanent wobble. Teams then blame the features.

Decay the rate or average the iterates once learning looks close. Constant steps track; decaying steps converge.

Off-policy updates without correction

TD that learns about a target policy from another policy's samples weights surprises wrongly: frequent-under-target transitions dominate. Q-learning handles this with a max, but plain TD needs importance weights. Skipping them biases the fixed point.

Check the behavior policy matches the update's assumption, or add the correction.

The Quick Version

TD(0) updates from one-step surprise $\delta = r + \gamma V(s') - V(s)$ .
Expected updates equal Bellman backups plus zero-mean noise, so averaging converges.
Robbins-Monro steps must sum to infinity with finite square sum, like $1/t$ .
The four-sample run $12, 8, 11, 9$ lands exactly on 10.0.
Linear approximation shifts the fixed point; nonlinear nets can diverge without stabilizers.