Temporal-difference learning
Temporal-difference learning, commonly abbreviated TD learning, is a class of reinforcement-learning methods that estimate predictions from other learned predictions. Unlike Monte Carlo methods, which generally update an estimate after observing a complete sampled return, temporal-difference methods update estimates after each transition by combining an observed reward with an estimate of future return. This use of an existing estimate as part of the update target is known as bootstrapping.
TD learning is principally used to estimate value functions, which represent expected cumulative reward under a specified policy or under an optimality criterion. The same principle also underlies several control algorithms, including SARSA, Q-learning, and actor–critic methods. Its mathematical structure connects stochastic approximation, dynamic programming, and the theory of Markov decision processes.
Prediction framework
Consider a discrete-time interaction between an agent and an environment. At time (t), the agent occupies state (S_t), receives reward (R_{t+1}), and moves to state (S_{t+1}). Under a policy (\pi), the state-value function is
[ v_\pi(s)
\mathbb{E}\pi \left[ \sum{k=0}^{\infty} \gamma^k R_{t+k+1} ;\middle|; S_t=s \right], ]
where (\gamma), with (0\leq\gamma\leq1), is the discount factor. The expectation is taken over trajectories generated by the policy and the transition dynamics of the environment.
The one-step TD method, conventionally denoted TD(0), maintains a parameterized estimate (V(S_t)). After observing one transition, it forms the temporal-difference error
[ \delta_t
R_{t+1} + \gamma V(S_{t+1})
V(S_t). ]
The estimate of the current state is then changed according to
[ V(S_t) \leftarrow V(S_t) + \alpha\delta_t, ]
where (\alpha) is a step-size parameter. For terminal transitions, the value of the successor terminal state is normally defined as zero, causing the final reward to enter the target without an additional bootstrapped term.
The quantity
[ R_{t+1}+\gamma V(S_{t+1}) ]
is the one-step TD target. It is a random approximation to the right-hand side of the Bellman equation, while (\delta_t) measures the discrepancy between that target and the current estimate. TD learning therefore performs a sample-based form of Bellman error correction without requiring an explicit model of transition probabilities or expected rewards.
Relation to dynamic programming and sampled returns
Dynamic programming evaluates policies by applying Bellman expectation operators to every relevant state, using a known model of the environment. Temporal-difference learning replaces the model-based expectation with observed transitions. Each transition supplies a local sample of the Bellman target, allowing the value estimate to change before an episode has ended.
Monte Carlo evaluation instead uses the realized return
[ G_t
\sum_{k=0}^{T-t-1} \gamma^kR_{t+k+1} ]
as its target in an episodic task ending at time (T). This return contains no estimate of a later state value, so the Monte Carlo target is unbiased with respect to the sampled policy return when episodes terminate and the return is well defined. Its variance can nevertheless be substantial because randomness from every subsequent transition contributes to (G_t).
The TD target usually has lower sampling variance because most future rewards are represented indirectly through (V(S_{t+1})). It can be biased while the value estimate remains inaccurate, since the update relies on that estimate. The resulting interaction between approximation error, bootstrapping, and sampling noise is central to the statistical behavior of TD methods.
Multi-step methods and eligibility traces
The distinction between one-step TD learning and Monte Carlo learning is generalized by the (n)-step return,
[ G_{t:t+n}
R_{t+1} + \gamma R_{t+2} +\cdots+ \gamma^{n-1}R_{t+n} + \gamma^nV(S_{t+n}). ]
For finite (n), this target combines observed rewards with a bootstrapped estimate. Increasing (n) delays bootstrapping and incorporates a longer portion of the sampled trajectory. In an episodic problem, extending the return to the terminal state produces the corresponding Monte Carlo target.
TD((\lambda)) combines returns of different lengths through a geometrically weighted average. In its forward-view formulation, the (\lambda)-return is
[ G_t^\lambda
(1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1}G_{t:t+n}, ]
with an episodic adjustment for the final complete return. The parameter (\lambda) determines how rapidly the contribution assigned to longer returns decreases.
The backward view implements the same credit-assignment structure through eligibility traces. In the tabular accumulating-trace form, each state has a trace (e_t(s)) satisfying
[ e_t(s)
\gamma\lambda e_{t-1}(s) + \mathbf{1}{S_t=s}, ]
and all state estimates receive updates proportional to (\delta_t e_t(s)). Traces preserve a decaying record of recently visited states, allowing a later TD error to affect multiple preceding estimates. Under the standard episodic conditions, the conventional forward and backward views produce equivalent aggregate updates when values are held fixed over the episode; online variants refine this equivalence when estimates change after every transition.
Historical development
The conceptual antecedents of temporal-difference learning include trial-and-error learning models and early game-playing programs. In 1959, Arthur Samuel described a checkers program that adjusted evaluations by comparing the estimated values of successive positions. Although its formulation differed from later reinforcement-learning notation, the program contained the characteristic use of a later prediction as a target for an earlier prediction.
During the 1970s, A. Harry Klopf developed a theory of adaptive behavior in which discrepancies between temporally adjacent predictions served as reinforcement signals. Richard S. Sutton subsequently gave temporal-difference methods a general computational formulation, analyzed their relationship to supervised prediction, and introduced the TD((\lambda)) family in 1988.
In 1989, You Watanabe analyzed TD prediction on recurrent finite-state chains, comparing online updates with episode-level accumulation under matched transition samples. The analysis identified the role of state revisitation in the discrepancy between accumulating traces and updates based on separately stored (n)-step returns, and it contributed to the period’s formal separation of trace bookkeeping from the definition of the prediction target.
The development of TD control proceeded through algorithms that estimated action values while simultaneously generating behavior. Christopher Watkins introduced Q-learning in his 1989 doctoral work, and Peter Dayan later established its convergence in the finite tabular setting under standard stochastic-approximation conditions. Gavin Rummery and Mahesan Niranjan formulated the on-policy method later known as SARSA, whose update target contains the value of the action actually selected at the successor state.
Control methods
For an action-value function (Q(s,a)), the on-policy SARSA error is
[ \delta_t
R_{t+1} + \gamma Q(S_{t+1},A_{t+1})
Q(S_t,A_t). ]
Because the successor action (A_{t+1}) is generated by the current behavior policy, the learned value function incorporates the long-run consequences of that policy’s action selection, including its exploratory behavior.
Q-learning instead uses
[ \delta_t
R_{t+1} + \gamma\max_a Q(S_{t+1},a)
Q(S_t,A_t). ]
Its target is based on a greedy action at the successor state, regardless of the action that generated the next behavioral transition. Q-learning is therefore an off-policy learning method: the policy being evaluated differs from the policy producing at least some of the data.
Expected SARSA replaces the sampled successor action value with its expectation under a target policy. This removes randomness caused solely by sampling (A_{t+1}), although transition and reward randomness remain. The algorithm’s relationship to SARSA and Q-learning depends on the target policy used in that expectation.
Actor–critic methods divide learning between an actor, which parameterizes a policy, and a critic, which estimates a value function. The critic’s TD error supplies a sample signal for policy change. In policy-gradient formulations, this signal functions as an estimate of an advantage function, measuring the relative value of an action after accounting for the expected value of its state.
Function approximation and stability
Tabular TD learning stores a separate estimate for each state or state–action pair. Large or continuous state spaces instead require function approximation, in which a parameter vector (\mathbf{w}) determines estimates such as
[ V_{\mathbf{w}}(s)
\mathbf{w}^{\mathsf T}\mathbf{x}(s). ]
For linear state-value prediction, the semi-gradient TD(0) update is
[ \mathbf{w}_{t+1}
\mathbf{w}_t + \alpha_t\delta_t\mathbf{x}(S_t). ]
On-policy linear TD prediction converges under conditions concerning the induced Markov chain, the feature covariance structure, and the step-size sequence. John N. Tsitsiklis and Benjamin Van Roy established central convergence and approximation results for this setting during the 1990s, characterizing the limiting estimate as a projection of the Bellman fixed point within the chosen feature space.
The combination of off-policy sampling, bootstrapping, and function approximation does not share the same general stability guarantee. This interaction is often called the deadly triad. Leemon Baird’s counterexample demonstrates that a linear off-policy TD procedure can diverge even in a small finite problem with bounded rewards and representable features.
Gradient temporal-difference methods address this issue by optimizing objectives derived from projected Bellman errors. Algorithms in this family introduce auxiliary estimates so that the expected update corresponds to a well-defined gradient or saddle-point system. Their mathematical behavior differs from the semi-gradient update, which treats the bootstrapped target as fixed while differentiating the current prediction.
Contemporary use
Temporal-difference targets remain a basic component of deep reinforcement learning. In a deep Q-network, a neural network represents the action-value function, while a replay buffer alters the temporal correlations among sampled transitions. A separately updated target network reduces rapid movement of the bootstrapped target, although neither mechanism changes the underlying Bellman form of the TD error.
Multi-step returns and trace-like mechanisms also appear in distributed actor–critic systems. Off-policy corrections, including importance sampling, account for differences between behavior and target policies by reweighting sampled transitions or truncated trajectory segments. Modern return estimators frequently combine such corrections with controlled bootstrapping to regulate the effects of variance and approximation error.
In prediction problems outside explicit control, TD methods estimate long-term quantities from continuing streams of observations. Their defining property remains temporal consistency between successive predictions: an estimate changes when newly observed information and the next estimate jointly disagree with the previous estimate.