A Switching System Theory of Q-Learning with Linear Function Approximation

# A Switching System Theory of Q-Learning with Linear Function Approximation
Source: [https://arxiv.org/html/2605.11021](https://arxiv.org/html/2605.11021)
Donghwan Lee and Han\-Dong Lim 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 switching\-system interpretation of Q\-learning with linear function approximation \(LFA\) based on the joint spectral radius \(JSR\)\. We derive an exact linear switched model for the mean dynamics and relate convergence to stability of the corresponding switched system\. The same construction is then used for stochastic linear Q\-learning with independent and identically distributed \(i\.i\.d\.\) observations and with Markovian observations\. Although exact JSR computation is difficult in general, the certificate captures products of switching modes and can be less conservative than one\-step norm bounds\. The framework also yields a JSR\-based view of regularized Q\-learning with LFA\. The resulting analysis connects projected Bellman equations, finite\-difference stochastic\-policy switching, and switched\-system stability in a single parameter\-space formulation\.

## 1Introduction

Q\-learning\[[34](https://arxiv.org/html/2605.11021#bib.bib22)\]is a foundational algorithm for reinforcement learning in discounted Markov decision processes \(MDPs\)\[[30](https://arxiv.org/html/2605.11021#bib.bib2),[27](https://arxiv.org/html/2605.11021#bib.bib1),[2](https://arxiv.org/html/2605.11021#bib.bib4)\]\. In large state\-action spaces, linear function approximation \(LFA\) represents action\-value functions by a low\-dimensional parameter\. With LFA, the Bellman optimality operator is projected onto a feature subspace, and the greedy action may change as the parameter changes\. The resulting mean recursion is not a single linear system; it is a policy\-dependent linear switching dynamics\. To keep the main development focused, all proofs of the paper’s new statements are deferred to the appendix\.

We study Q\-learning with LFA, called linear Q\-learning, through switching\-system theory\[[19](https://arxiv.org/html/2605.11021#bib.bib13),[23](https://arxiv.org/html/2605.11021#bib.bib11)\]\. The Bellman optimality error induces a stochastic\-policy\-based switching system, and the stability object is the joint spectral radius \(JSR\) of the associated switching matrix family\[[29](https://arxiv.org/html/2605.11021#bib.bib17),[32](https://arxiv.org/html/2605.11021#bib.bib18),[12](https://arxiv.org/html/2605.11021#bib.bib16)\]\. The basic identity is a stochastic\-policy linearization of the Bellman maximum: the difference between two value\-max vectors can be represented exactly as a policy\-weighted linear function of the parameter difference\.

This representation gives a switched linear model for the deterministic recursion of linear Q\-learning\. When the corresponding JSR is less than one, a piecewise quadratic Lyapunov norm\[[11](https://arxiv.org/html/2605.11021#bib.bib15)\]certifies contraction of the mean linear Q\-learning map, uniqueness of the projected Bellman fixed point, and exponential convergence\. The JSR analysis permits arbitrary switching, whereas the deterministic linear Q\-learning realizes only the stochastic\-policy modes generated along its trajectory\. Therefore, the proposed JSR condition is a robust sufficient certificate for the actual recursion\.

The proposed Lyapunov certificate is then used for stochastic linear Q\-learning\. Under i\.i\.d\. observations, the sampled recursion is the switched mean dynamics plus martingale\-difference noise\. Under Markovian observations, the stationary averaged drift is added and subtracted, and the coordinate\-sampling discrepancy is treated as a bounded error\. This keeps the same JSR\-induced norm throughout the deterministic, i\.i\.d\., and Markovian analyses\.

We also apply the switching viewpoint to regularized Q\-learning with LFA\[[21](https://arxiv.org/html/2605.11021#bib.bib49)\]\. Regularization shifts each direct switching mode, which leads to a regularized JSR and stability conditions depending on the regularization parameter\. The analysis gives a unified way to compare unregularized and regularized linear Q\-learning through the switched matrix families induced by the Bellman optimality error via stochastic\-policy linearization\.

## 2Related Work

Classical convergence analyses of Q\-learning rely on stochastic approximation, ODE methods, Bellman contraction, monotonicity, and finite\-time error estimates\[[33](https://arxiv.org/html/2605.11021#bib.bib24),[31](https://arxiv.org/html/2605.11021#bib.bib29),[13](https://arxiv.org/html/2605.11021#bib.bib27),[3](https://arxiv.org/html/2605.11021#bib.bib26),[9](https://arxiv.org/html/2605.11021#bib.bib28),[1](https://arxiv.org/html/2605.11021#bib.bib30),[28](https://arxiv.org/html/2605.11021#bib.bib32),[18](https://arxiv.org/html/2605.11021#bib.bib33),[7](https://arxiv.org/html/2605.11021#bib.bib34)\]\. These results form the standard foundation for tabular Q\-learning\. The present paper takes a different route for linear Q\-learning: it treats the linear Q\-learning as a switching system and studies the induced switching dynamics through a matrix family and its JSR\.

Convergence theory for linear Q\-learning has also been developed beyond the tabular setting\. Early sufficient conditions for convergence with LFA were given by\[[25](https://arxiv.org/html/2605.11021#bib.bib58)\]\. Subsequent work introduced convergent variants and stabilization mechanisms, including two\-time\-scale variants\[[4](https://arxiv.org/html/2605.11021#bib.bib53)\], target networks\[[35](https://arxiv.org/html/2605.11021#bib.bib60)\], target networks with truncation\[[6](https://arxiv.org/html/2605.11021#bib.bib55)\], and target networks with over\-parameterization\[[5](https://arxiv.org/html/2605.11021#bib.bib54)\]\. Finite\-sample analyses of nonlinear stochastic approximation have also been used to study reinforcement\-learning algorithms with Markovian noise\[[8](https://arxiv.org/html/2605.11021#bib.bib56)\]\. Recent work on projected Bellman equations and linear Q\-learning has established existence, stability, and bounded\-set convergence results under suitable conditions\[[26](https://arxiv.org/html/2605.11021#bib.bib59),[24](https://arxiv.org/html/2605.11021#bib.bib57)\]\. These results address related stability questions through stochastic approximation, algorithmic modification, target\-network structure, or projected\-equation analysis\. The approach here is complementary: it extracts the switched matrix family of the deterministic linear Q\-learning recursion and uses its JSR as the stability certificate\.

Linear approximation and projected Bellman equations have been studied in approximate dynamic programming, projected value iteration, linear Q\-learning, and regularized Q\-learning\[[22](https://arxiv.org/html/2605.11021#bib.bib50),[21](https://arxiv.org/html/2605.11021#bib.bib49),[10](https://arxiv.org/html/2605.11021#bib.bib48)\]\. These works clarify projection structure, approximation error, algorithmic differences, and the role of regularization\. We focus on the finite\-difference stochastic\-policy switching structure induced by the Bellman maximum and use it to derive deterministic and stochastic bounds in a common Lyapunov norm\.

Switching system theory studies systems whose dynamics change among multiple modes\[[19](https://arxiv.org/html/2605.11021#bib.bib13),[23](https://arxiv.org/html/2605.11021#bib.bib11)\]\. The JSR gives the worst\-case exponential growth rate of all products generated by a matrix family\[[29](https://arxiv.org/html/2605.11021#bib.bib17),[32](https://arxiv.org/html/2605.11021#bib.bib18),[12](https://arxiv.org/html/2605.11021#bib.bib16)\]\. Previous switching\-system analyses of Q\-learning focused mainly on tabular algorithms, affine switching models, comparison systems, or JSR Lyapunov constructions\[[14](https://arxiv.org/html/2605.11021#bib.bib37),[15](https://arxiv.org/html/2605.11021#bib.bib38),[16](https://arxiv.org/html/2605.11021#bib.bib39),[20](https://arxiv.org/html/2605.11021#bib.bib41),[17](https://arxiv.org/html/2605.11021#bib.bib52)\]\. This paper develops the corresponding switching and JSR theory for linear Q\-learning where the modes act in feature\-parameter space\.

The stochastic analysis is related to constant step\-size stochastic approximation\. Under i\.i\.d\. sampling, the recursion is decomposed into the switched mean dynamics plus martingale noise; under Markovian observations, an additional coordinate\-sampling error appears\. Instead of replacing the dynamics by a scalar contraction argument, the paper keeps the JSR Lyapunov norm as the common certificate for deterministic, i\.i\.d\., Markovian, and regularized linear Q\-learning\.

## 3Preliminaries

### 3\.1Notation

The set of real numbers is denoted byℝ\\mathbb\{R\};ℝm\\mathbb\{R\}^\{m\}is themm\-dimensional Euclidean space; andℝm×r\\mathbb\{R\}^\{m\\times r\}is the set of allm×rm\\times rreal matrices\. For a matrixAA,A⊤A^\{\\top\}denotes its transpose\. The identity matrix is denoted byII\. For vectors,eie\_\{i\}is theiith standard basis vector, with dimension clear from context, and⊗\\otimesdenotes the Kronecker product\. For a finite set𝒮\\mathcal\{S\},\|𝒮\|\|\\mathcal\{S\}\|denotes its cardinality\. We writeΔm:=\{q∈ℝm:qi≥0,∑i=1mqi=1\}\\Delta\_\{m\}:=\\\{q\\in\\mathbb\{R\}^\{m\}:q\_\{i\}\\geq 0,\\ \\sum\_\{i=1\}^\{m\}q\_\{i\}=1\\\}for the probability simplex inℝm\\mathbb\{R\}^\{m\}\. For a finite matrix familyℋ=\{𝐀1,…,𝐀N\}\\mathcal\{H\}=\\\{\\mathbf\{A\}\_\{1\},\\ldots,\\mathbf\{A\}\_\{N\}\\\},co⁡\(ℋ\):=\{∑i=1Nλi​𝐀i:λi≥0,∑i=1Nλi=1\}\\operatorname\{co\}\(\\mathcal\{H\}\):=\\left\\\{\\sum\_\{i=1\}^\{N\}\\lambda\_\{i\}\\mathbf\{A\}\_\{i\}:\\lambda\_\{i\}\\geq 0,\\ \\sum\_\{i=1\}^\{N\}\\lambda\_\{i\}=1\\right\\\}denotes its convex hull\.

### 3\.2Switching Systems

A discrete\-time switched linear system is a dynamical system whose state evolves according to one matrix selected from a prescribed family at each time\[[19](https://arxiv.org/html/2605.11021#bib.bib13),[23](https://arxiv.org/html/2605.11021#bib.bib11),[12](https://arxiv.org/html/2605.11021#bib.bib16)\]\. For a matrix familyℋ=\{𝐀1,…,𝐀M\}⊂ℝm×m\\mathcal\{H\}=\\\{\\mathbf\{A\}\_\{1\},\\ldots,\\mathbf\{A\}\_\{M\}\\\}\\subset\\mathbb\{R\}^\{m\\times m\}, the arbitrary\-switching system is

xk\+1=𝐀σk​xk,σk∈\{1,…,M\},k∈\{0,1,…\}\.x\_\{k\+1\}=\\mathbf\{A\}\_\{\\sigma\_\{k\}\}x\_\{k\},\\qquad\\sigma\_\{k\}\\in\\\{1,\\ldots,M\\\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.The switching signal\{σk\}k≥0\\\{\\sigma\_\{k\}\\\}\_\{k\\geq 0\}may be deterministic, state dependent, or generated by an external process\. The system is uniformly exponentially stable under arbitrary switching if there exist constantsC≥1C\\geq 1andη∈\(0,1\)\\eta\\in\(0,1\)such that

‖𝐀σk−1​⋯​𝐀σ0​x‖2≤C​ηk​‖x‖2\\\|\\mathbf\{A\}\_\{\\sigma\_\{k\-1\}\}\\cdots\\mathbf\{A\}\_\{\\sigma\_\{0\}\}x\\\|\_\{2\}\\leq C\\eta^\{k\}\\\|x\\\|\_\{2\}for every horizonk≥0k\\geq 0, every initial statex∈ℝnx\\in\\mathbb\{R\}^\{n\}, and every switching sequence\. A common Lyapunov function forℋ\\mathcal\{H\}is a positive definite function that decreases along every mode in the family\. In the analysis below, the Bellman maximum in linear Q\-learning induces finite\-difference stochastic\-policy switching, and the relevant Lyapunov function is built directly from products of the induced mode matrices\.

### 3\.3Joint Spectral Radius

For a bounded set of matricesℋ⊂ℝm×m\\mathcal\{H\}\\subset\\mathbb\{R\}^\{m\\times m\}, its joint spectral radius \(JSR\)\[[29](https://arxiv.org/html/2605.11021#bib.bib17),[32](https://arxiv.org/html/2605.11021#bib.bib18),[12](https://arxiv.org/html/2605.11021#bib.bib16)\]is

ρ​\(ℋ\):=limk→∞sup𝐀1,…,𝐀k∈ℋ‖𝐀k​⋯​𝐀1‖1/k,\\rho\(\\mathcal\{H\}\):=\\lim\_\{k\\to\\infty\}\\sup\_\{\\mathbf\{A\}\_\{1\},\\ldots,\\mathbf\{A\}\_\{k\}\\in\\mathcal\{H\}\}\\\|\\mathbf\{A\}\_\{k\}\\cdots\\mathbf\{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 products generated by matrices inℋ\\mathcal\{H\}\. The JSR is the exact worst\-case exponential growth rate of the switched products generated byℋ\\mathcal\{H\}\. In this paper, a JSR less than one is used to construct a common piecewise quadratic Lyapunov certificate for arbitrary\-switching stability and for contraction of the Bellman\-generated nonlinear recursion\.

The following piecewise quadratic Lyapunov construction is the finite\-family common Lyapunov lemma introduced in\[[17](https://arxiv.org/html/2605.11021#bib.bib52),[11](https://arxiv.org/html/2605.11021#bib.bib15)\]\. It is stated here because it is the Lyapunov certificate used throughout the deterministic, stochastic, and regularized analyses\.

###### Lemma 1\(Common Lyapunov construction\[[17](https://arxiv.org/html/2605.11021#bib.bib52), Lemma 4\]\)\.

Let

ℋ=\{𝐀1,𝐀2,…,𝐀M\}⊂ℝm×m,ρ:=ρ​\(ℋ\),\\mathcal\{H\}=\\\{\\mathbf\{A\}\_\{1\},\\mathbf\{A\}\_\{2\},\\ldots,\\mathbf\{A\}\_\{M\}\\\}\\subset\\mathbb\{R\}^\{m\\times m\},\\qquad\\rho:=\\rho\(\\mathcal\{H\}\),and fixε\>0\\varepsilon\>0such thatβε:=ρ\+ε∈\(0,1\)\\beta\_\{\\varepsilon\}:=\\rho\+\\varepsilon\\in\(0,1\)\. For a sequence of modesσ=\(σ1,…,σk\)∈\{1,…,M\}k\\sigma=\(\\sigma\_\{1\},\\ldots,\\sigma\_\{k\}\)\\in\\\{1,\\ldots,M\\\}^\{k\}, write

𝐀σ:=𝐀σk​⋯​𝐀σ1,\\mathbf\{A\}\_\{\\sigma\}:=\\mathbf\{A\}\_\{\\sigma\_\{k\}\}\\cdots\\mathbf\{A\}\_\{\\sigma\_\{1\}\},with the convention that, fork=0k=0, the empty word gives𝐀σ=I\\mathbf\{A\}\_\{\\sigma\}=I\. For each integert≥0t\\geq 0, define

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

1. \(i\)For everyt≥0t\\geq 0, Vεt\+1​\(x\)≥‖x‖22\+βε−2​maxi∈\{1,…,M\}⁡Vεt​\(𝐀i​x\),∀x∈ℝm\.V\_\{\\varepsilon\}^\{t\+1\}\(x\)\\geq\\\|x\\\|\_\{2\}^\{2\}\+\\beta\_\{\\varepsilon\}^\{\-2\}\\max\_\{i\\in\\\{1,\\ldots,M\\\}\}V\_\{\\varepsilon\}^\{t\}\(\\mathbf\{A\}\_\{i\}x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{m\}\.
2. \(ii\)For everyt≥0t\\geq 0, the functionVεtV\_\{\\varepsilon\}^\{t\}is absolutely homogeneous of degree two and is monotone intt: 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. \(iii\)There existsCε\>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. \(iv\)The pointwise limit Vε∞​\(x\):=limt→∞Vεt​\(x\)V\_\{\\varepsilon\}^\{\\infty\}\(x\):=\\lim\_\{t\\to\\infty\}V\_\{\\varepsilon\}^\{t\}\(x\)exists and satisfies ‖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. \(v\)The functionpε​\(x\):=Vε∞​\(x\)p\_\{\\varepsilon\}\(x\):=\\sqrt\{V\_\{\\varepsilon\}^\{\\infty\}\(x\)\}is a norm onℝm\\mathbb\{R\}^\{m\}\.
6. \(vi\)For everyi∈\{1,…,M\}i\\in\\\{1,\\ldots,M\\\}, Vε∞​\(𝐀i​x\)≤βε2​\(Vε∞​\(x\)−‖x‖22\)≤βε2​Vε∞​\(x\),∀x∈ℝm\.V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{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\}\.Equivalently,pε​\(𝐀i​x\)≤βε​pε​\(x\)p\_\{\\varepsilon\}\(\\mathbf\{A\}\_\{i\}x\)\\leq\\beta\_\{\\varepsilon\}p\_\{\\varepsilon\}\(x\)for everyx∈ℝmx\\in\\mathbb\{R\}^\{m\}\.

### 3\.4Discounted MDPs and LFA

In this paper, we consider a finite discounted Markov decision process \(MDP\)\[[27](https://arxiv.org/html/2605.11021#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\. 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\. 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

F​\(Q\):=R\+γ​P​VQ\.F\(Q\):=R\+\\gamma PV\_\{Q\}\.LetΦ∈ℝ\|𝒮\|​\|𝒜\|×m\\Phi\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\\times m\}be a feature matrix\. In this paper, we assume that the feature matrixΦ∈ℝ\|𝒮\|​\|𝒜\|×m\\Phi\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\\times m\}has full column rank, which is standard in the literature\. Its row corresponding to\(s,a\)\(s,a\)is denoted byϕ​\(s,a\)⊤\\phi\(s,a\)^\{\\top\}, whereϕ​\(s,a\)∈ℝm\\phi\(s,a\)\\in\\mathbb\{R\}^\{m\}\. The linear function approximation \(LFA\) of the Q\-function is

Qθ:=Φ​θ\.Q\_\{\\theta\}:=\\Phi\\theta\.For an LFA parameterθ\\theta, define the corresponding value function with the greedy policy

Vθ​\(s\):=maxa∈𝒜⁡ϕ​\(s,a\)⊤​θ,Vθ:=\(Vθ​\(1\),…,Vθ​\(\|𝒮\|\)\)⊤\.V\_\{\\theta\}\(s\):=\\max\_\{a\\in\\mathcal\{A\}\}\\phi\(s,a\)^\{\\top\}\\theta,\\qquad V\_\{\\theta\}:=\(V\_\{\\theta\}\(1\),\\ldots,V\_\{\\theta\}\(\|\\mathcal\{S\}\|\)\)^\{\\top\}\.
We useddto denote a state\-action sampling distribution on𝒮×𝒜\\mathcal\{S\}\\times\\mathcal\{A\}\. In the i\.i\.d\. observation model,ddis the sampling distribution of\(sk,ak\)\(s\_\{k\},a\_\{k\}\); in the Markovian observation model,ddis the stationary state\-action distribution of the behavior\-induced chain\. Throughout the paper, we assume that the sampling distribution satisfiesd​\(s,a\)\>0d\(s,a\)\>0for every\(s,a\)∈𝒮×𝒜\(s,a\)\\in\{\\mathcal\{S\}\}\\times\{\\mathcal\{A\}\}\. Under the assumption,Φ⊤​D​Φ≻0\\Phi^\{\\top\}D\\Phi\\succ 0\. Since the state\-action space is finite, the feature radius

ϕmax:=max\(s,a\)∈𝒮×𝒜⁡‖ϕ​\(s,a\)‖2\\phi\_\{\\max\}:=\\max\_\{\(s,a\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\}\\\|\\phi\(s,a\)\\\|\_\{2\}is finite as well\.

### 3\.5Projected Bellman Equation and Projected Q\-Value Iteration

For a sampling distributionddon state\-action pairs, define the diagonal weighting matrix

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\}\|\}\.WheneverΦ⊤​D​Φ\\Phi^\{\\top\}D\\Phiis nonsingular, theDD\-orthogonal projection ontorange⁡\(Φ\)\\operatorname\{range\}\(\\Phi\)is

𝚷D:=Φ​\(Φ⊤​D​Φ\)−1​Φ⊤​D\.\\boldsymbol\{\\Pi\}\_\{D\}:=\\Phi\(\\Phi^\{\\top\}D\\Phi\)^\{\-1\}\\Phi^\{\\top\}D\.The projected Bellman equation\[[22](https://arxiv.org/html/2605.11021#bib.bib50)\]is

Φ​θ=𝚷D​F​\(Φ​θ\)=𝚷D​\(R\+γ​P​Vθ\)\.\\Phi\\theta=\\boldsymbol\{\\Pi\}\_\{D\}F\(\\Phi\\theta\)=\\boldsymbol\{\\Pi\}\_\{D\}\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)\.\(1\)A projected Bellman fixed point is a parameterθ⋆\\theta^\{\\star\}satisfying

Φ​θ⋆=𝚷D​F​\(Φ​θ⋆\)=𝚷D​\(R\+γ​P​Vθ⋆\)\.\\Phi\\theta^\{\\star\}=\\boldsymbol\{\\Pi\}\_\{D\}F\(\\Phi\\theta^\{\\star\}\)=\\boldsymbol\{\\Pi\}\_\{D\}\\left\(R\+\\gamma PV\_\{\\theta^\{\\star\}\}\\right\)\.In general, such a fixed point need not exist, and when it exists it need not be unique\[[22](https://arxiv.org/html/2605.11021#bib.bib50)\]\. The projected Q\-value iteration \(projected Q\-VI\) associated with[Equation˜1](https://arxiv.org/html/2605.11021#S3.E1)is

Φ​θk\+1PQVI=𝚷D​\(R\+γ​P​VθkPQVI\),k∈\{0,1,…\},\\Phi\\theta\_\{k\+1\}^\{\\mathrm\{PQVI\}\}=\\boldsymbol\{\\Pi\}\_\{D\}\\left\(R\+\\gamma PV\_\{\\theta\_\{k\}^\{\\mathrm\{PQVI\}\}\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\},or, equivalently, in parameter space,

θk\+1PQVI=\(Φ⊤​D​Φ\)−1​Φ⊤​D​\(R\+γ​P​VθkPQVI\),k∈\{0,1,…\}\.\\theta\_\{k\+1\}^\{\\mathrm\{PQVI\}\}=\(\\Phi^\{\\top\}D\\Phi\)^\{\-1\}\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\_\{k\}^\{\\mathrm\{PQVI\}\}\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.

### 3\.6Linear Q\-Learning and Deterministic Linear Q\-Learning

Given a transition sample\(sk,ak,rk\+1,sk′\)\(s\_\{k\},a\_\{k\},r\_\{k\+1\},s^\{\\prime\}\_\{k\}\), whererk\+1=r​\(sk,ak,sk′\)r\_\{k\+1\}=r\(s\_\{k\},a\_\{k\},s^\{\\prime\}\_\{k\}\), the scalar\-stepsize linear Q\-learning update is

θk\+1=θk\+α​ϕ​\(sk,ak\)​\(rk\+1\+γ​maxu∈𝒜⁡ϕ​\(sk′,u\)⊤​θk−ϕ​\(sk,ak\)⊤​θk\),k∈\{0,1,…\},\\theta\_\{k\+1\}=\\theta\_\{k\}\+\\alpha\\phi\(s\_\{k\},a\_\{k\}\)\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}\\phi\(s^\{\\prime\}\_\{k\},u\)^\{\\top\}\\theta\_\{k\}\-\\phi\(s\_\{k\},a\_\{k\}\)^\{\\top\}\\theta\_\{k\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\},whereα∈\(0,1\)\\alpha\\in\(0,1\)is the step\-size, and the initial parameterθ0\\theta\_\{0\}is assumed to be deterministic throughout this paper\. The parameterθk\\theta\_\{k\}determines the approximate action\-value functionQθk=Φ​θkQ\_\{\\theta\_\{k\}\}=\\Phi\\theta\_\{k\}\. The term inside parentheses is the temporal\-difference error formed from the greedy next\-action value under the same parameter\. The rest of the paper studies the deterministic averaged version of this update and then returns to sampled updates under i\.i\.d\. and Markovian observation models\.

Taking expectation with respect to the sampling distribution and the transition kernel gives the deterministic linear Q\-learning recursion

θk\+1=θk\+α​Φ⊤​D​\(R\+γ​P​Vθk−Φ​θk\),k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\theta\_\{k\}\+\\alpha\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\_\{k\}\}\-\\Phi\\theta\_\{k\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.\(2\)Let us define the deterministic linear Q\-learning map

𝐓α​\(θ\):=θ\+α​g​\(θ\),\\mathbf\{T\}\_\{\\alpha\}\(\\theta\):=\\theta\+\\alpha g\(\\theta\),\(3\)where

g​\(θ\):=Φ⊤​D​\(R\+γ​P​Vθ−Φ​θ\)g\(\\theta\):=\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\-\\Phi\\theta\\right\)\(4\)will be called the projected Bellman residual\. With this notation,[Equation˜2](https://arxiv.org/html/2605.11021#S3.E2)is written compactly as

θk\+1=𝐓α​\(θk\),k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.
The following lemma states the exact relation between the projected Bellman equation in[Equation˜1](https://arxiv.org/html/2605.11021#S3.E1)and the projected Bellman residual equationg​\(θ\)=0g\(\\theta\)=0\.

###### Lemma 2\.

Suppose thatΦ⊤​D​Φ\\Phi^\{\\top\}D\\Phiis nonsingular\. Then the solution set ofg​\(θ\)=0g\(\\theta\)=0is identical to the solution set of the projected Bellman equation[Equation˜1](https://arxiv.org/html/2605.11021#S3.E1)\.

By[Lemma˜2](https://arxiv.org/html/2605.11021#Thmlemma2), a projected Bellman fixed pointθ⋆\\theta^\{\\star\}can equivalently be characterized by the equation

Φ⊤​D​\(R\+γ​P​Vθ⋆−Φ​θ⋆\)=g​\(θ⋆\)=0\.\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\)=g\(\\theta^\{\\star\}\)=0\.\(5\)Therefore, a projected Bellman fixed point is precisely a zero of the projected Bellman residual,g​\(θ⋆\)=0g\(\\theta^\{\\star\}\)=0\. Equivalently, because𝐓α​\(θ\)=θ\+α​g​\(θ\)\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)=\\theta\+\\alpha g\(\\theta\)andα\>0\\alpha\>0, the same point satisfies

𝐓α​\(θ⋆\)=θ⋆\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta^\{\\star\}\)=\\theta^\{\\star\}\.
It is important to distinguish the deterministic linear Q\-learning recursion in[Equation˜2](https://arxiv.org/html/2605.11021#S3.E2)from projected Q\-VI\. The deterministic linear Q\-learning recursion can be written as a residual step toward the projected Q\-VI update:

θk\+1=θk\+α​Φ⊤​D​Φ​\(θk\+1PQVI−θk\),k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\theta\_\{k\}\+\\alpha\\Phi^\{\\top\}D\\Phi\\left\(\\theta\_\{k\+1\}^\{\\mathrm\{PQVI\}\}\-\\theta\_\{k\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.The two iterations coincide only in the special scalar\-stepsize case

α​Φ⊤​D​Φ=I\.\\alpha\\Phi^\{\\top\}D\\Phi=I\.Equality of the fixed points of the deterministic linear Q\-learning and the projected Q\-VI does not imply equality of their convergence behavior\. In general, convergence of one iteration does not automatically imply convergence of the other\. A closely related discussion appears in\[[22](https://arxiv.org/html/2605.11021#bib.bib50)\], where examples show that convergence of either one of the two iterations need not guarantee convergence of the other\. The following two examples make this separation explicit\.

###### Example 1\(Deterministic linear Q\-learning converges while projected Q\-VI diverges\)\.

Consider a two\-state MDP with one action, zero reward, discount factorγ=0\.9\\gamma=0\.9,α=0\.1\\alpha=0\.1, and transition matrix

P=\[0101\]\.P=\\begin\{bmatrix\}0&1\\\\ 0&1\\end\{bmatrix\}\.Let the sampling distribution and feature matrix be

d​\(1,1\)=0\.99,d​\(2,1\)=0\.01,Φ=\[1−10\]\.d\(1,1\)=0\.99,\\qquad d\(2,1\)=0\.01,\\qquad\\Phi=\\begin\{bmatrix\}1\\\\ \-10\\end\{bmatrix\}\.Since there is only one action, the maximization is trivial andVθ=Φ​θV\_\{\\theta\}=\\Phi\\theta\. Hence

Φ⊤​D​Φ=0\.99⋅12\+0\.01⋅\(−10\)2=1\.99,\\Phi^\{\\top\}D\\Phi=0\.99\\cdot 1^\{2\}\+0\.01\\cdot\(\-10\)^\{2\}=1\.99,and, sinceP​Φ=\(−10,−10\)⊤P\\Phi=\(\-10,\-10\)^\{\\top\},

Φ⊤​D​P​Φ=0\.99⋅1⋅\(−10\)\+0\.01⋅\(−10\)⋅\(−10\)=−8\.9\.\\Phi^\{\\top\}DP\\Phi=0\.99\\cdot 1\\cdot\(\-10\)\+0\.01\\cdot\(\-10\)\\cdot\(\-10\)=\-8\.9\.The projected Q\-VI is the scalar recursion

θk\+1PQVI=γ​Φ⊤​D​P​ΦΦ⊤​D​Φ​θk=−8\.011\.99​θk,k∈\{0,1,…\}\.\\theta\_\{k\+1\}^\{\\mathrm\{PQVI\}\}=\\gamma\\frac\{\\Phi^\{\\top\}DP\\Phi\}\{\\Phi^\{\\top\}D\\Phi\}\\theta\_\{k\}=\-\\frac\{8\.01\}\{1\.99\}\\theta\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Since8\.01/1\.99\>18\.01/1\.99\>1, projected Q\-VI diverges for every nonzero initial condition\. On the other hand, the deterministic linear Q\-learning recursion is

θk\+1\\displaystyle\\theta\_\{k\+1\}=\(1−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​Φ\)​θk\\displaystyle=\\left\(1\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\Phi\\right\)\\theta\_\{k\}=\(1−0\.1⋅1\.99\+0\.1⋅0\.9⋅\(−8\.9\)\)​θk=0,k∈\{0,1,…\}\.\\displaystyle=\\left\(1\-0\.1\\cdot 1\.99\+0\.1\\cdot 0\.9\\cdot\(\-8\.9\)\\right\)\\theta\_\{k\}=0,\\qquad k\\in\\\{0,1,\\ldots\\\}\.Thus deterministic linear Q\-learning reaches the projected Bellman fixed pointθ⋆=0\\theta^\{\\star\}=0in one step, while projected Q\-VI diverges\.

###### Example 2\(Projected Q\-VI converges while deterministic linear Q\-learning diverges\)\.

Consider a one\-state MDP with one action, zero reward, deterministic self\-transition,γ=0\.9\\gamma=0\.9,α=0\.5\\alpha=0\.5,d​\(1,1\)=1d\(1,1\)=1, and the one\-dimensional feature representationΦ=10\\Phi=10\. Again, the maximization is trivial\. In this case

Φ⊤​D​Φ=100,Φ⊤​D​P​Φ=100\.\\Phi^\{\\top\}D\\Phi=100,\\qquad\\Phi^\{\\top\}DP\\Phi=100\.Therefore projected Q\-VI satisfies

θk\+1PQVI=γ​Φ⊤​D​P​ΦΦ⊤​D​Φ​θk=0\.9​θk,k∈\{0,1,…\},\\theta\_\{k\+1\}^\{\\mathrm\{PQVI\}\}=\\gamma\\frac\{\\Phi^\{\\top\}DP\\Phi\}\{\\Phi^\{\\top\}D\\Phi\}\\theta\_\{k\}=0\.9\\theta\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\},which converges to0\. However, deterministic linear Q\-learning satisfies

θk\+1\\displaystyle\\theta\_\{k\+1\}=\(1−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​Φ\)​θk\\displaystyle=\\left\(1\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\Phi\\right\)\\theta\_\{k\}=\(1−0\.5⋅100\+0\.5⋅0\.9⋅100\)​θk=−4​θk,k∈\{0,1,…\}\.\\displaystyle=\\left\(1\-0\.5\\cdot 100\+0\.5\\cdot 0\.9\\cdot 100\\right\)\\theta\_\{k\}=\-4\\theta\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Thus deterministic linear Q\-learning diverges for every nonzero initial condition, even though projected Q\-VI converges to the same fixed point\.

## 4Analysis of Deterministic Linear Q\-Learning

### 4\.1Switching System Representation

The next lemma is the key step that expresses Q\-learning recursions as switched\-system dynamics, and it is motivated by\[[10](https://arxiv.org/html/2605.11021#bib.bib48)\]\.

###### Lemma 3\(Stochastic\-policy linearization\)\.

For everyθ,θ¯∈ℝm\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}, there exists a stochastic policyμθ,θ¯:𝒮→Δ\|𝒜\|\\mu\_\{\\theta,\\bar\{\\theta\}\}:\\mathcal\{S\}\\to\\Delta\_\{\|\\mathcal\{A\}\|\}such that

Vθ−Vθ¯=𝚷μθ,θ¯​Φ​\(θ−θ¯\)\.V\_\{\\theta\}\-V\_\{\\bar\{\\theta\}\}=\\boldsymbol\{\\Pi\}^\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\\Phi\(\\theta\-\\bar\{\\theta\}\)\.Moreover,μθ,θ¯\\mu\_\{\\theta,\\bar\{\\theta\}\}can be chosen as a measurable function of\(θ,θ¯\)\(\\theta,\\bar\{\\theta\}\)\.

The above lemma converts a nonlinear maximization difference into a policy\-indexed linear operator\. For a stochastic policyμ\\mu, let us define

𝐀μ:=I−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​𝚷μ​Φ∈ℝm×m\.\\mathbf\{A\}\_\{\\mu\}:=I\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\mu\}\\Phi\\in\\mathbb\{R\}^\{m\\times m\}\.The next proposition shows that the deterministic linear Q\-learning update inherits identical linear switching system representation\.

###### Proposition 1\.

For everyθ,θ¯∈ℝm\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}, there exists a stochastic policyμθ,θ¯\\mu\_\{\\theta,\\bar\{\\theta\}\}such that

𝐓α​\(θ\)−𝐓α​\(θ¯\)=𝐀μθ,θ¯​\(θ−θ¯\)\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)=\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\(\\theta\-\\bar\{\\theta\}\)\.In particular, ifθ⋆\\theta^\{\\star\}is a projected Bellman fixed point andxk:=θk−θ⋆x\_\{k\}:=\\theta\_\{k\}\-\\theta^\{\\star\}, then the deterministic linear Q\-learning recursionθk\+1=𝐓α​\(θk\)\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)satisfies

xk\+1=𝐀μk​xk,k∈\{0,1,…\},x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\},\(6\)whereμk\\mu\_\{k\}is a stochastic policy depending measurably onθk\\theta\_\{k\}andθ⋆\\theta^\{\\star\}\.

An explicit trajectory\-level example illustrating[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1)is given in[Example˜8](https://arxiv.org/html/2605.11021#Thmexample8)\. Therefore, the deterministic linear Q\-learning recursion in[Equation˜2](https://arxiv.org/html/2605.11021#S3.E2)is exactly represented by the switched linear error recursion in[Equation˜6](https://arxiv.org/html/2605.11021#S4.E6), relative to a projected Bellman fixed point\. This allows the convergence of deterministic linear Q\-learning to be analyzed through the stability of[Equation˜6](https://arxiv.org/html/2605.11021#S4.E6)\.

The set of all possible such matrices corresponding to deterministic policies is defined as

𝒜α:=\{𝐀π:=I−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​𝚷π​Φ:π∈Θ\}\.\\mathcal\{A\}\_\{\\alpha\}:=\\left\\\{\\mathbf\{A\}\_\{\\pi\}:=I\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi:\\pi\\in\\Theta\\right\\\}\.The corresponding JSR is defined as

ραdir:=ρ​\(𝒜α\)\.\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}:=\\rho\(\\mathcal\{A\}\_\{\\alpha\}\)\.
The JSRραdir\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}above is defined for the finite deterministic matrix family𝒜α\\mathcal\{A\}\_\{\\alpha\}\. However, the switched system in[Equation˜6](https://arxiv.org/html/2605.11021#S4.E6)can involve stochastic\-policy modes𝐀μ\\mathbf\{A\}\_\{\\mu\}, so a direct arbitrary\-switching analysis would appear to require the JSR over all such stochastic\-policy matrices\. To close this gap,[Section˜B\.4](https://arxiv.org/html/2605.11021#A2.SS4)proves in[Lemma˜4](https://arxiv.org/html/2605.11021#Thmlemma4)that every stochastic\-policy mode lies in the convex hull of the finite deterministic modes, and that the JSR of this convex hull is equal to the finite\-family JSR\. Thus the finite matrices in𝒜α\\mathcal\{A\}\_\{\\alpha\}are sufficient for certifying all Bellman\-induced stochastic modes\.

### 4\.2Analysis of Deterministic Linear Q\-Learning

This section analyzes[Equation˜2](https://arxiv.org/html/2605.11021#S3.E2)using the JSR of the switching family𝒜α\\mathcal\{A\}\_\{\\alpha\}\. The first step is to build a Lyapunov norm directly from products of the finite switching famity𝒜α\\mathcal\{A\}\_\{\\alpha\}\. To this end, let us assume

ραdir<1\.\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\.Fix anyε\>0\\varepsilon\>0such that

βε:=ραdir\+ε<1\.\\beta\_\{\\varepsilon\}:=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1\.For each integert≥0t\\geq 0, let us define

Vεt​\(x\):=∑ℓ=0tβε−2​ℓ​maxπ1,…,πℓ∈Θ⁡‖𝐀πℓ​⋯​𝐀π1​x‖22,x∈ℝm,V\_\{\\varepsilon\}^\{t\}\(x\):=\\sum\_\{\\ell=0\}^\{t\}\\beta\_\{\\varepsilon\}^\{\-2\\ell\}\\max\_\{\\pi\_\{1\},\\ldots,\\pi\_\{\\ell\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{\\ell\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{1\}\}x\\right\\\|\_\{2\}^\{2\},\\qquad x\\in\\mathbb\{R\}^\{m\},where theℓ=0\\ell=0term is‖x‖22\\\|x\\\|\_\{2\}^\{2\}\. Now, define

Vε∞​\(x\):=limt→∞Vεt​\(x\)\.V\_\{\\varepsilon\}^\{\\infty\}\(x\):=\\lim\_\{t\\to\\infty\}V\_\{\\varepsilon\}^\{t\}\(x\)\.\(7\)The piecewise quadratic construction below turns the JSR condition into a global contraction certificate for the nonlinear projected Bellman map\. The following theorem states the deterministic convergence result\.

###### Theorem 1\(Deterministic JSR Lyapunov convergence\)\.

Suppose that

ραdir<1\.\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\.Fixε\>0\\varepsilon\>0such thatβε:=ραdir\+ε<1\\beta\_\{\\varepsilon\}:=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1\. ThenVε∞V\_\{\\varepsilon\}^\{\\infty\}in[Equation˜7](https://arxiv.org/html/2605.11021#S4.E7)is well\-defined, and there existsCε≥1C\_\{\\varepsilon\}\\geq 1such that

‖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\}\.\(8\)Moreover,

pε​\(x\):=Vε∞​\(x\)p\_\{\\varepsilon\}\(x\):=\\sqrt\{V\_\{\\varepsilon\}^\{\\infty\}\(x\)\}is a norm, and for every stochastic policyμ\\mu,

Vε∞​\(𝐀μ​x\)≤βε2​\(Vε∞​\(x\)−‖x‖22\)≤βε2​Vε∞​\(x\)\.V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{A\}\_\{\\mu\}x\)\\leq\\beta\_\{\\varepsilon\}^\{2\}\\left\(V\_\{\\varepsilon\}^\{\\infty\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\\leq\\beta\_\{\\varepsilon\}^\{2\}V\_\{\\varepsilon\}^\{\\infty\}\(x\)\.\(9\)Consequently,

pε​\(𝐀μ​x\)≤βε​pε​\(x\),∀x∈ℝm\.p\_\{\\varepsilon\}\(\\mathbf\{A\}\_\{\\mu\}x\)\\leq\\beta\_\{\\varepsilon\}p\_\{\\varepsilon\}\(x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{m\}\.\(10\)The deterministic map𝐓α\\mathbf\{T\}\_\{\\alpha\}is a global contraction inpεp\_\{\\varepsilon\}:

pε​\(𝐓α​\(θ\)−𝐓α​\(θ¯\)\)≤βε​pε​\(θ−θ¯\),∀θ,θ¯∈ℝm\.p\_\{\\varepsilon\}\(\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)\)\\leq\\beta\_\{\\varepsilon\}p\_\{\\varepsilon\}\(\\theta\-\\bar\{\\theta\}\),\\qquad\\forall\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}\.\(11\)Hence there exists a unique projected Bellman fixed pointθ⋆\\theta^\{\\star\}satisfying[Equation˜5](https://arxiv.org/html/2605.11021#S3.E5)\. For the deterministic recursion[Equation˜2](https://arxiv.org/html/2605.11021#S3.E2),

Vε∞​\(θk−θ⋆\)≤βε2​k​Vε∞​\(θ0−θ⋆\),V\_\{\\varepsilon\}^\{\\infty\}\(\\theta\_\{k\}\-\\theta^\{\\star\}\)\\leq\\beta\_\{\\varepsilon\}^\{2k\}V\_\{\\varepsilon\}^\{\\infty\}\(\\theta\_\{0\}\-\\theta^\{\\star\}\),\(12\)and therefore

‖θk−θ⋆‖2≤Cε​βεk​‖θ0−θ⋆‖2\.\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\\leq\\sqrt\{C\_\{\\varepsilon\}\}\\,\\beta\_\{\\varepsilon\}^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\.In Q\-function norm,

‖Φ​θk−Φ​θ⋆‖2≤‖Φ‖2​Cε​βεk​‖θ0−θ⋆‖2\.\\\|\\Phi\\theta\_\{k\}\-\\Phi\\theta^\{\\star\}\\\|\_\{2\}\\leq\\\|\\Phi\\\|\_\{2\}\\sqrt\{C\_\{\\varepsilon\}\}\\,\\beta\_\{\\varepsilon\}^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\.

![Refer to caption](https://arxiv.org/html/2605.11021v1/x1.png)Figure 1:Truncated Theorem 1 norm ball for the MDP in[Example˜3](https://arxiv.org/html/2605.11021#Thmexample3)\. Since the feature dimension is three, the set\{x∈ℝ3:pε,T​\(x\)≤1\}\\\{x\\in\\mathbb\{R\}^\{3\}:p\_\{\\varepsilon,T\}\(x\)\\leq 1\\\}can be plotted directly, without projection\.###### Example 3\(A three\-dimensional MDP norm ball\)\.

Consider a three\-state, two\-action MDP with𝒮=\{1,2,3\}\\mathcal\{S\}=\\\{1,2,3\\\}and𝒜=\{1,2\}\\mathcal\{A\}=\\\{1,2\\\}\. Enumerate the state\-action pairs in the action\-block order

\(1,1\),\(2,1\),\(3,1\),\(1,2\),\(2,2\),\(3,2\)\(1,1\),\(2,1\),\(3,1\),\(1,2\),\(2,2\),\(3,2\)\. Let the transition matrix be

P=\[0\.73250\.01220\.25520\.63590\.21040\.15370\.51330\.19500\.29170\.47220\.03790\.48990\.00230\.86700\.13070\.74370\.05530\.2010\],P=\\begin\{bmatrix\}0\.7325&0\.0122&0\.2552\\\\ 0\.6359&0\.2104&0\.1537\\\\ 0\.5133&0\.1950&0\.2917\\\\ 0\.4722&0\.0379&0\.4899\\\\ 0\.0023&0\.8670&0\.1307\\\\ 0\.7437&0\.0553&0\.2010\\end\{bmatrix\},letγ=0\.7965\\gamma=0\.7965,α=0\.9000\\alpha=0\.9000

D=diag⁡\(0\.1595,0\.0198,0\.1480,0\.2228,0\.2155,0\.2343\),D=\\operatorname\{diag\}\(0\.1595,\\,0\.0198,\\,0\.1480,\\,0\.2228,\\,0\.2155,\\,0\.2343\),and choose the feature matrix

Φ=\[−0\.0957−0\.3996−0\.50500\.02420\.13280\.18580\.73780\.45820\.0919−0\.48820\.53050\.2531−0\.2158−0\.1461−0\.25950\.40130\.5568−0\.7554\]∈ℝ6×3\.\\Phi=\\begin\{bmatrix\}\-0\.0957&\-0\.3996&\-0\.5050\\\\ 0\.0242&0\.1328&0\.1858\\\\ 0\.7378&0\.4582&0\.0919\\\\ \-0\.4882&0\.5305&0\.2531\\\\ \-0\.2158&\-0\.1461&\-0\.2595\\\\ 0\.4013&0\.5568&\-0\.7554\\end\{bmatrix\}\\in\\mathbb\{R\}^\{6\\times 3\}\.Since there are three states and two actions, there are23=82^\{3\}=8deterministic policies\. For each deterministic policyπ∈Θ\\pi\\in\\Theta, the corresponding direct mode is

𝐀π=I−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​𝚷π​Φ∈ℝ3×3\.\\mathbf\{A\}\_\{\\pi\}=I\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\in\\mathbb\{R\}^\{3\\times 3\}\.For this example, the eight mode norms are approximately

0\.8966,0\.9324,0\.9135,0\.9461,0\.9335,0\.9653,0\.9338,0\.9678\.0\.8966,\\quad 0\.9324,\\quad 0\.9135,\\quad 0\.9461,\\quad 0\.9335,\\quad 0\.9653,\\quad 0\.9338,\\quad 0\.9678\.Hence, for every product lengthkk, submultiplicativity gives the common induced\-norm bound

ραdir\\displaystyle\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=limk→∞maxπ1,…,πk∈Θ⁡‖𝐀πk​⋯​𝐀π1‖21/k\\displaystyle=\\lim\_\{k\\to\\infty\}\\max\_\{\\pi\_\{1\},\\ldots,\\pi\_\{k\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{k\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{1\}\}\\right\\\|\_\{2\}^\{1/k\}≤limk→∞maxπ1,…,πk∈Θ\(∏j=1k∥𝐀πj∥2\)1/k\\displaystyle\\leq\\lim\_\{k\\to\\infty\}\\max\_\{\\pi\_\{1\},\\ldots,\\pi\_\{k\}\\in\\Theta\}\\left\(\\prod\_\{j=1\}^\{k\}\\\|\\mathbf\{A\}\_\{\\pi\_\{j\}\}\\\|\_\{2\}\\right\)^\{1/k\}≤maxπ∈Θ⁡‖𝐀π‖2=0\.9678<1\.\\displaystyle\\leq\\max\_\{\\pi\\in\\Theta\}\\\|\\mathbf\{A\}\_\{\\pi\}\\\|\_\{2\}=9678<1\.Therefore,[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)applies\. We chooseβε=0\.975\\beta\_\{\\varepsilon\}=0\.975,T=4T=4, so thatmaxπ∈Θ⁡‖𝐀π‖2<βε<1\\max\_\{\\pi\\in\\Theta\}\\\|\\mathbf\{A\}\_\{\\pi\}\\\|\_\{2\}<\\beta\_\{\\varepsilon\}<1\. For intuition,[Figure˜1](https://arxiv.org/html/2605.11021#S4.F1)shows a three\-dimensional visualization of the truncated norm ball induced by[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)

pε,T​\(x\):=∑ℓ=0Tβε−2​ℓ​maxπ1,…,πℓ∈Θ⁡‖𝐀πℓ​⋯​𝐀π1​x‖22,p\_\{\\varepsilon,T\}\(x\):=\\sqrt\{\\sum\_\{\\ell=0\}^\{T\}\\beta\_\{\\varepsilon\}^\{\-2\\ell\}\\max\_\{\\pi\_\{1\},\\ldots,\\pi\_\{\\ell\}\\in\\Theta\}\\left\\\|\\mathbf\{A\}\_\{\\pi\_\{\\ell\}\}\\cdots\\mathbf\{A\}\_\{\\pi\_\{1\}\}x\\right\\\|\_\{2\}^\{2\}\},which approximates the normpε​\(x\)=Vε∞​\(x\)p\_\{\\varepsilon\}\(x\)=\\sqrt\{V\_\{\\varepsilon\}^\{\\infty\}\(x\)\}from[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)\. The resulting surface in[Figure˜1](https://arxiv.org/html/2605.11021#S4.F1)is visibly non\-Euclidean: the maximizing switched products produces a slightly bumpy but smooth curved norm ball rather than a sphere\.

The previous theorem gives convergence of deterministic linear Q\-learning fromραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. However, the theorem also gives a robust certificate for the larger arbitrary\-switching inclusion, which is a conservative worst\-case model: it allows switching sequences that may never be generated by the Bellman maximum along an actual trajectory \([Section˜C\.2](https://arxiv.org/html/2605.11021#A3.SS2)\)\. The actual deterministic nonlinear recursionθk\+1=𝐓α​\(θk\)\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)realizes only those stochastic policies generated by Bellman maximization along a trajectory\. Thereforeραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1is used here as a sufficient condition\. A valueραdir\>1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\>1shows that the larger arbitrary\-switching inclusion can be unstable, but it does not by itself show nonconvergence of the Bellman\-generated nonlinear recursion\.

The preceding discussion shows that the arbitrary\-switching inclusion and the actual nonlinear recursion should not be identified\. The following example makes this distinction explicit: the direct JSR is larger than one, so the arbitrary\-switching inclusion can be unstable, but the Bellman\-generated nonlinear recursion is globally convergent\.

###### Example 4\.

Consider a one\-state MDP with𝒮=\{1\}\\mathcal\{S\}=\\\{1\\\}, two actions𝒜=\{1,2\}\\mathcal\{A\}=\\\{1,2\\\}, zero reward, and deterministic self\-transition ,P​\(1∣1,a\)=1P\(1\\mid 1,a\)=1,R​\(1,a\)=0R\(1,a\)=0\. Letγ=0\.9\\gamma=0\.9,α=0\.9\\alpha=0\.9,d​\(1,1\)=0\.9d\(1,1\)=0\.9,d​\(1,2\)=0\.1d\(1,2\)=0\.1, and use the one\-dimensional feature representation

ϕ​\(1,1\)=1,ϕ​\(1,2\)=−2,Φ=\[1−2\]\.\\phi\(1,1\)=1,\\qquad\\phi\(1,2\)=\-2,\\qquad\\Phi=\\begin\{bmatrix\}1\\\\ \-2\\end\{bmatrix\}\.Then

Φ⊤​D​Φ=0\.9⋅12\+0\.1⋅\(−2\)2=1\.3,Φ⊤​D​P=0\.9⋅1\+0\.1⋅\(−2\)=0\.7\.\\Phi^\{\\top\}D\\Phi=0\.9\\cdot 1^\{2\}\+0\.1\\cdot\(\-2\)^\{2\}=1\.3,\\qquad\\Phi^\{\\top\}DP=0\.9\\cdot 1\+0\.1\\cdot\(\-2\)=0\.7\.There are two deterministic policies, selecting action 1 or action 2\. The corresponding scalar direct modes are

𝐀1=1−0\.9⋅1\.3\+0\.9⋅0\.9⋅0\.7⋅1=0\.397,𝐀2=1−0\.9⋅1\.3\+0\.9⋅0\.9⋅0\.7⋅\(−2\)=−1\.304\.\\mathbf\{A\}\_\{1\}=1\-0\.9\\cdot 1\.3\+0\.9\\cdot 0\.9\\cdot 0\.7\\cdot 1=0\.397,\\qquad\\mathbf\{A\}\_\{2\}=1\-0\.9\\cdot 1\.3\+0\.9\\cdot 0\.9\\cdot 0\.7\\cdot\(\-2\)=\-1\.304\.Hence

ραdir=ρ​\(\{0\.397,−1\.304\}\)=1\.304\>1\.\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=\\rho\(\\\{0\.397,\-1\.304\\\}\)=1\.304\>1\.The arbitrary\-switching inclusion can therefore generate the divergent trajectoryxk=\(−1\.304\)k​x0x\_\{k\}=\(\-1\.304\)^\{k\}x\_\{0\}by repeatedly selecting the second mode\.

The actual deterministic nonlinear recursion behaves differently\. Since rewards are zero,

Vθ=max⁡\{θ,−2​θ\},V\_\{\\theta\}=\\max\\\{\\theta,\-2\\theta\\\},and the mean update is

𝐓α​\(θ\)=θ\+Φ⊤​D​\(γ​P​Vθ−Φ​θ\)=−0\.17​θ\+0\.567​max⁡\{θ,−2​θ\}\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)=\\theta\+\\Phi^\{\\top\}D\\left\(\\gamma PV\_\{\\theta\}\-\\Phi\\theta\\right\)=\-0\.17\\theta\+0\.567\\max\\\{\\theta,\-2\\theta\\\}\.Thus

𝐓α​\(θ\)=\{0\.397​θ,θ≥0,−1\.304​θ,θ<0\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)=\\begin\{cases\}0\.397\\theta,&\\theta\\geq 0,\\\\ \-1\.304\\theta,&\\theta<0\.\\end\{cases\}Ifθ0≥0\\theta\_\{0\}\\geq 0, thenθk=0\.397k​θ0→0\\theta\_\{k\}=0\.397^\{k\}\\theta\_\{0\}\\to 0\. Ifθ0<0\\theta\_\{0\}<0, thenθ1=−1\.304​θ0\>0\\theta\_\{1\}=\-1\.304\\theta\_\{0\}\>0, and from that point onward

θk=0\.397k−1​θ1→0\.\\theta\_\{k\}=0\.397^\{k\-1\}\\theta\_\{1\}\\to 0\.Therefore the actual deterministic nonlinear recursion converges globally to the unique fixed pointθ⋆=0\\theta^\{\\star\}=0, even thoughραdir\>1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\>1\.

The reason is that the unstable second mode is not repeatedly admissible under Bellman maximization\. It is selected only whenθ<0\\theta<0, and one application sends the iterate to the regionθ\>0\\theta\>0, where the stable first mode is selected\. Therefore, the product𝐀2​𝐀2​𝐀2​⋯\\mathbf\{A\}\_\{2\}\\mathbf\{A\}\_\{2\}\\mathbf\{A\}\_\{2\}\\cdots, although allowed by the arbitrary\-switching inclusion and counted by the JSR, is not realized by the actual Bellman\-generated dynamics\.

## 5i\.i\.d\. Linear Q\-Learning

This section analyzes the sampled linear Q\-learning recursion under an independent and identically distributed \(i\.i\.d\.\) observation model\. The analysis uses the same JSR Lyapunov norm constructed for the deterministic direct family\.

### 5\.1i\.i\.d\. Sampled Recursion

At each timekk, sample\(sk,ak\)\(s\_\{k\},a\_\{k\}\)independently according todd, then samplesk′∼P\(⋅∣sk,ak\)s^\{\\prime\}\_\{k\}\\sim P\(\\cdot\\mid s\_\{k\},a\_\{k\}\), and setrk\+1:=r​\(sk,ak,sk′\)r\_\{k\+1\}:=r\(s\_\{k\},a\_\{k\},s^\{\\prime\}\_\{k\}\)\. Define the filtration explicitly by

ℱ0:=σ​\(θ0\),ℱk:=σ​\(θ0,\{\(st,at,st′,rt\+1\):0≤t≤k−1\}\),k≥1\.\\mathcal\{F\}\_\{0\}:=\\sigma\(\\theta\_\{0\}\),\\qquad\\mathcal\{F\}\_\{k\}:=\\sigma\\left\(\\theta\_\{0\},\\\{\(s\_\{t\},a\_\{t\},s^\{\\prime\}\_\{t\},r\_\{t\+1\}\):0\\leq t\\leq k\-1\\\}\\right\),\\quad k\\geq 1\.The linear Q\-learning update is

θk\+1=θk\+α​ϕ​\(sk,ak\)​\(rk\+1\+γ​maxu∈𝒜⁡ϕ​\(sk′,u\)⊤​θk−ϕ​\(sk,ak\)⊤​θk\),k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\theta\_\{k\}\+\\alpha\\phi\(s\_\{k\},a\_\{k\}\)\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}\\phi\(s^\{\\prime\}\_\{k\},u\)^\{\\top\}\\theta\_\{k\}\-\\phi\(s\_\{k\},a\_\{k\}\)^\{\\top\}\\theta\_\{k\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.\(13\)Define the sample update vector

g^k​\(θ\):=ϕ​\(sk,ak\)​\(rk\+1\+γ​maxu∈𝒜⁡ϕ​\(sk′,u\)⊤​θ−ϕ​\(sk,ak\)⊤​θ\)\.\\widehat\{g\}\_\{k\}\(\\theta\):=\\phi\(s\_\{k\},a\_\{k\}\)\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}\\phi\(s^\{\\prime\}\_\{k\},u\)^\{\\top\}\\theta\-\\phi\(s\_\{k\},a\_\{k\}\)^\{\\top\}\\theta\\right\)\.Then

𝔼​\[g^k​\(θk\)∣ℱk\]=g​\(θk\),\\mathbb\{E\}\[\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\\mid\\mathcal\{F\}\_\{k\}\]=g\(\\theta\_\{k\}\),\(14\)whereggis defined in[Equation˜4](https://arxiv.org/html/2605.11021#S3.E4)\. This identifies the sampled recursion as the deterministic map plus a martingale\-difference perturbation\. Define the martingale\-difference noise

wk:=g^k​\(θk\)−g​\(θk\)\.w\_\{k\}:=\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\-g\(\\theta\_\{k\}\)\.\(15\)Then𝔼​\[wk∣ℱk\]=0\\mathbb\{E\}\[w\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=0, and[Equation˜13](https://arxiv.org/html/2605.11021#S5.E13)becomes

θk\+1=𝐓α​\(θk\)\+α​wk,k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.\(16\)
The exact switching system representation from the deterministic analysis can now be applied pathwise to the conditional mean part of the stochastic recursion\.

###### Proposition 2\.

Suppose thatραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. Letθ⋆\\theta^\{\\star\}be the unique projected Bellman fixed point from[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1), and define

xk:=θk−θ⋆\.x\_\{k\}:=\\theta\_\{k\}\-\\theta^\{\\star\}\.Then, for eachk∈\{0,1,…\}k\\in\\\{0,1,\\ldots\\\}, there exists anℱk\\mathcal\{F\}\_\{k\}\-measurable stochastic policyμk\\mu\_\{k\}such that

xk\+1=𝐀μk​xk\+α​wk,k∈\{0,1,…\},x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\},\(17\)where𝔼​\[wk∣ℱk\]=0\\mathbb\{E\}\[w\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=0\.

To turn this recursion into a finite\-time bound, the remaining task is to control the martingale term in the same JSR Lyapunov norm\.

### 5\.2Constant\-Step\-Size Bounded\-Error Bound

The stochastic recursion[Equation˜17](https://arxiv.org/html/2605.11021#S5.E17)is the deterministic switching system plus martingale\-difference noise\. The following theorem gives the corresponding constant step\-size i\.i\.d\. bounded\-error estimate in the JSR Lyapunov norm\.

###### Theorem 3\(i\.i\.d\. constant\-step\-size bounded\-error estimate via the JSR Lyapunov norm\)\.

Suppose that

ραdir<1\.\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\.Fixε\>0\\varepsilon\>0such thatβε:=ραdir\+ε<1\\beta\_\{\\varepsilon\}:=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1, and letpεp\_\{\\varepsilon\}be the JSR Lyapunov norm in[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)\. The constantCεC\_\{\\varepsilon\}appearing below is defined in[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8)\. Assume additionally that

λε:=βε\+2​α​Cε​\(1\+γ\)​ϕmax2<1\.\\lambda\_\{\\varepsilon\}:=\\beta\_\{\\varepsilon\}\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}<1\.\(18\)Then the i\.i\.d\. linear Q\-learning recursion[Equation˜13](https://arxiv.org/html/2605.11021#S5.E13)satisfies, for allk≥0k\\geq 0,

𝔼​\[pε​\(xk\)\]≤λεk​pε​\(x0\)\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε​\(1−λεk\)\.\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(x\_\{k\}\)\]\\leq\\lambda\_\{\\varepsilon\}^\{k\}p\_\{\\varepsilon\}\(x\_\{0\}\)\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\\left\(1\-\\lambda\_\{\\varepsilon\}^\{k\}\\right\)\.\(19\)Consequently,

𝔼​\[‖θk−θ⋆‖2\]≤Cε​λεk​‖θ0−θ⋆‖2\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε,\\displaystyle\\mathbb\{E\}\[\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\sqrt\{C\_\{\\varepsilon\}\}\\,\\lambda\_\{\\varepsilon\}^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\},\(20\)and

lim supk→∞𝔼​\[‖θk−θ⋆‖2\]≤2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε\.\\limsup\_\{k\\to\\infty\}\\mathbb\{E\}\[\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\.The corresponding LFA Q\-function error satisfies

𝔼​\[‖Φ​θk−Φ​θ⋆‖2\]≤‖Φ‖2​\(Cε​λεk​‖θ0−θ⋆‖2\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε\)\.\\mathbb\{E\}\[\\\|\\Phi\\theta\_\{k\}\-\\Phi\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\\|\\Phi\\\|\_\{2\}\\left\(\\sqrt\{C\_\{\\varepsilon\}\}\\,\\lambda\_\{\\varepsilon\}^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\\right\)\.\(21\)

The residual term in[Equation˜20](https://arxiv.org/html/2605.11021#S5.E20)is the constant\-step\-size stochastic neighborhood\. It disappears in the deterministic recursion becausewk=0w\_\{k\}=0\. For a fixed JSR Lyapunov certificate satisfying[Equation˜18](https://arxiv.org/html/2605.11021#S5.E18), the transient rate isλε\\lambda\_\{\\varepsilon\}, which is the JSR\-induced drift rateβε\\beta\_\{\\varepsilon\}enlarged by the feature\-dependent noise\-growth coefficient2​α​Cε​\(1\+γ\)​ϕmax22\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}\.

## 6Markovian Observation Model

This section extends the i\.i\.d\. LFA analysis to a single\-trajectory Markovian observation model\. The treatment does not use a mixing\-time argument\. Instead, following the direct\-switching bounded\-error viewpoint, the stationary averaged drift is added and subtracted, and the resulting coordinate\-sampling discrepancy is treated as an additional error term\.

Fix a behavior policyb​\(a∣s\)b\(a\\mid s\)\. The trajectory evolves according to

sk\+1∼P\(⋅∣sk,ak\),rk\+1=r\(sk,ak,sk\+1\),ak\+1∼b\(⋅∣sk\+1\),k∈\{0,1,…\}\.s\_\{k\+1\}\\sim P\(\\cdot\\mid s\_\{k\},a\_\{k\}\),\\qquad r\_\{k\+1\}=r\(s\_\{k\},a\_\{k\},s\_\{k\+1\}\),\\qquad a\_\{k\+1\}\\sim b\(\\cdot\\mid s\_\{k\+1\}\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.Let

Xk:=\(sk,ak\)X\_\{k\}:=\(s\_\{k\},a\_\{k\}\)be the state\-action Markov chain with behavior\-induced transition kernel

Pb​\(s′,a′∣s,a\):=P​\(s′∣s,a\)​b​\(a′∣s′\)\.P^\{b\}\(s^\{\\prime\},a^\{\\prime\}\\mid s,a\):=P\(s^\{\\prime\}\\mid s,a\)b\(a^\{\\prime\}\\mid s^\{\\prime\}\)\.Assume that this chain has stationary distributiondd, and letD=diag⁡\(d​\(s,a\)\)D=\\operatorname\{diag\}\(d\(s,a\)\)as before\. The chain need not be initialized in stationarity\. Letei∈ℝ\|𝒮\|​\|𝒜\|e\_\{i\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\}denote the coordinate vector associated with state\-action indexii\. With the action\-block ordering used above, ifXk=\(sk,ak\)X\_\{k\}=\(s\_\{k\},a\_\{k\}\), then

eXk=eak⊗esk∈ℝ\|𝒜\|​\|𝒮\|,e\_\{X\_\{k\}\}=e\_\{a\_\{k\}\}\\otimes e\_\{s\_\{k\}\}\\in\\mathbb\{R\}^\{\|\\mathcal\{A\}\|\|\\mathcal\{S\}\|\},whereeak∈ℝ\|𝒜\|e\_\{a\_\{k\}\}\\in\\mathbb\{R\}^\{\|\\mathcal\{A\}\|\}andesk∈ℝ\|𝒮\|e\_\{s\_\{k\}\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\}are the standard basis vectors for the action and state coordinates, respectively\. Define the Markovian filtration explicitly by

ℱ0:=σ​\(θ0,X0\),ℱk:=σ​\(θ0,X0,r1,X1,…,rk,Xk\),k≥1\.\\mathcal\{F\}\_\{0\}:=\\sigma\(\\theta\_\{0\},X\_\{0\}\),\\qquad\\mathcal\{F\}\_\{k\}:=\\sigma\\left\(\\theta\_\{0\},X\_\{0\},r\_\{1\},X\_\{1\},\\ldots,r\_\{k\},X\_\{k\}\\right\),\\quad k\\geq 1\.In this Markovian section,ℱk\\mathcal\{F\}\_\{k\}denotes the filtration generated by the single trajectory above; it should not be confused with the i\.i\.d\. filtration introduced in[Section˜5](https://arxiv.org/html/2605.11021#S5)\.

The single\-trajectory linear Q\-learning update is

θk\+1=θk\+α​ϕ​\(sk,ak\)​\(rk\+1\+γ​maxu∈𝒜⁡ϕ​\(sk\+1,u\)⊤​θk−ϕ​\(sk,ak\)⊤​θk\),k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\theta\_\{k\}\+\\alpha\\phi\(s\_\{k\},a\_\{k\}\)\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}\\phi\(s\_\{k\+1\},u\)^\{\\top\}\\theta\_\{k\}\-\\phi\(s\_\{k\},a\_\{k\}\)^\{\\top\}\\theta\_\{k\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.\(22\)For compactness, define

δ​\(θ\):=R\+γ​P​Vθ−Φ​θ∈ℝ\|𝒮\|​\|𝒜\|\.\\delta\(\\theta\):=R\+\\gamma PV\_\{\\theta\}\-\\Phi\\theta\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\}\.The transition\-reward noise is

ξk\+1:=ϕ​\(Xk\)​\(rk\+1\+γ​maxu∈𝒜⁡ϕ​\(sk\+1,u\)⊤​θk−ϕ​\(Xk\)⊤​θk−eXk⊤​δ​\(θk\)\),\\xi\_\{k\+1\}:=\\phi\(X\_\{k\}\)\\left\(r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}\\phi\(s\_\{k\+1\},u\)^\{\\top\}\\theta\_\{k\}\-\\phi\(X\_\{k\}\)^\{\\top\}\\theta\_\{k\}\-e\_\{X\_\{k\}\}^\{\\top\}\\delta\(\\theta\_\{k\}\)\\right\),\(23\)whereϕ​\(Xk\)=ϕ​\(sk,ak\)\\phi\(X\_\{k\}\)=\\phi\(s\_\{k\},a\_\{k\}\)\. Then

𝔼​\[ξk\+1∣ℱk\]=0\.\\mathbb\{E\}\[\\xi\_\{k\+1\}\\mid\\mathcal\{F\}\_\{k\}\]=0\.The parameter recursion can be written as

θk\+1=θk\+α​Φ⊤​eXk​eXk⊤​δ​\(θk\)\+α​ξk\+1,k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\theta\_\{k\}\+\\alpha\\Phi^\{\\top\}e\_\{X\_\{k\}\}e\_\{X\_\{k\}\}^\{\\top\}\\delta\(\\theta\_\{k\}\)\+\\alpha\\xi\_\{k\+1\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Adding and subtracting the stationary averaged drift gives

θk\+1=𝐓α​\(θk\)\+α​bk\+α​ξk\+1,k∈\{0,1,…\},\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)\+\\alpha b\_\{k\}\+\\alpha\\xi\_\{k\+1\},\\qquad k\\in\\\{0,1,\\ldots\\\},\(24\)where

bk:=Φ⊤​\(eXk​eXk⊤−D\)​δ​\(θk\)\.b\_\{k\}:=\\Phi^\{\\top\}\(e\_\{X\_\{k\}\}e\_\{X\_\{k\}\}^\{\\top\}\-D\)\\delta\(\\theta\_\{k\}\)\.\(25\)Thus the Markovian observation model differs from the i\.i\.d\. model by the additional coordinate\-sampling errorbkb\_\{k\}\.

###### Proposition 3\(Exact Markovian direct stochastic recursion\)\.

Suppose thatραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. Letθ⋆\\theta^\{\\star\}be the unique projected Bellman fixed point from[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1), and define

xk:=θk−θ⋆\.x\_\{k\}:=\\theta\_\{k\}\-\\theta^\{\\star\}\.Then, for eachk∈\{0,1,…\}k\\in\\\{0,1,\\ldots\\\}, there exists anℱk\\mathcal\{F\}\_\{k\}\-measurable stochastic policyμk\\mu\_\{k\}such that

xk\+1=𝐀μk​xk\+α​bk\+α​ξk\+1,k∈\{0,1,…\},x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\+\\alpha b\_\{k\}\+\\alpha\\xi\_\{k\+1\},\\qquad k\\in\\\{0,1,\\ldots\\\},\(26\)where𝔼​\[ξk\+1∣ℱk\]=0\\mathbb\{E\}\[\\xi\_\{k\+1\}\\mid\\mathcal\{F\}\_\{k\}\]=0\. The following decomposition separates the fixed\-point residual from the part proportional to the current error\. The Markovian coordinate\-sampling error admits the decomposition

bk=Φ⊤​\(eXk​eXk⊤−D\)​\(R\+γ​P​Vθ⋆−Φ​θ⋆\+\(γ​P​𝚷μk−I\)​Φ​xk\)\.b\_\{k\}=\\Phi^\{\\top\}\(e\_\{X\_\{k\}\}e\_\{X\_\{k\}\}^\{\\top\}\-D\)\\left\(R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\+\(\\gamma P\\boldsymbol\{\\Pi\}^\{\\mu\_\{k\}\}\-I\)\\Phi x\_\{k\}\\right\)\.\(27\)

The Markovian error bound combines the i\.i\.d\.\-type transition\-reward noise with the additional coordinate\-sampling discrepancy\. The proof of the Markovian bound follows the same one\-step contraction argument as in the i\.i\.d\. case, with enlarged constants\.

###### Theorem 4\.

Suppose that

ραdir<1\.\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\.Fixε\>0\\varepsilon\>0such thatβε:=ραdir\+ε<1\\beta\_\{\\varepsilon\}:=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1, and letpεp\_\{\\varepsilon\}be the JSR Lyapunov norm in[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)\. The constantCεC\_\{\\varepsilon\}appearing below is defined in[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8)\. Assume additionally that

λε:=βε\+4​α​Cε​\(1\+γ\)​ϕmax2<1\.\\lambda\_\{\\varepsilon\}:=\\beta\_\{\\varepsilon\}\+4\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}<1\.Then the single\-trajectory Markovian linear Q\-learning recursion[Equation˜22](https://arxiv.org/html/2605.11021#S6.E22)satisfies, for allk≥0k\\geq 0,

𝔼​\[pε​\(xk\)\]≤\(λε\)k​pε​\(x0\)\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)1−λε​\(1−\(λε\)k\)\.\\mathbb\{E\}\[p\_\{\\varepsilon\}\(x\_\{k\}\)\]\\leq\(\\lambda\_\{\\varepsilon\}\)^\{k\}p\_\{\\varepsilon\}\(x\_\{0\}\)\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\\left\(1\-\(\\lambda\_\{\\varepsilon\}\)^\{k\}\\right\)\.\(28\)Consequently,

𝔼​\[‖θk−θ⋆‖2\]≤Cε​\(λε\)k​‖θ0−θ⋆‖2\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)1−λε,\\mathbb\{E\}\[\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\sqrt\{C\_\{\\varepsilon\}\}\(\\lambda\_\{\\varepsilon\}\)^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\},and

lim supk→∞𝔼​\[‖θk−θ⋆‖2\]≤2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)1−λε\.\\limsup\_\{k\\to\\infty\}\\mathbb\{E\}\[\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\.The corresponding LFA Q\-function error satisfies

𝔼\[∥Φθk−Φθ⋆∥2\]≤∥Φ∥2\(\\displaystyle\\mathbb\{E\}\[\\\|\\Phi\\theta\_\{k\}\-\\Phi\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\\|\\Phi\\\|\_\{2\}\\Bigg\(Cε​\(λε\)k​‖θ0−θ⋆‖2\\displaystyle\\sqrt\{C\_\{\\varepsilon\}\}\(\\lambda\_\{\\varepsilon\}\)^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)1−λε\)\.\\displaystyle\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\\Bigg\)\.

The Markovian bound above does not estimate how fast the behavior chain approaches stationarity\. Instead, it uses the stationary averaged direct mode𝐀μk\\mathbf\{A\}\_\{\\mu\_\{k\}\}and treats the difference between the realized coordinate update and the stationary averaged update as the errorbkb\_\{k\}\. The price is an enlarged linear\-growth coefficient and an enlarged residual constant\. Thus the result should be interpreted as a robust bounded\-error estimate rather than a mixing\-based finite\-time rate\.

## 7Regularized Linear Q\-Learning

This section adds theℓ2\\ell\_\{2\}\-regularized term used in regularized Q\-learning\[[21](https://arxiv.org/html/2605.11021#bib.bib49)\]\. In the notation of this paper, the sampled regularization term is−η​θk\-\\eta\\theta\_\{k\}, whereη≥0\\eta\\geq 0is the regularization weight\. The deterministic regularized LFA map is

𝐓α,η​\(θ\):=θ\+α​\[Φ⊤​D​\(R\+γ​P​Vθ−Φ​θ\)−η​θ\]=𝐓α​\(θ\)−α​η​θ\.\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\):=\\theta\+\\alpha\\left\[\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\-\\Phi\\theta\\right\)\-\\eta\\theta\\right\]=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\alpha\\eta\\theta\.\(29\)The corresponding regularized projected Bellman fixed point, if exists, is a parameterθη⋆\\theta\_\{\\eta\}^\{\\star\}satisfying

Φ⊤​D​\(R\+γ​P​Vθη⋆−Φ​θη⋆\)−η​θη⋆=0\.\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\_\{\\eta\}^\{\\star\}\}\-\\Phi\\theta\_\{\\eta\}^\{\\star\}\\right\)\-\\eta\\theta\_\{\\eta\}^\{\\star\}=0\.\(30\)Equivalently, with the definition of the regularized projection

𝚪η:=Φ​\(Φ⊤​D​Φ\+η​I\)−1​Φ⊤​D,\\boldsymbol\{\\Gamma\}\_\{\\eta\}:=\\Phi\(\\Phi^\{\\top\}D\\Phi\+\\eta I\)^\{\-1\}\\Phi^\{\\top\}D,[Equation˜30](https://arxiv.org/html/2605.11021#S7.E30)can be written as the regularized projected Bellman equation

Φ​θη⋆=𝚪η​\(R\+γ​P​Vθη⋆\)\.\\Phi\\theta\_\{\\eta\}^\{\\star\}=\\boldsymbol\{\\Gamma\}\_\{\\eta\}\\left\(R\+\\gamma PV\_\{\\theta\_\{\\eta\}^\{\\star\}\}\\right\)\.Equivalently, becauseα\>0\\alpha\>0, this fixed point satisfies the zero fixed\-point\-residual equation

𝐓α,η​\(θη⋆\)−θη⋆=0,\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\_\{\\eta\}^\{\\star\}\)\-\\theta\_\{\\eta\}^\{\\star\}=0,or, equivalently,𝐓α,η​\(θη⋆\)=θη⋆\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\_\{\\eta\}^\{\\star\}\)=\\theta\_\{\\eta\}^\{\\star\}\. Forη\>0\\eta\>0,𝚪η\\boldsymbol\{\\Gamma\}\_\{\\eta\}is generally not an idempotentDD\-orthogonal projection\. Thus the phrase regularized projected Bellman equation refers here to the regularized normal equation[Equation˜30](https://arxiv.org/html/2605.11021#S7.E30), rather than to an ordinary orthogonal projection\.

The corresponding regularized projected Q\-VI is

Φ​θk\+1RPVI=𝚪η​\(R\+γ​P​VθkRPVI\),k∈\{0,1,…\},\\Phi\\theta\_\{k\+1\}^\{\\mathrm\{RPVI\}\}=\\boldsymbol\{\\Gamma\}\_\{\\eta\}\\left\(R\+\\gamma PV\_\{\\theta\_\{k\}^\{\\mathrm\{RPVI\}\}\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\},or, equivalently, in parameter space,

θk\+1RPVI=\(Φ⊤​D​Φ\+η​I\)−1​Φ⊤​D​\(R\+γ​P​VθkRPVI\),k∈\{0,1,…\}\.\\theta\_\{k\+1\}^\{\\mathrm\{RPVI\}\}=\(\\Phi^\{\\top\}D\\Phi\+\\eta I\)^\{\-1\}\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\_\{k\}^\{\\mathrm\{RPVI\}\}\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.\(31\)Following the regularized Q\-learning analysis of\[[21](https://arxiv.org/html/2605.11021#bib.bib49)\], a sufficient condition for the regularized projected Bellman operator

Q↦𝚪η​\(R\+γ​P​VQ\)Q\\mapsto\\boldsymbol\{\\Gamma\}\_\{\\eta\}\\left\(R\+\\gamma PV\_\{Q\}\\right\)to be a contraction in the sup norm is

γ​‖𝚪η​P‖∞<1\.\\gamma\\\|\\boldsymbol\{\\Gamma\}\_\{\\eta\}P\\\|\_\{\\infty\}<1\.\(32\)Indeed, for any two representable Q\-functionsQ=Φ​θQ=\\Phi\\thetaandQ¯=Φ​θ¯\\bar\{Q\}=\\Phi\\bar\{\\theta\},

‖𝚪η​γ​P​\(VQ−VQ¯\)‖∞≤γ​‖𝚪η​P‖∞​‖Q−Q¯‖∞\.\\left\\\|\\boldsymbol\{\\Gamma\}\_\{\\eta\}\\gamma P\\left\(V\_\{Q\}\-V\_\{\\bar\{Q\}\}\\right\)\\right\\\|\_\{\\infty\}\\leq\\gamma\\\|\\boldsymbol\{\\Gamma\}\_\{\\eta\}P\\\|\_\{\\infty\}\\\|Q\-\\bar\{Q\}\\\|\_\{\\infty\}\.Because𝚪η→0\\boldsymbol\{\\Gamma\}\_\{\\eta\}\\to 0asη→∞\\eta\\to\\infty, condition[Equation˜32](https://arxiv.org/html/2605.11021#S7.E32)holds for all sufficiently largeη\\eta\. Hence, for sufficiently largeη\\eta, the regularized projected Bellman equation has a unique fixed point and the regularized projected Q\-VI converges to it\.

The corresponding regularized deterministic linear Q\-learning iteration is

θk\+1RegDLQ=θkRegDLQ\+α​\[Φ⊤​D​\(R\+γ​P​VθkRegDLQ−Φ​θkRegDLQ\)−η​θkRegDLQ\],k∈\{0,1,…\}\.\\theta\_\{k\+1\}^\{\\mathrm\{RegDLQ\}\}=\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}\+\\alpha\\left\[\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}\}\-\\Phi\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}\\right\)\-\\eta\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}\\right\],\\qquad k\\in\\\{0,1,\\ldots\\\}\.Equivalently,

θk\+1RegDLQ=𝐓α,η​\(θkRegDLQ\)\.\\theta\_\{k\+1\}^\{\\mathrm\{RegDLQ\}\}=\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}\)\.The regularized deterministic linear Q\-learning iteration can also be written as a residual step toward the regularized projected Q\-VI update:

θk\+1RegDLQ=θkRegDLQ\+α​\(Φ⊤​D​Φ\+η​I\)​\(θk\+1RPVI−θkRegDLQ\),\\theta\_\{k\+1\}^\{\\mathrm\{RegDLQ\}\}=\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}\+\\alpha\(\\Phi^\{\\top\}D\\Phi\+\\eta I\)\\left\(\\theta\_\{k\+1\}^\{\\mathrm\{RPVI\}\}\-\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}\\right\),whereθk\+1RPVI\\theta\_\{k\+1\}^\{\\mathrm\{RPVI\}\}is computed from[Equation˜31](https://arxiv.org/html/2605.11021#S7.E31)usingθkRPVI=θkRegDLQ\\theta\_\{k\}^\{\\mathrm\{RPVI\}\}=\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}\. Thus the two regularized iterations have the same fixed points when they converge, but their convergence behavior can be different because the deterministic linear Q\-learning step contains the additional preconditioning factorα​\(Φ⊤​D​Φ\+η​I\)\\alpha\(\\Phi^\{\\top\}D\\Phi\+\\eta I\)\. Whenη=0\\eta=0, the regularized map reduces to the unregularized linear Q\-learning map in[Equation˜3](https://arxiv.org/html/2605.11021#S3.E3)\. The regularized case therefore follows the same direct\-switching template, with each mode shifted by the regularization term\.

The next two examples show that the regularized projected Q\-VI and the regularized deterministic linear Q\-learning iteration can still have different convergence behavior\.

###### Example 5\(Regularized projected Q\-VI converges while regularized deterministic linear Q\-learning diverges\)\.

Consider a one\-state MDP with one action, zero reward, deterministic self\-transition,γ=0\.9\\gamma=0\.9,η=1\\eta=1,α=0\.5\\alpha=0\.5,d​\(1,1\)=1d\(1,1\)=1, and the one\-dimensional feature representationΦ=10\\Phi=10\. Since there is only one action, the maximization is trivial\. In this case

Φ⊤​D​Φ=100,Φ⊤​D​P​Φ=100\.\\Phi^\{\\top\}D\\Phi=100,\\qquad\\Phi^\{\\top\}DP\\Phi=100\.The regularized projected Q\-VI satisfies

θk\+1RPVI=γ​Φ⊤​D​P​ΦΦ⊤​D​Φ\+η​θkRPVI=90101​θkRPVI,k∈\{0,1,…\},\\theta\_\{k\+1\}^\{\\mathrm\{RPVI\}\}=\\gamma\\frac\{\\Phi^\{\\top\}DP\\Phi\}\{\\Phi^\{\\top\}D\\Phi\+\\eta\}\\theta\_\{k\}^\{\\mathrm\{RPVI\}\}=\\frac\{90\}\{101\}\\theta\_\{k\}^\{\\mathrm\{RPVI\}\},\\qquad k\\in\\\{0,1,\\ldots\\\},which converges to0\. However, the regularized deterministic linear Q\-learning iteration satisfies

θk\+1RegDLQ\\displaystyle\\theta\_\{k\+1\}^\{\\mathrm\{RegDLQ\}\}=\(1−α​\(Φ⊤​D​Φ\+η\)\+α​γ​Φ⊤​D​P​Φ\)​θkRegDLQ\\displaystyle=\\left\(1\-\\alpha\(\\Phi^\{\\top\}D\\Phi\+\\eta\)\+\\alpha\\gamma\\Phi^\{\\top\}DP\\Phi\\right\)\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}=\(1−0\.5⋅101\+0\.5⋅90\)​θkRegDLQ=−4\.5​θkRegDLQ,k∈\{0,1,…\}\.\\displaystyle=\\left\(1\-0\.5\\cdot 101\+0\.5\\cdot 90\\right\)\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}=\-5\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Thus regularized deterministic linear Q\-learning diverges for every nonzero initial condition, even though the regularized projected Q\-VI converges to the same fixed point\.

###### Example 6\(Regularized deterministic linear Q\-learning converges while regularized projected Q\-VI diverges\)\.

Consider a two\-state MDP with one action, zero reward, discount factorγ=0\.9\\gamma=0\.9,η=1\\eta=1,α=0\.1\\alpha=0\.1, and transition matrix

P=\[0101\]\.P=\\begin\{bmatrix\}0&1\\\\ 0&1\\end\{bmatrix\}\.Let the sampling distribution and feature matrix be

d​\(1,1\)=0\.99,d​\(2,1\)=0\.01,Φ=\[1−10\]\.d\(1,1\)=0\.99,\\qquad d\(2,1\)=0\.01,\\qquad\\Phi=\\begin\{bmatrix\}1\\\\ \-10\\end\{bmatrix\}\.Again, the maximization is trivial\. As in the corresponding unregularized example,

Φ⊤​D​Φ=1\.99,Φ⊤​D​P​Φ=−8\.9\.\\Phi^\{\\top\}D\\Phi=1\.99,\\qquad\\Phi^\{\\top\}DP\\Phi=\-8\.9\.The regularized projected Q\-VI is

θk\+1RPVI=γ​Φ⊤​D​P​ΦΦ⊤​D​Φ\+η​θkRPVI=−8\.012\.99​θkRPVI,k∈\{0,1,…\}\.\\theta\_\{k\+1\}^\{\\mathrm\{RPVI\}\}=\\gamma\\frac\{\\Phi^\{\\top\}DP\\Phi\}\{\\Phi^\{\\top\}D\\Phi\+\\eta\}\\theta\_\{k\}^\{\\mathrm\{RPVI\}\}=\-\\frac\{8\.01\}\{2\.99\}\\theta\_\{k\}^\{\\mathrm\{RPVI\}\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Since8\.01/2\.99\>18\.01/2\.99\>1, the regularized projected Q\-VI diverges for every nonzero initial condition\. On the other hand, the regularized deterministic linear Q\-learning iteration satisfies

θk\+1RegDLQ\\displaystyle\\theta\_\{k\+1\}^\{\\mathrm\{RegDLQ\}\}=\(1−α​\(Φ⊤​D​Φ\+η\)\+α​γ​Φ⊤​D​P​Φ\)​θkRegDLQ\\displaystyle=\\left\(1\-\\alpha\(\\Phi^\{\\top\}D\\Phi\+\\eta\)\+\\alpha\\gamma\\Phi^\{\\top\}DP\\Phi\\right\)\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}=\(1−0\.1⋅2\.99\+0\.1⋅0\.9⋅\(−8\.9\)\)​θkRegDLQ=−0\.1​θkRegDLQ,k∈\{0,1,…\}\.\\displaystyle=\\left\(1\-0\.1\\cdot 2\.99\+0\.1\\cdot 0\.9\\cdot\(\-8\.9\)\\right\)\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\}=\-1\\theta\_\{k\}^\{\\mathrm\{RegDLQ\}\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Therefore regularized deterministic linear Q\-learning converges to0, while the regularized projected Q\-VI diverges\.

### 7\.1Regularized Direct Modes and JSR

For a stochastic policyμ\\mu, define the regularized direct mode

𝐀μη:=I−α​\(Φ⊤​D​Φ\+η​I\)\+α​γ​Φ⊤​D​P​𝚷μ​Φ=𝐀μ−α​η​I\.\\mathbf\{A\}\_\{\\mu\}^\{\\eta\}:=I\-\\alpha\(\\Phi^\{\\top\}D\\Phi\+\\eta I\)\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\mu\}\\Phi=\\mathbf\{A\}\_\{\\mu\}\-\\alpha\\eta I\.For deterministic policies, define

𝒜α,η:=\{𝐀πη:=I−α​\(Φ⊤​D​Φ\+η​I\)\+α​γ​Φ⊤​D​P​𝚷π​Φ:π∈Θ\}\.\\mathcal\{A\}\_\{\\alpha,\\eta\}:=\\left\\\{\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}:=I\-\\alpha\(\\Phi^\{\\top\}D\\Phi\+\\eta I\)\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi:\\pi\\in\\Theta\\right\\\}\.The regularized direct JSR rate is

ρα,ηdir:=ρ​\(𝒜α,η\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}:=\\rho\(\\mathcal\{A\}\_\{\\alpha,\\eta\}\)\.
The next proposition is the regularized counterpart of the pairwise direct representation\.

###### Proposition 4\(Regularized pairwise direct representation\)\.

For everyθ,θ¯∈ℝm\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}, there exists a stochastic policyμθ,θ¯\\mu\_\{\\theta,\\bar\{\\theta\}\}such that

𝐓α,η​\(θ\)−𝐓α,η​\(θ¯\)=𝐀μθ,θ¯η​\(θ−θ¯\)\.\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\bar\{\\theta\}\)=\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}^\{\\eta\}\(\\theta\-\\bar\{\\theta\}\)\.In particular, ifθη⋆\\theta\_\{\\eta\}^\{\\star\}satisfies[Equation˜30](https://arxiv.org/html/2605.11021#S7.E30)andxk:=θk−θη⋆x\_\{k\}:=\\theta\_\{k\}\-\\theta\_\{\\eta\}^\{\\star\}, then the deterministic regularized recursionθk\+1=𝐓α,η​\(θk\)\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\_\{k\}\)satisfies

xk\+1=𝐀μkη​xk,k∈\{0,1,…\},x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}^\{\\eta\}x\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\},\(33\)whereμk\\mu\_\{k\}is a stochastic policy depending measurably onθk\\theta\_\{k\}andθη⋆\\theta\_\{\\eta\}^\{\\star\}\.

The regularized convergence analysis can be obtained by applying almost the same interpretation as in the preceding linear Q\-learning analysis to the shifted family𝒜α,η\\mathcal\{A\}\_\{\\alpha,\\eta\}\. In particular, whenρα,ηdir<1\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}<1, the JSR Lyapunov construction applied to the modes𝐀πη\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}gives a contraction of the deterministic regularized map around the regularized projected Bellman fixed pointθη⋆\\theta\_\{\\eta\}^\{\\star\}\. The sampled i\.i\.d\. regularized recursion is handled in the same way: the conditional mean drift uses the shifted regularized modes, while the sampling noise is the same martingale\-difference term as in the unregularized linear Q\-learning case\. Therefore, by replacing𝐀π\\mathbf\{A\}\_\{\\pi\}with𝐀πη\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}andθ⋆\\theta^\{\\star\}withθη⋆\\theta\_\{\\eta\}^\{\\star\}in the previous linear Q\-learning argument, the corresponding deterministic convergence and stochastic bounded\-error bounds follow\. Since these derivations overlap almost completely with the earlier linear Q\-learning analysis, we omit the details\.

The regularization replaces each drift mode𝐀π\\mathbf\{A\}\_\{\\pi\}by𝐀πη=𝐀π−α​η​I\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}=\\mathbf\{A\}\_\{\\pi\}\-\\alpha\\eta I\. Therefore the convergence certificate is obtained by computing or bounding the JSR of the shifted family𝒜α,η\\mathcal\{A\}\_\{\\alpha,\\eta\}\.

### 7\.2Regularization\-Dependent JSR Upper Bounds

This subsection presents three regularization\-dependent consequences of the shifted mode representation\. First, the regularized JSR can be written as a rescaled unregularized JSR\. Second, when0≤α​η≤10\\leq\\alpha\\eta\\leq 1, the same representation gives a Euclidean upper bound that displays the interaction betweenα\\alphaandη\\eta\. Third, a more conservative all\-η\\etabound follows by bounding the shifted drift norm directly\.

Let

cΦ\\displaystyle c\_\{\\Phi\}:=minπ∈Θ⁡λmin​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\+\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)⊤2\),\\displaystyle=\\min\_\{\\pi\\in\\Theta\}\\lambda\_\{\\min\}\\left\(\\frac\{\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\+\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)^\{\\top\}\}\{2\}\\right\),\(34\)LΦ\\displaystyle L\_\{\\Phi\}:=maxπ∈Θ⁡‖Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ‖2\.\\displaystyle=\\max\_\{\\pi\\in\\Theta\}\\left\\\|\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\\\|\_\{2\}\.For each deterministic policyπ\\pi, let us define

𝐀πη=I−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\+η​I\)\.\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}=I\-\\alpha\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\+\\eta I\\right\)\.Thus regularized switching system matrix is a scalar shift of each unregularized switching system matrix\. In the regularized Q\-learning analysis of\[[21](https://arxiv.org/html/2605.11021#bib.bib49)\], increasingη\\etastrengthens the regularized stability mechanism\. In the present fixed\-α\\alphaswitched\-system analysis, however, this monotone interpretation does not directly apply: increasingη\\etaalso changes the discrete\-time factor1−α​η1\-\\alpha\\etaand the effective step\-size scaling that appears in[Proposition˜5](https://arxiv.org/html/2605.11021#Thmproposition5)\.

###### Proposition 5\.

Forα¯∈ℝ\\bar\{\\alpha\}\\in\\mathbb\{R\}, define the formal switching family

ℬα¯:=\{I−α¯​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\):π∈Θ\}\.\\mathcal\{B\}\_\{\\bar\{\\alpha\}\}:=\\left\\\{I\-\\bar\{\\alpha\}\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\):\\pi\\in\\Theta\\right\\\}\.Ifα​η≠1\\alpha\\eta\\neq 1, then

ρα,ηdir=\|1−α​η\|​ρ​\(ℬα/\(1−α​η\)\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}=\|1\-\\alpha\\eta\|\\,\\rho\\left\(\\mathcal\{B\}\_\{\\alpha/\(1\-\\alpha\\eta\)\}\\right\)\.\(35\)In particular, if0≤α​η<10\\leq\\alpha\\eta<1, then

ρα,ηdir=\(1−α​η\)​ρ​\(ℬα/\(1−α​η\)\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}=\(1\-\\alpha\\eta\)\\,\\rho\\left\(\\mathcal\{B\}\_\{\\alpha/\(1\-\\alpha\\eta\)\}\\right\)\.Ifα​η=1\\alpha\\eta=1, then

ρα,ηdir=α​ρ​\(\{Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ:π∈Θ\}\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}=\\alpha\\,\\rho\\left\(\\left\\\{\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi:\\pi\\in\\Theta\\right\\\}\\right\)\.\(36\)

###### Proposition 6\(Regularization\-dependent Euclidean JSR upper bound\)\.

LetcΦc\_\{\\Phi\}andLΦL\_\{\\Phi\}be defined in[Equation˜34](https://arxiv.org/html/2605.11021#S7.E34)\. If0≤α​η≤10\\leq\\alpha\\eta\\leq 1, then

ρα,ηdir≤\(1−α​η\)2−2​α​\(1−α​η\)​cΦ\+α2​LΦ2\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{\(1\-\\alpha\\eta\)^\{2\}\-2\\alpha\(1\-\\alpha\\eta\)c\_\{\\Phi\}\+\\alpha^\{2\}L\_\{\\Phi\}^\{2\}\}\.\(37\)Equivalently,

ρα,ηdir≤1−2​α​\(cΦ\+η\)\+α2​\(LΦ2\+2​cΦ​η\+η2\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{1\-2\\alpha\(c\_\{\\Phi\}\+\\eta\)\+\\alpha^\{2\}\\left\(L\_\{\\Phi\}^\{2\}\+2c\_\{\\Phi\}\\eta\+\\eta^\{2\}\\right\)\}\.\(38\)Consequently, if

0≤α​η≤1,cΦ\+η\>0,0<α<2​\(cΦ\+η\)LΦ2\+2​cΦ​η\+η2,0\\leq\\alpha\\eta\\leq 1,\\qquad c\_\{\\Phi\}\+\\eta\>0,\\qquad 0<\\alpha<\\frac\{2\(c\_\{\\Phi\}\+\\eta\)\}\{L\_\{\\Phi\}^\{2\}\+2c\_\{\\Phi\}\\eta\+\\eta^\{2\}\},\(39\)thenρα,ηdir<1\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}<1\.

###### Corollary 1\(All\-η\\etaconservative Euclidean bound\)\.

For everyη≥0\\eta\\geq 0, define

LΦ,η:=maxπ∈Θ⁡‖Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\+η​I‖2\.L\_\{\\Phi,\\eta\}:=\\max\_\{\\pi\\in\\Theta\}\\left\\\|\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\+\\eta I\\right\\\|\_\{2\}\.Then

ρα,ηdir≤1−2​α​\(cΦ\+η\)\+α2​LΦ,η2\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{1\-2\\alpha\(c\_\{\\Phi\}\+\\eta\)\+\\alpha^\{2\}L\_\{\\Phi,\\eta\}^\{2\}\}\.\(40\)SinceLΦ,η≤LΦ\+ηL\_\{\\Phi,\\eta\}\\leq L\_\{\\Phi\}\+\\eta, the more conservative but directly computable bound

ρα,ηdir≤1−2​α​\(cΦ\+η\)\+α2​\(LΦ\+η\)2\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{1\-2\\alpha\(c\_\{\\Phi\}\+\\eta\)\+\\alpha^\{2\}\(L\_\{\\Phi\}\+\\eta\)^\{2\}\}\(41\)also holds\. Hence, if

cΦ\+η\>0,0<α<2​\(cΦ\+η\)LΦ,η2,c\_\{\\Phi\}\+\\eta\>0,\\qquad 0<\\alpha<\\frac\{2\(c\_\{\\Phi\}\+\\eta\)\}\{L\_\{\\Phi,\\eta\}^\{2\}\},\(42\)thenρα,ηdir<1\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}<1\. A sufficient condition using onlyLΦL\_\{\\Phi\}is obtained by replacingLΦ,η2L\_\{\\Phi,\\eta\}^\{2\}with\(LΦ\+η\)2\(L\_\{\\Phi\}\+\\eta\)^\{2\}in[Equation˜42](https://arxiv.org/html/2605.11021#S7.E42)\.

###### Example 7\(Applying the all\-η\\etabound to stabilize the direct JSR\)\.

Consider a two\-state MDP with one action, zero reward, discount factorγ=0\.9\\gamma=0\.9,α=0\.1\\alpha=0\.1, and transition matrix

P=\[0101\]\.P=\\begin\{bmatrix\}0&1\\\\ 0&1\\end\{bmatrix\}\.Let

d​\(1,1\)=0\.9,d​\(2,1\)=0\.1,Φ=\[110\]\.d\(1,1\)=0\.9,\\qquad d\(2,1\)=0\.1,\\qquad\\Phi=\\begin\{bmatrix\}1\\\\ 10\\end\{bmatrix\}\.Since there is only one action, the maximization is trivial and there is only one direct mode\. We have

Φ⊤​D​Φ=0\.9⋅12\+0\.1⋅102=10\.9,\\Phi^\{\\top\}D\\Phi=0\.9\\cdot 1^\{2\}\+0\.1\\cdot 10^\{2\}=10\.9,and, sinceP​Φ=\(10,10\)⊤P\\Phi=\(10,10\)^\{\\top\},

Φ⊤​D​P​Φ=0\.9⋅1⋅10\+0\.1⋅10⋅10=19\.\\Phi^\{\\top\}DP\\Phi=0\.9\\cdot 1\\cdot 10\+0\.1\\cdot 10\\cdot 10=19\.Hence

Φ⊤​D​Φ−γ​Φ⊤​D​P​Φ=10\.9−0\.9⋅19=−6\.2\.\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\Phi=10\.9\-0\.9\\cdot 19=\-6\.2\.The unregularized direct mode is

𝐀=I−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​Φ\)=1−0\.1​\(−6\.2\)=1\.62,\\mathbf\{A\}=I\-\\alpha\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\Phi\)=1\-0\.1\(\-6\.2\)=1\.62,and therefore

ραdir=1\.62\>1\.\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=1\.62\>1\.Now chooseη=20\\eta=20\. Thenα​η=2\\alpha\\eta=2, so the restriction0≤α​η≤10\\leq\\alpha\\eta\\leq 1in[Proposition˜6](https://arxiv.org/html/2605.11021#Thmproposition6)is not available\. However,[Corollary˜1](https://arxiv.org/html/2605.11021#Thmcorollary1)applies\. In this scalar example,

cΦ=−6\.2,LΦ=6\.2,LΦ,η=\|Φ⊤​D​Φ−γ​Φ⊤​D​P​Φ\+η\|=13\.8\.c\_\{\\Phi\}=\-6\.2,\\qquad L\_\{\\Phi\}=6\.2,\\qquad L\_\{\\Phi,\\eta\}=\|\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\Phi\+\\eta\|=13\.8\.The step\-size condition in[Corollary˜1](https://arxiv.org/html/2605.11021#Thmcorollary1)holds because

cΦ\+η=13\.8\>0,0<α=0\.1<2​\(cΦ\+η\)LΦ,η2=27\.613\.82=213\.8\.c\_\{\\Phi\}\+\\eta=13\.8\>0,\\qquad 0<\\alpha=0\.1<\\frac\{2\(c\_\{\\Phi\}\+\\eta\)\}\{L\_\{\\Phi,\\eta\}^\{2\}\}=\\frac\{27\.6\}\{13\.8^\{2\}\}=\\frac\{2\}\{13\.8\}\.Therefore, the sharp bound in[Equation˜40](https://arxiv.org/html/2605.11021#S7.E40)gives

ρα,ηdir≤1−2⋅0\.1⋅13\.8\+0\.12⋅13\.82=0\.38<1\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{1\-2\\cdot 0\.1\\cdot 13\.8\+0\.1^\{2\}\\cdot 13\.8^\{2\}\}=0\.38<1\.Directly, the regularized direct mode is

𝐀η=I−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​Φ\+η\)=1−0\.1​\(13\.8\)=−0\.38,\\mathbf\{A\}^\{\\eta\}=I\-\\alpha\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\Phi\+\\eta\)=1\-0\.1\(13\.8\)=\-0\.38,so

ρα,ηdir=0\.38<1\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}=0\.38<1\.Thus, although the unregularized direct JSR is larger than one,[Corollary˜1](https://arxiv.org/html/2605.11021#Thmcorollary1)certifies that this regularized direct JSR is strictly smaller than one\.

The bounds above should therefore not be read as saying thatρα,ηdir\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}is monotone decreasing inη\\eta\. The exact identity[Equation˜35](https://arxiv.org/html/2605.11021#S7.E35)shows that increasingη\\etasimultaneously introduces the scalar factor\|1−α​η\|\|1\-\\alpha\\eta\|and changes the effective step size toα/\(1−α​η\)\\alpha/\(1\-\\alpha\\eta\)whenα​η≠1\\alpha\\eta\\neq 1\. For this reason, regularization may improve a stability certificate by increasing the accretivity termcΦ\+ηc\_\{\\Phi\}\+\\eta, but with a fixed scalar step sizeα\\alpha, largerη\\etacan also make the discrete\-time step\-size restriction more severe\. This is the main distinction from analyses in which larger regularization directly strengthens stability after the algorithmic scaling is adjusted accordingly\.

## 8Conclusion

This paper introduced a switching system and JSR interpretation of linear Q\-learning\. Starting from an exact linear switching system model for the mean dynamics, convergence was interpreted through stability of the induced switched system and the condition that the direct JSR is less than one\. The same Lyapunov certificate was extended to stochastic linear Q\-learning with i\.i\.d\. observations and Markovian observations, and a parallel JSR\-based interpretation was given for regularized Q\-learning\. Although the JSR is difficult to compute exactly, it provides a less conservative sufficient condition than simple one\-step norm bounds and gives a new switching\-theoretic perspective on Q\-learning with LFA\.

## References

- \[1\]\(2012\)Error bounds for constant step\-size Q\-learning\.Systems & control letters61\(12\),pp\. 1203–1208\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[2\]D\. P\. Bertsekas\(2015\)Dynamic programming and optimal control 4th edition, volume ii\.Athena Scientific\.Cited by:[§1](https://arxiv.org/html/2605.11021#S1.p1.1)\.
- \[3\]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:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[4\]D\. Carvalho, F\. S\. Melo, and P\. Santos\(2020\)A new convergent variant of Q\-learning with linear function approximation\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 19412–19421\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p2.1)\.
- \[5\]F\. Che, C\. Xiao, J\. Mei, B\. Dai, R\. Gummadi, O\. A\. Ramirez, C\. K\. Harris, A\. R\. Mahmood, and D\. Schuurmans\(2024\)Target networks and over\-parameterization stabilize off\-policy bootstrapping with function approximation\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 6372–6396\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p2.1)\.
- \[6\]Z\. Chen, J\. Clarke, and S\. T\. Maguluri\(2023\)Target network and truncation overcome the deadly triad in Q\-learning\.SIAM Journal on Mathematics of Data Science5\(4\),pp\. 1078–1101\.External Links:[Document](https://dx.doi.org/10.1137/22M1499261)Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p2.1)\.
- \[7\]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:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[8\]Z\. Chen, S\. Zhang, T\. T\. Doan, J\. Clarke, and S\. T\. Maguluri\(2022\)Finite\-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning\.Automatica146,pp\. 110623\.External Links:[Document](https://dx.doi.org/10.1016/j.automatica.2022.110623)Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p2.1)\.
- \[9\]E\. Even\-Dar and Y\. Mansour\(2003\)Learning rates for Q\-learning\.Journal of machine learning Research5\(Dec\),pp\. 1–25\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[10\]V\. Goyal and J\. Grand\-Clement\(2023\)A first\-order approach to accelerated value iteration\.Operations research71\(2\),pp\. 517–535\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p3.1),[§4\.1](https://arxiv.org/html/2605.11021#S4.SS1.p1.1)\.
- \[11\]J\. Hu, J\. Shen, and W\. Zhang\(2010\)Generating functions of switched linear systems: analysis, computation, and stability applications\.IEEE transactions on automatic control56\(5\),pp\. 1059–1074\.Cited by:[§1](https://arxiv.org/html/2605.11021#S1.p3.1),[§3\.3](https://arxiv.org/html/2605.11021#S3.SS3.p2.1)\.
- \[12\]R\. Jungers\(2009\)The joint spectral radius: Theory and applications\.Vol\.385,Springer Science & Business Media\.Cited by:[§C\.3](https://arxiv.org/html/2605.11021#A3.SS3.3.p3.2),[§1](https://arxiv.org/html/2605.11021#S1.p2.1),[§2](https://arxiv.org/html/2605.11021#S2.p4.1),[§3\.2](https://arxiv.org/html/2605.11021#S3.SS2.p1.1),[§3\.3](https://arxiv.org/html/2605.11021#S3.SS3.p1.1)\.
- \[13\]M\. Kearns and S\. Singh\(1998\)Finite\-sample convergence rates for Q\-learning and indirect algorithms\.Advances in neural information processing systems11\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[14\]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:[§2](https://arxiv.org/html/2605.11021#S2.p4.1)\.
- \[15\]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:[§2](https://arxiv.org/html/2605.11021#S2.p4.1),[Lemma 4](https://arxiv.org/html/2605.11021#Thmlemma4)\.
- \[16\]D\. Lee\(2024\)Final iteration convergence bound of Q\-learning: Switching system approach\.IEEE Transactions on Automatic Control69\(7\),pp\. 4765–4772\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p4.1)\.
- \[17\]D\. Lee\(2026\)Lyapunov\-certified direct switching theory for q\-learning\.arXiv preprint arXiv:2604\.19569\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p4.1),[§3\.3](https://arxiv.org/html/2605.11021#S3.SS3.p2.1),[Lemma 1](https://arxiv.org/html/2605.11021#Thmlemma1),[Lemma 4](https://arxiv.org/html/2605.11021#Thmlemma4)\.
- \[18\]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:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[19\]D\. Liberzon\(2003\)Switching in systems and control\.Springer Science & Business Media\.Cited by:[§1](https://arxiv.org/html/2605.11021#S1.p2.1),[§2](https://arxiv.org/html/2605.11021#S2.p4.1),[§3\.2](https://arxiv.org/html/2605.11021#S3.SS2.p1.1)\.
- \[20\]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:[§2](https://arxiv.org/html/2605.11021#S2.p4.1)\.
- \[21\]H\. Lim and D\. Lee\(2024\)Regularized q\-learning\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 129855–129887\.Cited by:[§1](https://arxiv.org/html/2605.11021#S1.p5.1),[§2](https://arxiv.org/html/2605.11021#S2.p3.1),[§7\.2](https://arxiv.org/html/2605.11021#S7.SS2.p2.5),[§7](https://arxiv.org/html/2605.11021#S7.p1.3),[§7](https://arxiv.org/html/2605.11021#S7.p2.9)\.
- \[22\]H\. Lim and D\. Lee\(2025\)Understanding the theoretical properties of projected bellman equation, linear q\-learning, and approximate value iteration\.arXiv preprint arXiv:2504\.10865\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p3.1),[§3\.5](https://arxiv.org/html/2605.11021#S3.SS5.p1.6),[§3\.5](https://arxiv.org/html/2605.11021#S3.SS5.p1.7),[§3\.6](https://arxiv.org/html/2605.11021#S3.SS6.p5.3)\.
- \[23\]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.11021#S1.p2.1),[§2](https://arxiv.org/html/2605.11021#S2.p4.1),[§3\.2](https://arxiv.org/html/2605.11021#S3.SS2.p1.1)\.
- \[24\]X\. Liu, Z\. Xie, and S\. Zhang\(2025\)Linear Q\-learning does not diverge: convergence rates to a bounded set\.arXiv preprint arXiv:2501\.19254\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p2.1)\.
- \[25\]F\. S\. Melo and M\. I\. Ribeiro\(2007\)Convergence of Q\-learning with linear function approximation\.In2007 European Control Conference \(ECC\),pp\. 2671–2678\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p2.1)\.
- \[26\]S\. P\. Meyn\(2024\)The projected bellman equation in reinforcement learning\.IEEE Transactions on Automatic Control69\(12\),pp\. 8323–8337\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2024.3409647)Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p2.1)\.
- \[27\]M\. L\. Puterman\(2014\)Markov decision processes: Discrete stochastic dynamic programming\.John Wiley & Sons\.Cited by:[§1](https://arxiv.org/html/2605.11021#S1.p1.1),[§3\.4](https://arxiv.org/html/2605.11021#S3.SS4.p1.4)\.
- \[28\]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:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[29\]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.11021#S1.p2.1),[§2](https://arxiv.org/html/2605.11021#S2.p4.1),[§3\.3](https://arxiv.org/html/2605.11021#S3.SS3.p1.1)\.
- \[30\]R\. S\. Sutton and A\. G\. Barto\(1998\)Reinforcement learning: An introduction\.MIT Press\.Cited by:[§1](https://arxiv.org/html/2605.11021#S1.p1.1)\.
- \[31\]C\. Szepesvári\(1998\)The asymptotic convergence\-rate of Q\-learning\.InAdvances in Neural Information Processing Systems,pp\. 1064–1070\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[32\]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.11021#S1.p2.1),[§2](https://arxiv.org/html/2605.11021#S2.p4.1),[§3\.3](https://arxiv.org/html/2605.11021#S3.SS3.p1.1)\.
- \[33\]J\. N\. Tsitsiklis\(1994\)Asynchronous stochastic approximation and Q\-learning\.Machine learning16\(3\),pp\. 185–202\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p1.1)\.
- \[34\]C\. J\. Watkins and P\. Dayan\(1992\)Q\-learning\.Machine learning8\(3\),pp\. 279–292\.Cited by:[§1](https://arxiv.org/html/2605.11021#S1.p1.1)\.
- \[35\]S\. Zhang, H\. Yao, and S\. Whiteson\(2021\)Breaking the deadly triad with a target network\.InProceedings of the 38th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.139,pp\. 12621–12631\.Cited by:[§2](https://arxiv.org/html/2605.11021#S2.p2.1)\.

## Appendix AProof of the Equivalence Between the Projected Equation and the Normal Equation

The first appendix item states the algebraic equivalence between the projected Bellman equation and its normal\-equation form\. This result is used throughout the paper to identify projected Bellman fixed points with zeros of the projected Bellman residual\.

\{restatementbox\}

Restatement of[Lemma˜2](https://arxiv.org/html/2605.11021#Thmlemma2)\.Suppose thatΦ⊤​D​Φ\\Phi^\{\\top\}D\\Phiis nonsingular\. Then the solution set ofg​\(θ\)=0g\(\\theta\)=0is identical to the solution set of the projected Bellman equation[Equation˜1](https://arxiv.org/html/2605.11021#S3.E1)\.

###### Proof of[Lemma˜2](https://arxiv.org/html/2605.11021#Thmlemma2)\.

SinceΦ⊤​D​Φ\\Phi^\{\\top\}D\\Phiis nonsingular by assumption, the projected Bellman equation[Equation˜1](https://arxiv.org/html/2605.11021#S3.E1)can be written as

Φ​θ=Φ​\(Φ⊤​D​Φ\)−1​Φ⊤​D​\(R\+γ​P​Vθ\)\.\\displaystyle\\Phi\\theta=\\Phi\(\\Phi^\{\\top\}D\\Phi\)^\{\-1\}\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)\.\(43\)We prove the two implications separately\.

First, suppose thatθ\\thetasatisfies the projected Bellman equation\. Multiplying[Equation˜43](https://arxiv.org/html/2605.11021#A1.E43)from the left byΦ⊤​D\\Phi^\{\\top\}Dgives

Φ⊤​D​Φ​θ=Φ⊤​D​Φ​\(Φ⊤​D​Φ\)−1​Φ⊤​D​\(R\+γ​P​Vθ\)=Φ⊤​D​\(R\+γ​P​Vθ\)\.\\Phi^\{\\top\}D\\Phi\\theta=\\Phi^\{\\top\}D\\Phi\(\\Phi^\{\\top\}D\\Phi\)^\{\-1\}\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)=\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)\.Therefore

g​\(θ\)=Φ⊤​D​\(R\+γ​P​Vθ−Φ​θ\)=0\.g\(\\theta\)=\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\-\\Phi\\theta\\right\)=0\.Thus every solution of the projected Bellman equation is a zero of the normal\-equation residual\.

Conversely, suppose thatg​\(θ\)=0g\(\\theta\)=0\. Then

0=Φ⊤​D​\(R\+γ​P​Vθ−Φ​θ\)=Φ⊤​D​\(R\+γ​P​Vθ\)−Φ⊤​D​Φ​θ,0=\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\-\\Phi\\theta\\right\)=\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)\-\\Phi^\{\\top\}D\\Phi\\theta,and hence

Φ⊤​D​Φ​θ=Φ⊤​D​\(R\+γ​P​Vθ\)\.\\Phi^\{\\top\}D\\Phi\\theta=\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)\.SinceΦ⊤​D​Φ\\Phi^\{\\top\}D\\Phiis nonsingular,

θ=\(Φ⊤​D​Φ\)−1​Φ⊤​D​\(R\+γ​P​Vθ\)\.\\theta=\(\\Phi^\{\\top\}D\\Phi\)^\{\-1\}\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)\.Multiplying this identity byΦ\\Phiyields

Φ​θ=Φ​\(Φ⊤​D​Φ\)−1​Φ⊤​D​\(R\+γ​P​Vθ\)=𝚷D​\(R\+γ​P​Vθ\)\.\\Phi\\theta=\\Phi\(\\Phi^\{\\top\}D\\Phi\)^\{\-1\}\\Phi^\{\\top\}D\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)=\\boldsymbol\{\\Pi\}\_\{D\}\\left\(R\+\\gamma PV\_\{\\theta\}\\right\)\.This is exactly[Equation˜1](https://arxiv.org/html/2605.11021#S3.E1)\. Therefore, every zero ofggsolves the projected Bellman equation\. ∎

## Appendix BProofs for the Linear Switching System Representation

### B\.1Proof of[Lemma˜3](https://arxiv.org/html/2605.11021#Thmlemma3)

\{restatementbox\}

Restatement of[Lemma˜3](https://arxiv.org/html/2605.11021#Thmlemma3)\.For everyθ,θ¯∈ℝm\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}, there exists a stochastic policyμθ,θ¯:𝒮→Δ\|𝒜\|\\mu\_\{\\theta,\\bar\{\\theta\}\}:\\mathcal\{S\}\\to\\Delta\_\{\|\\mathcal\{A\}\|\}such that

Vθ−Vθ¯=𝚷μθ,θ¯​Φ​\(θ−θ¯\)\.V\_\{\\theta\}\-V\_\{\\bar\{\\theta\}\}=\\boldsymbol\{\\Pi\}^\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\\Phi\(\\theta\-\\bar\{\\theta\}\)\.Moreover,μθ,θ¯\\mu\_\{\\theta,\\bar\{\\theta\}\}can be chosen as a measurable function of\(θ,θ¯\)\(\\theta,\\bar\{\\theta\}\)\.

###### Proof\.

Fixθ,θ¯∈ℝm\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}and a states∈𝒮s\\in\\mathcal\{S\}\. Let

e​\(s,a\):=\(Φ​\(θ−θ¯\)\)​\(s,a\)\.e\(s,a\):=\(\\Phi\(\\theta\-\\bar\{\\theta\}\)\)\(s,a\)\.We show that

ys:=Vθ​\(s\)−Vθ¯​\(s\)y\_\{s\}:=V\_\{\\theta\}\(s\)\-V\_\{\\bar\{\\theta\}\}\(s\)lies in the interval betweenmina⁡e​\(s,a\)\\min\_\{a\}e\(s,a\)andmaxa⁡e​\(s,a\)\\max\_\{a\}e\(s,a\)\. Since

Vθ​\(s\)=maxa⁡\{\(Φ​θ¯\)​\(s,a\)\+e​\(s,a\)\},V\_\{\\theta\}\(s\)=\\max\_\{a\}\\\{\(\\Phi\\bar\{\\theta\}\)\(s,a\)\+e\(s,a\)\\\},we have

Vθ​\(s\)≤Vθ¯​\(s\)\+maxa⁡e​\(s,a\),V\_\{\\theta\}\(s\)\\leq V\_\{\\bar\{\\theta\}\}\(s\)\+\\max\_\{a\}e\(s,a\),and henceys≤maxa⁡e​\(s,a\)y\_\{s\}\\leq\\max\_\{a\}e\(s,a\)\. Ifa⋆∈arg​maxa⁡\(Φ​θ¯\)​\(s,a\)a\_\{\\star\}\\in\\operatorname\{arg\\,max\}\_\{a\}\(\\Phi\\bar\{\\theta\}\)\(s,a\), then

Vθ​\(s\)≥\(Φ​θ¯\)​\(s,a⋆\)\+e​\(s,a⋆\)≥Vθ¯​\(s\)\+mina⁡e​\(s,a\),V\_\{\\theta\}\(s\)\\geq\(\\Phi\\bar\{\\theta\}\)\(s,a\_\{\\star\}\)\+e\(s,a\_\{\\star\}\)\\geq V\_\{\\bar\{\\theta\}\}\(s\)\+\\min\_\{a\}e\(s,a\),soys≥mina⁡e​\(s,a\)y\_\{s\}\\geq\\min\_\{a\}e\(s,a\)\. Thusysy\_\{s\}belongs to the convex hull of the finite set\{e​\(s,a\):a∈𝒜\}\\\{e\(s,a\):a\\in\\mathcal\{A\}\\\}\.

Choose lexicographic minimizers and maximizers

amin​\(s\)∈arg​mina⁡e​\(s,a\),amax​\(s\)∈arg​maxa⁡e​\(s,a\)\.a\_\{\\min\}\(s\)\\in\\operatorname\{arg\\,min\}\_\{a\}e\(s,a\),\\qquad a\_\{\\max\}\(s\)\\in\\operatorname\{arg\\,max\}\_\{a\}e\(s,a\)\.If the minimum and maximum are equal, assign probability one toamin​\(s\)a\_\{\\min\}\(s\)\. Otherwise define

λs:=ys−e​\(s,amin​\(s\)\)e​\(s,amax​\(s\)\)−e​\(s,amin​\(s\)\)∈\[0,1\]\\lambda\_\{s\}:=\\frac\{y\_\{s\}\-e\(s,a\_\{\\min\}\(s\)\)\}\{e\(s,a\_\{\\max\}\(s\)\)\-e\(s,a\_\{\\min\}\(s\)\)\}\\in\[0,1\]and set

μθ,θ¯​\(amax​\(s\)∣s\)=λs,μθ,θ¯​\(amin​\(s\)∣s\)=1−λs,\\mu\_\{\\theta,\\bar\{\\theta\}\}\(a\_\{\\max\}\(s\)\\mid s\)=\\lambda\_\{s\},\\qquad\\mu\_\{\\theta,\\bar\{\\theta\}\}\(a\_\{\\min\}\(s\)\\mid s\)=1\-\\lambda\_\{s\},with all other action probabilities set to zero\. Then

ys=∑a∈𝒜μθ,θ¯​\(a∣s\)​e​\(s,a\)\.y\_\{s\}=\\sum\_\{a\\in\\mathcal\{A\}\}\\mu\_\{\\theta,\\bar\{\\theta\}\}\(a\\mid s\)e\(s,a\)\.Stacking these identities over all states gives

Vθ−Vθ¯=𝚷μθ,θ¯​Φ​\(θ−θ¯\)\.V\_\{\\theta\}\-V\_\{\\bar\{\\theta\}\}=\\boldsymbol\{\\Pi\}^\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\\Phi\(\\theta\-\\bar\{\\theta\}\)\.The lexicographic rule makes the construction single\-valued\. Because it uses finitely many comparisons of continuous functions and explicit continuous formulas away from equality regions, the selected policy is measurable\. ∎

### B\.2Proof of[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1)

\{restatementbox\}

Restatement of[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1)\.For everyθ,θ¯∈ℝm\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}, there exists a stochastic policyμθ,θ¯\\mu\_\{\\theta,\\bar\{\\theta\}\}such that

𝐓α​\(θ\)−𝐓α​\(θ¯\)=𝐀μθ,θ¯​\(θ−θ¯\)\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)=\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\(\\theta\-\\bar\{\\theta\}\)\.In particular, ifθ⋆\\theta^\{\\star\}is a projected Bellman fixed point andxk:=θk−θ⋆x\_\{k\}:=\\theta\_\{k\}\-\\theta^\{\\star\}, then the deterministic linear Q\-learning recursionθk\+1=𝐓α​\(θk\)\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)satisfies

xk\+1=𝐀μk​xk,k∈\{0,1,…\},x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\},whereμk\\mu\_\{k\}is a stochastic policy depending measurably onθk\\theta\_\{k\}andθ⋆\\theta^\{\\star\}\.

###### Proof\.

Using[Equation˜3](https://arxiv.org/html/2605.11021#S3.E3),

𝐓α​\(θ\)−𝐓α​\(θ¯\)\\displaystyle\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)=θ−θ¯\+α​Φ⊤​D​\(γ​P​\(Vθ−Vθ¯\)−Φ​\(θ−θ¯\)\)\.\\displaystyle=\\theta\-\\bar\{\\theta\}\+\\alpha\\Phi^\{\\top\}D\\left\(\\gamma P\(V\_\{\\theta\}\-V\_\{\\bar\{\\theta\}\}\)\-\\Phi\(\\theta\-\\bar\{\\theta\}\)\\right\)\.By[Lemma˜3](https://arxiv.org/html/2605.11021#Thmlemma3), there exists a stochastic policyμθ,θ¯\\mu\_\{\\theta,\\bar\{\\theta\}\}such that

Vθ−Vθ¯=𝚷μθ,θ¯​Φ​\(θ−θ¯\)\.V\_\{\\theta\}\-V\_\{\\bar\{\\theta\}\}=\\boldsymbol\{\\Pi\}^\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\\Phi\(\\theta\-\\bar\{\\theta\}\)\.Substitution gives

𝐓α​\(θ\)−𝐓α​\(θ¯\)\\displaystyle\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)=\(I−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​𝚷μθ,θ¯​Φ\)​\(θ−θ¯\)\\displaystyle=\\left\(I\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\\Phi\\right\)\(\\theta\-\\bar\{\\theta\}\)=𝐀μθ,θ¯​\(θ−θ¯\)\.\\displaystyle=\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\(\\theta\-\\bar\{\\theta\}\)\.Ifθ⋆\\theta^\{\\star\}is a fixed point andθ¯=θ⋆\\bar\{\\theta\}=\\theta^\{\\star\}, then𝐓α​\(θ⋆\)=θ⋆\\mathbf\{T\}\_\{\\alpha\}\(\\theta^\{\\star\}\)=\\theta^\{\\star\}, and[Equation˜6](https://arxiv.org/html/2605.11021#S4.E6)follows\. ∎

### B\.3Trajectory Example for the Linear Switching System Representation

###### Example 8\(Deterministic linear Q\-learning trajectory and its switching\-system trajectory\)\.

Consider the one\-state two\-action MDP,𝒮=\{1\},𝒜=\{1,2\}\\mathcal\{S\}=\\\{1\\\},\\mathcal\{A\}=\\\{1,2\\\}, with zero reward and deterministic self\-transition\. Letγ=12,α=0\.9,d​\(1,1\)=0\.9,d​\(1,2\)=0\.1\\gamma=\\frac\{1\}\{2\},\\alpha=0\.9,d\(1,1\)=0\.9,d\(1,2\)=0\.1, and use the one\-dimensional feature representation

ϕ​\(1,1\)=1,ϕ​\(1,2\)=−2,Φ=\[1−2\]\.\\phi\(1,1\)=1,\\qquad\\phi\(1,2\)=\-2,\\qquad\\Phi=\\begin\{bmatrix\}1\\\\ \-2\\end\{bmatrix\}\.For this example,

Φ⊤​D​Φ=0\.9⋅12\+0\.1⋅\(−2\)2=1\.3,Φ⊤​D​P=0\.9⋅1\+0\.1⋅\(−2\)=0\.7\.\\Phi^\{\\top\}D\\Phi=0\.9\\cdot 1^\{2\}\+0\.1\\cdot\(\-2\)^\{2\}=1\.3,\\qquad\\Phi^\{\\top\}DP=0\.9\\cdot 1\+0\.1\\cdot\(\-2\)=0\.7\.Since the reward is zero and the next state is always the single state,

Vθ=max⁡\{θ,−2​θ\},V\_\{\\theta\}=\\max\\\{\\theta,\-2\\theta\\\},and the deterministic linear Q\-learning map is

𝐓α​\(θ\)=θ\+Φ⊤​D​\(γ​P​Vθ−Φ​θ\)=−0\.17​θ\+0\.315​max⁡\{θ,−2​θ\}\.\\displaystyle\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)=\\theta\+\\Phi^\{\\top\}D\\left\(\\gamma PV\_\{\\theta\}\-\\Phi\\theta\\right\)=\-17\\theta\+315\\max\\\{\\theta,\-2\\theta\\\}\.Equivalently,

𝐓α​\(θ\)=\{0\.145​θ,θ≥0,−0\.8​θ,θ<0\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)=\\begin\{cases\}0\.145\\theta,&\\theta\\geq 0,\\\\ \-0\.8\\theta,&\\theta<0\.\\end\{cases\}Consequently,θ⋆=0\\theta^\{\\star\}=0is a projected Bellman fixed point\. The two deterministic\-policy direct modes are

𝐀1=1−0\.9⋅1\.3\+0\.9⋅12⋅0\.7⋅1=0\.145,𝐀2=1−0\.9⋅1\.3\+0\.9⋅12⋅0\.7⋅\(−2\)=−0\.8\.\\mathbf\{A\}\_\{1\}=1\-0\.9\\cdot 1\.3\+0\.9\\cdot\\frac\{1\}\{2\}\\cdot 0\.7\\cdot 1=0\.145,\\qquad\\mathbf\{A\}\_\{2\}=1\-0\.9\\cdot 1\.3\+0\.9\\cdot\\frac\{1\}\{2\}\\cdot 0\.7\\cdot\(\-2\)=\-0\.8\.Now choose the initial parameterθ0=−2\\theta\_\{0\}=\-2\. The deterministic Q\-learning trajectory is

θ1=𝐓α​\(−2\)=1\.6,θ2=𝐓α​\(1\.6\)=0\.232,θ3=𝐓α​\(0\.232\)=0\.03364,\\theta\_\{1\}=\\mathbf\{T\}\_\{\\alpha\}\(\-2\)=1\.6,\\qquad\\theta\_\{2\}=\\mathbf\{T\}\_\{\\alpha\}\(1\.6\)=0\.232,\\qquad\\theta\_\{3\}=\\mathbf\{T\}\_\{\\alpha\}\(0\.232\)=0\.03364,and, in closed form,

θk=1\.6​\(0\.145\)k−1,k≥1\.\\theta\_\{k\}=1\.6\(0\.145\)^\{k\-1\},\\qquad k\\geq 1\.The greedy action is action 2 atk=0k=0, because−2​θ0\>θ0\-2\\theta\_\{0\}\>\\theta\_\{0\}, and action 1 for everyk≥1k\\geq 1, becauseθk\>0\\theta\_\{k\}\>0\. Hence the corresponding switching mode sequence is

σ0=2,σk=1\(k≥1\)\.\\sigma\_\{0\}=2,\\qquad\\sigma\_\{k\}=1\\quad\(k\\geq 1\)\.For the switching system statexk:=θk−θ⋆=θkx\_\{k\}:=\\theta\_\{k\}\-\\theta^\{\\star\}=\\theta\_\{k\}, the switched linear trajectory satisfies

xk\+1=𝐀σk​xk,x0=−2\.x\_\{k\+1\}=\\mathbf\{A\}\_\{\\sigma\_\{k\}\}x\_\{k\},\\qquad x\_\{0\}=\-2\.Therefore

x1\\displaystyle x\_\{1\}=𝐀2​x0=\(−0\.8\)​\(−2\)=1\.6,x2=𝐀1​x1=0\.145⋅1\.6=0\.232,\\displaystyle=\\mathbf\{A\}\_\{2\}x\_\{0\}=\(\-8\)\(\-2\)=6,\\qquad x\_\{2\}=\\mathbf\{A\}\_\{1\}x\_\{1\}=145\\cdot 6=232,x3\\displaystyle x\_\{3\}=𝐀1​x2=0\.145⋅0\.232=0\.03364\.\\displaystyle=\\mathbf\{A\}\_\{1\}x\_\{2\}=145\\cdot 232=03364\.The deterministic Q\-learning error trajectory and the switching\-system state trajectory agree term by term:

kθkσk​used to compute​k\+1xk0−22−211\.611\.620\.23210\.23230\.0336410\.03364\\begin\{array\}\[\]\{c\|c\|c\|c\}k&\\theta\_\{k\}&\\sigma\_\{k\}\\text\{ used to compute \}k\+1&x\_\{k\}\\\\ \\hline\\cr 0&\-2&2&\-2\\\\ 1&1\.6&1&1\.6\\\\ 2&0\.232&1&0\.232\\\\ 3&0\.03364&1&0\.03364\\end\{array\}This calculation illustrates[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1): the nonlinear deterministic Q\-learning trajectory is reproduced exactly by the switched linear system once the mode sequence is chosen from the Bellman\-max regions encountered by the trajectory\.

### B\.4Convexification of Stochastic\-Policy Direct Modes

The pairwise representation above may produce a stochastic policy, whereas the JSR certificate is built from deterministic policies\. The next result closes this gap: every stochastic\-policy mode belongs to the convex hull of deterministic\-policy modes, and convexification does not change the JSR\.

###### Lemma 4\(Convex\-hull property\[[17](https://arxiv.org/html/2605.11021#bib.bib52),[15](https://arxiv.org/html/2605.11021#bib.bib38)\]\)\.

For every stochastic policyμ\\mu,

𝐀μ∈co⁡\(𝒜α\)\.\\mathbf\{A\}\_\{\\mu\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\)\.Moreover,

ρ​\(co⁡\(𝒜α\)\)=ρ​\(𝒜α\)=ραdir\.\\rho\(\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\)\)=\\rho\(\\mathcal\{A\}\_\{\\alpha\}\)=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\.

###### Proof\.

For a stochastic policyμ\\mu, define

cπ​\(μ\):=∏s∈𝒮μ​\(π​\(s\)∣s\),π∈Θ\.c\_\{\\pi\}\(\\mu\):=\\prod\_\{s\\in\\mathcal\{S\}\}\\mu\(\\pi\(s\)\\mid s\),\\qquad\\pi\\in\\Theta\.Thencπ​\(μ\)≥0c\_\{\\pi\}\(\\mu\)\\geq 0and∑π∈Θcπ​\(μ\)=1\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)=1\. Since deterministic stationary policies are the extreme points of the product of state\-wise probability simplices,

𝚷μ=∑π∈Θcπ​\(μ\)​𝚷π\.\\boldsymbol\{\\Pi\}^\{\\mu\}=\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)\\boldsymbol\{\\Pi\}^\{\\pi\}\.Using the affine dependence of𝐀μ\\mathbf\{A\}\_\{\\mu\}on𝚷μ\\boldsymbol\{\\Pi\}^\{\\mu\},

𝐀μ\\displaystyle\\mathbf\{A\}\_\{\\mu\}=I−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​𝚷μ​Φ\\displaystyle=I\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\mu\}\\Phi=∑π∈Θcπ​\(μ\)​\(I−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​𝚷π​Φ\)\\displaystyle=\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)\\left\(I\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)=∑π∈Θcπ​\(μ\)​𝐀π\.\\displaystyle=\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)\\mathbf\{A\}\_\{\\pi\}\.Therefore𝐀μ∈co⁡\(𝒜α\)\\mathbf\{A\}\_\{\\mu\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\)\. The equality of the JSR before and after convexification is the standard convex\-hull invariance of the JSR for finite matrix families\. ∎

## Appendix CProofs for the JSR Lyapunov Construction

This section collects the deterministic Lyapunov certificate and the corresponding arbitrary\-switching inclusion result\. The general product\-based Lyapunov construction is stated later in[Lemma˜9](https://arxiv.org/html/2605.11021#Thmlemma9); the deterministic proof below uses it as the common norm certificate for the direct matrix family\.

###### Lemma 9\(Piecewise quadratic JSR Lyapunov construction\)\.

Letℋ=\{𝐀1,…,𝐀M\}⊂ℝm×m\\mathcal\{H\}=\\\{\\mathbf\{A\}\_\{1\},\\ldots,\\mathbf\{A\}\_\{M\}\\\}\\subset\\mathbb\{R\}^\{m\\times m\}be finite, letρ:=ρ​\(ℋ\)\\rho:=\\rho\(\\mathcal\{H\}\), and fixε\>0\\varepsilon\>0such thatβ:=ρ\+ε<1\\beta:=\\rho\+\\varepsilon<1\. Fort≥0t\\geq 0, define

Vεt​\(x\):=∑ℓ=0tβ−2​ℓ​maxσ∈\{1,…,M\}ℓ⁡‖𝐀σℓ​⋯​𝐀σ1​x‖22,V\_\{\\varepsilon\}^\{t\}\(x\):=\\sum\_\{\\ell=0\}^\{t\}\\beta^\{\-2\\ell\}\\max\_\{\\sigma\\in\\\{1,\\ldots,M\\\}^\{\\ell\}\}\\\|\\mathbf\{A\}\_\{\\sigma\_\{\\ell\}\}\\cdots\\mathbf\{A\}\_\{\\sigma\_\{1\}\}x\\\|\_\{2\}^\{2\},with the empty product equal toII\. ThenVε∞​\(x\):=limt→∞Vεt​\(x\)V\_\{\\varepsilon\}^\{\\infty\}\(x\):=\\lim\_\{t\\to\\infty\}V\_\{\\varepsilon\}^\{t\}\(x\)exists, there isCε≥1C\_\{\\varepsilon\}\\geq 1such that

‖x‖22≤Vε∞​\(x\)≤Cε​‖x‖22,\\\|x\\\|\_\{2\}^\{2\}\\leq V\_\{\\varepsilon\}^\{\\infty\}\(x\)\\leq C\_\{\\varepsilon\}\\\|x\\\|\_\{2\}^\{2\},pε​\(x\):=Vε∞​\(x\)p\_\{\\varepsilon\}\(x\):=\\sqrt\{V\_\{\\varepsilon\}^\{\\infty\}\(x\)\}is a norm, and

Vε∞​\(𝐀i​x\)≤β2​\(Vε∞​\(x\)−‖x‖22\)≤β2​Vε∞​\(x\)V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{A\}\_\{i\}x\)\\leq\\beta^\{2\}\\left\(V\_\{\\varepsilon\}^\{\\infty\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\\leq\\beta^\{2\}V\_\{\\varepsilon\}^\{\\infty\}\(x\)for everyi∈\{1,…,M\}i\\in\\\{1,\\ldots,M\\\}\.

###### Proof\.

Fort≥0t\\geq 0, the definition gives

Vεt\+1​\(x\)≥‖x‖22\+β−2​maxi⁡Vεt​\(𝐀i​x\)\.V\_\{\\varepsilon\}^\{t\+1\}\(x\)\\geq\\\|x\\\|\_\{2\}^\{2\}\+\\beta^\{\-2\}\\max\_\{i\}V\_\{\\varepsilon\}^\{t\}\(\\mathbf\{A\}\_\{i\}x\)\.Indeed, split every product of lengthℓ\+1\\ell\+1into its first applied matrix𝐀i\\mathbf\{A\}\_\{i\}and the remaining product of lengthℓ\\ell\. Hence

Vεt​\(𝐀i​x\)≤β2​\(Vεt\+1​\(x\)−‖x‖22\)\.V\_\{\\varepsilon\}^\{t\}\(\\mathbf\{A\}\_\{i\}x\)\\leq\\beta^\{2\}\\left\(V\_\{\\varepsilon\}^\{t\+1\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\.
Sinceβ\>ρ\\beta\>\\rho, chooseη\\etawithρ<η<β\\rho<\\eta<\\beta\. By the definition of the JSR, there existsC0≥1C\_\{0\}\\geq 1such that every length\-ℓ\\ellproduct𝐀σ\\mathbf\{A\}\_\{\\sigma\}satisfies

‖𝐀σ‖2≤C0​ηℓ\.\\\|\\mathbf\{A\}\_\{\\sigma\}\\\|\_\{2\}\\leq C\_\{0\}\\eta^\{\\ell\}\.Thus

Vεt​\(x\)≤C02​∑ℓ=0t\(η/β\)2​ℓ​‖x‖22≤C021−\(η/β\)2​‖x‖22\.V\_\{\\varepsilon\}^\{t\}\(x\)\\leq C\_\{0\}^\{2\}\\sum\_\{\\ell=0\}^\{t\}\(\\eta/\\beta\)^\{2\\ell\}\\\|x\\\|\_\{2\}^\{2\}\\leq\\frac\{C\_\{0\}^\{2\}\}\{1\-\(\\eta/\\beta\)^\{2\}\}\\\|x\\\|\_\{2\}^\{2\}\.The lower bound follows from theℓ=0\\ell=0term\. Also,Vεt​\(x\)V\_\{\\varepsilon\}^\{t\}\(x\)is nondecreasing intt, so the pointwise limit exists and satisfies the same norm\-equivalence bounds\.

To prove thatpεp\_\{\\varepsilon\}is a norm, define seminorms

νℓ​\(x\):=β−ℓ​maxσ∈\{1,…,M\}ℓ⁡‖𝐀σℓ​⋯​𝐀σ1​x‖2,ν0​\(x\):=‖x‖2\.\\nu\_\{\\ell\}\(x\):=\\beta^\{\-\\ell\}\\max\_\{\\sigma\\in\\\{1,\\ldots,M\\\}^\{\\ell\}\}\\\|\\mathbf\{A\}\_\{\\sigma\_\{\\ell\}\}\\cdots\\mathbf\{A\}\_\{\\sigma\_\{1\}\}x\\\|\_\{2\},\\qquad\\nu\_\{0\}\(x\):=\\\|x\\\|\_\{2\}\.For finitett,pεt​\(x\):=\(∑ℓ=0tνℓ​\(x\)2\)1/2p\_\{\\varepsilon\}^\{t\}\(x\):=\(\\sum\_\{\\ell=0\}^\{t\}\\nu\_\{\\ell\}\(x\)^\{2\}\)^\{1/2\}is a norm by Minkowski’s inequality\. Sincepε​\(x\)=limt→∞pεt​\(x\)p\_\{\\varepsilon\}\(x\)=\\lim\_\{t\\to\\infty\}p\_\{\\varepsilon\}^\{t\}\(x\), the triangle inequality, homogeneity, and positive definiteness pass to the limit\.

Finally, lett→∞t\\to\\inftyin

Vεt​\(𝐀i​x\)≤β2​\(Vεt\+1​\(x\)−‖x‖22\)\.V\_\{\\varepsilon\}^\{t\}\(\\mathbf\{A\}\_\{i\}x\)\\leq\\beta^\{2\}\\left\(V\_\{\\varepsilon\}^\{t\+1\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\.This proves the Lyapunov inequality\. ∎

### C\.1Proof of[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)

\{restatementbox\}

Restatement of[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)\.Suppose thatραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. Fixε\>0\\varepsilon\>0such thatβε:=ραdir\+ε<1\\beta\_\{\\varepsilon\}:=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1\. ThenVε∞V\_\{\\varepsilon\}^\{\\infty\}in[Equation˜7](https://arxiv.org/html/2605.11021#S4.E7)is well\-defined, and there existsCε≥1C\_\{\\varepsilon\}\\geq 1such that

‖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\}\.Moreover,pε​\(x\):=Vε∞​\(x\)p\_\{\\varepsilon\}\(x\):=\\sqrt\{V\_\{\\varepsilon\}^\{\\infty\}\(x\)\}is a norm, and for every stochastic policyμ\\mu,

Vε∞​\(𝐀μ​x\)≤βε2​\(Vε∞​\(x\)−‖x‖22\)≤βε2​Vε∞​\(x\)\.V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{A\}\_\{\\mu\}x\)\\leq\\beta\_\{\\varepsilon\}^\{2\}\\left\(V\_\{\\varepsilon\}^\{\\infty\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\\leq\\beta\_\{\\varepsilon\}^\{2\}V\_\{\\varepsilon\}^\{\\infty\}\(x\)\.Consequently,

pε​\(𝐀μ​x\)≤βε​pε​\(x\),∀x∈ℝm\.p\_\{\\varepsilon\}\(\\mathbf\{A\}\_\{\\mu\}x\)\\leq\\beta\_\{\\varepsilon\}p\_\{\\varepsilon\}\(x\),\\qquad\\forall x\\in\\mathbb\{R\}^\{m\}\.The deterministic map𝐓α\\mathbf\{T\}\_\{\\alpha\}is a global contraction inpεp\_\{\\varepsilon\}:

pε​\(𝐓α​\(θ\)−𝐓α​\(θ¯\)\)≤βε​pε​\(θ−θ¯\),∀θ,θ¯∈ℝm\.p\_\{\\varepsilon\}\(\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)\)\\leq\\beta\_\{\\varepsilon\}p\_\{\\varepsilon\}\(\\theta\-\\bar\{\\theta\}\),\\qquad\\forall\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}\.Hence there exists a unique projected Bellman fixed pointθ⋆\\theta^\{\\star\}satisfying[Equation˜5](https://arxiv.org/html/2605.11021#S3.E5)\. For the deterministic recursion[Equation˜2](https://arxiv.org/html/2605.11021#S3.E2),

Vε∞​\(θk−θ⋆\)≤βε2​k​Vε∞​\(θ0−θ⋆\),V\_\{\\varepsilon\}^\{\\infty\}\(\\theta\_\{k\}\-\\theta^\{\\star\}\)\\leq\\beta\_\{\\varepsilon\}^\{2k\}V\_\{\\varepsilon\}^\{\\infty\}\(\\theta\_\{0\}\-\\theta^\{\\star\}\),and therefore

‖θk−θ⋆‖2≤Cε​βεk​‖θ0−θ⋆‖2\.\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\\leq\\sqrt\{C\_\{\\varepsilon\}\}\\,\\beta\_\{\\varepsilon\}^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\.In Q\-function norm,

‖Φ​θk−Φ​θ⋆‖2≤‖Φ‖2​Cε​βεk​‖θ0−θ⋆‖2\.\\\|\\Phi\\theta\_\{k\}\-\\Phi\\theta^\{\\star\}\\\|\_\{2\}\\leq\\\|\\Phi\\\|\_\{2\}\\sqrt\{C\_\{\\varepsilon\}\}\\,\\beta\_\{\\varepsilon\}^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\.
###### Proof\.

Apply[Lemma˜9](https://arxiv.org/html/2605.11021#Thmlemma9)to the finite family𝒜α\\mathcal\{A\}\_\{\\alpha\}\. This proves the existence ofVε∞V\_\{\\varepsilon\}^\{\\infty\}, the norm equivalence[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8), and the deterministic\-policy inequality\.

For a stochastic policyμ\\mu,[Lemma˜4](https://arxiv.org/html/2605.11021#Thmlemma4)gives

𝐀μ=∑π∈Θcπ​\(μ\)​𝐀π\\mathbf\{A\}\_\{\\mu\}=\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)\\mathbf\{A\}\_\{\\pi\}with convex weights\. The functionVε∞V\_\{\\varepsilon\}^\{\\infty\}is convex because it is a pointwise limit of nondecreasing convex functionsVεtV\_\{\\varepsilon\}^\{t\}\. Hence Jensen’s inequality gives

Vε∞​\(𝐀μ​x\)≤∑π∈Θcπ​\(μ\)​Vε∞​\(𝐀π​x\)≤βε2​\(Vε∞​\(x\)−‖x‖22\)\.\\displaystyle V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{A\}\_\{\\mu\}x\)\\leq\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{A\}\_\{\\pi\}x\)\\leq\\beta\_\{\\varepsilon\}^\{2\}\\left\(V\_\{\\varepsilon\}^\{\\infty\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\.Taking square roots gives[Equation˜10](https://arxiv.org/html/2605.11021#S4.E10)\.

For arbitraryθ,θ¯\\theta,\\bar\{\\theta\},[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1)gives

𝐓α​\(θ\)−𝐓α​\(θ¯\)=𝐀μθ,θ¯​\(θ−θ¯\)\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)=\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\(\\theta\-\\bar\{\\theta\}\)\.Using[Equation˜10](https://arxiv.org/html/2605.11021#S4.E10)gives the contraction inequality[Equation˜11](https://arxiv.org/html/2605.11021#S4.E11)\. Since\(ℝm,pε\)\(\\mathbb\{R\}^\{m\},p\_\{\\varepsilon\}\)is complete, Banach’s fixed\-point theorem implies that𝐓α\\mathbf\{T\}\_\{\\alpha\}has a unique fixed pointθ⋆\\theta^\{\\star\}\. By the definition of𝐓α\\mathbf\{T\}\_\{\\alpha\}, this fixed point satisfies[Equation˜5](https://arxiv.org/html/2605.11021#S3.E5)\.

Applying[Equation˜9](https://arxiv.org/html/2605.11021#S4.E9)toxk=θk−θ⋆x\_\{k\}=\\theta\_\{k\}\-\\theta^\{\\star\}gives

Vε∞​\(xk\+1\)≤βε2​Vε∞​\(xk\)\.V\_\{\\varepsilon\}^\{\\infty\}\(x\_\{k\+1\}\)\\leq\\beta\_\{\\varepsilon\}^\{2\}V\_\{\\varepsilon\}^\{\\infty\}\(x\_\{k\}\)\.Iteration proves[Equation˜12](https://arxiv.org/html/2605.11021#S4.E12)\. The Euclidean and Q\-function bounds follow from[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8)and‖Φ​x‖2≤‖Φ‖2​‖x‖2\\\|\\Phi x\\\|\_\{2\}\\leq\\\|\\Phi\\\|\_\{2\}\\\|x\\\|\_\{2\}\. ∎

### C\.2Direct\-Inclusion JSR Certificate

###### Theorem 2\(Direct\-inclusion JSR certificate\)\.

Consider the direct switched linear inclusion

xk\+1=𝐀k​xk,𝐀k∈co⁡\(𝒜α\),k∈\{0,1,…\}\.x\_\{k\+1\}=\\mathbf\{A\}\_\{k\}x\_\{k\},\\qquad\\mathbf\{A\}\_\{k\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.\(44\)If

ραdir<1,\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1,then[Equation˜44](https://arxiv.org/html/2605.11021#A3.E44)is uniformly exponentially stable under arbitrary switching\. More specifically, for everyε\>0\\varepsilon\>0withραdir\+ε<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1, the normpεp\_\{\\varepsilon\}defined by[Equation˜7](https://arxiv.org/html/2605.11021#S4.E7)satisfies

pε​\(A​x\)≤\(ραdir\+ε\)​pε​\(x\),∀𝐀∈co⁡\(𝒜α\),∀x∈ℝm\.p\_\{\\varepsilon\}\(Ax\)\\leq\(\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon\)p\_\{\\varepsilon\}\(x\),\\qquad\\forall\\mathbf\{A\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\),\\quad\\forall x\\in\\mathbb\{R\}^\{m\}\.Consequently, there existC≥1C\\geq 1andη∈\(0,1\)\\eta\\in\(0,1\)such that

‖𝐀k−1​⋯​𝐀0​x‖2≤C​ηk​‖x‖2\\\|\\mathbf\{A\}\_\{k\-1\}\\cdots\\mathbf\{A\}\_\{0\}x\\\|\_\{2\}\\leq C\\eta^\{k\}\\\|x\\\|\_\{2\}for everyk≥0k\\geq 0, everyx∈ℝmx\\in\\mathbb\{R\}^\{m\}, and every switching sequence𝐀j∈co⁡\(𝒜α\)\\mathbf\{A\}\_\{j\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\)\. If insteadραdir\>1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\>1, then the arbitrary\-switching inclusion admits a periodically switched trajectory whose state does not converge to zero\.

### C\.3Proof of[Theorem˜2](https://arxiv.org/html/2605.11021#Thmtheorem2)

###### Proof\.

Because of[Lemma˜4](https://arxiv.org/html/2605.11021#Thmlemma4), the JSR ofco⁡\(𝒜α\)\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\)equalsραdir\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\.

Assume first thatραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. Fix anyε\>0\\varepsilon\>0withβε:=ραdir\+ε<1\\beta\_\{\\varepsilon\}:=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1\. The Lyapunov construction in[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)gives

Vε∞​\(𝐀π​x\)≤βε2​\(Vε∞​\(x\)−‖x‖22\)V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{A\}\_\{\\pi\}x\)\\leq\\beta\_\{\\varepsilon\}^\{2\}\\left\(V\_\{\\varepsilon\}^\{\\infty\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)for every deterministic policyπ∈Θ\\pi\\in\\Theta\. Now take an arbitrary𝐀∈co⁡\(𝒜α\)\\mathbf\{A\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\)and write

𝐀=∑π∈Θcπ​𝐀π,cπ≥0,∑π∈Θcπ=1\.\\mathbf\{A\}=\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\\mathbf\{A\}\_\{\\pi\},\\qquad c\_\{\\pi\}\\geq 0,\\qquad\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}=1\.SinceVε∞V\_\{\\varepsilon\}^\{\\infty\}is convex, Jensen’s inequality gives

Vε∞​\(𝐀​x\)\\displaystyle V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{A\}x\)=Vε∞​\(∑π∈Θcπ​𝐀π​x\)\\displaystyle=V\_\{\\varepsilon\}^\{\\infty\}\\left\(\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\\mathbf\{A\}\_\{\\pi\}x\\right\)≤∑π∈Θcπ​Vε∞​\(𝐀π​x\)\\displaystyle\\leq\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}V\_\{\\varepsilon\}^\{\\infty\}\(\\mathbf\{A\}\_\{\\pi\}x\)≤βε2​\(Vε∞​\(x\)−‖x‖22\)≤βε2​Vε∞​\(x\)\.\\displaystyle\\leq\\beta\_\{\\varepsilon\}^\{2\}\\left\(V\_\{\\varepsilon\}^\{\\infty\}\(x\)\-\\\|x\\\|\_\{2\}^\{2\}\\right\)\\leq\\beta\_\{\\varepsilon\}^\{2\}V\_\{\\varepsilon\}^\{\\infty\}\(x\)\.Taking square roots yields

pε​\(𝐀​x\)≤βε​pε​\(x\)=\(ραdir\+ε\)​pε​\(x\)p\_\{\\varepsilon\}\(\\mathbf\{A\}x\)\\leq\\beta\_\{\\varepsilon\}p\_\{\\varepsilon\}\(x\)=\(\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon\)p\_\{\\varepsilon\}\(x\)for every𝐀∈co⁡\(𝒜α\)\\mathbf\{A\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\)\. Iterating this inequality gives exponential decay in thepεp\_\{\\varepsilon\}\-norm\. Since all norms onℝm\\mathbb\{R\}^\{m\}are equivalent, the same decay holds in Euclidean norm with adjusted constants, proving uniform exponential stability of[Equation˜44](https://arxiv.org/html/2605.11021#A3.E44)\.

Assume next thatραdir\>1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\>1\. By the Berger–Wang formula for finite bounded matrix families\[[12](https://arxiv.org/html/2605.11021#bib.bib16)\], there exist matrices𝐀1,…,𝐀ℓ∈co⁡\(𝒜α\)\\mathbf\{A\}\_\{1\},\\ldots,\\mathbf\{A\}\_\{\\ell\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha\}\)such that the product

𝐏σ:=𝐀ℓ​⋯​𝐀1\\mathbf\{P\}\_\{\\sigma\}:=\\mathbf\{A\}\_\{\\ell\}\\cdots\\mathbf\{A\}\_\{1\}satisfiesρ​\(𝐏σ\)\>1\\rho\(\\mathbf\{P\}\_\{\\sigma\}\)\>1\. Choose an initial vectorx0x\_\{0\}in an invariant real subspace associated with an eigenvalue of modulus larger than one\. Repeating the wordσ=\(𝐀1,…,𝐀ℓ\)\\sigma=\(\\mathbf\{A\}\_\{1\},\\ldots,\\mathbf\{A\}\_\{\\ell\}\)periodically gives

xn​ℓ=𝐏σn​x0,x\_\{n\\ell\}=\\mathbf\{P\}\_\{\\sigma\}^\{n\}x\_\{0\},which does not converge to zero\. Hence the arbitrary\-switching inclusion admits a periodically switched nonconvergent trajectory\. ∎

## Appendix DBaird’s Seven\-Star Q\-Learning Example

This section gives a direct numerical lower bound on the direct JSR for Baird’s seven\-star Q\-learning example\. The goal is not to compute the exact JSR, but to show that the direct\-JSR certificate

ραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1fails on this example\.

We use the direct mode family

𝒜α=\{Aπ=I−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​𝚷π​Φ:π∈Θ\},ραdir=ρ​\(𝒜α\)\.\\mathcal\{A\}\_\{\\alpha\}=\\left\\\{A\_\{\\pi\}=I\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi:\\pi\\in\\Theta\\right\\\},\\qquad\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=\\rho\(\\mathcal\{A\}\_\{\\alpha\}\)\.For any deterministic policyπ\\pi,

ραdir=ρ​\(𝒜α\)≥ρ​\(Aπ\),\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}=\\rho\(\\mathcal\{A\}\_\{\\alpha\}\)\\geq\\rho\(A\_\{\\pi\}\),whereρ​\(Aπ\)\\rho\(A\_\{\\pi\}\)is the ordinary spectral radius of the single matrixAπA\_\{\\pi\}\. Hence one policy mode with spectral radius larger than one is sufficient to prove thatραdir\>1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\>1\.

We consider the seven\-state, two\-action Baird example with

𝒮=\{1,…,7\},𝒜=\{1,2\}\.\\mathcal\{S\}=\\\{1,\\ldots,7\\\},\\qquad\\mathcal\{A\}=\\\{1,2\\\}\.Actiona=1a=1denotes the solid action, and actiona=2a=2denotes the dash action\. The feature dimension ism=15m=15\. State\-action rows are ordered as

\(1,1\),\(2,1\),…,\(7,1\),\(1,2\),\(2,2\),…,\(7,2\)\.\(1,1\),\(2,1\),\\ldots,\(7,1\),\(1,2\),\(2,2\),\\ldots,\(7,2\)\.The normalized feature matrix is

Φ=15​\[200000010000000020000010000000002000010000000000200010000000000020010000000000002010000000000000120000000000000001000000000000000100000000000000010000000000000001000000000000000100000000000000010000000000000001\]∈ℝ14×15\.\\Phi=\\frac\{1\}\{\\sqrt\{5\}\}\\left\[\\begin\{array\}\[\]\{rrrrrrrrrrrrrrr\}2&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\\\ 0&2&0&0&0&0&0&1&0&0&0&0&0&0&0\\\\ 0&0&2&0&0&0&0&1&0&0&0&0&0&0&0\\\\ 0&0&0&2&0&0&0&1&0&0&0&0&0&0&0\\\\ 0&0&0&0&2&0&0&1&0&0&0&0&0&0&0\\\\ 0&0&0&0&0&2&0&1&0&0&0&0&0&0&0\\\\ 0&0&0&0&0&0&1&2&0&0&0&0&0&0&0\\\\ 0&0&0&0&0&0&0&0&1&0&0&0&0&0&0\\\\ 0&0&0&0&0&0&0&0&0&1&0&0&0&0&0\\\\ 0&0&0&0&0&0&0&0&0&0&1&0&0&0&0\\\\ 0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\\\ 0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&1&0\\\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\end\{array\}\\right\]\\in\\mathbb\{R\}^\{14\\times 15\}\.
The sampling distribution is

d​\(s,1\)=17​16=142,d​\(s,2\)=17​56=542\.d\(s,1\)=\\frac\{1\}\{7\}\\frac\{1\}\{6\}=\\frac\{1\}\{42\},\\qquad d\(s,2\)=\\frac\{1\}\{7\}\\frac\{5\}\{6\}=\\frac\{5\}\{42\}\.We use

γ=0\.99,α=0\.25\.\\gamma=0\.99,\\qquad\\alpha=0\.25\.Let

denote the nonterminal probability at state77, corresponding to terminal probability1/1001/100\. The terminal mass is omitted in the bootstrap term because it contributes zero continuation value\.

s=1s=1s=2s=2s=3s=3s=4s=4s=5s=5s=6s=6s=7s=7a=2a=2θ9\\theta\_\{9\}θ10\\theta\_\{10\}θ11\\theta\_\{11\}θ12\\theta\_\{12\}θ13\\theta\_\{13\}θ14\\theta\_\{14\}θ15\\theta\_\{15\}a=2a=22​θ1\+θ82\\theta\_\{1\}\+\\theta\_\{8\}a=1a=12​θ2\+θ82\\theta\_\{2\}\+\\theta\_\{8\}a=1a=12​θ3\+θ82\\theta\_\{3\}\+\\theta\_\{8\}a=1a=12​θ4\+θ82\\theta\_\{4\}\+\\theta\_\{8\}a=1a=12​θ5\+θ82\\theta\_\{5\}\+\\theta\_\{8\}a=1a=12​θ6\+θ82\\theta\_\{6\}\+\\theta\_\{8\}a=1a=1θ7\+2​θ8\\theta\_\{7\}\+2\\theta\_\{8\}a=1a=1Figure 2:Baird’s seven\-star Q\-learning example\. Solid arrows are labeled with the solid actiona=1a=1, and dashed or dotted arrows are labeled with the dash actiona=2a=2\. The labels on the arrows show the corresponding feature components\.With the row ordering

\(1,1\),\(2,1\),…,\(7,1\),\(1,2\),\(2,2\),…,\(7,2\),\(1,1\),\(2,1\),\\ldots,\(7,1\),\(1,2\),\(2,2\),\\ldots,\(7,2\),the transition matrixP∈ℝ14×7P\\in\\mathbb\{R\}^\{14\\times 7\}is

P=\[1234567\(1,1\)0000001\(2,1\)0000001\(3,1\)0000001\(4,1\)0000001\(5,1\)0000001\(6,1\)0000001\(7,1\)000000τ\(1,2\)1616161616160\(2,2\)1616161616160\(3,2\)1616161616160\(4,2\)1616161616160\(5,2\)1616161616160\(6,2\)1616161616160\(7,2\)τ6τ6τ6τ6τ6τ60\]\.P=\\left\[\\begin\{array\}\[\]\{c\|ccccccc\}&1&2&3&4&5&6&7\\\\ \\hline\\cr\(1,1\)&0&0&0&0&0&0&1\\\\ \(2,1\)&0&0&0&0&0&0&1\\\\ \(3,1\)&0&0&0&0&0&0&1\\\\ \(4,1\)&0&0&0&0&0&0&1\\\\ \(5,1\)&0&0&0&0&0&0&1\\\\ \(6,1\)&0&0&0&0&0&0&1\\\\ \(7,1\)&0&0&0&0&0&0&\\tau\\\\ \(1,2\)&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&0\\\\ \(2,2\)&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&0\\\\ \(3,2\)&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&0\\\\ \(4,2\)&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&0\\\\ \(5,2\)&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&0\\\\ \(6,2\)&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&\\frac\{1\}\{6\}&0\\\\ \(7,2\)&\\frac\{\\tau\}\{6\}&\\frac\{\\tau\}\{6\}&\\frac\{\\tau\}\{6\}&\\frac\{\\tau\}\{6\}&\\frac\{\\tau\}\{6\}&\\frac\{\\tau\}\{6\}&0\\end\{array\}\\right\]\.
Letπ1\\pi\_\{1\}be the all\-action\-11policy:

π1​\(s\)=1,s=1,…,7\.\\pi\_\{1\}\(s\)=1,\\qquad s=1,\\ldots,7\.The corresponding switching system’s matrix is

Aπ1=I−α​Φ⊤​D​Φ\+α​γ​Φ⊤​D​P​𝚷π1​Φ\.A\_\{\\pi\_\{1\}\}=I\-\\alpha\\Phi^\{\\top\}D\\Phi\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\_\{1\}\}\\Phi\.A direct15×1515\\times 15computation gives

ρ​\(Aπ1\)=1\.001684277044667\.\\rho\(A\_\{\\pi\_\{1\}\}\)=1\.001684277044667\.Therefore,

ρ0\.25dir≥ρ​\(Aπ1\)=1\.001684277044667\>1\.\\rho\_\{0\.25\}^\{\\mathrm\{dir\}\}\\geq\\rho\(A\_\{\\pi\_\{1\}\}\)=1\.001684277044667\>1\.Therefore, the JSR sufficient condition

ραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1does not hold for this Baird Q\-learning example\.

## Appendix EProofs for the i\.i\.d\. Linear Q\-Learning Recursion

In this section, we separate the stochastic proof into three steps: the exact switched recursion, a linear\-growth bound for the martingale term, and the final scalar recursion that gives the finite\-time estimate\.

### E\.1Proof of[Proposition˜2](https://arxiv.org/html/2605.11021#Thmproposition2)

\{restatementbox\}

Restatement of[Proposition˜2](https://arxiv.org/html/2605.11021#Thmproposition2)\.Suppose thatραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. Letθ⋆\\theta^\{\\star\}be the unique projected Bellman fixed point from[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1), and definexk:=θk−θ⋆x\_\{k\}:=\\theta\_\{k\}\-\\theta^\{\\star\}\. Then, for eachk∈\{0,1,…\}k\\in\\\{0,1,\\ldots\\\}, there exists anℱk\\mathcal\{F\}\_\{k\}\-measurable stochastic policyμk\\mu\_\{k\}such that

xk\+1=𝐀μk​xk\+α​wk,k∈\{0,1,…\},x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\},where𝔼​\[wk∣ℱk\]=0\\mathbb\{E\}\[w\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=0\.

###### Proof\.

From[Equation˜16](https://arxiv.org/html/2605.11021#S5.E16),

θk\+1=𝐓α​\(θk\)\+α​wk,k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Subtractθ⋆=𝐓α​\(θ⋆\)\\theta^\{\\star\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta^\{\\star\}\)from both sides:

xk\+1=𝐓α​\(θk\)−𝐓α​\(θ⋆\)\+α​wk,k∈\{0,1,…\}\.x\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\theta^\{\\star\}\)\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.By[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1), there exists anℱk\\mathcal\{F\}\_\{k\}\-measurable stochastic policyμk\\mu\_\{k\}such that

𝐓α​\(θk\)−𝐓α​\(θ⋆\)=𝐀μk​xk\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\theta^\{\\star\}\)=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\.This proves[Equation˜17](https://arxiv.org/html/2605.11021#S5.E17)\. The identity𝔼​\[wk∣ℱk\]=0\\mathbb\{E\}\[w\_\{k\}\\mid\\mathcal\{F\}\_\{k\}\]=0follows from[Equations˜14](https://arxiv.org/html/2605.11021#S5.E14)and[15](https://arxiv.org/html/2605.11021#S5.E15)\. ∎

### E\.2Linear\-Growth Noise Bound

###### Lemma 5\(Linear\-growth noise bound\)\.

Under the assumptions of[Proposition˜2](https://arxiv.org/html/2605.11021#Thmproposition2), letCεC\_\{\\varepsilon\}be the norm\-equivalence constant defined in[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8)\. Then, for everyk∈\{0,1,…\}k\\in\\\{0,1,\\ldots\\\},

𝔼​\[pε​\(wk\)∣ℱk\]≤2​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)\+2​Cε​\(1\+γ\)​ϕmax2​pε​\(xk\)\.\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(w\_\{k\}\)\\mid\\mathcal\{F\}\_\{k\}\]\\leq 2\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\+2\\sqrt\{C\_\{\\varepsilon\}\}\\,\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}p\_\{\\varepsilon\}\(x\_\{k\}\)\.\(45\)

### E\.3Proof of[Lemma˜5](https://arxiv.org/html/2605.11021#Thmlemma5)

###### Proof\.

By[Equation˜15](https://arxiv.org/html/2605.11021#S5.E15),wk=g^k​\(θk\)−g​\(θk\)w\_\{k\}=\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\-g\(\\theta\_\{k\}\), andg​\(θk\)=𝔼​\[g^k​\(θk\)∣ℱk\]g\(\\theta\_\{k\}\)=\\mathbb\{E\}\[\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\\mid\\mathcal\{F\}\_\{k\}\]\. Sincepεp\_\{\\varepsilon\}is a norm,

𝔼​\[pε​\(wk\)∣ℱk\]\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(w\_\{k\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤𝔼​\[pε​\(g^k​\(θk\)\)∣ℱk\]\+pε​\(g​\(θk\)\)\\displaystyle\\leq\\mathbb\{E\}\[p\_\{\\varepsilon\}\(\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\)\\mid\\mathcal\{F\}\_\{k\}\]\+p\_\{\\varepsilon\}\(g\(\\theta\_\{k\}\)\)≤2​𝔼​\[pε​\(g^k​\(θk\)\)∣ℱk\],\\displaystyle\\leq 2\\mathbb\{E\}\[p\_\{\\varepsilon\}\(\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\)\\mid\\mathcal\{F\}\_\{k\}\],where the second inequality uses Jensen’s inequality for the norm:

pε​\(g​\(θk\)\)=pε​\(𝔼​\[g^k​\(θk\)∣ℱk\]\)≤𝔼​\[pε​\(g^k​\(θk\)\)∣ℱk\]\.p\_\{\\varepsilon\}\(g\(\\theta\_\{k\}\)\)=p\_\{\\varepsilon\}\(\\mathbb\{E\}\[\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\\mid\\mathcal\{F\}\_\{k\}\]\)\\leq\\mathbb\{E\}\[p\_\{\\varepsilon\}\(\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\)\\mid\\mathcal\{F\}\_\{k\}\]\.The norm equivalence[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8)gives

pε​\(z\)≤Cε​‖z‖2\.p\_\{\\varepsilon\}\(z\)\\leq\\sqrt\{C\_\{\\varepsilon\}\}\\\|z\\\|\_\{2\}\.For every sample,

‖g^k​\(θk\)‖2\\displaystyle\\\|\\widehat\{g\}\_\{k\}\(\\theta\_\{k\}\)\\\|\_\{2\}≤ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θk‖∞\)\\displaystyle\\leq\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta\_\{k\}\\\|\_\{\\infty\}\\right\)≤ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+\(1\+γ\)​‖Φ​xk‖∞\)\\displaystyle\\leq\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\(1\+\\gamma\)\\\|\\Phi x\_\{k\}\\\|\_\{\\infty\}\\right\)≤ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+\(1\+γ\)​ϕmax​‖xk‖2\)\\displaystyle\\leq\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\(1\+\\gamma\)\\phi\_\{\\max\}\\\|x\_\{k\}\\\|\_\{2\}\\right\)≤ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+\(1\+γ\)​ϕmax​pε​\(xk\)\),\\displaystyle\\leq\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\(1\+\\gamma\)\\phi\_\{\\max\}p\_\{\\varepsilon\}\(x\_\{k\}\)\\right\),because‖x‖2≤pε​\(x\)\\\|x\\\|\_\{2\}\\leq p\_\{\\varepsilon\}\(x\)\. Combining the last inequalities gives

𝔼​\[pε​\(wk\)∣ℱk\]≤2​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)\+2​Cε​\(1\+γ\)​ϕmax2​pε​\(xk\),\\mathbb\{E\}\[p\_\{\\varepsilon\}\(w\_\{k\}\)\\mid\\mathcal\{F\}\_\{k\}\]\\leq 2\\sqrt\{C\_\{\\varepsilon\}\}\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\+2\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}p\_\{\\varepsilon\}\(x\_\{k\}\),which is[Equation˜45](https://arxiv.org/html/2605.11021#A5.E45)\. ∎

### E\.4Proof of[Theorem˜3](https://arxiv.org/html/2605.11021#Thmtheorem3)

\{restatementbox\}

Restatement of[Theorem˜3](https://arxiv.org/html/2605.11021#Thmtheorem3)\.Suppose thatραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. Fixε\>0\\varepsilon\>0such thatβε:=ραdir\+ε<1\\beta\_\{\\varepsilon\}:=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1, and letpεp\_\{\\varepsilon\}be the JSR Lyapunov norm in[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)\. The constantCεC\_\{\\varepsilon\}appearing below is defined in[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8)\. Assume additionally that

λε:=βε\+2​α​Cε​\(1\+γ\)​ϕmax2<1\.\\lambda\_\{\\varepsilon\}:=\\beta\_\{\\varepsilon\}\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}<1\.Then the i\.i\.d\. linear Q\-learning recursion[Equation˜13](https://arxiv.org/html/2605.11021#S5.E13)satisfies, for allk≥0k\\geq 0,

𝔼​\[pε​\(xk\)\]≤λεk​pε​\(x0\)\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε​\(1−λεk\)\.\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(x\_\{k\}\)\]\\leq\\lambda\_\{\\varepsilon\}^\{k\}p\_\{\\varepsilon\}\(x\_\{0\}\)\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\\left\(1\-\\lambda\_\{\\varepsilon\}^\{k\}\\right\)\.Consequently,

𝔼​\[‖θk−θ⋆‖2\]≤Cε​λεk​‖θ0−θ⋆‖2\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε,\\displaystyle\\mathbb\{E\}\[\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\sqrt\{C\_\{\\varepsilon\}\}\\,\\lambda\_\{\\varepsilon\}^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\},and

lim supk→∞𝔼​\[‖θk−θ⋆‖2\]≤2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε\.\\limsup\_\{k\\to\\infty\}\\mathbb\{E\}\[\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\.The corresponding LFA Q\-function error satisfies

𝔼\[∥Φθk−Φθ⋆∥2\]≤∥Φ∥2\(\\displaystyle\\mathbb\{E\}\[\\\|\\Phi\\theta\_\{k\}\-\\Phi\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\\|\\Phi\\\|\_\{2\}\\Bigg\(Cε​λεk​‖θ0−θ⋆‖2\\displaystyle\\sqrt\{C\_\{\\varepsilon\}\}\\,\\lambda\_\{\\varepsilon\}^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε\)\.\\displaystyle\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\\Bigg\)\.
###### Proof\.

By[Proposition˜2](https://arxiv.org/html/2605.11021#Thmproposition2),

xk\+1=𝐀μk​xk\+α​wk,k∈\{0,1,…\}\.x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\+\\alpha w\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Using the triangle inequality forpεp\_\{\\varepsilon\},[Equation˜10](https://arxiv.org/html/2605.11021#S4.E10), and[Lemma˜5](https://arxiv.org/html/2605.11021#Thmlemma5),

𝔼​\[pε​\(xk\+1\)∣ℱk\]\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(x\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤pε​\(𝐀μk​xk\)\+α​𝔼​\[pε​\(wk\)∣ℱk\]\\displaystyle\\leq p\_\{\\varepsilon\}\(\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\)\+\\alpha\\mathbb\{E\}\[p\_\{\\varepsilon\}\(w\_\{k\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤βε​pε​\(xk\)\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)\\displaystyle\\leq\\beta\_\{\\varepsilon\}p\_\{\\varepsilon\}\(x\_\{k\}\)\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\+2​α​Cε​\(1\+γ\)​ϕmax2​pε​\(xk\)\\displaystyle\\qquad\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}p\_\{\\varepsilon\}\(x\_\{k\}\)=λε​pε​\(xk\)\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)\.\\displaystyle=\\lambda\_\{\\varepsilon\}p\_\{\\varepsilon\}\(x\_\{k\}\)\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\.Taking total expectation and defining

ak:=𝔼​\[pε​\(xk\)\]a\_\{k\}:=\\mathbb\{E\}\[p\_\{\\varepsilon\}\(x\_\{k\}\)\]gives

ak\+1≤λε​ak\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\),k∈\{0,1,…\}\.a\_\{k\+1\}\\leq\\lambda\_\{\\varepsilon\}a\_\{k\}\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.Sinceλε<1\\lambda\_\{\\varepsilon\}<1, iteration yields

ak\\displaystyle a\_\{k\}≤λεk​a0\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)​∑j=0k−1λεj\\displaystyle\\leq\\lambda\_\{\\varepsilon\}^\{k\}a\_\{0\}\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\\sum\_\{j=0\}^\{k\-1\}\\lambda\_\{\\varepsilon\}^\{j\}=λεk​a0\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)1−λε​\(1−λεk\)\.\\displaystyle=\\lambda\_\{\\varepsilon\}^\{k\}a\_\{0\}\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\(1\-\\lambda\_\{\\varepsilon\}^\{k\}\)\.This proves[Equation˜19](https://arxiv.org/html/2605.11021#S5.E19)\.

The Euclidean bound follows from

‖xk‖2≤pε​\(xk\),pε​\(x0\)≤Cε​‖x0‖2\.\\\|x\_\{k\}\\\|\_\{2\}\\leq p\_\{\\varepsilon\}\(x\_\{k\}\),\\qquad p\_\{\\varepsilon\}\(x\_\{0\}\)\\leq\\sqrt\{C\_\{\\varepsilon\}\}\\\|x\_\{0\}\\\|\_\{2\}\.Thelim sup\\limsupstatement follows by lettingk→∞k\\to\\infty\. Finally,

‖Φ​xk‖2≤‖Φ‖2​‖xk‖2,\\\|\\Phi x\_\{k\}\\\|\_\{2\}\\leq\\\|\\Phi\\\|\_\{2\}\\\|x\_\{k\}\\\|\_\{2\},which gives[Equation˜21](https://arxiv.org/html/2605.11021#S5.E21)\. ∎

## Appendix FProofs for the Markovian Observation Model

The Markovian appendix follows the same pattern as the i\.i\.d\. case, but it includes one additional coordinate\-sampling discrepancy\. The proofs below first identify this discrepancy and then bound it together with the transition\-reward martingale noise\.

### F\.1Proof of[Proposition˜3](https://arxiv.org/html/2605.11021#Thmproposition3)

\{restatementbox\}

Restatement of[Proposition˜3](https://arxiv.org/html/2605.11021#Thmproposition3)\.Suppose thatραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. Letθ⋆\\theta^\{\\star\}be the unique projected Bellman fixed point from[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1), and definexk:=θk−θ⋆x\_\{k\}:=\\theta\_\{k\}\-\\theta^\{\\star\}\. Then, for eachk∈\{0,1,…\}k\\in\\\{0,1,\\ldots\\\}, there exists anℱk\\mathcal\{F\}\_\{k\}\-measurable stochastic policyμk\\mu\_\{k\}such that

xk\+1=𝐀μk​xk\+α​bk\+α​ξk\+1,k∈\{0,1,…\},x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\+\\alpha b\_\{k\}\+\\alpha\\xi\_\{k\+1\},\\qquad k\\in\\\{0,1,\\ldots\\\},where𝔼​\[ξk\+1∣ℱk\]=0\\mathbb\{E\}\[\\xi\_\{k\+1\}\\mid\\mathcal\{F\}\_\{k\}\]=0\. Moreover, the Markovian coordinate\-sampling error admits the decomposition

bk=Φ⊤​\(eXk​eXk⊤−D\)​\(R\+γ​P​Vθ⋆−Φ​θ⋆\+\(γ​P​𝚷μk−I\)​Φ​xk\)\.b\_\{k\}=\\Phi^\{\\top\}\(e\_\{X\_\{k\}\}e\_\{X\_\{k\}\}^\{\\top\}\-D\)\\left\(R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\+\(\\gamma P\\boldsymbol\{\\Pi\}^\{\\mu\_\{k\}\}\-I\)\\Phi x\_\{k\}\\right\)\.
###### Proof\.

By[Equation˜24](https://arxiv.org/html/2605.11021#S6.E24),

θk\+1=𝐓α​\(θk\)\+α​bk\+α​ξk\+1,k∈\{0,1,…\}\.\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)\+\\alpha b\_\{k\}\+\\alpha\\xi\_\{k\+1\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.Subtractθ⋆=𝐓α​\(θ⋆\)\\theta^\{\\star\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta^\{\\star\}\)from both sides\. Then

xk\+1=𝐓α​\(θk\)−𝐓α​\(θ⋆\)\+α​bk\+α​ξk\+1,k∈\{0,1,…\}\.x\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\theta^\{\\star\}\)\+\\alpha b\_\{k\}\+\\alpha\\xi\_\{k\+1\},\\qquad k\\in\\\{0,1,\\ldots\\\}\.By[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1), there exists anℱk\\mathcal\{F\}\_\{k\}\-measurable stochastic policyμk\\mu\_\{k\}such that

𝐓α​\(θk\)−𝐓α​\(θ⋆\)=𝐀μk​xk\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\_\{k\}\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\theta^\{\\star\}\)=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\.This proves[Equation˜26](https://arxiv.org/html/2605.11021#S6.E26)\. The martingale\-difference property𝔼​\[ξk\+1∣ℱk\]=0\\mathbb\{E\}\[\\xi\_\{k\+1\}\\mid\\mathcal\{F\}\_\{k\}\]=0follows directly from the definition ofξk\+1\\xi\_\{k\+1\}in[Equation˜23](https://arxiv.org/html/2605.11021#S6.E23)\.

It remains to prove[Equation˜27](https://arxiv.org/html/2605.11021#S6.E27)\. By the definition ofδ​\(θ\)\\delta\(\\theta\),

δ​\(θk\)\\displaystyle\\delta\(\\theta\_\{k\}\)=δ​\(θ⋆\)\+γ​P​\(Vθk−Vθ⋆\)−Φ​xk\.\\displaystyle=\\delta\(\\theta^\{\\star\}\)\+\\gamma P\(V\_\{\\theta\_\{k\}\}\-V\_\{\\theta^\{\\star\}\}\)\-\\Phi x\_\{k\}\.Using the same stochastic\-policy linearization as in[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1),

Vθk−Vθ⋆=𝚷μk​Φ​xk\.V\_\{\\theta\_\{k\}\}\-V\_\{\\theta^\{\\star\}\}=\\boldsymbol\{\\Pi\}^\{\\mu\_\{k\}\}\\Phi x\_\{k\}\.Therefore

δ​\(θk\)=R\+γ​P​Vθ⋆−Φ​θ⋆\+\(γ​P​𝚷μk−I\)​Φ​xk\.\\delta\(\\theta\_\{k\}\)=R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\+\(\\gamma P\\boldsymbol\{\\Pi\}^\{\\mu\_\{k\}\}\-I\)\\Phi x\_\{k\}\.Substituting this expression into[Equation˜25](https://arxiv.org/html/2605.11021#S6.E25)proves[Equation˜27](https://arxiv.org/html/2605.11021#S6.E27)\. ∎

### F\.2Markovian Error\-Growth Bound

###### Lemma 6\(Markovian error\-growth bound\)\.

Under the assumptions of[Proposition˜3](https://arxiv.org/html/2605.11021#Thmproposition3), letCεC\_\{\\varepsilon\}be the norm\-equivalence constant defined in[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8)\. Then, for everyk∈\{0,1,…\}k\\in\\\{0,1,\\ldots\\\},

𝔼​\[pε​\(bk\+ξk\+1\)∣ℱk\]\\displaystyle\\mathbb\{E\}\\left\[p\_\{\\varepsilon\}\(b\_\{k\}\+\\xi\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\\right\]≤2​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)\+2​Cε​ϕmax​‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\\displaystyle\\quad\\leq 2\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\+2\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\+4​Cε​\(1\+γ\)​ϕmax2​pε​\(xk\)\.\\displaystyle\\qquad\\quad\+4\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}p\_\{\\varepsilon\}\(x\_\{k\}\)\.

### F\.3Proof of[Lemma˜6](https://arxiv.org/html/2605.11021#Thmlemma6)

###### Proof\.

The coordinate\-sampling error is bounded first\. For anyh∈ℝ\|𝒮\|​\|𝒜\|h\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\|\\mathcal\{A\}\|\}and any coordinate indexii,

‖Φ⊤​\(ei​ei⊤−D\)​h‖2\\displaystyle\\\|\\Phi^\{\\top\}\(e\_\{i\}e\_\{i\}^\{\\top\}\-D\)h\\\|\_\{2\}≤‖Φ⊤​ei​ei⊤​h‖2\+‖Φ⊤​D​h‖2\\displaystyle\\leq\\\|\\Phi^\{\\top\}e\_\{i\}e\_\{i\}^\{\\top\}h\\\|\_\{2\}\+\\\|\\Phi^\{\\top\}Dh\\\|\_\{2\}≤ϕmax​‖h‖∞\+∑jdj​‖ϕj‖2​\|hj\|\\displaystyle\\leq\\phi\_\{\\max\}\\\|h\\\|\_\{\\infty\}\+\\sum\_\{j\}d\_\{j\}\\\|\\phi\_\{j\}\\\|\_\{2\}\|h\_\{j\}\|≤2​ϕmax​‖h‖∞\.\\displaystyle\\leq 2\\phi\_\{\\max\}\\\|h\\\|\_\{\\infty\}\.By[Equation˜27](https://arxiv.org/html/2605.11021#S6.E27), with

hk:=R\+γ​P​Vθ⋆−Φ​θ⋆\+\(γ​P​𝚷μk−I\)​Φ​xk,h\_\{k\}:=R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\+\(\\gamma P\\boldsymbol\{\\Pi\}^\{\\mu\_\{k\}\}\-I\)\\Phi x\_\{k\},we havebk=Φ⊤​\(eXk​eXk⊤−D\)​hkb\_\{k\}=\\Phi^\{\\top\}\(e\_\{X\_\{k\}\}e\_\{X\_\{k\}\}^\{\\top\}\-D\)h\_\{k\}\. SinceP​𝚷μkP\\boldsymbol\{\\Pi\}^\{\\mu\_\{k\}\}is row\-stochastic,

‖hk‖∞\\displaystyle\\\|h\_\{k\}\\\|\_\{\\infty\}≤‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\+\(1\+γ\)​‖Φ​xk‖∞\\displaystyle\\leq\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\+\(1\+\\gamma\)\\\|\\Phi x\_\{k\}\\\|\_\{\\infty\}≤‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\+\(1\+γ\)​ϕmax​‖xk‖2\\displaystyle\\leq\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\+\(1\+\\gamma\)\\phi\_\{\\max\}\\\|x\_\{k\}\\\|\_\{2\}≤‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\+\(1\+γ\)​ϕmax​pε​\(xk\)\.\\displaystyle\\leq\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\+\(1\+\\gamma\)\\phi\_\{\\max\}p\_\{\\varepsilon\}\(x\_\{k\}\)\.Usingpε​\(z\)≤Cε​‖z‖2p\_\{\\varepsilon\}\(z\)\\leq\\sqrt\{C\_\{\\varepsilon\}\}\\\|z\\\|\_\{2\}, it follows that

pε​\(bk\)≤2​Cε​ϕmax​‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\+2​Cε​\(1\+γ\)​ϕmax2​pε​\(xk\)\.p\_\{\\varepsilon\}\(b\_\{k\}\)\\leq 2\\sqrt\{C\_\{\\varepsilon\}\}\\phi\_\{\\max\}\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\+2\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}p\_\{\\varepsilon\}\(x\_\{k\}\)\.
The transition\-reward noise is bounded next\. Define the scalar sample target residual

Yk\+1:=rk\+1\+γ​maxu∈𝒜⁡ϕ​\(sk\+1,u\)⊤​θk−ϕ​\(Xk\)⊤​θk\.Y\_\{k\+1\}:=r\_\{k\+1\}\+\\gamma\\max\_\{u\\in\\mathcal\{A\}\}\\phi\(s\_\{k\+1\},u\)^\{\\top\}\\theta\_\{k\}\-\\phi\(X\_\{k\}\)^\{\\top\}\\theta\_\{k\}\.TheneXk⊤​δ​\(θk\)=𝔼​\[Yk\+1∣ℱk\]e\_\{X\_\{k\}\}^\{\\top\}\\delta\(\\theta\_\{k\}\)=\\mathbb\{E\}\[Y\_\{k\+1\}\\mid\\mathcal\{F\}\_\{k\}\]\. Hence

ξk\+1=ϕ​\(Xk\)​\(Yk\+1−𝔼​\[Yk\+1∣ℱk\]\)\.\\xi\_\{k\+1\}=\\phi\(X\_\{k\}\)\\left\(Y\_\{k\+1\}\-\\mathbb\{E\}\[Y\_\{k\+1\}\\mid\\mathcal\{F\}\_\{k\}\]\\right\)\.Since

\|Yk\+1\|≤Rmax\+\(1\+γ\)​‖Φ​θk‖∞,\|Y\_\{k\+1\}\|\\leq R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta\_\{k\}\\\|\_\{\\infty\},and

‖Φ​θk‖∞≤‖Φ​θ⋆‖∞\+‖Φ​xk‖∞≤‖Φ​θ⋆‖∞\+ϕmax​pε​\(xk\),\\\|\\Phi\\theta\_\{k\}\\\|\_\{\\infty\}\\leq\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\\|\\Phi x\_\{k\}\\\|\_\{\\infty\}\\leq\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\phi\_\{\\max\}p\_\{\\varepsilon\}\(x\_\{k\}\),we obtain

‖ξk\+1‖2\\displaystyle\\\|\\xi\_\{k\+1\}\\\|\_\{2\}≤2​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+\(1\+γ\)​ϕmax​pε​\(xk\)\)\.\\displaystyle\\leq 2\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\(1\+\\gamma\)\\phi\_\{\\max\}p\_\{\\varepsilon\}\(x\_\{k\}\)\\right\)\.Therefore,

𝔼​\[pε​\(ξk\+1\)∣ℱk\]≤\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(\\xi\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]\\leq2​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)\\displaystyle 2\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\+2​Cε​\(1\+γ\)​ϕmax2​pε​\(xk\)\.\\displaystyle\\;\+2\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}p\_\{\\varepsilon\}\(x\_\{k\}\)\.Finally, by the triangle inequality,

𝔼​\[pε​\(bk\+ξk\+1\)∣ℱk\]\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(b\_\{k\}\+\\xi\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤pε​\(bk\)\+𝔼​\[pε​\(ξk\+1\)∣ℱk\]\\displaystyle\\quad\\leq p\_\{\\varepsilon\}\(b\_\{k\}\)\+\\mathbb\{E\}\[p\_\{\\varepsilon\}\(\\xi\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤2​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\)\+2​Cε​ϕmax​‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\\displaystyle\\quad\\leq 2\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\\right\)\+2\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\+4​Cε​\(1\+γ\)​ϕmax2​pε​\(xk\)\.\\displaystyle\\qquad\\quad\+4\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}p\_\{\\varepsilon\}\(x\_\{k\}\)\.∎

### F\.4Proof of[Theorem˜4](https://arxiv.org/html/2605.11021#Thmtheorem4)

\{restatementbox\}

Restatement of[Theorem˜4](https://arxiv.org/html/2605.11021#Thmtheorem4)\.Suppose thatραdir<1\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}<1\. Fixε\>0\\varepsilon\>0such thatβε:=ραdir\+ε<1\\beta\_\{\\varepsilon\}:=\\rho\_\{\\alpha\}^\{\\mathrm\{dir\}\}\+\\varepsilon<1, and letpεp\_\{\\varepsilon\}be the JSR Lyapunov norm in[Theorem˜1](https://arxiv.org/html/2605.11021#Thmtheorem1)\. The constantCεC\_\{\\varepsilon\}appearing below is defined in[Equation˜8](https://arxiv.org/html/2605.11021#S4.E8)\. Assume additionally that

λε:=βε\+4​α​Cε​\(1\+γ\)​ϕmax2<1\.\\lambda\_\{\\varepsilon\}:=\\beta\_\{\\varepsilon\}\+4\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\(1\+\\gamma\)\\phi\_\{\\max\}^\{2\}<1\.Then the single\-trajectory Markovian linear Q\-learning recursion[Equation˜22](https://arxiv.org/html/2605.11021#S6.E22)satisfies, for allk≥0k\\geq 0,

𝔼​\[pε​\(xk\)\]≤\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(x\_\{k\}\)\]\\leq\(λε\)k​pε​\(x0\)\\displaystyle\\;\(\\lambda\_\{\\varepsilon\}\)^\{k\}p\_\{\\varepsilon\}\(x\_\{0\}\)\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)1−λε​\(1−\(λε\)k\)\.\\displaystyle\\;\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\\left\(1\-\(\\lambda\_\{\\varepsilon\}\)^\{k\}\\right\)\.Consequently,

𝔼​\[‖θk−θ⋆‖2\]≤\\displaystyle\\mathbb\{E\}\[\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\]\\leqCε​\(λε\)k​‖θ0−θ⋆‖2\\displaystyle\\;\\sqrt\{C\_\{\\varepsilon\}\}\(\\lambda\_\{\\varepsilon\}\)^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)1−λε,\\displaystyle\\;\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\},and

lim supk→∞𝔼​\[‖θk−θ⋆‖2\]≤2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)1−λε\.\\limsup\_\{k\\to\\infty\}\\mathbb\{E\}\[\\\|\\theta\_\{k\}\-\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\.The corresponding LFA Q\-function error satisfies

𝔼\[∥Φθk−Φθ⋆∥2\]≤∥Φ∥2\(\\displaystyle\\mathbb\{E\}\[\\\|\\Phi\\theta\_\{k\}\-\\Phi\\theta^\{\\star\}\\\|\_\{2\}\]\\leq\\\|\\Phi\\\|\_\{2\}\\Bigg\(Cε​\(λε\)k​‖θ0−θ⋆‖2\\displaystyle\\sqrt\{C\_\{\\varepsilon\}\}\(\\lambda\_\{\\varepsilon\}\)^\{k\}\\\|\\theta\_\{0\}\-\\theta^\{\\star\}\\\|\_\{2\}\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)1−λε\)\.\\displaystyle\+\\frac\{2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\}\{1\-\\lambda\_\{\\varepsilon\}\}\\Bigg\)\.
###### Proof\.

By[Proposition˜3](https://arxiv.org/html/2605.11021#Thmproposition3),

xk\+1=𝐀μk​xk\+α​\(bk\+ξk\+1\),k∈\{0,1,…\}\.x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\+\\alpha\(b\_\{k\}\+\\xi\_\{k\+1\}\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.Using the triangle inequality forpεp\_\{\\varepsilon\}, the contraction inequality[Equation˜10](https://arxiv.org/html/2605.11021#S4.E10), and[Lemma˜6](https://arxiv.org/html/2605.11021#Thmlemma6),

𝔼​\[pε​\(xk\+1\)∣ℱk\]\\displaystyle\\mathbb\{E\}\[p\_\{\\varepsilon\}\(x\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤pε​\(𝐀μk​xk\)\+α​𝔼​\[pε​\(bk\+ξk\+1\)∣ℱk\]\\displaystyle\\leq p\_\{\\varepsilon\}\(\\mathbf\{A\}\_\{\\mu\_\{k\}\}x\_\{k\}\)\+\\alpha\\mathbb\{E\}\[p\_\{\\varepsilon\}\(b\_\{k\}\+\\xi\_\{k\+1\}\)\\mid\\mathcal\{F\}\_\{k\}\]≤λε​pε​\(xk\)\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\)\.\\displaystyle\\leq\\lambda\_\{\\varepsilon\}p\_\{\\varepsilon\}\(x\_\{k\}\)\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\)\.Taking total expectation and setting

ak:=𝔼​\[pε​\(xk\)\]a\_\{k\}:=\\mathbb\{E\}\[p\_\{\\varepsilon\}\(x\_\{k\}\)\]gives

ak\+1≤λε​ak\+2​α​Cε​ϕmax​\(Rmax\+\(1\+γ\)​‖Φ​θ⋆‖∞\+‖R\+γ​P​Vθ⋆−Φ​θ⋆‖∞\),k∈\{0,1,…\}\.a\_\{k\+1\}\\leq\\lambda\_\{\\varepsilon\}a\_\{k\}\+2\\alpha\\sqrt\{C\_\{\\varepsilon\}\}\\,\\phi\_\{\\max\}\\left\(R\_\{\\max\}\+\(1\+\\gamma\)\\\|\\Phi\\theta^\{\\star\}\\\|\_\{\\infty\}\+\\left\\\|R\+\\gamma PV\_\{\\theta^\{\\star\}\}\-\\Phi\\theta^\{\\star\}\\right\\\|\_\{\\infty\}\\right\),\\qquad k\\in\\\{0,1,\\ldots\\\}\.Sinceλε<1\\lambda\_\{\\varepsilon\}<1, iteration yields[Equation˜28](https://arxiv.org/html/2605.11021#S6.E28)\. The Euclidean bound follows from

‖xk‖2≤pε​\(xk\),pε​\(x0\)≤Cε​‖x0‖2\.\\\|x\_\{k\}\\\|\_\{2\}\\leq p\_\{\\varepsilon\}\(x\_\{k\}\),\\qquad p\_\{\\varepsilon\}\(x\_\{0\}\)\\leq\\sqrt\{C\_\{\\varepsilon\}\}\\\|x\_\{0\}\\\|\_\{2\}\.Thelim sup\\limsupstatement follows by lettingk→∞k\\to\\infty\. The Q\-function bound follows from

‖Φ​xk‖2≤‖Φ‖2​‖xk‖2\.\\\|\\Phi x\_\{k\}\\\|\_\{2\}\\leq\\\|\\Phi\\\|\_\{2\}\\\|x\_\{k\}\\\|\_\{2\}\.∎

## Appendix GProofs for Regularized Linear Q\-Learning

This appendix groups the regularized arguments\. The direct representation is unchanged except for the scalar shift−α​η​I\-\\alpha\\eta I, the convex\-hull property is restated in regularized form, and the deterministic and stochastic bounds then follow by applying the same JSR Lyapunov template to the shifted family\.

### G\.1Proof of[Proposition˜4](https://arxiv.org/html/2605.11021#Thmproposition4)

\{restatementbox\}

Restatement of[Proposition˜4](https://arxiv.org/html/2605.11021#Thmproposition4)\.For everyθ,θ¯∈ℝm\\theta,\\bar\{\\theta\}\\in\\mathbb\{R\}^\{m\}, there exists a stochastic policyμθ,θ¯\\mu\_\{\\theta,\\bar\{\\theta\}\}such that

𝐓α,η​\(θ\)−𝐓α,η​\(θ¯\)=𝐀μθ,θ¯η​\(θ−θ¯\)\.\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\bar\{\\theta\}\)=\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}^\{\\eta\}\(\\theta\-\\bar\{\\theta\}\)\.In particular, ifθη⋆\\theta\_\{\\eta\}^\{\\star\}satisfies[Equation˜30](https://arxiv.org/html/2605.11021#S7.E30)andxk:=θk−θη⋆x\_\{k\}:=\\theta\_\{k\}\-\\theta\_\{\\eta\}^\{\\star\}, then the deterministic regularized recursionθk\+1=𝐓α,η​\(θk\)\\theta\_\{k\+1\}=\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\_\{k\}\)satisfies

xk\+1=𝐀μkη​xk,k∈\{0,1,…\},x\_\{k\+1\}=\\mathbf\{A\}\_\{\\mu\_\{k\}\}^\{\\eta\}x\_\{k\},\\qquad k\\in\\\{0,1,\\ldots\\\},whereμk\\mu\_\{k\}is a stochastic policy depending measurably onθk\\theta\_\{k\}andθη⋆\\theta\_\{\\eta\}^\{\\star\}\.

###### Proof\.

Using[Equation˜29](https://arxiv.org/html/2605.11021#S7.E29),

𝐓α,η​\(θ\)−𝐓α,η​\(θ¯\)=𝐓α​\(θ\)−𝐓α​\(θ¯\)−α​η​\(θ−θ¯\)\.\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\bar\{\\theta\}\)=\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)\-\\alpha\\eta\(\\theta\-\\bar\{\\theta\}\)\.By[Proposition˜1](https://arxiv.org/html/2605.11021#Thmproposition1), there exists a stochastic policyμθ,θ¯\\mu\_\{\\theta,\\bar\{\\theta\}\}such that

𝐓α​\(θ\)−𝐓α​\(θ¯\)=𝐀μθ,θ¯​\(θ−θ¯\)\.\\mathbf\{T\}\_\{\\alpha\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha\}\(\\bar\{\\theta\}\)=\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\(\\theta\-\\bar\{\\theta\}\)\.Therefore

𝐓α,η​\(θ\)−𝐓α,η​\(θ¯\)=\(𝐀μθ,θ¯−α​η​I\)​\(θ−θ¯\)=𝐀μθ,θ¯η​\(θ−θ¯\)\.\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\theta\)\-\\mathbf\{T\}\_\{\\alpha,\\eta\}\(\\bar\{\\theta\}\)=\(\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}\-\\alpha\\eta I\)\(\\theta\-\\bar\{\\theta\}\)=\\mathbf\{A\}\_\{\\mu\_\{\\theta,\\bar\{\\theta\}\}\}^\{\\eta\}\(\\theta\-\\bar\{\\theta\}\)\.Ifθη⋆\\theta\_\{\\eta\}^\{\\star\}is a fixed point of𝐓α,η\\mathbf\{T\}\_\{\\alpha,\\eta\}andθ¯=θη⋆\\bar\{\\theta\}=\\theta\_\{\\eta\}^\{\\star\}, then[Equation˜33](https://arxiv.org/html/2605.11021#S7.E33)follows\. ∎

### G\.2Regularized Convexification

The next lemma is the regularized counterpart of[Lemma˜4](https://arxiv.org/html/2605.11021#Thmlemma4)\. It shows that stochastic regularized modes are still covered by the finite deterministic regularized family after convexification\.

###### Lemma 7\(Regularized convex\-hull property\)\.

For every stochastic policyμ\\mu,

𝐀μη∈co⁡\(𝒜α,η\)\.\\mathbf\{A\}\_\{\\mu\}^\{\\eta\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha,\\eta\}\)\.Moreover,

ρ​\(co⁡\(𝒜α,η\)\)=ρ​\(𝒜α,η\)=ρα,ηdir\.\\rho\(\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha,\\eta\}\)\)=\\rho\(\\mathcal\{A\}\_\{\\alpha,\\eta\}\)=\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\.

### G\.3Proof of[Lemma˜7](https://arxiv.org/html/2605.11021#Thmlemma7)

###### Proof\.

For a stochastic policyμ\\mu, the standard convex\-hull identity for stationary policies gives convex weightscπ​\(μ\)c\_\{\\pi\}\(\\mu\)satisfying

𝚷μ=∑π∈Θcπ​\(μ\)​𝚷π,cπ​\(μ\)≥0,∑π∈Θcπ​\(μ\)=1\.\\boldsymbol\{\\Pi\}^\{\\mu\}=\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)\\boldsymbol\{\\Pi\}^\{\\pi\},\\qquad c\_\{\\pi\}\(\\mu\)\\geq 0,\\qquad\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)=1\.Using the affine dependence of𝐀μη\\mathbf\{A\}\_\{\\mu\}^\{\\eta\}on𝚷μ\\boldsymbol\{\\Pi\}^\{\\mu\},

𝐀μη\\displaystyle\\mathbf\{A\}\_\{\\mu\}^\{\\eta\}=I−α​\(Φ⊤​D​Φ\+η​I\)\+α​γ​Φ⊤​D​P​𝚷μ​Φ\\displaystyle=I\-\\alpha\(\\Phi^\{\\top\}D\\Phi\+\\eta I\)\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\mu\}\\Phi=∑π∈Θcπ​\(μ\)​\(I−α​\(Φ⊤​D​Φ\+η​I\)\+α​γ​Φ⊤​D​P​𝚷π​Φ\)\\displaystyle=\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)\\left\(I\-\\alpha\(\\Phi^\{\\top\}D\\Phi\+\\eta I\)\+\\alpha\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)=∑π∈Θcπ​\(μ\)​𝐀πη\.\\displaystyle=\\sum\_\{\\pi\\in\\Theta\}c\_\{\\pi\}\(\\mu\)\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}\.Thus𝐀μη∈co⁡\(𝒜α,η\)\\mathbf\{A\}\_\{\\mu\}^\{\\eta\}\\in\\operatorname\{co\}\(\\mathcal\{A\}\_\{\\alpha,\\eta\}\)\. The equality of the JSR before and after convexification is the standard convex\-hull invariance of the JSR for finite matrix families, applied to𝒜α,η\\mathcal\{A\}\_\{\\alpha,\\eta\}\. ∎

## Appendix HProofs for Regularization\-Dependent JSR Upper Bounds

This appendix proves the regularization\-dependent JSR bounds stated in[Section˜7](https://arxiv.org/html/2605.11021#S7)\. As in the previous appendix sections, each proof begins with the corresponding statement from the main text\. For convenience, we recall the constants

cΦ\\displaystyle c\_\{\\Phi\}:=minπ∈Θ⁡λmin​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\+\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)⊤2\),\\displaystyle=\\min\_\{\\pi\\in\\Theta\}\\lambda\_\{\\min\}\\left\(\\frac\{\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\+\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)^\{\\top\}\}\{2\}\\right\),LΦ\\displaystyle L\_\{\\Phi\}:=maxπ∈Θ⁡‖Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ‖2\.\\displaystyle=\\max\_\{\\pi\\in\\Theta\}\\left\\\|\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\\\|\_\{2\}\.
### H\.1Proof of[Proposition˜5](https://arxiv.org/html/2605.11021#Thmproposition5)

\{restatementbox\}

Restatement of[Proposition˜5](https://arxiv.org/html/2605.11021#Thmproposition5)\.Forα¯∈ℝ\\bar\{\\alpha\}\\in\\mathbb\{R\}, define the formal drift family

ℬα¯:=\{I−α¯​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\):π∈Θ\}\.\\mathcal\{B\}\_\{\\bar\{\\alpha\}\}:=\\left\\\{I\-\\bar\{\\alpha\}\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\):\\pi\\in\\Theta\\right\\\}\.Ifα​η≠1\\alpha\\eta\\neq 1, then

ρα,ηdir=\|1−α​η\|​ρ​\(ℬα/\(1−α​η\)\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}=\|1\-\\alpha\\eta\|\\,\\rho\\left\(\\mathcal\{B\}\_\{\\alpha/\(1\-\\alpha\\eta\)\}\\right\)\.In particular, if0≤α​η<10\\leq\\alpha\\eta<1, then

ρα,ηdir=\(1−α​η\)​ρ​\(ℬα/\(1−α​η\)\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}=\(1\-\\alpha\\eta\)\\,\\rho\\left\(\\mathcal\{B\}\_\{\\alpha/\(1\-\\alpha\\eta\)\}\\right\)\.Ifα​η=1\\alpha\\eta=1, then

ρα,ηdir=α​ρ​\(\{Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ:π∈Θ\}\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}=\\alpha\\,\\rho\\left\(\\left\\\{\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi:\\pi\\in\\Theta\\right\\\}\\right\)\.
###### Proof\.

For each deterministic policyπ\\pi,

𝐀πη=\(1−α​η\)​I−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)\.\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}=\(1\-\\alpha\\eta\)I\-\\alpha\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)\.Ifα​η≠1\\alpha\\eta\\neq 1, then

