Gaussian Approximation for Asynchronous Q-learning

arXiv:2604.07323v1 Announce Type: cross 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^{-omega},, omega 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.

Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
Active Statistical Inference
PAC-Bayesian Bounds on Constrained f-Entropic Risk Measures
Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem

Source: arXiv cs.LG | 2026-04-10

Related