# Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs

arXiv: https://arxiv.org/abs/2405.15050 · HTML: https://mlsanity.com/paper/2405.15050/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 23 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 20 of 20)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Regret Bounds for Reinforcement Learning via Markov Chain Concentration](https://mlsanity.com/paper/1808.01813/) (2018)
- [Regret Bounds for Discounted MDPs](https://mlsanity.com/paper/2002.05138/) (2020)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Optimal Sample Complexity for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2310.08833/) (2023)
- [Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time](https://mlsanity.com/paper/2305.15546/) (2023)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [Span-Based Optimal Sample Complexity for Average Reward MDPs](https://mlsanity.com/paper/2311.13469/) (2023)

## Built on by (most cited first, 7 of 7)

- [Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning](https://mlsanity.com/paper/2502.13900/) (2025)
- [Optimistic Q-learning for average reward and episodic reinforcement learning](https://mlsanity.com/paper/2407.13743/) (2024)
- [On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes](https://mlsanity.com/paper/2408.16262/) (2024)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span](https://mlsanity.com/paper/2410.14992/) (2024)
- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)

## Abstract (arXiv)

We study the problem of infinite-horizon average-reward reinforcement learning with linear Markov decision processes (MDPs). The associated Bellman operator of the problem not being a contraction makes the algorithm design challenging. Previous approaches either suffer from computational inefficiency or require strong assumptions on dynamics, such as ergodicity, for achieving a regret bound of widetildeO(√T). In this paper, we propose the first algorithm that achieves widetildeO(√T) regret with computational complexity polynomial in the problem parameters, without making strong assumptions on dynamics. Our approach approximates the average-reward setting by a discounted MDP with a carefully chosen discounting factor, and then applies an optimistic value iteration. We propose an algorithmic structure that plans for a nonstationary policy through optimistic value iteration and follows that policy until a specified information metric in the collected data doubles. Additionally, we introduce a value function clipping procedure for limiting the span of the value function for sample efficiency.