Gradient Corrections for Stable Off-Policy Learning

34 concepts29 papers1 proposal

In reinforcement learning, three core algorithmic choices form a powerful combination: function approximation (to handle massive state spaces), bootstrapping (to update value estimates using other value estimates), and off-policy learning (to evaluate a target policy using data collected by a different behavior policy). Together, these three choices are known as the Deadly Triad. When combined naively, they cause standard temporal difference (TD) methods to diverge, causing value estimates to spiral to infinity.

Overcoming this instability requires fundamentally altering how we update value functions. By rewriting the optimization objectives or reweighting the data distribution, we can restore mathematical convergence guarantees without sacrificing the efficiency of linear function approximation.

The Geometry of Divergence

To understand why off-policy learning fails with function approximation, we must look at the geometry of the Bellman update.

In a tabular setting, the true Bellman operator is a contraction mapping: applying it brings our value estimates closer to the true value function. When we introduce linear function approximation, we restrict our value estimates to a lower-dimensional subspace spanned by our state features. Every time we apply a Bellman update, the resulting vector typically falls outside this subspace, forcing us to project it back down.

As John N. Tsitsiklis demonstrated in Analysis of Temporal-Diffference Learning with Function Approximation, if data is sampled on-policy, the combined operator—Bellman update followed by orthogonal projection—remains a contraction. The stationary distribution of the on-policy transitions ensures that the projection does not expand the norm of the value function.

True Value Space
     |
     |   [True Bellman Step]
     |----------> (Unconstrained Update)
     |                 |
     |                 | [Projection Matrix]
     |                 v
+----+---------------------------------+ Linear Subspace
     |           (Projected Update)

Under off-policy sampling, however, the state distribution shifts. The projection matrix is now weighted by the behavior policy's distribution, which no longer aligns with the target policy's transitions. This misalignment means the projection can actually stretch the vector. Over multiple iterations of bootstrapping, this stretching accumulates, leading to parameter divergence.

Bypassing the Double Sampling Problem

A natural response to this instability is to abandon semi-gradient TD updates and perform true gradient descent on an explicit error metric, such as the Mean Squared Bellman Error (MSBE). In Convergent Combinations of Reinforcement Learning with Linear Function Approximation, Ralf Schoknecht et al. proved that residual gradient algorithms can guarantee stability under arbitrary data sampling by optimizing this error directly.

However, true gradient descent on the MSBE introduces the double sampling problem. The gradient of the MSBE contains a product of expectations:

$$\nabla_\theta \text{MSBE} \propto \mathbb{E}[r + \gamma \phi(s')^T \theta - \phi(s)^T \theta] \mathbb{E}[\phi(s) - \gamma \phi(s')]$$

To approximate this gradient from data, we would need two independent samples of the next state $s'$ from the exact same starting state $s$. In a model-free setting, this is impossible without an environment reset.

To circumvent this, modern convergent off-policy methods minimize the Mean Squared Projected Bellman Error (MSPBE) instead. The MSPBE measures the Bellman error after it has been projected back onto the linear feature space. Minimizing the MSPBE ensures that the algorithm converges to the best possible representable solution.

The Saddle-Point Trick

How do we minimize the MSPBE without double sampling? The breakthrough lies in reframing the optimization as a convex-concave saddle-point problem.

By leveraging a mathematical identity, the inverse matrix inside the projected error can be expanded into a minimax optimization. This allows us to introduce an auxiliary weight vector, $w$, that runs on a faster timescale than our primary value parameters, $\theta$. This formulation was pioneered by Hamid Reza Maei et al. in Toward Off-Policy Learning Control with Function Approximation and Convergent Temporal-Difference Learning with Arbitrary Smooth Function Approximation.

The auxiliary variable $w$ effectively learns to predict the projected Bellman error. The primary parameters $\theta$ then use $w$ to apply a gradient correction to the standard TD update. The update rules for Temporal-Difference with Gradient Correction (TDC) take the form:

$$\theta_{t+1} = \theta_t + \alpha_t \delta_t \phi(s_t) - \alpha_t \gamma \phi(s_{t+1}) (\phi(s_t)^T w_t)$$

$$w_{t+1} = w_t + \beta_t (\delta_t - \phi(s_t)^T w_t) \phi(s_t)$$

The second term in the $\theta$ update acts as a stabilizer. It subtracts out the component of the update that would otherwise cause divergence under the off-policy distribution. Because this formulation splits the complex objective into two coupled linear updates, it completely avoids the double sampling problem.

Subsequent work has expanded this saddle-point framework to improve efficiency and feature selection. For instance, Simon S. Du et al. in Stochastic Variance Reduction Methods for Policy Evaluation applied variance reduction techniques to accelerate convergence, while Bo Liu et al. in Regularized Off-Policy TD-Learning introduced proximal mappings to enforce sparsity. Long Yang et al. further extended this to multi-step settings with On Convergence of Gradient Expected Sarsa(λ), proving that the saddle-point formulation remains robust across eligibility trace configurations.

Correcting the Distribution via Emphatic Updates

While Gradient TD methods stabilize learning by changing the objective function, an alternative paradigm stabilizes learning by changing the data distribution.

Introduced by Richard S. Sutton et al. in An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning, Emphatic TD (ETD) alters the magnitude of updates state-by-state using a scalar called the followon trace.

The followon trace dynamically measures how state transitions under the behavior policy map to the requirements of the target policy. By selectively emphasizing updates for states that are highly relevant to the target policy, ETD mathematically reconstructs the favorable algebraic properties of an on-policy distribution.

The key to ETD's convergence is that it ensures the underlying update matrix remains positive definite. When this matrix is positive definite, the expected update vector always points in a direction that reduces the distance to the true solution, preventing parameter divergence.

An empirical analysis by Sina Ghiassian et al. in A First Empirical Study of Emphatic Temporal Difference Learning demonstrated that this emphatic weighting provides a robust foundation for general-purpose value estimation, stabilizing updates even in complex on-policy settings where bootstrapping parameters vary across the state space.

Multi-Step Returns and Alternative Projections

The quest for off-policy stability naturally extends to multi-step returns, where balancing bias and variance is critical. Standard multi-step off-policy algorithms like Tree Backup and Retrace can still diverge when paired with linear function approximation.

To resolve this, Ahmed Touati et al. developed gradient-based variants in Convergent TREE BACKUP and RETRACE with Function Approximation, embedding eligibility traces directly into a primal-dual saddle-point framework. This allows agents to safely propagate multi-step returns off-policy. Similarly, Rohan Deb et al. in Schedule Based Temporal Difference Algorithms showed that integrating gradient corrections with flexible return schedules prevents the divergence typically seen in the Deadly Triad.

Standard TD:   Orthogonal Projection  ---> Destabilizes Off-Policy
Gradient TD:   Saddle-Point Correction ---> Restores Stability, Slower On-Policy
Oblique TD:    Oblique Projection     ---> Matches On-Policy Speed + Off-Policy Stability

Rather than modifying the update rules or weights, some approaches re-examine the geometry of the projection itself. Bo Liu et al. proposed Stable and Efficient Policy Evaluation, which replaces standard orthogonal projection with an oblique projection. By carefully selecting a projection matrix that accounts for the off-policy distribution shift, they match the stability guarantees of gradient methods while maintaining the rapid convergence speed of traditional on-policy TD methods.

Key Foundational Work

Analysis of Temporal-Diffference Learning with Function Approximation (1996) — contributed 3 concept elements to this direction.
Convergent Combinations of Reinforcement Learning with Linear Function Approximation (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_function_approximation_stability_9d38edec,
  title = {linear function approximation stability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-function-approximation-stability/rdr_9d38edecc78a475b8b2b23fb6a1fc44b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_function_approximation_stability_9d38edec_v1,
  title = {linear function approximation stability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-function-approximation-stability/rdr_9d38edecc78a475b8b2b23fb6a1fc44b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake