betaFeedback

WorksMathematics

Sharp Gaussian Approximation for Q-Learning

Abstract

Gaussian approximation provides a foundation for online statistical inference in reinforcement learning. We establish sharp non-asymptotic Gaussian approximation rates in Wasserstein distance for asynchronous Q-learning with Polyak-Ruppert averaging. We prove an upper bound of O~(n−1/4)\widetilde{O}(n^{-1/4}), where nn is the number of iterations, together with a matching lower bound up to logarithmic factors. Q-learning is more challenging to analyze than linear stochastic approximation due to the nonlinearity of the Bellman operator. Asynchronous updates introduce further challenges due to Markovian noise. Our analysis separates the errors from Bellman nonlinearity, Markovian noise, and the finite-sample covariance discrepancy. In particular, we show that Markovian noise induces an unavoidable bias even when the Bellman operator is linear. The trade-off between this bias and the covariance discrepancy determines the convergence rate. We further extend our analysis to the synchronous setting and establish a sharp rate of O~(n−1/2)\widetilde{O}(n^{-1/2}).

Introduction

Q-learning [45] is one of the most fundamental algorithms in reinforcement learning (RL). It learns an optimal action-value function directly from sampled transitions and rewards. In this work, we study the convergence rate of Gaussian approximation for Q-learning as a function of the iteration number nn, which is also the number of samples in the asynchronous setting. Considerable progress has been made in understanding the finite-sample guarantees for Q-learning [13, 7 LWC+20, 23]. However, this line of work only bounds the distance between the estimate and the optimal Q-function, which does not determine the distribution of its error. Gaussian approximation addresses a different question. For the average Qˉn=n−1∑k=1nQk\bar{Q}_n = n^{-1} \sum_{k=1}^{n} Q_k, we study how close the distribution of n(Qˉn−Q⋆)\sqrt{n}(\bar{Q}_n - Q^\star) is to a centered Gaussian distribution. This provides a theoretical foundation for statistical inference, including the construction of confidence intervals and hypothesis tests [39]. It also plays an important role in designing UCB- and LCB-based algorithms.

Stochastic approximation (SA) [3, 4] is a general iterative framework to solve fixed-point equation problems. Since the Bellman operator in RL is a contraction map with a unique fixed point, many RL algorithms can be studied under this framework. A classic example is temporal-difference (TD) learning [38], which is an instance of linear SA. In contrast, Q-learning involves maximizing over actions, making the underlying Bellman operator nonlinear. Q-learning is typically studied in two settings, synchronous and asynchronous, which correspond to SA with martingale difference noise and Markovian noise, respectively. In synchronous Q-learning, all state-action pairs are updated at each iteration using samples from a generative model. This requires the ability to sample transitions from arbitrary state-action pairs, which is typically only available in simulations. In contrast, asynchronous Q-learning updates only the state-action pair visited at each iteration, making it a realistic formulation for interaction with the real environment. However, this gives rise to Markovian noise. In this work, we focus mainly on the more challenging asynchronous setting and then extend our results to the synchronous setting.

Gaussian approximation for SA algorithms has been extensively studied [29, 43, 17, 16, 22, 1, 41 SMS+24, 25]. However, existing results may not directly apply to specific RL algorithms, which can present additional challenges. Moreover, existing SA results often rely on more restrictive assumptions and do not fully exploit problem-specific structure and parameters. The lower-bound constructions therein are also not applicable to RL algorithms. Non-asymptotic Gaussian approximations for TD learning have been established in [41 SMS+24]. For Q-learning, functional central limit theorems have been shown [47, 28, 49, 34]. The first non-asymptotic Gaussian approximation bound for Q-learning was proved in [24], which obtained a rate of O~(n−1/6)\widetilde{O}(n^{-1/6}) in Wasserstein distance under the asynchronous setting. Subsequently, [37] established a bound with the same rate on nn in a different distance. These results leave open the question of whether the convergence rate can be further improved and, more fundamentally,

What is the sharpest achievable rate of Gaussian approximation for Q-learning in terms of nn?

Overview of Main Results

We study Q-learning with Polyak–Ruppert averaging and polynomial stepsizes αt=c0(t+b)−β\alpha_t = c_0(t+b)^{-\beta}. Our objective is to quantify how accurately a centered Gaussian approximates the normalized error Xn=n(Qˉn−Q⋆)X_n = \sqrt{n}(\bar{Q}_n - Q^\star). We first consider asynchronous updates along a single Markovian trajectory. Theorem 3.1 gives the following bound in Wasserstein distance, up to logarithmic factors,

