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

arXiv: https://arxiv.org/abs/2102.06548 · HTML: https://mlsanity.com/paper/2102.06548/

## Key facts

- Cited by 92 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 63 references that are in the map.
- First posted on arXiv 12 Feb 2021.

## Builds on (most cited first, 28 of 28)

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [Reanalysis of Variance Reduced Temporal Difference Learning](https://mlsanity.com/paper/2001.01898/) (2020)
- [Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes](https://mlsanity.com/paper/2002.00874/) (2020)
- [Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning](https://mlsanity.com/paper/2002.10301/) (2020)
- [Finite-Time Analysis for Double Q-learning](https://mlsanity.com/paper/2009.14257/) (2020)
- [The Mean-Squared Error of Double Q-Learning](https://mlsanity.com/paper/2007.05034/) (2020)
- [Stochastic Primal-Dual Q-Learning](https://mlsanity.com/paper/1810.08298/) (2018)
- [Momentum Q-learning with Finite-Sample Convergence Guarantee](https://mlsanity.com/paper/2007.15418/) (2020)

## Built on by (most cited first, 30 of 92)

- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Sample Complexity of Variance-reduced Distributionally Robust Q-learning](https://mlsanity.com/paper/2305.18420/) (2023)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning](https://mlsanity.com/paper/2106.14352/) (2021)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [High-probability sample complexities for policy evaluation with linear function approximation](https://mlsanity.com/paper/2305.19001/) (2023)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Optimal Sample Complexity for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2310.08833/) (2023)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/2205.14211/) (2022)
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025)
- [Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices](https://mlsanity.com/paper/2402.05876/) (2024)
- [Statistically Efficient Advantage Learning for Offline Reinforcement Learning in Infinite Horizons](https://mlsanity.com/paper/2202.13163/) (2022)
- [A Concentration Bound for TD(0) with Function Approximation](https://mlsanity.com/paper/2312.10424/) (2023)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)

## Abstract (arXiv)

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 γ-discounted infinite-horizon MDP with state space S and action space A: 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|S||A|(1-γ)5varepsilon2, 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 |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|S|(1-γ)3varepsilon2 (up to log factor); (2) when |A|≥ 2, we settle the sample complexity of Q-learning to be on the order of frac|S||A|(1-γ)4varepsilon2 (up to log factor). Our theory unveils the strict sub-optimality of Q-learning when |A|≥ 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 frac1(1-γ)4.