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

# Sign-Separated Finite-Time Error Analysis of Q-Learning
Source: [https://arxiv.org/html/2605.16103](https://arxiv.org/html/2605.16103)
Donghwan Lee Department of Electrical Engineering Korea Advanced Institute of Science and Technology \(KAIST\) Daejeon 34141, South Korea donghwan@kaist\.ac\.kr

###### 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\.

## 1Introduction

Q\-learning\[[30](https://arxiv.org/html/2605.16103#bib.bib22)\]is a foundational algorithm in reinforcement learning \(RL\)\[[23](https://arxiv.org/html/2605.16103#bib.bib2)\]for solving 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](https://arxiv.org/html/2605.16103#bib.bib24),[7](https://arxiv.org/html/2605.16103#bib.bib25),[4](https://arxiv.org/html/2605.16103#bib.bib26),[11](https://arxiv.org/html/2605.16103#bib.bib37)\]\. These results are fundamental, but asymptotic convergence alone does not quantify the finite\-time progress of the iterates toward the solution\. This limitation has motivated a growing body of finite\-time convergence analyses, which provide explicit bounds on the iterates’ approach to the optimal Q\-function\. Recent advances in finite\-time analysis include\[[24](https://arxiv.org/html/2605.16103#bib.bib29),[9](https://arxiv.org/html/2605.16103#bib.bib27),[6](https://arxiv.org/html/2605.16103#bib.bib28),[1](https://arxiv.org/html/2605.16103#bib.bib30),[29](https://arxiv.org/html/2605.16103#bib.bib31),[20](https://arxiv.org/html/2605.16103#bib.bib32),[15](https://arxiv.org/html/2605.16103#bib.bib33),[5](https://arxiv.org/html/2605.16103#bib.bib34)\]\. Most existing results view Q\-learning as a nonlinear stochastic approximation scheme\[[10](https://arxiv.org/html/2605.16103#bib.bib8)\]and rely on the contraction property of the Bellman optimality operator\.

An alternative viewpoint treats Q\-learning as a discrete\-time stochastic switching system\[[18](https://arxiv.org/html/2605.16103#bib.bib11),[16](https://arxiv.org/html/2605.16103#bib.bib13)\]\. This perspective was developed in\[[11](https://arxiv.org/html/2605.16103#bib.bib37),[12](https://arxiv.org/html/2605.16103#bib.bib38),[13](https://arxiv.org/html/2605.16103#bib.bib39),[17](https://arxiv.org/html/2605.16103#bib.bib41)\]and was used to prove finite\-time bounds 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 affine term is controlled through upper and lower comparison systems\. The upper comparison system remains a switching system, whereas the lower comparison system can be restricted to optimal\-policy modes\. Although this comparison\-system approach gives valid finite\-time bounds, it controls the Q\-learning error through auxiliary systems rather than directly exploiting the switching structure of the original error recursion\. As a result, intrinsic switching\-system quantities such as the joint spectral radius \(JSR\)\[[26](https://arxiv.org/html/2605.16103#bib.bib18),[21](https://arxiv.org/html/2605.16103#bib.bib17),[3](https://arxiv.org/html/2605.16103#bib.bib19),[8](https://arxiv.org/html/2605.16103#bib.bib16)\]are difficult to apply directly to the original Q\-learning dynamics\.

The exact switching\-system representation removes this obstacle by representing the Bellman maximization error exactly as an average of action\-wise Q\-errors under a suitably chosen stochastic policy\[[14](https://arxiv.org/html/2605.16103#bib.bib52)\]\. The corresponding deterministic convergence rate can then be characterized by the JSR of the resulting direct switching family\. Because the JSR is the exact worst\-case exponential rate of a switched linear family, the direct switching viewpoint provides a sharp drift\-based framework for understanding transient Q\-learning behavior\.

This paper refines that viewpoint in\[[14](https://arxiv.org/html/2605.16103#bib.bib52)\]by separating the Q\-learning error into its componentwise negative and positive parts\. The sign separation exposes an asymmetry induced by the Bellman max operator\. This asymmetry is closely related to the overestimation mechanism in value\-based RL\[[25](https://arxiv.org/html/2605.16103#bib.bib55),[28](https://arxiv.org/html/2605.16103#bib.bib56)\]: the maximum can select actions with positive estimation errors, whereas negative errors can be compared against an optimal\-policy lower system\. The negative side is compared with a fixed LTI system associated with an optimal policy, yielding a certificate with rateρ−⋆\\rho\_\{\-\}^\{\\star\}\. The positive side is controlled by a linear switching system over the set of deterministic policies, because suboptimal actions with large positive error can enter through the maximization\. Its certified rate isρ\+=ραdir\\rho\_\{\+\}=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\. Sinceρ−⋆≤ρ\+\\rho\_\{\-\}^\{\\star\}\\leq\\rho\_\{\+\}, and the inequality can be strict, the finite\-time bounds give a certificate\-level sense in which negative errors may decay faster than positive errors\. The resulting envelopes are illustrated in[Figure˜1](https://arxiv.org/html/2605.16103#S1.F1)\.

kkError0ek\+e\_\{k\}^\{\+\}−ek−\-e\_\{k\}^\{\-\}Figure 1:Schematic sign\-separated envelopes\. The positive component is certified by the full switching\-family rate, whereas the negative component is certified by an optimized fixed\-mode LTI rate\.We first develop the sign\-separated comparison systems for the deterministic conditional\-mean recursion, where the max\-induced residuals and the lower and upper comparison mechanisms are most transparent\. We then extend the same sign\-separated structure to constant\-step\-size stochastic Q\-learning under an i\.i\.d\. observation model\. The finite\-time rate certificates use two Lyapunov constructions: a fixed\-mode Lyapunov function for the negative\-side LTI comparison system and a product\-defined JSR Lyapunov function for the positive\-side direct switching family\.

The aim is to provide a switching\-system perspective on the convergence behavior of Q\-learning\. The framework is not meant to replace analyses based on Bellman contractions or stochastic approximation, nor does it assert uniformly improved sample complexity over all problem instances\. Instead, the sign\-separated direct\-switching viewpoint complements existing analyses by identifying the switched drift and by showing when the optimized negative\-side rate is sharper than the positive\-side direct switching rate\. The present paper focuses on the i\.i\.d\. observation model\. The method of\[[14](https://arxiv.org/html/2605.16103#bib.bib52)\]can be used to extend the analysis to Markovian observations, but the i\.i\.d\. setting keeps the sign\-separated switching\-system argument transparent\.

## 2Preliminaries

### 2\.1Notation

We use the following notation\. The symbolsℝ\{\\mathbb\{R\}\},ℝn\{\\mathbb\{R\}\}^\{n\}, andℝn×m\{\\mathbb\{R\}\}^\{n\\times m\}denote the set of real numbers, thenn\-dimensional Euclidean space, and the set ofn×mn\\times mreal matrices, respectively\. For a matrixAA,A⊤A^\{\\top\}denotes its transpose\. The identity matrix with appropriate dimensions is denoted byII\. For a finite set𝒮\\mathcal\{S\}, its cardinality is denoted by\|𝒮\|\|\\mathcal\{S\}\|\. The Kronecker product ofAAandBBis denoted byA⊗BA\\otimes B\. For a square matrixAA,ρ​\(A\)\\rho\(A\)denotes its spectral radius\.

For a set𝒴⊂ℝn\\mathcal\{Y\}\\subset\\mathbb\{R\}^\{n\}and a vectorx∈ℝnx\\in\\mathbb\{R\}^\{n\},dist∞⁡\(x,𝒴\)\\operatorname\{dist\}\_\{\\infty\}\(x,\\mathcal\{Y\}\)denotes the infinity\-norm distance fromxxto𝒴\\mathcal\{Y\}:dist∞⁡\(x,𝒴\):=infy∈𝒴‖x−y‖∞\\operatorname\{dist\}\_\{\\infty\}\(x,\\mathcal\{Y\}\):=\\inf\_\{y\\in\\mathcal\{Y\}\}\\\|x\-y\\\|\_\{\\infty\}\. We writeΔ\|𝒜\|\\Delta\_\{\|\{\\cal A\}\|\}for the probability simplex over a finite action set𝒜\{\\cal A\}:Δ\|𝒜\|:=\{p∈ℝ\|𝒜\|:pi≥0,∑i=1\|𝒜\|pi=1\}\\Delta\_\{\|\{\\cal A\}\|\}:=\\left\\\{p\\in\\mathbb\{R\}^\{\|\{\\cal A\}\|\}:\\ p\_\{i\}\\geq 0,\\ \\sum\_\{i=1\}^\{\{\|\{\\cal A\}\|\}\}p\_\{i\}=1\\right\\\}\. Throughout the paper,Arg​max\\operatorname\{Arg\\,max\}denotes the set\-valued maximizer, whilearg​max\\operatorname\{arg\\,max\}denotes a fixed tie\-broken single\-valued maximizer\.

All vector inequalities are understood componentwise unless otherwise stated\. For a scalarxx, define

x\+:=max⁡\{x,0\},x−:=max⁡\{−x,0\}\.x^\{\+\}:=\\max\\\{x,0\\\},\\qquad x^\{\-\}:=\\max\\\{\-x,0\\\}\.Thus,x\+x^\{\+\}is the positive part ofxx, whilex−x^\{\-\}is the magnitude of the negative part ofxx\. For a vectorxx,x\+x^\{\+\}andx−x^\{\-\}are defined componentwise, and therefore

x=x\+−x−,\|x\|=x\+\+x−,x\+≥0,x−≥0\.x=x^\{\+\}\-x^\{\-\},\\qquad\|x\|=x^\{\+\}\+x^\{\-\},\\qquad x^\{\+\}\\geq 0,\\qquad x^\{\-\}\\geq 0\.For a finite matrix familyℋ=\{A1,…,AN\}\\mathcal\{H\}=\\\{A\_\{1\},\\ldots,A\_\{N\}\\\}, the notationco⁡\(ℋ\)\\operatorname\{co\}\(\\mathcal\{H\}\)denotes the convex hullco⁡\(ℋ\):=\{∑i=1Nλi​Ai:λi≥0,∑i=1Nλi=1\}\\operatorname\{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\.2Switching Systems

Let us consider the discrete\-time switched linear system\[[16](https://arxiv.org/html/2605.16103#bib.bib13),[18](https://arxiv.org/html/2605.16103#bib.bib11),[22](https://arxiv.org/html/2605.16103#bib.bib12)\]

zk\+1=Aσk​zk\+ξk,k∈\{0,1,2,…\},z\_\{k\+1\}=A\_\{\\sigma\_\{k\}\}z\_\{k\}\+\\xi\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},where each indexi∈\{1,2,…,M\}i\\in\\\{1,2,\\ldots,M\\\}is called a mode and corresponds to one matrixAiA\_\{i\}\. The sequenceσk∈\{1,2,…,M\}\\sigma\_\{k\}\\in\\\{1,2,\\ldots,M\\\}is the switching signal; it specifies which mode is active at timekk\. Equivalently, saying that modeσk=i\\sigma\_\{k\}=iis active means that the update fromzkz\_\{k\}tozk\+1z\_\{k\+1\}uses the dynamics matrixAiA\_\{i\}\. The prescribed set of all possible mode matricesℋ:=\{A1,A2,…,AM\}\\mathcal\{H\}:=\\\{A\_\{1\},A\_\{2\},\\ldots,A\_\{M\}\\\}is called the switching family, andξk\\xi\_\{k\}is an additive disturbance\. In this paper, a mode denotes the currently applied dynamics matrix; in the Q\-learning applications below, modes are induced by policy selectors\. Whenξk=0\\xi\_\{k\}=0, the deterministic part reduces to

zk\+1=Aσk​zk,k∈\{0,1,2,…\}\.z\_\{k\+1\}=A\_\{\\sigma\_\{k\}\}z\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.If the switching family has a single element, sayℋ=\{H\}\\mathcal\{H\}=\\\{H\\\}, then there is no genuine mode variation and the switched system reduces to the usual linear time\-invariant \(LTI\) recursion

zk\+1=H​zk\+ξk,z\_\{k\+1\}=Hz\_\{k\}\+\\xi\_\{k\},or, in the disturbance\-free case,zk\+1=H​zkz\_\{k\+1\}=Hz\_\{k\}\. Thus, LTI systems are included as the singleton\-family special case of switching systems\. The worst\-case exponential rate of a switched linear family is characterized by the joint spectral radius \(JSR\)\[[26](https://arxiv.org/html/2605.16103#bib.bib18),[21](https://arxiv.org/html/2605.16103#bib.bib17),[3](https://arxiv.org/html/2605.16103#bib.bib19),[8](https://arxiv.org/html/2605.16103#bib.bib16)\], defined as follows\.

###### Definition 1\.

For a bounded set of matricesℋ⊂ℝm×m\\mathcal\{H\}\\subset\\mathbb\{R\}^\{m\\times m\}, its JSR is denoted by

ρ​\(ℋ\):=limk→∞supA1,…,Ak∈ℋ‖Ak​⋯​A1‖1/k,\\rho\(\\mathcal\{H\}\):=\\lim\_\{k\\to\\infty\}\\sup\_\{A\_\{1\},\\ldots,A\_\{k\}\\in\\mathcal\{H\}\}\\\|A\_\{k\}\\cdots A\_\{1\}\\\|^\{1/k\},where the value is independent of the chosen submultiplicative norm\. Whenℋ\\mathcal\{H\}is finite, the supremum for each fixed product length is a maximum over all products generated by matrices inℋ\\mathcal\{H\}\. Ifℋ=\{H\}\\mathcal\{H\}=\\\{H\\\}consists of a single matrix, then this definition reduces to the usual spectral radius:

ρ​\(\{H\}\)=limk→∞‖Hk‖1/k=ρ​\(H\)\.\\rho\(\\\{H\\\}\)=\\lim\_\{k\\to\\infty\}\\\|H^\{k\}\\\|^\{1/k\}=\\rho\(H\)\.

### 2\.3Markov Decision Processes

We consider an infinite\-horizon discounted Markov decision process \(MDP\)\[[19](https://arxiv.org/html/2605.16103#bib.bib1)\], in which an agent sequentially chooses actions to maximize cumulative discounted rewards\. The state and action spaces are finite and are denoted by𝒮:=\{1,2,…,\|𝒮\|\}\{\\cal S\}:=\\\{1,2,\\ldots,\|\{\\cal S\}\|\\\}and𝒜:=\{1,2,…,\|𝒜\|\}\{\\cal A\}:=\\\{1,2,\\ldots,\|\{\\cal A\}\|\\\}, respectively\. At states∈𝒮s\\in\{\\cal S\}, the decision maker selects an actiona∈𝒜a\\in\{\\cal A\}\. The next states′s^\{\\prime\}is drawn according toP​\(s′\|s,a\)P\(s^\{\\prime\}\|s,a\), and the transition incurs rewardr​\(s,a,s′\)r\(s,a,s^\{\\prime\}\), wherer:𝒮×𝒜×𝒮→ℝr:\{\\cal S\}\\times\{\\cal A\}\\times\{\\cal S\}\\to\{\\mathbb\{R\}\}\. We writer\(sk,ak,sk\+1\)=:rk\+1r\(s\_\{k\},a\_\{k\},s\_\{k\+1\}\)=:r\_\{k\+1\}fork≥0k\\geq 0\. The expected one\-step reward is

R​\(s,a\):=𝔼​\[rk\+1∣sk=s,ak=a\]=∑s′∈𝒮P​\(s′\|s,a\)​r​\(s,a,s′\)\.R\(s,a\):=\{\\mathbb\{E\}\}\[r\_\{k\+1\}\\mid s\_\{k\}=s,a\_\{k\}=a\]=\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}P\(s^\{\\prime\}\|s,a\)r\(s,a,s^\{\\prime\}\)\.A deterministic policyπ:𝒮→𝒜\\pi:\{\\cal S\}\\to\{\\cal A\}maps each statessto an actionπ​\(s\)\\pi\(s\)\. Throughout the paper, the discount factor satisfiesγ∈\(0,1\)\\gamma\\in\(0,1\)\. LetΘ\\Thetadenote the set of all admissible deterministic policies\. For a policyπ\\pi, the Q\-function underπ\\piis defined as

Qπ​\(s,a\)=𝔼​\[∑k=0∞γk​rk\+1\|s0=s,a0=a,π\],Q^\{\\pi\}\(s,a\)=\{\\mathbb\{E\}\}\\left\[\\left\.\\sum\_\{k=0\}^\{\\infty\}\{\\gamma^\{k\}r\_\{k\+1\}\}\\right\|s\_\{0\}=s,a\_\{0\}=a,\\pi\\right\],for alls∈𝒮s\\in\{\\cal S\}anda∈𝒜a\\in\{\\cal A\}\. The corresponding value function isVπ​\(s\):=Qπ​\(s,π​\(s\)\)V^\{\\pi\}\(s\):=Q^\{\\pi\}\(s,\\pi\(s\)\)\. The optimal Q\-function is

Q∗​\(s,a\):=supπ∈ΘQπ​\(s,a\),s∈𝒮,a∈𝒜\.Q^\{\*\}\(s,a\):=\\sup\_\{\\pi\\in\\Theta\}Q^\{\\pi\}\(s,a\),\\qquad s\\in\{\\cal S\},\\ a\\in\{\\cal A\}\.A deterministic policyπ∗\\pi^\{\*\}is optimal ifQπ∗​\(s,a\)=Q∗​\(s,a\)Q^\{\\pi^\{\*\}\}\(s,a\)=Q^\{\*\}\(s,a\)for all\(s,a\)∈𝒮×𝒜\(s,a\)\\in\{\\cal S\}\\times\{\\cal A\}\. OnceQ∗Q^\{\*\}is known, an optimal tie\-broken greedy policy can be recovered asπ∗​\(s\)=arg​maxa∈𝒜⁡Q∗​\(s,a\)\\pi^\{\*\}\(s\)=\\operatorname\{arg\\,max\}\_\{a\\in\{\\cal A\}\}Q^\{\*\}\(s,a\)\. The corresponding optimal value function is

V∗​\(s\):=maxa∈𝒜⁡Q∗​\(s,a\)\.V^\{\*\}\(s\):=\\max\_\{a\\in\{\\cal A\}\}Q^\{\*\}\(s,a\)\.For each states∈𝒮s\\in\{\\cal S\}, define the set of optimal greedy actions by

Φ∗​\(s\):=Arg​maxa∈𝒜⁡Q∗​\(s,a\)\.\\Phi^\{\*\}\(s\):=\\operatorname\{Arg\\,max\}\_\{a\\in\{\\cal A\}\}Q^\{\*\}\(s,a\)\.The set of all optimal deterministic policies is then

Θ∗:=\{π∈Θ:π​\(s\)∈Φ∗​\(s\),∀s∈𝒮\}\.\\Theta^\{\*\}:=\\\{\\pi\\in\\Theta:\\ \\pi\(s\)\\in\\Phi^\{\*\}\(s\),\\ \\forall s\\in\{\\cal S\}\\\}\.The definition above is equivalent to the usual set of optimal deterministic policies in a finite discounted MDP\. Ifπ∈Θ∗\\pi\\in\\Theta^\{\*\}, thenV∗V^\{\*\}satisfies the Bellman evaluation equation forπ\\pi\. Uniqueness of the discounted evaluation fixed point givesVπ=V∗V^\{\\pi\}=V^\{\*\}, and henceQπ=Q∗Q^\{\\pi\}=Q^\{\*\}\. Conversely, ifπ\\piis optimal, thenVπ=V∗V^\{\\pi\}=V^\{\*\}, and the policy\-evaluation equation impliesV∗​\(s\)=Q∗​\(s,π​\(s\)\)V^\{\*\}\(s\)=Q^\{\*\}\(s,\\pi\(s\)\)for every state\. Thusπ​\(s\)∈Φ∗​\(s\)\\pi\(s\)\\in\\Phi^\{\*\}\(s\)for allss, soΘ∗\\Theta^\{\*\}is exactly the set of optimal deterministic policies\.

### 2\.4Definitions

In this paper, we consider a finite discounted Markov decision process \(MDP\)\[[19](https://arxiv.org/html/2605.16103#bib.bib1)\]with state\-space𝒮=\{1,…,\|𝒮\|\}\\mathcal\{S\}=\\\{1,\\ldots,\|\\mathcal\{S\}\|\\\}, action\-space𝒜=\{1,…,\|𝒜\|\}\\mathcal\{A\}=\\\{1,\\ldots,\|\\mathcal\{A\}\|\\\}, transition probabilityP​\(s′∣s,a\)P\(s^\{\\prime\}\\mid s,a\), real\-valued one\-step rewardr​\(s,a,s′\)r\(s,a,s^\{\\prime\}\), expected reward

R​\(s,a\):=∑s′∈𝒮P​\(s′∣s,a\)​r​\(s,a,s′\),R\(s,a\):=\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}P\(s^\{\\prime\}\\mid s,a\)r\(s,a,s^\{\\prime\}\),and discount factorγ∈\(0,1\)\\gamma\\in\(0,1\)\. State\-action functions are viewed as vectors inℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\}using the action\-block ordering

\(1,1\),\(2,1\),…,\(\|𝒮\|,1\),\(1,2\),\(2,2\),…,\(\|𝒮\|,\|𝒜\|\)\.\(1,1\),\(2,1\),\\ldots,\(\|\\mathcal\{S\}\|,1\),\(1,2\),\(2,2\),\\ldots,\(\|\\mathcal\{S\}\|,\|\\mathcal\{A\}\|\)\.All matrices and vectors indexed by state\-action pairs use this ordering\. ForQ∈ℝ\|𝒮\|​\|𝒜\|Q\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\},

Q=\[Q​\(⋅,1\)⋮Q​\(⋅,\|𝒜\|\)\],Q​\(s,a\)=\(ea⊗es\)⊤​Q,Q=\\begin\{bmatrix\}Q\(\\cdot,1\)\\\\ \\vdots\\\\ Q\(\\cdot,\|\\mathcal\{A\}\|\)\\end\{bmatrix\},\\qquad Q\(s,a\)=\(e\_\{a\}\\otimes e\_\{s\}\)^\{\\top\}Q,wherees∈ℝ\|𝒮\|e\_\{s\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\}andea∈ℝ\|𝒜\|e\_\{a\}\\in\\mathbb\{R\}^\{\|\\mathcal\{A\}\|\}are the standard basis vectors\. Let us define the matrix

P:=\[P1⋮P\|𝒜\|\]∈ℝ\|𝒮\|​\|𝒜\|×\|𝒮\|,R:=\[R​\(⋅,1\)⋮R​\(⋅,\|𝒜\|\)\]∈ℝ\|𝒮\|​\|𝒜\|,P:=\\begin\{bmatrix\}P\_\{1\}\\\\ \\vdots\\\\ P\_\{\|\\mathcal\{A\}\|\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\\times\|\\mathcal\{S\}\|\},\\qquad R:=\\begin\{bmatrix\}R\(\\cdot,1\)\\\\ \\vdots\\\\ R\(\\cdot,\|\\mathcal\{A\}\|\)\\end\{bmatrix\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\},wherePa=P\(⋅∣⋅,a\)∈ℝ\|𝒮\|×\|𝒮\|P\_\{a\}=P\(\\cdot\\mid\\cdot,a\)\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\times\|\\mathcal\{S\}\|\}\. For the finite MDP above, let us define

Rmax:=max\(s,a,s′\)∈𝒮×𝒜×𝒮⁡\|r​\(s,a,s′\)\|\.R\_\{\\max\}:=\\max\_\{\(s,a,s^\{\\prime\}\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\times\\mathcal\{S\}\}\|r\(s,a,s^\{\\prime\}\)\|\.Because the state and action spaces are finite and rewards are real\-valued,Rmax<∞R\_\{\\max\}<\\infty\.

LetΘ\\Thetadenote the set of deterministic stationary policiesπ:𝒮→𝒜\\pi:\\mathcal\{S\}\\to\\mathcal\{A\}\. For any stochastic policyμ:𝒮→Δ\|𝒜\|\\mu:\\mathcal\{S\}\\to\\Delta\_\{\|\\mathcal\{A\}\|\}, we define

𝚷μ:=\[μ​\(1\)⊤⊗e1⊤μ​\(2\)⊤⊗e2⊤⋮μ​\(\|𝒮\|\)⊤⊗e\|𝒮\|⊤\]∈ℝ\|𝒮\|×\|𝒮\|​\|𝒜\|\.\\boldsymbol\{\\Pi\}^\{\\mu\}:=\\begin\{bmatrix\}\\mu\(1\)^\{\\top\}\\otimes e\_\{1\}^\{\\top\}\\\\ \\mu\(2\)^\{\\top\}\\otimes e\_\{2\}^\{\\top\}\\\\ \\vdots\\\\ \\mu\(\|\\mathcal\{S\}\|\)^\{\\top\}\\otimes e\_\{\|\\mathcal\{S\}\|\}^\{\\top\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\times\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\}\.For a deterministic policyπ∈Θ\\pi\\in\\Theta, we use the same notation𝚷π\\boldsymbol\{\\Pi\}^\{\\pi\}by identifyingπ​\(s\)\\pi\(s\)with its one\-hot encoding\. ThenP​𝚷μ∈ℝ\|𝒮\|​\|𝒜\|×\|𝒮\|​\|𝒜\|P\\boldsymbol\{\\Pi\}^\{\\mu\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\\times\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\}is the transition matrix of the state\-action pair induced byμ\\mu\. ForQ∈ℝ\|𝒮\|​\|𝒜\|Q\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\}, define

VQ​\(s\):=maxa∈𝒜⁡Q​\(s,a\),VQ:=\(VQ​\(1\),…,VQ​\(\|𝒮\|\)\)⊤\.V\_\{Q\}\(s\):=\\max\_\{a\\in\\mathcal\{A\}\}Q\(s,a\),\\qquad V\_\{Q\}:=\(V\_\{Q\}\(1\),\\ldots,V\_\{Q\}\(\|\\mathcal\{S\}\|\)\)^\{\\top\}\.The Bellman optimality operator is written as

F​\(Q\):=R\+γ​P​VQ\.F\(Q\):=R\+\\gamma PV\_\{Q\}\.With this notation,Q∗Q^\{\*\}is the unique fixed point ofFF, andV∗=VQ∗V^\{\*\}=V\_\{Q^\{\*\}\}\. For anyQ∈ℝ\|𝒮\|​\|𝒜\|Q\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\}, letπQ​\(s\):=arg​maxa∈𝒜⁡Q​\(s,a\)\\pi\_\{Q\}\(s\):=\\operatorname\{arg\\,max\}\_\{a\\in\\mathcal\{A\}\}Q\(s,a\)denote the tie\-broken greedy policy with respect toQQ\. We also use the shorthand

𝚷Q:=𝚷πQ\.\\boldsymbol\{\\Pi\}\_\{Q\}:=\\boldsymbol\{\\Pi\}^\{\\pi\_\{Q\}\}\.The advantage function at statessand actionaais

A∗​\(s,a\):=V∗​\(s\)−Q∗​\(s,a\)≥0\.A^\{\*\}\(s,a\):=V^\{\*\}\(s\)\-Q^\{\*\}\(s,a\)\\geq 0\.Consequently,

A∗​\(s,a\)=0⟺a∈Φ∗​\(s\)\.A^\{\*\}\(s,a\)=0\\quad\\Longleftrightarrow\\quad a\\in\\Phi^\{\*\}\(s\)\.

### 2\.5Q\-Learning

We consider the standard asynchronous Q\-learning recursion\[[23](https://arxiv.org/html/2605.16103#bib.bib2),[2](https://arxiv.org/html/2605.16103#bib.bib3)\]with a constant step\-sizeα\\alphaunder an i\.i\.d\. observation model\. At stepkk, a state\-action pair\(sk,ak\)\(s\_\{k\},a\_\{k\}\)is sampled independently acrosskkaccording to

ℙ​\(sk=s,ak=a\)=d​\(s,a\):=p​\(s\)​b​\(a∣s\),\(s,a\)∈𝒮×𝒜,\\mathbb\{P\}\(s\_\{k\}=s,a\_\{k\}=a\)=d\(s,a\):=p\(s\)b\(a\\mid s\),\\qquad\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\},whereppis a state\-sampling distribution andbbis a behavior policy\. Thensk′∼P\(⋅∣sk,ak\)s^\{\\prime\}\_\{k\}\\sim P\(\\cdot\\mid s\_\{k\},a\_\{k\}\)is sampled independently conditional on\(sk,ak\)\(s\_\{k\},a\_\{k\}\), and the reward sample is taken as

rk\+1:=r​\(sk,ak,sk′\),k∈\{0,1,2,…\}\.r\_\{k\+1\}:=r\(s\_\{k\},a\_\{k\},s^\{\\prime\}\_\{k\}\),\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.The asynchronous Q\-learning update is

Qk\+1​\(sk,ak\)=Qk​\(sk,ak\)\+α​\(rk\+1\+γ​maxu∈𝒜⁡Qk​\(sk′,u\)−Qk​\(sk,ak\)\),k∈\{0,1,2,…\},Q\_\{k\+1\}\(s\_\{k\},a\_\{k\}\)=Q\_\{k\}\(s\_\{k\},a\_\{k\}\)\+\\alpha\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}Q\_\{k\}\(s^\{\\prime\}\_\{k\},u\)\-Q\_\{k\}\(s\_\{k\},a\_\{k\}\)\\right\),\\qquad k\\in\\\{0,1,2,\\ldots\\\},All other coordinates\(s,a\)​e​\(sk,ak\)\(s,a\)e\(s\_\{k\},a\_\{k\}\)remain unchanged:

Qk\+1​\(s,a\)=Qk​\(s,a\),\(s,a\)≠\(sk,ak\),k∈\{0,1,2,…\}\.Q\_\{k\+1\}\(s,a\)=Q\_\{k\}\(s,a\),\\qquad\(s,a\)\\neq\(s\_\{k\},a\_\{k\}\),\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Let\{ℱk\}k≥0\\\{\\mathcal\{F\}\_\{k\}\\\}\_\{k\\geq 0\}be the natural filtration of this Q\-learning process,

ℱ0:=σ​\(Q0\),ℱk:=σ​\(Q0,\{\(st,at,st′,rt\+1\):0≤t≤k−1\}\),k≥1\.\\mathcal\{F\}\_\{0\}:=\\sigma\(Q\_\{0\}\),\\qquad\\mathcal\{F\}\_\{k\}:=\\sigma\\\!\\left\(Q\_\{0\},\\\{\(s\_\{t\},a\_\{t\},s^\{\\prime\}\_\{t\},r\_\{t\+1\}\):0\\leq t\\leq k\-1\\\}\\right\),\\quad k\\geq 1\.ThenQkQ\_\{k\}isℱk\\mathcal\{F\}\_\{k\}\-measurable\. Moreover, the fresh observation\(sk,ak,sk′,rk\+1\)\(s\_\{k\},a\_\{k\},s^\{\\prime\}\_\{k\},r\_\{k\+1\}\)is independent ofℱk\\mathcal\{F\}\_\{k\}and is revealed between timeskkandk\+1k\+1\.

Let

D:=diag\(d\(s,a\)\)\(s,a\)∈𝒮×𝒜∈ℝ\(\|𝒮\|​\|𝒜\|\)×\(\|𝒮\|​\|𝒜\|\)\.D:=\\operatorname\{diag\}\(d\(s,a\)\)\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\in\\mathbb\{R\}^\{\(\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\)\\times\(\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\)\}\.Writees,ae\_\{s,a\}for the standard basis vector corresponding to coordinate\(s,a\)\(s,a\), equivalentlyea⊗ese\_\{a\}\\otimes e\_\{s\}under the chosen Kronecker ordering\. For the sampled coordinate, define the random vector

ζk:=esk,ak​\(rk\+1\+γ​maxu∈𝒜⁡Qk​\(sk′,u\)−Qk​\(sk,ak\)\)\.\\zeta\_\{k\}:=e\_\{s\_\{k\},a\_\{k\}\}\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}Q\_\{k\}\(s^\{\\prime\}\_\{k\},u\)\-Q\_\{k\}\(s\_\{k\},a\_\{k\}\)\\right\)\.SinceQkQ\_\{k\}isℱk\\mathcal\{F\}\_\{k\}\-measurable and the observation at timekkis independent ofℱk\\mathcal\{F\}\_\{k\},

𝔼​\[ζk∣ℱk\]=D​\(F​\(Qk\)−Qk\)\.\\mathbb\{E\}\[\\zeta\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=D\(F\(Q\_\{k\}\)\-Q\_\{k\}\)\.Accordingly, the martingale\-difference noise is

wk:=esk,ak​\(rk\+1\+γ​maxu∈𝒜⁡Qk​\(sk′,u\)−Qk​\(sk,ak\)\)−D​\(F​\(Qk\)−Qk\)\.w\_\{k\}:=e\_\{s\_\{k\},a\_\{k\}\}\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}Q\_\{k\}\(s^\{\\prime\}\_\{k\},u\)\-Q\_\{k\}\(s\_\{k\},a\_\{k\}\)\\right\)\-D\(F\(Q\_\{k\}\)\-Q\_\{k\}\)\.\(1\)Therefore, the vector form of Q\-learning is

Qk\+1=Qk\+α​\{D​\(F​\(Qk\)−Qk\)\+wk\},k∈\{0,1,2,…\},Q\_\{k\+1\}=Q\_\{k\}\+\\alpha\\\{D\(F\(Q\_\{k\}\)\-Q\_\{k\}\)\+w\_\{k\}\\\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},wherewkw\_\{k\}is defined in[Equation˜1](https://arxiv.org/html/2605.16103#S2.E1)\. With

ek:=Qk−Q∗,e\_\{k\}:=Q\_\{k\}\-Q^\{\*\},the Q\-learning error recursion is

ek\+1=ek\+α​D​\{γ​P​\(VQk−V∗\)−ek\}\+α​wk,k∈\{0,1,2,…\}\.e\_\{k\+1\}=e\_\{k\}\+\\alpha D\\\{\\gamma P\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\-e\_\{k\}\\\}\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.
###### Assumption 1\.

The following standing conditions hold throughout the paper\.

1. \(i\)d​\(s,a\)\>0d\(s,a\)\>0for every\(s,a\)∈𝒮×𝒜\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\.
2. \(ii\)The step size satisfiesα∈\(0,1\)\\alpha\\in\(0,1\)\.
3. \(iii\)The initial Q\-tableQ0∈ℝ\|𝒮\|​\|𝒜\|Q\_\{0\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}is deterministic\.

For the stochastic finite\-time analysis, define the uniform noise constant using the reward boundRmaxR\_\{\\max\}from[Section˜2\.4](https://arxiv.org/html/2605.16103#S2.SS4):

Wmax:=\(1\+\|𝒮\|​\|𝒜\|\)2​\(Rmax\+\(1\+γ\)​max⁡\{‖Q0‖∞,Rmax1−γ\}\)2\.W\_\{\\max\}:=\\left\(1\+\\sqrt\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\\right\)^\{2\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\\right\)^\{2\}\.\(2\)The conditional moment estimates forwkw\_\{k\},wk−w\_\{k\}^\{\-\}, andwk\+w\_\{k\}^\{\+\}are proved in[AppendixC\.1](https://arxiv.org/html/2605.16103#A3.SS1)from bounded rewards, the boundedness of the iterates, and the i\.i\.d\. observation model\. The processeswk−w\_\{k\}^\{\-\}andwk\+w\_\{k\}^\{\+\}need not be martingale differences; the finite\-time bounds below use only the fact that their conditional second moments are bounded byWmaxW\_\{\\max\}\.

## 3Deterministic Q\-Learning

Before the stochastic Q\-learning analysis, we study the corresponding noise\-free deterministic analysis\. The deterministic recursion is the conditional\-mean counterpart of the asynchronous stochastic Q\-learning update:

Qk\+1=Qk\+α​D​\(F​\(Qk\)−Qk\),k∈\{0,1,2,…\}\.Q\_\{k\+1\}=Q\_\{k\}\+\\alpha D\(F\(Q\_\{k\}\)\-Q\_\{k\}\),\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Withek:=Qk−Q∗e\_\{k\}:=Q\_\{k\}\-Q^\{\*\}, we have

ek\+1=ek\+α​D​\{γ​P​\(VQk−V∗\)−ek\},k∈\{0,1,2,…\}\.e\_\{k\+1\}=e\_\{k\}\+\\alpha D\\\{\\gamma P\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\-e\_\{k\}\\\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.\(3\)SinceVQk=𝚷Qk​QkV\_\{Q\_\{k\}\}=\\boldsymbol\{\\Pi\}\_\{Q\_\{k\}\}Q\_\{k\}, the deterministic recursion also has the affine switching\-system representation\[[11](https://arxiv.org/html/2605.16103#bib.bib37),[12](https://arxiv.org/html/2605.16103#bib.bib38),[13](https://arxiv.org/html/2605.16103#bib.bib39)\]

Qk\+1=𝐀πQk​Qk\+α​D​R,k∈\{0,1,2,…\},Q\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{Q\_\{k\}\}\}Q\_\{k\}\+\\alpha DR,\\qquad k\\in\\\{0,1,2,\\ldots\\\},where, for each deterministic policyπ∈Θ\\pi\\in\\Theta,

𝐀π:=I−α​D\+α​γ​D​P​𝚷π\.\\mathbf\{A\}\_\{\\pi\}:=I\-\\alpha D\+\\alpha\\gamma DP\\boldsymbol\{\\Pi\}^\{\\pi\}\.Equivalently, in error coordinates, the error recursion can be written as

ek\+1=𝐀πQk​ek−α​γ​D​P​\(V∗−𝚷πQk​Q∗\),k∈\{0,1,2,…\}\.e\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{Q\_\{k\}\}\}e\_\{k\}\-\\alpha\\gamma DP\\bigl\(V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{Q\_\{k\}\}\}Q^\{\*\}\\bigr\),\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Thus, deterministic Q\-learning is an affine discrete\-time switching system whose mode is selected by the greedy policy induced by the current iterate\[[13](https://arxiv.org/html/2605.16103#bib.bib39),[12](https://arxiv.org/html/2605.16103#bib.bib38),[11](https://arxiv.org/html/2605.16103#bib.bib37)\]\. The affine offset can also be removed exactly by the stochastic\-policy linearization of the Bellman maximization error as in\[[14](https://arxiv.org/html/2605.16103#bib.bib52)\]\.

###### Lemma 1\.

Along every trajectory of the deterministic recursion, there exists a sequence of stochastic policies\{μk\}k≥0\\\{\\mu\_\{k\}\\\}\_\{k\\geq 0\}such that the deterministic error recursion can be written exactly as the linear switching system

ek\+1=𝐀μk​ek,𝐀μk:=I−α​D\+α​γ​D​P​𝚷μk,k∈\{0,1,2,…\}\.e\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}e\_\{k\},\\qquad\\mathbf\{A\}\_\{\\mu\_\{k\}\}:=I\-\\alpha D\+\\alpha\\gamma DP\\boldsymbol\{\\Pi\}^\{\\mu\_\{k\}\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Moreover, each𝐀μk\\mathbf\{A\}\_\{\\mu\_\{k\}\}belongs toco⁡\(ℳα\)\\operatorname\{co\}\(\\mathcal\{M\}\_\{\\alpha\}\)\.

The corresponding switching family is

ℳα:=\{𝐀π:π∈Θ\}\.\\mathcal\{M\}\_\{\\alpha\}:=\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta\\\}\.The corresponding JSR is

ραdir:=ρ​\(ℳα\)\.\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}:=\\rho\(\\mathcal\{M\}\_\{\\alpha\}\)\.
### 3\.1Lower and Upper Comparison Systems

We first recall the lower and upper comparison\-system framework of\[[13](https://arxiv.org/html/2605.16103#bib.bib39),[12](https://arxiv.org/html/2605.16103#bib.bib38),[11](https://arxiv.org/html/2605.16103#bib.bib37)\]\. The detailed Bellman\-max expansion and residual\-sign derivation are given in[AppendixC\.2](https://arxiv.org/html/2605.16103#A3.SS2)\. We record only the comparison systems and the resulting order statement\.

For the lower comparison, choose a single optimal policy whose associated LTI subsystem has the smallest spectral radius:

π−⋆∈arg​minπ∈Θ∗⁡ρ​\(𝐀π\)\.\\pi\_\{\-\}^\{\\star\}\\in\\operatorname\{arg\\,min\}\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\)\.The minimizer exists becauseΘ∗\\Theta^\{\*\}is finite\. Define

𝐀−⋆:=𝐀π−⋆,ρ−⋆:=ρ​\(𝐀−⋆\)=minπ∈Θ∗⁡ρ​\(𝐀π\)\.\\mathbf\{A\}\_\{\-\}^\{\\star\}:=\\mathbf\{A\}\_\{\\pi\_\{\-\}^\{\\star\}\},\\qquad\\rho\_\{\-\}^\{\\star\}:=\\rho\(\\mathbf\{A\}\_\{\-\}^\{\\star\}\)=\\min\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\)\.Then, the lower comparison system is

ℓk\+1=𝐀−⋆​ℓk,ℓ0=e0,k∈\{0,1,2,…\}\.\\ell\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}\\ell\_\{k\},\\qquad\\ell\_\{0\}=e\_\{0\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.\(4\)It corresponds to dropping a nonnegative Bellman\-max residual from the exact error identity relative to the fixed optimal policyπ−⋆\\pi\_\{\-\}^\{\\star\}\.

For the upper comparison system, let us define the state\-wise maximizer of the current error

πk\+​\(s\)∈arg​maxa∈𝒜⁡ek​\(s,a\),s∈𝒮\.\\pi\_\{k\}^\{\+\}\(s\)\\in\\operatorname\{arg\\,max\}\_\{a\\in\\mathcal\{A\}\}e\_\{k\}\(s,a\),\\qquad s\\in\\mathcal\{S\}\.Then, the upper comparison system is

uk\+1=𝐀πk\+​uk,u0=e0,k∈\{0,1,2,…\}\.u\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}u\_\{k\},\\qquad u\_\{0\}=e\_\{0\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.\(5\)It corresponds to dropping a nonnegative residual in the opposite direction, where the active mode is selected by the largest state\-wise error component\. Thus,[Equation˜4](https://arxiv.org/html/2605.16103#S3.E4)is a fixed\-mode LTI comparison, whereas[Equation˜5](https://arxiv.org/html/2605.16103#S3.E5)is a linear switching comparison driven byπk\+\\pi\_\{k\}^\{\+\}\.

###### Lemma 2\.

Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), withℓk\\ell\_\{k\}anduku\_\{k\}defined in[Equations˜4](https://arxiv.org/html/2605.16103#S3.E4)and[5](https://arxiv.org/html/2605.16103#S3.E5), we have

ℓk≤ek≤uk,k∈\{0,1,2,…\}\.\\ell\_\{k\}\\leq e\_\{k\}\\leq u\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.

###### Proof\.

The proof is provided in[AppendixC\.2](https://arxiv.org/html/2605.16103#A3.SS2)\. ∎

### 3\.2Sign Comparison Systems

The sign comparison systems below follow from the same residual signs\. Writeek=ek\+−ek−e\_\{k\}=e\_\{k\}^\{\+\}\-e\_\{k\}^\{\-\}\. The lower residual identity gives

ek\+1=𝐀−⋆​ek\+−𝐀−⋆​ek−\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\),e\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\+\}\-\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\),where the last term is nonnegative\. Indeed,𝐀−⋆​ek\+\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\+\}and the residual term are nonnegative, and𝐀−⋆​ek−≥0\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\\geq 0\. It follows that each coordinate ofek\+1e\_\{k\+1\}has the formai−bia\_\{i\}\-b\_\{i\}, withai≥0a\_\{i\}\\geq 0andbi=\(𝐀−⋆​ek−\)i≥0b\_\{i\}=\(\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\)\_\{i\}\\geq 0\. Since\(ai−bi\)−≤bi\(a\_\{i\}\-b\_\{i\}\)^\{\-\}\\leq b\_\{i\}, we obtain

ek\+1−≤𝐀−⋆​ek−\.e\_\{k\+1\}^\{\-\}\\leq\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\.Similarly, the upper residual identity gives

ek\+1=𝐀πk\+​ek\+−𝐀πk\+​ek−−α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\),e\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\-\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\-\}\-\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\),where the subtracted residual is nonnegative\. Therefore, we similarly obtain

ek\+1\+≤𝐀πk\+​ek\+\.e\_\{k\+1\}^\{\+\}\\leq\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\.These inequalities lead to the following comparison systems for the negative and positive parts\. The detailed one\-step proof is included in[AppendixC\.2](https://arxiv.org/html/2605.16103#A3.SS2)\.

###### Lemma 3\.

Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), define

zk\+1−=𝐀−⋆​zk−,z0−=e0−,k∈\{0,1,2,…\},z^\{\-\}\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}z^\{\-\}\_\{k\},\\qquad z^\{\-\}\_\{0\}=e\_\{0\}^\{\-\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},\(6\)and

zk\+1\+=𝐀πk\+​zk\+,z0\+=e0\+,k∈\{0,1,2,…\}\.z^\{\+\}\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}z^\{\+\}\_\{k\},\\qquad z^\{\+\}\_\{0\}=e\_\{0\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.\(7\)Then

ek−≤zk−,ek\+≤zk\+,k∈\{0,1,2,…\}\.e\_\{k\}^\{\-\}\\leq z^\{\-\}\_\{k\},\\qquad e\_\{k\}^\{\+\}\\leq z^\{\+\}\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.

###### Proof\.

The proof is provided in[AppendixC\.2](https://arxiv.org/html/2605.16103#A3.SS2)\. ∎

The formal deterministic comparison lemmas and their proofs are given in[AppendixC\.2](https://arxiv.org/html/2605.16103#A3.SS2)\. These sign\-separated recursions are the finite\-time objects used below: the negative part evolves under fixed\-mode LTI dynamics, whereas the positive part is propagated by switching\-system dynamics\.

The positive\-side comparison uses the full switching family

ℳα\+:=\{𝐀π:π∈Θ\}=ℳα,\\mathcal\{M\}\_\{\\alpha\}^\{\+\}:=\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta\\\}=\\mathcal\{M\}\_\{\\alpha\},with

ρ\+:=ρ​\(ℳα\+\)=ραdir\.\\rho\_\{\+\}:=\\rho\(\\mathcal\{M\}\_\{\\alpha\}^\{\+\}\)=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\.For comparison with the optimized negative\-side LTI certificate, define the optimal\-policy switching family

ℳα−:=\{𝐀π:π∈Θ∗\},\\mathcal\{M\}\_\{\\alpha\}^\{\-\}:=\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta^\{\*\}\\\},with JSR

ρ−:=ρ​\(ℳα−\)\.\\rho\_\{\-\}:=\\rho\(\\mathcal\{M\}\_\{\\alpha\}^\{\-\}\)\.SinceΘ∗⊆Θ\\Theta^\{\*\}\\subseteq\\Theta, we have

ρ−⋆≤ρ−≤ρ\+\.\\rho\_\{\-\}^\{\\star\}\\leq\\rho\_\{\-\}\\leq\\rho\_\{\+\}\.Thus, the optimized negative\-side LTI certificate is no slower than the optimal\-policy switching certificate at the level of spectral\-radius certificates, and it can be strictly faster than the positive\-side direct switching certificate\.

### 3\.3Deterministic Finite\-Time Rates

We first apply the fixed\-mode Lyapunov construction to the negative comparison system\. Because this system is LTI, the resulting bound uses the spectral\-radius certificate of LTI systems\.

#### 3\.3\.1Construction of the negative\-side fixed\-mode Lyapunov function

The Lyapunov construction in this subsection is adapted from\[[14](https://arxiv.org/html/2605.16103#bib.bib52)\]\. Here it is specialized to the singleton family generated by the optimized negative\-side mode𝐀−⋆\\mathbf\{A\}\_\{\-\}^\{\\star\}\. We first state the properties of this construction that are used in the finite\-time argument\.

Fixε\>0\\varepsilon\>0such that

β−:=ρ−⋆\+ε∈\(0,1\)\.\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilon\\in\(0,1\)\.For each integerT≥0T\\geq 0, define

v−,T⋆​\(x\):=∑t=0Tβ−−2​t​‖\(𝐀−⋆\)t​x‖22,x∈ℝ\|𝒮\|​\|𝒜\|\.v\_\{\-,T\}^\{\\star\}\(x\):=\\sum\_\{t=0\}^\{T\}\\beta\_\{\-\}^\{\-2t\}\\\|\(\\mathbf\{A\}\_\{\-\}^\{\\star\}\)^\{t\}x\\\|\_\{2\}^\{2\},\\qquad x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.Then the following properties hold\.

1. \(1\)For everyT≥0T\\geq 0, v−,T\+1⋆​\(x\)=‖x‖22\+β−−2​v−,T⋆​\(𝐀−⋆​x\),∀x∈ℝ\|𝒮\|​\|𝒜\|\.v\_\{\-,T\+1\}^\{\\star\}\(x\)=\\\|x\\\|\_\{2\}^\{2\}\+\\beta\_\{\-\}^\{\-2\}v\_\{\-,T\}^\{\\star\}\(\\mathbf\{A\}\_\{\-\}^\{\\star\}x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.
2. \(2\)For everyT≥0T\\geq 0, everyx∈ℝ\|𝒮\|​\|𝒜\|x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, and everyλ∈ℝ\\lambda\\in\\mathbb\{R\}, we havev−,T⋆​\(λ​x\)=\|λ\|2​v−,T⋆​\(x\)v\_\{\-,T\}^\{\\star\}\(\\lambda x\)=\|\\lambda\|^\{2\}v\_\{\-,T\}^\{\\star\}\(x\), andv−,T⋆​\(x\)≤v−,T\+1⋆​\(x\)v\_\{\-,T\}^\{\\star\}\(x\)\\leq v\_\{\-,T\+1\}^\{\\star\}\(x\)\.
3. \(3\)There exists a constantC−⋆\>0C\_\{\-\}^\{\\star\}\>0, which is the Euclidean norm\-equivalence constant associated with the fixed\-mode negative\-side Lyapunov construction, such that ‖x‖22≤v−,T⋆​\(x\)≤C−⋆​‖x‖22,∀x∈ℝ\|𝒮\|​\|𝒜\|,∀T≥0\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\-,T\}^\{\\star\}\(x\)\\leq C\_\{\-\}^\{\\star\}\\\|x\\\|\_\{2\}^\{2\},\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\},\\quad\\forall T\\geq 0\.
4. \(4\)For everyx∈ℝ\|𝒮\|​\|𝒜\|x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, the limit v−⋆​\(x\):=limT→∞v−,T⋆​\(x\)=∑t=0∞β−−2​t​‖\(𝐀−⋆\)t​x‖22v\_\{\-\}^\{\\star\}\(x\):=\\lim\_\{T\\to\\infty\}v\_\{\-,T\}^\{\\star\}\(x\)=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\-\}^\{\-2t\}\\\|\(\\mathbf\{A\}\_\{\-\}^\{\\star\}\)^\{t\}x\\\|\_\{2\}^\{2\}exists and is finite\. Moreover, ‖x‖22≤v−⋆​\(x\)≤C−⋆​‖x‖22,∀x∈ℝ\|𝒮\|​\|𝒜\|\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\-\}^\{\\star\}\(x\)\\leq C\_\{\-\}^\{\\star\}\\\|x\\\|\_\{2\}^\{2\},\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.
5. \(5\)The functionp−⋆​\(x\):=v−⋆​\(x\)p\_\{\-\}^\{\\star\}\(x\):=\\sqrt\{v\_\{\-\}^\{\\star\}\(x\)\}is a norm onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.
6. \(6\)The functionv−⋆v\_\{\-\}^\{\\star\}satisfies the fixed\-mode Lyapunov identity v−⋆​\(𝐀−⋆​x\)=β−2​\(v−⋆​\(x\)−‖x‖22\)≤β−2​v−⋆​\(x\),∀x∈ℝ\|𝒮\|​\|𝒜\|\.v\_\{\-\}^\{\\star\}\(\\mathbf\{A\}\_\{\-\}^\{\\star\}x\)=\\beta\_\{\-\}^\{2\}\\left\(v\_\{\-\}^\{\\star\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\\leq\\beta\_\{\-\}^\{2\}v\_\{\-\}^\{\\star\}\(x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.Equivalently, p−⋆​\(𝐀−⋆​x\)≤β−​p−⋆​\(x\),∀x∈ℝ\|𝒮\|​\|𝒜\|\.p\_\{\-\}^\{\\star\}\(\\mathbf\{A\}\_\{\-\}^\{\\star\}x\)\\leq\\beta\_\{\-\}p\_\{\-\}^\{\\star\}\(x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.

Statements 1–4 ensure that the finite power\-based functions converge to a well\-defined Lyapunov function uniformly comparable to the Euclidean norm\. Statement 5 shows that its square root is a genuine norm\. Statement 6 provides the deterministic contraction inequality used for the negative\-side fixed LTI comparison system\.

We now convert the negative sign comparison system into an explicit finite\-time bound\. The next result applies the fixed\-mode Lyapunov identity to the negative\-side comparison system and shows that the optimized LTI rate associated with an optimal policy enters the certified envelope\.

###### Theorem 1\.

Assume[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1)and fixε\>0\\varepsilon\>0such that

ρ−⋆\+ε<1,\\rho\_\{\-\}^\{\\star\}\+\\varepsilon<1,and define

β−:=ρ−⋆\+ε\.\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilon\.Letv−⋆v\_\{\-\}^\{\\star\}be the fixed\-mode Lyapunov function

v−⋆​\(x\):=∑t=0∞β−−2​t​‖\(𝐀−⋆\)t​x‖22,v\_\{\-\}^\{\\star\}\(x\):=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\-\}^\{\-2t\}\\\|\(\\mathbf\{A\}\_\{\-\}^\{\\star\}\)^\{t\}x\\\|\_\{2\}^\{2\},and letC−⋆≥1C\_\{\-\}^\{\\star\}\\geq 1be the fixed\-mode norm\-equivalence constant associated withv−⋆v\_\{\-\}^\{\\star\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, satisfying

‖x‖22≤v−⋆​\(x\)≤C−⋆​‖x‖22\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\-\}^\{\\star\}\(x\)\\leq C\_\{\-\}^\{\\star\}\\\|x\\\|\_\{2\}^\{2\}\.Then, for everyk≥0k\\geq 0,

‖ek−‖∞≤C−⋆​β−k​‖e0−‖2\.\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\.\(8\)Consequently, the deterministic negative part is certified at the optimized single\-policy LTI rate

ρ−⋆=minπ∈Θ∗⁡ρ​\(𝐀π\)\.\\rho\_\{\-\}^\{\\star\}=\\min\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\)\.

###### Proof\.

The proof is provided in[AppendixC\.3](https://arxiv.org/html/2605.16103#A3.SS3)\. ∎

The positive side is handled with the product\-defined Lyapunov function for the full direct switching family, since its comparison mode can vary over all deterministic policies\.

#### 3\.3\.2Construction of the positive\-side JSR Lyapunov function

The Lyapunov construction in this subsection is also adapted from\[[14](https://arxiv.org/html/2605.16103#bib.bib52)\]\. Here it is built from all finite products generated by the positive\-side direct family

ℳα\+=\{𝐀π:π∈Θ\}\.\\mathcal\{M\}\_\{\\alpha\}^\{\+\}=\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta\\\}\.We recall here the properties of the product\-defined construction that are used in the finite\-time argument\.

Fixε\>0\\varepsilon\>0such that

β\+:=ρ\+\+ε∈\(0,1\)\.\\beta\_\{\+\}:=\\rho\_\{\+\}\+\\varepsilon\\in\(0,1\)\.For a sequence of deterministic policiesσ=\(π0,…,πt−1\)∈Θt\\sigma=\(\\pi\_\{0\},\\ldots,\\pi\_\{t\-1\}\)\\in\\Theta^\{t\}, write

𝐀σ:=𝐀πt−1​⋯​𝐀π0,\\mathbf\{A\}\_\{\\sigma\}:=\\mathbf\{A\}\_\{\\pi\_\{t\-1\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{0\}\},and fort=0t=0interpretΘ0\\Theta^\{0\}as the singleton empty word and𝐀σ=I\\mathbf\{A\}\_\{\\sigma\}=I\. For each integerT≥0T\\geq 0, define

v\+,T​\(x\):=∑t=0Tβ\+−2​t​maxσ∈Θt⁡‖𝐀σ​x‖22,x∈ℝ\|𝒮\|​\|𝒜\|\.v\_\{\+,T\}\(x\):=\\sum\_\{t=0\}^\{T\}\\beta\_\{\+\}^\{\-2t\}\\max\_\{\\sigma\\in\\Theta^\{t\}\}\\\|\\mathbf\{A\}\_\{\\sigma\}x\\\|\_\{2\}^\{2\},\\qquad x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.Then the following properties hold\.

1. \(1\)For everyT≥0T\\geq 0, v\+,T\+1​\(x\)≥‖x‖22\+β\+−2​maxπ∈Θ⁡v\+,T​\(𝐀π​x\),∀x∈ℝ\|𝒮\|​\|𝒜\|\.v\_\{\+,T\+1\}\(x\)\\geq\\\|x\\\|\_\{2\}^\{2\}\+\\beta\_\{\+\}^\{\-2\}\\max\_\{\\pi\\in\\Theta\}v\_\{\+,T\}\(\\mathbf\{A\}\_\{\\pi\}x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.
2. \(2\)For everyT≥0T\\geq 0, everyx∈ℝ\|𝒮\|​\|𝒜\|x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, and everyλ∈ℝ\\lambda\\in\\mathbb\{R\}, we havev\+,T​\(λ​x\)=\|λ\|2​v\+,T​\(x\)v\_\{\+,T\}\(\\lambda x\)=\|\\lambda\|^\{2\}v\_\{\+,T\}\(x\), andv\+,T​\(x\)≤v\+,T\+1​\(x\)v\_\{\+,T\}\(x\)\\leq v\_\{\+,T\+1\}\(x\)\.
3. \(3\)There exists a constantC\+\>0C\_\{\+\}\>0, which is the Euclidean norm\-equivalence constant associated with the positive\-side product\-defined JSR Lyapunov construction, such that ‖x‖22≤v\+,T​\(x\)≤C\+​‖x‖22,∀x∈ℝ\|𝒮\|​\|𝒜\|,∀T≥0\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\+,T\}\(x\)\\leq C\_\{\+\}\\\|x\\\|\_\{2\}^\{2\},\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\},\\quad\\forall T\\geq 0\.
4. \(4\)For everyx∈ℝ\|𝒮\|​\|𝒜\|x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, the limit v\+​\(x\):=limT→∞v\+,T​\(x\)=∑t=0∞β\+−2​t​maxπ0,…,πt−1∈Θ⁡‖𝐀πt−1​⋯​𝐀π0​x‖22v\_\{\+\}\(x\):=\\lim\_\{T\\to\\infty\}v\_\{\+,T\}\(x\)=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\+\}^\{\-2t\}\\max\_\{\\pi\_\{0\},\\ldots,\\pi\_\{t\-1\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{t\-1\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{0\}\}x\\right\\\|\_\{2\}^\{2\}exists and is finite\. Moreover, ‖x‖22≤v\+​\(x\)≤C\+​‖x‖22,∀x∈ℝ\|𝒮\|​\|𝒜\|\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\+\}\(x\)\\leq C\_\{\+\}\\\|x\\\|\_\{2\}^\{2\},\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.
5. \(5\)The functionp\+​\(x\):=v\+​\(x\)p\_\{\+\}\(x\):=\\sqrt\{v\_\{\+\}\(x\)\}is a norm onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\.
6. \(6\)The functionv\+v\_\{\+\}satisfies the stronger Lyapunov inequality v\+​\(𝐀π​x\)≤β\+2​\(v\+​\(x\)−‖x‖22\)≤β\+2​v\+​\(x\),∀x∈ℝ\|𝒮\|​\|𝒜\|,∀π∈Θ\.v\_\{\+\}\(\\mathbf\{A\}\_\{\\pi\}x\)\\leq\\beta\_\{\+\}^\{2\}\\left\(v\_\{\+\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\\leq\\beta\_\{\+\}^\{2\}v\_\{\+\}\(x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\},\\quad\\forall\\pi\\in\\Theta\.Equivalently, p\+​\(𝐀π​x\)≤β\+​p\+​\(x\),∀x∈ℝ\|𝒮\|​\|𝒜\|,∀π∈Θ\.p\_\{\+\}\(\\mathbf\{A\}\_\{\\pi\}x\)\\leq\\beta\_\{\+\}p\_\{\+\}\(x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\},\\quad\\forall\\pi\\in\\Theta\.

Statements 1–4 ensure that the finite product\-based functions converge to a well\-defined Lyapunov function uniformly comparable to the Euclidean norm\. Statement 5 shows that its square root is a genuine norm\. Statement 6 provides the deterministic contraction inequality applied to every positive\-side switching family\.

The same argument gives the positive\-side counterpart\. Unlike the negative part, the positive part must be controlled uniformly over all deterministic\-policy modes; hence the rate is governed by the full direct JSR\.

###### Theorem 2\.

Assume[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1)\. Fixε\>0\\varepsilon\>0such that

ρ\+\+ε<1,\\rho\_\{\+\}\+\\varepsilon<1,and define

β\+:=ρ\+\+ε\.\\beta\_\{\+\}:=\\rho\_\{\+\}\+\\varepsilon\.Letv\+v\_\{\+\}be the product\-defined JSR Lyapunov function

v\+​\(x\):=∑t=0∞β\+−2​t​maxπ0,…,πt−1∈Θ⁡‖𝐀πt−1​⋯​𝐀π0​x‖22,v\_\{\+\}\(x\):=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\+\}^\{\-2t\}\\max\_\{\\pi\_\{0\},\\ldots,\\pi\_\{t\-1\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{t\-1\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{0\}\}x\\right\\\|\_\{2\}^\{2\},where thet=0t=0product is the identity, and letC\+≥1C\_\{\+\}\\geq 1be the product\-family norm\-equivalence constant associated withv\+v\_\{\+\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, satisfying

‖x‖22≤v\+​\(x\)≤C\+​‖x‖22\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\+\}\(x\)\\leq C\_\{\+\}\\\|x\\\|\_\{2\}^\{2\}\.Then, for everyk≥0k\\geq 0,

‖ek\+‖∞≤C\+​β\+k​‖e0\+‖2\.\\\|e\_\{k\}^\{\+\}\\\|\_\{\\infty\}\\leq\\sqrt\{C\_\{\+\}\}\\,\\beta\_\{\+\}^\{k\}\\\|e\_\{0\}^\{\+\}\\\|\_\{2\}\.\(9\)Consequently, the deterministic positive part is certified at the full direct switching rate

ρ\+=ραdir=ρ​\(\{𝐀π:π∈Θ\}\)\.\\rho\_\{\+\}=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=\\rho\(\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta\\\}\)\.

###### Proof\.

The proof is provided in[AppendixC\.3](https://arxiv.org/html/2605.16103#A3.SS3)\. ∎

The two bounds show that the certified upper bound for the negative\-part error can converge faster than the certified upper bound for the positive\-part error\. This comparison concerns upper bounds only; it does not mean that the actual error dynamics must always follow the same trend\. The examples in[AppendixB](https://arxiv.org/html/2605.16103#A2)illustrate both possibilities: one trajectory exhibits the slower positive\-side decay suggested by the certificates, while another trajectory shows that the realized positive and negative errors can decay at the same rate\.

###### Corollary 1\.

Let

ℝ\+\|𝒮\|​\|𝒜\|:=\{x∈ℝ\|𝒮\|​\|𝒜\|:x≥0\}\.\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}:=\\\{x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}:x\\geq 0\\\}\.Under the assumptions of[Theorem˜1](https://arxiv.org/html/2605.16103#Thmtheorem1), for everyε\>0\\varepsilon\>0satisfyingρ−⋆\+ε<1\\rho\_\{\-\}^\{\\star\}\+\\varepsilon<1, withβ−:=ρ−⋆\+ε\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilonand with the same fixed\-mode norm\-equivalence constantC−⋆C\_\{\-\}^\{\\star\}associated withv−⋆v\_\{\-\}^\{\\star\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, everyk≥0k\\geq 0satisfies

dist∞⁡\(ek,ℝ\+\|𝒮\|​\|𝒜\|\)≤C−⋆​β−k​‖e0−‖2\.\\operatorname\{dist\}\_\{\\infty\}\(e\_\{k\},\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\)\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\.Consequently, the deterministic full error iterateeke\_\{k\}approaches the nonnegative orthant at the certified exponential rateρ−⋆\\rho\_\{\-\}^\{\\star\}, with no stochastic noise floor\.

###### Proof\.

The proof is provided in[AppendixC\.3](https://arxiv.org/html/2605.16103#A3.SS3)\. ∎

The deterministic analysis therefore assigns the two sides of the error to different finite\-time envelopes\. The negative part is bounded by the optimized fixed\-mode LTI rateρ−⋆\\rho\_\{\-\}^\{\\star\}, while the positive part is bounded by the full switching\-family rateρ\+\\rho\_\{\+\}\. Sinceρ−⋆≤ρ\+\\rho\_\{\-\}^\{\\star\}\\leq\\rho\_\{\+\}, the certified convergence bound for the negative part is no slower than, and may be faster than, the corresponding positive\-part bound\. This is the deterministic core of the sign\-separated asymmetry developed further in the stochastic analysis below\.

## 4Stochastic Q\-Learning and Sign\-Separated Analysis

This section presents the stochastic switching\-system form of Q\-learning and then introduces the sign\-separated lower and upper comparison systems\. SinceVQk=𝚷Qk​QkV\_\{Q\_\{k\}\}=\\boldsymbol\{\\Pi\}\_\{Q\_\{k\}\}Q\_\{k\}, the stochastic recursion can be written as

Qk\+1=𝐀πQk​Qk\+α​D​R\+α​wk,k∈\{0,1,2,…\}\.Q\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{Q\_\{k\}\}\}Q\_\{k\}\+\\alpha DR\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Equivalently, in error coordinates, the error recursion is

ek\+1=𝐀πQk​ek−α​γ​D​P​\(V∗−𝚷πQk​Q∗\)\+α​wk,k∈\{0,1,2,…\}\.e\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{Q\_\{k\}\}\}e\_\{k\}\-\\alpha\\gamma DP\\bigl\(V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{Q\_\{k\}\}\}Q^\{\*\}\\bigr\)\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Thus, constant\-step\-size stochastic Q\-learning is an affine stochastic switching system with an additive noise increment\. As in the deterministic switching\-system representation, the affine offset can be removed by representing the Bellman\-max error through a stochastic policy\[[14](https://arxiv.org/html/2605.16103#bib.bib52)\]\. The following stochastic linear switching\-system representation follows the direct switching theory in\[[14](https://arxiv.org/html/2605.16103#bib.bib52)\]\.

###### Lemma 4\.

Under the standing Q\-learning assumptions, along every trajectory of the stochastic Q\-learning recursion, there exists a sequence ofℱk\\mathcal\{F\}\_\{k\}\-measurable stochastic policies\{μk\}k≥0\\\{\\mu\_\{k\}\\\}\_\{k\\geq 0\}such that the stochastic error recursion can be written exactly as the linear stochastic switching system

ek\+1=𝐀μk​ek\+α​wk,𝐀μk:=I−α​D\+α​γ​D​P​𝚷μk,k∈\{0,1,2,…\}\.e\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}e\_\{k\}\+\\alpha w\_\{k\},\\qquad\\mathbf\{A\}\_\{\\mu\_\{k\}\}:=I\-\\alpha D\+\\alpha\\gamma DP\\boldsymbol\{\\Pi\}^\{\\mu\_\{k\}\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Moreover, each𝐀μk\\mathbf\{A\}\_\{\\mu\_\{k\}\}belongs toco⁡\(ℳα\)\\operatorname\{co\}\(\\mathcal\{M\}\_\{\\alpha\}\)\.

This representation and the associated lower/upper comparison systems build on the switching\-system analyses of\[[13](https://arxiv.org/html/2605.16103#bib.bib39),[12](https://arxiv.org/html/2605.16103#bib.bib38),[11](https://arxiv.org/html/2605.16103#bib.bib37),[14](https://arxiv.org/html/2605.16103#bib.bib52)\]\. The Bellman\-max sandwich and the deterministic residual identities are the same as in[Section˜3\.1](https://arxiv.org/html/2605.16103#S3.SS1); the only additional term is the stochastic incrementα​wk\\alpha w\_\{k\}\. Throughout this section,QkQ\_\{k\},eke\_\{k\}, the greedy selectors introduced below, and all Bellman\-max residuals areℱk\\mathcal\{F\}\_\{k\}\-measurable\.

### 4\.1Lower, Upper, and Sign\-Separated Comparison Systems

As in the deterministic analysis, the stochastic lower comparison system is an LTI system, whereas the upper comparison system is a linear switching system\. The lower stochastic residual identity is

ek\+1=𝐀−⋆​ek\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\+α​wk,k∈\{0,1,2,…\},e\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},\(10\)where the residual satisfiesVQk−V∗−𝚷π−⋆​ek≥0V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\geq 0\. Accordingly, as in the deterministic lower comparison, we keep the same stochastic incrementα​wk\\alpha w\_\{k\}and remove this nonnegative residual\. This gives the optimized lower comparison system

ℓk\+1=𝐀−⋆​ℓk\+α​wk,ℓ0=e0,k∈\{0,1,2,…\}\.\\ell\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}\\ell\_\{k\}\+\\alpha w\_\{k\},\\qquad\\ell\_\{0\}=e\_\{0\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.\(11\)The system in[Equation˜11](https://arxiv.org/html/2605.16103#S4.E11)is a fixed\-mode LTI comparison system driven by the same noise as the original error recursion; the nonnegative residual removed from[Equation˜10](https://arxiv.org/html/2605.16103#S4.E10)is what makes it a lower comparison\.

For the upper comparison, let us define the predictable state\-wise maximizer

πk\+​\(s\)∈arg​maxa∈𝒜⁡ek​\(s,a\),s∈𝒮\.\\pi\_\{k\}^\{\+\}\(s\)\\in\\operatorname\{arg\\,max\}\_\{a\\in\\mathcal\{A\}\}e\_\{k\}\(s,a\),\\qquad s\\in\\mathcal\{S\}\.The upper stochastic residual identity is

ek\+1=𝐀πk\+​ek−α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)\+α​wk,k∈\{0,1,2,…\},e\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},\(12\)where𝚷πk\+​ek−\(VQk−V∗\)≥0\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\geq 0\. Removing the subtracted nonnegative residual gives the direct upper comparison system

uk\+1=𝐀πk\+​uk\+α​wk,u0=e0,k∈\{0,1,2,…\}\.u\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}u\_\{k\}\+\\alpha w\_\{k\},\\qquad u\_\{0\}=e\_\{0\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.\(13\)Unlike the lower comparison,[Equation˜13](https://arxiv.org/html/2605.16103#S4.E13)is a linear stochastic switching system, because the modeπk\+\\pi\_\{k\}^\{\+\}can change with the current error\. The switching signalπk\+\\pi\_\{k\}^\{\+\}is predictable with respect to the one\-step update from timekkto timek\+1k\+1, because it isℱk\\mathcal\{F\}\_\{k\}\-measurable\.

###### Lemma 5\.

Under the standing Q\-learning assumptions, withℓk\\ell\_\{k\}anduku\_\{k\}defined in[Equations˜11](https://arxiv.org/html/2605.16103#S4.E11)and[13](https://arxiv.org/html/2605.16103#S4.E13), we have

ℓk≤ek≤uk,k∈\{0,1,2,…\}\.\\ell\_\{k\}\\leq e\_\{k\}\\leq u\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.

###### Proof\.

The proof is provided in[AppendixC\.4](https://arxiv.org/html/2605.16103#A3.SS4)\. ∎

The order relations imply

ek−≤ℓk−,ek\+≤uk\+,k∈\{0,1,2,…\},e\_\{k\}^\{\-\}\\leq\\ell\_\{k\}^\{\-\},\\qquad e\_\{k\}^\{\+\}\\leq u\_\{k\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},and the following inequalities hold:

ek\+1−≤𝐀−⋆​ek−\+α​wk−,k∈\{0,1,2,…\},e\_\{k\+1\}^\{\-\}\\leq\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\+\\alpha w\_\{k\}^\{\-\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},ek\+1\+≤𝐀πk\+​ek\+\+α​wk\+,k∈\{0,1,2,…\}\.e\_\{k\+1\}^\{\+\}\\leq\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\+\\alpha w\_\{k\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.The formal sign\-control and one\-step domination lemmas are stated and proved in[AppendixC\.4](https://arxiv.org/html/2605.16103#A3.SS4)\.

These one\-step inequalities define the stochastic sign comparison systems used in the finite\-time bounds\. The negative sign comparison keeps only the fixed\-mode LTI propagation of the previous negative part and the negative part of the noise increment:

zk\+1−=𝐀−⋆​zk−\+α​wk−,z0−=e0−,k∈\{0,1,2,…\}\.z^\{\-\}\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}z^\{\-\}\_\{k\}\+\\alpha w\_\{k\}^\{\-\},\\qquad z^\{\-\}\_\{0\}=e\_\{0\}^\{\-\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.\(14\)The positive sign comparison keeps the switching propagation selected byπk\+\\pi\_\{k\}^\{\+\}and the positive part of the noise increment:

zk\+1\+=𝐀πk\+​zk\+\+α​wk\+,z0\+=e0\+,k∈\{0,1,2,…\}\.z^\{\+\}\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}z^\{\+\}\_\{k\}\+\\alpha w\_\{k\}^\{\+\},\\qquad z^\{\+\}\_\{0\}=e\_\{0\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.\(15\)The next lemma states that these two auxiliary systems dominate the actual negative and positive parts pathwise\.

###### Lemma 6\.

Under the standing Q\-learning assumptions, withzk−z\_\{k\}^\{\-\}andzk\+z\_\{k\}^\{\+\}defined in[Equations˜14](https://arxiv.org/html/2605.16103#S4.E14)and[15](https://arxiv.org/html/2605.16103#S4.E15), for allk∈\{0,1,2,…\}k\\in\\\{0,1,2,\\ldots\\\},

ek−≤zk−,ek\+≤zk\+\.e\_\{k\}^\{\-\}\\leq z^\{\-\}\_\{k\},\\qquad e\_\{k\}^\{\+\}\\leq z^\{\+\}\_\{k\}\.

###### Proof\.

The proof is provided in[AppendixC\.4](https://arxiv.org/html/2605.16103#A3.SS4)\. ∎

### 4\.2Finite\-Time Rates for Sign\-Separated Components

We next derive finite\-time bounds for the two sign components\. The Lyapunov constructions are the same as in the deterministic finite\-time analysis; the additional step is to track the stochastic increments\. The negative comparison system is the fixed LTI system generated by𝐀−⋆\\mathbf\{A\}\_\{\-\}^\{\\star\}, whereas the positive comparison system is controlled by a switching family\.

###### Theorem 3\.

Assume[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), and letWmaxW\_\{\\max\}be the noise constant defined in[Equation˜2](https://arxiv.org/html/2605.16103#S2.E2)\. Fixε\>0\\varepsilon\>0such that

ρ−⋆\+ε<1,\\rho\_\{\-\}^\{\\star\}\+\\varepsilon<1,and define

β−:=ρ−⋆\+ε\.\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilon\.Letv−⋆v\_\{\-\}^\{\\star\}be the fixed\-mode Lyapunov function

v−⋆​\(x\):=∑t=0∞β−−2​t​‖\(𝐀−⋆\)t​x‖22\.v\_\{\-\}^\{\\star\}\(x\):=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\-\}^\{\-2t\}\\\|\(\\mathbf\{A\}\_\{\-\}^\{\\star\}\)^\{t\}x\\\|\_\{2\}^\{2\}\.Then

v−⋆​\(𝐀−⋆​x\)=β−2​\(v−⋆​\(x\)−‖x‖22\),∀x∈ℝ\|𝒮\|​\|𝒜\|,v\_\{\-\}^\{\\star\}\(\\mathbf\{A\}\_\{\-\}^\{\\star\}x\)=\\beta\_\{\-\}^\{2\}\\left\(v\_\{\-\}^\{\\star\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\},and there existsC−⋆≥1C\_\{\-\}^\{\\star\}\\geq 1, the fixed\-mode norm\-equivalence constant associated withv−⋆v\_\{\-\}^\{\\star\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, such that

‖x‖22≤v−⋆​\(x\)≤C−⋆​‖x‖22\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\-\}^\{\\star\}\(x\)\\leq C\_\{\-\}^\{\\star\}\\\|x\\\|\_\{2\}^\{2\}\.Then, for everyk≥0k\\geq 0,

𝔼​\[‖ek−‖∞\]≤C−⋆​β−k​‖e0−‖2\+α​C−⋆​Wmax1−β−2\.\\mathbb\{E\}\[\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\]\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\+\\alpha C\_\{\-\}^\{\\star\}\\sqrt\{\\frac\{W\_\{\\max\}\}\{1\-\\beta\_\{\-\}^\{2\}\}\}\.\(16\)Consequently, the negative part is certified at the optimized single\-policy LTI rate

ρ−⋆=minπ∈Θ∗⁡ρ​\(𝐀π\)\.\\rho\_\{\-\}^\{\\star\}=\\min\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\)\.

###### Proof\.

The proof is provided in[AppendixC\.5](https://arxiv.org/html/2605.16103#A3.SS5)\. ∎

Since the distance to the nonnegative orthant is exactly the infinity norm of the negative part, the previous theorem immediately gives the following orthant\-distance estimate\.

###### Corollary 2\.

Let

ℝ\+\|𝒮\|​\|𝒜\|:=\{x∈ℝ\|𝒮\|​\|𝒜\|:x≥0\}\.\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}:=\\\{x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}:x\\geq 0\\\}\.Under the assumptions of[Theorem˜3](https://arxiv.org/html/2605.16103#Thmtheorem3), for everyε\>0\\varepsilon\>0satisfyingρ−⋆\+ε<1\\rho\_\{\-\}^\{\\star\}\+\\varepsilon<1, withβ−:=ρ−⋆\+ε\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilonand with the same fixed\-mode norm\-equivalence constantC−⋆C\_\{\-\}^\{\\star\}associated withv−⋆v\_\{\-\}^\{\\star\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, everyk≥0k\\geq 0satisfies

𝔼​\[dist∞⁡\(ek,ℝ\+\|𝒮\|​\|𝒜\|\)\]≤C−⋆​β−k​‖e0−‖2\+α​C−⋆​Wmax1−β−2\.\\mathbb\{E\}\\\!\\left\[\\operatorname\{dist\}\_\{\\infty\}\(e\_\{k\},\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\)\\right\]\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\+\\alpha C\_\{\-\}^\{\\star\}\\sqrt\{\\frac\{W\_\{\\max\}\}\{1\-\\beta\_\{\-\}^\{2\}\}\}\.Consequently, the full error iterateeke\_\{k\}approaches the nonnegative orthant at the certified exponential rate

ρ−⋆=minπ∈Θ∗⁡ρ​\(𝐀π\),\\rho\_\{\-\}^\{\\star\}=\\min\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\),up to the constant\-step\-size noise floor of orderO​\(α\)O\(\\alpha\)\.

###### Proof\.

The proof is provided in[AppendixC\.5](https://arxiv.org/html/2605.16103#A3.SS5)\. ∎

The positive component is estimated analogously, except that the Lyapunov function must dominate every product generated by the corresponding switching family instead of the single\-mode LTI system\.

###### Theorem 4\.

Assume[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), and letWmaxW\_\{\\max\}be the noise constant defined in[Equation˜2](https://arxiv.org/html/2605.16103#S2.E2)\. Fixε\>0\\varepsilon\>0such that

ρ\+\+ε<1,\\rho\_\{\+\}\+\\varepsilon<1,and define

β\+:=ρ\+\+ε\.\\beta\_\{\+\}:=\\rho\_\{\+\}\+\\varepsilon\.Letv\+v\_\{\+\}be the product\-defined JSR Lyapunov function

v\+​\(x\):=∑t=0∞β\+−2​t​maxπ0,…,πt−1∈Θ⁡‖𝐀πt−1​⋯​𝐀π0​x‖22,v\_\{\+\}\(x\):=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\+\}^\{\-2t\}\\max\_\{\\pi\_\{0\},\\ldots,\\pi\_\{t\-1\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{t\-1\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{0\}\}x\\right\\\|\_\{2\}^\{2\},where thet=0t=0product is the identity\. Then, for everyπ∈Θ\\pi\\in\\Theta,

v\+​\(𝐀π​x\)≤β\+2​\(v\+​\(x\)−‖x‖22\),∀x∈ℝ\|𝒮\|​\|𝒜\|,v\_\{\+\}\(\\mathbf\{A\}\_\{\\pi\}x\)\\leq\\beta\_\{\+\}^\{2\}\\left\(v\_\{\+\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\},and there existsC\+≥1C\_\{\+\}\\geq 1, the product\-family norm\-equivalence constant associated withv\+v\_\{\+\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, such that

‖x‖22≤v\+​\(x\)≤C\+​‖x‖22\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\+\}\(x\)\\leq C\_\{\+\}\\\|x\\\|\_\{2\}^\{2\}\.Then, for everyk≥0k\\geq 0,

𝔼​\[‖ek\+‖∞\]≤C\+​β\+k​‖e0\+‖2\+α​C\+​Wmax1−β\+2\.\\mathbb\{E\}\[\\\|e\_\{k\}^\{\+\}\\\|\_\{\\infty\}\]\\leq\\sqrt\{C\_\{\+\}\}\\,\\beta\_\{\+\}^\{k\}\\\|e\_\{0\}^\{\+\}\\\|\_\{2\}\+\\alpha C\_\{\+\}\\sqrt\{\\frac\{W\_\{\\max\}\}\{1\-\\beta\_\{\+\}^\{2\}\}\}\.\(17\)Consequently, the positive part is certified at the full direct JSR rate

ρ\+=ραdir=ρ​\(\{𝐀π:π∈Θ\}\)\.\\rho\_\{\+\}=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=\\rho\(\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta\\\}\)\.

###### Proof\.

The proof is provided in[AppendixC\.5](https://arxiv.org/html/2605.16103#A3.SS5)\. ∎

Combining[Theorems˜3](https://arxiv.org/html/2605.16103#Thmtheorem3)and[4](https://arxiv.org/html/2605.16103#Thmtheorem4), the negative part is certified at the optimized single\-policy LTI rate

ρ−⋆=minπ∈Θ∗⁡ρ​\(𝐀π\),\\rho\_\{\-\}^\{\\star\}=\\min\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\),whereas the positive part is certified at the full JSR rate

ρ\+=ραdir=ρ​\(\{𝐀π:π∈Θ\}\)\.\\rho\_\{\+\}=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=\\rho\(\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta\\\}\)\.Since

ρ−⋆≤ρ−≤ρ\+,\\rho\_\{\-\}^\{\\star\}\\leq\\rho\_\{\-\}\\leq\\rho\_\{\+\},the optimized negative\-side LTI certificate is no slower than the optimal\-policy switching certificate and can be strictly faster than the positive\-side direct switching certificate\. This comparison follows from the sign of the Bellman\-max residuals: for every optimal policyπ∈Θ∗\\pi\\in\\Theta^\{\*\},

VQ−V∗≥𝚷π​e,V\_\{Q\}\-V^\{\*\}\\geq\\boldsymbol\{\\Pi\}^\{\\pi\}e,Thus, the residual relative to a fixed optimal policy is nonnegative and does not enlarge the negative\-part upper comparison\. Choosing

π−⋆∈arg​minπ∈Θ∗⁡ρ​\(𝐀π\)\\pi\_\{\-\}^\{\\star\}\\in\\operatorname\{arg\\,min\}\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\)therefore gives the fastest spectral\-radius certificate among fixed LTI lower comparisons associated with optimal policies\. In contrast, the positive side must allow all actions through

VQ−V∗≤maxa∈𝒜⁡e​\(s,a\),V\_\{Q\}\-V^\{\*\}\\leq\\max\_\{a\\in\\mathcal\{A\}\}e\(s,a\),Thus, suboptimal actions with positive error can enter the positive\-side switching dynamics\. This is the structural source of the max\-induced overestimation\-like asymmetry\.

These conclusions are structural comparison statements, not a universal positive\-bias theorem for Q\-learning\. They do not by themselves imply𝔼​\[ek\]≥0\\mathbb\{E\}\[e\_\{k\}\]\\geq 0or𝔼​\[VQk−V∗\]≥0\\mathbb\{E\}\[V\_\{Q\_\{k\}\}\-V^\{\*\}\]\\geq 0\. Rather, they show that negative errors are dominated by an optimized LTI comparison associated with an optimal policy, while positive errors may be propagated by the switching family and may also be sustained by the nonnegative residual

α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\.\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)\.Whenρ−⋆<ρ\+\\rho\_\{\-\}^\{\\star\}<\\rho\_\{\+\}, the negative component has a strictly faster certified exponential envelope than the positive component, although a particular sample path or problem instance need not exhibit strictly faster realized decay ofek−e\_\{k\}^\{\-\}\. Under a constant step\-size, the stochastic bounds also contain anO​\(α\)O\(\\alpha\)noise floor; hence the natural interpretation is entry into a small neighborhood rather than exact convergence to zero in general\.

## 5Conclusion

This paper developed a sign\-separated finite\-time analysis of constant\-step\-size Q\-learning from the switching\-system viewpoint\. By decomposing the error into its negative and positive components, the analysis shows that the Bellman maximum induces different comparison mechanisms on the two sides of the error\. The negative component is bounded by an optimized fixed\-mode linear system associated with an optimal policy, whereas the positive component requires a switching\-system bound over the full deterministic\-policy family\.

The deterministic analysis gives pure exponential envelopes for the two sign components\. The stochastic analysis extends the same structure to the i\.i\.d\. observation model and adds the usual constant\-step\-size noise floor\. The results are certificate\-level comparison bounds, not a claim that every trajectory must display the same sign\-separated trend\. The framework complements contraction\-based and stochastic\-approximation analyses by showing how the Bellman maximum can create asymmetric transient behavior in Q\-learning\.

## References

- \[1\]\(2012\)Error bounds for constant step\-size Q\-learning\.Systems & control letters61\(12\),pp\. 1203–1208\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[2\]D\. P\. Bertsekas and J\. N\. Tsitsiklis\(1996\)Neuro\-dynamic programming\.Athena Scientific Belmont, MA\.Cited by:[§2\.5](https://arxiv.org/html/2605.16103#S2.SS5.p1.4)\.
- \[3\]V\. D\. Blondel and Y\. Nesterov\(2005\)Computationally efficient approximations of the joint spectral radius\.SIAM Journal on Matrix Analysis and Applications27\(1\),pp\. 256–272\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§2\.2](https://arxiv.org/html/2605.16103#S2.SS2.p1.13)\.
- \[4\]V\. S\. Borkar and S\. P\. Meyn\(2000\)The ODE method for convergence of stochastic approximation and reinforcement learning\.SIAM Journal on Control and Optimization38\(2\),pp\. 447–469\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[5\]Z\. Chen, S\. T\. Maguluri, S\. Shakkottai, and K\. Shanmugam\(2021\)A Lyapunov theory for finite\-sample guarantees of asynchronous Q\-learning and TD\-learning variants\.arXiv preprint arXiv:2102\.01567\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[6\]E\. Even\-Dar and Y\. Mansour\(2003\)Learning rates for Q\-learning\.Journal of machine learning Research5\(Dec\),pp\. 1–25\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[7\]T\. Jaakkola, M\. Jordan, and S\. Singh\(1993\)Convergence of stochastic iterative dynamic programming algorithms\.Advances in neural information processing systems6\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[8\]R\. Jungers\(2009\)The joint spectral radius: Theory and applications\.Vol\.385,Springer Science & Business Media\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§2\.2](https://arxiv.org/html/2605.16103#S2.SS2.p1.13)\.
- \[9\]M\. Kearns and S\. Singh\(1998\)Finite\-sample convergence rates for Q\-learning and indirect algorithms\.Advances in neural information processing systems11\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[10\]H\. Kushner and G\. G\. Yin\(2003\)Stochastic approximation and recursive algorithms and applications\.Vol\.35,Springer Science & Business Media\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[11\]D\. Lee and N\. He\(2020\)A unified switching system perspective and convergence analysis of Q\-learning algorithms\.In34th Conference on Neural Information Processing Systems, NeurIPS 2020,Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1),[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§3\.1](https://arxiv.org/html/2605.16103#S3.SS1.p1.1),[§3](https://arxiv.org/html/2605.16103#S3.p1.2),[§3](https://arxiv.org/html/2605.16103#S3.p1.6),[§4](https://arxiv.org/html/2605.16103#S4.p2.4)\.
- \[12\]D\. Lee, J\. Hu, and N\. He\(2023\)A discrete\-time switching system analysis of Q\-learning\.SIAM Journal on Control and Optimization61\(3\),pp\. 1861–1880\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§3\.1](https://arxiv.org/html/2605.16103#S3.SS1.p1.1),[§3](https://arxiv.org/html/2605.16103#S3.p1.2),[§3](https://arxiv.org/html/2605.16103#S3.p1.6),[§4](https://arxiv.org/html/2605.16103#S4.p2.4)\.
- \[13\]D\. Lee\(2024\)Final iteration convergence bound of Q\-learning: Switching system approach\.IEEE Transactions on Automatic Control69\(7\),pp\. 4765–4772\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§3\.1](https://arxiv.org/html/2605.16103#S3.SS1.p1.1),[§3](https://arxiv.org/html/2605.16103#S3.p1.2),[§3](https://arxiv.org/html/2605.16103#S3.p1.6),[§4](https://arxiv.org/html/2605.16103#S4.p2.4)\.
- \[14\]D\. Lee\(2026\)Lyapunov\-certified direct switching theory for Q\-learning\.arXiv preprint arXiv:2604\.19569\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p3.1),[§1](https://arxiv.org/html/2605.16103#S1.p4.3),[§1](https://arxiv.org/html/2605.16103#S1.p6.1),[§3\.3\.1](https://arxiv.org/html/2605.16103#S3.SS3.SSS1.p1.1),[§3\.3\.2](https://arxiv.org/html/2605.16103#S3.SS3.SSS2.p1.1),[§3](https://arxiv.org/html/2605.16103#S3.p1.6),[§4](https://arxiv.org/html/2605.16103#S4.p1.3),[§4](https://arxiv.org/html/2605.16103#S4.p2.4)\.
- \[15\]G\. Li, Y\. Wei, Y\. Chi, Y\. Gu, and Y\. Chen\(2021\)Sample complexity of asynchronous Q\-learning: Sharper analysis and variance reduction\.IEEE Transactions on Information Theory68\(1\),pp\. 448–473\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[16\]D\. Liberzon\(2003\)Switching in systems and control\.Springer Science & Business Media\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§2\.2](https://arxiv.org/html/2605.16103#S2.SS2.p1.14)\.
- \[17\]H\. Lim and D\. Lee\(2024\)Finite\-time analysis of asynchronous Q\-learning under diminishing step\-size from control\-theoretic view\.IEEE Access12,pp\. 149916–149939\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1)\.
- \[18\]H\. Lin and P\. J\. Antsaklis\(2009\)Stability and stabilizability of switched linear systems: A survey of recent results\.IEEE Transactions on Automatic control54\(2\),pp\. 308–322\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§2\.2](https://arxiv.org/html/2605.16103#S2.SS2.p1.14)\.
- \[19\]M\. L\. Puterman\(2014\)Markov decision processes: Discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[§2\.3](https://arxiv.org/html/2605.16103#S2.SS3.p1.10),[§2\.4](https://arxiv.org/html/2605.16103#S2.SS4.p1.4)\.
- \[20\]G\. Qu and A\. Wierman\(2020\)Finite\-time analysis of asynchronous stochastic approximation and Q\-learning\.InConference on learning theory,pp\. 3185–3205\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[21\]G\. Rota and G\. Strang\(1960\)A note on the joint spectral radius\.Indag\. Math22\(4\),pp\. 379–381\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§2\.2](https://arxiv.org/html/2605.16103#S2.SS2.p1.13)\.
- \[22\]R\. Shorten, F\. Wirth, O\. Mason, K\. Wulff, and C\. King\(2007\)Stability criteria for switched and hybrid systems\.SIAM Review49\(4\),pp\. 545–592\.Cited by:[§2\.2](https://arxiv.org/html/2605.16103#S2.SS2.p1.14)\.
- \[23\]R\. S\. Sutton and A\. G\. Barto\(1998\)Reinforcement learning: An introduction\.MIT Press\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1),[§2\.5](https://arxiv.org/html/2605.16103#S2.SS5.p1.4)\.
- \[24\]C\. Szepesvári\(1998\)The asymptotic convergence\-rate of Q\-learning\.InAdvances in Neural Information Processing Systems,pp\. 1064–1070\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[25\]S\. Thrun and A\. Schwartz\(1993\)Issues in using function approximation for reinforcement learning\.InProceedings of the 1993 Connectionist Models Summer School,M\. Mozer, P\. Smolensky, D\. Touretzky, J\. Elman, and A\. Weigend \(Eds\.\),pp\. 255–263\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p4.3)\.
- \[26\]J\. N\. Tsitsiklis and V\. D\. Blondel\(1997\)The lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impossible—to compute and to approximate\.Mathematics of Control, Signals and Systems10\(1\),pp\. 31–40\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p2.1),[§2\.2](https://arxiv.org/html/2605.16103#S2.SS2.p1.13)\.
- \[27\]J\. N\. Tsitsiklis\(1994\)Asynchronous stochastic approximation and Q\-learning\.Machine learning16\(3\),pp\. 185–202\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[28\]H\. van Hasselt\(2010\)Double q\-learning\.InAdvances in Neural Information Processing Systems,Vol\.23,pp\. 2613–2622\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p4.3)\.
- \[29\]M\. J\. Wainwright\(2019\)Stochastic approximation with cone\-contractive operators: Sharpl∞l\_\{\\infty\}\-bounds for Q\-learning\.arXiv preprint arXiv:1905\.06265\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.
- \[30\]C\. J\. Watkins and P\. Dayan\(1992\)Q\-learning\.Machine learning8\(3\),pp\. 279–292\.Cited by:[§1](https://arxiv.org/html/2605.16103#S1.p1.1)\.

Appendix

## Appendix AAuxiliary Lyapunov constructions

The following lemma records the product\-defined Lyapunov construction used in the finite\-time arguments\.

###### Lemma 7\.

Let

ℋ:=\{A1,A2,…,AM\}⊂ℝm×m,ρ:=ρ​\(ℋ\),\\mathcal\{H\}:=\\\{A\_\{1\},A\_\{2\},\\ldots,A\_\{M\}\\\}\\subset\\mathbb\{R\}^\{m\\times m\},\\qquad\\rho:=\\rho\(\\mathcal\{H\}\),and fix anyε\>0\\varepsilon\>0such that

βε:=ρ\+ε∈\(0,1\)\.\\beta\_\{\\varepsilon\}:=\\rho\+\\varepsilon\\in\(0,1\)\.For a sequence of switching modesσ=\(σ1,…,σk\)∈\{1,…,M\}k\\sigma=\(\\sigma\_\{1\},\\ldots,\\sigma\_\{k\}\)\\in\\\{1,\\ldots,M\\\}^\{k\}, write

Aσ:=Aσk​⋯​Aσ1,A\_\{\\sigma\}:=A\_\{\\sigma\_\{k\}\}\\cdots A\_\{\\sigma\_\{1\}\},and fork=0k=0interpret\{1,…,M\}0\\\{1,\\ldots,M\\\}^\{0\}as the singleton empty word andAσ=IA\_\{\\sigma\}=I\. For each integert≥0t\\geq 0, define

vεt​\(x\):=∑k=0tβε−2​k​maxσ∈\{1,2,…,M\}k⁡‖Aσ​x‖22,x∈ℝm\.v\_\{\\varepsilon\}^\{t\}\(x\):=\\sum\_\{k=0\}^\{t\}\\beta\_\{\\varepsilon\}^\{\-2k\}\\max\_\{\\sigma\\in\\\{1,2,\\ldots,M\\\}^\{k\}\}\\\|A\_\{\\sigma\}x\\\|\_\{2\}^\{2\},\\qquad x\\in\\mathbb\{R\}^\{m\}\.Then the following statements hold\.

1. \(1\)For everyt≥0t\\geq 0, vεt\+1​\(x\)≥‖x‖22\+βε−2​maxi∈\{1,…,M\}⁡vεt​\(Ai​x\),∀x∈ℝm\.v\_\{\\varepsilon\}^\{t\+1\}\(x\)\\geq\\\|x\\\|\_\{2\}^\{2\}\+\\beta\_\{\\varepsilon\}^\{\-2\}\\max\_\{i\\in\\\{1,\\ldots,M\\\}\}v\_\{\\varepsilon\}^\{t\}\(A\_\{i\}x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{m\}\.
2. \(2\)For everyt≥0t\\geq 0, everyx∈ℝmx\\in\\mathbb\{R\}^\{m\}, and everyλ∈ℝ\\lambda\\in\\mathbb\{R\}, vεt​\(λ​x\)=\|λ\|2​vεt​\(x\),vεt​\(x\)≤vεt\+1​\(x\)\.v\_\{\\varepsilon\}^\{t\}\(\\lambda x\)=\|\\lambda\|^\{2\}v\_\{\\varepsilon\}^\{t\}\(x\),\\qquad v\_\{\\varepsilon\}^\{t\}\(x\)\\leq v\_\{\\varepsilon\}^\{t\+1\}\(x\)\.
3. \(3\)There exists a constantCε\>0C\_\{\\varepsilon\}\>0such that ‖x‖22≤vεt​\(x\)≤Cε​‖x‖22,∀x∈ℝm,∀t≥0\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\\varepsilon\}^\{t\}\(x\)\\leq C\_\{\\varepsilon\}\\\|x\\\|\_\{2\}^\{2\},\\qquad\\forall x\\in\\mathbb\{R\}^\{m\},\\quad\\forall t\\geq 0\.
4. \(4\)For everyx∈ℝmx\\in\\mathbb\{R\}^\{m\}, the limit vε∞​\(x\):=limt→∞vεt​\(x\)v\_\{\\varepsilon\}^\{\\infty\}\(x\):=\\lim\_\{t\\to\\infty\}v\_\{\\varepsilon\}^\{t\}\(x\)exists and is finite\. Moreover, ‖x‖22≤vε∞​\(x\)≤Cε​‖x‖22,∀x∈ℝm\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\\varepsilon\}^\{\\infty\}\(x\)\\leq C\_\{\\varepsilon\}\\\|x\\\|\_\{2\}^\{2\},\\qquad\\forall x\\in\\mathbb\{R\}^\{m\}\.
5. \(5\)The functionpε​\(x\):=vε∞​\(x\)p\_\{\\varepsilon\}\(x\):=\\sqrt\{v\_\{\\varepsilon\}^\{\\infty\}\(x\)\}is a norm onℝm\\mathbb\{R\}^\{m\}\.
6. \(6\)The functionvε∞v\_\{\\varepsilon\}^\{\\infty\}satisfies the stronger Lyapunov inequality vε∞​\(Ai​x\)≤βε2​\(vε∞​\(x\)−‖x‖22\)≤βε2​vε∞​\(x\),∀x∈ℝm,∀i∈\{1,…,M\}\.v\_\{\\varepsilon\}^\{\\infty\}\(A\_\{i\}x\)\\leq\\beta\_\{\\varepsilon\}^\{2\}\\left\(v\_\{\\varepsilon\}^\{\\infty\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\\leq\\beta\_\{\\varepsilon\}^\{2\}v\_\{\\varepsilon\}^\{\\infty\}\(x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{m\},\\quad\\forall i\\in\\\{1,\\ldots,M\\\}\.Equivalently, pε​\(Ai​x\)≤βε​pε​\(x\),∀x∈ℝm,∀i∈\{1,…,M\}\.p\_\{\\varepsilon\}\(A\_\{i\}x\)\\leq\\beta\_\{\\varepsilon\}p\_\{\\varepsilon\}\(x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{m\},\\quad\\forall i\\in\\\{1,\\ldots,M\\\}\.

###### Proof\.

For eachk≥0k\\geq 0, set

ak:=maxσ∈\{1,2,…,M\}k⁡‖Aσ‖2,a\_\{k\}:=\\max\_\{\\sigma\\in\\\{1,2,\\ldots,M\\\}^\{k\}\}\\\|A\_\{\\sigma\}\\\|\_\{2\},wherea0=1a\_\{0\}=1\. Sinceβε\>ρ​\(ℋ\)\\beta\_\{\\varepsilon\}\>\\rho\(\\mathcal\{H\}\), the definition of the JSR implies that

Cε:=∑k=0∞βε−2​k​ak2C\_\{\\varepsilon\}:=\\sum\_\{k=0\}^\{\\infty\}\\beta\_\{\\varepsilon\}^\{\-2k\}a\_\{k\}^\{2\}is finite\. Hence

vεt​\(x\)≤∑k=0tβε−2​k​ak2​‖x‖22≤Cε​‖x‖22\.v\_\{\\varepsilon\}^\{t\}\(x\)\\leq\\sum\_\{k=0\}^\{t\}\\beta\_\{\\varepsilon\}^\{\-2k\}a\_\{k\}^\{2\}\\\|x\\\|\_\{2\}^\{2\}\\leq C\_\{\\varepsilon\}\\\|x\\\|\_\{2\}^\{2\}\.The lower bound follows from thek=0k=0term, which is‖x‖22\\\|x\\\|\_\{2\}^\{2\}\. This proves Statement 3\. Statement 2 follows from homogeneity of the Euclidean norm and from the fact thatvεt\+1v\_\{\\varepsilon\}^\{t\+1\}is obtained fromvεtv\_\{\\varepsilon\}^\{t\}by adding one nonnegative term\.

For Statement 1, fixi∈\{1,…,M\}i\\in\\\{1,\\ldots,M\\\}\. For everyk≥0k\\geq 0, each productAσ​AiA\_\{\\sigma\}A\_\{i\}, withσ∈\{1,…,M\}k\\sigma\\in\\\{1,\\ldots,M\\\}^\{k\}, is a product of lengthk\+1k\+1fromℋ\\mathcal\{H\}\. Therefore

βε−2​vεt​\(Ai​x\)\\displaystyle\\beta\_\{\\varepsilon\}^\{\-2\}v\_\{\\varepsilon\}^\{t\}\(A\_\{i\}x\)=∑k=0tβε−2​\(k\+1\)​maxσ∈\{1,…,M\}k⁡‖Aσ​Ai​x‖22\\displaystyle=\\sum\_\{k=0\}^\{t\}\\beta\_\{\\varepsilon\}^\{\-2\(k\+1\)\}\\max\_\{\\sigma\\in\\\{1,\\ldots,M\\\}^\{k\}\}\\\|A\_\{\\sigma\}A\_\{i\}x\\\|\_\{2\}^\{2\}≤∑r=1t\+1βε−2​r​maxτ∈\{1,…,M\}r⁡‖Aτ​x‖22\\displaystyle\\leq\\sum\_\{r=1\}^\{t\+1\}\\beta\_\{\\varepsilon\}^\{\-2r\}\\max\_\{\\tau\\in\\\{1,\\ldots,M\\\}^\{r\}\}\\\|A\_\{\\tau\}x\\\|\_\{2\}^\{2\}=vεt\+1​\(x\)−‖x‖22\.\\displaystyle=v\_\{\\varepsilon\}^\{t\+1\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\.Taking the maximum overiigives Statement 1\.

Statement 4 follows becausevεt​\(x\)v\_\{\\varepsilon\}^\{t\}\(x\)is monotone nondecreasing inttand uniformly bounded above by Statement 3\. For Statement 5, define

gk​\(x\):=βε−k​maxσ∈\{1,…,M\}k⁡‖Aσ​x‖2,k≥0\.g\_\{k\}\(x\):=\\beta\_\{\\varepsilon\}^\{\-k\}\\max\_\{\\sigma\\in\\\{1,\\ldots,M\\\}^\{k\}\}\\\|A\_\{\\sigma\}x\\\|\_\{2\},\\qquad k\\geq 0\.Eachgkg\_\{k\}is a seminorm andg0​\(x\)=‖x‖2g\_\{0\}\(x\)=\\\|x\\\|\_\{2\}is a norm\. Sincepε​\(x\)=‖\(g0​\(x\),g1​\(x\),…\)‖ℓ2p\_\{\\varepsilon\}\(x\)=\\\|\(g\_\{0\}\(x\),g\_\{1\}\(x\),\\ldots\)\\\|\_\{\\ell\_\{2\}\}, positivity follows fromg0g\_\{0\}, homogeneity is immediate, and the triangle inequality follows from the triangle inequality for eachgkg\_\{k\}and Minkowski’s inequality inℓ2\\ell\_\{2\}\. Consequently,pεp\_\{\\varepsilon\}is a norm\.

Finally, applying Statement 1 and passing to the limitt→∞t\\to\\inftygives

vε∞​\(x\)≥‖x‖22\+βε−2​maxi∈\{1,…,M\}⁡vε∞​\(Ai​x\)\.v\_\{\\varepsilon\}^\{\\infty\}\(x\)\\geq\\\|x\\\|\_\{2\}^\{2\}\+\\beta\_\{\\varepsilon\}^\{\-2\}\\max\_\{i\\in\\\{1,\\ldots,M\\\}\}v\_\{\\varepsilon\}^\{\\infty\}\(A\_\{i\}x\)\.This is equivalent to Statement 6, and taking square roots gives the norm inequality\. ∎

## Appendix BExamples

The first example shows a case in which the positive component realizes the slower certificate rate\.

###### Example 1\.

The following one\-state, two\-action example shows that the positive part can have a strictly slower realized decay than the negative part, and also that the certificate rates can satisfyρ−⋆<ρ\+\\rho\_\{\-\}^\{\\star\}<\\rho\_\{\+\}\. Let𝒮=\{1\}\\mathcal\{S\}=\\\{1\\\}and𝒜=\{1,2\}\\mathcal\{A\}=\\\{1,2\\\}, and let both actions be self\-loops:P​\(1∣1,1\)=P​\(1∣1,2\)=1P\(1\\mid 1,1\)=P\(1\\mid 1,2\)=1\. LetR​\(1,1\)=R​\(1,2\)=0R\(1,1\)=R\(1,2\)=0,γ=0\.9\\gamma=0\.9, andα∈\(0,1\)\\alpha\\in\(0,1\), and use the sampling distribution

d​\(1,1\)=0\.9,d​\(1,2\)=0\.1\.d\(1,1\)=0\.9,\\qquad d\(1,2\)=0\.1\.Then

Q∗​\(1,1\)=Q∗​\(1,2\)=0\.Q^\{\*\}\(1,1\)=Q^\{\*\}\(1,2\)=0\.It follows that both actions are optimal and

Θ∗=\{π1,π2\},πi​\(1\)=i,i∈\{1,2\}\.\\Theta^\{\*\}=\\\{\\pi\_\{1\},\\pi\_\{2\}\\\},\\qquad\\pi\_\{i\}\(1\)=i,\\quad i\\in\\\{1,2\\\}\.With the ordering\(1,1\),\(1,2\)\(1,1\),\(1,2\), write

ek=\[xkyk\]=\[Qk​\(1,1\)Qk​\(1,2\)\]\.e\_\{k\}=\\begin\{bmatrix\}x\_\{k\}\\\\ y\_\{k\}\\end\{bmatrix\}=\\begin\{bmatrix\}Q\_\{k\}\(1,1\)\\\\ Q\_\{k\}\(1,2\)\\end\{bmatrix\}\.The selection matrices are

𝚷π1=\[10\],𝚷π2=\[01\],\\boldsymbol\{\\Pi\}^\{\\pi\_\{1\}\}=\\begin\{bmatrix\}1&0\\end\{bmatrix\},\\qquad\\boldsymbol\{\\Pi\}^\{\\pi\_\{2\}\}=\\begin\{bmatrix\}0&1\\end\{bmatrix\},and

D=\[0\.9000\.1\]\.D=\\begin\{bmatrix\}0\.9&0\\\\ 0&0\.1\\end\{bmatrix\}\.Therefore the two direct modes are

𝐀1:=𝐀π1=\[1−0\.09​α00\.09​α1−0\.1​α\],𝐀2:=𝐀π2=\[1−0\.9​α0\.81​α01−0\.01​α\]\.\\mathbf\{A\}\_\{1\}:=\\mathbf\{A\}\_\{\\pi\_\{1\}\}=\\begin\{bmatrix\}1\-0\.09\\alpha&0\\\\ 0\.09\\alpha&1\-0\.1\\alpha\\end\{bmatrix\},\\qquad\\mathbf\{A\}\_\{2\}:=\\mathbf\{A\}\_\{\\pi\_\{2\}\}=\\begin\{bmatrix\}1\-0\.9\\alpha&0\.81\\alpha\\\\ 0&1\-0\.01\\alpha\\end\{bmatrix\}\.Since these matrices are triangular, their spectral radii are

ρ​\(𝐀1\)=1−0\.09​α,ρ​\(𝐀2\)=1−0\.01​α\.\\rho\(\\mathbf\{A\}\_\{1\}\)=1\-0\.09\\alpha,\\qquad\\rho\(\\mathbf\{A\}\_\{2\}\)=1\-0\.01\\alpha\.Therefore, the optimized negative\-side LTI certificate is

ρ−⋆=minπ∈Θ∗⁡ρ​\(𝐀π\)=1−0\.09​α\.\\rho\_\{\-\}^\{\\star\}=\\min\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\)=1\-0\.09\\alpha\.On the other hand,

‖𝐀1‖∞=‖𝐀2‖∞=1−0\.01​α,\\\|\\mathbf\{A\}\_\{1\}\\\|\_\{\\infty\}=\\\|\\mathbf\{A\}\_\{2\}\\\|\_\{\\infty\}=1\-0\.01\\alpha,hence

ρ​\(\{𝐀1,𝐀2\}\)≤1−0\.01​α\.\\rho\(\\\{\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\\\}\)\\leq 1\-0\.01\\alpha\.Since𝐀2\\mathbf\{A\}\_\{2\}itself has spectral radius1−0\.01​α1\-0\.01\\alpha, we also have

ρ​\(\{𝐀1,𝐀2\}\)≥1−0\.01​α\.\\rho\(\\\{\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\\\}\)\\geq 1\-0\.01\\alpha\.Consequently,

ρ\+=ρ​\(\{𝐀1,𝐀2\}\)=1−0\.01​α,\\rho\_\{\+\}=\\rho\(\\\{\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\}\\\}\)=1\-0\.01\\alpha,and hence

ρ−⋆=1−0\.09​α<1−0\.01​α=ρ\+\.\\rho\_\{\-\}^\{\\star\}=1\-0\.09\\alpha<1\-0\.01\\alpha=\\rho\_\{\+\}\.
Choose

e0=\[−AB\],A\>0,B\>0\.e\_\{0\}=\\begin\{bmatrix\}\-A\\\\ B\\end\{bmatrix\},\\qquad A\>0,\\quad B\>0\.Ifyk\>xky\_\{k\}\>x\_\{k\}, then the Bellman max selects action22, and the recursion is

ek\+1=𝐀2​ek,k∈\{0,1,2,…\}\.e\_\{k\+1\}=\\mathbf\{A\}\_\{2\}e\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Solving this triangular recursion gives

yk=B​\(1−0\.01​α\)k,y\_\{k\}=B\(1\-0\.01\\alpha\)^\{k\},and

xk=8189​B​\(1−0\.01​α\)k−\(A\+8189​B\)​\(1−0\.9​α\)k\.x\_\{k\}=\\frac\{81\}\{89\}B\(1\-0\.01\\alpha\)^\{k\}\-\\left\(A\+\\frac\{81\}\{89\}B\\right\)\(1\-0\.9\\alpha\)^\{k\}\.Moreover,

yk−xk=889​B​\(1−0\.01​α\)k\+\(A\+8189​B\)​\(1−0\.9​α\)k\>0y\_\{k\}\-x\_\{k\}=\\frac\{8\}\{89\}B\(1\-0\.01\\alpha\)^\{k\}\+\\left\(A\+\\frac\{81\}\{89\}B\\right\)\(1\-0\.9\\alpha\)^\{k\}\>0for everyk≥0k\\geq 0\. Hence the branchek\+1=𝐀2​eke\_\{k\+1\}=\\mathbf\{A\}\_\{2\}e\_\{k\}is valid for allk≥0k\\geq 0\. Sinceyk\>0y\_\{k\}\>0andyk\>xky\_\{k\}\>x\_\{k\}, the positive part satisfies

‖ek\+‖∞=yk=B​\(1−0\.01​α\)k\.\\\|e\_\{k\}^\{\+\}\\\|\_\{\\infty\}=y\_\{k\}=B\(1\-0\.01\\alpha\)^\{k\}\.The negative part is

‖ek−‖∞=\(−xk\)\+=\[\(A\+8189​B\)​\(1−0\.9​α\)k−8189​B​\(1−0\.01​α\)k\]\+,\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}=\(\-x\_\{k\}\)^\{\+\}=\\left\[\\left\(A\+\\frac\{81\}\{89\}B\\right\)\(1\-0\.9\\alpha\)^\{k\}\-\\frac\{81\}\{89\}B\(1\-0\.01\\alpha\)^\{k\}\\right\]^\{\+\},and therefore

‖ek−‖∞≤\(A\+8189​B\)​\(1−0\.9​α\)k\.\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\\leq\\left\(A\+\\frac\{81\}\{89\}B\\right\)\(1\-0\.9\\alpha\)^\{k\}\.Consequently, on this deterministic trajectory, the positive part decays exactly at the slow factor1−0\.01​α1\-0\.01\\alpha, whereas the negative part is bounded by the faster\(1−0\.9​α\)\(1\-0\.9\\alpha\)\-geometric term and eventually vanishes\.

The second example clarifies that the certificate asymmetry need not force different realized decay rates on every trajectory\.

###### Example 2\.

The comparison rates above are certificate rates, and they need not imply that one sign component has a strictly faster realized decay on every deterministic trajectory\. The following two\-state, two\-action example gives a simple trajectory on which the positive and negative errors have exactly the same magnitude and the same decay factor\.

Let𝒮=\{1,2\}\\mathcal\{S\}=\\\{1,2\\\}and𝒜=\{1,2\}\\mathcal\{A\}=\\\{1,2\\\}\. For every state and action, let the transition be a self\-loop,

P​\(s∣s,i\)=1,s∈\{1,2\},i∈\{1,2\},P\(s\\mid s,i\)=1,\\qquad s\\in\\\{1,2\\\},\\ i\\in\\\{1,2\\\},and let the rewards be

R​\(s,1\)=0,R​\(s,2\)=−1,s∈\{1,2\}\.R\(s,1\)=0,\\qquad R\(s,2\)=\-1,\\qquad s\\in\\\{1,2\\\}\.Then

V∗​\(s\)=0,Q∗​\(s,1\)=0,Q∗​\(s,2\)=−1,V^\{\*\}\(s\)=0,\\qquad Q^\{\*\}\(s,1\)=0,\\qquad Q^\{\*\}\(s,2\)=\-1,hence action11is the unique optimal action in each state and the action gap of action22is equal to one\. Consider the deterministic recursion[Equation˜3](https://arxiv.org/html/2605.16103#S3.E3)with uniform sampling

d​\(s,i\)=14,s∈\{1,2\},i∈\{1,2\},d\(s,i\)=\\frac\{1\}\{4\},\\qquad s\\in\\\{1,2\\\},\\ i\\in\\\{1,2\\\},step sizeα∈\(0,1\)\\alpha\\in\(0,1\), and discount factorγ=0\.9\\gamma=0\.9\. With the ordering

\(1,1\),\(2,1\),\(1,2\),\(2,2\),\(1,1\),\(2,1\),\(1,2\),\(2,2\),choose

e0=\(c,−c,c,−c\),c\>0\.e\_\{0\}=\(c,\-c,c,\-c\),\\qquad c\>0\.The deterministic error remains on the one\-dimensional symmetric trajectory

ek=\(xk,−xk,xk,−xk\)\.e\_\{k\}=\(x\_\{k\},\-x\_\{k\},x\_\{k\},\-x\_\{k\}\)\.To verify this, suppose the identity holds at timekk\. In state11,

Qk​\(1,1\)=xk,Qk​\(1,2\)=−1\+xk,Q\_\{k\}\(1,1\)=x\_\{k\},\\qquad Q\_\{k\}\(1,2\)=\-1\+x\_\{k\},and henceVQk​\(1\)−V∗​\(1\)=xkV\_\{Q\_\{k\}\}\(1\)\-V^\{\*\}\(1\)=x\_\{k\}\. In state22,

Qk​\(2,1\)=−xk,Qk​\(2,2\)=−1−xk,Q\_\{k\}\(2,1\)=\-x\_\{k\},\\qquad Q\_\{k\}\(2,2\)=\-1\-x\_\{k\},and henceVQk​\(2\)−V∗​\(2\)=−xkV\_\{Q\_\{k\}\}\(2\)\-V^\{\*\}\(2\)=\-x\_\{k\}\. Therefore, for eachi∈\{1,2\}i\\in\\\{1,2\\\},

ek\+1​\(1,i\)\\displaystyle e\_\{k\+1\}\(1,i\)=xk\+α4​\(γ​xk−xk\)=\(1−α​\(1−γ\)4\)​xk,\\displaystyle=x\_\{k\}\+\\frac\{\\alpha\}\{4\}\(\\gamma x\_\{k\}\-x\_\{k\}\)=\\left\(1\-\\frac\{\\alpha\(1\-\\gamma\)\}\{4\}\\right\)x\_\{k\},ek\+1​\(2,i\)\\displaystyle e\_\{k\+1\}\(2,i\)=−xk\+α4​\(−γ​xk\+xk\)=−\(1−α​\(1−γ\)4\)​xk,\\displaystyle=\-x\_\{k\}\+\\frac\{\\alpha\}\{4\}\(\-\\gamma x\_\{k\}\+x\_\{k\}\)=\-\\left\(1\-\\frac\{\\alpha\(1\-\\gamma\)\}\{4\}\\right\)x\_\{k\},fork∈\{0,1,2,…\}k\\in\\\{0,1,2,\\ldots\\\}\. Sinceγ=0\.9\\gamma=0\.9,

1−α​\(1−γ\)4=1−0\.025​α\.1\-\\frac\{\\alpha\(1\-\\gamma\)\}\{4\}=1\-0\.025\\alpha\.Therefore,

xk=\(1−0\.025​α\)k​c,ek=\(1−0\.025​α\)k​\(c,−c,c,−c\)\.x\_\{k\}=\(1\-0\.025\\alpha\)^\{k\}c,\\qquad e\_\{k\}=\(1\-0\.025\\alpha\)^\{k\}\(c,\-c,c,\-c\)\.Consequently,

ek\+=\(1−0\.025​α\)k​\(c,0,c,0\),ek−=\(1−0\.025​α\)k​\(0,c,0,c\),e\_\{k\}^\{\+\}=\(1\-0\.025\\alpha\)^\{k\}\(c,0,c,0\),\\qquad e\_\{k\}^\{\-\}=\(1\-0\.025\\alpha\)^\{k\}\(0,c,0,c\),and hence

‖ek\+‖∞=‖ek−‖∞=\(1−0\.025​α\)k​c,\\\|e\_\{k\}^\{\+\}\\\|\_\{\\infty\}=\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}=\(1\-0\.025\\alpha\)^\{k\}c,while

‖ek\+‖2=‖ek−‖2=2​\(1−0\.025​α\)k​c\.\\\|e\_\{k\}^\{\+\}\\\|\_\{2\}=\\\|e\_\{k\}^\{\-\}\\\|\_\{2\}=\\sqrt\{2\}\\,\(1\-0\.025\\alpha\)^\{k\}c\.For this trajectory, the Bellman\-max residuals vanish\. The realized positive and negative sign components therefore decay with exactly the same factor\. This does not contradict the comparison results above; it shows only that the certified sign\-separated asymmetry is a property of the available comparison envelopes, not a statement that every deterministic trajectory must exhibit strictly faster realized decay ofek−e\_\{k\}^\{\-\}than ofek\+e\_\{k\}^\{\+\}\.

## Appendix CProofs

### C\.1Noise moment bounds

We begin the noise analysis with the boundedness and martingale\-difference estimates needed later\.

###### Lemma 8\.

Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), let

Rmax:=maxs,a,s′⁡\|r​\(s,a,s′\)\|,R\_\{\\max\}:=\\max\_\{s,a,s^\{\\prime\}\}\|r\(s,a,s^\{\\prime\}\)\|,and define

Wmax:=\(1\+\|𝒮\|​\|𝒜\|\)2​\(Rmax\+\(1\+γ\)​max⁡\{‖Q0‖∞,Rmax1−γ\}\)2\.W\_\{\\max\}:=\\left\(1\+\\sqrt\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\\right\)^\{2\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\\right\)^\{2\}\.Then, for everyk∈\{0,1,2,…\}k\\in\\\{0,1,2,\\ldots\\\},

‖Qk‖∞≤max⁡\{‖Q0‖∞,Rmax1−γ\},\\\|Q\_\{k\}\\\|\_\{\\infty\}\\leq\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\},and the incrementwkw\_\{k\}isℱk\+1\\mathcal\{F\}\_\{k\+1\}\-measurable and satisfies

𝔼​\[wk∣ℱk\]=0,𝔼​\[‖wk‖22∣ℱk\]≤Wmax\.\\mathbb\{E\}\[w\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=0,\\qquad\\mathbb\{E\}\[\\\|w\_\{k\}\\\|\_\{2\}^\{2\}\\mid\\mathcal\{F\}\_\{k\}\]\\leq W\_\{\\max\}\.

###### Proof of[Lemma˜8](https://arxiv.org/html/2605.16103#Thmlemma8)\.

Since the state and action spaces are finite,Rmax<∞R\_\{\\max\}<\\infty\. We first prove the pathwise bound onQkQ\_\{k\}\. Suppose

‖Qk‖∞≤max⁡\{‖Q0‖∞,Rmax1−γ\}\.\\\|Q\_\{k\}\\\|\_\{\\infty\}\\leq\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\.If a coordinate is not sampled, it remains unchanged\. If\(sk,ak\)\(s\_\{k\},a\_\{k\}\)is sampled, then

\|Qk\+1​\(sk,ak\)\|\\displaystyle\|Q\_\{k\+1\}\(s\_\{k\},a\_\{k\}\)\|≤\(1−α\)​\|Qk​\(sk,ak\)\|\+α​\(\|rk\+1\|\+γ​maxu⁡\|Qk​\(sk′,u\)\|\)\\displaystyle\\leq\(1\-\\alpha\)\|Q\_\{k\}\(s\_\{k\},a\_\{k\}\)\|\+\\alpha\\left\(\|r\_\{k\+1\}\|\+\\gamma\\max\_\{u\}\|Q\_\{k\}\(s^\{\\prime\}\_\{k\},u\)\|\\right\)≤\(1−α\)​max⁡\{‖Q0‖∞,Rmax1−γ\}\+α​\(Rmax\+γ​max⁡\{‖Q0‖∞,Rmax1−γ\}\)\.\\displaystyle\\leq\(1\-\\alpha\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\+\\alpha\(R\_\{\\max\}\+\\gamma\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\)\.Ifmax⁡\{‖Q0‖∞,Rmax1−γ\}≥Rmax/\(1−γ\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\\geq R\_\{\\max\}/\(1\-\\gamma\), thenRmax\+γ​max⁡\{‖Q0‖∞,Rmax1−γ\}≤max⁡\{‖Q0‖∞,Rmax1−γ\}R\_\{\\max\}\+\\gamma\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\\leq\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}, and therefore\|Qk\+1​\(sk,ak\)\|≤max⁡\{‖Q0‖∞,Rmax1−γ\}\|Q\_\{k\+1\}\(s\_\{k\},a\_\{k\}\)\|\\leq\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\. Since the other coordinates remain bounded bymax⁡\{‖Q0‖∞,Rmax1−γ\}\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}, induction gives‖Qk‖∞≤max⁡\{‖Q0‖∞,Rmax1−γ\}\\\|Q\_\{k\}\\\|\_\{\\infty\}\\leq\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}for allk≥0k\\geq 0\.

The sample temporal\-difference term satisfies

\|rk\+1\+γ​maxu∈𝒜⁡Qk​\(sk′,u\)−Qk​\(sk,ak\)\|≤Rmax\+\(1\+γ\)​max⁡\{‖Q0‖∞,Rmax1−γ\}\.\\left\|r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}Q\_\{k\}\(s^\{\\prime\}\_\{k\},u\)\-Q\_\{k\}\(s\_\{k\},a\_\{k\}\)\\right\|\\leq R\_\{\\max\}\+\(1\+\\gamma\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\.Also, for every coordinate,

\|R\(s,a\)\+γ∑s′P\(s′∣s,a\)VQk\(s′\)−Qk\(s,a\)\|≤Rmax\+\(1\+γ\)max\{∥Q0∥∞,Rmax1−γ\}\.\\left\|R\(s,a\)\+\\gamma\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\\mid s,a\)V\_\{Q\_\{k\}\}\(s^\{\\prime\}\)\-Q\_\{k\}\(s,a\)\\right\|\\leq R\_\{\\max\}\+\(1\+\\gamma\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\.Because0<d​\(s,a\)≤10<d\(s,a\)\\leq 1, this implies

‖D​\(F​\(Qk\)−Qk\)‖2≤\|𝒮\|​\|𝒜\|​\(Rmax\+\(1\+γ\)​max⁡\{‖Q0‖∞,Rmax1−γ\}\)\.\\left\\\|D\(F\(Q\_\{k\}\)\-Q\_\{k\}\)\\right\\\|\_\{2\}\\leq\\sqrt\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\\right\)\.The sampled vector in[Equation˜1](https://arxiv.org/html/2605.16103#S2.E1)has Euclidean norm at mostRmax\+\(1\+γ\)​max⁡\{‖Q0‖∞,Rmax1−γ\}R\_\{\\max\}\+\(1\+\\gamma\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\. Hence, pathwise,

‖wk‖2≤\(1\+\|𝒮\|​\|𝒜\|\)​\(Rmax\+\(1\+γ\)​max⁡\{‖Q0‖∞,Rmax1−γ\}\),\\\|w\_\{k\}\\\|\_\{2\}\\leq\\left\(1\+\\sqrt\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\\right\)\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\\right\),and therefore

𝔼​\[‖wk‖22∣ℱk\]≤\(1\+\|𝒮\|​\|𝒜\|\)2​\(Rmax\+\(1\+γ\)​max⁡\{‖Q0‖∞,Rmax1−γ\}\)2=Wmax\.\\mathbb\{E\}\[\\\|w\_\{k\}\\\|\_\{2\}^\{2\}\\mid\\mathcal\{F\}\_\{k\}\]\\leq\\left\(1\+\\sqrt\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\\right\)^\{2\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\max\\left\\\{\\\|Q\_\{0\}\\\|\_\{\\infty\},\\frac\{R\_\{\\max\}\}\{1\-\\gamma\}\\right\\\}\\right\)^\{2\}=W\_\{\\max\}\.Theℱk\+1\\mathcal\{F\}\_\{k\+1\}\-measurability follows from the fact that the fresh observation is revealed between timeskkandk\+1k\+1, whileD​\(F​\(Qk\)−Qk\)D\(F\(Q\_\{k\}\)\-Q\_\{k\}\)isℱk\\mathcal\{F\}\_\{k\}\-measurable\. Finally, using conditional independence of the fresh observation fromℱk\\mathcal\{F\}\_\{k\},

𝔼\[esk,ak\(rk\+1\+γmaxu∈𝒜Qk\(sk′,u\)−Qk\(sk,ak\)\)\|ℱk\]\\displaystyle\\mathbb\{E\}\\\!\\left\[e\_\{s\_\{k\},a\_\{k\}\}\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}Q\_\{k\}\(s^\{\\prime\}\_\{k\},u\)\-Q\_\{k\}\(s\_\{k\},a\_\{k\}\)\\right\)\\middle\|\\mathcal\{F\}\_\{k\}\\right\]=∑s∈𝒮∑a∈𝒜d​\(s,a\)​es,a​\(R​\(s,a\)\+γ​∑s′∈𝒮P​\(s′∣s,a\)​VQk​\(s′\)−Qk​\(s,a\)\)\\displaystyle\\quad=\\sum\_\{s\\in\\mathcal\{S\}\}\\sum\_\{a\\in\\mathcal\{A\}\}d\(s,a\)e\_\{s,a\}\\left\(R\(s,a\)\+\\gamma\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}P\(s^\{\\prime\}\\mid s,a\)V\_\{Q\_\{k\}\}\(s^\{\\prime\}\)\-Q\_\{k\}\(s,a\)\\right\)=D​\(F​\(Qk\)−Qk\)\.\\displaystyle\\quad=D\(F\(Q\_\{k\}\)\-Q\_\{k\}\)\.Together with the definition ofwkw\_\{k\}, this gives𝔼​\[wk∣ℱk\]=0\\mathbb\{E\}\[w\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=0\. ∎

The next lemma transfers the same second\-moment control to the positive and negative noise components\.

###### Lemma 9\.

Under the conditions of[Lemma˜8](https://arxiv.org/html/2605.16103#Thmlemma8), for everyk∈\{0,1,2,…\}k\\in\\\{0,1,2,\\ldots\\\},

𝔼​\[‖wk−‖22∣ℱk\]≤Wmax,𝔼​\[‖wk\+‖22∣ℱk\]≤Wmax\.\\mathbb\{E\}\[\\\|w\_\{k\}^\{\-\}\\\|\_\{2\}^\{2\}\\mid\\mathcal\{F\}\_\{k\}\]\\leq W\_\{\\max\},\\qquad\\mathbb\{E\}\[\\\|w\_\{k\}^\{\+\}\\\|\_\{2\}^\{2\}\\mid\\mathcal\{F\}\_\{k\}\]\\leq W\_\{\\max\}\.

###### Proof of[Lemma˜9](https://arxiv.org/html/2605.16103#Thmlemma9)\.

Componentwise,

0≤\(wk,i−\)2≤wk,i2,0≤\(wk,i\+\)2≤wk,i2\.0\\leq\(w\_\{k,i\}^\{\-\}\)^\{2\}\\leq w\_\{k,i\}^\{2\},\\qquad 0\\leq\(w\_\{k,i\}^\{\+\}\)^\{2\}\\leq w\_\{k,i\}^\{2\}\.Indeed, ifwk,i≥0w\_\{k,i\}\\geq 0, thenwk,i−=0w\_\{k,i\}^\{\-\}=0and\(wk,i\+\)2=wk,i2\(w\_\{k,i\}^\{\+\}\)^\{2\}=w\_\{k,i\}^\{2\}\. Ifwk,i<0w\_\{k,i\}<0, then\(wk,i−\)2=wk,i2\(w\_\{k,i\}^\{\-\}\)^\{2\}=w\_\{k,i\}^\{2\}andwk,i\+=0w\_\{k,i\}^\{\+\}=0\. Hence each signed\-part square is either zero or exactlywk,i2w\_\{k,i\}^\{2\}\. Summing over coordinates gives‖wk−‖22≤‖wk‖22\\\|w\_\{k\}^\{\-\}\\\|\_\{2\}^\{2\}\\leq\\\|w\_\{k\}\\\|\_\{2\}^\{2\}and‖wk\+‖22≤‖wk‖22\\\|w\_\{k\}^\{\+\}\\\|\_\{2\}^\{2\}\\leq\\\|w\_\{k\}\\\|\_\{2\}^\{2\}\. Taking conditional expectations and applying[Lemma˜8](https://arxiv.org/html/2605.16103#Thmlemma8)proves the claim\. ∎

### C\.2Deterministic comparison lemmas

For anyQQande=Q−Q∗e=Q\-Q^\{\*\}, the Bellman\-max term can be expanded state by state as

VQ​\(s\)−V∗​\(s\)\\displaystyle V\_\{Q\}\(s\)\-V^\{\*\}\(s\)=maxa∈𝒜⁡\{Q∗​\(s,a\)\+e​\(s,a\)\}−V∗​\(s\)\\displaystyle=\\max\_\{a\\in\\mathcal\{A\}\}\\\{Q^\{\*\}\(s,a\)\+e\(s,a\)\\\}\-V^\{\*\}\(s\)=maxa∈𝒜⁡\{e​\(s,a\)−A∗​\(s,a\)\}\.\\displaystyle=\\max\_\{a\\in\\mathcal\{A\}\}\\\{e\(s,a\)\-A^\{\*\}\(s,a\)\\\}\.Ifπ∈Θ∗\\pi\\in\\Theta^\{\*\}, thenA∗​\(s,π​\(s\)\)=0A^\{\*\}\(s,\\pi\(s\)\)=0, and therefore

VQ−V∗−𝚷π​e≥0\.V\_\{Q\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\}e\\geq 0\.For the upper comparison, ifπ\+​\(s\)∈arg​maxa∈𝒜⁡e​\(s,a\)\\pi^\{\+\}\(s\)\\in\\operatorname\{arg\\,max\}\_\{a\\in\\mathcal\{A\}\}e\(s,a\), thenA∗​\(s,a\)≥0A^\{\*\}\(s,a\)\\geq 0gives

𝚷π\+​e−\(VQ−V∗\)≥0\.\\boldsymbol\{\\Pi\}^\{\\pi^\{\+\}\}e\-\(V\_\{Q\}\-V^\{\*\}\)\\geq 0\.Substituting these two decompositions into the deterministic error recursion produces the lower and upper residual identities below\.

The first deterministic comparison lemma records the lower residual identity and its sign\.

###### Lemma 10\.

Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), the deterministic error recursion satisfies

ek\+1=𝐀−⋆​ek\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\),k∈\{0,1,2,…\},e\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\),\\qquad k\\in\\\{0,1,2,\\ldots\\\},and

VQk−V∗−𝚷π−⋆​ek≥0\.V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\geq 0\.

###### Proof of[Lemma˜10](https://arxiv.org/html/2605.16103#Thmlemma10)\.

For each statess, becauseπ−⋆∈Θ∗\\pi\_\{\-\}^\{\\star\}\\in\\Theta^\{\*\}, we haveQ∗​\(s,π−⋆​\(s\)\)=V∗​\(s\)Q^\{\*\}\(s,\\pi\_\{\-\}^\{\\star\}\(s\)\)=V^\{\*\}\(s\)\. Hence

VQk​\(s\)−V∗​\(s\)−ek​\(s,π−⋆​\(s\)\)\\displaystyle V\_\{Q\_\{k\}\}\(s\)\-V^\{\*\}\(s\)\-e\_\{k\}\(s,\\pi\_\{\-\}^\{\\star\}\(s\)\)=maxa∈𝒜⁡\{Q∗​\(s,a\)\+ek​\(s,a\)\}−V∗​\(s\)−ek​\(s,π−⋆​\(s\)\)\\displaystyle=\\max\_\{a\\in\\mathcal\{A\}\}\\\{Q^\{\*\}\(s,a\)\+e\_\{k\}\(s,a\)\\\}\-V^\{\*\}\(s\)\-e\_\{k\}\(s,\\pi\_\{\-\}^\{\\star\}\(s\)\)≥Q∗​\(s,π−⋆​\(s\)\)\+ek​\(s,π−⋆​\(s\)\)−V∗​\(s\)−ek​\(s,π−⋆​\(s\)\)\\displaystyle\\geq Q^\{\*\}\(s,\\pi\_\{\-\}^\{\\star\}\(s\)\)\+e\_\{k\}\(s,\\pi\_\{\-\}^\{\\star\}\(s\)\)\-V^\{\*\}\(s\)\-e\_\{k\}\(s,\\pi\_\{\-\}^\{\\star\}\(s\)\)=0\.\\displaystyle=0\.Using

VQk−V∗=𝚷π−⋆​ek\+\(VQk−V∗−𝚷π−⋆​ek\)V\_\{Q\_\{k\}\}\-V^\{\*\}=\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\+\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)in[Equation˜3](https://arxiv.org/html/2605.16103#S3.E3), we obtain

ek\+1\\displaystyle e\_\{k\+1\}=ek\+α​D​\{γ​P​𝚷π−⋆​ek−ek\}\\displaystyle=e\_\{k\}\+\\alpha D\\\{\\gamma P\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\-e\_\{k\}\\\}\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\\displaystyle\\quad\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)=\(I−α​D\+α​γ​D​P​𝚷π−⋆\)​ek\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\\displaystyle=\\bigl\(I\-\\alpha D\+\\alpha\\gamma DP\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}\\bigr\)e\_\{k\}\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)=𝐀−⋆​ek\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\.\\displaystyle=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)\.This proves the lower residual identity\. ∎

The next lemma records the corresponding upper residual identity\.

###### Lemma 11\.

Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), the deterministic error recursion satisfies

ek\+1=𝐀πk\+​ek−α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\),k∈\{0,1,2,…\},e\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\),\\qquad k\\in\\\{0,1,2,\\ldots\\\},where

πk\+​\(s\)∈arg​maxa∈𝒜⁡ek​\(s,a\),s∈𝒮,\\pi\_\{k\}^\{\+\}\(s\)\\in\\operatorname\{arg\\,max\}\_\{a\\in\\mathcal\{A\}\}e\_\{k\}\(s,a\),\\qquad s\\in\\mathcal\{S\},and

𝚷πk\+​ek−\(VQk−V∗\)≥0\.\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\geq 0\.

###### Proof of[Lemma˜11](https://arxiv.org/html/2605.16103#Thmlemma11)\.

SinceA∗​\(s,a\)=V∗​\(s\)−Q∗​\(s,a\)≥0A^\{\*\}\(s,a\)=V^\{\*\}\(s\)\-Q^\{\*\}\(s,a\)\\geq 0, we have

VQk​\(s\)−V∗​\(s\)=maxa∈𝒜⁡\{ek​\(s,a\)−A∗​\(s,a\)\}≤maxa∈𝒜⁡ek​\(s,a\)=ek​\(s,πk\+​\(s\)\)\.V\_\{Q\_\{k\}\}\(s\)\-V^\{\*\}\(s\)=\\max\_\{a\\in\\mathcal\{A\}\}\\\{e\_\{k\}\(s,a\)\-A^\{\*\}\(s,a\)\\\}\\leq\\max\_\{a\\in\\mathcal\{A\}\}e\_\{k\}\(s,a\)=e\_\{k\}\(s,\\pi\_\{k\}^\{\+\}\(s\)\)\.Therefore,𝚷πk\+​ek−\(VQk−V∗\)≥0\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\geq 0\. Using

VQk−V∗=𝚷πk\+​ek−\(𝚷πk\+​ek−\(VQk−V∗\)\)V\_\{Q\_\{k\}\}\-V^\{\*\}=\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)in[Equation˜3](https://arxiv.org/html/2605.16103#S3.E3), we obtain

ek\+1\\displaystyle e\_\{k\+1\}=ek\+α​D​\{γ​P​𝚷πk\+​ek−ek\}\\displaystyle=e\_\{k\}\+\\alpha D\\\{\\gamma P\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-e\_\{k\}\\\}−α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)\\displaystyle\\quad\-\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)=\(I−α​D\+α​γ​D​P​𝚷πk\+\)​ek−α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)\\displaystyle=\\bigl\(I\-\\alpha D\+\\alpha\\gamma DP\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}\\bigr\)e\_\{k\}\-\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)=𝐀πk\+​ek−α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)\.\\displaystyle=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)\.This proves the upper residual identity\. ∎

Combining the two one\-sided comparisons gives the main deterministic order statement\.

\{restatementbox\}

Restatement of[Lemma˜2](https://arxiv.org/html/2605.16103#Thmlemma2)\.Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), withℓk\\ell\_\{k\}anduku\_\{k\}defined in[Equations˜4](https://arxiv.org/html/2605.16103#S3.E4)and[5](https://arxiv.org/html/2605.16103#S3.E5),

ℓk≤ek≤uk,k∈\{0,1,2,…\}\.\\ell\_\{k\}\\leq e\_\{k\}\\leq u\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.
###### Proof of[Lemma˜2](https://arxiv.org/html/2605.16103#Thmlemma2)\.

We prove the two inequalities directly from the residual identities\. First, set

δk:=ek−ℓk\.\\delta\_\{k\}:=e\_\{k\}\-\\ell\_\{k\}\.Using[Lemma˜10](https://arxiv.org/html/2605.16103#Thmlemma10)and the lower comparison recursion in[Equation˜4](https://arxiv.org/html/2605.16103#S3.E4), we obtain

δk\+1\\displaystyle\\delta\_\{k\+1\}=ek\+1−ℓk\+1\\displaystyle=e\_\{k\+1\}\-\\ell\_\{k\+1\}=\[𝐀−⋆​ek\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\]−𝐀−⋆​ℓk\\displaystyle=\\left\[\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)\\right\]\-\\mathbf\{A\}\_\{\-\}^\{\\star\}\\ell\_\{k\}=𝐀−⋆​\(ek−ℓk\)\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\\displaystyle=\\mathbf\{A\}\_\{\-\}^\{\\star\}\(e\_\{k\}\-\\ell\_\{k\}\)\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)=𝐀−⋆​δk\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\.\\displaystyle=\\mathbf\{A\}\_\{\-\}^\{\\star\}\\delta\_\{k\}\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)\.Sinceδ0=e0−ℓ0=0\\delta\_\{0\}=e\_\{0\}\-\\ell\_\{0\}=0,𝐀−⋆≥0\\mathbf\{A\}\_\{\-\}^\{\\star\}\\geq 0,D≥0D\\geq 0,P≥0P\\geq 0, and

