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

CardsList
  1. Gaussian Approximation for Asynchronous Q-learning

    Apr 8, 2026Artemy Rubtsov, Sergey Samsonov, Vladimir Ulyanov +1Polyak-Ruppert AveragingQ-Learning

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

    May 17, 2026Artemy Rubtsov, Rahul Singh, Eric Moulines +2Reinforcement LearningStochastic Approximation

  3. Hitting-Time Bounds for Asynchronous Q-Learning

    Oct 9, 2026Yang PengReinforcement LearningQ-Learning