In traditional reinforcement learning (RL), algorithms typically optimize for an episodic or discounted reward objective. Under a discounted framework, future rewards are multiplied by a factor $\gamma < 1$, meaning immediate gratification is mathematically prioritized over long-term outcomes. This discount factor serves a vital theoretical purpose: it ensures that the infinite sum of future rewards converges to a finite number, and it turns the standard Bellman operator into a strict contraction mapping with a unique fixed point.
However, many real-world systems—such as power grids, network routing, supply chains, and robotic locomotion—operate continuously without a natural termination or reset. In these persistent environments, discounting can cause an agent to sacrifice steady-state sustainability for short-term gains. If an infrastructure management agent discounts the future, it might neglect long-term maintenance because the catastrophic failures occurring hundreds of steps away are mathematically devalued to zero.
To build agents that optimize for true sustainability, we must shift to the infinite-horizon average-reward criterion. Instead of maximizing a discounted sum, the goal becomes maximizing the steady-state gain per time step:
$$\rho^\pi = \lim_{T \to \infty} \frac{1}{T} \mathbb{E}\left[\sum_{t=1}^T r_t\right]$$
While conceptually straightforward, removing the discount factor ($\gamma = 1$) shatters the mathematical safety nets that standard RL relies on. Value functions can grow indefinitely, and the lack of a contraction mapping makes proving convergence and stability notoriously difficult.
The Core Challenge: Unbounded Values and Relative Bias
If an agent accumulates rewards indefinitely without a discount factor, the absolute value of any state diverges to infinity. To resolve this, average-reward RL shifts its focus from absolute value to relative value.
Instead of asking "How much total reward will I get from this state?", we ask "How much better or worse is this state compared to the long-run average reward $\rho$?" This gives rise to the relative value function (also called the bias function) $h(s)$:
$$h(s) = \mathbb{E}\left[\sum_{t=0}^\infty (r_t - \rho) \right]$$
The average-reward Bellman equation replaces the standard discounted formulation with a pair consisting of the scalar average reward $\rho$ and the relative value function $h(s)$:
$$h(s) + \rho = r(s, a) + \sum_{s'} P(s'|s,a) h(s')$$
Here, $\rho$ acts as a baseline that normalizes the rewards at every step, keeping the relative values $h(s)$ stable and bounded. The primary algorithmic challenge in this field is simultaneously estimating this global baseline $\rho$ and the local advantages $h(s)$ without letting value estimates drift to infinity.
Bridging the Gap via the Vanishing Discount Limit
One of the most intuitive ways to design algorithms for the average-reward setting is to treat it as the limiting case of a discounted problem as $\gamma$ approaches $1$. As the discount factor vanishes, the discounted value function $V_\gamma(s)$ can be asymptotically decomposed into a divergent term and the relative value function: $V_\gamma(s) \approx \frac{\rho}{1-\gamma} + h(s)$.
This mathematical bridge allows researchers to port insights from the well-understood discounted domain into the average-reward domain. For example, in Robust Average-Reward Markov Decision Processes, Yue Wang et al. tackle model uncertainty by demonstrating that robust optimal policies can be systematically found either by taking the limit of discounted rewards or through a direct Relative Value Iteration approach.
Similarly, when extending reinforcement learning to continuous time and space via Stochastic Differential Equations, the vanishing discount limit serves as a critical theoretical anchor. As noted by Hanyang Zhao et al. in Policy Optimization for Continuous Reinforcement Learning, while continuous-time frameworks require a positive discount factor to maintain stable occupation measures, analyzing the limit where the discount factor vanishes is essential for establishing consistent performance bounds in long-run average reward scenarios.
In model-free settings, this approximation can be leveraged directly to achieve optimal efficiency. In Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes, Zihan Zhang et al. introduce UCB-AVG, an algorithm that combines variance-reduction techniques with a discounted reward approximation of average rewards. This allows them to achieve the first computationally efficient model-free regret bounds that scale optimally ($\sqrt{T}$) for general, weakly communicating environments.
Stabilizing Model-Free Learning
When an agent learns purely from environment interactions without a model, tracking the relative value function requires explicit stabilization mechanisms to prevent mathematical divergence.
Adaptive Stepsizes as Local Clocks
In standard Q-learning, a global learning rate is often sufficient. In the average-reward setting, however, the absence of a discount factor means that errors in value estimation can propagate and compound indefinitely.
To address this, Zaiwei Chen in Non-Asymptotic Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes provides a finite-time analysis proving that asynchronous average-reward Q-learning requires adaptive stepsizes. These stepsizes act as localized clocks for each state-action pair, ensuring that updates are scaled dynamically based on visitation frequency. This mechanism provides the necessary mathematical stabilization to guarantee convergence to the correct optimal policy at an $\tilde{\mathcal{O}}(1/k)$ rate.
Policy Gradients and Bounded Regret
For policy-based methods, the challenge shifts to ensuring the smoothness of the objective function when values are unbounded. Most policy gradient theories assume discounted returns, leaving a gap for continuous, non-terminating tasks.
The authors of Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes address this by extending Policy Gradient methods directly to the infinite-horizon average reward setting, establishing formal regret bounds for steady-state performance. Building on this, Swetha Ganesh et al. in Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs introduce novel policy gradient architectures that achieve order-optimal regret by carefully managing the smoothness and gradient bounds of the objective function without diminishing the importance of future rewards.
Managing Mixing Times and Two-Timescale Dynamics
A fundamental property governing average-reward environments is the mixing time ($\tau_{mix}$)—a measure of how quickly the environment transitions from an arbitrary initial state to its steady-state distribution. If an environment mixes slowly, the transient effects of early actions linger for a long time, complicating the estimation of the long-run average reward $\rho$.
Reversing the Timescales
To decouple the estimation of the average reward from policy updates, actor-critic methods traditionally employ a two-timescale stochastic approximation where the critic learns much faster than the actor. This ensures the actor always receives stable value estimates.
However, Prashansa Panda et al. challenge this convention in Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation. By reversing the timescales—making the actor update faster than the critic—they demonstrate that the algorithm can achieve near-optimal sample complexity and train up to twice as fast as standard methods, while maintaining rigorous convergence guarantees in the average-reward setting.
Traditional Actor-Critic:
[Critic (Fast Scale: Bounded Variance)] ---> [Actor (Slow Scale: Policy Update)]
Reversed Two-Timescale (Panda et al.):
[Actor (Fast Scale: Rapid Exploration)] ---> [Critic (Slow Scale: Stable Gain Estimation)]
Eliminating Mixing Time Oracles
Many classical average-reward algorithms require explicit "oracle knowledge" of the environment's mixing time to tune exploration parameters and step sizes. In practice, knowing $\tau_{mix}$ beforehand is impossible for complex environments.
To bypass this restriction, Bhrij Patel et al. in Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles leverage a Multi-level Actor-Critic (MAC) framework. Their approach achieves global convergence with a tighter theoretical dependence on the mixing time ($\mathcal{O}(\sqrt{\tau_{mix}})$) without requiring the agent to know the mixing time oracle in advance, making average-reward optimization viable for practical navigation and control tasks.
Scaling to High Dimensions
To move beyond small, tabular state spaces, average-reward RL must safely integrate with function approximation.
In Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation, Dongruo Zhou et al. introduce UCRL2-VTR. This algorithm represents the relative value function using linear features and achieves nearly minimax optimal regret, proving that agents can explore efficiently in massive state spaces without relying on restrictive uniform mixing assumptions.
For complex, non-linear function approximations like deep neural networks, the theoretical challenges multiply. Jianliang He et al. address this in Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation by introducing a unifying complexity measure called the Average-reward Information Gain (AGEC). They propose the LOOP algorithm, providing a generalized framework that guarantees sample-efficient learning and sublinear regret across a wide variety of high-dimensional, non-terminating environments.
Robustness and Multi-Agent Extensions
As the foundations of average-reward RL have matured, the framework has expanded to handle model uncertainty and multi-agent interactions.
- Robust Optimization: In real-world deployments, the deployment environment often deviates from the training model. To ensure stability under these shifts, Yue Wang et al. develop the first model-free algorithms for robust average-reward RL in Model-Free Robust Average-Reward Reinforcement Learning. By integrating Multi-Level Monte Carlo techniques, they construct unbiased estimators for non-linear robust operators, ensuring the agent's relative value estimates remain stable even when environment dynamics are perturbed.
- Multi-Agent Systems: In decentralized settings, agents must optimize their long-term behavior while accounting for the evolving strategies of others. Nicolas Gast et al. extend the average-reward framework to competitive environments in Decentralized model-free reinforcement learning in stochastic games with average-reward objective. They introduce DONQ-learning, a decentralized, model-free algorithm for two-player zero-sum stochastic games that achieves sublinear expected regret ($T^{2/3}$) while operating within strict memory and computational constraints.