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 $\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.

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.

Machine Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML)

arXiv:2302.07477 [cs.LG]

(or arXiv:2302.07477v4 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2302.07477 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Optimal Sample Complexity of Stable Discounted Markov Decision Processes

Subiecte conexe