Temporal-Difference Learning

Temporal-difference (TD) learning is a family of machine learning methods for predicting future outcomes from sequential experience. Central to reinforcement learning, it adjusts predictions using newly observed rewards and other, currently estimated predictions, rather than waiting for a final outcome. This use of estimates to update estimates is called bootstrapping. TD methods combine learning from sampled experience with the recursive structure of dynamic programming, enabling incremental learning without an explicit model of environmental transitions. (people.cs.umass.edu)

Origins and conceptual basis

Richard S. Sutton’s 1988 paper, Learning to Predict by the Methods of Temporal Differences, formalized a class of incremental prediction methods and established convergence results for particular cases. It identified earlier related mechanisms in Arthur Samuel’s checkers program and adaptive heuristic critics. The defining idea was to assign credit through differences between temporally successive predictions, rather than exclusively through differences between predictions and final observed outcomes. (jmvidal.cse.sc.edu)

Unlike conventional supervised learning, TD learning does not require a completed target outcome for every update. A prediction can change as additional information arrives, and that change provides a learning signal for earlier predictions. The method therefore addresses temporal credit assignment: determining how observations or decisions earlier in a sequence relate to consequences that appear later. Although closely associated with reward maximization, its underlying prediction mechanism is more general than action selection. (jmvidal.cse.sc.edu)

Prediction and the TD error

A standard formulation uses a Markov decision process. At time $t$ , an agent occupies state $S_t$ , selects an action according to a policy $\pi$ , receives reward $R_{t+1}$ , and reaches $S_{t+1}$ . The state value function is the expected value of the discounted return:

v_\pi(s)= \mathbb{E}_\pi\!\left[ \sum_{k=0}^{\infty}\gamma^k R_{t+k+1} \mid S_t=s \right],

where $\gamma$ is the discount factor. This value satisfies a recursive Bellman equation. One-step TD prediction, called TD(0), replaces the unknown future value with its current estimate $V$ :

\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t), \qquad V(S_t)\leftarrow V(S_t)+\alpha_t\delta_t.

Here $\delta_t$ is the TD error and $\alpha_t$ is the learning rate. For a terminal transition, the successor value is conventionally zero. (andrew.cmu.edu)

As an illustrative calculation, suppose $V(S_t)=4$ , the reward is $1$ , $V(S_{t+1})=6$ , and $\gamma=0.9$ . The target is $6.4$ , so the TD error is $2.4$ . With $\alpha_t=0.1$ , the updated estimate is $4.24$ . This arithmetic shows how one observed transition moves a prediction toward a partly estimated target.

Comparison with other prediction methods

Monte Carlo methods update values toward observed returns, generally requiring an episode to finish before its complete return is available. TD(0) can update after each transition and can operate in continuing tasks without episode termination. Dynamic programming also bootstraps, but ordinarily calculates expectations using a model of transition probabilities and rewards; TD instead uses sampled transitions. (people.cs.umass.edu)

Bootstrapping exchanges dependence on complete outcomes for dependence on current estimates. Monte Carlo returns can have substantial variance, whereas TD targets can be affected by inaccurate successor predictions. Consequently, neither method is universally superior: their behavior depends on the task, representation, data, and update settings. (andrew.cmu.edu)

Multistep learning and eligibility traces

Multistep TD methods use several observed rewards before bootstrapping. Their $n$ -step target is

G_t^{(n)} = \sum_{k=0}^{n-1}\gamma^kR_{t+k+1} +\gamma^nV(S_{t+n}),

with appropriate adjustment when termination occurs earlier. These methods interpolate between one-step prediction and learning from complete returns. (jmlr.org)

TD( $\lambda$ ) combines information from returns of different lengths. Its backward-view implementation uses eligibility traces: decaying records of recently visited states or recently active features. A new TD error can therefore modify several earlier predictions, rather than only the immediately preceding one. The trace parameter $\lambda$ controls how strongly earlier activity remains eligible for updates. (jmlr.org)

Conventional forward and backward views need not be exactly equivalent when estimates change during an episode. True online TD( $\lambda$ ) introduces modified traces and corrections that preserve equivalence to an online forward view for linear prediction at arbitrary step sizes. (proceedings.mlr.press)

Learning to select actions

TD prediction evaluates a policy; TD control combines value learning with changes in action selection. Sarsa updates an action-value estimate using the reward and the estimated value of the next action actually selected. It is an on-policy method because its target follows the policy generating experience. (people.cs.umass.edu)

Q-learning instead uses the highest estimated successor action value:

Q(S_t,A_t)\leftarrow Q(S_t,A_t)+ \alpha_t\left[ R_{t+1}+\gamma\max_a Q(S_{t+1},a)-Q(S_t,A_t) \right].

It exemplifies off-policy learning: the policy being learned can differ from the behavior used to collect observations. Watkins and Dayan’s 1992 analysis established convergence to optimal action values under specified tabular conditions, including repeated sampling of all state–action pairs and suitable step sizes. (gatsby.ucl.ac.uk)

Function approximation and stability

Large state spaces often require function approximation rather than a separate table entry for every state. For a differentiable estimate $V_\theta$ , a common update is

\theta\leftarrow\theta+ \alpha_t\delta_t\nabla_\theta V_\theta(S_t).

This is a semi-gradient update: it uses the gradient of the current prediction while treating the bootstrapped target as fixed during that update. It is not generally the full gradient of a squared TD-error loss function. (andrew.cmu.edu)

Tsitsiklis and Van Roy’s 1997 analysis established convergence and approximation-error results for linear TD under stated assumptions about sampling, features, and step sizes. The limiting approximation is characterized through projected value equations, rather than necessarily minimizing ordinary prediction error. Their work also demonstrated that nonlinear approximation can produce divergence. (web.mit.edu)

Combining bootstrapping, approximation, and off-policy sampling creates additional stability problems. Gradient-TD methods and emphatic TD were developed to obtain convergence guarantees under specified off-policy conditions. Such guarantees depend on their assumptions; they do not automatically extend to arbitrary neural networks, data distributions, or constant learning rates. (arxiv.org)

References

Learning to Predict by the Methods of Temporal Differencesjmvidal.cse.sc.edu
Chapter 6: Temporal Difference Learningpeople.cs.umass.edu
Reinforcement Learning: An Introductionandrew.cmu.edu
True Online Temporal-Difference Learningjmlr.org
True Online TD(lambda)proceedings.mlr.press
Q-learninggatsby.ucl.ac.uk
An Analysis of Temporal-Difference Learning with Function Approximationweb.mit.edu
An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learningarxiv.org