VQk−V∗−𝚷π−⋆​ek≥0,V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\geq 0,induction givesδk≥0\\delta\_\{k\}\\geq 0, that is,

ℓk≤ek,k∈\{0,1,2,…\}\.\\ell\_\{k\}\\leq e\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.
Second, set

qk:=uk−ek\.q\_\{k\}:=u\_\{k\}\-e\_\{k\}\.Using[Lemma˜11](https://arxiv.org/html/2605.16103#Thmlemma11)and the upper comparison recursion in[Equation˜5](https://arxiv.org/html/2605.16103#S3.E5), we obtain

qk\+1\\displaystyle q\_\{k\+1\}=uk\+1−ek\+1\\displaystyle=u\_\{k\+1\}\-e\_\{k\+1\}=𝐀πk\+​uk−\[𝐀πk\+​ek−α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)\]\\displaystyle=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}u\_\{k\}\-\\left\[\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)\\right\]=𝐀πk\+​\(uk−ek\)\+α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)\\displaystyle=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}\(u\_\{k\}\-e\_\{k\}\)\+\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)=𝐀πk\+​qk\+α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)\.\\displaystyle=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}q\_\{k\}\+\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)\.Sinceq0=u0−e0=0q\_\{0\}=u\_\{0\}\-e\_\{0\}=0,𝐀πk\+≥0\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}\\geq 0,D≥0D\\geq 0,P≥0P\\geq 0, and

