Optimal Sample Complexity of Reinforcement Learning for Mixing Discounted Markov Decision Processes
This provides a tighter theoretical bound for RL practitioners working with mixing MDPs, though it is incremental as it refines existing complexity results under specific conditions.
The paper tackles the problem of optimal sample complexity in tabular reinforcement learning for discounted Markov decision processes, showing that when policies induce mixing, the complexity is Ψ(t_mix(1-γ)^{-2}ε^{-2}), improving upon the previous Ψ((1-γ)^{-3}ε^{-2}) by reducing the dependence on the discount factor.
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 $\tilde Θ((1-γ)^{-3}ε^{-2})$, 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 $\tilde Θ(t_{\text{mix}}(1-γ)^{-2}ε^{-2})$, where $t_{\text{mix}}$ 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.