Gaussian Approximation for Asynchronous Q-learning

• URL: http://arxiv.org/abs/2604.07323v1
• Date: Wed, 08 Apr 2026 17:37:15 GMT
• Title: Gaussian Approximation for Asynchronous Q-learning
• Abstract summary: We prove a high-dimensional central limit theorem for sums of martingale differences.<n>We present bounds for high-order moments for the algorithm's last iterate.
• Score: 11.260593100797381
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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^{-ω},\, ω\in (1/2, 1]$. Assuming that the sequence of state-action-next-state triples $(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/6} \log^{4} (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.

Related papers

• Gaussian Approximation for Multivariate Martingale Sums from Uniformly Ergodic Markov Chains [19.40811084751516]
  We develop bounds in higher-order Wasserstein distance $W_p$, $pgeq2$, for sums of multivariate martingale differences generated by a uniformly ergodic Markov chain.<n>Our analysis develops two techniques for addressing the interplay between higher-order Wasserstein distance and temporal dependence.
  arXiv  Detail & Related papers  (2026-09-08T21:54:29Z)
• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere.<n>Our guiding principle is that its maximizers are rounding candidates.
  arXiv  Detail & Related papers  (2026-08-03T17:58:00Z)
• On Gaussian approximation for entropy-regularized Q-learning with function approximation [30.147231451149064]
  We derive rates of convergence in the high-dimensional central theorem for Polyak-uppert iterates generated by entropy-regularized asynchronous Q-learning.<n>We establish a Gaussian approximation bound in the convex distance with rate of order $n-1/4$, up to polyarithmic factors in $n$, where $n$ is the number of samples used by the algorithm.
  arXiv  Detail & Related papers  (2026-05-17T22:23:25Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• The Picard-Lagrange Framework for Higher-Order Langevin Monte Carlo [15.440889897519483]
  We introduce a new sampling algorithm built on a general $K$th-order Langevin dynamics, extending beyond second- and third-order methods.<n>For targets with smooth, strongly log-concave densities, we prove dimension-dependent convergence in Wasserstein distance.<n>This is the first sampling algorithm achieving such query complexity.
  arXiv  Detail & Related papers  (2025-10-21T03:04:58Z)
• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Decision Processes (MDs) with finite state spaces.<n>We demonstrate that the step sizes for both the actor and critic must decay as ( O(k-Pfrac12) ) with $k$ diverging from the conventional ( O(k-Pfrac12) ) rates commonly used in (non- optimal) Markov framework optimization.
  arXiv  Detail & Related papers  (2024-10-11T14:46:29Z)
• A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties [7.281869462071603]
  The proximal gradient method (PSGD) is one of the state-of-the-art approaches for composite-type problems.<n>In this paper, we present a simple variant of PSGD based on Robinsons map.
  arXiv  Detail & Related papers  (2023-05-10T01:12:11Z)
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
  We develop two new algorithms to approximate a solution of nonlinear equations in large-scale settings.<n>We apply our methods to a class of large-scale finite-sum inclusions, which covers prominent applications in machine learning, statistical learning, and network optimization.
  arXiv  Detail & Related papers  (2023-01-08T21:46:27Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation [22.51165277694864]
  This paper provides a finite-time analysis of linear approximation (LSA) algorithms with fixed step size. LSA is used to compute approximate solutions of a $d$-dimensional linear system.
  arXiv  Detail & Related papers  (2022-07-10T14:36:04Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  We show a non-asymptotic bound of the order $t_mathrmmix tfracdn$ on the squared error of the last iterate of a standard scheme. We derive corollaries of these results for policy evaluation with Markov noise.
  arXiv  Detail & Related papers  (2021-12-23T18:47:50Z)
• The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning [3.8098187557917464]
  The paper concerns the $d$-dimensional recursion approximation, $$theta_n+1= theta_n + alpha_n + 1 f(theta_n, Phi_n+1) The main results are established under additional conditions on the mean flow and a version of the Donsker-Varadhan Lyapunov drift condition known as (DV3) An example is given where $f$ and $barf$ are linear in $theta$, and $Phi$ is a geometrical
  arXiv  Detail & Related papers  (2021-10-27T13:38:25Z)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
  We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. We prove that the zigzag sampling algorithm achieves $varepsilon$ error in chi-square divergence with a computational cost equivalent to $Obigl.
  arXiv  Detail & Related papers  (2020-12-21T03:10:21Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  We first prove a simple variant of the vanilla coordinate ascent, called Coordinate-Ascent+. We then propose Coordinate-Ascent++, that achieves tight $(1-1/e-varepsilon)$-approximation guarantee while performing the same number of iterations. The computation of each round of Coordinate-Ascent++ can be easily parallelized so that the computational cost per machine scales as $O(n/sqrtvarepsilon+nlog n)$.
  arXiv  Detail & Related papers  (2020-06-21T06:57:59Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.