Sharp asymptotic theory for Q-learning with LD2Z learning rate and its generalization

Soham Bonnerjee, Zhipeng Lou, Wei Biao Wu, [1em] Department of Statistics, University of Chicago · 2026

Read Sharp asymptotic theory for Q-learning with LD2Z learning rate and its generalization by Soham Bonnerjee, Zhipeng Lou, Wei Biao Wu, [1em] Department of Statistics, University of Chicago (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-04218.txt.

Introduction

Bonnerjee, Lou and Wu sharpen the theory of Q-learning, a method for learning policies. They study learning rates that decay linearly or as a power law to zero. For this schedule family, the paper proves a tight non-asymptotic error bound. A central limit result follows for a tail-averaged estimator. A time-uniform Gaussian approximation rounds out the results, supporting bootstrap inference. Numerical tests back the theory, which explains why these schedules combine fast early progress with lasting convergence.

Catalog record

CREATORSoham Bonnerjee, Zhipeng Lou, Wei Biao Wu, [1em] Department of Statistics, University of Chicago
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75751
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.04218

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sharp asymptotic theory for Q-learning with LD2Z learning rate and its generalization Soham Bonnerjee, Zhipeng Lou, Wei Biao Wu, [1em] Department of Statistics, University of Chicago Abstract Despite the sustained popularity of Q-learning as a practical tool for policy determination, a majority of relevant theoretical literature deals with either constant ( η t ≡ η \eta_{t}\equiv\eta ) or polynomially decaying ( η t = η ​ t − α \eta_{t}=\eta t^{-\alpha} ) learning schedules. However, it is well known that these choices suffer from either persistent bias or prohibitively slow convergence. In contrast, the recently proposed linear decay to zero ( LD2Z : η t , n = η ⁡ ( 1 − t / n ) \eta_{t,n}=\eta(1-t/n) ) schedule has shown appreciable empirical performance, but its theoretical and statistical properties remain largely unexplored, especially in the Q-learning setting. We address this gap in the literature by first considering a general class of power-law decay to zero ( PD2Z - ν \nu : η t , n = η ​ ( 1 − t / n ) ν \eta_{t,n}=\eta(1-t/n)^{\nu} ). Proceeding step-by-step, we present a sharp non-asymptotic error bound for Q-learning with PD2Z - ν \nu schedule, which then is used to derive a central limit theory for a new tail Polyak-Ruppert averaging estimator. Finally, we also provide a novel time-uniform Gaussian approximation (also known as strong invariance principle ) for the partial sum process of Q-learning iterates, which facilitates bootstrap-based inference. All our theoretical results are complemented by extensive numerical experiments. Beyond being new theoretical and statistical contributions to the Q-learning literature, our results definitively establish that LD2Z and in general PD2Z - ν \nu achieve a best-of-both-worlds property: they inherit the rapid decay from initialization (characteristic of constant step-sizes) while retaining the asymptotic convergence guarantees (characteristic of polynomially decaying schedules). This dual advantage explains the empirical success of LD2Z while providing practical guidelines for inference through our results. 1 Introduction With the advent of generative AI models and its continuing ascent towards ubiquity, the use of reinforcement learning (RL) to train multiple agents to undertake complex sequential decisions seamlessly, has occupied a central role in modern learning theory. In that regard, Q-learning ( Watkins et al. 1989 ; Watkins and Dayan 1992 ; Sutton and Barto 2018 ; Chi et al. 2025 ) , represents a classical, yet practically relevant model-free approach to estimate the optimal policy of a Markov decision process (MDP). Research on the statistical properties of the Q-learning algorithm has been extensive; in particular, treatment of asymptotic and non-asymptotic error bounds have ranged from techniques particular to synchronous Q-learning ( Jaakkola et al. 1993 ; Tsitsiklis 1994 ; Szepesvári 1997 ; Shi et al. 2022 ) , to the more modern lens of stochastic approximation (SA) algorithms ( Chen et al. 2020b ; Qu and Wierman 2020 ; Chen et al. 2021 ) . Specifically, these latter works cast the Q-learning algorithm as an SA targeting the Bellman equation, and thereby, more general tools can be employed to derive finer theoretical results on these algorithms. This direction also has been, arguably, adequately explored with central limit theory, and functional central-limit-theorems, appearing in ( Xie and Zhang 2022 ; Li et al. 2023b ; Li et al. 2023a ; Panda et al. 2024 ) . A special case of Q-learning with a singleton action space, is the Temporal-difference (TD) learning, for which Berry-Esseen theorems and subsequent Gaussian approximations and bootstrap strategies have been discussed ( Wu et al. 2024b ; Wu et al. 2025 ; Samsonov et al. 2025 ) . A very important, but often ignored aspect in these theoretical studies is the choice of step-sizes or learning rates. Indeed, it has become widely common in statistical inference literature to analyze either the constant learning rates or the polynomially decaying learning rate. Such choices are not without their own advantages; the constant learning rate enjoys experimental evidence of a much faster convergence, however a proof similar to Li et al. 2024b shows that the Q-learning with constant learning rate will converge to a stationary distribution around the optimal \mathbf{Q}^{\star} ; in other words, the asymptotic bias is non-negligible, and requires further jackknifing to ensure convergence. On the other hand, the polynomially decaying learning rate is theoretically attractive; the aforementioned results establishing Gaussian approximations and other inferential results extensively use a polynomially decaying learning rate. This choice has been guided by theory of stochastic gradient descent at least since ( Ruppert 1988 ; Polyak and Juditsky 1992 ) , however its theoretical optimality often masks its excruciatingly slow convergence, as also observed by ( Zhang and Xie 2024 ) . These criticisms have been echoed by the broad stochastic optimization community, leading to a recent proposal of linearly decaying to zero ( LD2Z ) learning rate \eta_{t,n}=\eta(1-t/n) ( Devlin et al. 2019 ; Touvron et al. 2023 ) . Despite a requirement of pre-specified number of schedules, this step-size choice achieves a balance between the rapid initial dissipation of initialization effects provided by a constant learning rate and the asymptotic convergence guarantees of a polynomially decaying learning rate. In this article, we establish a number of sharp asymptotic results for the Q-learning algorithm with this particular learning rate schedule. To the best of our knowledge, our results are the first-of-its-kind theory using this step-size for Q-learning; the theoretical results and subsequent numerical exercise definitively showcases the effectiveness and superiority of this learning rate over the ones usually employed in theoretical analyses. 1.1 Main contributions The paper develops a comprehensive theoretical framework for Q-learning with power-law decay to zero ( PD2Z - \nu ) learning schedules. Our results advance the theoretical understanding of Q-learning and offer new insights into its statistical properties and practical performance. The main contributions are summarized below: • Non-asymptotic concentration inequality. Under standard regularity conditions, we derive explicit non-asymptotic bounds on the p -th moments of the Q-learning iterates for any fixed p\geq 2 . In particular, our \mathcal{L}_{2} bounds can be summarized as follows. Theorem 1.1 (Theorem 3.3 , Informal) . If \mathbf{Q}_{n} denotes the final Q-learning iterate with the PD2Z - \nu step-size, then it follows that \|\mathbf{Q}_{n}-\mathbf{Q}^{\star}\|_{2}\lesssim\exp(-cn)|\mathbf{Q}_{0}-\mathbf{Q}^{\star}|+n^{-\frac{\nu}{2(\nu+1)}}, where \mathbf{Q}^{\star} is the long term reward corresponding to the optimal policy \pi^{\star} . These bounds serve as fundamental tools underpinning the empirical success of Q-learning with PD2Z - \nu schedules compared to their polynomially decaying counterparts (Section 3.1 ). In particular, the exponential decay from the initialization is empirically observed in Figure 1 , further validating our theory. • Distribution theory. We propose a novel averaging scheme that aggregates a batch of the most recent Q-learning iterates, referred to as the tail Polyak-Ruppert averaging estimator , and establish its asymptotic normality (Section 3.2 ). This is, to the best of our knowledge, a novel contribution in stochastic approximation literature. For the PD2Z - \nu learning schedules, our simulation (in § 5.4 ) also establishes the superiority of tail PR averaged estimator over the usual PR averaged ones. • Strong invariance principle. We establish strong invariance principles with covariance matching for the partial sum processes of Q-learning with both PD2Z - \nu and polynomially decaying learning schedules. This is accomplished via a novel

Read the complete text