W1(Xn,Z∞)≲n−1/4⏟Gaussian approximation+nβ−1⏟covariance discrepancy+n1/2−β⏟Bellman nonlinearity and Markovian noise.W_1(X_n, Z_\infty) \lesssim\underbrace{n^{-1/4}}_{\text{Gaussian approximation}} + \underbrace{n^{\beta-1}}_{\text{covariance discrepancy}} + \underbrace{n^{1/2-\beta}}_{\text{Bellman nonlinearity and Markovian noise}}.

where Z∞∼N(0,Σ∞)Z_\infty\sim\mathcal{N}(0,\Sigma_\infty), Σ∞\Sigma_\infty is the limiting covariance, and 12<β<1\frac{1}{2} < \beta< 1.

The three terms reflect different parts of the approximation. First, we approximate a weighted sum MnM_n of fixed-point martingale noises by a Gaussian vector Zn∼N(0,Cn)Z_n \sim\mathcal{N}(0,C_n), where the deterministic covariance CnC_n retains the finite horizon. Second, we compare CnC_n with its limit Σ∞\Sigma_\infty. Third, we analyze the errors from the nonlinear Bellman operator and the Markovian noises.

A key step in the analysis is to retain the exact averaging weights when constructing the intermediate Gaussian approximation. Replacing these weights by their limits and using a second-moment coupling gives an error bound of order n(β−1)/2n^{(\beta-1)/2}. We instead first approximate MnM_n by ZnZ_n and then compare them through their covariance matrices. The latter error is proportional to ∥Cn−Σ∞∥F=O(nβ−1)\lVert C_n-\Sigma_\infty\rVert_F = O(n^{\beta-1}). Avoiding the additional square root allows a sharper balance with the n1/2−βn^{1/2-\beta} term and improves the previously established polynomial rate from n−1/6n^{-1/6} to n−1/4n^{-1/4}. We also carry out a numerical experiment (Figure 1) to validate our theoretical results.

Figure 1. Gaussian approximation for asynchronous QQ-learning on a four-state, three-action MDP with β=3/4\beta= 3/4. (a) Empirical projected Wasserstein distance d^n\hat{d}_n and its theoretical rate n−1/4Bn^{-1/4}B, where B≈73.13670B \approx73.13670 is computed from the given MDP and stepsize. (b) Covariance error ∥Cn−Σ∞∥F\lVert C_n - \Sigma_\infty\rVert_{\mathrm{F}} and its theoretical rate n−1/4∥G∥Fn^{-1/4}\lVert G\rVert_{\mathrm{F}}, where ∥G∥F≈24.44716\lVert G\rVert_{\mathrm{F}} \approx24.44716.

The stepsize creates a trade-off between the last two terms. Increasing β\beta makes the stepsizes smaller and reduces the accumulated nonlinear and Markovian errors of order n1/2−βn^{1/2-\beta}. However, it increases the covariance discrepancy of order nβ−1n^{\beta-1}. Smaller updates give samples collected near the end less time to influence the average, increasing the difference between the finite-sample covariance and its limit. The two orders balance at β=3/4\beta= 3/4, giving the upper bound O~(n−1/4)\widetilde{O}(n^{-1/4}).

To determine whether this rate can be improved, we construct a fixed two-state, one-action MDP and establish matching lower bounds for every fixed β∈(1/2,1)\beta\in(1/2,1) in Theorem 3.2. On this example, the mean bias has order nαn\sqrt{n}\alpha_n, and the covariance has the expansion Cn=Σ∞+nβ−1G+o(nβ−1)C_n = \Sigma_\infty+ n^{\beta-1}G + o(n^{\beta-1}) with G≻0G \succ0. These two results give a lower bound of order max⁡{n1/2−β,nβ−1}\max\{n^{1/2-\beta}, n^{\beta-1}\}. Since there is only one action, the Bellman operator is linear. Thus, the mean-bias lower bound isolates the effect of Markovian sampling. Together, the upper and lower bounds establish the optimal polynomial rate n−1/4n^{-1/4} up to logarithmic factors.

We then study synchronous Q-learning, which uses independent transition samples for every state-action pair at each iteration. Under certain conditions and up to logarithmic factors,

