mlsanityData to 7 Oct 2026

Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes

arXiv 2306.16394 ↗First posted 28 Jun 2023cs.LGcited by 28

Not on the map. Why?

Abstract (arXiv)

We develop several provably efficient model-free reinforcement learning (RL) algorithms for infinite-horizon average-reward Markov Decision Processes (MDPs). We consider both online setting and the setting with access to a simulator. In the online setting, we propose model-free RL algorithms based on reference-advantage decomposition. Our algorithm achieves widetildeO(S5A2sp(h^*)√T) regret after T steps, where S× A is the size of state-action space, and sp(h^*) the span of the optimal bias function. Our results are the first to achieve optimal dependence in T for weakly communicating MDPs. In the simulator setting, we propose a model-free RL algorithm that finds an ε-optimal policy using widetildeO left(fracSAsp2(h^*)ε2+fracS2Asp(h^*)ε right) samples, whereas the minimax lower bound is Omegaleft(fracSAsp(h^*)ε2right). Our results are based on two new techniques that are unique in the average-reward setting: 1) better discounted approximation by value-difference estimation; 2) efficient construction of confidence region for the optimal bias function with space complexity O(SA).

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). Builds on 21 of its 36 references that are in the map. First posted on arXiv 28 Jun 2023.

Builds on

21 of 36 references.

References · 21

  1. 2018Is Q-learning Provably Efficient?cited by 485
  2. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  5. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  6. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  7. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  8. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  9. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  10. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  11. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  12. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
9 more
  1. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  2. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  3. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
  4. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  5. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  6. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  7. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  8. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  9. 2019Exploration-Enhanced POLITEXcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 10; 2025: 9; 2026: 7.

28 papers.

Sort:

By area:

  1. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  2. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  3. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  4. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  5. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  6. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  7. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  8. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  9. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  10. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  11. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5
  12. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
16 more
  1. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 3
  2. 2025Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gaincited by 3
  3. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 3
  4. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
  5. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 2
  6. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  7. 2025Q-learning with Posterior Samplingcited by 1
  8. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  9. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 1
  10. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
  11. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  12. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  13. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholdingcited by 0
  14. 2026Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Valuescited by 0
  15. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  16. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0