The Vanishing Discount Limit for Average Reward MDPs

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 294 papers122 conceptsfrozen 2026-10-04

In reinforcement learning, we often distinguish between two worlds: episodic tasks, which have a clear beginning and end, and continuing tasks, where an agent operates indefinitely. While episodic RL is well-understood, many real-world systems—like data centers, traffic grids, or autonomous robots—are better modeled as infinite-horizon processes where the goal is to maximize the average reward per time step.

Historically, average-reward Markov Decision Processes (MDPs) have been notoriously difficult to solve directly. However, a powerful consensus has emerged across recent research: we can solve these infinite-horizon problems by treating them as discounted-reward problems where the discount factor $\gamma$ is pushed very close to 1. This "vanishing discount" approach provides a mathematical bridge that allows us to apply mature discounted RL algorithms to the more complex average-reward setting.

The Discounting Proxy as a Temporal Horizon

The core intuition behind this research direction is that discounting acts as a soft truncation mechanism. In a discounted MDP, a reward $t$ steps in the future is weighted by $\gamma^t$. This effectively creates a "planning horizon" of approximately $1/(1-\gamma)$ steps.

As Matthew Zurek and Yudong Chen demonstrate in Span-Based Optimal Sample Complexity for Average Reward MDPs, if we set $\gamma$ high enough such that this effective horizon exceeds the "span" of the environment's bias function, the discounted objective begins to capture the long-run steady-state behavior of the system.

By carefully tuning $\gamma$ as a function of the total time horizon $T$ or the environment's mixing time, researchers like Honghao Wei and Lei Ying have developed algorithms like Triple-QA that achieve sublinear regret and zero constraint violations in average-reward settings A Provably-Efficient Model-Free Algorithm for Infinite-Horizon Average-Reward Constrained Markov Decision Processes.

Bridging the Gap with Mixing Time

Why does a discounted proxy work? The answer lies in how quickly an environment "forgets" its starting state and reaches a stationary distribution, a property known as mixing time ($t_{mix}$).

Yujia Jin and Aaron Sidford established a formal quantitative relationship between these two objectives in Towards Tight Bounds on the Sample Complexity of Average-reward MDPs. They showed that the value difference between an average-reward policy and a discounted-reward policy can be bounded by a function of the mixing time. If the discount factor is calibrated to the system's mixing time and the desired precision, the optimal policy for the discounted model becomes near-optimal for the original average-reward objective.

This reduction is not just a theoretical convenience; it enables the first "minimax optimal" sample complexity bounds. Shengbo Wang and Jose Blanchet used this approach to close a long-standing gap in RL theory, proving exactly how many samples are needed to learn an optimal average-reward policy Optimal Sample Complexity for Average Reward Markov Decision Processes.

Robustness and Multi-Agent Games

The vanishing discount limit is particularly useful when dealing with uncertainty or competition. In Robust MDPs, where the transition dynamics are not perfectly known, proving the existence of an optimal average-reward strategy is mathematically daunting.

Yue Wang and Shaofeng Zou showed that the value function for discounted rewards converges uniformly to the average reward as $\gamma \to 1$ Robust Average-Reward Markov Decision Processes. This uniform convergence allows researchers to exchange the limit and minimization operations, making it possible to find robust policies for long-term performance by solving a sequence of more tractable discounted problems.

This logic extends to multi-agent settings. Zachary Andrew Roch and Yue Wang applied this to Markov Games, proving that a stationary Nash Equilibrium for average rewards can be found by analyzing the limit of discounted-reward games Distributionally Robust Markov Games with Average Reward.

Unifying Episodic and Continuing RL

Perhaps the most elegant result of this research direction is the unification of episodic and average-reward RL. Priyank Agrawal and Shipra Agrawal argue that episodic RL is actually a special case of the average-reward setting where the terminal state acts as a frequent, recurring anchor Optimistic Q-learning for average reward and episodic reinforcement learning.

By viewing the discount factor as a dynamic horizon that expands over time, algorithms can learn to optimize for long-term steady-state performance without needing to know hidden environment parameters like mixing time upfront. As Ying Jin and Jose H. Blanchet demonstrate, this "feasible" approach allows agents to transition smoothly from short-term exploration to long-term average-reward optimization Feasible Q-Learning for Average Reward Reinforcement Learning.

Papers in this version

Showing 60 of 94 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 90 papers
  2. Version 1 · 2026-10-04 · 94 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_discounted_to_average_reward_reduction_fa4a1605,
  title = {discounted-to-average reward reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discounted-to-average-reward-reduction/rdr_fa4a160515724ac5a18c612aaa3c38d0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_vanishing_discount_limit_for_average_fa4a1605_v1,
  title = {The Vanishing Discount Limit for Average Reward MDPs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-vanishing-discount-limit-for-average-reward-mdps/rdr_fa4a160515724ac5a18c612aaa3c38d0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}