Temporal-Difference Learning: Bootstrapping Value Estimates Before the Episode Ends

The core idea: learn a guess from a guess

Reinforcement learning agents want a value function Vπ(s) — the expected total (discounted) reward from state s under policy π: Vπ(s) = Eπ[ Σₖ γᵏ Rₜ₊ₖ₊₁ | Sₜ = s ]. The problem is that this expectation stretches to the end of the episode, which may be thousands of steps away or never arrive at all.

TD learning's insight is the Bellman consistency of Vπ: the value of a state equals the immediate reward plus the discounted value of the next state, Vπ(s) = Eπ[ Rₜ₊₁ + γ Vπ(Sₜ₊₁) ]. So instead of waiting for the true return Gₜ, TD forms a bootstrapped target Rₜ₊₁ + γ V(Sₜ₊₁) using its current estimate of the next state. The gap between where you thought you were and where the next step says you are is the TD error:

δₜ = Rₜ₊₁ + γ·V(Sₜ₊₁) − V(Sₜ)

The invariant is that at the true value function Vπ, the expected TD error is zero: E[δₜ | Sₜ] = 0 for all states. Learning is nothing more than nudging V to drive that expectation to zero. Because δₜ needs only the next state and reward, TD updates during the episode — the property Sutton called learning "before the final outcome is known."

TD(0), step by step

The simplest algorithm, TD(0) (one-step TD), evaluates a fixed policy π. It keeps a table V of one number per state and applies a single stochastic-approximation update per transition:

Initialize V(s) ← 0 for all s (V(terminal) = 0)
for each episode:
    s ← initial state
    while s is not terminal:
        a ← action from π(s)
        take a, observe reward r and next state s'
        δ ← r + γ·V(s') − V(s)      # TD error
        V(s) ← V(s) + α·δ            # move estimate toward target
        s ← s'

• α is the step size (learning rate), 0 < α ≤ 1. It controls how far each observation moves the estimate.
• γ ∈ [0, 1] is the discount factor. γ < 1 keeps returns finite in continuing tasks and weights near rewards more.
• The bracketed target r + γ·V(s') is biased (it uses an imperfect V(s')) but low variance (it depends on one random reward and one transition, not a whole trajectory).

This is online, model-free, and incremental: no transition probabilities, no episode buffer, no waiting. Control algorithms swap the state-value V for an action-value Q and pick actions greedily — SARSA uses the on-policy target r + γ·Q(s',a'), and Q-learning uses the off-policy target r + γ·maxₐ Q(s',a).

Complexity and convergence

Per transition, TD(0) reads V(s), reads V(s'), computes δ, and writes V(s): a constant number of arithmetic and table operations, so O(1) time per step regardless of |S| or |A|. Space is O(|S|) for the tabular value array (O(|S|·|A|) for action values). Contrast dynamic programming, whose synchronous backup costs O(|S|²·|A|) per sweep because it enumerates every successor of every state.

Convergence. Tabular TD(0) converges to Vπ with probability 1 under the Robbins–Monro conditions on the step sizes: Σₜ αₜ = ∞ and Σₜ αₜ² < ∞ (e.g. αₜ = 1/t), provided every state is visited infinitely often. The proof (Sutton 1988; Dayan 1992; Jaakkola, Jordan & Singh 1994) treats the update as stochastic approximation of a contraction mapping — the Bellman operator Tπ is a γ-contraction in the max norm, so its fixed point Vπ is unique.

• Bias–variance. The Monte Carlo target Gₜ is unbiased but its variance grows with episode length (it sums many random rewards). The TD target has variance from a single step but is biased while V is wrong. In practice TD's lower variance usually makes it learn faster.
• Rate. There is no clean O(f(n)) sample-complexity constant like sorting has; convergence speed depends on γ (harder as γ→1), the mixing of the Markov chain, and α. Larger γ means longer credit assignment and slower propagation of information.

TD(λ) and eligibility traces: the spectrum between TD and Monte Carlo

One-step TD bootstraps immediately; Monte Carlo never bootstraps. n-step TD sits in between, using the target Rₜ₊₁ + γRₜ₊₂ + … + γⁿ⁻¹Rₜ₊ₙ + γⁿV(Sₜ₊ₙ) — more real rewards, less bootstrap. TD(λ) elegantly averages all n-step returns with geometric weights (1−λ)λⁿ⁻¹, giving a single knob λ ∈ [0,1] where λ=0 recovers TD(0) and λ=1 recovers Monte Carlo.

The efficient online implementation uses eligibility traces e(s): a short-term memory that marks how "eligible" each recently visited state is for the current error. On every step you decay all traces by γλ, bump the current state's trace, then apply δ to every state in proportion to its trace:

e(s) ← γλ·e(s) for all s;   e(Sₜ) ← e(Sₜ) + 1
for all s:  V(s) ← V(s) + α·δₜ·e(s)

• Naively this is O(|S|) per step; with a list of states whose trace is above ε it is effectively O(active states).
• Traces spread each TD error backward in time, dramatically speeding credit assignment on long-delayed rewards.
• The equivalence theorem: the offline backward view (traces) computes exactly the same total update as the forward view (λ-weighted returns).

Where TD runs at scale: DQN, actor-critic, and function approximation

Real problems have too many states to tabulate, so V or Q becomes a parametric function V(s;θ) — a linear model or a neural network — and TD becomes a semi-gradient update: θ ← θ + α·δₜ·∇θ V(Sₜ;θ). It is "semi" because we differentiate only the current estimate, not the bootstrapped target (the target is treated as a constant).

• TD-Gammon (1992) trained a neural net with TD(λ), reaching near-world-championship play and rewriting backgammon opening theory.
• Deep Q-Networks (DQN, 2015) — DeepMind's Atari agent — is TD control with a CNN Q-function, a target network (a frozen copy of θ that stabilizes the bootstrap), and an experience replay buffer that breaks correlation between consecutive samples.
• Actor-critic and A3C/PPO use a TD-learned critic V(s;θ) to compute the advantage δₜ that guides the policy gradient; this is the workhorse of continuous-control and of the RL step in RLHF for language models.
• Neuroscience found the same math: dopamine neurons encode a reward-prediction error that matches δₜ (Schultz, Dayan & Montague, 1997), making TD a rare algorithm that predicted a biological signal.

Pitfalls, failure modes, and edge cases

TD's bootstrap is powerful but fragile. The classic warning is the deadly triad: combining (1) function approximation, (2) bootstrapping, and (3) off-policy training can make the value estimates diverge to ±∞ even with a perfectly linear model — Baird's counterexample is the canonical demonstration. Any two of the three are usually safe; all three together are not.

• Step-size sensitivity. Too large an α oscillates or blows up; too small crawls. Constant α tracks non-stationary targets but never fully converges (it keeps a residual noise floor).
• Maximization bias. Q-learning's maxₐ operator over noisy estimates systematically over-estimates action values. Double Q-learning (two decoupled tables/nets) removes this bias.
• Bootstrap on garbage. Early in training V is arbitrary, so TD is learning from a bad guess; it self-corrects, but a target network or slow α is often needed to keep the process stable.
• Discount edge cases. γ = 1 in a continuing task makes returns and thus values unbounded; terminal-state values must be pinned to 0 or the bootstrap leaks reward across episode boundaries.
• Non-Markov states. TD assumes the Bellman equation holds; if the state omits relevant history (partial observability), V(s') is not a sufficient statistic and the fixed point is biased.

When to reach for TD vs the alternatives

Choose based on what you can afford to wait for and what you know about the environment:

• Use TD when episodes are long, non-terminating, or you need to learn online from a live stream — a robot, a recommender, an ad server. Its O(1) per-step update and low-variance target let it start improving after the very first transition.
• Use Monte Carlo when episodes are short and always terminate, the environment badly violates the Markov assumption (so bootstrapping is misleading), or you want an unbiased value estimate for evaluation. MC has zero bootstrap bias but must wait for the return Gₜ.
• Use dynamic programming when you actually have the model P and R and |S| is small enough to sweep — value iteration and policy iteration compute Vπ exactly, no sampling needed, but at O(|S|²·|A|) per sweep.
• Tune λ to interpolate: intermediate λ (≈0.7–0.9) frequently beats both extremes because it blends TD's low variance with MC's low bias.

The one-sentence heuristic interviewers want: TD is the only one of the three that is simultaneously model-free and bootstrapping — that combination is exactly what makes it learn from raw experience, step by step, before the game ends.

TD(0) vs Monte Carlo vs Dynamic Programming for policy evaluation

Property	Dynamic Programming	Monte Carlo	TD(0)
Needs model P, R	Yes (full sweep)	No	No
Bootstraps (uses own estimate)	Yes	No	Yes
Update timing	Full backup	End of episode	Every step
Works on incomplete episodes	N/A	No	Yes
Variance / bias of target	None / exact	High var, unbiased	Low var, biased
Cost per update	O(|S|·|A|·|S|)	O(1) amortized	O(1)