mlsanityData to 14 Oct 2026

Achieving Tractable Minimax Optimal Regret in Average Reward MDPs

arXiv 2406.01234 ↗First posted 3 Jun 2024cs.LG cs.SY eess.SYcited by 15

Not on the map. Why?

Abstract (arXiv)

In recent years, significant attention has been directed towards learning average-reward Markov Decision Processes (MDPs). However, existing algorithms either suffer from sub-optimal regret guarantees or computational inefficiencies. In this paper, we present the first tractable algorithm with minimax optimal regret of widetildeO(√sp(h^*) S A T), where sp(h^*) is the span of the optimal bias function h^*, S × A is the size of the state-action space and T the number of learning steps. Remarkably, our algorithm does not require prior information on sp(h^*). Our algorithm relies on a novel subroutine, Projected Mitigated Extended Value Iteration (PMEVI), to compute bias-constrained optimal policies efficiently. This subroutine can be applied to various previous algorithms to improve regret bounds.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 12 of its 28 references that are in the map. First posted on arXiv 3 Jun 2024.

Builds on

12 of 28 references.

References · 12

  1. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  2. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  3. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  4. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  5. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  6. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  7. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
  8. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  9. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  10. 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 25
  11. 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
  12. 2017Posterior Sampling for Large Scale Reinforcement Learningcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 3; 2026: 8.

15 papers.

Sort:

By area:

  1. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  2. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 5
  3. 2026Policy Gradient Algorithms in Average-Reward Multichain MDPscited by 3
  4. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  5. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2
  6. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 2
  7. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  8. 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1
  9. 2024Provably Efficient Exploration in Reward Machines with Low Regretcited by 1
  10. 2025Q-learning with Posterior Samplingcited by 1
  11. 2026Fairness of Explanations in Artificial Intelligence (AI): A Unifying Framework, Axioms, and Future Direction toward Responsible AIcited by 1
  12. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholdingcited by 0
3 more
  1. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0
  2. 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learningcited by 0
  3. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0