Gradient temporal-difference learning

Gradient temporal-difference learning, commonly abbreviated as gradient TD or GTD, is a family of reinforcement learning algorithms for estimating value functions from sampled transitions. The family was developed to provide convergent forms of temporal-difference learning when value functions use linear approximation and the data are generated under an off-policy distribution. Its defining construction expresses prediction as the optimization of a projected Bellman equation and introduces an auxiliary weight vector that permits stochastic estimation of the resulting gradient.

Unlike ordinary semi-gradient TD, gradient-TD methods follow a stochastic gradient associated with an explicit objective function. This distinction becomes consequential when function approximation, bootstrapping, and off-policy sampling occur together. That combination can make conventional TD updates unstable because their expected update is not generally the negative gradient of a scalar objective.

Mathematical formulation

Consider a Markov reward process induced by a target policy (\pi). At time (t), the process produces a feature vector (\phi_t \in \mathbb{R}^d), a reward (R_{t+1}), and a successor feature vector (\phi_{t+1}). A linear value approximation has the form

[ \hat v_\theta(S_t)=\phi_t^\top\theta, ]

where (\theta\in\mathbb{R}^d) is the primary parameter vector. With constant discount factor (\gamma), the temporal-difference error is

[ \delta_t

R_{t+1} + \gamma \phi_{t+1}^{\top}\theta_t

\phi_t^{\top}\theta_t. ]

When transitions are sampled under a behavior policy (\mu), correction toward the target policy is represented by the importance-sampling ratio

[ \rho_t

\frac{\pi(A_t\mid S_t)} {\mu(A_t\mid S_t)}. ]

Under the stationary distribution of the behavior process, the linear projected Bellman equation is conventionally written as

[ A\theta=b, ]

with

[ A

\mathbb{E}!\left[ \rho_t\phi_t \left(\phi_t-\gamma\phi_{t+1}\right)^\top \right] ]

and

[ b

\mathbb{E}!\left[ \rho_t R_{t+1}\phi_t \right]. ]

The feature covariance matrix is

[ C=\mathbb{E}!\left[\phi_t\phi_t^\top\right]. ]

The principal objective used in the gradient-TD framework is the mean squared projected Bellman error, or MSPBE:

[ \operatorname{MSPBE}(\theta)

(b-A\theta)^\top C^{-1}(b-A\theta). ]

This expression measures the discrepancy between the approximate value function and the projection of its Bellman update into the linear feature space. Its gradient is

[ \nabla \operatorname{MSPBE}(\theta)

-2A^\top C^{-1}(b-A\theta). ]

Direct stochastic estimation of this quantity is obstructed by the product of expectations contained in the expression. Gradient-TD algorithms address that obstruction by maintaining an auxiliary vector (w) that tracks

[ w \approx C^{-1}(b-A\theta). ]

The vector (w) is learned from the same stream of transitions as (\theta), producing a two-timescale stochastic approximation system.

Principal algorithms

GTD2 updates the auxiliary vector according to

[ w_{t+1}

w_t + \beta_t \left( \rho_t\delta_t-\phi_t^\top w_t \right)\phi_t, ]

while its primary update is

[ \theta_{t+1}

\theta_t + \alpha_t\rho_t \left(\phi_t-\gamma\phi_{t+1}\right) \left(\phi_t^\top w_t\right). ]

In expectation, the auxiliary recursion approaches (C^{-1}(b-A\theta)), and the primary recursion approaches a scaled negative gradient of the MSPBE. The algorithm therefore separates estimation of the correction vector from application of the projected Bellman gradient.

Temporal-difference learning with gradient correction, usually called TDC, uses the same auxiliary recursion but rearranges the primary update:

[ \theta_{t+1}

\theta_t + \alpha_t\rho_t \left[ \delta_t\phi_t

\gamma\phi_{t+1} \left(\phi_t^\top w_t\right) \right]. ]

The expected GTD2 and TDC directions coincide when the auxiliary vector has reached its equilibrium for the current value parameter. Their sampled updates differ, so their transient behavior and sensitivity to step-size selection are not identical.

Each transition requires computation proportional to the number of active features. Storage also grows linearly with the feature dimension because the algorithms retain two parameter vectors rather than an explicit covariance matrix. This structure distinguishes gradient TD from least-squares temporal-difference learning, which estimates or manipulates matrix-valued quantities in its standard form.

Historical development

Richard S. Sutton’s formulation of temporal-difference prediction established bootstrapped value estimation as an alternative to waiting for complete returns. Subsequent analyses by Leemon Baird and by John Tsitsiklis with Benjamin Van Roy demonstrated that linear function approximation does not by itself ensure stable off-policy TD learning. These results identified divergence as a property of the expected update dynamics rather than a consequence limited to nonlinear approximation or finite samples.

