Error Propagation in Approximate Dynamic Programming

26 concepts22 papers1 proposal

In reinforcement learning (RL), we rarely have the luxury of waiting for an episode to end to evaluate our choices. Instead, we rely on bootstrapping—updating our current estimate of a state's value based on our estimated value of the next state via the Bellman equation.

When combined with function approximators like deep neural networks to handle high-dimensional spaces, this recursive update mechanism introduces a fundamental vulnerability. A neural network inevitably introduces small local fitting errors. Because bootstrapping trains the network on its own previous predictions, these minor inaccuracies do not remain isolated. Instead, they feed back into the system, propagating and compounding across iterations.

This phenomenon is known as recursive error propagation. Understanding why this error loop occurs, how it destabilizes learning, and how modern algorithms break the cycle is essential to building stable value-based RL agents.


The Bootstrapping Feedback Loop

To understand why errors grow, imagine a game of telephone where each participant slightly misremembers the message before passing it on. In approximate dynamic programming, the Bellman operator acts as the transmission line.

As early as 1994, Justin A. Boyan et al. demonstrated this core instability in Generalization in Reinforcement Learning: Safely Approximating the Value Function. They showed that even in simple environments where the true underlying value function is perfectly smooth, combining recursive dynamic programming updates with function approximation can cause value estimates to spiral toward infinity or collapse into catastrophic policies.

The root cause is the coupling between the Bellman backup and the function approximator's generalization. When a network updates its value estimate for a specific state, its weights change, which inadvertently alters the value estimates of neighboring states. When the agent later bootstraps from those neighboring states, it ingests the corrupted values, creating a runaway feedback loop.


The Mechanics of Error Magnification

Why don't these errors simply average out over time? Several structural properties of standard reinforcement learning algorithms actively amplify noise rather than dampening it:

1. The Maximization Bias

The standard Bellman optimality operator relies on a hard maximization ($\max_{a} Q(s,a)$). If a function approximator randomly overestimates the value of a suboptimal action due to local noise, the max operator will greedily select it, propagating this positive error backward.

As Aaron Sidford et al. noted in Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model, greedy policies are highly sensitive to tiny value inaccuracies. In offline settings, this becomes fatal. Aviral Kumar et al. showed in Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction that when an agent queries the value of unseen actions outside the training distribution, it bootstraps off these unconstrained overestimates, completely destabilizing the training process.

2. Discount Factors and Iteration Order

Errors do not hit the system equally. Amir-massoud Farahmand et al. proved in Error Propagation for Approximate Policy and Value Iteration that approximation errors introduced in the later stages of training are far more damaging to the final policy than errors made early on. Furthermore, Tadashi Kozuno et al. demonstrated in Theoretical Analysis of Efficiency and Robustness of Softmax and Gap-Increasing Operators in Reinforcement Learning that standard value iteration amplifies errors at each step by a factor related to the discount rate $\gamma$, leading to an exponential blow-up in total error if left unchecked.

3. Downstream Effects on Exploration and Generalization

When errors propagate backward through the Bellman equation, they distort the agent's view of the world. Andrea Zanette et al. showed in Frequentist Regret Bounds for Randomized Least-Squares Value Iteration that backward-propagating estimation errors can cause an agent to become overly pessimistic about certain states, leading it to prematurely cease exploration of optimal paths.

Spatially, as Carlos Riquelme et al. observed in Adaptive Temporal-Difference Learning for Policy Evaluation with Per-State Uncertainty Estimates, when a network tries to fit sharp discontinuities in a value function, its local approximation errors bleed across the state space due to generalization, corrupting otherwise accurate regions.


Smoothing the Operator via Regularization

To break this amplification cycle, researchers modify the Bellman operator to make it less sensitive to single-step errors. The most prominent approach is policy regularization.

Instead of taking a hard maximum over actions, regularized methods smooth out the update. Mohammad Gheshlaghi Azar et al. introduced this concept in Dynamic Policy Programming with Function Approximation by adding a relative entropy penalty to the Bellman equation. This ensures smooth policy updates that resist single-step estimation noise, a concept that fits into a broader mathematical framework of regularized Markov Decision Processes analyzed by Bruno Scherrer et al. in A Theory of Regularized Markov Decision Processes.

Standard Bellman (Hard Max)  --> Selects absolute maximum --> Amplifies local noise
Regularized Bellman (Soft)   --> Averages over actions    --> Dampens error propagation

Why does this regularization stabilize the system? Nino Vieillard et al. provided the core intuition in Leverage the Average: an Analysis of KL Regularization in Reinforcement Learning: Kullback-Leibler (KL) divergence regularization forces the algorithm to effectively average value estimates across successive iterations. Rather than aggressively chasing the latest noisy network update, the algorithm acts as a low-pass filter, preventing errors from compounding.

To maximize this effect, Toshinori Kitamura et al. developed Geometric Value Iteration: Dynamic Error-Aware KL Regularization for Reinforcement Learning, which dynamically adjusts the strength of this KL regularization based on the actual amount of approximation error detected during training. Similarly, Lingwei Zhu et al. demonstrated in Cautious Actor-Critic that combining policy interpolation with entropy regularization prevents the critic's errors from destabilizing policy updates.

Furthermore, Lior Shani et al. showed in Exploration Conscious Reinforcement Learning Revisited that by designing agents to learn policies that explicitly account for their own future stochastic exploration—rather than targeting a rigid, absolute optimal value function—the system becomes significantly more robust to value estimation noise.


Uncertainty-Aware and Constrained Bootstrapping

A complementary strategy is to control where and when the agent bootstraps. If recursive propagation spreads error, the agent should avoid bootstrapping from states or actions where the function approximator is highly uncertain.

In Adaptive Temporal-Difference Learning for Policy Evaluation with Per-State Uncertainty Estimates, the authors utilize an ensemble of neural networks to track per-state uncertainty. If a temporal-difference (TD) target is highly uncertain, the algorithm dynamically switches to a Monte Carlo return. This breaks the recursive bootstrapping chain for that state, anchoring the value estimate in real data rather than letting a local error propagate.

In offline reinforcement learning, where out-of-distribution actions trigger catastrophic error propagation, Yixiu Mao et al. introduced the Doubly Mild Generalization for Offline Reinforcement Learning (DMG) framework. DMG allows the neural network to generalize slightly outside the dataset to find policy improvements, but it explicitly dampens how those generalized value "guesses" propagate backward through the Bellman update, preventing minor out-of-distribution errors from poisoning the entire value function.


Bypassing the Value Function via Planning and Alternative Objectives

Finally, some approaches mitigate error propagation by reducing the agent's reliance on a global value function for immediate action selection, or by avoiding backward induction entirely.

Aravind Rajeswaran proposed the POLO framework in Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control to decouple action selection from local value function errors. Instead of acting greedily based on a potentially corrupted value function, POLO uses an online model-predictive control planner to look ahead multiple steps. The value function is only used to guide the long-term horizon, drastically reducing the agent's sensitivity to local approximation errors.

In multi-agent scenarios, Julien Pérolat et al. demonstrated in On the Use of Non-Stationary Strategies for Solving Two-Player Zero-Sum Markov Games that cycling through a sequence of non-stationary strategies, rather than relying on a single stationary value function, provides a powerful buffer that prevents approximation errors from accumulating across iterations.

For specific problem domains like optimal stopping, recursive value estimation can be abandoned altogether. NIRANJAN DAMERA VENKATA et al. showed in Deep Recurrent Optimal Stopping that by framing the problem using a Bayesian network and optimizing it directly via policy gradients, recurrent neural networks can solve complex history-dependent tasks without suffering from the backward induction biases and recursive error propagation that plague traditional value-based RL.

Key Foundational Work

Generalization in Reinforcement Learning: Safely Approximating the Value Function (1994) — contributed 4 concept elements to this direction.
Error Propagation for Approximate Policy and Value Iteration (2010) — 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_recursive_error_propagation_19390c19,
  title = {recursive error propagation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-error-propagation/rdr_19390c1969f747248b19dc17096ee4c8},
  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_recursive_error_propagation_19390c19_v1,
  title = {recursive error propagation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-error-propagation/rdr_19390c1969f747248b19dc17096ee4c8/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