mlsanityData to 7 Oct 2026

A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants

arXiv 2102.01567 ↗First posted 2 Feb 2021cs.LG math.OC stat.MLcited by 57

Not on the map. Why?

Abstract (arXiv)

This paper develops an unified framework to study finite-sample convergence guarantees of a large class of value-based asynchronous reinforcement learning (RL) algorithms. We do this by first reformulating the RL algorithms as textitMarkovian Stochastic Approximation (SA) algorithms to solve fixed-point equations. We then develop a Lyapunov analysis and derive mean-square error bounds on the convergence of the Markovian SA. Based on this result, we establish finite-sample mean-square convergence bounds for asynchronous RL algorithms such as Q-learning, n-step TD, TD(λ), and off-policy TD algorithms including V-trace. As a by-product, by analyzing the convergence bounds of n-step TD and TD(λ), we provide theoretical insights into the bias-variance trade-off, i.e., efficiency of bootstrapping in RL. This was first posed as an open problem in (Sutton, 1999).

Key facts. Cited by 57 papers in the map (data through 7 Oct 2026). Builds on 18 of its 64 references that are in the map. First posted on arXiv 2 Feb 2021.

Builds on

18 of 64 references.

References · 18

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 866
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Safe and Efficient Off-Policy Reinforcement Learningcited by 260
  5. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  6. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  7. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  8. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  9. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  10. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  11. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  12. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
6 more
  1. 2016Q(λ) with Off-Policy Correctionscited by 48
  2. 2019A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithmscited by 14
  3. 2020Finite-Time Analysis for Double Q-learningcited by 12
  4. 2014Rate of Convergence and Error Bounds for LSTD(λ)cited by 8
  5. 2020Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximationcited by 3
  6. 2018Optimal Matrix Momentum Stochastic Approximation and Applications to Q-learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 10; 2023: 8; 2024: 11; 2025: 6; 2026: 8.

57 papers.

Sort:

By area:

  1. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  2. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  3. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  4. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  5. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  6. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  7. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  8. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  9. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 28
  10. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  11. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  12. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
38 more
  1. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  2. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  3. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  4. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  5. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  6. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  7. 2021A Discrete-Time Switching System Analysis of Q-learningcited by 16
  8. 2022On the Convergence of SARSA with Linear Function Approximationcited by 15
  9. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  10. 2023Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applicationscited by 15
  11. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 14
  12. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  13. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  14. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
  15. 2024Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 10
  16. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  17. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
  18. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  19. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 5
  20. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  21. 2022Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic Viewcited by 4
  22. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3
  23. 2023Finite-Time Analysis of Minimax Q-Learning for Two-Player Zero-Sum Markov Games: Switching System Approachcited by 3
  24. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 3
  25. 2022Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learningcited by 2
  26. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  27. 2024Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Gamescited by 2
  28. 2024Markov Chain Variance Estimation: A Stochastic Approximation Approachcited by 2
  29. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2
  30. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  31. 2025Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learningcited by 2
  32. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  33. 2026A Switching System Theory of Q-Learning with Linear Function Approximationcited by 2
  34. 2024A finite time analysis of distributed Q-learningcited by 1
  35. 2024Is Thompson Sampling Susceptible to Algorithmic Collusion?cited by 1
  36. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  37. 2026Gaussian Approximation for Multivariate Martingale Sums from Uniformly Ergodic Markov Chainscited by 1
  38. 2021Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learningcited by 0

50 most cited of 57 All 57 (JSON)