Lyapunov-Certified Direct Switching Theory for Q-Learning

• URL: http://arxiv.org/abs/2604.19569v1
• Date: Tue, 21 Apr 2026 15:22:42 GMT
• Title: Lyapunov-Certified Direct Switching Theory for Q-Learning
• Abstract summary: 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.
• Score: 7.8232617281369805
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Q-learning is one of the most fundamental algorithms in reinforcement learning. We analyze constant-stepsize Q-learning through a direct stochastic switching system representation. The key observation is that the Bellman maximization error can be represented exactly by a stochastic policy. Therefore, the Q-learning error admits a switched linear conditional-mean recursion with martingale-difference noise. The intrinsic drift rate is the joint spectral radius (JSR) of the direct switching family, which can be strictly smaller than the standard row-sum rate. Using this representation, we derive a finite-time final-iterate bound via a JSR-induced Lyapunov function and then give a computable quadratic-certificate version.

Related papers

• Spectral Analysis of Dueling Q-Learning [7.8232617281369805]
  Q-learning is a fundamental algorithm in reinforcement learning (RL) for solving discounted Markov decision processes (MDPs)<n>The deep Q-network (DQN) extends Q-learning by using a deep neural network for Q-function approximation.<n>Dueling Q-learning decomposes the Q-function into a value function and an advantage function and learns the two components jointly.
  arXiv  Detail & Related papers  (2026-07-09T10:29:22Z)
• Online Learning with Gradient-Variation Interval Regret [54.59204826681113]
  We propose the first online learning algorithm that achieves an interval regret bound scaling with gradient variation.<n>Our method employs a simple and efficient two-layer online ensemble structure that achieves strong theoretical guarantees.
  arXiv  Detail & Related papers  (2026-06-02T16:16:45Z)
• Target Updates May Stabilize Linear Q-Learning: Periodic and Soft Dynamics [7.8232617281369805]
  This paper gives a rigorous and exact analysis of mechanisms for Q-learning with linear function approximation (linear Q-learning)<n>Although linear Q-learning can fail to converge in general, we prove that, under explicit spectral and step-size conditions, periodic hard target updates and soft target updates can guarantee convergence to the exact projected Q-Bellman solution.
  arXiv  Detail & Related papers  (2026-05-31T15:46:20Z)
• Sign-Separated Finite-Time Error Analysis of Q-Learning [7.8232617281369805]
  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.
  arXiv  Detail & Related papers  (2026-05-15T15:54:35Z)
• 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)
• GP-FL: Model-Based Hessian Estimation for Second-Order Over-the-Air Federated Learning [52.295563400314094]
  Second-order methods are widely adopted to improve the convergence rate of learning algorithms.<n>This paper introduces a novel second-order FL framework tailored for wireless channels.
  arXiv  Detail & Related papers  (2024-12-05T04:27:41Z)
• 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)
• Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity [3.4376560669160394]
  We introduce and analyze a novel model-free algorithm called Variance-Reduced Cascade Q-learning (VRCQ)<n>VRCQ provides superior guarantees in the $ell_infty$-norm compared with the existing model-free approximation-type algorithms.
  arXiv  Detail & Related papers  (2024-08-13T00:34:33Z)
• Symmetric Q-learning: Reducing Skewness of Bellman Error in Online Reinforcement Learning [55.75959755058356]
  In deep reinforcement learning, estimating the value function is essential to evaluate the quality of states and actions. A recent study suggested that the error distribution for training the value function is often skewed because of the properties of the Bellman operator. We proposed a method called Symmetric Q-learning, in which the synthetic noise generated from a zero-mean distribution is added to the target values to generate a Gaussian error distribution.
  arXiv  Detail & Related papers  (2024-03-12T14:49:19Z)
• Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation [27.17913040244775]
  We study asynchronous Q-learning with constant stepsize, which is commonly used in practice for its fast convergence. By connecting the constant stepsize Q-learning to a time-homogeneous chain, we show the distributional convergence of the iterates in distance. We also establish a Central Limit Theory for Q-learning iterates, demonstrating the normality of the averaged iterates. Specifically, the bias is proportional to the stepsize up to higher-order terms and we provide an explicit expression for the linear coefficient.
  arXiv  Detail & Related papers  (2024-01-25T02:01:53Z)
• QLABGrad: a Hyperparameter-Free and Convergence-Guaranteed Scheme for Deep Learning [6.555832619920502]
  We propose a novel learning rate adaptation scheme called QLABGrad. QLABGrad automatically determines the learning rate by optimizing the Quadratic Loss Approximation-Based (QLAB) function for a given gradient descent direction.
  arXiv  Detail & Related papers  (2023-02-01T05:29:10Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• Deep Learning Approximation of Diffeomorphisms via Linear-Control Systems [91.3755431537592]
  We consider a control system of the form $dot x = sum_i=1lF_i(x)u_i$, with linear dependence in the controls. We use the corresponding flow to approximate the action of a diffeomorphism on a compact ensemble of points.
  arXiv  Detail & Related papers  (2021-10-24T08:57:46Z)
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs [50.75812033462294]
  We bridge the gap between practical success of Q-learning and pessimistic theoretical results. We present novel methods Q-Rex and Q-RexDaRe. We show that Q-Rex efficiently finds the optimal policy for linear MDPs.
  arXiv  Detail & Related papers  (2021-10-16T01:47:41Z)
• 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.