Convergence in Average Reward Reinforcement Learning

This direction is split into other directions: non-contractive Bellman operators. Its last version stays readable and citable here.

Version 1 of 1124 papers141 conceptsfrozen 2026-10-04

In standard Reinforcement Learning (RL), the discount factor $\gamma < 1$ is more than just a parameter for "patience"—it is the mathematical glue that holds the field together. When $\gamma < 1$, the Bellman operator is a contraction mapping, meaning that every time an agent updates its value estimates, those estimates are guaranteed to move closer to a unique, stable fixed point.

However, many real-world systems—like queueing networks, data centers, or inventory management—operate on an infinite horizon where we care about the average reward per time step rather than a discounted sum. In these settings, $\gamma$ is effectively 1. As noted by Yue Wang and Shaofeng Zou in Model-Free Robust Average-Reward Reinforcement Learning, the loss of the contraction property makes it notoriously difficult to guarantee that an algorithm will converge at all.

The Stability Crisis of Undiscounted RL

Without a discount factor, the mathematical landscape of RL changes in three destabilizing ways:

  1. Unbounded Values: In a discounted MDP, the maximum possible value is capped at $R_{max} / (1-\gamma)$. When $\gamma=1$, cumulative values can grow to infinity. Chen-Yu Wei and colleagues highlight that this prevents stable learning in model-free settings Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes.
  2. Non-Uniqueness: The Bellman equation may admit multiple solutions. Baoxiang Wang and Siu On Chan demonstrated in The Gambler's Problem and Beyond that even simple problems can have "pathological" value functions that are fractal or non-smooth, leading agents to converge on incorrect, spurious solutions.
  3. The Deadly Triad: When you combine undiscounted updates with function approximation and off-policy learning, the system often diverges. Shangtong Zhang and Yi Wan note that most stability techniques are designed for the discounted case and fail to bridge this gap Average-Reward Off-Policy Policy Evaluation with Function Approximation.

Mechanism 1: Relative Value Iteration

The most common way to handle unbounded values is to stop caring about the absolute value of a state and focus on its relative value. Relative Value Iteration (RVI) works by subtracting the value of a reference state (or the average reward) from all other states at each step.

This transformation keeps the value estimates bounded. Yue Wang used this approach to develop the first model-free algorithms for robust RL, proving that RVI can converge to optimal worst-case performance even under environmental perturbations Robust Average-Reward Markov Decision Processes.

Mechanism 2: Anchoring and Halpern Iteration

While RVI keeps values bounded, it doesn't necessarily make the Bellman operator a contraction; it often remains merely "non-expansive" (meaning updates don't make things worse, but they don't necessarily get closer to the goal).

To solve this, researchers have turned to Halpern’s anchoring. In Accelerating Value Iteration with Anchoring, Jongmin Lee and Ernest K. Ryu introduce an "anchor" state that pulls the iterates toward a fixed point. By mixing the standard Bellman update with a fixed initial estimate, they achieve an optimal $O(1/k)$ convergence rate even in undiscounted scenarios. This technique was further refined in SAVIA+ to achieve near-optimal sample complexity without needing to know the environment's mixing times.

Mechanism 3: Multi-Step Lookahead

Another way to restore contractivity is to look further into the future. While a single-step Bellman update might not be a contraction when using linear function approximation, a multi-step update often is. Francisco S. Melo and Pedro A. Santos proved in Multi-Bellman operator for convergence of Q-learning with linear function approximation that an $n$-step lookahead eventually becomes a contraction, providing a path to guarantee convergence for Q-learning in complex feature spaces.

Mechanism 4: Discounted Approximation and Clipping

Finally, some researchers bypass the average-reward complexity by approximating it with a carefully tuned discounted MDP. Ki-Hyuk Hong and Ambuj Tewari showed that by using a discount factor very close to 1 and introducing value function clipping, they could achieve optimal regret bounds for linear MDPs without requiring restrictive "ergodicity" assumptions Provably Efficient Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs.

Why it Matters: Beyond the Discount Factor

The shift toward average-reward RL represents a move toward more realistic, long-horizon autonomy. Whether it is solving "Reach-Avoid" problems in robotics Solving Reach- and Stabilize-Avoid Problems Using Discounted Reachability or ensuring safety in asymmetric environments QPRL, the goal is the same: building agents that can operate indefinitely without the mathematical "crutch" of a discount factor. By using tools like anchoring, RVI, and multi-step operators, the field is finally providing the same rigorous guarantees for infinite-horizon tasks that it has long enjoyed for simpler, discounted ones.

Papers in this version

Showing 60 of 124 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_convergence_in_average_reward_reinforcem_be279d15,
  title = {Convergence in Average Reward Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convergence-in-average-reward-reinforcement-learning/rdr_be279d154d8645c981adecbfacb7c734},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_convergence_in_average_reward_reinforcem_be279d15_v1,
  title = {Convergence in Average Reward Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convergence-in-average-reward-reinforcement-learning/rdr_be279d154d8645c981adecbfacb7c734/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}