Sign-Separated Finite-Time Error Analysis of Q-Learning

• URL: http://arxiv.org/abs/2605.16103v1
• Date: Fri, 15 May 2026 15:54:35 GMT
• Title: Sign-Separated Finite-Time Error Analysis of Q-Learning
• Abstract summary: This paper develops a sign-separated finite-time error analysis for constant step-size Q-learning.<n>The analysis identifies a max-induced asymmetry in Q-learning error dynamics.
• Score: 7.8232617281369805
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper develops a sign-separated finite-time error analysis for constant step-size Q-learning. Starting from the switching-system representation, the error is decomposed into its componentwise negative and positive parts. The negative part is dominated by a lower comparison linear time-invariant (LTI) system associated with a fixed optimal policy, whereas the positive part is controlled by a linear switching system. The resulting bounds show that the negative-side LTI certificate is no slower than the positive-side switching certificate and may produce a faster exponential envelope. The analysis identifies a max-induced asymmetry in Q-learning error dynamics. This asymmetry is connected to overestimation: positive action-wise errors can be selected and propagated by the Bellman maximum, whereas negative errors admit an optimal-policy lower comparison. Finite-time bounds are provided for both deterministic and stochastic constant-step-size recursions.

Related papers

• Joint Training of Multi-Token Prediction in Reinforcement Learning via Optimal Coefficient Calibration [61.46060073417047]
  Multi-Token Prediction (MTP) has been a widely adopted module in pretraining.<n>We show that the per-step effect of MTP on the RL objective can be decomposed into two terms: a first-order correlation and a second-order penalty.<n>We propose an adaptive scheme that tracks the optimal coefficient online via a log-probability proxy at negligible cost.
  arXiv  Detail & Related papers  (2026-05-27T09:07:06Z)
• A Switching System Theory of Q-Learning with Linear Function Approximation [10.48957127047368]
  This paper develops a switching-system interpretation of Q-learning with linear function approximation (LFA) based on the joint spectral radius (JSR)<n>We derive an exact linear switched model for the mean dynamics and relate it to the corresponding switched system.<n>The framework also yields a JSR-based view of regularized Q-learning with LFA.
  arXiv  Detail & Related papers  (2026-05-10T16:21:31Z)
• A Residual-Based Quantum Linear System Algorithm with Dynamic Stopping and Applications to Elliptic PDEs [3.3636842548621275]
  Quantum linear-system algorithms (QLSAs) have rigorous worst-case complexity guarantees, but their runtimes are often chosen from spectral information assumed in advance.<n>What is largely lacking is an a posteriori progress flag: most QLSA, unlike the classical counterparts, do not provide a built-in mechanism to signal whether a particular instance has already converged.<n>We design an augmented dynamics with residual variables, in which measuring a residual register gives an on-the-fly convergence indicator.
  arXiv  Detail & Related papers  (2026-05-07T15:22:55Z)
• Lyapunov-Certified Direct Switching Theory for Q-Learning [7.8232617281369805]
  We analyze Q-learning through a direct switching system representation.<n>We derive a finite-time final-iterate bound via a JSR-induced Lyapunov function.
  arXiv  Detail & Related papers  (2026-04-21T15:22:42Z)
• Verifying Closed-Loop Contractivity of Learning-Based Controllers via Partitioning [52.23804865017831]
  We address the problem of verifying closed-loop contraction in nonlinear control systems whose controller and contraction metric are both parameterized by neural networks.<n>We derive a tractable and scalable sufficient condition for closed-loop contractivity that reduces to checking that the dominant eigenvalue of a symmetric Metzler matrix is nonpositive.
  arXiv  Detail & Related papers  (2025-12-01T23:06:56Z)
• The Hidden Cost of Approximation in Online Mirror Descent [56.99972253009168]
  Online mirror descent (OMD) is a fundamental algorithmic paradigm that underlies many algorithms in optimization, machine learning and sequential decision-making.<n>In this work we initiate a systematic study into inexact OMD, and uncover an intricate relation between regularizer smoothness and robustness to approximation errors.
  arXiv  Detail & Related papers  (2025-11-27T10:09:07Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  We study the non-asymptotic performance of approximation schemes with delayed updates under Markovian sampling. Our theoretical findings shed light on the finite-time effects of delays for a broad class of algorithms.
  arXiv  Detail & Related papers  (2024-02-19T03:08:02Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• Learning with little mixing [9.574025613149871]
  We study square loss in a realizable time-series framework with martingale difference noise. Our main result is a fast rate excess risk bound which shows that whenever a trajectory hypercontractivity condition holds, the risk of the least-squares estimator on dependent data matches the iid rate order-wise after a burn-in time.
  arXiv  Detail & Related papers  (2022-06-16T16:06:47Z)
• Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes [72.68201611113673]
  This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. We assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available.
  arXiv  Detail & Related papers  (2020-03-13T23:39:40Z)

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.