In standard reinforcement learning (RL), we typically rely on a discount factor ($\gamma < 1$) to ensure mathematical tractability. This discount factor guarantees that the Bellman operator is a strict $\gamma$-contraction mapping. By the Banach fixed-point theorem, repeatedly applying a contraction mapping shrinks the distance between any two value function estimates, pulling them reliably toward a unique optimal solution.
However, many real-world problems—such as network routing, robotic locomotion, and inventory management—are inherently continuing, infinite-horizon tasks where discounting artificializes the objective. In these settings, it is more natural to maximize the average reward per time step.
The mathematical challenge of average-reward RL is that setting $\gamma = 1$ destroys the contraction property. The Bellman operator becomes merely non-expansive: it preserves distances but no longer shrinks them. Because rewards accumulate indefinitely, absolute value estimates drift toward infinity during iterative updates, causing numerical overflow and algorithmic divergence. To restore stability, a rich line of research focuses on anchoring, centering, and clipping value functions.
Relative Value Iteration and Grounding
To prevent absolute values from blowing up, we must shift our focus from absolute utilities to relative utilities. In average-reward settings, the absolute value of a state is less important than its bias—how much better or worse it is to start in that state compared to a baseline.
Early foundational work by Singh in Reinforcement Learning Algorithms for Average-Payoff Markovian Decision Processes and Mahadevan in An Average-Reward Reinforcement Learning Algorithm for Computing Bias-Optimal Policies introduced Relative Value Iteration (RVI) to operationalize this intuition. The core mechanism is simple: at each update step, choose a designated reference state $s_0$ and subtract its value from all other states:
$$V_{k+1}(s) = \mathcal{T}V_k(s) - \mathcal{T}V_k(s_0)$$
By fixing the value of the reference state to zero, the algorithm grounds the coordinate system. The uniform growth caused by the infinite accumulation of the average reward is stripped away at every step, leaving only the bounded, relative differences necessary to identify optimal policies. As shown by Murthy et al. in Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms, this representational strategy allows for the definition of a stable Bellman operator that functions entirely without a discount factor.
This centering mechanism has been adapted across various settings:
- Continuous States: Sharma et al. extended RVI to continuous state spaces in Approximate Relative Value Learning for Average-reward Continuous State MDPs by subtracting the minimum value of the current iterate rather than a single state's value.
- Stochastic Games: Akian et al. combined relative value updates with Krasnoselskii-Mann damping in Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration to achieve logarithmic convergence rates in zero-sum games.
- Robust and Risk-Aware RL: Wang et al. leveraged relative value centering to guarantee convergence for robust model-free algorithms (Model-Free Robust Average-Reward Reinforcement Learning) and robust model-based algorithms (Robust Average-Reward Markov Decision Processes). Similarly, Wang et al. applied relative adjustments to prevent numerical overflow when calculating risk-sensitive costs over infinite horizons (Planning and Learning in Average Risk-aware MDPs).
- Deep RL: Hisaki et al. integrated RVI into the Soft Actor-Critic framework (RVI-SAC: Average Reward Off-Policy Deep Reinforcement Learning), demonstrating that bounding Q-values via reference subtraction eliminates the need to tune the sensitive discount factor $\gamma$ in continuous control tasks.
Fixed-Point Anchoring for Accelerated Convergence
While subtracting a reference scalar keeps value estimates bounded, it does not change the underlying non-expansive nature of the operator. To establish fast, finite-time sample complexity bounds, recent theoretical work introduces fixed-point anchoring—frequently drawing on Halpern’s iteration technique.
Instead of merely shifting the value vector, anchoring explicitly mixes the output of the non-expansive Bellman operator $\mathcal{T}$ with a fixed initial anchor point $V_0$:
$$V_{k+1} = (1 - \alpha_k) \mathcal{T}V_k + \alpha_k V_0$$
where $\alpha_k$ is a vanishing step size.
The anchor acts as a contractive regularizer, akin to weight decay. It exerts a directional pull that forces the iterative sequence to converge reliably toward a unique solution, even when the mathematical operator itself lacks a natural contractive pull.
Lee et al. demonstrated in Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes that this anchoring mechanism accelerates the sublinear convergence rate of average-reward value iteration to $O(1/k)$, outperforming traditional relaxation techniques that only reach $O(1/\sqrt{k})$. The authors extended this principle in Near-Optimal Sample Complexity for MDPs via Anchoring to design SAVIA+, an algorithm that achieves near-optimal sample complexity without requiring prior knowledge of environmental mixing times or bias norms. For offline settings, Lee et al. incorporated this anchor mechanism into fitted Q-iteration (Finite-Time Bounds for Average-Reward Fitted Q-Iteration), providing the stability necessary to derive finite-time sample complexity bounds under general function approximation.
Span-Constrained Clipping
When moving from tabular environments to function approximation (such as linear MDPs), simply subtracting a single reference state's value is no longer sufficient. Because function approximators generalize across states, errors in one region can cause the range of values across the state space—known as the span—to expand uncontrollably during exploration.
To maintain stability in these complex spaces, algorithms apply a clipping operation directly to the value function iterates based on the span of the optimal bias function:
$$\text{clip}(V(s)) = \max\left( -H, \min\left( H, V(s) \right) \right)$$
where $H$ is a bound proportional to the environment's span or diameter.
Clipping explicitly constrains the maximum possible difference between any two state value estimates. By forcing the value function to reside within a fixed function space, it prevents exploration bonuses from exploding and ensures that iterative updates remain stable.
Hong et al. utilized this clipping strategy in Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs to keep exploration bonuses statistically valid as the discount factor approaches one. Similarly, Chae et al. introduced the UCLK-C algorithm in Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span, proving that clipping the value function prevents the span of the bias function from exploding, thereby achieving minimax optimal regret bounds in linear mixture models.
Generalizing the Anchoring Principle
The core intuition of anchoring—using a stable, reliable reference to regularize an otherwise unstable optimization process—extends beyond average-reward value iteration into policy optimization and off-policy learning.
In policy optimization, value estimation often suffers from wild fluctuations. Wu et al. addressed this in Nearly Optimal Policy Optimization with Stable at Any Time Guarantee by maintaining a reference value function computed from historical empirical data. By anchoring current estimates to this statistically reliable baseline, the authors achieved a "Stable at Any Time" guarantee, removing state-space dependency factors from regret bounds.
In model-based RL, complex non-linear models like neural networks can cause optimization targets to shift drastically between iterations. Zhang resolved this in Conservative Dual Policy Optimization for Efficient Model-Based Reinforcement Learning by using a simple, stable reference model (such as a least-squares estimate) as a fixed anchor for policy updates, ensuring steady, monotonic policy improvement.
Even in discounted settings, off-policy data distribution mismatches can cause standard Bellman updates to diverge. As shown by Hallak et al. in Emphatic TD Bellman Operator is a Contraction, state reweighting serves a similar stabilizing purpose: it alters the underlying geometry of the update space to restore the strict contraction property of the Bellman operator, ensuring convergence when behavior and target policies differ.
Whether by subtracting a scalar baseline, mixing updates with an initial fixed point, or clipping functions within a bounded span, anchoring techniques provide the mathematical constraints necessary to stabilize reinforcement learning when standard contraction guarantees vanish.
Key Foundational Work
Reinforcement Learning Algorithms for Average-Payoff Markovian Decision Processes (1994) — contributed 2 concept elements to this direction.
An Average-Reward Reinforcement Learning Algorithm for Computing Bias-Optimal Policies (1996) — contributed 1 concept elements to this direction.