𝚷πk\+​ek−\(VQk−V∗\)≥0,\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\geq 0,induction givesqk≥0q\_\{k\}\\geq 0, that is,

ek≤uk,k∈\{0,1,2,…\}\.e\_\{k\}\\leq u\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Combining the two inequalities yields

ℓk≤ek≤uk,k∈\{0,1,2,…\}\.\\ell\_\{k\}\\leq e\_\{k\}\\leq u\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.∎

The following lemma connects these order comparisons to the componentwise sign parts\.

###### Lemma 12\.

Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), withℓk\\ell\_\{k\}anduku\_\{k\}defined in[Equations˜4](https://arxiv.org/html/2605.16103#S3.E4)and[5](https://arxiv.org/html/2605.16103#S3.E5),

ek−≤ℓk−,ek\+≤uk\+,k∈\{0,1,2,…\}\.e\_\{k\}^\{\-\}\\leq\\ell\_\{k\}^\{\-\},\\qquad e\_\{k\}^\{\+\}\\leq u\_\{k\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.

###### Proof of[Lemma˜12](https://arxiv.org/html/2605.16103#Thmlemma12)\.

Fix a coordinateiiand a timekk\. From[Lemma˜2](https://arxiv.org/html/2605.16103#Thmlemma2),

ℓk,i≤ek,i≤uk,i\.\\ell\_\{k,i\}\\leq e\_\{k,i\}\\leq u\_\{k,i\}\.The positive\-part mapx↦x\+=max⁡\{x,0\}x\\mapsto x^\{\+\}=\\max\\\{x,0\\\}is monotone increasing onℝ\\mathbb\{R\}\. Therefore, the upper comparison inequality gives

ek,i\+=\(ek,i\)\+≤\(uk,i\)\+=uk,i\+\.e\_\{k,i\}^\{\+\}=\(e\_\{k,i\}\)^\{\+\}\\leq\(u\_\{k,i\}\)^\{\+\}=u\_\{k,i\}^\{\+\}\.For the negative part, the lower comparison inequalityℓk,i≤ek,i\\ell\_\{k,i\}\\leq e\_\{k,i\}implies

−ek,i≤−ℓk,i\.\-e\_\{k,i\}\\leq\-\\ell\_\{k,i\}\.Applying the same monotonicity to the positive\-part map gives

ek,i−=\(−ek,i\)\+≤\(−ℓk,i\)\+=ℓk,i−\.e\_\{k,i\}^\{\-\}=\(\-e\_\{k,i\}\)^\{\+\}\\leq\(\-\\ell\_\{k,i\}\)^\{\+\}=\\ell\_\{k,i\}^\{\-\}\.Since the coordinateiiwas arbitrary, these scalar inequalities hold componentwise, and hence

ek−≤ℓk−,ek\+≤uk\+,k∈\{0,1,2,…\}\.e\_\{k\}^\{\-\}\\leq\\ell\_\{k\}^\{\-\},\\qquad e\_\{k\}^\{\+\}\\leq u\_\{k\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.∎

The next lemma gives the one\-step sign domination that drives the sign\-separated systems\.

###### Lemma 13\.

Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), the deterministic negative part satisfies

ek\+1−≤𝐀−⋆​ek−,k∈\{0,1,2,…\},e\_\{k\+1\}^\{\-\}\\leq\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},and the deterministic positive part satisfies

ek\+1\+≤𝐀πk\+​ek\+,k∈\{0,1,2,…\}\.e\_\{k\+1\}^\{\+\}\\leq\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.

###### Proof of[Lemma˜13](https://arxiv.org/html/2605.16103#Thmlemma13)\.

From[Lemma˜10](https://arxiv.org/html/2605.16103#Thmlemma10)andek=ek\+−ek−e\_\{k\}=e\_\{k\}^\{\+\}\-e\_\{k\}^\{\-\},

ek\+1=𝐀−⋆​ek\+−𝐀−⋆​ek−\+rk−,rk−:=α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)≥0\.e\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\+\}\-\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\+r\_\{k\}^\{\-\},\\qquad r\_\{k\}^\{\-\}:=\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)\\geq 0\.Because𝐀−⋆≥0\\mathbf\{A\}\_\{\-\}^\{\\star\}\\geq 0andek\+,ek−≥0e\_\{k\}^\{\+\},e\_\{k\}^\{\-\}\\geq 0, the vectors

ak−:=𝐀−⋆​ek\+\+rk−,bk−:=𝐀−⋆​ek−a\_\{k\}^\{\-\}:=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\+\}\+r\_\{k\}^\{\-\},\\qquad b\_\{k\}^\{\-\}:=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}are nonnegative and satisfyek\+1=ak−−bk−e\_\{k\+1\}=a\_\{k\}^\{\-\}\-b\_\{k\}^\{\-\}\. Hence, component by component,

\(ek\+1,i\)−=\(bk,i−−ak,i−\)\+≤bk,i−\.\(e\_\{k\+1,i\}\)^\{\-\}=\(b\_\{k,i\}^\{\-\}\-a\_\{k,i\}^\{\-\}\)^\{\+\}\\leq b\_\{k,i\}^\{\-\}\.Thus,

ek\+1−≤bk−=𝐀−⋆​ek−\.e\_\{k\+1\}^\{\-\}\\leq b\_\{k\}^\{\-\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\.Similarly, from[Lemma˜11](https://arxiv.org/html/2605.16103#Thmlemma11),

ek\+1=𝐀πk\+​ek\+−𝐀πk\+​ek−−rk\+,rk\+:=α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)≥0\.e\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\-\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\-\}\-r\_\{k\}^\{\+\},\\qquad r\_\{k\}^\{\+\}:=\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)\\geq 0\.Set

ak\+:=𝐀πk\+​ek\+,bk\+:=𝐀πk\+​ek−\+rk\+\.a\_\{k\}^\{\+\}:=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\},\\qquad b\_\{k\}^\{\+\}:=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\-\}\+r\_\{k\}^\{\+\}\.Thenak\+,bk\+≥0a\_\{k\}^\{\+\},b\_\{k\}^\{\+\}\\geq 0andek\+1=ak\+−bk\+e\_\{k\+1\}=a\_\{k\}^\{\+\}\-b\_\{k\}^\{\+\}\. Hence

\(ek\+1,i\)\+=\(ak,i\+−bk,i\+\)\+≤ak,i\+,\(e\_\{k\+1,i\}\)^\{\+\}=\(a\_\{k,i\}^\{\+\}\-b\_\{k,i\}^\{\+\}\)^\{\+\}\\leq a\_\{k,i\}^\{\+\},which yields

ek\+1\+≤ak\+=𝐀πk\+​ek\+\.e\_\{k\+1\}^\{\+\}\\leq a\_\{k\}^\{\+\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\.∎

The pathwise deterministic sign comparison now follows by induction\.

\{restatementbox\}

Restatement of[Lemma˜3](https://arxiv.org/html/2605.16103#Thmlemma3)\.Under[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), ifzk−z^\{\-\}\_\{k\}andzk\+z^\{\+\}\_\{k\}are defined by[Equations˜6](https://arxiv.org/html/2605.16103#S3.E6)and[7](https://arxiv.org/html/2605.16103#S3.E7), then

ek−≤zk−,ek\+≤zk\+,k∈\{0,1,2,…\}\.e\_\{k\}^\{\-\}\\leq z^\{\-\}\_\{k\},\\qquad e\_\{k\}^\{\+\}\\leq z^\{\+\}\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.
###### Proof of[Lemma˜3](https://arxiv.org/html/2605.16103#Thmlemma3)\.

Atk=0k=0, the inequalities hold by definition\. If they hold at timekk, then[Lemma˜13](https://arxiv.org/html/2605.16103#Thmlemma13)and the nonnegativity of𝐀−⋆\\mathbf\{A\}\_\{\-\}^\{\\star\}and𝐀πk\+\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}give the inequalities at timek\+1k\+1\. The result follows by induction\. ∎

### C\.3Deterministic finite\-time proofs

We now prove the deterministic negative\-side finite\-time bound\.

\{restatementbox\}

Restatement of[Theorem˜1](https://arxiv.org/html/2605.16103#Thmtheorem1)\.Assume[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1)\. Fixε\>0\\varepsilon\>0such that

ρ−⋆\+ε<1,\\rho\_\{\-\}^\{\\star\}\+\\varepsilon<1,and defineβ−:=ρ−⋆\+ε\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilon\. Let

v−⋆​\(x\):=∑t=0∞β−−2​t​‖\(𝐀−⋆\)t​x‖22,v\_\{\-\}^\{\\star\}\(x\):=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\-\}^\{\-2t\}\\\|\(\\mathbf\{A\}\_\{\-\}^\{\\star\}\)^\{t\}x\\\|\_\{2\}^\{2\},and letC−⋆≥1C\_\{\-\}^\{\\star\}\\geq 1be the fixed\-mode norm\-equivalence constant associated withv−⋆v\_\{\-\}^\{\\star\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, satisfying

‖x‖22≤v−⋆​\(x\)≤C−⋆​‖x‖22\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\-\}^\{\\star\}\(x\)\\leq C\_\{\-\}^\{\\star\}\\\|x\\\|\_\{2\}^\{2\}\.Then, for everyk≥0k\\geq 0,

‖ek−‖∞≤C−⋆​β−k​‖e0−‖2\.\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\.Consequently, the deterministic negative part is certified at the optimized single\-policy LTI rate

ρ−⋆=minπ∈Θ∗⁡ρ​\(𝐀π\)\.\\rho\_\{\-\}^\{\\star\}=\\min\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\)\.
###### Proof of[Theorem˜1](https://arxiv.org/html/2605.16103#Thmtheorem1)\.

For the negative side,[Equation˜6](https://arxiv.org/html/2605.16103#S3.E6)and the definition ofv−⋆v\_\{\-\}^\{\\star\}give

v−⋆​\(zk\+1−\)=v−⋆​\(𝐀−⋆​zk−\)≤β−2​v−⋆​\(zk−\)\.v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\+1\}\)=v\_\{\-\}^\{\\star\}\(\\mathbf\{A\}\_\{\-\}^\{\\star\}z^\{\-\}\_\{k\}\)\\leq\\beta\_\{\-\}^\{2\}v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\}\)\.Iterating and usingz0−=e0−z^\{\-\}\_\{0\}=e\_\{0\}^\{\-\},

