# Gaussian Approximation for Asynchronous Q-learning

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

## Key facts

- Cited by 1 papers 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 (most cited first, 22 of 22)

- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes](https://mlsanity.com/paper/2002.00874/) (2020)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Statistical Inference for Policy Evaluation with Temporal Difference Learning](https://mlsanity.com/paper/2410.16106/) (2024)
- [Statistical inference for Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2505.19102/) (2025)
- [Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning](https://mlsanity.com/paper/2502.13822/) (2025)
- [Gaussian Approximation and Multiplier Bootstrap for Stochastic Gradient Descent](https://mlsanity.com/paper/2502.06719/) (2025)
- [Asymptotics of Stochastic Gradient Descent with Dropout Regularization in Linear Models](https://mlsanity.com/paper/2409.07434/) (2024)
- [Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2502.09884/) (2025)
- [Gaussian Approximation for Two-Timescale Linear Stochastic Approximation](https://mlsanity.com/paper/2508.07928/) (2025)
- [Central Limit Theorems for Asynchronous Averaged Q-Learning](https://mlsanity.com/paper/2509.18964/) (2025)
- [Improved Central Limit Theorem and Bootstrap Approximations for Linear Stochastic Approximation](https://mlsanity.com/paper/2510.12375/) (2025)

## Built on by (most cited first, 1 of 1)

- [On Gaussian approximation for entropy-regularized Q-learning with function approximation](https://mlsanity.com/paper/2605.17678/) (2026)

## 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.