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 $\widetilde\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 $\widetilde\Theta(H(1-\gamma)^{-2}\epsilon^{-2})$, where $H=|v^*|_{\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 $\widetilde\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.