W1(Xn,Z∞syn)≲n−1/2+n−β+nβ−1,W_1(X_n, Z^{\mathrm{syn}}_\infty) \lesssim n^{-1/2} + n^{-\beta} + n^{\beta-1},

for 12≤β<1\frac{1}{2} \le\beta< 1. Independent sampling removes the Markovian mean bias. This allows β=1/2\beta= 1/2 and yields a better rate O~(n−1/2)\widetilde{O}(n^{-1/2}). Switching the same lower-bound MDP to the synchronous setting gives an Ω(n−1/2)\Omega(n^{-1/2}) lower bound at β=1/2\beta= 1/2 and an Ω(nβ−1)\Omega(n^{\beta-1}) lower bound for every fixed β>1/2\beta> 1/2. Thus the synchronous rate is also sharp up to logarithmic factors.

Remark 1.1. In asynchronous Q-learning, each iteration uses one sample, and therefore nn denotes both the number of iterations and the number of samples. In the synchronous setting, we use nn to count iterations, each of which requires one sample per state-action pair. The total sample size is therefore N=n∣S∣∣A∣N = n|\mathcal{S}||\mathcal{A}|. Thus, faster convergence in iterations does not by itself imply better sample complexity. A comparison at the same sample budget must also account for the dimension dependence hidden in our bounds, which we leave for future work.

Preliminaries

An infinite-horizon discounted Markov decision process (MDP) is denoted by M\mathcal{M}, and is defined by the tuple ⟨S,A,P,r,γ⟩\langle\mathcal{S}, \mathcal{A}, P, r, \gamma\rangle where S\mathcal{S} is the set of states, A\mathcal{A} is the set of actions, P:S×A→ΔSP : \mathcal{S} \times\mathcal{A} \to\Delta_{\mathcal{S}} is the transition probability function, r(s,a)∈[0,1]r(s,a) \in[0,1] is the reward, and γ∈(0,1)\gamma\in(0,1) is the discount factor. Let d=∣S∣∣A∣d = |\mathcal{S}||\mathcal{A}| and H=(1−γ)−1H = (1-\gamma)^{-1}. Let ΔA\Delta_{\mathcal{A}} denotes the simplex over the action space. The action-value function (Q-function) of a stationary and stochastic policy π:S→ΔA\pi: \mathcal{S} \to\Delta_{\mathcal{A}} is defined as Qπ(s,a)=E[∑t=0∞γtr(st,at)|s0=s,a0=a]Q^\pi(s,a) = \mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^t r(s_t,a_t)\middle|s_0=s,a_0=a\right], where at∼π(⋅∣st)a_t \sim\pi(\cdot|s_t) and st+1∼P(⋅∣st,at)s_{t+1} \sim P(\cdot|s_t,a_t). The optimal Q-function is defined as Q⋆:=max⁡πQπQ^\star:= \max_\pi Q^\pi. We identify a Q-function with a vector in Rd\mathbb{R}^d. For q∈Rdq \in\mathbb{R}^d, let V(q)∈R∣S∣V(q) \in\mathbb{R}^{|\mathcal{S}|} be its associated value vector and let T:Rd→Rd\mathcal{T} : \mathbb{R}^d \to\mathbb{R}^d be the Bellman operator:

