Learning to Predict by the Methods of Temporal Differences

Sutton frames the core challenge as a multi-step prediction problem. You observe a sequence of states $x_1, x_2, \ldots, x_m$ and eventually learn the outcome $z$. The goal is to produce a prediction $P_t$ at each step that estimates $z$ as accurately as possible.

The conventional supervised-learning approach treats each step as an independent observation-outcome pair $(x_t, z)$ and updates using the Widrow-Hoff (delta) rule:

Think of this like a university professor who collects all exam booklets and grades them only after the semester ends. Every student's midterm performance — a rich signal about what they know — is ignored until the final grade arrives. TD methods, by contrast, are like giving feedback after every quiz: each intermediate signal sharpens the next prediction.

Sutton's breakthrough is to notice that the total error $z - P_t$ can be decomposed into a telescoping sum of successive prediction differences:

$z - P_t = \sum_{k=t}^{m} (P_{k+1} - P_k)$

where $P_{m+1} \stackrel{\text{def}}{=} z$. Instead of waiting for $z$, the learner can update after each step using only the change from $P_t$ to $P_{t+1}$. This is the essence of temporal-difference learning.

Sutton defines a spectrum of TD methods parameterized by $\lambda \in [0, 1]$. The update rule is:

Think of $\lambda$ as a memory dial. Turn it all the way up ($\lambda = 1$) and the learner gives equal credit to all past observations — exactly like supervised learning. Turn it all the way down ($\lambda = 0$) and only the most recent step matters. In between, recent steps get exponentially more credit than distant ones, like a spotlight that fades with distance.

The key insight is that the exponential weighting $\lambda^{t-k}$ has a beautifully incremental form. Define the eligibility trace $e_t$:

$e_t = \nabla_w P_t + \lambda \, e_{t-1}$

This trace is a running sum that decays old gradients by $\lambda$ at each step. It allows TD($\lambda$) to be computed with constant memory per step — no need to store the entire history.

To test TD methods empirically, Sutton designed an elegantly simple experiment: a bounded random walk on 7 states (A through G). Every walk starts at the center state D. At each step the walk moves left or right with equal probability. If it reaches A (left edge) the outcome is $z = 0$; if it reaches G (right edge) the outcome is $z = 1$. The task is to predict, for each state, the probability of terminating at G.

The true probabilities are $\frac{1}{6}, \frac{2}{6}, \frac{3}{6}, \frac{4}{6}, \frac{5}{6}$ for states B through F. This problem is one of the simplest dynamical systems imaginable, yet it cleanly reveals the advantage of TD methods.

Sutton found two striking results. Under repeated presentations (showing the same training set until convergence), TD(0) achieved lower RMS error than the Widrow-Hoff procedure for every value of $\lambda < 1$. Under single presentation (one pass through the data), TD methods with $\lambda \approx 0.3$ performed best, but all $\lambda < 1$ beat the supervised approach.

Why does Widrow-Hoff — a method proven to minimize training-set error — lose? Because minimizing error on the training set is not the same as minimizing error on future data. TD(0) converges to the maximum-likelihood estimates consistent with the underlying Markov process, which generalize better.

At $\lambda = 0$, the update rule reaches its simplest and most distinctive form:

The term $(P_{t+1} - P_t)$ is now called the TD error and is universally denoted $\delta_t$ in reinforcement learning. It is the fundamental learning signal of modern RL: every time Q-learning, SARSA, or an actor-critic updates, it is computing a version of this error.

Bootstrapping — using your own estimate to improve your estimate — sounds circular, but Sutton proved it works. The intuition is that $P_{t+1}$ incorporates one more step of real-world information than $P_t$: it has seen the actual next state. This extra observation makes $P_{t+1}$ a better performance standard than the distant and noisy final outcome $z$.

The deepest contribution of the paper is proving that linear TD(0) converges. This was remarkable because the method learns from its own predictions, which are initially wrong. Earlier TD methods (Samuel's checkers, Holland's bucket brigade) worked well empirically but had no convergence guarantees.

Sutton proves two theorems for data generated by absorbing Markov chains with linearly independent observation vectors:

Theorem 2 (Convergence): With sufficiently small learning rate $\alpha$, linear TD(0) converges in expected value to the ideal predictions — the true expected outcomes for each state.

Theorem 3 (Optimality): Under repeated presentations of a finite training set, linear TD(0) converges to the maximum-likelihood estimates — the predictions that would be ideal if the training data perfectly described the true process. Widrow-Hoff, by contrast, converges to the estimates that minimize training-set error, which are generally suboptimal for future data.

Sutton extends TD methods beyond predicting a single final outcome to predicting cumulative costs that accumulate over a sequence. If $c_{t+1}$ is the cost incurred between steps $t$ and $t+1$, the prediction target becomes:

$z_t = \sum_{k=t}^{m} c_{k+1}$

The TD error generalizes to $(c_{t+1} + P_{t+1} - P_t)$, which is exactly the form used in modern reinforcement learning. With a discount factor $\gamma$, this becomes the discounted TD error:

$\delta_t = c_{t+1} + \gamma P_{t+1} - P_t$

This is the update signal of Sutton's own Adaptive Heuristic Critic (1984), and it is precisely the signal used by every modern value-based RL algorithm.

TD learning occupies a unique middle ground between two classical approaches:

Dynamic programming (Bellman, 1957) computes values from a known model of the environment: $V(s) = \sum_a \pi(a|s) \sum_{s'} p(s'|s,a) [r + \gamma V(s')]$. It is exact but requires a complete model — transition probabilities and rewards for every state-action pair.

Monte Carlo methods estimate values by averaging complete returns: $V(s) \approx \text{average of } G_t$ across episodes. They need no model but must wait until the end of each episode.

TD combines the best of both: like Monte Carlo, it learns from raw experience without a model. Like dynamic programming, it updates estimates based on other estimates (bootstrapping), allowing learning at every step without waiting for the episode to end.