In the theoretical foundation of reinforcement learning (RL), few concepts are as comforting as the contraction mapping. When we update a value function using a standard Bellman expectation or optimality operator, we rely on the discount factor $\gamma < 1$ to act as a mathematical compressor. Under the maximum norm, applying the operator to two different value functions brings them closer together by a factor of at least $\gamma$.
This geometric shrinking guarantees two elegant properties: a unique fixed point (the optimal value function) exists, and repeatedly applying the operator will inevitably find it. As shown in the foundational work by Tommi Jaakkola et al. in Convergence of Stochastic Iterative Dynamic Programming Algorithms, extending classical stochastic approximation theory to handle these maximum norm contractions is what proves that algorithms like Q-learning and TD($\lambda$) reliably converge.
But what happens when this gravitational pull disappears? In many realistic, long-horizon, or structurally complex settings, the Bellman operator ceases to be a contraction. Without this property, value functions can drift, oscillate, or diverge entirely.
Why the Contraction Breaks
The loss of the contraction property typically stems from three distinct sources: undiscounted objectives, algorithmic smoothing, or structural complexities in the environment.
1. Undiscounted and Average-Reward Settings
When modeling infinite-horizon tasks without a discount factor ($\gamma = 1$), we often switch to the average-reward criterion, maximizing the expected reward per time step. As noted by Kihyuk Hong et al. in Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs, the standard Bellman operator loses its shrinking error property in this regime. Instead, it becomes merely non-expansive, meaning it prevents distances between value estimates from growing, but fails to make them smaller (Shangtong Zhang et al. in Almost Sure Convergence of Average Reward Temporal Difference Learning).
Worse still, the average-reward Bellman equation exhibits shift invariance: if a value function $v$ satisfies the equation, then $v + c$ (adding a constant $c$ to all states) is also a valid solution. As Sheng Zhang et al. explain in Finite Sample Analysis of Average-Reward TD Learning and $Q$-Learning, this non-uniqueness means there is no single fixed point to pull iterations toward, causing standard value iteration to drift or climb toward infinity (JongMin Lee et al. in Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes).
2. Algorithmic and Operator Choices
Sometimes, non-contraction is a byproduct of the operators we design for exploration or representation:
- Softmax Operators: To balance exploration and exploitation, algorithms often replace the hard
maxoperator with a smooth alternative like the Boltzmann softmax. However, Kavosh Asadi et al. demonstrate in An Alternative Softmax Operator for Reinforcement Learning that standard Boltzmann softmax operators fail to satisfy the non-expansion property, which can cause value iterations to oscillate. To fix this, Ling Pan proposes the Dynamic Boltzmann Softmax Updates framework, dynamically tuning the temperature parameter over time to recover convergence guarantees. - Distributional Control: In Distributional RL, we evaluate the entire distribution of returns rather than just their expected value. While policy evaluation operators in this space can contract under specific metrics, the optimality operator used for control (finding the best policy) does not necessarily share this property, introducing theoretical instability (Marc G Bellemare et al. in A Distributional Perspective on Reinforcement Learning).
3. Structural and Hybrid Environments
Complex task structures frequently break standard contraction assumptions:
- Stochastic Shortest Path (SSP): In SSP problems, an agent must reach a goal state while minimizing cumulative costs without a discount factor. Value iteration can easily diverge here because there is no inherent mathematical horizon constraining the value estimates (Yifei Min et al. in Learning Stochastic Shortest Path with Linear Function Approximation).
- Modified Policy Iteration: Hybrid algorithms that perform multiple policy evaluation steps between policy updates generate operators that do not behave as contractions in any norm, rendering standard stability proofs insufficient (Bruno Scherrer et al. in Approximate Modified Policy Iteration).
- Temporal Logic Objectives: When optimizing for complex Linear Temporal Logic (LTL) goals without discounting, the Bellman equation loses its contraction property, allowing agents to converge to incorrect value functions that misrepresent the true probability of satisfying the goal (Zetong Xuan et al. in On the uniqueness of solution for the Bellman equation of LTL objectives).
The Consequences of Non-Contraction
When an operator stops contracting, standard iterative solvers become unstable. Errors introduced by function approximation or sample noise no longer shrink over time; instead, they propagate and compound (William Powell et al. in Offline Actor-Critic for Average Reward MDPs). This makes deriving finite-time or sample-complexity guarantees exceptionally difficult, especially in offline scenarios where data coverage is limited (Jongmin Lee et al. in Finite-Time Bounds for Average-Reward Fitted Q-Iteration).
Restoring Stability: Algorithmic Remedies
To overcome these challenges, researchers have developed several core mechanisms to stabilize non-contractive operators.
Halpern's Anchoring
If a non-expansive operator allows value functions to drift freely, we can anchor them. Halpern's anchoring is a classical fixed-point technique that modifies the standard iterative update by mixing a small fraction of a fixed reference vector (the "anchor") back into the iteration:
$$v_{k+1} = (1 - \alpha_k) T v_k + \alpha_k v_0$$
Here, $T$ is the non-contractive Bellman operator, and $v_0$ is the anchor. By choosing a sequence of weights $\alpha_k \to 0$, the anchor provides an artificial, decaying contraction effect that tethers the value function and prevents it from drifting to infinity.
In Accelerating Value Iteration with Anchoring, JongMin Lee et al. utilize this mechanism to design Anc-VI, achieving an optimal $O(1/k)$ convergence rate for Bellman error in undiscounted scenarios. The authors expand this concept to model-free settings in Near-Optimal Sample Complexity for MDPs via Anchoring, eliminating the need for restrictive prior knowledge about environmental mixing times or bias vector norms.
Discounted Reductions
Another strategy is to approximate the non-contractive average-reward problem using a sequence of well-behaved discounted problems where $\gamma$ approaches 1. Zachary Andrew Roch et al. formalize this in A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward, identifying a specific, non-asymptotic discount factor that allows algorithms to leverage standard discounted contraction properties while bounding the approximation error relative to the true average-reward objective.
Alternative Seminorms and Optimization
When standard Euclidean or maximum norms fail to show contraction, we can change the mathematical lens:
- Span Seminorm: Instead of measuring absolute values, the span seminorm measures the variance of the value function across states, effectively neutralizing the shift-invariance problem. However, as Zaiwei Chen notes in Non-Asymptotic Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes, this approach requires adaptive stepsizes to guarantee convergence when the underlying MDP is not weakly communicating.
- Primal-Dual Formulations: Rather than trying to fix value iteration, we can bypass the Bellman operator entirely. By framing policy evaluation as a min-max optimization over stationary state-action distributions, methods like the Log Density Policy Gradient circumvent the need for contractive value updates altogether (Pulkit Katdare et al. in Towards Provable Log Density Policy Gradient).
Key Foundational Work
Convergence of Stochastic Iterative Dynamic Programming Algorithms (1993) — contributed 1 concept elements to this direction.
Suboptimality Bounds for Stochastic Shortest Path Problems (2011) — contributed 1 concept elements to this direction.