# Achieving Tractable Minimax Optimal Regret in Average Reward MDPs

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

## 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 (most cited first, 12 of 12)

- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [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)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)
- [Posterior Sampling for Large Scale Reinforcement Learning](https://mlsanity.com/paper/1711.07979/) (2017)

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

- [Optimistic Q-learning for average reward and episodic reinforcement learning](https://mlsanity.com/paper/2407.13743/) (2024)
- [Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL](https://mlsanity.com/paper/2502.11238/) (2025)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Finite-Time Bounds for Average-Reward Fitted Q-Iteration](https://mlsanity.com/paper/2510.17391/) (2025)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span](https://mlsanity.com/paper/2410.14992/) (2024)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [Provably Efficient Exploration in Reward Machines with Low Regret](https://mlsanity.com/paper/2412.19194/) (2024)
- [Q-learning with Posterior Sampling](https://mlsanity.com/paper/2506.00917/) (2025)
- [Fairness of Explanations in Artificial Intelligence (AI): A Unifying Framework, Axioms, and Future Direction toward Responsible AI](https://mlsanity.com/paper/2605.09852/) (2026)
- [Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding](https://mlsanity.com/paper/2602.00781/) (2026)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)
- [Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2608.07725/) (2026)
- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)

## 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.