mlsanityData to 14 Oct 2026

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

arXiv 2405.15050 ↗First posted 23 May 2024stat.ML cs.LGcited by 7

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

20 of 31 references.

References · 20

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  5. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  6. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  7. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  8. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  10. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  11. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  12. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
8 more
  1. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  2. 2020Regret Bounds for Discounted MDPscited by 19
  3. 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
  4. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  5. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  6. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  7. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  8. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 1; 2026: 3.

7 papers.

  1. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  2. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  3. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processescited by 9
  4. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 2
  5. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  6. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  7. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
  2. 2025A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs
  3. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation
  4. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  5. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs
  6. 2025Non-stationary and Varying-discounting Markov Decision Processes for Reinforcement Learning
  7. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm
  8. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach