stat.MLNov 15, 2026

Sharp Gaussian Approximation for Q-Learning

Authors: Xingtu Liu

Organizations: Department of Statistics and Data Science, University of California, Los Angeles.

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}).

Figures & tables

Explore similar work

Apr 8, 2026

Gaussian Approximation for Asynchronous Q-learning

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]k^{-ω},\, ω\in (1/2, 1]. Assuming that the sequence of state-action-next-state triples (sk,ak,sk+1)k≥0(s_k, a_k, s_{k+1})_{k \geq 0} forms a uniformly geometrically ergodic Markov chain, we establish a rate of order up to n−1/6log⁡4(nSA)n^{-1/6} \log^{4} (nS A) over the class of hyper-rectangles, where nn is the number of samples used by the algorithm and SS and AA 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.
May 17, 2026

On Gaussian approximation for entropy-regularized Q-learning with function approximation

In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak--Ruppert averaged iterates generated by entropy-regularized asynchronous Q-learning with linear function approximation and a polynomial stepsize k−ωk^{-ω}, ω∈(1/2,1)ω\in (1/2,1). Assuming that the sequence of observed triples (sk,ak,sk+1)k≥0(s_k,a_k,s_{k+1})_{k \geq 0} forms a uniformly geometrically ergodic Markov chain, and under suitable regularity conditions for the projected soft Bellman equation, we establish a Gaussian approximation bound in the convex distance with rate of order n−1/4n^{-1/4}, up to polylogarithmic factors in nn, where nn is the number of samples used by the algorithm. To obtain this result, we combine a linearization of the soft Bellman recursion with a Gaussian approximation for the leading martingale term. Finally, we derive high-order moment bounds for the algorithm's last iterate, which might be of independent interest.
Oct 9, 2026

Hitting-Time Bounds for Asynchronous Q-Learning

We study the last iterate of standard asynchronous Q-learning from a single trajectory of a finite Markov decision process. The trajectory follows a fixed behavior policy whose state--action chain is irreducible and may be periodic. For discount factor γγ, write H=(1−γ)−1H=(1-γ)^{-1}, and let μmin⁡μ_{\min} be the minimum stationary state--action probability and h⋆\mathfrak h_\star the largest expected hitting time of the reverse state--action chain. We prove that zero-initialized Q-learning with a constant step size achieves sup-norm error at most ε\varepsilon with high probability using O~(H4/(μmin⁡ε2)+h⋆)\widetilde{O}(H^4/(μ_{\min}\varepsilon^2)+\mathfrak h_\star) transitions, for 0<ε≤10<\varepsilon\le1. The statistical term retains the quartic effective-horizon dependence of standard Q-learning, while initialization cost is additive in h⋆\mathfrak h_\star. For aperiodic behavior chains, a comparison with mixing time yields a transient term O~(tmix/μmin⁡)\widetilde{O}(t_{\mathrm{mix}}/μ_{\min}). An empirical state--action count rule selects a constant step size for a subsequent training run and attains the same rate without prior knowledge of model parameters, target accuracy, or confidence level. The output is the last training iterate, with both stages included in the sample count. The proof uses two deterministic Bellman envelopes to separate statistical error from fixed-policy initialization error and adapts reverse-time hitting-cost compensation from TD learning to state--action propagation. An exploration lower bound holds for arbitrary predictable step sizes. Together with the existing statistical lower bound and its extension to pilot-selected constant steps, it yields matching mean-square rates up to logarithmic factors on the stated large-sample parameter classes.