In reinforcement learning (RL), we often want agents to optimize for long-term, steady-state performance. This is naturally framed as an average-reward objective, where the goal is to maximize the expected reward per step over an infinite horizon. Average-reward Markov Decision Processes (MDPs) are ideal for continuous, non-terminating tasks like network routing, inventory management, or maintaining long-term algorithmic fairness.
However, average-reward problems are notoriously difficult to solve directly. Unlike discounted MDPs, they lack a natural geometric contraction property, meaning standard value iteration algorithms can diverge or become unstable without strict ergodicity assumptions.
To bypass these mathematical hurdles, a powerful and recurring strategy has emerged: reducing average-reward problems to discounted-reward problems. By training an agent with a carefully calibrated discount factor $\gamma$ close to $1$, we can leverage the mature, stable algorithmic ecosystem of discounted RL while guaranteeing that the resulting policy is near-optimal for the long-run average reward.
The Core Intuition: Effective Horizons and Mixing Times
Why should a discounted objective tell us anything about the long-run average reward? The answer lies in the relationship between the effective horizon of a discount factor and the mixing time of the environment.
When we apply a discount factor $\gamma$, we are implicitly forcing the agent to care primarily about a finite window of time. Mathematically, this can be interpreted as a random time horizon following a geometric distribution, as described by Enric Ribera Borrell in Reinforcement Learning with Random Time Horizons. The expected length of this horizon is:
$$\text{Effective Horizon} = \frac{1}{1-\gamma}$$
Now, consider the environment's mixing time ($t_{\text{mix}}$)—the number of steps it takes for the underlying Markov chain to transition from any starting state to its steady-state (stationary) distribution.
If we choose a discount factor $\gamma$ such that the effective horizon is much larger than the mixing time ($\frac{1}{1-\gamma} \gg t_{\text{mix}}$), the agent's transient starting conditions become negligible. The agent spends the vast majority of its "effective lifetime" operating within the steady-state distribution of the MDP. Consequently, maximizing the discounted sum of rewards over this long horizon becomes functionally equivalent to maximizing the average reward earned per step in the steady state.
The Mathematical Bridge: Blackwell Optimality
The foundational justification for this reduction dates back to the principle of Blackwell optimality. In the limit as the discount factor approaches $1$, the scaled discounted value function $(1-\gamma)V_\gamma(s)$ converges uniformly to the average reward value.
Historically, this limit was used analytically to derive long-term properties, as seen in the work of Krishnendu Chatterjee et al. on stochastic games (Stochastic Limit-Average Games are in EXPTIME) and Rahul Meshram et al. on recommendation systems (A Hidden Markov Restless Multi-armed Bandit Model for Playout Recommendation Systems).
A breakthrough by Julien Grand-Clément in Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor proved that this reduction is not merely asymptotic. The author showed that there exists a explicit, non-asymptotic threshold called the Blackwell discount factor. Once $\gamma$ crosses this threshold, any policy that maximizes the discounted reward is exactly optimal for the long-term average reward objective. This provides a rigorous guarantee that we can solve an average-reward problem perfectly using a standard discounted solver, provided $\gamma$ is sufficiently large.
Calibrating $\gamma$ for Sample Efficiency
While setting $\gamma$ arbitrarily close to $1$ guarantees theoretical convergence to the average-reward policy, it introduces a severe practical trade-off: statistical variance. As $\gamma \to 1$, the effective horizon explodes, making value estimates highly sensitive to noise and drastically increasing sample complexity.
To solve this, recent algorithmic work focuses on precisely calibrating $\gamma$ to balance approximation error (from discounting) against statistical error (from finite data).
Mixing-Time Calibration
Yujia Jin et al. quantified this relationship in Towards Tight Bounds on the Sample Complexity of Average-reward MDPs by bounding the value difference between the two objectives as a function of $t_{\text{mix}}$. By setting $(1-\gamma)$ proportional to the target accuracy $\epsilon$ and the environment's mixing time, they showed that discounted algorithms can find near-optimal average-reward policies with predictable sample bounds. Building on this reduction, Shengbo Wang et al. achieved the first provably optimal sample complexity for average-reward MDPs in Optimal Sample Complexity for Average Reward Markov Decision Processes.
Span-Agnostic and Horizon Calibration
In practice, parameters like mixing time or the span ($H$) of the optimal bias function are rarely known upfront. To circumvent this, Matthew Zurek et al. introduced a technique called horizon calibration in Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL. Instead of fixing a single discount factor, the algorithm solves a sequence of discounted problems with dynamically expanding effective horizons, automatically identifying the optimal balance without requiring prior knowledge of the environment's structural parameters.
Generalizing the Reduction
The elegance of the discounted-to-average reduction framework is its versatility. Researchers have successfully exported this mechanism to solve complex variations of reinforcement learning:
- Robust Reinforcement Learning: When an environment's transition dynamics are uncertain, Yue Wang demonstrated in Robust Average-Reward Markov Decision Processes that the uniform convergence of discounted value functions holds even under worst-case model perturbations. This allows distributionally robust average-reward problems to be solved via standard robust discounted tools, a framework expanded to large-scale environments by Zachary Andrew Roch et al. in A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward.
- Constrained MDPs (CMDPs): For safety-critical applications requiring zero constraint violations over an infinite horizon, Honghao Wei et al. utilized a high-discount proxy to deliver the first provably efficient model-free algorithm for average-reward CMDPs (A Provably-Efficient Model-Free Algorithm for Infinite-Horizon Average-Reward Constrained Markov Decision Processes).
- Decentralized Multi-Agent Systems: In game-theoretic settings, Nicolas Gast et al. leveraged "artificial discounting" to adapt discounted multi-agent Q-learning into decentralized algorithms targeting long-term average payoffs (Decentralized model-free reinforcement learning in stochastic games with average-reward objective).
- Logical Specifications: When agents must satisfy complex temporal logic goals infinitely often, researchers use discounted reachability as a proxy. By incrementally shifting the discount factor toward unity, authors like Bach Le 0001 et al. (Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards) and Amin Falah et al. (Reinforcement Learning for Omega-Regular Specifications on Continuous-Time MDP) ensure convergence to policies that satisfy infinite-horizon logical constraints.
By treating the discount factor not as an immutable part of the problem specification, but as a tunable algorithmic hyperparameter, this research direction bridges the gap between what is mathematically tractable (discounted RL) and what we actually want to optimize (long-term average performance).
Key Foundational Work
The Optimal Reward Baseline for Gradient-Based Reinforcement Learning (2001) — contributed 3 concept elements to this direction.
A forecast horizon and a stopping rule for general Markov decision processes (1988) — contributed 2 concept elements to this direction.