@inproceedings{
boone2024achieving,
title={Achieving Tractable Minimax Optimal Regret in Average Reward {MDP}s},
author={Victor Boone and Zihan Zhang},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=SM9IWrHz4e}
}
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 $\mathrm{O}\left(\sqrt{\mathrm{sp}(h^*) S A T \log(SAT)}\right)$ where $\mathrm{sp}(h^*)$ is the span of the optimal bias function $h^*$, $S\times 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 $\mathrm{sp}(h^*)$. 

Our algorithm relies on a novel subroutine, **P**rojected **M**itigated **E**xtended **V**alue **I**teration (`PMEVI`), to compute bias-constrained optimal policies efficiently. 
This subroutine can be applied to various previous algorithms to obtain improved regret bounds.
Achieving Tractable Minimax Optimal Regret in Average Reward MDPs
Victor Boone Zihan Zhang