Most reinforcement learning (RL) research operates in two comfortable settings: the episodic world, where a game of chess eventually ends and resets, or the discounted world, where a mathematical "discount factor" ($\gamma < 1$) makes the immediate future matter more than the distant one.
However, many real-world systems—like data centers, power grids, or autonomous supply chains—don't have a "reset" button and must operate indefinitely. In these "continuing" tasks, the goal is to maximize the average reward per time step over an infinite horizon. While intuitively simpler, the average-reward setting is mathematically much more stubborn. Recent work has focused on making these algorithms robust to model errors and safe under constraints, specifically by relaxing the restrictive assumptions that have historically limited their use.
The Reachability Bottleneck
The biggest hurdle in average-reward RL is how the agent moves through the environment. Early theoretical proofs relied on ergodicity or the unichain assumption: the idea that every state is reachable from every other state under any policy. In this "perfect bubble," the agent can never get permanently stuck.
But real-world environments have "sink states" (like a broken robot) or "dead ends" (irreversible failures). As Akhil Agnihotri and Rahul Jain point out in ACPO: A Policy Optimization Algorithm for Average MDPs with Constraints, these assumptions fail when an agent encounters irreversible states.
Researchers are now moving toward the weakly communicating assumption. In a communicating MDP, any state can be reached from any other state by some policy, but not necessarily every policy. This is a significant relaxation that allows for more realistic environments where an agent must learn to avoid regions of the state space from which it cannot return. Jongmin Lee and Ernest K. Ryu demonstrated in Finite-Time Bounds for Average-Reward Fitted Q-Iteration that finite-time guarantees can still be established in these more complex, weakly communicating structures.
Robustness Against the Unknown
In the real world, the mathematical model of the environment is often an approximation. If an agent optimizes for a specific model that turns out to be slightly wrong, its long-term average performance can collapse. This is the domain of Robust MDPs, which optimize for the "worst-case scenario" within a set of possible environments.
Yue Wang, Alvaro Velasquez, and Shaofeng Zou have pioneered model-free algorithms for this setting. In Model-Free Robust Average-Reward Reinforcement Learning, they combine Relative Value Iteration (RVI)—a technique that looks at the difference in value between states rather than absolute values—with multi-level Monte-Carlo sampling. This allows the agent to converge to a policy that remains stable even if the environment's transition dynamics shift (e.g., due to sensor noise or wear and tear).
To provide even stronger guarantees, Zachary Andrew Roch and colleagues introduced Robust Halpern Iteration (RHI) in A Finite-Sample Analysis of Distributionally Robust Average-Reward Reinforcement Learning. This algorithm provides the first finite-sample complexity guarantees for robust average-reward RL without requiring prior knowledge of the environment's mixing time, effectively bridging the gap between theoretical "sim-to-real" robustness and practical deployment.
Safety and Long-Term Constraints
For many systems, maximizing reward isn't enough; they must also stay within safety limits (e.g., a drone must not exceed a certain battery temperature). In average-reward settings, these constraints must hold over the long run.
Traditional methods often struggle because they only look at "cost-to-come." Harsh Satija and Joelle Pineau addressed this in Constrained Markov Decision Processes via Backward Value Functions by introducing Backward Value Functions (BVF). By estimating the "cost-so-far" alongside the "cost-to-come," they transform global trajectory-level constraints into local, state-wise constraints that can be solved efficiently during training.
Furthermore, Rahul Jain and Haipeng Luo achieved a major breakthrough in Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints, proving that it is possible to achieve near-optimal regret and constant constraint violation even in the challenging class of weakly communicating MDPs.
Bridging the Gap with the Blackwell Discount Factor
If average-reward RL is so difficult, why not just use a very high discount factor (e.g., $\gamma = 0.9999$)? While this is a common heuristic, it often leads to numerical instability.
Julien Grand-Clément and Marek Petrik provided a rigorous foundation for this intuition in Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor. They identified a specific threshold—the Blackwell discount factor—beyond which a policy that is optimal for a discounted MDP is guaranteed to be optimal for the average-reward setting. This allows researchers to use the well-developed machinery of discounted RL to solve long-term average-reward problems with formal guarantees.
Similarly, Ki-Hyuk Hong and Ambuj Tewari used a carefully tuned discounted-reward approximation in Provably Efficient Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs to bypass the need for restrictive ergodicity assumptions, achieving optimal regret bounds in high-dimensional linear environments.