𝐀πη=\(1−α​η\)​\(I−α1−α​η​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)\)\.\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}=\(1\-\\alpha\\eta\)\\left\(I\-\\frac\{\\alpha\}\{1\-\\alpha\\eta\}\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)\\right\)\.Every length\-kkproduct of matrices in𝒜α,η\\mathcal\{A\}\_\{\\alpha,\\eta\}is therefore\(1−α​η\)k\(1\-\\alpha\\eta\)^\{k\}times the corresponding length\-kkproduct generated byℬα/\(1−α​η\)\\mathcal\{B\}\_\{\\alpha/\(1\-\\alpha\\eta\)\}\. Taking the supremum over products, thekkth root, and the limit gives[Equation˜35](https://arxiv.org/html/2605.11021#S7.E35)\. Ifα​η=1\\alpha\\eta=1, then

𝐀πη=−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\),\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}=\-\\alpha\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\),and homogeneity of the JSR gives[Equation˜36](https://arxiv.org/html/2605.11021#S7.E36)\. ∎

### H\.2Proof of[Proposition˜6](https://arxiv.org/html/2605.11021#Thmproposition6)

\{restatementbox\}

Restatement of[Proposition˜6](https://arxiv.org/html/2605.11021#Thmproposition6)\.LetcΦc\_\{\\Phi\}andLΦL\_\{\\Phi\}be defined in[Equation˜34](https://arxiv.org/html/2605.11021#S7.E34)\. If0≤α​η≤10\\leq\\alpha\\eta\\leq 1, then

ρα,ηdir≤\(1−α​η\)2−2​α​\(1−α​η\)​cΦ\+α2​LΦ2\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{\(1\-\\alpha\\eta\)^\{2\}\-2\\alpha\(1\-\\alpha\\eta\)c\_\{\\Phi\}\+\\alpha^\{2\}L\_\{\\Phi\}^\{2\}\}\.Equivalently,

ρα,ηdir≤1−2​α​\(cΦ\+η\)\+α2​\(LΦ2\+2​cΦ​η\+η2\)\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{1\-2\\alpha\(c\_\{\\Phi\}\+\\eta\)\+\\alpha^\{2\}\\left\(L\_\{\\Phi\}^\{2\}\+2c\_\{\\Phi\}\\eta\+\\eta^\{2\}\\right\)\}\.Consequently, if

0≤α​η≤1,cΦ\+η\>0,0<α<2​\(cΦ\+η\)LΦ2\+2​cΦ​η\+η2,0\\leq\\alpha\\eta\\leq 1,\\qquad c\_\{\\Phi\}\+\\eta\>0,\\qquad 0<\\alpha<\\frac\{2\(c\_\{\\Phi\}\+\\eta\)\}\{L\_\{\\Phi\}^\{2\}\+2c\_\{\\Phi\}\\eta\+\\eta^\{2\}\},thenρα,ηdir<1\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}<1\.

###### Proof\.

For each deterministic policyπ\\pi,

𝐀πη=\(1−α​η\)​I−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)\.\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}=\(1\-\\alpha\\eta\)I\-\\alpha\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)\.For anyx∈ℝmx\\in\\mathbb\{R\}^\{m\}, using0≤α​η≤10\\leq\\alpha\\eta\\leq 1,

