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

• URL: http://arxiv.org/abs/2604.04218v1
• Date: Sun, 05 Apr 2026 18:31:51 GMT
• Title: Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization
• Abstract summary: We show that a proposed linear decay to zero (textttLD2Z: $_t,n= (1-t/n)$) schedule achieves a best-of-both-worlds result.<n>We also provide a novel time-uniform Gaussian approximation (textttPD2Z-$$) for the partial sum process of Q-learning iterates.
• Score: 1.7842332554022695
• License: http://creativecommons.org/licenses/by/4.0/
• 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}\equiv η$) or polynomially decaying ($η_{t} = ηt^{-α}$) 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 (\texttt{LD2Z}: $η_{t,n}=η(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 (\texttt{PD2Z}-$ν$: $η_{t,n}=η(1-t/n)^ν$). Proceeding step-by-step, we present a sharp non-asymptotic error bound for Q-learning with \texttt{PD2Z}-$ν$ schedule, which then is used to derive a central limit theory for a new \textit{tail} Polyak-Ruppert averaging estimator. Finally, we also provide a novel time-uniform Gaussian approximation (also known as \textit{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 \texttt{LD2Z} and in general \texttt{PD2Z}-$ν$ 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 \texttt{LD2Z} while providing practical guidelines for inference through our results.

Related papers

• Non-Asymptotic Variational Learning for Monotone Nonlinear Multiscale Elliptic Equations: Scale-Robust Primal-Dual Bounds and Strong-Form Statistical Ill-Conditioning [0.0]
  We develop a non-asymptotic approximation, sampling, and finite-iteration optimization theory for variational physics-informed approximations of uniformly nonlinear multiscale elliptic equations.<n>For boundary-compatible neural feature classes, the population error splits into approximation, empirical quadreration, and projected-gradient terms, with all non-approximation constants uniform in the microscopic scale (varepsilon)
  arXiv  Detail & Related papers  (2026-07-17T07:26:29Z)
• Sharper Analysis of Single-Loop Methods for Bilevel Optimization [81.36947969465848]
  We establish sharper convergence results for single-loop approximate implicit differentiation (AID) and iterative differentiation (ITD) methods.<n>We prove that the error is $mathcalO(2)$, exactly matching the known lower bound and improving upon the previous $mathcalO(3)$ guarantee.
  arXiv  Detail & Related papers  (2026-07-11T11:41:42Z)
• Exponential-Family Tensor Completion via Nonconvex Dual Total-Variation Regularization [33.64818873746132]
  We present a rigorous theoretical analysis of TV regularization for tensor completion under exponential-family noise.<n>We propose a family of dual-TV (DTV) regularizers based on the transformed L1 function, which simultaneously capture sparsity and low-rank structures in the gradient tensor.
  arXiv  Detail & Related papers  (2026-06-29T22:32:19Z)
• Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD [2.8104708182884046]
  We show that Random Reshuffling sharpens the mean-squared error (MSE) of the estimated solution, while Richardson-Romberg extrapolation acts as a second-order reduction in its bias.<n>Our work provides the first theoretical guarantees for such a synergy in structured non-monotone VIPs.
  arXiv  Detail & Related papers  (2026-04-11T22:59:26Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  We provide the first convergence guarantee for Optimistic Multiplicative Weights Update ($mathtOMWU$) in NLHF.<n>Our analysis identifies a novel marginal convergence behavior, where the probability of rarely played actions grows exponentially from exponentially small values.
  arXiv  Detail & Related papers  (2025-12-31T12:08:29Z)
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  Learning intersections of halfspaces is a central problem in Computational Learning Theory.<n>Even for just two halfspaces, it remains a major open question whether learning is possible in time.<n>We introduce a novel algorithm that provably circumvents the CSQ hardness barrier.
  arXiv  Detail & Related papers  (2025-11-13T00:28:24Z)
• A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies [3.950802208390739]
  We present the first finite-time analysis of the Q-learning algorithm under time-varying learning policies.<n>Results reveal that on-policy Q-learning exhibits weaker exploration than its off-policy counterpart.<n> Numerical simulations corroborate our theory.
  arXiv  Detail & Related papers  (2025-10-17T18:19:00Z)
• A Unified Analysis for Finite Weight Averaging [50.75116992029417]
  Averaging iterations of Gradient Descent (SGD) have achieved empirical success in training deep learning models, such as Weight Averaging (SWA), Exponential Moving Average (EMA), and LAtest Weight Averaging (LAWA) In this paper, we generalize LAWA as Finite Weight Averaging (FWA) and explain their advantages compared to SGD from the perspective of optimization and generalization.
  arXiv  Detail & Related papers  (2024-11-20T10:08:22Z)
• Double Successive Over-Relaxation Q-Learning with an Extension to Deep Reinforcement Learning [0.0]
  Successive Over-Relaxation (SOR) Q-learning, which introduces a relaxation factor to speed up convergence, has two major limitations.<n>We propose a sample-based, model-free double SOR Q-learning algorithm.<n>The proposed algorithm is extended to large-scale problems using deep RL.
  arXiv  Detail & Related papers  (2024-09-10T09:23:03Z)
• Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult [49.8719617899285]
  Large learning rates, when applied to objective descent for non optimization, yield various implicit biases including the edge of stability. This paper provides an initial step in descent and shows that these implicit biases are in fact various tips same iceberg.
  arXiv  Detail & Related papers  (2023-10-26T01:11:17Z)
• Stability and Risk Bounds of Iterative Hard Thresholding [41.082982732100696]
  We introduce a novel sparse generalization theory for IHT under the notion of algorithmic stability. We show that IHT with sparsity level $k$ enjoys an $mathcaltilde O(n-1/2sqrtlog(n)log(p))$ rate of convergence in sparse excess risk. Preliminary numerical evidence is provided to confirm our theoretical predictions.
  arXiv  Detail & Related papers  (2022-03-17T16:12:56Z)
• Beyond Tikhonov: Faster Learning with Self-Concordant Losses via Iterative Regularization [120.31448970413298]
  We extend the theory of Tikhonov regularization to generalized self concordant loss functions. We show that fast and optimal rates can be achieved for GSC by using the iterated Tikhonov regularization scheme.
  arXiv  Detail & Related papers  (2021-06-16T15:25:41Z)
• Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance [1.52292571922932]
  We study the convergence and finite-time analysis of the nonlinear two-time-scale approximation. In particular, we show that the method achieves a convergence in expectation at a rate $mathcalO (1/k2/3)$, where $k$ is the number of iterations.
  arXiv  Detail & Related papers  (2020-11-03T17:43:39Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  We provide the first non-asymptotic, finite-time analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $epsilon$-accurate neighborhood of the global optimum.
  arXiv  Detail & Related papers  (2020-09-29T18:48:21Z)

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.