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

DOI10.1287/OPRE.2023.2450MaRDI QIDQ6198738zbMATH OpenFDO

Authors Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, Yuejie Chi

Publication date 20 March 2024

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.06548

zbMATH Keywords

effective horizonlower boundminimax optimalityoverestimationQ-learningsample complexitytemporal difference learning

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

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 $mathcalS$ and action space $mathcalA$: to yield an entrywise $varepsilon$-approximation of the optimal Q-function, state-of-the-art theory for Q-learning requires a sample size exceeding the order of $frac|mathcalS||mathcalA|(1-gamma{)}^{5}varepsilo{n}^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 $|mathcalA|=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|mathcalS|(1-gamma{)}^{3}varepsilo{n}^2$ (up to log factor); (2) when $|mathcalA|geq2$, we settle the sample complexity of Q-learning to be on the order of $frac|mathcalS||mathcalA|(1-gamma{)}^{4}varepsilo{n}^2$ (up to log factor). Our theory unveils the strict sub-optimality of Q-learning when $|mathcalA|geq2$, 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 $frac1(1-gamma{)}^4$.

Recommendations

• Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model
• \({\mathcal Q}\)-learning
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Empirical Q-value iteration
• Reinforcement learning in finite MDPs: PAC analysis

Cited in

(6)

• Target Network and Truncation Overcome the Deadly Triad in \(\boldsymbol{Q}\)-Learning
• Settling the sample complexity of model-based offline reinforcement learning
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Settling the sample complexity of online reinforcement learning
• Concentration of contractive stochastic approximation: additive and multiplicative noise
• Off-Policy Evaluation in Doubly Inhomogeneous Environments

This page was built for publication: Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198738)