mlsanityData to 14 Oct 2026

Central Limit Theorems for Asynchronous Averaged Q-Learning

arXiv 2509.18964 ↗First posted 23 Sep 2025cs.LG math.OC stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

This paper establishes central limit theorems for Polyak-Ruppert averaged Q-learning under asynchronous updates. We prove a non-asymptotic central limit theorem, where the convergence rate in Wasserstein distance explicitly reflects the dependence on the number of iterations, state-action space size, the discount factor, and the quality of exploration. In addition, we derive a functional central limit theorem, showing that the partial-sum process converges weakly to a Brownian motion.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 28 of its 43 references that are in the map. First posted on arXiv 23 Sep 2025.

Builds on

28 of 43 references.

References · 28

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  3. 2018Sim-to-Real: Learning Agile Locomotion For Quadruped Robotscited by 319
  4. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  5. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  6. 2019TossingBot: Learning to Throw Arbitrary Objects with Residual Physicscited by 137
  7. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  8. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  9. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  10. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  11. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  12. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
16 more
  1. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  2. 2019Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLTcited by 30
  3. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  4. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19
  5. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  6. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  7. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  8. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  9. 2025Statistical inference for Linear Stochastic Approximation with Markovian Noisecited by 13
  10. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noisecited by 9
  11. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  12. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  13. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5
  14. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  15. 2024Asymptotic Analysis of Sample-averaged Q-learningcited by 2
  16. 2024Decoupled Functional Central Limit Theorems for Two-Time-Scale Stochastic Approximationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Gaussian Approximation for Asynchronous Q-learningcited by 1
  2. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  3. 2026On Gaussian approximation for entropy-regularized Q-learning with function approximationcited by 0
  4. 2026Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Hitting-Time Bounds for Asynchronous Q-Learning
  2. 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
  3. 2025From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
  4. 2026Online Statistical Inference of Constant Sample-averaged Q-Learning
  5. 2024Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning
  6. 2022The Efficacy of Pessimism in Asynchronous Q-Learning
  7. 2023Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments
  8. 2026Non-asymptotic Convergence of Average-reward Q-learning with Options