# Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning

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

## Key facts

- Cited by 96 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2020.

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

- [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)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (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)
- [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)
- [Robust Multi-Agent Reinforcement Learning with State Uncertainty](https://mlsanity.com/paper/2307.16212/) (2023)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (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)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path](https://mlsanity.com/paper/2208.11639/) (2022)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [A Survey on Reinforcement Learning in Aviation Applications](https://mlsanity.com/paper/2211.02147/) (2022)
- [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)
- [A Discrete-Time Switching System Analysis of Q-learning](https://mlsanity.com/paper/2102.08583/) (2021)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [Reward Centering](https://mlsanity.com/paper/2405.09999/) (2024)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications](https://mlsanity.com/paper/2312.02828/) (2023)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)

## Abstract (arXiv)

We consider a general asynchronous Stochastic Approximation (SA) scheme featuring a weighted infinity-norm contractive operator, and prove a bound on its finite-time convergence rate on a single trajectory. Additionally, we specialize the result to asynchronous Q-learning. The resulting bound matches the sharpest available bound for synchronous Q-learning, and improves over previous known bounds for asynchronous Q-learning.