‖𝐀πη​x‖22\\displaystyle\\\|\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}x\\\|\_\{2\}^\{2\}=‖\(1−α​η\)​x−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)​x‖22\\displaystyle=\\left\\\|\(1\-\\alpha\\eta\)x\-\\alpha\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)x\\right\\\|\_\{2\}^\{2\}=\(1−α​η\)2​‖x‖22−2​α​\(1−α​η\)​x⊤​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)​x\\displaystyle=\(1\-\\alpha\\eta\)^\{2\}\\\|x\\\|\_\{2\}^\{2\}\-2\\alpha\(1\-\\alpha\\eta\)x^\{\\top\}\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)x\+α2​‖\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)​x‖22\\displaystyle\\qquad\+\\alpha^\{2\}\\left\\\|\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)x\\right\\\|\_\{2\}^\{2\}≤\[\(1−α​η\)2−2​α​\(1−α​η\)​cΦ\+α2​LΦ2\]​‖x‖22\.\\displaystyle\\leq\\left\[\(1\-\\alpha\\eta\)^\{2\}\-2\\alpha\(1\-\\alpha\\eta\)c\_\{\\Phi\}\+\\alpha^\{2\}L\_\{\\Phi\}^\{2\}\\right\]\\\|x\\\|\_\{2\}^\{2\}\.Thus