v−⋆​\(zk−\)≤β−2​k​v−⋆​\(e0−\)≤C−⋆​β−2​k​‖e0−‖22\.v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\}\)\\leq\\beta\_\{\-\}^\{2k\}v\_\{\-\}^\{\\star\}\(e\_\{0\}^\{\-\}\)\\leq C\_\{\-\}^\{\\star\}\\beta\_\{\-\}^\{2k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}^\{2\}\.By[Lemma˜3](https://arxiv.org/html/2605.16103#Thmlemma3),

‖ek−‖∞≤‖zk−‖∞≤‖zk−‖2≤v−⋆​\(zk−\),\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\\leq\\\|z^\{\-\}\_\{k\}\\\|\_\{\\infty\}\\leq\\\|z^\{\-\}\_\{k\}\\\|\_\{2\}\\leq\\sqrt\{v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\}\)\},which proves[Equation˜8](https://arxiv.org/html/2605.16103#S3.E8)\. ∎

The positive\-side deterministic bound uses the product\-defined switching Lyapunov function\.

\{restatementbox\}

Restatement of[Theorem˜2](https://arxiv.org/html/2605.16103#Thmtheorem2)\.Assume[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1)\. Fixε\>0\\varepsilon\>0such that

ρ\+\+ε<1,\\rho\_\{\+\}\+\\varepsilon<1,and defineβ\+:=ρ\+\+ε\\beta\_\{\+\}:=\\rho\_\{\+\}\+\\varepsilon\. Let

v\+​\(x\):=∑t=0∞β\+−2​t​maxπ0,…,πt−1∈Θ⁡‖𝐀πt−1​⋯​𝐀π0​x‖22,v\_\{\+\}\(x\):=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\+\}^\{\-2t\}\\max\_\{\\pi\_\{0\},\\ldots,\\pi\_\{t\-1\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{t\-1\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{0\}\}x\\right\\\|\_\{2\}^\{2\},where thet=0t=0product is the identity, and letC\+≥1C\_\{\+\}\\geq 1be the product\-family norm\-equivalence constant associated withv\+v\_\{\+\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, satisfying

‖x‖22≤v\+​\(x\)≤C\+​‖x‖22\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\+\}\(x\)\\leq C\_\{\+\}\\\|x\\\|\_\{2\}^\{2\}\.Then, for everyk≥0k\\geq 0,

‖ek\+‖∞≤C\+​β\+k​‖e0\+‖2\.\\\|e\_\{k\}^\{\+\}\\\|\_\{\\infty\}\\leq\\sqrt\{C\_\{\+\}\}\\,\\beta\_\{\+\}^\{k\}\\\|e\_\{0\}^\{\+\}\\\|\_\{2\}\.Consequently, the deterministic positive part is certified at the full direct switching rate

ρ\+=ραdir=ρ​\(\{𝐀π:π∈Θ\}\)\.\\rho\_\{\+\}=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=\\rho\(\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta\\\}\)\.
###### Proof of[Theorem˜2](https://arxiv.org/html/2605.16103#Thmtheorem2)\.

The product\-defined Lyapunov function satisfies

v\+​\(𝐀π​x\)≤β\+2​v\+​\(x\),∀π∈Θ\.v\_\{\+\}\(\\mathbf\{A\}\_\{\\pi\}x\)\\leq\\beta\_\{\+\}^\{2\}v\_\{\+\}\(x\),\\qquad\\forall\\pi\\in\\Theta\.Therefore, along the deterministic switching signalπk\+\\pi\_\{k\}^\{\+\},

v\+​\(zk\+1\+\)=v\+​\(𝐀πk\+​zk\+\)≤β\+2​v\+​\(zk\+\)\.v\_\{\+\}\(z^\{\+\}\_\{k\+1\}\)=v\_\{\+\}\(\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}z^\{\+\}\_\{k\}\)\\leq\\beta\_\{\+\}^\{2\}v\_\{\+\}\(z^\{\+\}\_\{k\}\)\.Iterating and usingz0\+=e0\+z^\{\+\}\_\{0\}=e\_\{0\}^\{\+\},

v\+​\(zk\+\)≤β\+2​k​v\+​\(e0\+\)≤C\+​β\+2​k​‖e0\+‖22\.v\_\{\+\}\(z^\{\+\}\_\{k\}\)\\leq\\beta\_\{\+\}^\{2k\}v\_\{\+\}\(e\_\{0\}^\{\+\}\)\\leq C\_\{\+\}\\beta\_\{\+\}^\{2k\}\\\|e\_\{0\}^\{\+\}\\\|\_\{2\}^\{2\}\.By[Lemma˜3](https://arxiv.org/html/2605.16103#Thmlemma3),

‖ek\+‖∞≤‖zk\+‖∞≤‖zk\+‖2≤v\+​\(zk\+\),\\\|e\_\{k\}^\{\+\}\\\|\_\{\\infty\}\\leq\\\|z^\{\+\}\_\{k\}\\\|\_\{\\infty\}\\leq\\\|z^\{\+\}\_\{k\}\\\|\_\{2\}\\leq\\sqrt\{v\_\{\+\}\(z^\{\+\}\_\{k\}\)\},which proves[Equation˜9](https://arxiv.org/html/2605.16103#S3.E9)\. ∎

The deterministic orthant\-distance estimate is an immediate consequence of the negative\-part bound\.

\{restatementbox\}

Restatement of[Corollary˜1](https://arxiv.org/html/2605.16103#Thmcorollary1)\.Let

ℝ\+\|𝒮\|​\|𝒜\|:=\{x∈ℝ\|𝒮\|​\|𝒜\|:x≥0\}\.\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}:=\\\{x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}:x\\geq 0\\\}\.Under the assumptions of[Theorem˜1](https://arxiv.org/html/2605.16103#Thmtheorem1), for everyε\>0\\varepsilon\>0satisfyingρ−⋆\+ε<1\\rho\_\{\-\}^\{\\star\}\+\\varepsilon<1, withβ−:=ρ−⋆\+ε\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilonand with the same fixed\-mode norm\-equivalence constantC−⋆C\_\{\-\}^\{\\star\}associated withv−⋆v\_\{\-\}^\{\\star\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, everyk≥0k\\geq 0satisfies

dist∞⁡\(ek,ℝ\+\|𝒮\|​\|𝒜\|\)≤C−⋆​β−k​‖e0−‖2\.\\operatorname\{dist\}\_\{\\infty\}\(e\_\{k\},\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\)\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\.
###### Proof of[Corollary˜1](https://arxiv.org/html/2605.16103#Thmcorollary1)\.

Letn:=\|𝒮\|​\|𝒜\|n:=\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\. We first compute the distance to the nonnegative orthant\. For anyx∈ℝnx\\in\\mathbb\{R\}^\{n\}and anyy∈ℝ\+ny\\in\\mathbb\{R\}\_\{\+\}^\{n\}, ifxi<0x\_\{i\}<0, thenyi≥0y\_\{i\}\\geq 0and therefore

\|xi−yi\|≥−xi=xi−\.\|x\_\{i\}\-y\_\{i\}\|\\geq\-x\_\{i\}=x\_\{i\}^\{\-\}\.Taking the maximum over coordinates and then the infimum overy∈ℝ\+ny\\in\\mathbb\{R\}\_\{\+\}^\{n\}gives

dist∞⁡\(x,ℝ\+n\)=infy∈ℝ\+n‖x−y‖∞≥‖x−‖∞\.\\operatorname\{dist\}\_\{\\infty\}\(x,\\mathbb\{R\}\_\{\+\}^\{n\}\)=\\inf\_\{y\\in\\mathbb\{R\}\_\{\+\}^\{n\}\}\\\|x\-y\\\|\_\{\\infty\}\\geq\\\|x^\{\-\}\\\|\_\{\\infty\}\.On the other hand, choosey=x\+∈ℝ\+ny=x^\{\+\}\\in\\mathbb\{R\}\_\{\+\}^\{n\}\. Since

we have

dist∞⁡\(x,ℝ\+n\)≤‖x−x\+‖∞=‖x−‖∞\.\\operatorname\{dist\}\_\{\\infty\}\(x,\\mathbb\{R\}\_\{\+\}^\{n\}\)\\leq\\\|x\-x^\{\+\}\\\|\_\{\\infty\}=\\\|x^\{\-\}\\\|\_\{\\infty\}\.Thus

dist∞⁡\(x,ℝ\+n\)=‖x−‖∞\.\\operatorname\{dist\}\_\{\\infty\}\(x,\\mathbb\{R\}\_\{\+\}^\{n\}\)=\\\|x^\{\-\}\\\|\_\{\\infty\}\.Applying this identity withx=ekx=e\_\{k\}gives

dist∞⁡\(ek,ℝ\+n\)=‖ek−‖∞\.\\operatorname\{dist\}\_\{\\infty\}\(e\_\{k\},\\mathbb\{R\}\_\{\+\}^\{n\}\)=\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\.Finally,[Equation˜8](https://arxiv.org/html/2605.16103#S3.E8)yields

dist∞⁡\(ek,ℝ\+n\)=‖ek−‖∞≤C−⋆​β−k​‖e0−‖2,\\operatorname\{dist\}\_\{\\infty\}\(e\_\{k\},\\mathbb\{R\}\_\{\+\}^\{n\}\)=\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\},which proves the claim\. ∎

### C\.4Stochastic comparison lemmas

The first stochastic comparison lemma adds the Q\-learning noise term to the deterministic residual identities\.

###### Lemma 14\.

Under the standing Q\-learning assumptions, the Q\-learning error satisfies[Equations˜10](https://arxiv.org/html/2605.16103#S4.E10)and[12](https://arxiv.org/html/2605.16103#S4.E12), with the residual inequalities stated there\.

###### Proof of[Lemma˜14](https://arxiv.org/html/2605.16103#Thmlemma14)\.

The deterministic identities in[Lemmas˜10](https://arxiv.org/html/2605.16103#Thmlemma10)and[11](https://arxiv.org/html/2605.16103#Thmlemma11)gain only the additive termα​wk\\alpha w\_\{k\}in the stochastic recursion\. This proves[Equations˜10](https://arxiv.org/html/2605.16103#S4.E10)and[12](https://arxiv.org/html/2605.16103#S4.E12)\. ∎

The stochastic lower and upper comparisons follow because the shared noise cancels in the difference recursions\.

\{restatementbox\}

Restatement of[Lemma˜5](https://arxiv.org/html/2605.16103#Thmlemma5)\.Define the optimized lower comparison system

ℓk\+1=𝐀−⋆​ℓk\+α​wk,ℓ0=e0,k∈\{0,1,2,…\},\\ell\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}\\ell\_\{k\}\+\\alpha w\_\{k\},\\qquad\\ell\_\{0\}=e\_\{0\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},and the direct upper comparison system

uk\+1=𝐀πk\+​uk\+α​wk,u0=e0,k∈\{0,1,2,…\}\.u\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}u\_\{k\}\+\\alpha w\_\{k\},\\qquad u\_\{0\}=e\_\{0\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Then

ℓk≤ek≤uk,k∈\{0,1,2,…\}\.\\ell\_\{k\}\\leq e\_\{k\}\\leq u\_\{k\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.
###### Proof of[Lemma˜5](https://arxiv.org/html/2605.16103#Thmlemma5)\.

Subtracting[Equation˜11](https://arxiv.org/html/2605.16103#S4.E11)from[Equation˜10](https://arxiv.org/html/2605.16103#S4.E10)yields

ek\+1−ℓk\+1=𝐀−⋆​\(ek−ℓk\)\+α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)\.e\_\{k\+1\}\-\\ell\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}\(e\_\{k\}\-\\ell\_\{k\}\)\+\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)\.The noise cancels\. Sincee0−ℓ0=0e\_\{0\}\-\\ell\_\{0\}=0, all factors are nonnegative, and the residual is nonnegative, induction givesℓk≤ek\\ell\_\{k\}\\leq e\_\{k\}\.

Subtracting[Equation˜12](https://arxiv.org/html/2605.16103#S4.E12)from[Equation˜13](https://arxiv.org/html/2605.16103#S4.E13)gives

uk\+1−ek\+1=𝐀πk\+​\(uk−ek\)\+α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)\.u\_\{k\+1\}\-e\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}\(u\_\{k\}\-e\_\{k\}\)\+\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)\.The noise again cancels\. Sinceu0−e0=0u\_\{0\}\-e\_\{0\}=0, all factors are nonnegative, and the residual is nonnegative, induction givesek≤uke\_\{k\}\\leq u\_\{k\}\. ∎

The next lemma converts the stochastic order comparisons into sign\-part inequalities\.

###### Lemma 15\.

Under the standing Q\-learning assumptions, withℓk\\ell\_\{k\}anduku\_\{k\}defined in[Equations˜11](https://arxiv.org/html/2605.16103#S4.E11)and[13](https://arxiv.org/html/2605.16103#S4.E13),

ek−≤ℓk−,ek\+≤uk\+,k∈\{0,1,2,…\}\.e\_\{k\}^\{\-\}\\leq\\ell\_\{k\}^\{\-\},\\qquad e\_\{k\}^\{\+\}\\leq u\_\{k\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.

###### Proof of[Lemma˜15](https://arxiv.org/html/2605.16103#Thmlemma15)\.

Sinceℓk≤ek\\ell\_\{k\}\\leq e\_\{k\}, we have−ek≤−ℓk\-e\_\{k\}\\leq\-\\ell\_\{k\}, and henceek−=\(−ek\)\+≤\(−ℓk\)\+=ℓk−e\_\{k\}^\{\-\}=\(\-e\_\{k\}\)^\{\+\}\\leq\(\-\\ell\_\{k\}\)^\{\+\}=\\ell\_\{k\}^\{\-\}\. Sinceek≤uke\_\{k\}\\leq u\_\{k\}, monotonicity of the componentwise positive\-part map givesek\+≤uk\+e\_\{k\}^\{\+\}\\leq u\_\{k\}^\{\+\}\. ∎

The following one\-step estimate separates the deterministic propagation from the signed noise increments\.

###### Lemma 16\.

Under the standing Q\-learning assumptions, the negative part satisfies

ek\+1−≤𝐀−⋆​ek−\+α​wk−,k∈\{0,1,2,…\}\.e\_\{k\+1\}^\{\-\}\\leq\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\+\\alpha w\_\{k\}^\{\-\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.The positive part satisfies

ek\+1\+≤𝐀πk\+​ek\+\+α​wk\+,k∈\{0,1,2,…\}\.e\_\{k\+1\}^\{\+\}\\leq\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\+\\alpha w\_\{k\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.

###### Proof of[Lemma˜16](https://arxiv.org/html/2605.16103#Thmlemma16)\.

From[Equation˜10](https://arxiv.org/html/2605.16103#S4.E10)andek=ek\+−ek−e\_\{k\}=e\_\{k\}^\{\+\}\-e\_\{k\}^\{\-\},

ek\+1=𝐀−⋆​ek\+−𝐀−⋆​ek−\+rk−\+α​wk,rk−:=α​γ​D​P​\(VQk−V∗−𝚷π−⋆​ek\)≥0\.e\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\+\}\-\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\+r\_\{k\}^\{\-\}\+\\alpha w\_\{k\},\\qquad r\_\{k\}^\{\-\}:=\\alpha\\gamma DP\\bigl\(V\_\{Q\_\{k\}\}\-V^\{\*\}\-\\boldsymbol\{\\Pi\}^\{\\pi\_\{\-\}^\{\\star\}\}e\_\{k\}\\bigr\)\\geq 0\.The nonnegative vector𝐀−⋆​ek\+\+rk−\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\+\}\+r\_\{k\}^\{\-\}cannot increase the negative part\. Componentwise,

ek\+1−≤\(𝐀−⋆​ek−−α​wk\)\+\.e\_\{k\+1\}^\{\-\}\\leq\\left\(\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\-\\alpha w\_\{k\}\\right\)^\{\+\}\.Since𝐀−⋆​ek−≥0\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\\geq 0, the scalar inequality\(a−ξ\)\+≤a\+ξ−\(a\-\\xi\)^\{\+\}\\leq a\+\\xi^\{\-\}fora≥0a\\geq 0, applied witha=\(𝐀−⋆​ek−\)ia=\(\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\)\_\{i\}andξ=α​wk,i\\xi=\\alpha w\_\{k,i\}, gives

ek\+1−≤𝐀−⋆​ek−\+α​wk−\.e\_\{k\+1\}^\{\-\}\\leq\\mathbf\{A\}\_\{\-\}^\{\\star\}e\_\{k\}^\{\-\}\+\\alpha w\_\{k\}^\{\-\}\.Similarly, from[Equation˜12](https://arxiv.org/html/2605.16103#S4.E12),

ek\+1=𝐀πk\+​ek\+−𝐀πk\+​ek−−rk\+\+α​wk,rk\+:=α​γ​D​P​\(𝚷πk\+​ek−\(VQk−V∗\)\)≥0\.e\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\-\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\-\}\-r\_\{k\}^\{\+\}\+\\alpha w\_\{k\},\\qquad r\_\{k\}^\{\+\}:=\\alpha\\gamma DP\\bigl\(\\boldsymbol\{\\Pi\}^\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}\-\(V\_\{Q\_\{k\}\}\-V^\{\*\}\)\\bigr\)\\geq 0\.The nonnegative vector𝐀πk\+​ek−\+rk\+\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\-\}\+r\_\{k\}^\{\+\}cannot increase the positive part; hence

ek\+1\+≤\(𝐀πk\+​ek\+\+α​wk\)\+\.e\_\{k\+1\}^\{\+\}\\leq\\left\(\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\+\\alpha w\_\{k\}\\right\)^\{\+\}\.Since𝐀πk\+​ek\+≥0\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\\geq 0, the scalar inequality\(a\+ξ\)\+≤a\+ξ\+\(a\+\\xi\)^\{\+\}\\leq a\+\\xi^\{\+\}fora≥0a\\geq 0, applied componentwise, proves

ek\+1\+≤𝐀πk\+​ek\+\+α​wk\+\.e\_\{k\+1\}^\{\+\}\\leq\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}e\_\{k\}^\{\+\}\+\\alpha w\_\{k\}^\{\+\}\.∎

The pathwise stochastic sign comparison is obtained by iterating the one\-step estimates\.

\{restatementbox\}

Restatement of[Lemma˜6](https://arxiv.org/html/2605.16103#Thmlemma6)\.Define the sign comparison systems

zk\+1−=𝐀−⋆​zk−\+α​wk−,z0−=e0−,k∈\{0,1,2,…\},z^\{\-\}\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}z^\{\-\}\_\{k\}\+\\alpha w\_\{k\}^\{\-\},\\qquad z^\{\-\}\_\{0\}=e\_\{0\}^\{\-\},\\qquad k\\in\\\{0,1,2,\\ldots\\\},and

zk\+1\+=𝐀πk\+​zk\+\+α​wk\+,z0\+=e0\+,k∈\{0,1,2,…\}\.z^\{\+\}\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}z^\{\+\}\_\{k\}\+\\alpha w\_\{k\}^\{\+\},\\qquad z^\{\+\}\_\{0\}=e\_\{0\}^\{\+\},\\qquad k\\in\\\{0,1,2,\\ldots\\\}\.Then, for allk∈\{0,1,2,…\}k\\in\\\{0,1,2,\\ldots\\\},

ek−≤zk−,ek\+≤zk\+\.e\_\{k\}^\{\-\}\\leq z^\{\-\}\_\{k\},\\qquad e\_\{k\}^\{\+\}\\leq z^\{\+\}\_\{k\}\.
###### Proof of[Lemma˜6](https://arxiv.org/html/2605.16103#Thmlemma6)\.

Atk=0k=0, the inequalities hold by definition\. If they hold at timekk, then[Lemma˜16](https://arxiv.org/html/2605.16103#Thmlemma16)and the nonnegativity of𝐀−⋆\\mathbf\{A\}\_\{\-\}^\{\\star\}and𝐀πk\+\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}give

ek\+1−≤𝐀−⋆​zk−\+α​wk−=zk\+1−,e\_\{k\+1\}^\{\-\}\\leq\\mathbf\{A\}\_\{\-\}^\{\\star\}z\_\{k\}^\{\-\}\+\\alpha w\_\{k\}^\{\-\}=z\_\{k\+1\}^\{\-\},and

ek\+1\+≤𝐀πk\+​zk\+\+α​wk\+=zk\+1\+\.e\_\{k\+1\}^\{\+\}\\leq\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}z\_\{k\}^\{\+\}\+\\alpha w\_\{k\}^\{\+\}=z\_\{k\+1\}^\{\+\}\.The result follows by induction\. ∎

### C\.5Stochastic finite\-time proofs

We next prove the stochastic finite\-time bound for the negative component\.

\{restatementbox\}

Restatement of[Theorem˜3](https://arxiv.org/html/2605.16103#Thmtheorem3)\.Assume[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), and letWmaxW\_\{\\max\}be defined as in[Lemma˜8](https://arxiv.org/html/2605.16103#Thmlemma8)\. Fixε\>0\\varepsilon\>0such that

ρ−⋆\+ε<1,\\rho\_\{\-\}^\{\\star\}\+\\varepsilon<1,and defineβ−:=ρ−⋆\+ε\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilon\. Let

v−⋆​\(x\):=∑t=0∞β−−2​t​‖\(𝐀−⋆\)t​x‖22\.v\_\{\-\}^\{\\star\}\(x\):=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\-\}^\{\-2t\}\\\|\(\\mathbf\{A\}\_\{\-\}^\{\\star\}\)^\{t\}x\\\|\_\{2\}^\{2\}\.Then

v−⋆​\(𝐀−⋆​x\)=β−2​\(v−⋆​\(x\)−‖x‖22\),∀x∈ℝ\|𝒮\|​\|𝒜\|,v\_\{\-\}^\{\\star\}\(\\mathbf\{A\}\_\{\-\}^\{\\star\}x\)=\\beta\_\{\-\}^\{2\}\\left\(v\_\{\-\}^\{\\star\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\},and there existsC−⋆≥1C\_\{\-\}^\{\\star\}\\geq 1, the fixed\-mode norm\-equivalence constant associated withv−⋆v\_\{\-\}^\{\\star\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, such that

‖x‖22≤v−⋆​\(x\)≤C−⋆​‖x‖22\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\-\}^\{\\star\}\(x\)\\leq C\_\{\-\}^\{\\star\}\\\|x\\\|\_\{2\}^\{2\}\.Then, for everyk≥0k\\geq 0,

𝔼​\[‖ek−‖∞\]≤C−⋆​β−k​‖e0−‖2\+α​C−⋆​Wmax1−β−2\.\\mathbb\{E\}\[\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\]\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\+\\alpha C\_\{\-\}^\{\\star\}\\sqrt\{\\frac\{W\_\{\\max\}\}\{1\-\\beta\_\{\-\}^\{2\}\}\}\.Consequently, the negative part is certified at the optimized single\-policy LTI rate

ρ−⋆=minπ∈Θ∗⁡ρ​\(𝐀π\)\.\\rho\_\{\-\}^\{\\star\}=\\min\_\{\\pi\\in\\Theta^\{\*\}\}\\rho\(\\mathbf\{A\}\_\{\\pi\}\)\.
###### Proof of[Theorem˜3](https://arxiv.org/html/2605.16103#Thmtheorem3)\.

Let

p−⋆​\(x\):=v−⋆​\(x\)\.p\_\{\-\}^\{\\star\}\(x\):=\\sqrt\{v\_\{\-\}^\{\\star\}\(x\)\}\.Thenp−⋆p\_\{\-\}^\{\\star\}is a norm\. Since

v−⋆​\(𝐀−⋆​x\)=β−2​\(v−⋆​\(x\)−‖x‖22\),v\_\{\-\}^\{\\star\}\(\\mathbf\{A\}\_\{\-\}^\{\\star\}x\)=\\beta\_\{\-\}^\{2\}\\left\(v\_\{\-\}^\{\\star\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\),we have

p−⋆​\(𝐀−⋆​x\)≤β−​v−⋆​\(x\)−‖x‖22\.p\_\{\-\}^\{\\star\}\(\\mathbf\{A\}\_\{\-\}^\{\\star\}x\)\\leq\\beta\_\{\-\}\\sqrt\{v\_\{\-\}^\{\\star\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\}\.From[Equation˜14](https://arxiv.org/html/2605.16103#S4.E14),

zk\+1−=𝐀−⋆​zk−\+α​wk−\.z^\{\-\}\_\{k\+1\}=\\mathbf\{A\}\_\{\-\}^\{\\star\}z^\{\-\}\_\{k\}\+\\alpha w\_\{k\}^\{\-\}\.Using the triangle inequality forp−⋆p\_\{\-\}^\{\\star\}, squaring, and usingv−⋆​\(wk−\)≤C−⋆​‖wk−‖22v\_\{\-\}^\{\\star\}\(w\_\{k\}^\{\-\}\)\\leq C\_\{\-\}^\{\\star\}\\\|w\_\{k\}^\{\-\}\\\|\_\{2\}^\{2\}, we obtain

𝔼​\[v−⋆​\(zk\+1−\)∣ℱk\]\\displaystyle\\mathbb\{E\}\[v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤β−2​v−⋆​\(zk−\)−β−2​‖zk−‖22\\displaystyle\\leq\\beta\_\{\-\}^\{2\}v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\}\)\-\\beta\_\{\-\}^\{2\}\\\|z^\{\-\}\_\{k\}\\\|\_\{2\}^\{2\}\+2​α​β−​C−⋆​\(C−⋆−1\)​Wmax​‖zk−‖2\+α2​C−⋆​Wmax\.\\displaystyle\\quad\+2\\alpha\\beta\_\{\-\}\\sqrt\{C\_\{\-\}^\{\\star\}\(C\_\{\-\}^\{\\star\}\-1\)W\_\{\\max\}\}\\,\\\|z^\{\-\}\_\{k\}\\\|\_\{2\}\+\\alpha^\{2\}C\_\{\-\}^\{\\star\}W\_\{\\max\}\.Using2​a​b≤a2\+b22ab\\leq a^\{2\}\+b^\{2\}with

a=β−​‖zk−‖2,b=α​C−⋆​\(C−⋆−1\)​Wmax,a=\\beta\_\{\-\}\\\|z^\{\-\}\_\{k\}\\\|\_\{2\},\\qquad b=\\alpha\\sqrt\{C\_\{\-\}^\{\\star\}\(C\_\{\-\}^\{\\star\}\-1\)W\_\{\\max\}\},gives

𝔼​\[v−⋆​\(zk\+1−\)∣ℱk\]≤β−2​v−⋆​\(zk−\)\+α2​\(C−⋆\)2​Wmax\.\\mathbb\{E\}\[v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]\\leq\\beta\_\{\-\}^\{2\}v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\}\)\+\\alpha^\{2\}\(C\_\{\-\}^\{\\star\}\)^\{2\}W\_\{\\max\}\.Taking total expectation and iterating,

𝔼​\[v−⋆​\(zk−\)\]≤C−⋆​β−2​k​‖e0−‖22\+α2​\(C−⋆\)2​Wmax1−β−2\.\\mathbb\{E\}\[v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\}\)\]\\leq C\_\{\-\}^\{\\star\}\\beta\_\{\-\}^\{2k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}^\{2\}\+\\frac\{\\alpha^\{2\}\(C\_\{\-\}^\{\\star\}\)^\{2\}W\_\{\\max\}\}\{1\-\\beta\_\{\-\}^\{2\}\}\.By[Lemma˜6](https://arxiv.org/html/2605.16103#Thmlemma6),

‖ek−‖∞≤‖zk−‖∞≤‖zk−‖2≤v−⋆​\(zk−\)\.\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\\leq\\\|z^\{\-\}\_\{k\}\\\|\_\{\\infty\}\\leq\\\|z^\{\-\}\_\{k\}\\\|\_\{2\}\\leq\\sqrt\{v\_\{\-\}^\{\\star\}\(z^\{\-\}\_\{k\}\)\}\.Jensen’s inequality anda\+b≤a\+b\\sqrt\{a\+b\}\\leq\\sqrt\{a\}\+\\sqrt\{b\}prove[Equation˜16](https://arxiv.org/html/2605.16103#S4.E16)\. ∎

The stochastic orthant\-distance bound follows from the same identity between distance and the negative part\.

\{restatementbox\}

Restatement of[Corollary˜2](https://arxiv.org/html/2605.16103#Thmcorollary2)\.Let

ℝ\+\|𝒮\|​\|𝒜\|:=\{x∈ℝ\|𝒮\|​\|𝒜\|:x≥0\}\.\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}:=\\\{x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}:x\\geq 0\\\}\.Under the assumptions of[Theorem˜3](https://arxiv.org/html/2605.16103#Thmtheorem3), for everyε\>0\\varepsilon\>0satisfyingρ−⋆\+ε<1\\rho\_\{\-\}^\{\\star\}\+\\varepsilon<1, withβ−:=ρ−⋆\+ε\\beta\_\{\-\}:=\\rho\_\{\-\}^\{\\star\}\+\\varepsilonand with the same fixed\-mode norm\-equivalence constantC−⋆C\_\{\-\}^\{\\star\}associated withv−⋆v\_\{\-\}^\{\\star\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, everyk≥0k\\geq 0satisfies

𝔼​\[dist∞⁡\(ek,ℝ\+\|𝒮\|​\|𝒜\|\)\]≤C−⋆​β−k​‖e0−‖2\+α​C−⋆​Wmax1−β−2\.\\mathbb\{E\}\\\!\\left\[\\operatorname\{dist\}\_\{\\infty\}\(e\_\{k\},\\mathbb\{R\}\_\{\+\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}\)\\right\]\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\+\\alpha C\_\{\-\}^\{\\star\}\\sqrt\{\\frac\{W\_\{\\max\}\}\{1\-\\beta\_\{\-\}^\{2\}\}\}\.
###### Proof of[Corollary˜2](https://arxiv.org/html/2605.16103#Thmcorollary2)\.

Letn:=\|𝒮\|​\|𝒜\|n:=\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\. As in the deterministic case, for anyx∈ℝnx\\in\\mathbb\{R\}^\{n\}and anyy∈ℝ\+ny\\in\\mathbb\{R\}\_\{\+\}^\{n\}, the coordinates withxi<0x\_\{i\}<0satisfy

\|xi−yi\|≥−xi=xi−\.\|x\_\{i\}\-y\_\{i\}\|\\geq\-x\_\{i\}=x\_\{i\}^\{\-\}\.Hence

dist∞⁡\(x,ℝ\+n\)=infy∈ℝ\+n‖x−y‖∞≥‖x−‖∞\.\\operatorname\{dist\}\_\{\\infty\}\(x,\\mathbb\{R\}\_\{\+\}^\{n\}\)=\\inf\_\{y\\in\\mathbb\{R\}\_\{\+\}^\{n\}\}\\\|x\-y\\\|\_\{\\infty\}\\geq\\\|x^\{\-\}\\\|\_\{\\infty\}\.Choosingy=x\+∈ℝ\+ny=x^\{\+\}\\in\\mathbb\{R\}\_\{\+\}^\{n\}gives the reverse inequality because

‖x−x\+‖∞=‖−x−‖∞=‖x−‖∞\.\\\|x\-x^\{\+\}\\\|\_\{\\infty\}=\\\|\-x^\{\-\}\\\|\_\{\\infty\}=\\\|x^\{\-\}\\\|\_\{\\infty\}\.Therefore,

dist∞⁡\(x,ℝ\+n\)=‖x−‖∞\.\\operatorname\{dist\}\_\{\\infty\}\(x,\\mathbb\{R\}\_\{\+\}^\{n\}\)=\\\|x^\{\-\}\\\|\_\{\\infty\}\.Withx=ekx=e\_\{k\}, this identity gives the pathwise equality

dist∞⁡\(ek,ℝ\+n\)=‖ek−‖∞\.\\operatorname\{dist\}\_\{\\infty\}\(e\_\{k\},\\mathbb\{R\}\_\{\+\}^\{n\}\)=\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\.Taking expectations and applying[Theorem˜3](https://arxiv.org/html/2605.16103#Thmtheorem3), we obtain

𝔼​\[dist∞⁡\(ek,ℝ\+n\)\]\\displaystyle\\mathbb\{E\}\\\!\\left\[\\operatorname\{dist\}\_\{\\infty\}\(e\_\{k\},\\mathbb\{R\}\_\{\+\}^\{n\}\)\\right\]=𝔼​\[‖ek−‖∞\]\\displaystyle=\\mathbb\{E\}\[\\\|e\_\{k\}^\{\-\}\\\|\_\{\\infty\}\]≤C−⋆​β−k​‖e0−‖2\+α​C−⋆​Wmax1−β−2\.\\displaystyle\\leq\\sqrt\{C\_\{\-\}^\{\\star\}\}\\,\\beta\_\{\-\}^\{k\}\\\|e\_\{0\}^\{\-\}\\\|\_\{2\}\+\\alpha C\_\{\-\}^\{\\star\}\\sqrt\{\\frac\{W\_\{\\max\}\}\{1\-\\beta\_\{\-\}^\{2\}\}\}\.This proves the corollary\. ∎

Finally, the positive\-side stochastic bound uses the switching\-family Lyapunov inequality\.

\{restatementbox\}

Restatement of[Theorem˜4](https://arxiv.org/html/2605.16103#Thmtheorem4)\.Assume[Assumption˜1](https://arxiv.org/html/2605.16103#Thmassumption1), and letWmaxW\_\{\\max\}be defined as in[Lemma˜8](https://arxiv.org/html/2605.16103#Thmlemma8)\. Fixε\>0\\varepsilon\>0such that

ρ\+\+ε<1,\\rho\_\{\+\}\+\\varepsilon<1,and defineβ\+:=ρ\+\+ε\\beta\_\{\+\}:=\\rho\_\{\+\}\+\\varepsilon\. Let

v\+​\(x\):=∑t=0∞β\+−2​t​maxπ0,…,πt−1∈Θ⁡‖𝐀πt−1​⋯​𝐀π0​x‖22,v\_\{\+\}\(x\):=\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\+\}^\{\-2t\}\\max\_\{\\pi\_\{0\},\\ldots,\\pi\_\{t\-1\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{t\-1\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{0\}\}x\\right\\\|\_\{2\}^\{2\},where thet=0t=0product is the identity\. Then, for everyπ∈Θ\\pi\\in\\Theta,

v\+​\(𝐀π​x\)≤β\+2​\(v\+​\(x\)−‖x‖22\),∀x∈ℝ\|𝒮\|​\|𝒜\|,v\_\{\+\}\(\\mathbf\{A\}\_\{\\pi\}x\)\\leq\\beta\_\{\+\}^\{2\}\\left\(v\_\{\+\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\),\\qquad\\forall x\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\},and there existsC\+≥1C\_\{\+\}\\geq 1, the product\-family norm\-equivalence constant associated withv\+v\_\{\+\}onℝ\|𝒮\|​\|𝒜\|\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\,\|\\mathcal\{A\}\|\}, such that

‖x‖22≤v\+​\(x\)≤C\+​‖x‖22\.\\\|x\\\|\_\{2\}^\{2\}\\leq v\_\{\+\}\(x\)\\leq C\_\{\+\}\\\|x\\\|\_\{2\}^\{2\}\.Then, for everyk≥0k\\geq 0,

𝔼​\[‖ek\+‖∞\]≤C\+​β\+k​‖e0\+‖2\+α​C\+​Wmax1−β\+2\.\\mathbb\{E\}\[\\\|e\_\{k\}^\{\+\}\\\|\_\{\\infty\}\]\\leq\\sqrt\{C\_\{\+\}\}\\,\\beta\_\{\+\}^\{k\}\\\|e\_\{0\}^\{\+\}\\\|\_\{2\}\+\\alpha C\_\{\+\}\\sqrt\{\\frac\{W\_\{\\max\}\}\{1\-\\beta\_\{\+\}^\{2\}\}\}\.Consequently, the positive part is certified at the full direct JSR rate

ρ\+=ραdir=ρ​\(\{𝐀π:π∈Θ\}\)\.\\rho\_\{\+\}=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=\\rho\(\\\{\\mathbf\{A\}\_\{\\pi\}:\\pi\\in\\Theta\\\}\)\.
###### Proof of[Theorem˜4](https://arxiv.org/html/2605.16103#Thmtheorem4)\.

Let

p\+​\(x\):=v\+​\(x\)\.p\_\{\+\}\(x\):=\\sqrt\{v\_\{\+\}\(x\)\}\.Thenp\+p\_\{\+\}is a norm\. The product\-defined Lyapunov function satisfies, for allπ∈Θ\\pi\\in\\Theta,

v\+​\(𝐀π​x\)≤β\+2​\(v\+​\(x\)−‖x‖22\)\.v\_\{\+\}\(\\mathbf\{A\}\_\{\\pi\}x\)\\leq\\beta\_\{\+\}^\{2\}\\left\(v\_\{\+\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\.Indeed, appending the fixed matrix𝐀π\\mathbf\{A\}\_\{\\pi\}to any product of lengthttproduces a product of lengtht\+1t\+1, and therefore

v\+​\(𝐀π​x\)\\displaystyle v\_\{\+\}\(\\mathbf\{A\}\_\{\\pi\}x\)≤∑t=0∞β\+−2​t​maxπ0,…,πt∈Θ⁡‖𝐀πt​⋯​𝐀π0​x‖22\\displaystyle\\leq\\sum\_\{t=0\}^\{\\infty\}\\beta\_\{\+\}^\{\-2t\}\\max\_\{\\pi\_\{0\},\\ldots,\\pi\_\{t\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{t\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{0\}\}x\\right\\\|\_\{2\}^\{2\}=β\+2​∑r=1∞β\+−2​r​maxπ0,…,πr−1∈Θ⁡‖𝐀πr−1​⋯​𝐀π0​x‖22\\displaystyle=\\beta\_\{\+\}^\{2\}\\sum\_\{r=1\}^\{\\infty\}\\beta\_\{\+\}^\{\-2r\}\\max\_\{\\pi\_\{0\},\\ldots,\\pi\_\{r\-1\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{r\-1\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{0\}\}x\\right\\\|\_\{2\}^\{2\}=β\+2​\(v\+​\(x\)−‖x‖22\)\.\\displaystyle=\\beta\_\{\+\}^\{2\}\\left\(v\_\{\+\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\.From[Equation˜15](https://arxiv.org/html/2605.16103#S4.E15),

zk\+1\+=𝐀πk\+​zk\+\+α​wk\+\.z^\{\+\}\_\{k\+1\}=\\mathbf\{A\}\_\{\\pi\_\{k\}^\{\+\}\}z^\{\+\}\_\{k\}\+\\alpha w\_\{k\}^\{\+\}\.Using the triangle inequality forp\+p\_\{\+\}, squaring, and using[Lemma˜9](https://arxiv.org/html/2605.16103#Thmlemma9), we obtain

𝔼​\[v\+​\(zk\+1\+\)∣ℱk\]\\displaystyle\\mathbb\{E\}\[v\_\{\+\}\(z^\{\+\}\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤β\+2​v\+​\(zk\+\)−β\+2​‖zk\+‖22\\displaystyle\\leq\\beta\_\{\+\}^\{2\}v\_\{\+\}\(z^\{\+\}\_\{k\}\)\-\\beta\_\{\+\}^\{2\}\\\|z^\{\+\}\_\{k\}\\\|\_\{2\}^\{2\}\+2​α​β\+​C\+​\(C\+−1\)​Wmax​‖zk\+‖2\+α2​C\+​Wmax\.\\displaystyle\\quad\+2\\alpha\\beta\_\{\+\}\\sqrt\{C\_\{\+\}\(C\_\{\+\}\-1\)W\_\{\\max\}\}\\,\\\|z^\{\+\}\_\{k\}\\\|\_\{2\}\+\\alpha^\{2\}C\_\{\+\}W\_\{\\max\}\.Using2​a​b≤a2\+b22ab\\leq a^\{2\}\+b^\{2\}with

a=β\+​‖zk\+‖2,b=α​C\+​\(C\+−1\)​Wmax,a=\\beta\_\{\+\}\\\|z^\{\+\}\_\{k\}\\\|\_\{2\},\\qquad b=\\alpha\\sqrt\{C\_\{\+\}\(C\_\{\+\}\-1\)W\_\{\\max\}\},gives

𝔼​\[v\+​\(zk\+1\+\)∣ℱk\]≤β\+2​v\+​\(zk\+\)\+α2​C\+2​Wmax\.\\mathbb\{E\}\[v\_\{\+\}\(z^\{\+\}\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]\\leq\\beta\_\{\+\}^\{2\}v\_\{\+\}\(z^\{\+\}\_\{k\}\)\+\\alpha^\{2\}C\_\{\+\}^\{2\}W\_\{\\max\}\.Taking total expectation and iterating,

𝔼​\[v\+​\(zk\+\)\]≤C\+​β\+2​k​‖e0\+‖22\+α2​C\+2​Wmax1−β\+2\.\\mathbb\{E\}\[v\_\{\+\}\(z^\{\+\}\_\{k\}\)\]\\leq C\_\{\+\}\\beta\_\{\+\}^\{2k\}\\\|e\_\{0\}^\{\+\}\\\|\_\{2\}^\{2\}\+\\frac\{\\alpha^\{2\}C\_\{\+\}^\{2\}W\_\{\\max\}\}\{1\-\\beta\_\{\+\}^\{2\}\}\.By[Lemma˜6](https://arxiv.org/html/2605.16103#Thmlemma6),

‖ek\+‖∞≤‖zk\+‖∞≤‖zk\+‖2≤v\+​\(zk\+\)\.\\\|e\_\{k\}^\{\+\}\\\|\_\{\\infty\}\\leq\\\|z^\{\+\}\_\{k\}\\\|\_\{\\infty\}\\leq\\\|z^\{\+\}\_\{k\}\\\|\_\{2\}\\leq\\sqrt\{v\_\{\+\}\(z^\{\+\}\_\{k\}\)\}\.Jensen’s inequality anda\+b≤a\+b\\sqrt\{a\+b\}\\leq\\sqrt\{a\}\+\\sqrt\{b\}prove[Equation˜17](https://arxiv.org/html/2605.16103#S4.E17)\. ∎