Instability in Non-Linear Temporal Difference Learning

18 concepts19 papers1 proposal

Temporal Difference (TD) learning is a cornerstone of reinforcement learning, combining the timing of Monte Carlo methods with the bootstrapping of dynamic programming. When paired with linear function approximation, the mathematical landscape is elegant and well-behaved. As established by John N. Tsitsiklis in Analysis of Temporal-Diffference Learning with Function Approximation, linear TD learning guarantees convergence because projecting value estimates onto a linear subspace acts as a mathematical non-expansion, preserving the essential contraction properties of the Bellman operator.

However, when we swap linear models for non-linear function approximators like deep neural networks, this guarantee completely evaporates. In a non-linear setting, updating network weights to reduce the error at one state can unpredictably warp the value landscape of unobserved states. This interaction between non-linearities and temporal updates frequently causes value estimates to oscillate, stall in suboptimal local minima, or diverge boundlessly (Convergence of Reinforcement Learning with General Function Approximators; Fitted Natural Actor-Critic: A New Algorithm for Continuous State-Action MDPs).

Understanding why this divergence occurs—and how modern architectures circumvent it—requires looking closely at how non-linearity disrupts credit assignment, contraction mappings, and optimization gradients.

Feature Non-Stationarity and Stale Gradients

To understand the root of non-linear instability, consider how credit assignment works over time. Traditional multi-step bootstrapping methods like TD($\lambda$) rely on eligibility traces to pass rewards backward to preceding states.

As analyzed by Dhawal Gupta et al. in From Past to Future: Rethinking Eligibility Traces, eligibility traces implicitly assume a fixed feature space where state representations remain constant. When a non-linear neural network updates its weights, the underlying feature representation shifts dynamically across the entire state space. Consequently, the backward view of credit assignment relies on "stale" gradients computed from past feature configurations. This mismatch between historical credit allocation and the newly evolved feature space breaks the intended update logic, causing value estimates to degrade or diverge.

The Bellman Residual Minimization Alternative

Standard TD updates are semi-gradient methods: they update the current value estimate while treating the target value as a fixed constant, ignoring how changing the weights affects the target. This asymmetry is precisely what destroys the contraction mapping property in non-linear spaces (Borrowing From the Future: Addressing Double Sampling in Model-free Control).

An alternative approach is Bellman Residual Minimization (BRM), which treats value estimation as a true optimization problem by minimizing the squared error of the entire Bellman equation. Early work by Mance E. Harmon et al. (Advantage Updating Applied to a Differrential Game) leveraged residual gradients to decouple state values from action benefits, achieving stable convergence in continuous-time settings where standard Q-learning fails.

Standard TD (Semi-Gradient):
Weights influence only the current prediction, treating the target as a fixed constant.
[Current Prediction W] ---> [Target (Frozen W)] (Can cause uncontrolled error propagation)

Bellman Residual Minimization (True Gradient):
Weights influence both sides of the equation, minimizing internal inconsistency.
[Current Prediction W] <---> [Target W] (Mathematically stable, but suffers from double sampling)

Despite its stability, BRM introduces the "double sampling" problem: computing an unbiased gradient of the squared Bellman error requires two independent samples of the next state from the exact same starting state. In model-free environments, this is impossible without a simulator.

To resolve this, Yuhua Zhu et al. developed the "Borrowing From the Future" algorithm in Borrowing From the Future: Addressing Double Sampling in Model-free Control, which uses the subsequent step in a continuous trajectory to approximate the missing second sample, achieving near-unbiased gradient updates. By framing value estimation within online learning, Drew Bagnell et al. (Online Bellman Residual Algorithms with Predictive Error Guarantees) and Wen Sun et al. (Online Bellman Residual and Temporal Difference Algorithms with Predictive Error Guarantees) proved that minimizing the Bellman residual provides guaranteed bounds on long-term predictive error, even in highly unstable, non-Markovian, or adversarial environments.

Stabilizing Mechanics: Target Networks and Emphasis

In practical deep reinforcement learning, practitioners often rely on heuristic constraints to prevent non-linear TD from exploding. The most ubiquitous of these is the target network—keeping a frozen, lagging copy of the neural network weights to compute the bootstrapping targets.

Alexandre Piché et al. investigated this mechanism in Bridging the Gap Between Target Networks and Functional Regularization, revealing that target networks act as a form of functional regularization. However, the authors also showed that this implicit regularization does not always correspond to a convex function. This non-convexity can paradoxically introduce new theoretical instabilities, occasionally pushing weights away from the optimal solution and explaining why deep RL training remains highly sensitive to hyperparameter tuning.

Another rigorous stabilization strategy is Emphatic TD (ETD). Non-linear updates often suffer from severe transient phases where errors spike before reaching an asymptotic value (A First Empirical Study of Emphatic Temporal Difference Learning). By reweighting the updates of states based on how much they are emphasized by the follow-on trajectory, Sina Ghiassian et al. demonstrated in Should All Temporal Difference Learning Use Emphasis? that emphasis tames these chaotic transient phases, providing superior stability in both off-policy and on-policy scenarios. Similarly, alternative planning frameworks like Gradient Dyna, proposed by Yi Wan et al. (Planning with Expectation Models), restructure the update equations entirely to ensure value estimates do not grow boundlessly during off-policy planning.

Resolving the Theory-Practice Gap via Mean-Field Theory

Given these pervasive mathematical vulnerabilities, a glaring question remains: why do deep neural networks successfully solve complex reinforcement learning tasks in practice? As noted by Haoxing Tian et al. in On the Performance of Temporal Difference Learning With Neural Networks, a significant gap has persisted between empirical success and the pessimistic divergence proofs of classical theory.

A compelling resolution emerges when we look at the scale of the networks. Yufeng Zhang et al. provided a theoretical breakthrough in Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory by analyzing TD learning through the lens of mean-field theory.

The authors proved that when using overparameterized, wide two-layer neural networks, the learning dynamics escape the restrictive "lazy training" regime of Neural Tangent Kernels (NTK). Instead, the features are able to evolve significantly and adapt to the environment. In this overparameterized limit, the collective continuous movement of the network's parameters allows the system to globally minimize the Bellman error.

This explains why massive neural networks bypass the local non-convex instabilities that plague narrower non-linear models: overparameterization smooths the optimization landscape, allowing gradient-based TD methods to reliably converge to optimal feature representations.

Key Foundational Work

Analysis of Temporal-Diffference Learning with Function Approximation (1996) — contributed 1 concept elements to this direction.
Advantage Updating Applied to a Differrential Game (1994) — 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_function_approximation_divergence_302f3f11,
  title = {function approximation divergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/function-approximation-divergence/rdr_302f3f11bbdf411d8912e34180738f5b},
  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_function_approximation_divergence_302f3f11_v1,
  title = {function approximation divergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/function-approximation-divergence/rdr_302f3f11bbdf411d8912e34180738f5b/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