mlsanityData to 14 Oct 2026

Gaussian Approximation for Asynchronous Q-learning

arXiv 2604.07323 ↗First posted 8 Apr 2026stat.ML cs.LG math.PRcited by 1

Not on the map. Why?

Abstract (arXiv)

In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak-Ruppert averaged iterates generated by the asynchronous Q-learning algorithm with a polynomial stepsize k-ω,, ω ∈ (1/2, 1]. Assuming that the sequence of state-action-next-state triples (sk, ak, sk+1)k ≥ 0 forms a uniformly geometrically ergodic Markov chain, we establish a rate of order up to n-1/6 log4 (nS A) over the class of hyper-rectangles, where n is the number of samples used by the algorithm and S and A denote the numbers of states and actions, respectively. To obtain this result, we prove a high-dimensional central limit theorem for sums of martingale differences, which may be of independent interest. Finally, we present bounds for high-order moments for the algorithm's last iterate.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 22 of its 53 references that are in the map. First posted on arXiv 8 Apr 2026.

Builds on

22 of 53 references.

References · 22

  1. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  2. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  3. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  4. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  5. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  6. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  7. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  8. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
  9. 2020Online Covariance Matrix Estimation in Stochastic Gradient Descentcited by 37
  10. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  11. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  12. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
10 more
  1. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  2. 2024Statistical Inference for Policy Evaluation with Temporal Difference Learningcited by 15
  3. 2025Statistical inference for Linear Stochastic Approximation with Markovian Noisecited by 13
  4. 2025Uncertainty quantification for Markov chain induced martingales with application to temporal difference learningcited by 11
  5. 2025Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descentcited by 10
  6. 2024Asymptotics of Stochastic Gradient Descent with Dropout Regularization in Linear Modelscited by 7
  7. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  8. 2025Gaussian Approximation for Two-Timescale Linear Stochastic Approximationcited by 5
  9. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 4
  10. 2025Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximationcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026On Gaussian approximation for entropy-regularized Q-learning with function approximationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Hitting-Time Bounds for Asynchronous Q-Learning
  2. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation
  3. 2025From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes
  4. 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
  5. 2024Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA
  6. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
  7. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications
  8. 2026Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization