Wang, S., Blanchet, J., & Glynn, P. (2023). Optimal Sample Complexity of Reinforcement Learning for Mixing Discounted Markov Decision Processes. ArXiv. /abs/2302.07477

View Publication

Abstract

We consider the optimal sample complexity theory of tabular reinforcement learning (RL) for maximizing the infinite horizon discounted reward in a Markov decision process (MDP). Optimal worst-case complexity results have been developed for tabular RL problems in this setting, leading to a sample complexity dependence on and of the form , where denotes the discount factor and is the solution error tolerance. However, in many applications of interest, the optimal policy (or all policies) induces mixing. We establish that in such settings, the optimal sample complexity dependence is , where is the total variation mixing time. Our analysis is grounded in regeneration-type ideas, which we believe are of independent interest, as they can be used to study RL problems for general state space MDPs.

Authors
Shengbo Wang, Jose Blanchet, Peter Glynn
Publication date
2023/2/15
Journal
arXiv preprint arXiv:2302.07477