V(q)(s)=max⁡a∈Aq(s,a),(Tq)(s,a)=r(s,a)+γ∑s′∈SP(s′∣s,a)V(q)(s′).(1)V(q)(s) = \max_{a \in\mathcal{A}} q(s,a), \qquad(\mathcal{T}q)(s,a) = r(s,a) + \gamma\sum_{s' \in\mathcal{S}} P(s' \mid s,a)V(q)(s'). \tag*{(1)}

The operator T\mathcal{T} is a γ\gamma-contraction in the maximum norm. It therefore has a unique fixed point Q⋆Q^\star. The reward bound gives Q⋆∈[0,H]dQ^\star\in[0,H]^d. We write V⋆=V(Q⋆)V^\star= V(Q^\star) for the optimal value function.

References

  1. [1][BCD+25] Vivek Borkar, Shuhang Chen, Adithya Devraj, Ioannis Kontoyiannis, and Sean Meyn. The ode method for asymptotic statistics in stochastic approximation and reinforcement learning. The Annals of Applied Probability, 35(2):936–982, 2025.arxiv.org/abs/2110.14427
  2. [2][BMN+25] Bogdan Butyrin, Eric Moulines, Alexey Naumov, Sergey Samsonov, Qi-Man Shao, and Zhuo-Song Zhang. Improved central limit theorem and bootstrap approximations for linear stochastic approximation. arXiv preprint arXiv:2510.12375, 2025.arxiv.org/abs/2510.12375
  3. [3][BMP12] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012.
  4. [4][Bor08] Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2008.
  5. [5][BR97] Rajendra Bhatia and Peter Rosenthal. How and why to solve the operator equation AX − XB = Y. Bulletin of the London Mathematical Society, 29(1):1–21, 1997.DOI
  6. [6][BRN+26] Bogdan Butyrin, Artemy Rubtsov, Alexey Naumov, Vladimir V Ulyanov, and Sergey Samsonov. Gaussian approximation for two-timescale linear stochastic approximation. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43):36627–36635, 2026.arxiv.org/abs/2508.07928
  7. [7][BS12] Carolyn L Beck and Rayadurgam Srikant. Error bounds for constant step-size q-learning. Systems & control letters, 61(12):1203–1208, 2012.DOI
  8. [8][CDBM20] Shuhang Chen, Adithya Devraj, Ana Busic, and Sean Meyn. Explicit mean-square error bounds for monte-carlo and linear stochastic approximation. In International Conference on Artificial Intelligence and Statistics, pages 4173–4183. PMLR, 2020.arxiv.org/abs/2002.02584
  9. [9][Cha08] Sourav Chatterjee. A new method of normal approximation. The Annals of Probability, 36(4):1584 – 1610, 2008.DOI
  10. [11][CMZ25] Zaiwei Chen, Siva Theja Maguluri, and Martin Zubeldia. Concentration of contractive stochastic approximation: Additive and multiplicative noise. The Annals of Applied Probability, 35(2):1298–1352, 2025.arxiv.org/abs/2303.15740
  11. [12]Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier. Markov chains. Springer, 2018.
  12. [13]Eyal Even-Dar and Yishay Mansour. Learning rates for q-learning. Journal of machine learning Research, 5(Dec):1–25, 2003.DOI
  13. [14]Gerald B. Folland. Real Analysis: Modern Techniques and Their Applications. John Wiley & Sons, 2 edition, 1999.
  14. [15]Peter W Glynn and Sean P Meyn. A liapounov bound for solutions of the poisson equation. The Annals of Probability, pages 916–931, 1996.DOI
  15. [16]Jie Hu, Vishwaraj Doshi, and Do Young Eun. Central limit theorem for two-timescale stochastic approximation with markovian noise: Theory and applications. In International Conference on Artificial Intelligence and Statistics, pages 1477–1485. PMLR, 2024.arxiv.org/abs/2401.09339
  16. [17]Yuze Han, Xiang Li, Jiadong Liang, and Zhihua Zhang. Decoupled functional central limit theorems for two-time-scale stochastic approximation. arXiv preprint arXiv:2412.17070, 2024.arxiv.org/abs/2412.17070
  17. [18]Li Jiang, Xiao Li, Andre Milzarek, and Junwen Qiu. A generalized version of Chung’s lemma and its applications. arXiv preprint arXiv:2406.05637, 2024. The cited Proposition A.1 and Lemma 2.4(a) are in version 2, revised February 2026.arxiv.org/abs/2406.05637
  18. [19]Hassan K Khalil. Nonlinear systems. Prentice hall, Upper Saddle River, NJ, 3 edition, 2002.
  19. [20]Seo Taek Kong and R Srikant. Finite-sample wasserstein error bounds and concentration inequalities for nonlinear stochastic approximation. arXiv preprint arXiv:2602.02445, 2026.arxiv.org/abs/2602.02445
  20. [21]Koulik Khamaru, Eric Xia, Martin J Wainwright, and Michael I Jordan. Instance-optimality in optimal value estimation: Adaptivity via variance-reduced q-learning. arXiv preprint arXiv:2106.14352, 2021.arxiv.org/abs/2106.14352
  21. [22]Seo Taek Kong, Sihan Zeng, Thinh T Doan, and R Srikant. Nonasymptotic clt and error bounds for two-time-scale stochastic approximation. arXiv preprint arXiv:2502.09884, 2025.arxiv.org/abs/2502.09884
  22. [23]Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejie Chi. Is q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 72(1):222–236, 2024.arxiv.org/abs/2102.06548
  23. [24]Xingtu Liu. Central limit theorems for asynchronous averaged q-learning. In Proceedings of The 8th Annual Learning for Dynamics and Control Conference, volume 331 of Proceedings of Machine Learning Research, pages 2207–2230. PMLR, 17–19 Jun 2026.arxiv.org/abs/2509.18964
  24. [25]Xiang Li, Jiadong Liang, and Zhihua Zhang. Weak convergence rates for partial-sum processes of nonlinear stochastic approximation. arXiv preprint arXiv:2609.40338, 2026.arxiv.org/abs/2609.40338
  25. [26]David A. Levin and Yuval Peres. Markov Chains and Mixing Times. American Mathematical Society, 2 edition, 2017. With contributions by Elizabeth L. Wilmer.
  26. [28]Xiang Li, Wenhao Yang, Jiadong Liang, Zhihua Zhang, and Michael I Jordan. A statistical analysis of polyak-ruppert averaged q-learning. In International Conference on Artificial Intelligence and Statistics, pages 2207–2261. PMLR, 2023.
  27. [29]Wenlong Mou, Chris Junchi Li, Martin J Wainwright, Peter L Bartlett, and Michael I Jordan. On linear stochastic approximation: Fine-grained polyak-ruppert and non-asymptotic concentration. In Conference on Learning Theory, pages 2947–2997. PMLR, 2020.arxiv.org/abs/2004.04719
  28. [30]Abdelkader Mokkadem and Mariane Pelletier. Convergence rate and averaging of non-linear two-time-scale stochastic approximation algorithms. The Annals of Applied Probability, 16(3):1671–1702, 2006.
  29. [31]Armand M Makowski and Adam Shwartz. The poisson equation for countable markov chains: probabilistic methods and interpretations. In Handbook of Markov Decision Processes: Methods and Applications, pages 269–303. Springer, 2002.DOI
  30. [32]Iosif Pinelis. Optimum bounds for the distributions of martingales in Banach spaces. The Annals of Probability, 22(4):1679–1706, 1994.arxiv.org/abs/1208.2200
  31. [33]Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838–855, 1992.DOI
  32. [34]Saunak Kumar Panda, Ruiqi Liu, and Yisha Xiang. Asymptotic analysis of sample-averaged q-learning. IEEE Transactions on Information Theory, 2025.arxiv.org/abs/2410.10737
  33. [37]Artemy Rubtsov, Sergey Samsonov, Vladimir Ulyanov, and Alexey Naumov. Gaussian approximation for asynchronous q-learning. arXiv preprint arXiv:2604.07323, 2026.arxiv.org/abs/2604.07323
  34. [38]Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press Cambridge, 1998.DOI
  35. [39]Chengchun Shi. Statistical inference in reinforcement learning: A selective survey. arXiv preprint arXiv:2502.16195, 2025.arxiv.org/abs/2502.16195
  36. [41]R Srikant. Rates of convergence in the central limit theorem for markov chains, with an application to td learning. arXiv preprint arXiv:2401.15719, 2024.arxiv.org/abs/2401.15719
  37. [42]Marina Sheshukova, Sergey Samsonov, Denis Belomestny, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaussian approximation and multiplier bootstrap for stochastic gradient descent. arXiv preprint arXiv:2502.06719, 2025.arxiv.org/abs/2502.06719
  38. [43]Sergey Samsonov, Marina Sheshukova, Eric Moulines, and Alexey Naumov. Statistical inference for linear stochastic approximation with markovian noise. arXiv preprint arXiv:2505.19102, 2025.arxiv.org/abs/2505.19102
  39. [44]Cédric Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, 2009.
  40. [45]Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279–292, 1992.DOI
  41. [46]Ziyang Wei, Jiaqi Li, Zhipeng Lou, and Wei Biao Wu. Gaussian approximation and concentration of constant learning-rate stochastic gradient descent. Advances in Neural Information Processing Systems, 38:85003–85033, 2025.DOI
  42. [47]Chuhan Xie and Zhihua Zhang. A statistical online inference approach in averaged stochastic approximation. Advances in Neural Information Processing Systems, 35:8998–9009, 2022.DOI
  43. [49]Yixuan Zhang and Qiaomin Xie. Constant stepsize q-learning: Distributional convergence, bias and extrapolation. arXiv preprint arXiv:2401.13884, 2024.arxiv.org/abs/2401.13884

Paper details

vlnc:W_ynd2ufq2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents