Lyapunov-Certified Direct Switching Theory for Q-Learning
Donghwan Lee · 2026
Read Lyapunov-Certified Direct Switching Theory for Q-Learning by Donghwan Lee (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-19569.txt.
Introduction
Lee develops a new framework for analyzing constant step-size tabular Q-learning from a switching linear system viewpoint. Q-learning is a fundamental primitive in reinforcement learning. The paper derives a stochastic switching linear system representation of the Q-learning error. It adds a finite-time error analysis through the joint spectral radius of the corresponding system model. The joint spectral radius is the exact worst-case exponential rate of the associated system.
Catalog record
| CREATOR | Donghwan Lee |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105202 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.19569
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lyapunov-Certified Direct Switching Theory for Q-Learning Donghwan Lee Abstract Q-learning is a fundamental algorithmic primitive in reinforcement learning. This paper develops a new framework for analyzing Q-learning from a switching-system viewpoint. In particular, we derive a direct stochastic switching-system representation of the Q-learning error. The key observation is that the Bellman maximization error can be expressed exactly as an average of action-wise Q-errors under a suitable stochastic policy. The resulting recursion has a switched linear conditional-mean drift and martingale-difference noise. To the best of our knowledge, this is the first convergence-rate analysis of standard Q-learning whose leading exponential rate is expressed through the joint spectral radius (JSR) of a direct switching family. Since the JSR is the exact worst-case exponential rate of the associated switched linear drift, the resulting rate is among the tightest drift-based rates that can be certified for this Q-learning representation. Building on this representation, we prove finite-time bounds based on a product-defined JSR-induced Lyapunov function and also give an optional common quadratic Lyapunov certificate. The quadratic certificate is only a sufficient condition and hence applies only to instances for which the certificate is feasible, whereas the JSR-induced Lyapunov construction applies to the full direct switching family whenever its JSR is below one. When feasible, the quadratic certificate replaces product-based verification by a computable matrix inequality and gives a simpler stochastic bound. We further extend the framework to Markovian observation models. 1 Introduction Q-learning [ 29 ] is a foundational algorithm in reinforcement learning (RL) [ 24 ] for solving discounted Markov decision processes (MDPs) with unknown transition kernels. Its convergence has been studied extensively over the past several decades. Classical analyses primarily establish asymptotic convergence [ 27 , 9 , 3 , 13 ] . While these results are fundamental, asymptotic convergence alone does not quantify how rapidly the iterates approach the solution, and therefore does not fully characterize the efficiency of the algorithm. This limitation has motivated a growing body of finite-time convergence analyses, which provide explicit bounds on the progress of the iterates toward the optimal Q-function. Recent advances in finite-time analysis include [ 25 , 11 , 6 , 1 , 28 , 21 , 16 , 5 ] . Most existing results view Q-learning as a nonlinear stochastic approximation scheme [ 12 ] and rely on the contraction property of the Bellman optimality operator. A useful alternative viewpoint is to regard Q-learning as a discrete-time stochastic switching system [ 19 , 17 ] . This perspective was developed in [ 13 , 14 , 15 , 18 ] and was used to prove a final-iterate bound for constant-step-size Q-learning. In that formulation, the error dynamics are affine rather than linear, because the greedy policy selected by the current iterate may differ from an optimal policy. The resulting affine term is controlled through upper and lower comparison systems. More specifically, the upper comparison system remains a switching system, whereas the lower comparison system is linear. Although this comparison-system approach is useful for deriving valid finite-time bounds, it has an inherent limitation: it controls the Q-learning error through auxiliary systems rather than directly exploiting the switching structure of the original error recursion. Consequently, intrinsic quantities from switching-system theory, such as the joint spectral radius (JSR) [ 22 , 26 , 10 ] , are difficult to apply directly to the original Q-learning dynamics. To overcome this limitation, this paper develops a direct switching-system representation of the Q-learning error. The key observation is that the Bellman maximization error can be represented exactly as an average of action-wise Q-errors under a suitably chosen stochastic policy. Substituting this identity into the Q-learning recursion yields a switched linear conditional-mean error system, while the stochastic component remains a martingale difference. The corresponding deterministic convergence rate is characterized by the JSR of the resulting direct switching family. This is the central distinction from existing Bellman-contraction and comparison-system analyses: the rate is attached to the exact direct switched drift rather than to an auxiliary contraction or row-sum upper bound. To the best of our knowledge, this is the first convergence-rate framework for standard Q-learning whose leading exponential rate is formulated in terms of such a direct JSR. Since the JSR is the exact worst-case exponential rate of the switched linear family, the resulting transient bound is among the tightest drift-based bounds that can be certified for Q-learning under this direct representation. We first develop the framework under an i.i.d. observation model with a constant step size, where the direct switching structure is most transparent. We then extend both the representation and the corresponding finite-time analysis to Markovian observation models. To certify convergence rates, we use two complementary Lyapunov certificates. The first is a product-defined JSR-induced Lyapunov function [ 7 , 8 ] for the direct switching family. This certificate is intrinsic to the JSR analysis and, because the direct family has \rho_{\alpha}^{\mathrm{dir}}<1 under the standing assumptions, it is available for every Q-learning instance considered here. The second is a common quadratic Lyapunov certificate. This quadratic certificate is only a sufficient condition and therefore applies only to the special instances for which the associated matrix inequalities are feasible. Its advantage is computational and algebraic: it can be checked by finite linear matrix inequalities and yields a shorter stochastic proof with more explicit condition-number constants. Finally, we emphasize that the goal of this paper is to offer a new perspective and a methodological framework for understanding the convergence of Q-learning. The proposed framework is not intended to replace existing analyses based on Bellman contractions or stochastic approximation, nor does it claim uniformly improved sample complexity across all problem instances. Rather, the direct-switching viewpoint complements existing analyses by identifying the intrinsic switched drift and by exposing when the direct JSR rate is sharper than comparison-based rates. 2 Preliminaries 2.1 Notation The set of real numbers is denoted by \mathbb{R} ; \mathbb{R}^{m} is the m -dimensional Euclidean space; and \mathbb{R}^{m\times r} is the set of all m\times r real matrices. For a matrix A , A^{\top} denotes its transpose. For symmetric matrices, A\succ 0 and A\succeq 0 denote positive definiteness and positive semidefiniteness, and A\preceq B means B-A\succeq 0 . The identity matrix is denoted by I . For vectors, e_{i} is the i th standard basis vector, with dimension clear from context, and \otimes denotes the Kronecker product. The quantities \lambda_{\min}(A) and \lambda_{\max}(A) denote the minimum and maximum eigenvalues of a symmetric matrix A , respectively. For a finite set \mathcal{S} , |\mathcal{S}| denotes its cardinality. We write \Delta_{m}:=\left\{q\in\mathbb{R}^{m}:q_{i}\geq 0,\ \sum_{i=1}^{m}q_{i}=1\right\} for the probability simplex in \mathbb{R}^{m} . For a finite matrix family \mathcal{H}=\{A_{1},\ldots,A_{N}\} , the notation \co(\mathcal{H}) denotes the convex hull \co(\mathcal{H}):=\left\{\sum_{i=1}^{N}\lambda_{i}A_{i}:\lambda_{i}\geq 0,\ \sum_{i=1}^{N}\lambda_{i}=1\right\} . 2.2 Switching System Let us consider the discrete-time stochastic switched affine system [ 17 , 19 , 23 ] x_{k+1}=A_{\sigma_{k}}x_{k}+b_{\sigma_{k}}+\xi_{k}, where \sigma_{k}\in\{1,2,\ldots,M\} is a switching signal, A_{\sigma_{k}} is selected from a prescribed family of matrices {\cal H}:=\{A_{1},A_{2},\ldots,A_{M}\} , which is called a switching family, b_{\sigma_{k}} is a mode-dependent affine term, and \xi_{k} is a disturbance or martingale noise. When b_{\sigma_{k}}=0 , the deterministic part reduces to a switched linear system, x_{k+1}=A_{\sigma_{k}}x_{k}. The worst-case exponential rate of the switched linear family is characterized by the joint spectral radius (JSR)