Optimal Regret for Policy Optimization in Average Reward MDPs Without Mixing

William Powell, Jeongyeol Kwon, Qiaomin Xie, Hanbaek Lyu; 7, 2026.

Presented at the Reinforcement Learning Conference (RLC), Montréal, Quebec, Canada, August 15–17, 2026.

Abstract

We study model-free policy optimization algorithms for regret minimization in infinite horizon average reward Markov decision processes. Optimal regret bounds in this setting are only available under the restrictive uniform mixing assumption which states that, regardless of the policy one uses, the underlying Markov chain converges to its stationary behavior at a constant exponential rate. In this paper, we challenge this strong assumption and present the first provably efficient policy optimization method for infinite horizon average reward Markov decision processes without any mixing time dependence. Our algorithm achieves the optimal $\tilde{O}(\sqrt{T})$ regret assuming only a data coverage condition and the existence of a recurrent state that is re-visited within a finite expected time under all policies. Our results are obtained through a novel randomized episode length which allows us to leverage the Markov chain's renewal property.

[abs][pdf]

BibTeX

@article{powell2026optimal,
    title={Optimal Regret for Policy Optimization in Average Reward MDPs Without Mixing},
    author={William Powell and Jeongyeol Kwon and Qiaomin Xie and Hanbaek Lyu},
    journal={Reinforcement Learning Journal},
    volume={7},
    pages={},
    year={2026}
}