Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis

Abstract

Q-learning, which seeks to learn the optimal Q-function of a Markov decision process (MDP) in a model-free fashion, lies at the heart of reinforcement learning. When it comes to the synchronous setting (such that independent samples for all state-action pairs are drawn from a generative model in each iteration), substantial progress has been made towards understanding the sample efficiency of Q-learning. Consider a $\gamma$-discounted infinite-horizon MDP with state space $\mathcal{S}$ and action space $\mathcal{A}$: to yield an entrywise $\epsilon$-approximation of the optimal Q-function, state-of-the-art theory for Q-learning requires a sample size exceeding the order of $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma {)}^5{\epsilon }^2}$, which fails to match existing minimax lower bounds. This gives rise to natural questions: what is the sharp sample complexity of Q-learning? Is Q-learning provably sub-optimal? This paper addresses these questions for the synchronous setting: (1) when $|\mathcal{A}|=1$ (so that Q-learning reduces to TD learning), we prove that the sample complexity of TD learning is minimax optimal and scales as $\frac{|\mathcal{S}|}{(1-\gamma {)}^3{\epsilon }^2}$ (up to log factor); (2) when $|\mathcal{A}|\ge 2$, we settle the sample complexity of Q-learning to be on the order of $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma {)}^4{\epsilon }^2}$ (up to log factor). Our theory unveils the strict sub-optimality of Q-learning when $|\mathcal{A}|\ge 2$, and rigorizes the negative impact of over-estimation in Q-learning. Finally, we extend our analysis to accommodate asynchronous Q-learning (i.e., the case with Markovian samples), sharpening the horizon dependency of its sample complexity to be $\frac{1}{(1-\gamma {)}^4}$.

accepted to Operations Research

References in corpus (12)

• Finite-Time Analysis of Distributed TD(0) with Linear Function Approximation for Multi-Agent Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
• Finite-Time Analysis for Double Q-learning
• Reanalysis of Variance Reduced Temporal Difference Learning
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• The Mean-Squared Error of Double Q-Learning
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning

Cited by in corpus (5)

• Joint Mobility Control and MEC Offloading for Hybrid Satellite-Terrestrial-Network-Enabled Robots
• Online Robust Reinforcement Learning with Model Uncertainty
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Navigating to the Best Policy in Markov Decision Processes
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs