# Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction

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

## Key facts

- Cited by 95 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2020.

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

- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges](https://mlsanity.com/paper/2102.01168/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [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)
- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [On the Importance of Exploration for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2306.05483/) (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-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2102.09318/) (2021)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)

## Abstract (arXiv)

Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a γ-discounted MDP with state space S and action space A, we demonstrate that the ℓ∞-based sample complexity of classical asynchronous Q-learning --- namely, the number of samples needed to yield an entrywise varepsilon-accurate estimate of the Q-function --- is at most on the order of frac1μmin(1-γ)5varepsilon2+ fractmixμmin(1-γ) up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here, tmix and μmin denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the sample complexity in the synchronous case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the cost taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result citequ2020finite by a factor of at least |S||A| for all scenarios, and by a factor of at least tmix|S||A| for any sufficiently small accuracy level varepsilon. Further, we demonstrate that the scaling on the effective horizon frac11-γ can be improved by means of variance reduction.