Optimal Sample Complexity of Stable Discounted Markov Decision Processes

Abstract

We study the optimal sample complexity of tabular reinforcement learning for infinite-horizon discounted Markov decision processes. The unrestricted minimax sample complexity is known to scale as $\tilde{\Theta }((1-\gamma {)}^{-3}{\epsilon }^{-2})$, where $\gamma$ denotes the discount factor and $\epsilon$ is the solution-error tolerance. However, this worst-case rate does not account for stability structures that commonly arise in operational environments. Using the variance-reduced Q-learning framework, we show that, without imposing any additional stability assumptions, both sup-norm Q-function estimation and policy learning have leading sample-complexity dependence $\tilde{\Theta }(H(1-\gamma {)}^{-2}{\epsilon }^{-2})$, where $H=|v^{\ast }{|}_{\mathrm{span}}$ is the span of the optimal value function. Moreover, assuming a uniform mixing time upper bound $t_{\mathrm{mix}}$ over all policies, the optimal Q-function can be estimated up to a constant shift with sample complexity $\tilde{\Theta }\left(t_{\mathrm{mix}}^3{\epsilon }^{-2}\right)$, independent of $(1-\gamma {)}^{-1}$. Matching lower bounds establish the sharpness of these leading dependencies and reveal a separation between estimation and control: although the Q-function can be learned up to an additive constant at a horizon-free rate, policy learning generally retains its $(1-\gamma {)}^{-2}$ dependence.