mlsanityData to 13 Oct 2026

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

arXiv 2002.00260 ↗First posted 1 Feb 2020math.OC cs.LGcited by 94

Not on the map. Why?

Cited by 35 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

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.

Key facts. Cited by 94 papers in the map (data through 13 Oct 2026). First posted on arXiv 1 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2020: 1; 2021: 17; 2022: 12; 2023: 14; 2024: 18; 2025: 13; 2026: 19.

94 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 363
  2. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  3. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 90
  4. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  5. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  6. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  7. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  8. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  9. 2021Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challengescited by 40
  10. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 35
  11. 2023Robust Multi-Agent Reinforcement Learning with State Uncertaintycited by 35
  12. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
38 more
  1. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 30
  2. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  3. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  4. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  5. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  6. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  7. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  8. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  9. 2022A Survey on Reinforcement Learning in Aviation Applicationscited by 19
  10. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  11. 2021A Discrete-Time Switching System Analysis of Q-learningcited by 16
  12. 2022Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Pathcited by 16
  13. 2024Reward Centeringcited by 16
  14. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 15
  15. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  16. 2023Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applicationscited by 15
  17. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 15
  18. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  19. 2023Off-Policy RL Algorithms Can be Sample-Efficient for Continuous Control via Sample Multiple Reusecited by 12
  20. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  21. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  22. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  23. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  24. 2024Computing the Bias of Constant-step Stochastic Approximation with Markovian Noisecited by 9
  25. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 9
  26. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  27. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  28. 2022Constrained Stochastic Nonconvex Optimization with State-dependent Markov Datacited by 6
  29. 2023Statistical Inference with Stochastic Gradient Methods under φ-mixing Datacited by 6
  30. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 6
  31. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 6
  32. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 6
  33. 2021Convergence Results For Q-Learning With Experience Replaycited by 5
  34. 2022Data Sampling Affects the Complexity of Online SGD over Dependent Datacited by 5
  35. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  36. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
  37. 2022Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic Viewcited by 4
  38. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4

50 most cited of 94 All 94 (JSON)