maxπ∈Θ⁡‖𝐀πη‖2≤\(1−α​η\)2−2​α​\(1−α​η\)​cΦ\+α2​LΦ2\.\\max\_\{\\pi\\in\\Theta\}\\\|\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}\\\|\_\{2\}\\leq\\sqrt\{\(1\-\\alpha\\eta\)^\{2\}\-2\\alpha\(1\-\\alpha\\eta\)c\_\{\\Phi\}\+\\alpha^\{2\}L\_\{\\Phi\}^\{2\}\}\.Since the JSR is bounded above by any common induced\-norm bound,[Equation˜37](https://arxiv.org/html/2605.11021#S7.E37)follows\. Expanding the right\-hand side gives[Equation˜38](https://arxiv.org/html/2605.11021#S7.E38)\. The condition[Equation˜39](https://arxiv.org/html/2605.11021#S7.E39)is exactly the condition that the squared bound in[Equation˜38](https://arxiv.org/html/2605.11021#S7.E38)is strictly smaller than one\. ∎

### H\.3Proof of[Corollary˜1](https://arxiv.org/html/2605.11021#Thmcorollary1)

\{restatementbox\}

Restatement of[Corollary˜1](https://arxiv.org/html/2605.11021#Thmcorollary1)\.For everyη≥0\\eta\\geq 0, define

LΦ,η:=maxπ∈Θ⁡‖Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\+η​I‖2\.L\_\{\\Phi,\\eta\}:=\\max\_\{\\pi\\in\\Theta\}\\left\\\|\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\+\\eta I\\right\\\|\_\{2\}\.Then

ρα,ηdir≤1−2​α​\(cΦ\+η\)\+α2​LΦ,η2\.\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{1\-2\\alpha\(c\_\{\\Phi\}\+\\eta\)\+\\alpha^\{2\}L\_\{\\Phi,\\eta\}^\{2\}\}\.SinceLΦ,η≤LΦ\+ηL\_\{\\Phi,\\eta\}\\leq L\_\{\\Phi\}\+\\eta, the more conservative but directly computable bound

ρα,ηdir≤1−2​α​\(cΦ\+η\)\+α2​\(LΦ\+η\)2\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}\\leq\\sqrt\{1\-2\\alpha\(c\_\{\\Phi\}\+\\eta\)\+\\alpha^\{2\}\(L\_\{\\Phi\}\+\\eta\)^\{2\}\}also holds\. Hence, if

cΦ\+η\>0,0<α<2​\(cΦ\+η\)LΦ,η2,c\_\{\\Phi\}\+\\eta\>0,\\qquad 0<\\alpha<\\frac\{2\(c\_\{\\Phi\}\+\\eta\)\}\{L\_\{\\Phi,\\eta\}^\{2\}\},thenρα,ηdir<1\\rho\_\{\\alpha,\\eta\}^\{\\mathrm\{dir\}\}<1\. A sufficient condition using onlyLΦL\_\{\\Phi\}is obtained by replacingLΦ,η2L\_\{\\Phi,\\eta\}^\{2\}with\(LΦ\+η\)2\(L\_\{\\Phi\}\+\\eta\)^\{2\}in[Equation˜42](https://arxiv.org/html/2605.11021#S7.E42)\.

###### Proof\.

For each deterministic policyπ\\pi,

𝐀πη=I−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\+η​I\)\.\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}=I\-\\alpha\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\+\\eta I\\right\)\.By the definition ofcΦc\_\{\\Phi\},

