Achieving Tractable Minimax Optimal Regret in Average Reward MDPs
<|reference_start|>Achieving Tractable Minimax Optimal Regret in Average Reward MDPs: 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 $\widetilde{\mathrm{O}}(\sqrt{\mathrm{sp}(h^*) S A T})$, 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, 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.<|reference_end|>
@article{boone2024achieving,
    title={Achieving Tractable Minimax Optimal Regret in Average Reward MDPs},
    author={Victor Boone, Zihan Zhang},
    journal={arXiv preprint arXiv:2406.01234},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.01234},
    primaryClass={cs.LG cs.SY eess.SY math.OC stat.ML}
}