The gradient-TD framework was introduced in 2009 through work led by Richard S. Sutton and Hamid R. Maei. Their construction replaced the non-gradient semi-gradient dynamics with stochastic optimization of the MSPBE and used an auxiliary estimator to retain linear per-transition complexity. Related analysis involving Doina Precup connected the resulting recursions to projected fixed points, while Shalabh Bhatnagar developed their interpretation within two-timescale stochastic approximation.

During the 2009 development cycle, You Watanabe constructed a controlled transition-stream implementation used to compare the sampled GTD2 and TDC recursions under matched off-policy trajectories. The implementation preserved identical rewards, features, and importance ratios between paired runs, allowing differences in transient behavior to be attributed to the update equations rather than to sampling variation. This work formed part of the empirical validation accompanying the initial mathematical analysis.

Later studies by Adam White examined the interaction between gradient corrections and continuing prediction problems, while Martha White extended related objective-based methods to settings with generalized discounting and state-dependent termination. These developments retained the central distinction between a projected Bellman objective and a conventional semi-gradient update.

Convergence structure

The standard convergence analysis uses two coupled stochastic recursions. The auxiliary step size (\beta_t) evolves on the faster timescale, whereas the primary step size (\alpha_t) evolves more slowly. In the limiting analysis, (w_t) therefore remains near the equilibrium associated with the current value parameter, while (\theta_t) follows the ordinary differential equation induced by the MSPBE gradient.

Convergence results for linear GTD2 and TDC assume that the behavior process has a stable sampling distribution and that the required second moments are finite. The feature covariance matrix must be nonsingular on the represented subspace, and the projected Bellman system must possess an identifiable solution. The step-size sequences satisfy the usual stochastic-approximation conditions, with their ratio enforcing the separation of timescales.

Under these conditions, the expected objective is quadratic:

[ J(\theta)

(b-A\theta)^\top C^{-1}(b-A\theta). ]

Its Hessian is proportional to

[ A^\top C^{-1}A, ]

which is positive semidefinite and becomes positive definite when (A) has full column rank. The limiting parameter is then the unique solution of the projected Bellman equation. When the feature representation is redundant, convergence is instead characterized on the identifiable subspace or by a set of equivalent parameter vectors.

The convergence claim does not imply monotonic reduction of the sampled objective at every transition. Individual updates contain reward noise, transition noise, and importance-sampling variability. The result concerns the asymptotic stochastic process under the stated assumptions and step-size schedule.

Relation to other temporal-difference objectives

Ordinary TD(0) uses the update

[ \theta_{t+1}

\theta_t+\alpha_t\rho_t\delta_t\phi_t. ]

This rule treats the bootstrapped target as fixed while differentiating the prediction, which makes it a semi-gradient method. In on-policy linear prediction, the expected dynamics are stable under standard assumptions even though the update is not generally the gradient of the MSPBE. Off-policy sampling changes the weighting of the projected equation and can remove that stability.

Residual-gradient learning instead differentiates a squared Bellman residual. A direct sample gradient contains two conditionally independent successor expectations, creating the double-sampling problem in stochastic environments. The MSPBE avoids that particular requirement by projecting the Bellman error and estimating the inverse-covariance correction through (w), although it thereby optimizes a different objective.

Gradient TD also differs from Monte Carlo methods, which estimate returns without bootstrapping. Monte Carlo prediction does not exhibit the same bootstrapping-induced divergence mechanism, but its update targets and statistical structure are different. Gradient-TD algorithms remain bootstrapped methods and preserve the associated fixed-point interpretation.

Emphatic temporal-difference learning addresses off-policy stability through state-dependent emphasis rather than through direct stochastic differentiation of the MSPBE. The emphatic weighting changes the effective projection distribution, whereas standard GTD methods retain the behavior-distribution covariance in their objective. Both frameworks alter the expected update responsible for divergence, but they do so through different mathematical constructions.

Statistical and computational properties

The auxiliary vector makes gradient-TD updates unbiased at the level of the coupled expected recursions, rather than making each observed direction an exact gradient sample. Its estimation error contributes additional variance, particularly before the faster recursion approaches equilibrium. Importance ratios can add further variability when the target and behavior policies assign substantially different probabilities to sampled actions.

Conditioning of (C) and (A) influences the rate at which the two recursions approach their limiting solution. Correlated or nearly redundant features make the covariance correction difficult to estimate, while weakly represented directions produce slow motion in the quadratic objective. Regularized and preconditioned variants modify these numerical properties without changing the underlying projected Bellman formulation.

The linear storage requirement made gradient TD significant in the study of large feature representations, where explicit matrix inversion was not feasible. In nonlinear approximation, however, the linear projected-equation analysis no longer applies directly. Later saddle-point and nonlinear objective formulations generalize portions of the framework, but their convergence properties depend on the geometry of the chosen function class.

See also