λmin​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\+\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\)⊤2\+η​I\)≥cΦ\+η,\\lambda\_\{\\min\}\\left\(\\frac\{\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\+\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\\right\)^\{\\top\}\}\{2\}\+\\eta I\\right\)\\geq c\_\{\\Phi\}\+\\eta,and, by definition, the corresponding norm is bounded byLΦ,ηL\_\{\\Phi,\\eta\}, withLΦ,η≤LΦ\+ηL\_\{\\Phi,\\eta\}\\leq L\_\{\\Phi\}\+\\eta\. Therefore, for everyx∈ℝmx\\in\\mathbb\{R\}^\{m\},

‖𝐀πη​x‖22\\displaystyle\\\|\\mathbf\{A\}\_\{\\pi\}^\{\\eta\}x\\\|\_\{2\}^\{2\}=‖x−α​\(Φ⊤​D​Φ−γ​Φ⊤​D​P​𝚷π​Φ\+η​I\)​x‖22\\displaystyle=\\left\\\|x\-\\alpha\\left\(\\Phi^\{\\top\}D\\Phi\-\\gamma\\Phi^\{\\top\}DP\\boldsymbol\{\\Pi\}^\{\\pi\}\\Phi\+\\eta I\\right\)x\\right\\\|\_\{2\}^\{2\}≤\[1−2​α​\(cΦ\+η\)\+α2​LΦ,η2\]​‖x‖22\.\\displaystyle\\leq\\left\[1\-2\\alpha\(c\_\{\\Phi\}\+\\eta\)\+\\alpha^\{2\}L\_\{\\Phi,\\eta\}^\{2\}\\right\]\\\|x\\\|\_\{2\}^\{2\}\.Taking the maximum overπ\\piand using the induced\-norm upper bound on the JSR gives[Equation˜40](https://arxiv.org/html/2605.11021#S7.E40)\. ReplacingLΦ,ηL\_\{\\Phi,\\eta\}byLΦ\+ηL\_\{\\Phi\}\+\\etagives[Equation˜41](https://arxiv.org/html/2605.11021#S7.E41)\. The step\-size condition[Equation˜42](https://arxiv.org/html/2605.11021#S7.E42)makes the squared bound strictly smaller than one\. ∎