Optimal Sample Complexity of Stable Discounted Markov Decision Processes

arXiv:2302.07477v4 Announce Type: replace 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 widetildeTheta((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 widetildeTheta(H(1-gamma)^{-2}epsilon^{-2}), where H=|v^*|{span} is the span of the optimal value function. Moreover, assuming a uniform mixing time upper bound t{mix} over all policies, the optimal Q-function can be estimated up to a constant shift with sample complexity widetildeThetaleft(t_{mix}^3epsilon^{-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.

Source: arXiv cs.LG | 2026-09-22