Paper deep dive
Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration
Donghwan Lee
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 4/27/2026, 7:39:41 AM
Summary
The paper investigates the geometric structure of Q-value iteration (Q-VI) in discounted Markov Decision Processes (MDPs) by framing it as an affine switching system. While standard contraction arguments show Q-VI converges to the optimal Q-function (Q*) at a rate of the discount factor (γ), this research reveals a two-stage convergence behavior. The authors prove that Q-VI identifies the optimal action class (the practically optimal solution set, POS) in finite time. Specifically, the distance to a particular subset (X1) decays at a rate governed by the Joint Spectral Radius (JSR) of a restricted switching family, which can be strictly faster than γ. This provides a more refined understanding of the trajectory of Q-VI beyond the standard Bellman fixed-point analysis.
Entities (8)
Relation Signals (4)
Q-value iteration → canbemodeledas → Affine Switching System
confidence 100% · we show that the Bellman iteration can be written as an affine switching system
Q-value iteration → isatypeof → Dynamic Programming
confidence 100% · Among its many variants, Q-value iteration (Q-VI) is particularly important...
Q-value iteration → solves → Markov decision process
confidence 100% · Dynamic programming is one of the most fundamental methodologies for solving Markov decision problems.
Joint Spectral Radius → governsrateof → convergence to X1
confidence 90% · the distance from the iterate to a particular subset of X* decays exponentially at a rate governed by the joint spectral radius (JSR)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Dynamic programming is one of the most fundamental methodologies for solving Markov decision problems. Among its many variants, Q-value iteration (Q-VI) is particularly important due to its conceptual simplicity and its classical contraction-based convergence guarantee. Despite the central role of this contraction property, it does not fully reveal the geometric structure of the Q-VI trajectory. In particular, when one is interested not only in the final limit $Q^*$ but also in when the induced greedy policy becomes effectively optimal, the standard contraction argument provides only a coarse characterization. To formalize this notion, we denote by $\mathcal X^*$ the set of $Q$-functions whose corresponding tie-broken greedy policies are optimal, referred to as the practically optimal solution set (POS). In this paper, we revisit discounted Q-VI through the lens of switching system theory and derive new geometric insights into its behavior. In particular, we show that although Q-VI does not reach $Q^*$ in finite time in general, it identifies the optimal action class in finite time. Furthermore, we prove that the distance from the iterate to a particular subset of $\mathcal X^*$ decays exponentially at a rate governed by the joint spectral radius (JSR) of a restricted switching family. This rate can be strictly faster than the standard $\gamma$ rate when the restricted JSR is strictly smaller than $\gamma$, while the convergence of the entire $Q$-function to $Q^*$ can still be dominated by the slower $\gamma$ mode, where $\gamma$ denotes the discount factor. These results reveal a two-stage geometric behavior of Q-VI: a fast convergence toward $\mathcal X_1$, followed by a slower convergence toward $Q^*$ in general.
Tags
Links
- Source: https://arxiv.org/abs/2604.17457v1
- Canonical: https://arxiv.org/abs/2604.17457v1
Trouble viewing inline? Open PDF directly →
Full Text
104,578 characters extracted from source content.
Expand or collapse full text
Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration Donghwan Lee Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon 34141, South Korea donghwan@kaist.ac.kr Abstract Dynamic programming is one of the most fundamental methodologies for solving Markov decision problems. Among its many variants, Q-value iteration (Q-VI) is particularly important due to its conceptual simplicity and its classical contraction-based convergence guarantee. Despite the central role of this contraction property, it does not fully reveal the geometric structure of the Q-VI trajectory. In particular, when one is interested not only in the final limit Q∗Q^* but also in when the induced greedy policy becomes effectively optimal, the standard contraction argument provides only a coarse characterization. To formalize this notion, we denote by ∗X^* the set of Q-functions whose corresponding tie-broken greedy policies are optimal, referred to as the practically optimal solution set (POS). In this paper, we revisit discounted Q-VI through the lens of switching system theory and derive new geometric insights into its behavior. In particular, we show that although Q-VI does not reach Q∗Q^* in finite time in general, it identifies the optimal action class in finite time. Furthermore, we prove that the distance from the iterate to a particular subset of ∗X^* decays exponentially at a rate governed by the joint spectral radius (JSR) of a restricted switching family. This rate can be strictly faster than the standard γ rate when the restricted JSR is strictly smaller than γ, while the convergence of the entire Q-function to Q∗Q^* can still be dominated by the slower γ mode, where γ denotes the discount factor. These results reveal a two-stage geometric behavior of Q-VI: a fast convergence toward 1X_1, followed by a slower convergence toward Q∗Q^* in general. I Introduction Dynamic programming [1, 2, 3] is one of the most fundamental methodologies for solving Markov decision processes [4]. Among its many variants, Q-value iteration (Q-VI) is particularly important due to its conceptual simplicity and its classical contraction-based convergence guarantee [2, 3]. In the discounted setting with discount factor γ∈(0,1)γ∈(0,1), the Bellman operator is a γ-contraction in the infinity norm, and hence the Q-VI sequence converges exponentially to the optimal Q-function Q∗Q^* at the rate of γ. This classical result is standard and lies at the foundation of dynamic programming and reinforcement learning [5]. Despite the central importance of this contraction property, it does not fully reveal the geometric structure of the Q-VI trajectory. In particular, when one is interested not only in the final limit Q∗Q^* but also in when the induced greedy policy becomes effectively optimal, the standard contraction argument provides only a coarse characterization. To formalize this notion, we denote by ∗X^* the set of Q-functions whose corresponding tie-broken greedy policies are optimal, and call it the practically optimal solution set (POS). This motivates the main question of the present paper: can one obtain a more refined geometric description of Q-VI by viewing it through the lens of switching systems? To address this question, we introduce a switching-system viewpoint for discounted Q-VI [6]. More precisely, we show that the Bellman iteration can be written as an affine switching system whose switching depends on the tie-broken greedy policy induced by the current iterate. This perspective allows us to connect Q-VI with tools from switching system theory and Lyapunov analysis, and in turn reveals geometric behaviors that are not transparent from the standard contraction proof alone. A key geometric object in our analysis is the affine space 1=Q∗+span().X_1=Q^*+span( 1). The set 1X_1 plays a special role because shifts along the all-ones direction do not change the tie-broken greedy policy, i.e., 1⊂∗X_1 ^*. Moreover, we show that there exists a sufficiently small invariant tube around 1X_1 that is contained in ∗X^*. As a consequence, the iterates enter this tube in finite time, and the tie-broken greedy policy induced by Q-VI identifies the practically optimal solution in finite time. Another contribution of this paper concerns the rate at which this identification occurs. The standard contraction argument controls the distance to Q∗Q^* at rate γ, but does not distinguish between motion along the all-ones direction and motion transverse to it. By deriving an exact switched-linear representation of the Q-VI error over stochastic policies and combining it with a restricted piecewise quadratic Lyapunov analysis, we show that the distance from QkQ_k to 1X_1 decays exponentially at any rate larger than the JSR of a restricted switching family. In particular, when this restricted JSR is strictly smaller than γ, the approach to 1X_1 is strictly faster than the standard γ-rate. This leads to a two-stage picture: first, the iterate rapidly approaches a tube around 1X_1, therefore, we can identify a practically optimal solution; afterwards, the remaining convergence to Q∗Q^* can be dominated by the slower γ mode. I Related work Recently, a line of research has explored reinforcement learning [5] and dynamic programming [1, 2, 3] through the lens of switching system theory. The unified switching system perspective introduced in [7] provides a general framework for analyzing Q-learning algorithms, which was further developed into a discrete-time switching system formulation with rigorous convergence guarantees in [8]. Building upon this perspective, sharper convergence characterizations such as final iteration bounds were established in [9], and finite-time analyses under more practical settings, including the Markovian observation model and diminishing step sizes, were studied in [10]. In the context of Q-VI, geometric and Lyapunov-based properties have also been investigated. In particular, [11] provides a switching-system interpretation of Q-VI and reveals certain geometric behaviors on orthants. Complementary to this direction, convex-analytic and Lyapunov-based approaches have been proposed to study value-based reinforcement learning methods [12], and Q-VI has also been formulated as an affine switching system in [13]. Extensions to switching-based control strategies for policy selection have further been considered in [14]. These works are closely related to the present paper in that they use dynamical-systems tools to study value-based dynamic programming and reinforcement learning algorithms. Beyond the switching-system viewpoint, geometric perspectives on dynamic programming and reinforcement learning have been studied from several complementary directions. The value-function polytope perspective in [15] characterizes geometric and topological properties of value functions in finite MDPs and uses this structure to interpret the behavior of reinforcement learning algorithms. Building on related polyhedral ideas, [16] develops geometric policy iteration by exploiting hyperplane arrangements and boundary structures associated with Markov decision processes. These works are complementary to the present paper: while they focus primarily on the geometry of value functions, policy improvement, and polyhedral structures, we study the geometry of the Q-VI trajectory relative to the affine set 1=Q∗+span()X_1=Q^*+span(1) and the POS ∗X^*. More recently, alternative perspectives on Q-VI have been developed based on probabilistic and geometric viewpoints. The works [17, 18, 19] analyze Q-VI using tools such as absolute probability sequences and provide refined convergence insights for classical MDP solution methods. In a different but related direction, semismooth Newton-type interpretations of dynamic programming have been explored in [20]. Such nonsmooth-equation viewpoints are relevant because Bellman optimality operators involve maximization and policy selection, whereas the present paper focuses on how the same nonsmooth structure induces switching dynamics and finite-time identification of the optimal action class. The mathematical tools used in this paper are also related to the stability theory of switching systems and JSR analysis. The JSR was introduced in [21], and Lyapunov-based approaches to bounding or approximating it have been extensively developed; see, for example, [22]. Our projected Lyapunov construction follows the same broad philosophy, but is tailored to the projected Q-VI dynamics obtained after removing the all-ones direction. This projection is also reminiscent of seminorm-based analyses in reinforcement learning and dynamic programming. In particular, the recent non-asymptotic seminorm Lyapunov stability framework in [23] studies deterministic and stochastic iterative algorithms through seminorm contractions. Although these works provide important insights, most existing results focus either on asymptotic convergence properties, global contraction arguments, or geometric structures of value functions and policies. In contrast, the present paper provides a refined geometric analysis of the Q-VI trajectory itself, characterizing its finite-time policy-identification behavior and revealing a two-stage convergence phenomenon through the notions of invariant sets, invariant tubes, and projected switching dynamics. I Preliminaries I-A Notations The adopted notation is as follows: ℝR: set of real numbers; ℝnR^n: n-dimensional Euclidean space; ℝn×mR^n× m: set of all n×mn× m real matrices; A⊤A : transpose of matrix A; A≻0A 0 (A≺0A 0, A⪰0A 0, and A⪯0A 0, respectively): symmetric positive definite (negative definite, positive semi-definite, and negative semi-definite, respectively) matrix A; I: identity matrix with appropriate dimensions; ||| S|: cardinality of a finite set S; A⊗BA B: Kronecker’s product of matrices A and B; 1: the vector with all entries equal to one; λmax(⋅) _ (·): maximum eigenvalue; λmin(⋅) _ (·): minimum eigenvalue. For a set ⊂ℝnY ^n and a vector x∈ℝnx ^n, dist2(x,)dist_2(x,Y) and dist∞(x,)dist_∞(x,Y) denote the Euclidean distance and the infinity-norm distance from x to Y, respectively, i.e., dist2(x,):=infy∈‖x−y‖2,dist∞(x,):=infy∈‖x−y‖∞.dist_2(x,Y):= _y \|x-y\|_2, _∞(x,Y):= _y \|x-y\|_∞. We write Δ|| _| A| for the probability simplex over a discrete set A, i.e., Δ||:=p∈ℝ||:pi≥0,∑i=1||pi=1. _| A|:= \p ^| A|:\ p_i≥ 0,\ _i=1^| A|p_i=1 \. Throughout the paper, ArgmaxArg\,max denotes the set-valued maximizer. In contrast, argmaxarg\,max denotes a fixed tie-broken single-valued maximizer. Accordingly, for each Q, the map πQ(s):=argmaxa∈Q(s,a) _Q(s):=arg\,max_a∈ AQ(s,a) is called the tie-broken greedy policy. I-B Markov decision problem We consider the infinite-horizon discounted Markov decision problem (MDP) [4], where the agent sequentially takes actions to maximize cumulative discounted rewards. In an MDP with the state space :=1,2,…,|| S:=\1,2,…,| S|\ and action space :=1,2,…,|| A:=\1,2,…,| A|\, the decision maker selects an action a∈a∈ A at the current state s. The state then transitions to a state s′s with probability P(s′|s,a)P(s |s,a), and the transition incurs a reward r(s,a,s′)r(s,a,s ), where r is a reward function. For convenience, we consider a deterministic reward function and simply write r(sk,ak,sk+1)=:rk+1r(s_k,a_k,s_k+1)=:r_k+1 for k≥0k≥ 0. A deterministic policy, π:→π: S→ A, maps a state s∈s∈ S to an action π(s)∈π(s)∈ A. Throughout the paper, the discount factor satisfies γ∈(0,1)γ∈(0,1). For a policy π, the Q-function under policy π is defined as Qπ(s,a)=[∑k=0∞γkrk+1|s0=s,a0=a,π]Q^π(s,a)=E [ . _k=0^∞γ^kr_k+1 |s_0=s,a_0=a,π ] for all s∈,a∈s∈ S,a∈ A. The optimal Q-function is defined by Q∗(s,a):=supπ∈ΘQπ(s,a),s∈,a∈,Q^*(s,a):= _π∈ Q^π(s,a), s∈ S,\ a∈ A, where Θ is the set of all admissible deterministic policies. A deterministic policy π∗π^* is called optimal if Qπ∗(s,a)=Q∗(s,a)Q^π^*(s,a)=Q^*(s,a) for all (s,a)∈×(s,a)∈ S× A. Once Q∗Q^* is known, an optimal tie-broken greedy policy can be recovered by π∗(s)=argmaxa∈Q∗(s,a)π^*(s)=arg\,max_a∈ AQ^*(s,a). For each state s∈s∈ S, let us define the set of all optimal greedy actions Φ∗(s):=Argmaxa∈Q∗(s,a). ^*(s):=Arg\,max_a∈ AQ^*(s,a). Then, we can define the set of all optimal deterministic policies by Θ∗:=π∈Θ:π(s)∈Φ∗(s),∀s∈. ^*:=\π∈ :\ π(s)∈ ^*(s),\ ∀ s∈ S\. The corresponding optimal value function is defined as V∗(s):=maxa∈Q∗(s,a).V^*(s):= _a∈ AQ^*(s,a). I-C Q-value iteration In this paper, we consider the so-called Q-value iteration (Q-VI) [2] given in Algorithm 1, where F, defined as (FQ)(s,a):=R(s,a)+γ∑s′∈P(s′|s,a)maxa′∈Q(s′,a′),(s,a)∈×,(FQ)(s,a):=R(s,a)+γΣ _s ∈ SP(s |s,a) _a ∈ AQ(s ,a ), (s,a)∈ S× A, is called the Bellman operator. It is well known that the iterates of Q-VI converge exponentially to Q∗Q^* in terms of the infinity norm ∥⋅∥∞ \|· \|_∞ [2, Lemma 2.5]. Lemma 1. We have the bound for the Q-VI iterates ‖Qk+1−Q∗‖∞≤γ‖Qk−Q∗‖∞. \|Q_k+1-Q^* \|_∞≤γ \|Q_k-Q^* \|_∞. The proof is given in [2, Lemma 2.5], which is based on the contraction property of the Bellman operator. Note that [2, Lemma 2.5] deals with value iteration for the value function instead of the Q-function addressed in our work. However, the argument is equivalent for Q-VI. A direct consequence of Lemma 1 is the convergence of Q-VI: ‖Qk−Q∗‖∞≤γk‖Q0−Q∗‖∞. \|Q_k-Q^* \|_∞≤γ^k \|Q_0-Q^* \|_∞. (1) Algorithm 1 Q-VI 1:Initialize Q0∈ℝ||||Q_0∈R^| S|| A| randomly. 2:for iteration k=0,1,…k=0,1,… do 3: Update Qk+1(s,a)=R(s,a)+γ∑s′∈P(s′|s,a)maxa′∈Qk(s′,a′)⏟=:FQkQ_k+1(s,a)= R(s,a)+γΣ _s ∈ SP(s |s,a) _a ∈ AQ_k(s ,a )_=:FQ_k 4:end for In what follows, we introduce an equivalent switching-system model that captures the behavior of Q-VI. IV Switching system model of Q-VI In this section, we study a discrete-time switching-system model of Q-VI and establish its finite-time convergence based on the stability analysis of the switching system. IV-A Switching system Let us consider the linear switching system [6], denoted by ℋ:=A1,A2,…,AM H:=\A_1,A_2,…,A_M\, xk+1=Aσkxk,x0=z∈ℝn,k∈0,1,…,x_k+1=A_ _kx_k, x_0=z∈R^n, k∈\0,1,…\, where xk∈ℝnx_k ^n is the state, σ∈ℳ:=1,2,…,Mσ :=\1,2,…,M\ in AσA_σ is called the mode, σk∈ℳ _k is called the switching signal, and ℋ:=A1,A2,…,AM H:=\A_1,A_2,…,A_M\ is called the family of subsystem matrices. The analysis and control synthesis of linear switching systems have been actively studied during the last decades [6]. The joint spectral radius (JSR) [22, 21] measures the maximum exponential growth rate that can arise from switching arbitrarily among the matrices. Definition 1 (Joint spectral radius [21]). Given a set of matrices Ai∈ℝn×ni=1M\A_i∈R^n× n\_i=1^M, the JSR is defined as ρ(A1,⋯,AM)=limk→∞maxσ¯k∈ℳk‖Aσk⋯Aσ2Aσ1‖1/k.ρ(A_1,·s,A_M)= _k→∞ _ σ_k∈ M^k \|A_ _k·s A_ _2A_ _1 \|^1/k. where ∥⋅∥\|·\| is any submultiplicative matrix norm, and σ¯k:=(σ1,σ2,…,σk)∈ℳk σ_k:=( _1, _2,…, _k)∈ M^k. The JSR is independent of the choice of norm. In other words, the limit defining the JSR exists and is the same regardless of the norm, as long as the norm is submultiplicative. A more general class of systems is the affine switching system xk+1=Aσkxk+bσk,x0=z∈ℝn,k∈0,1,…,x_k+1=A_ _kx_k+b_ _k, x_0=z∈R^n, k∈\0,1,…\, where bσk∈ℝnb_ _k∈R^n is an additional input vector, which also switches according to σk _k. Due to the additional input bσkb_ _k, its stabilization becomes more challenging. IV-B Definitions Throughout the paper, we will use the following compact notations: P:=[P1⋮P||]∈ℝ||||×||,R:=[R(⋅,1)⋮R(⋅,||)]∈ℝ||||,Q:=[Q(⋅,1)⋮Q(⋅,||)]∈ℝ||||,P:= bmatrixP_1\\ \\ P_| A|\\ bmatrix∈R^| S|| A|×| S|, R:= bmatrixR(·,1)\\ \\ R(·,| A|)\\ bmatrix∈R^| S|| A|, Q:= bmatrixQ(·,1)\\ \\ Q(·,| A|) bmatrix∈R^| S|| A|, where Pa=P(⋅|⋅,a)∈ℝ||×||P_a=P(·|·,a)∈R^| S|×| S|, Q(⋅,a)∈ℝ||Q(·,a)∈R^| S| for a∈a∈ A, and R∈ℝ||||R∈R^| S|| A| is an enumeration of R(s,a):=[rk|sk=s,ak=a]R(s,a):=E[r_k|s_k=s,a_k=a] with an appropriate order compatible with the other definitions. In this notation, a Q-function is encoded as a single vector Q∈ℝ||||Q∈R^| S|| A|, which enumerates Q(s,a)Q(s,a) for all s∈s∈ S and a∈a∈ A in an appropriate order. In particular, the single value Q(s,a)Q(s,a) can be written as Q(s,a)=(ea⊗es)⊤Q,Q(s,a)=(e_a e_s) Q, where es∈ℝ||e_s∈R^| S| and ea∈ℝ||e_a∈R^| A| are the s-th and a-th basis vectors, respectively. Therefore, in the above definitions, all entries are ordered consistently with this vector Q. For any stochastic policy, π:→Δ||π: S→ _| A|, we define the corresponding action transition matrix as Ππ:=[π(1)⊤⊗e1⊤π(2)⊤⊗e2⊤⋮π(||)⊤⊗e||⊤]∈ℝ||×||||, ^π:= bmatrixπ(1) e_1 \\ π(2) e_2 \\ \\ π(| S|) e_| S| \\ bmatrix∈R^| S|×| S|| A|, (2) where es∈ℝ||e_s ^| S|. Then, it is well known that PΠπ∈ℝ||||×||||P ^π ^| S|| A|×| S|| A| is the transition probability matrix of the state-action pair under policy π. If we consider a deterministic policy, π:→π: S→ A, the stochastic policy can be replaced with the corresponding one-hot encoding vector π→(s):=eπ(s)∈Δ||, π(s):=e_π(s)∈ _| A|, where ea∈ℝ||e_a ^| A|, and the corresponding action transition matrix is identical to Equation 2 with π replaced with π→ π. For any given Q∈ℝ||||Q ^| S|| A|, denote the tie-broken greedy policy with respect to Q as πQ(s):=argmaxa∈Q(s,a)∈ _Q(s):=arg\,max_a∈ AQ(s,a)∈ A. Lastly, throughout the paper, we will use the shorthand ΠQ:=ΠπQ. _Q:= _Q. IV-C Switching system model of Q-VI Having established the basic notation and the Bellman update of Q-VI, we now reformulate the iteration as a switching system. This reformulation is the key step that allows us to analyze Q-VI using tools from switching system theory. In particular, it makes explicit that the evolution of the iterate is governed by a family of affine subsystems, where the active mode is determined by the tie-broken greedy policy induced by the current Q-function. Based on this viewpoint, the geometric and convergence properties of Q-VI can be studied in a more refined manner than by the standard contraction argument alone. In particular, using the notation introduced above, the update in Algorithm 1 can be rewritten as Qk+1=R+γPΠQkQk:=F(Qk).Q_k+1=R+γ P _Q_kQ_k:=F(Q_k). (3) Recall the definitions of πQ(s) _Q(s) and ΠQ _Q. Invoking the optimal Bellman equation (γPΠQ∗−I)Q∗+R=0(γ P _Q^*-I)Q^*+R=0, Equation 3 can be further rewritten as (Qk+1−Q∗)=γPΠQk(Qk−Q∗)+γP(ΠQk−ΠQ∗)Q∗,(Q_k+1-Q^*)=γ P _Q_k(Q_k-Q^*)+γ P( _Q_k- _Q^*)Q^*, which is an affine switching system. In particular, for any Q∈ℝ||||Q∈R^| S|| A|, let us define AQ:=γPΠQ∈ℝ||||×||||,bQ:=γP(ΠQ−ΠQ∗)Q∗∈ℝ||||.A_Q:=γ P _Q∈R^| S|| A|×| S|| A|, b_Q:=γ P( _Q- _Q^*)Q^*∈R^| S|| A|. Hence, Q-VI can be concisely represented as the affine switching system Qk+1−Q∗=AQk(Qk−Q∗)+bQk,Q_k+1-Q^*=A_Q_k(Q_k-Q^*)+b_Q_k, (4) where AQkA_Q_k and bQkb_Q_k switch among matrices from γPΠπ:π∈Θ\γ P ^π:π∈ \ and vectors from γP(Ππ−Ππ∗)Q∗:π∈Θ\γ P( ^π- ^π^*)Q^*:π∈ \ according to the changes of QkQ_k. In particular, let us define a one-to-one mapping φ:Θ→1,2,…,|Θ| : →\1,2,…,| |\ from a deterministic policy π∈Θπ∈ to an integer in 1,2,…,|Θ|\1,2,…,| |\, and define Ai=γPΠπ∈ℝ||||×||||,bi=γP(Ππ−Ππ∗)Q∗∈ℝ||||,A_i=γ P ^π∈R^| S|| A|×| S|| A|, b_i=γ P( ^π- ^π^*)Q^*∈R^| S|| A|, for all i=φ(π)i= (π) and π∈Θπ∈ . Then, Equation 4 can be written as an affine switching system with the switching signal σk∈1,2,…,|Θ| _k∈\1,2,…,| |\ at time k≥0k≥ 0 determined by σk=φ(πk) _k= ( _k) with πk(⋅):=argmaxa∈Qk(⋅,a)∈Θ. _k(·):= _a∈ AQ_k(·,a)∈ . The following lemma plays an important role. Lemma 2 ([8]). For any Q∈ℝ||||Q∈R^| S|| A|, ‖AQ‖∞=γ\|A_Q\|_∞=γ, where the matrix norm ‖A‖∞:=maxi∑j|Aij|\|A\|_∞:= _i _j|A_ij| and AijA_ij is the element of A in the i-th row and j-th column. Proof. Note that ∑j|[AQ]ij|=∑j|[γPΠQ]ij|=γ _j|[A_Q]_ij|= _j|[γ P _Q]_ij|=γ, which completes the proof. ∎ Building on this bound, we can identify the exact JSR of the full switching family. Lemma 3. The JSR of the switching system Equation 4 is γ. Proof. Since each PΠπP ^π is row-stochastic, for every switching sequence σ¯k=(σ1,…,σk) σ_k=( _1,…, _k), the matrix Aσk⋯Aσ1=γk(PΠπσk)⋯(PΠπσ1)A_ _k·s A_ _1=γ^k(P _ _k)·s(P _ _1) has infinity norm equal to γkγ^k. Hence, ρ(A1,⋯,AM)=limk→∞maxσ¯k∈1,…,Mk‖Aσk⋯Aσ1‖∞1/k=limk→∞(γk)1/k=γ.ρ(A_1,·s,A_M)= _k→∞ _ σ_k∈\1,…,M\^k \|A_ _k·s A_ _1 \|_∞^1/k= _k→∞(γ^k)^1/k=γ. This completes the proof. ∎ V Invariant tube and practically optimal solution set In the previous section, we reformulated Q-VI as an affine switching system, which provides a convenient dynamical framework for analyzing its trajectory. We now build on this viewpoint to introduce the geometric objects that play a central role in our analysis, namely the practically optimal solution set (POS) and an invariant tube around a distinguished affine subspace. These sets allow us to formalize the idea that, although Q-VI does not generally reach Q∗Q^* in finite time, it can still identify the optimal action class after finitely many iterations. This section develops the corresponding set-theoretic and invariance properties that will serve as the foundation for the subsequent rate analysis. In particular, the POS is defined by ∗:=Q∈ℝ||||:πQ(s)∈Φ∗(s),∀s∈,X^*:= \Q ^| S|| A|:\ _Q(s)∈ ^*(s),\ ∀ s∈ S \, where πQ _Q denotes the tie-broken greedy policy induced by Q, i.e., πQ(s):=argmaxa∈Q(s,a). _Q(s):=arg\,max_a∈ AQ(s,a). The set ∗X^* has the following interpretation: if Q∈∗Q ^*, then the corresponding tie-broken greedy policy πQ _Q is one of the optimal policies, even if Q≠Q∗Q≠ Q^*. In other words, although Q may not be the optimal Q-function, the induced policy πQ _Q is nonetheless optimal. Moreover, we define the affine space 1:=Q∈ℝ||||:Q=Q∗+α,α∈ℝ=span()+Q∗.X_1:= \Q ^| S|| A|:Q=Q^*+ 1,\ α \=span(1)+Q^*. A key property of the set 1X_1 is that adding a constant α 1 to Q∗Q^* does not change the corresponding tie-broken greedy policy, which remains optimal. Consequently, we have 1⊂∗X_1 ^*. This property is formally stated in the following result. Lemma 4. We have 1⊂∗X_1 ^*. Proof. Let Q∈1Q _1. Then Q=Q∗+αQ=Q^*+ 1 for some α∈ℝα . Since adding a constant multiple of 1 does not change the action ordering, Argmaxa∈Q(s,a)=Argmaxa∈Q∗(s,a)=Φ∗(s),∀s∈.Arg\,max_a∈ AQ(s,a)=Arg\,max_a∈ AQ^*(s,a)= ^*(s), ∀ s∈ S. Hence every tie-broken greedy action of Q belongs to Φ∗(s) ^*(s), so Q∈∗Q ^*. This completes the proof. ∎ The set 1X_1 plays a central role in this paper. We therefore begin by introducing an important property of this set: 1X_1 is, in fact, an invariant set under the Bellman operator F. Proposition 1 (Invariance of 1X_1). If Qk∈1Q_k _1, then Qk+1∈1Q_k+1 _1. More precisely, if Qk=Q∗+αkQ_k=Q^*+ _k1 for some αk∈ℝ _k , then Qk+1=Q∗+γαkQ_k+1=Q^*+γ _k1. Proof. Suppose that Qk=Q∗+αkQ_k=Q^*+ _k1. Since adding a constant multiple of 1 does not change the action ordering, every tie-broken greedy action of QkQ_k is optimal for Q∗Q^*. Hence πQk∈Θ∗ _Q_k∈ ^*. Using the Bellman update, Qk+1=R+γPΠQk(Q∗+αk)Q_k+1=R+γ P _Q_k(Q^*+ _k1). Because πQk _Q_k is an optimal policy, we have R+γPΠQkQ∗=Q∗R+γ P _Q_kQ^*=Q^*. Also, since PΠQkP _Q_k is stochastic, it satisfies PΠQk=P _Q_k1=1. Therefore, it follows that Qk+1=Q∗+γαkQ_k+1=Q^*+γ _k1, and Qk+1∈1Q_k+1 _1, which proves the claim. ∎ A natural question at this point is whether ∗X^* is also an invariant set under the same Bellman operator F. The answer is negative. In other words, ∗X^* is not an invariant set, as can be shown by a simple counterexample. However, we show that although ∗X^* itself is not invariant, there exists a sufficiently small tube around 1:=Q∗+span()X_1:=Q^*+span(1), which is invariant and contained in ∗X^*. This observation leads naturally to the next step of the analysis. Once such a tube is identified, we can connect set invariance with finite-time policy identification. Before proceeding further, we introduce an assumption to exclude the degenerate case. Assumption 1 (Optimal-class separation). Let us define sep:=s∈:Φ∗(s)≠. S_sep:=\s∈ S:\ ^*(s)≠ A\. Throughout the paper, we assume that sep≠∅ S_sep≠ . 1 excludes the degenerate case in which every action is optimal at every state. In particular, it guarantees the existence of at least one state where optimal and non-optimal actions are strictly separated so that the minimum optimality gap Δ¯ , which will be defined shortly, is positive. This positive gap plays a crucial role in our analysis, since it provides a quantitative margin that allows us to show finite-time identification of the optimal action class once the iterate enters a sufficiently small neighborhood of 1X_1. In particular, for each s∈seps∈ S_sep, let us define Δ¯s:=V∗(s)−maxa∉Φ∗(s)Q∗(s,a), _s:=V^*(s)- _a∉ ^*(s)Q^*(s,a), and let Δ¯:=mins∈sepΔ¯s. := _s∈ S_sep _s. Since the action space is finite, we have Δ¯>0 >0. If sep=∅ S_sep= , then every action is optimal at every state and the identification problem is trivial. That is, the above assumption is imposed merely to exclude the trivial case. We are now ready to state the invariant-tube result. Proposition 2 (Invariant tube inside ∗X^*). Let 1 hold, and fix any δ∈(0,Δ¯/2)δ∈(0, /2). Let us define the tube around 1X_1 δ:=Q∈ℝ||||:dist∞(Q,1)≤δ. T_δ:= \Q ^| S|| A|:\ dist_∞(Q,X_1)≤δ \. Then, the tube is a subset of ∗X^*, i.e., δ⊂∗ T_δ ^*, and, moreover, F(δ)⊂γδ⊂δF( T_δ)⊂ T_γδ⊂ T_δ, i.e., it is invariant under the Bellman operator F. Proof. Let Q∈δQ∈ T_δ. By definition, there exists α∈ℝα such that ‖Q−(Q∗+α)‖∞≤δ\|Q-(Q^*+ 1)\|_∞≤δ. Fix any state s∈seps∈ S_sep and any action b∉Φ∗(s)b∉ ^*(s). Then, we can derive the following inequalities: maxa∈Φ∗(s)Q(s,a)−Q(s,b)= _a∈ ^*(s)Q(s,a)-Q(s,b)= maxa∈Q∗(s,a)−Q∗(s,b) _a∈ AQ^*(s,a)-Q^*(s,b) +(maxa∈Φ∗(s)Q(s,a)−(maxa∈Q∗(s,a)+α)) + ( _a∈ ^*(s)Q(s,a)- ( _a∈ AQ^*(s,a)+α ) ) −(Q(s,b)−(Q∗(s,b)+α)) - (Q(s,b)- (Q^*(s,b)+α ) ) ≥ ≥ maxa∈Q∗(s,a)−Q∗(s,b) _a∈ AQ^*(s,a)-Q^*(s,b) +(maxa∈Φ∗(s)Q(s,a)−(maxa∈Φ∗(s)Q∗(s,a)+α)) + ( _a∈ ^*(s)Q(s,a)- ( _a∈ ^*(s)Q^*(s,a)+α ) ) −(Q(s,b)−(Q∗(s,b)+α)) - (Q(s,b)- (Q^*(s,b)+α ) ) ≥ ≥ Δ¯s−2δ _s-2δ ≥ ≥ Δ¯−2δ -2δ > > 0. 0. Therefore no non-optimal action can be tie-broken greedy at state s∈s∈ S. For states outside sep S_sep, all actions are optimal by definition. Therefore, πQ(s)∈Φ∗(s) _Q(s)∈ ^*(s) for all s∈s∈ S, and Q∈∗Q ^*. Now let Y:=Q∗+α∈1Y:=Q^*+ 1 _1 with ‖Q−Y‖∞≤δ\|Q-Y\|_∞≤δ. Since Q∈∗Q ^*, we have πQ∈Θ∗ _Q∈ ^*. Although πQ _Q need not be the tie-broken greedy policy of Y, the optimality of πQ _Q implies R+γPΠQY=R+γPΠQ(Q∗+α)=Q∗+γα∈1.R+γ P _QY=R+γ P _Q(Q^*+ 1)=Q^*+γ 1 _1. Moreover, F(Q)−(R+γPΠQY)=γPΠQ(Q−Y).F(Q)- (R+γ P _QY )=γ P _Q(Q-Y). Taking the infinity norm and using ‖PΠQ‖∞=1\|P _Q\|_∞=1, we obtain dist∞(F(Q),1)≤‖F(Q)−(R+γPΠQY)‖∞≤γ‖Q−Y‖∞≤γδ<δ.dist_∞(F(Q),X_1)≤ \|F(Q)- (R+γ P _QY ) \|_∞≤γ\|Q-Y\|_∞≤γδ<δ. Therefore, one concludes that F(δ)⊂γδ⊂δF( T_δ)⊂ T_γδ⊂ T_δ. This completes the proof. ∎ The above result implies that once QkQ_k enters the tube δ T_δ during Q-VI, all subsequent iterates remain within the tube. A natural question that then arises is whether the sequence Qkk=0∞\Q_k\_k=0^∞ generated by Q-VI eventually enters δ T_δ. Since this tube is contained in ∗X^*, an affirmative answer would imply finite-time entrance into the POS. The following corollary confirms exactly this point. Corollary 1 (Basic finite-time entrance into ∗X^*). Let 1 hold. Define Kbasic:=0,‖Q0−Q∗‖∞<Δ¯2,⌊log(2‖Q0−Q∗‖∞Δ¯)−logγ⌋+1,‖Q0−Q∗‖∞≥Δ¯2.K_basic:= cases0,&\|Q_0-Q^*\|_∞< 2,\\[5.16663pt] \! ( 2\|Q_0-Q^*\|_∞ )- γ +1,&\|Q_0-Q^*\|_∞≥ 2. cases Then, we have Qk∈∗Q_k ^* for all k≥Kbasick≥ K_basic. Proof. By Equation 1, one has ‖Qk−Q∗‖∞≤γk‖Q0−Q∗‖∞\|Q_k-Q^*\|_∞≤γ^k\|Q_0-Q^*\|_∞. The definition of KbasicK_basic guarantees γk‖Q0−Q∗‖∞<Δ¯2,∀k≥Kbasic.γ^k\|Q_0-Q^*\|_∞< 2, ∀ k≥ K_basic. Hence, for all k≥Kbasick≥ K_basic, we get ‖Qk−Q∗‖∞<Δ¯2\|Q_k-Q^*\|_∞< 2. Since Q∗∈1Q^* _1, this implies dist∞(Qk,1)<Δ¯2dist_∞(Q_k,X_1)< 2. By Proposition 2, it follows that Qk∈∗Q_k ^* for all k≥Kbasick≥ K_basic, which completes the proof. ∎ From the above result, we conclude that although the Q-VI sequence Qkk=0∞\Q_k\_k=0^∞ does not generally reach Q∗Q^* in finite time, the corresponding tie-broken greedy policy eventually identifies the optimal policy in finite time. This is analogous to the property that policy iteration finds the optimal policy in finite time. This naturally raises a sharper question. It is well known that the Q-VI sequence Qkk=0∞\Q_k\_k=0^∞ converges to Q∗Q^* at a rate of γ. Does QkQ_k also approach the tube at the same rate? Could the convergence to the tube be faster than the convergence to Q∗Q^*? If so, might the tie-broken greedy policy induced by QkQ_k identify the optimal policy at a much faster rate than what is suggested by the convergence of QkQ_k to Q∗Q^*? The next section shows that the answer is affirmative whenever the restricted JSR is strictly smaller than γ. VI Faster identification of the POS As discussed in the previous section, we now study the rate at which the Q-VI sequence Qkk=0∞\Q_k\_k=0^∞ converges to the tube δ T_δ. Since the set 1X_1 forms the central line of the tube δ T_δ, we analyze the rate at which the Q-VI iterates become sufficiently close to the set 1X_1. To this end, the first key point is that the Q-VI error admits an exact switching-system representation over some stochastic policies. Lemma 5 (Exact stochastic-policy representation of the Q-VI error). Let ek:=Qk−Q∗∈ℝ||||.e_k:=Q_k-Q^*∈R^| S|| A|. Then, for each k≥0k≥ 0, there exists a stochastic policy μk:→Δ|| _k: S→ _| A| such that ek+1=Aμkek,e_k+1=A_ _ke_k, where AμA_μ for any μ is defined as Aμ:=γPΠμ∈ℝ||||×||||A_μ:=γ P _μ∈R^| S|| A|×| S|| A|. Proof. For each state s∈s∈ S, let us define the optimality error δk(s):=maxa∈Qk(s,a)−maxa∈Q∗(s,a). _k(s):= _a∈ AQ_k(s,a)- _a∈ AQ^*(s,a). Since Qk(s,a)=Q∗(s,a)+ek(s,a)Q_k(s,a)=Q^*(s,a)+e_k(s,a), we have mina∈ek(s,a)≤δk(s)≤maxa∈ek(s,a). _a∈ Ae_k(s,a)≤ _k(s)≤ _a∈ Ae_k(s,a). Therefore, δk(s) _k(s) belongs to the convex hull of the finite set ek(s,a):a∈\e_k(s,a):a∈ A\. Hence there exists a probability vector μk(⋅|s)∈Δ|| _k(·|s)∈ _| A| for each k≥0k≥ 0 such that δk(s)=∑a∈μk(a|s)ek(s,a)=μk(⋅|s)⊤ek(s,⋅). _k(s)=Σ _a∈ A _k(a|s)e_k(s,a)= _k(·|s) e_k(s,·). Stacking these equalities over all states and using the definition of Πμk _ _k in Equation 2, with the same action-major ordering as the vector eke_k, yields δk=Πμkek,δk:=(δk(1),…,δk(||))⊤∈ℝ||. _k= _ _ke_k, _k:=( _k(1),…, _k(| S|)) ∈R^| S|. Now subtract the Bellman optimality equation from the Q-VI update: ek+1(s,a) e_k+1(s,a) =γ∑s′∈P(s′|s,a)(maxb∈Qk(s′,b)−maxb∈Q∗(s′,b)) =γ _s ∈ SP(s |s,a) ( _b∈ AQ_k(s ,b)- _b∈ AQ^*(s ,b) ) =γ∑s′∈P(s′|s,a)δk(s′). =γ _s ∈ SP(s |s,a)\, _k(s ). In vector form, we have ek+1=γPδk=γPΠμkek=Aμkek.e_k+1=γ P _k=γ P _ _ke_k=A_ _ke_k. This proves the claim. ∎ Lemma 5 is important because it shows that the Q-VI error can be represented exactly by a linear switching system without any additional approximation. In particular, although the Bellman operator involves the nonlinear maximization term, the lemma reveals that this nonlinearity can be absorbed into a state-dependent stochastic policy μk _k. As a result, the error dynamics can be analyzed through a family of linear maps AμA_μ, which makes it possible to apply spectral and Lyapunov-based tools to study convergence toward 1X_1. This exact representation serves as the starting point for the projected analysis developed below. Since our main object of interest is the distance from QkQ_k to the affine set 1=Q∗+span(),X_1=Q^*+span(1), it is natural to isolate the component of the error that is orthogonal to span()span(1). This is because the component along 1 only induces a uniform shift of the Q-function and does not affect the tie-broken greedy policy. Accordingly, let ⟂:=I−1n⊤,n:=||||, _ :=I- 1n11 , n:=| S|| A|, denote the orthogonal projection onto span()⟂span(1) . We then define the projected error zk:=⟂ek∈ℝn,z_k:= _ e_k∈R^n, the restricted matrices A¯i=⟂Ai⟂,i∈1,2,…,M, A_i= _ A_i _ , i∈\1,2,…,M\, and for each stochastic policy μ, the restricted matrix A¯μ:=⟂Aμ⟂. A_μ:= _ A_μ _ . The following result shows that the projected error zkz_k also evolves according to the switching system characterized by ℋ¯:=A¯1,A¯2,…,A¯M H:=\ A_1, A_2,…, A_M\, and moreover provides an exact characterization of the distance from QkQ_k to 1X_1. Lemma 6 (Projected error dynamics). The projected error zkz_k is the solution to the following switching-system dynamics: zk+1=A¯μkzk∀k≥0.z_k+1= A_ _kz_k ∀ k≥ 0. Moreover, dist2(Qk,1)=‖zk‖2dist_2(Q_k,X_1)=\|z_k\|_2. Proof. Since Aμ=γA_μ1= 1 for every stochastic policy μ, we may write ek=αk+zke_k= _k1+z_k for some αk∈ℝ _k , and then Aμkek=γαk+Aμkzk.A_ _ke_k=γ _k1+A_ _kz_k. Applying ⟂ _ to both sides yields zk+1=⟂ek+1=⟂Aμkek=⟂Aμkzk=⟂Aμk⟂zk=A¯μkzk,z_k+1= _ e_k+1= _ A_ _ke_k= _ A_ _kz_k= _ A_ _k _ z_k= A_ _kz_k, which proves the first claim. For the second claim, note that 1=Q∗+span()X_1=Q^*+span(1). Therefore, we get dist2(Qk,1)=dist2(ek,span())=‖⟂ek‖2=‖zk‖2,dist_2(Q_k,X_1)=dist_2(e_k,span(1))=\| _ e_k\|_2=\|z_k\|_2, which completes the proof. ∎ To analyze the projected switching dynamics obtained in Lemma 6, it is important to understand the spectral structure of the restricted matrices. In particular, since the convergence toward 1X_1 is governed by the component transverse to span()span(1), we now examine how the eigenstructure of the original matrices is modified under the projection ⟂ _ . The next lemma collects several basic properties of the matrices A¯i A_i, which will play a key role in the subsequent rate analysis. Lemma 7. The following statements hold: 1. Let (v,λ)(v,λ) be an eigenvector-eigenvalue pair of AiA_i. Then A¯i(⟂v)=λ(⟂v). A_i( _ v)=λ( _ v). In particular, if ⟂v≠0 _ v≠ 0, then (⟂v,λ)( _ v,λ) is an eigenvector-eigenvalue pair of A¯i A_i. 2. (,0)(1,0) is an eigenvector-eigenvalue pair of A¯i A_i. Proof. Recall that A¯i=⟂Ai⟂,⟂=I−1n⊤,Ai=γ. A_i= _ A_i _ , _ =I- 1n11 , A_i1= 1. To prove the first statement, let (v,λ)(v,λ) be an eigenvector-eigenvalue pair of AiA_i so that Aiv=λvA_iv=λ v. Since ⟂v=v−⊤vn _ v=v- 1 vn1, we have Ai(⟂v)=Aiv−⊤vnAi=λv−γ 1⊤vn.A_i( _ v)=A_iv- 1 vnA_i1=λ v- γ\,1 vn1. Applying ⟂ _ to both sides yields A¯i(⟂v) A_i( _ v) =⟂Ai⟂v = _ A_i _ v =⟂(λv−γ 1⊤vn) = _ (λ v- γ\,1 vn1 ) =λ⟂v−γ 1⊤vn⟂. =λ _ v- γ\,1 vn _ 1. Since ⟂=0 _ 1=0, it follows that A¯i(⟂v)=λ⟂v A_i( _ v)=λ _ v. Therefore, if ⟂v≠0 _ v≠ 0, then (⟂v,λ)( _ v,λ) is an eigenvector-eigenvalue pair of A¯i A_i. For the second statement, because ⟂=0 _ 1=0, we have A¯i=⟂Ai⟂=⟂Ai0=0 A_i1= _ A_i _ 1= _ A_i0=0. Therefore, (,0)(1,0) is an eigenvector-eigenvalue pair of A¯i A_i. This completes the proof. ∎ Before proceeding to the JSR analysis, we record a simple but useful algebraic identity that connects products of the original subsystem matrices with products of their restricted counterparts. This relation shows that the projection operator ⟂ _ can be propagated through arbitrary matrix products, and it will play a key role in comparing the full switching family with the restricted one. Lemma 8. For any vector x∈ℝnx ^n, any positive integer k, and any switching sequence σ¯k:=(σ1,σ2,…,σk)∈1,2,…,Mk σ_k:=( _1, _2,…, _k)∈\1,2,…,M\^k, we have ⟂Aσk⋯Aσ2Aσ1x=A¯σk⋯A¯σ2A¯σ1x. _ A_ _k·s A_ _2A_ _1x= A_ _k·s A_ _2 A_ _1x. Proof. We prove the claim by induction on k≥0k≥ 0. First, consider the case k=1k=1. Since x=⟂x+(I−⟂)x= _ x+(I- _ )x, we obtain ⟂Aσ1x=⟂Aσ1⟂x+⟂Aσ1(I−⟂)x. _ A_ _1x= _ A_ _1 _ x+ _ A_ _1(I- _ )x. Now note that (I−⟂)x∈span()(I- _ )x (1), and hence, there exists a scalar c∈ℝc such that (I−⟂)x=c.(I- _ )x=c1. Since Ai=γA_i1= 1 for every i, it follows that ⟂Aσ1(I−⟂)x=c⟂Aσ1=cγ⟂=0. _ A_ _1(I- _ )x=c\, _ A_ _11=cγ _ 1=0. Therefore, ⟂Aσ1x=⟂Aσ1⟂x=A¯σ1x. _ A_ _1x= _ A_ _1 _ x= A_ _1x. Hence, the claim holds for k=1k=1. Assume now that the identity holds for some k≥1k≥ 1, namely, ⟂Aσk⋯Aσ2Aσ1x=A¯σk⋯A¯σ2A¯σ1x. _ A_ _k·s A_ _2A_ _1x= A_ _k·s A_ _2 A_ _1x. We show that it also holds for k+1k+1. We write Aσk⋯Aσ1x=⟂Aσk⋯Aσ1x+(I−⟂)Aσk⋯Aσ1x.A_ _k·s A_ _1x= _ A_ _k·s A_ _1x+(I- _ )A_ _k·s A_ _1x. Applying ⟂Aσk+1 _ A_ _k+1 to both sides gives ⟂Aσk+1Aσk⋯Aσ1x _ A_ _k+1A_ _k·s A_ _1x =⟂Aσk+1⟂Aσk⋯Aσ1x = _ A_ _k+1 _ A_ _k·s A_ _1x +⟂Aσk+1(I−⟂)Aσk⋯Aσ1x. + _ A_ _k+1(I- _ )A_ _k·s A_ _1x. Again, since (I−⟂)Aσk⋯Aσ1x∈span()(I- _ )A_ _k·s A_ _1x (1), there exists some scalar d∈ℝd such that (I−⟂)Aσk⋯Aσ1x=d.(I- _ )A_ _k·s A_ _1x=d1. Using Ai=γA_i1= 1 and ⟂=0 _ 1=0, we obtain ⟂Aσk+1(I−⟂)Aσk⋯Aσ1x=d⟂Aσk+1=dγ⟂=0. _ A_ _k+1(I- _ )A_ _k·s A_ _1x=d\, _ A_ _k+11=dγ _ 1=0. Hence, ⟂Aσk+1Aσk⋯Aσ1x=⟂Aσk+1⟂Aσk⋯Aσ1x=A¯σk+1⟂Aσk⋯Aσ1x. _ A_ _k+1A_ _k·s A_ _1x= _ A_ _k+1 _ A_ _k·s A_ _1x= A_ _k+1 _ A_ _k·s A_ _1x. By the induction hypothesis, ⟂Aσk⋯Aσ1x=A¯σk⋯A¯σ1x. _ A_ _k·s A_ _1x= A_ _k·s A_ _1x. Substituting this into the previous equality yields ⟂Aσk+1Aσk⋯Aσ1x=A¯σk+1A¯σk⋯A¯σ1x. _ A_ _k+1A_ _k·s A_ _1x= A_ _k+1 A_ _k·s A_ _1x. Therefore, the claim holds for k+1k+1. By induction, the result follows for all k≥1k≥ 1. ∎ To further understand the convergence behavior of the projected dynamics, it is useful to examine the spectral structure of each restricted subsystem matrix A¯i A_i. In particular, the next result clarifies how the projection onto span()⟂span(1) removes the trivial eigen-direction associated with the all-ones vector and identifies the spectral radius that governs the transverse dynamics. Lemma 9. Let the eigenvalues of γ−1Aiγ^-1A_i be denoted by 1=λ1,i,λ2,i,…,λn,i,n:=||||,1= _1,i, _2,i,…, _n,i, n:=| S|| A|, ordered so that 1=|λ1,i|≥|λ2,i|≥⋯≥|λn,i|1=| _1,i|≥| _2,i|≥·s≥| _n,i|. Then, we have ρ(A¯i)=γ|λ2,i|ρ( A_i)=γ| _2,i|, where ρ denotes the spectral radius. Proof. Recall that Ai=γPΠπiA_i=γ P _ _i satisfies Ai=γA_i1= 1. Let W:=span()⟂W:=span(1) , and choose vectors w2,…,wnw_2,…,w_n forming a basis of W. Define the invertible matrix T:=[w2⋯wn]∈ℝn×n.T:= bmatrix1&w_2&·s&w_n bmatrix ^n× n. Since Ai=γA_i1= 1, the one-dimensional subspace span()span(1) is AiA_i-invariant. Therefore, in the basis induced by T, the matrix AiA_i has the block upper-triangular form T−1AiT=[γαi⊤0Γi]T^-1A_iT= bmatrixγ& _i \\ 0& _i bmatrix for some vector αi∈ℝn−1 _i ^n-1 and some matrix Γi∈ℝ(n−1)×(n−1) _i ^(n-1)×(n-1). Next, since ⟂ _ is the orthogonal projection onto W=span()⟂W=span(1) , we have ⟂=0,⟂wj=wj,j=2,…,n. _ 1=0, _ w_j=w_j, j=2,…,n. Hence, in the same basis, T−1⟂T=[000In−1].T^-1 _ T= bmatrix0&0\\ 0&I_n-1 bmatrix. Therefore, T−1A¯iT T^-1 A_iT =T−1⟂Ai⟂T =T^-1 _ A_i _ T =(T−1⟂T)(T−1AiT)(T−1⟂T) =(T^-1 _ T)(T^-1A_iT)(T^-1 _ T) =[000In−1][γαi⊤0Γi][000In−1] = bmatrix0&0\\ 0&I_n-1 bmatrix bmatrixγ& _i \\ 0& _i bmatrix bmatrix0&0\\ 0&I_n-1 bmatrix =[000Γi]. = bmatrix0&0\\ 0& _i bmatrix. It follows that σ(A¯i)=0∪σ(Γi).σ( A_i)=\0\∪σ( _i). On the other hand, since T−1AiT=[γαi⊤0Γi]T^-1A_iT= bmatrixγ& _i \\ 0& _i bmatrix is block upper triangular, its spectrum is σ(Ai)=γ∪σ(Γi).σ(A_i)=\γ\∪σ( _i). Equivalently, if the eigenvalues of γ−1Aiγ^-1A_i are 1=λ1,i,λ2,i,…,λn,i1= _1,i, _2,i,…, _n,i, then the eigenvalues of AiA_i are γ,γλ2,i,…,γλn,iγ,γ _2,i,…,γ _n,i, and the eigenvalues of A¯i A_i are 0,γλ2,i,…,γλn,i0,γ _2,i,…,γ _n,i. Therefore, ρ(A¯i)=max0,γ|λ2,i|,…,γ|λn,i|=γ|λ2,i|.ρ( A_i)= \0,\,γ| _2,i|,…,γ| _n,i| \=γ| _2,i|. This completes the proof. ∎ While Lemma 9 characterizes the spectral radius of each individual restricted subsystem, our ultimate goal is to understand the asymptotic behavior under arbitrary switching. For this purpose, we now introduce a computable upper bound on the JSR of the restricted switching family. This bound will later provide a convenient quantitative tool for constructing a common Lyapunov function and deriving an explicit exponential convergence estimate. Lemma 10 (A computable upper bound on the JSR). Let ℋ¯:=A¯1,A¯2,…,A¯M H:=\ A_1, A_2,…, A_M\ and suppose that there exist a submultiplicative matrix norm ∥⋅∥⋆\|·\|_ and a constant β¯∈(0,1) β∈(0,1) such that ‖A¯i‖⋆≤β¯,∀i∈1,2,…,M.\| A_i\|_ ≤ β, ∀ i∈\1,2,…,M\. Then the JSR of ℋ¯ H satisfies ρ(A¯1,A¯2,…,A¯M)≤β¯ρ( A_1, A_2,…, A_M)≤ β. Proof. By the definition of the JSR, for any positive integer k, ρ(A¯1,…,A¯M)=limk→∞maxσ¯k∈1,…,Mk‖A¯σk⋯A¯σ1‖⋆1/k.ρ( A_1,…, A_M)= _k→∞ _ σ_k∈\1,…,M\^k \| A_ _k·s A_ _1 \|_ ^1/k. Fix any switching sequence σ¯k=(σ1,σ2,…,σk)∈1,…,Mk σ_k=( _1, _2,…, _k)∈\1,…,M\^k. Since ∥⋅∥⋆\|·\|_ is submultiplicative, we have ‖A¯σk⋯A¯σ1‖⋆≤∏j=1k‖A¯σj‖⋆≤β¯k. \| A_ _k·s A_ _1 \|_ ≤ _j=1^k\| A_ _j\|_ ≤ β^k. Taking the maximum over all switching sequences yields maxσ¯k∈1,…,Mk‖A¯σk⋯A¯σ1‖⋆≤β¯k _ σ_k∈\1,…,M\^k \| A_ _k·s A_ _1 \|_ ≤ β^k. Taking the k-th root and letting k→∞k→∞, we obtain ρ(A¯1,A¯2,…,A¯M)≤β¯ρ( A_1, A_2,…, A_M)≤ β. This completes the proof. ∎ As a consequence, any computable constant β¯<1 β<1 satisfying ‖A¯i‖⋆≤β¯∀i∈1,…,M\| A_i\|_ ≤ β ∀ i∈\1,…,M\ provides an explicit upper bound on the JSR of the restricted switching family. In particular, such a β¯ β can be used as the scaling factor in the construction of the Lyapunov function for the projected dynamics. Lemma 10 provides a computable upper bound on the JSR under an appropriate norm condition. Independently of such a norm construction, however, one can also derive a general structural bound directly from the relationship between the original switching family and its projected counterpart. The next result establishes that the JSR of the restricted switching system cannot exceed that of the original family, and hence is bounded above by γ. Lemma 11. The JSR of the restricted switching system satisfies ρ(A¯1,…,A¯M)≤γ.ρ( A_1,…, A_M)≤γ. Proof. Fix any submultiplicative matrix norm ∥⋅∥\|·\|, any positive integer k≥0k≥ 0, and any switching sequence σ¯k=(σ1,…,σk)∈1,2,…,Mk σ_k=( _1,…, _k)∈\1,2,…,M\^k. Lemma 8 yields A¯σk⋯A¯σ1x=⟂Aσk⋯Aσ1x∀x∈ℝn. A_ _k·s A_ _1x= _ A_ _k·s A_ _1x ∀ x ^n. Hence, this implies A¯σk⋯A¯σ1=⟂Aσk⋯Aσ1 A_ _k·s A_ _1= _ A_ _k·s A_ _1. Therefore, it follows that ‖A¯σk⋯A¯σ1‖≤‖⟂‖‖Aσk⋯Aσ1‖. \| A_ _k·s A_ _1 \|≤\| _ \|\, \|A_ _k·s A_ _1 \|. Taking the maximum over all switching sequences gives maxσ¯k‖A¯σk⋯A¯σ1‖≤‖⟂‖maxσ¯k‖Aσk⋯Aσ1‖. _ σ_k \| A_ _k·s A_ _1 \|≤\| _ \| _ σ_k \|A_ _k·s A_ _1 \|. Taking the k-th root yields (maxσ¯k‖A¯σk⋯A¯σ1‖)1/k≤‖⟂‖1/k(maxσ¯k‖Aσk⋯Aσ1‖)1/k. ( _ σ_k \| A_ _k·s A_ _1 \| )^1/k≤\| _ \|^1/k ( _ σ_k \|A_ _k·s A_ _1 \| )^1/k. Letting k→∞k→∞, and using ‖⟂‖1/k→1\| _ \|^1/k→ 1, we obtain ρ(A¯1,…,A¯M)≤ρ(A1,…,AM).ρ( A_1,…, A_M)≤ρ(A_1,…,A_M). Since ρ(A1,…,AM)=γρ(A_1,…,A_M)=γ, it follows that ρ(A¯1,…,A¯M)≤γρ( A_1,…, A_M)≤γ. This completes the proof. ∎ The implication of Lemma 11 is that the JSR of the restricted switching system does not exceed γ. Motivated by Lemma 11, we now construct a common Lyapunov function for the restricted switching family in order to derive an explicit exponential convergence estimate for the projected dynamics. Lemma 12 (Common Lyapunov function for the restricted switching family). Let ¯:=A¯1,A¯2,…,A¯M,ρ¯:=ρ(A¯1,A¯2,…,A¯M), A:=\ A_1, A_2,…, A_M\, ρ:=ρ( A_1, A_2,…, A_M), and fix any ϵ>0ε>0 such that βϵ:=ρ¯+ϵ∈(0,1). _ε:= ρ+ε∈(0,1). For each integer t≥0t≥ 0, let us define the function Vεt(x):=∑k=0tβε−2kmaxσ¯k∈1,2,…,Mk‖A¯σk⋯A¯σ1x‖22,x∈ℝn.V_ ^t(x):= _k=0^t _ ^-2k _ σ_k∈\1,2,…,M\^k \| A_ _k·s A_ _1x \|_2^2, x ^n. Then the following statements hold: 1. For every t≥0t≥ 0, Vεt+1(x)=‖x‖22+βε−2maxi∈1,…,MVεt(A¯ix).V_ ^t+1(x)=\|x\|_2^2+ _ ^-2 _i∈\1,…,M\V_ ^t( A_ix). 2. For every t≥0t≥ 0 and every x∈ℝnx ^n, Vεt(λx)=|λ|2Vεt(x)V_ ^t(λ x)=|λ|^2V_ ^t(x) for all λ∈ℝλ , and Vεt(x)≤Vεt+1(x)V_ ^t(x)≤ V_ ^t+1(x). 3. There exists a constant Cε>0C_ >0 such that ‖x‖22≤Vεt(x)≤Cε‖x‖22,∀x∈ℝn,∀t≥0.\|x\|_2^2≤ V_ ^t(x)≤ C_ \|x\|_2^2, ∀ x ^n,\ ∀ t≥ 0. 4. For every x∈ℝnx ^n, the limit Vε∞(x):=limt→∞Vεt(x)V_ ^∞(x):= _t→∞V_ ^t(x) exists and is finite. Moreover, ‖x‖22≤Vε∞(x)≤Cε‖x‖22\|x\|_2^2≤ V_ ^∞(x)≤ C_ \|x\|_2^2. 5. The function pε(x):=Vε∞(x)p_ (x):= V_ ^∞(x) is a norm on ℝnR^n. 6. The function Vε∞V_ ^∞ satisfies the Lyapunov inequality Vε∞(A¯ix)≤βε2Vε∞(x),∀x∈ℝn,∀i∈1,…,M.V_ ^∞( A_ix)≤ _ ^2V_ ^∞(x), ∀ x ^n,\ ∀ i∈\1,…,M\. Equivalently, pε(A¯ix)≤βεpε(x),∀x∈ℝn,∀i∈1,…,M.p_ ( A_ix)≤ _ p_ (x), ∀ x ^n,\ ∀ i∈\1,…,M\. 7. Consequently, ‖A¯i‖pε≤βε,∀i∈1,…,M,\| A_i\|_p_ ≤ _ , ∀ i∈\1,…,M\, where ‖A¯i‖pε\| A_i\|_p_ is the induced matrix norm generated by pεp_ ‖A¯i‖pε:=supx≠0pε(A¯ix)pε(x).\| A_i\|_p_ := _x≠ 0 p_ ( A_ix)p_ (x). Therefore, we have ρ(A¯1,A¯2,…,A¯M)≤βερ( A_1, A_2,…, A_M)≤ _ . Proof. We prove the statements one by one. Proof of 1). By definition, one has Vεt+1(x)=∑k=0t+1βε−2kmaxσ¯k∈1,…,Mk‖A¯σk⋯A¯σ1x‖22.V_ ^t+1(x)= _k=0^t+1 _ ^-2k _ σ_k∈\1,…,M\^k \| A_ _k·s A_ _1x \|_2^2. The k=0k=0 term is simply ‖x‖22\|x\|_2^2. For k≥1k≥ 1, writing k=j+1k=j+1, we obtain Vεt+1(x) V_ ^t+1(x) =‖x‖22+∑j=0tβε−2(j+1)maxσ¯j+1‖A¯σj+1⋯A¯σ1x‖22 =\|x\|_2^2+ _j=0^t _ ^-2(j+1) _ σ_j+1 \| A_ _j+1·s A_ _1x \|_2^2 =‖x‖22+βε−2∑j=0tβε−2jmaxi∈1,…,Mmaxτ¯j∈1,…,Mj‖A¯τj⋯A¯τ1A¯ix‖22 =\|x\|_2^2+ _ ^-2 _j=0^t _ ^-2j _i∈\1,…,M\ _ τ_j∈\1,…,M\^j \| A_ _j·s A_ _1 A_ix \|_2^2 =‖x‖22+βε−2maxi∈1,…,MVεt(A¯ix). =\|x\|_2^2+ _ ^-2 _i∈\1,…,M\V_ ^t( A_ix). This proves 1). Proof of 2). The homogeneity follows immediately from the homogeneity of the Euclidean norm: Vεt(λx)=∑k=0tβε−2kmaxσ¯k‖A¯σk⋯A¯σ1(λx)‖22=|λ|2Vεt(x).V_ ^t(λ x)= _k=0^t _ ^-2k _ σ_k\| A_ _k·s A_ _1(λ x)\|_2^2=|λ|^2V_ ^t(x). The monotonicity Vεt(x)≤Vεt+1(x)V_ ^t(x)≤ V_ ^t+1(x) holds because Vεt+1V_ ^t+1 contains all terms of VεtV_ ^t plus one additional nonnegative term. Proof of 3). The lower bound is immediate from the k=0k=0 term: Vεt(x)≥‖x‖22V_ ^t(x)≥\|x\|_2^2. For the upper bound, since ρ¯<βε ρ< _ , choose any number η such that ρ¯<η<βε ρ<η< _ . By the definition of the JSR, there exists an integer K≥0K≥ 0 such that maxσ¯k∈1,…,Mk‖A¯σk⋯A¯σ1‖21/k≤η,∀k≥K. _ σ_k∈\1,…,M\^k \| A_ _k·s A_ _1 \|_2^1/k≤η, ∀ k≥ K. Hence, for all k≥Kk≥ K, we have maxσ¯k∈1,…,Mk‖A¯σk⋯A¯σ1‖2≤ηk. _ σ_k∈\1,…,M\^k \| A_ _k·s A_ _1 \|_2≤η^k. Now, let us define C0:=max1,max0≤k≤K−1η−kmaxσ¯k‖A¯σk⋯A¯σ1‖2.C_0:= \1,\, _0≤ k≤ K-1η^-k _ σ_k\| A_ _k·s A_ _1\|_2 \. Then, for every k≥0k≥ 0, maxσ¯k‖A¯σk⋯A¯σ1‖2≤C0ηk. _ σ_k \| A_ _k·s A_ _1 \|_2≤ C_0\,η^k. Therefore, Vεt(x) V_ ^t(x) =∑k=0tβε−2kmaxσ¯k‖A¯σk⋯A¯σ1x‖22 = _k=0^t _ ^-2k _ σ_k \| A_ _k·s A_ _1x \|_2^2 ≤∑k=0tβε−2k(maxσ¯k‖A¯σk⋯A¯σ1‖2)2‖x‖22 ≤ _k=0^t _ ^-2k ( _ σ_k \| A_ _k·s A_ _1 \|_2 )^2\|x\|_2^2 ≤C02∑k=0t(ηβε)2k‖x‖22 ≤ C_0^2 _k=0^t ( η _ )^2k\|x\|_2^2 ≤C02∑k=0∞(ηβε)2k‖x‖22. ≤ C_0^2 _k=0^∞ ( η _ )^2k\|x\|_2^2. Since η/βε<1η/ _ <1, the geometric series converges. Thus, setting Cε:=C021−(η/βε)2,C_ := C_0^21-(η/ _ )^2, we obtain Vεt(x)≤Cε‖x‖22V_ ^t(x)≤ C_ \|x\|_2^2 for all x and t≥0t≥ 0. This proves 3). Proof of 4). By 2), the sequence Vεt(x)V_ ^t(x) is nondecreasing in t, and by 3), it is uniformly bounded above by Cε‖x‖22C_ \|x\|_2^2. Hence the limit Vε∞(x):=limt→∞Vεt(x)V_ ^∞(x):= _t→∞V_ ^t(x) exists and is finite for every x∈ℝnx ^n. Passing to the limit in the bounds of 3) yields ‖x‖22≤Vε∞(x)≤Cε‖x‖22\|x\|_2^2≤ V_ ^∞(x)≤ C_ \|x\|_2^2. Proof of 5). For each fixed k≥1k≥ 1, let us define νk(x):=βε−kmaxσ¯k∈1,…,Mk‖A¯σk⋯A¯σ1x‖2. _k(x):= _ ^-k _ σ_k∈\1,…,M\^k\| A_ _k·s A_ _1x\|_2. Moreover, define ν0(x):=‖x‖2 _0(x):=\|x\|_2. For each k≥0k≥ 0, νk _k is a seminorm, since it is the pointwise maximum of seminorms. Then Vεt(x)=∑k=0tνk(x)2,pεt(x):=Vεt(x)=(∑k=0tνk(x)2)1/2.V_ ^t(x)= _k=0^t _k(x)^2, p_ ^t(x):= V_ ^t(x)= ( _k=0^t _k(x)^2 )^1/2. Because ν0(x)=‖x‖2 _0(x)=\|x\|_2 is a norm, pεtp_ ^t is a norm for every t≥0t≥ 0. Indeed, positivity and absolute homogeneity are immediate, and the triangle inequality follows from Minkowski’s inequality applied to the vector (ν0(x),ν1(x),…,νt(x))( _0(x), _1(x),…, _t(x)). Now, by definition, pε(x)=Vε∞(x)=limt→∞pεt(x),p_ (x)= V_ ^∞(x)= _t→∞p_ ^t(x), where the limit is monotone increasing. Since each pεtp_ ^t is a norm, we have for all x,y∈ℝnx,y ^n, pεt(x+y)≤pεt(x)+pεt(y)p_ ^t(x+y)≤ p_ ^t(x)+p_ ^t(y). Letting t→∞t→∞, we obtain pε(x+y)≤pε(x)+pε(y).p_ (x+y)≤ p_ (x)+p_ (y). Absolute homogeneity is inherited from Vε∞(λx)=|λ|2Vε∞(x)V_ ^∞(λ x)=|λ|^2V_ ^∞(x), and positive definiteness follows from pε(x)2=Vε∞(x)≥‖x‖22.p_ (x)^2=V_ ^∞(x)≥\|x\|_2^2. Hence pεp_ is a norm. Proof of 6). Using 1), we have Vεt+1(x)=‖x‖22+βε−2maxiVεt(A¯ix)V_ ^t+1(x)=\|x\|_2^2+ _ ^-2 _iV_ ^t( A_ix). Therefore, we have maxiVεt(A¯ix)≤βε2Vεt+1(x). _iV_ ^t( A_ix)≤ _ ^2V_ ^t+1(x). Fixing i, we have Vεt(A¯ix)≤βε2Vεt+1(x)V_ ^t( A_ix)≤ _ ^2V_ ^t+1(x). Letting t→∞t→∞ and using the monotone convergence of both sides gives Vε∞(A¯ix)≤βε2Vε∞(x).V_ ^∞( A_ix)≤ _ ^2V_ ^∞(x). Taking square roots yields pε(A¯ix)≤βεpε(x)p_ ( A_ix)≤ _ p_ (x). Proof of 7). From 6), the induced matrix norm generated by pεp_ satisfies ‖A¯i‖pε:=supx≠0pε(A¯ix)pε(x)≤βε,∀i∈1,…,M.\| A_i\|_p_ := _x≠ 0 p_ ( A_ix)p_ (x)≤ _ , ∀ i∈\1,…,M\. Hence, for any switching sequence (σ1,…,σk)( _1,…, _k), ‖A¯σk⋯A¯σ1‖pε≤∏j=1k‖A¯σj‖pε≤βεk.\| A_ _k·s A_ _1\|_p_ ≤ _j=1^k\| A_ _j\|_p_ ≤ _ ^k. Taking the maximum over all switching sequences, then the k-th root, and finally the limit as k→∞k→∞, we obtain ρ(A¯1,A¯2,…,A¯M)≤βερ( A_1, A_2,…, A_M)≤ _ . This completes the proof. ∎ Lemma 12 establishes a common Lyapunov function for the restricted switching family. In particular, the function V∞εV_∞ satisfies a Lyapunov inequality along the projected error dynamics zkz_k, which becomes the key tool for proving exponential convergence of the distance from QkQ_k to 1X_1. The next result extends the Lyapunov inequality from the deterministic restricted switching family to its convex hull. Therefore, it allows us to handle the stochastic-policy representation that appears in the projected error dynamics. Lemma 13 (Convex-hull extension of the piecewise quadratic Lyapunov function). Let V∞εV_∞ be the piecewise quadratic Lyapunov function defined in Lemma 12, and fix any ϵ>0ε>0 such that βϵ:=ρ¯+ϵ∈(0,1). _ε:= ρ+ε∈(0,1). Then V∞εV_∞ is convex, and for every stochastic policy μ, V∞ε(A¯μx)≤βε2V∞ε(x),∀x∈ℝ||||.V_∞ ( A_μx)≤ _ ^2V_∞ (x), ∀ x ^| S|| A|. Proof. For each deterministic policy π∈Θπ∈ , let Aπ:=γPΠπ,A¯π:=⟂Aπ⟂.A_π:=γ P _π, A_π:= _ A_π _ . Any stochastic policy μ can be represented as a convex combination of deterministic policies: Πμ=∑π∈Θcπ(μ)Ππ,cπ(μ)≥0,∑π∈Θcπ(μ)=1, _μ= _π∈ c_π(μ) _π, c_π(μ)≥ 0, _π∈ c_π(μ)=1, where cπ(μ):=∏s∈μ(π(s)|s).c_π(μ):= _s∈ Sμ(π(s)|s). Consequently, we have Aμ=∑π∈Θcπ(μ)Aπ,A¯μ=∑π∈Θcπ(μ)A¯π.A_μ= _π∈ c_π(μ)A_π, A_μ= _π∈ c_π(μ) A_π. Now, for each finite t, the function VtεV_t is convex because it is a sum of terms of the form x↦maxσ¯k‖A¯σk⋯A¯σ1x‖22x _ σ_k\| A_ _k·s A_ _1x\|_2^2, which is the pointwise maximum of convex quadratic functions. Since V∞ε(x)=supt≥0Vtε(x)V_∞ (x)= _t≥ 0V_t (x), it follows that V∞εV_∞ is also convex. Therefore, using Jensen’s inequality leads to V∞ε(A¯μx) V_∞ ( A_μx) =V∞ε(∑π∈Θcπ(μ)A¯πx) =V_∞ \! ( _π∈ c_π(μ) A_πx ) ≤∑π∈Θcπ(μ)V∞ε(A¯πx) ≤ _π∈ c_π(μ)\,V_∞ ( A_πx) ≤maxπ∈ΘV∞ε(A¯πx). ≤ _π∈ V_∞ ( A_πx). By Lemma 12, one gets maxπ∈ΘV∞ε(A¯πx)≤βε2V∞ε(x) _π∈ V_∞ ( A_πx)≤ _ ^2V_∞ (x). Combining the two inequalities completes the proof. ∎ Lemma 13 shows that the Lyapunov inequality is preserved not only for the deterministic restricted subsystems but also for their convex combinations. This is essential because the projected error dynamics are driven by stochastic policies, and hence the lemma allows the common Lyapunov framework to be applied directly to the actual Q-VI trajectory. With the Lyapunov framework now extended to the stochastic-policy representation of the projected error dynamics, we are ready to establish exponential convergence of the actual Q-VI iterates toward 1X_1. Theorem 1 (Global exponential convergence to 1X_1 for the actual Q-VI). Fix any ϵ>0ε>0 such that βϵ:=ρ¯+ϵ∈(0,1). _ε:= ρ+ε∈(0,1). There exists a constant Cε>0C_ >0 depending on ε>0 >0 such that dist2(Qk,1)≤Cεβεkdist2(Q0,1),∀k≥0.dist_2(Q_k,X_1)≤ C_ _ ^kdist_2(Q_0,X_1), ∀ k≥ 0. (5) Proof. By Lemma 6, we have zk+1=A¯μkzkz_k+1= A_ _kz_k. Hence, by Lemma 13, one can derive V∞ε(zk+1)≤βε2V∞ε(zk),∀k≥0.V_∞ (z_k+1)≤ _ ^2V_∞ (z_k), ∀ k≥ 0. Iterating this inequality gives V∞ε(zk)≤βε2kV∞ε(z0)V_∞ (z_k)≤ _ ^2kV_∞ (z_0). Now, let us define pε(x):=V∞ε(x)p_ (x):= V_∞ (x). Since V∞εV_∞ is the monotone pointwise limit of the functions VtεV_t , and each Vtε V_t is a norm, pεp_ is also a norm. By finite-dimensional norm equivalence, there exists Cε>0C_ >0 such that ‖x‖2≤pε(x)≤Cε‖x‖2,∀x∈ℝ||||.\|x\|_2≤ p_ (x)≤ C_ \|x\|_2, ∀ x ^| S|| A|. Therefore, ‖zk‖2≤pε(zk)≤βεkpε(z0)≤Cεβεk‖z0‖2.\|z_k\|_2≤ p_ (z_k)≤ _ ^kp_ (z_0)≤ C_ _ ^k\|z_0\|_2. Using Lemma 6 once again, dist2(Qk,1)=‖zk‖2,dist2(Q0,1)=‖z0‖2,dist_2(Q_k,X_1)=\|z_k\|_2, _2(Q_0,X_1)=\|z_0\|_2, which proves the claim. ∎ As shown above, QkQ_k converges to 1X_1 exponentially. Moreover, the JSR of the restricted switching system is no greater than γ. Therefore, if ρ¯<γ ρ<γ, then by choosing ε>0 >0 sufficiently small, the quantity βε _ can also be made strictly smaller than γ. In that case, the convergence toward 1X_1 is strictly faster than the standard convergence rate γ of Q-VI. Based on this observation, we can estimate the number of iterations required for QkQ_k to become sufficiently close to 1X_1 and hence enter the POS. This bound can be smaller than the one derived previously, since the earlier estimate was based on the standard rate γ, whereas the present estimate is based on the faster rate βε _ when βε<γ _ <γ. Corollary 2 (Fast finite-time identification of the POS). Let 1 hold, fix any ϵ>0ε>0 such that βϵ:=ρ¯+ϵ∈(0,1), _ε:= ρ+ε∈(0,1), and let Cε>0C_ >0 be the constant from Theorem 1. Define Kid:=0,Cεdist2(Q0,1)<Δ¯2,⌊log(2Cεdist2(Q0,1)Δ¯)−logβε⌋+1,Cεdist2(Q0,1)≥Δ¯2.K_id:= cases0,&C_ \,dist_2(Q_0,X_1)< 2,\\[5.16663pt] \! ( 2C_ \,dist_2(Q_0,X_1) )- _ +1,&C_ \,dist_2(Q_0,X_1)≥ 2. cases Then, we have Qk∈∗Q_k ^* for all k≥Kidk≥ K_id. In particular, πQk(s)∈Φ∗(s),∀s∈,∀k≥Kid. _Q_k(s)∈ ^*(s), ∀ s∈ S,\ ∀ k≥ K_id. Proof. Write ek=αk+zk,zk=⟂ek.e_k= _k1+z_k, z_k= _ e_k. Since αk _k1 does not change the action ordering, only zkz_k matters for policy identification. If ‖zk‖∞<Δ¯2\|z_k\|_∞< 2, then for every state s∈seps∈ S_sep and every action b∉Φ∗(s)b∉ ^*(s), maxa∈Φ∗(s)Q(s,a)−Q(s,b)= _a∈ ^*(s)Q(s,a)-Q(s,b)= maxa∈Q∗(s,a)−Q∗(s,b) _a∈ AQ^*(s,a)-Q^*(s,b) +(maxa∈Φ∗(s)Q(s,a)−(maxa∈Q∗(s,a))) + ( _a∈ ^*(s)Q(s,a)- ( _a∈ AQ^*(s,a) ) ) −(Q(s,b)−(Q∗(s,b))) - (Q(s,b)- (Q^*(s,b) ) ) ≥ ≥ maxa∈Q∗(s,a)−Q∗(s,b) _a∈ AQ^*(s,a)-Q^*(s,b) +(maxa∈Φ∗(s)Q(s,a)−(maxa∈Φ∗(s)Q∗(s,a))) + ( _a∈ ^*(s)Q(s,a)- ( _a∈ ^*(s)Q^*(s,a) ) ) −(Q(s,b)−(Q∗(s,b))) - (Q(s,b)- (Q^*(s,b) ) ) = = Δ¯s+maxa∈Φ∗(s)ek(s,a)−ek(s,b) _s+ _a∈ ^*(s)e_k(s,a)-e_k(s,b) = = Δ¯s+maxa∈Φ∗(s)zk(s,a)+αk−zk(s,b)−αk _s+ _a∈ ^*(s)z_k(s,a)+ _k-z_k(s,b)- _k ≥ ≥ Δ¯s−2‖zk‖∞. _s-2 \|z_k \|_∞. Hence maxa∈Φ∗(s)Qk(s,a)−Qk(s,b)≥Δ¯s−2‖zk‖∞≥Δ¯−2‖zk‖∞>0. _a∈ ^*(s)Q_k(s,a)-Q_k(s,b)≥ _s-2\|z_k\|_∞≥ -2\|z_k\|_∞>0. Thus no non-optimal action can be tie-broken greedy, so πQk(s)∈Φ∗(s) _Q_k(s)∈ ^*(s) for all s∈s∈ S. By Equation 5, ‖zk‖2=dist2(Qk,1)≤Cεβεkdist2(Q0,1).\|z_k\|_2=dist_2(Q_k,X_1)≤ C_ _ ^kdist_2(Q_0,X_1). The definition of KidK_id guarantees Cεβεkdist2(Q0,1)<Δ¯2,∀k≥Kid.C_ _ ^kdist_2(Q_0,X_1)< 2, ∀ k≥ K_id. Since ‖zk‖∞≤‖zk‖2\|z_k\|_∞≤\|z_k\|_2, it follows that Qk∈∗Q_k ^* for all k≥Kidk≥ K_id. ∎ Corollary 2 shows that the POS ∗X^* is identified in finite time through the rapid convergence of QkQ_k toward 1X_1. In particular, once the iterate becomes sufficiently close to 1X_1, its tie-broken greedy policy selects only optimal actions, even though the full Q-function has not yet converged to Q∗Q^*. Thus, this result yields a sharper policy-identification bound than the earlier estimate based solely on the standard γ contraction when βε<γ _ <γ. Overall, the geometric picture is as follows: in the initial phase, QkQ_k quickly approaches 1X_1, enters the tube δ T_δ, and therefore enters ∗X^*. From that point onward, all tie-broken greedy policies πQk _Q_k are optimal, so the remaining iterations may be interpreted as a policy-evaluation process over optimal policies. At the same time, this reveals a two-stage convergence behavior: the approach to 1X_1 may occur at a faster rate, whereas the final convergence to Q∗Q^* can still be dominated by the standard rate γ. VII Two-stage convergence We now formalize this two-stage picture. Theorem 2 (Two-stage convergence). Let 1 hold, and let KidK_id be defined as in Corollary 2. Define A¯∗:=A¯π:π∈Θ∗,ρ¯∗:=ρ(A¯∗), A_*:=\ A_π:π∈ ^*\, ρ_*:=ρ( A_*), where A¯π:=⟂(γPΠπ)⟂ A_π:= _ (γ P ^π) _ for any π∈Θ∗π∈ ^*. Then, ρ¯∗≤ρ¯≤γ ρ_*≤ ρ≤γ and the following statements hold. 1. For any ε>0 >0 such that βε:=ρ¯+ε<1 _ := ρ+ <1, there exists a constant Cε>0C_ >0 such that dist2(Qk,1)≤Cεβεkdist2(Q0,1),∀k≥0.dist_2(Q_k,X_1)≤ C_ _ ^k\,dist_2(Q_0,X_1), ∀ k≥ 0. In particular, the convergence toward the affine set 1X_1, and hence toward the POS ∗X^*, is governed by the JSR ρ¯ ρ of the full restricted switching family and its convex-hull extension through the Lyapunov inequality. 2. For all k≥Kidk≥ K_id, there exists a policy πk∈Θ∗ _k∈ ^* such that Qk+1−Q∗=Aπk(Qk−Q∗)Q_k+1-Q^*=A_ _k(Q_k-Q^*). 3. For any ε∗>0 _*>0 such that β∗:=ρ¯∗+ε∗<1 _*:= ρ_*+ _*<1, there exists a constant C~ε∗>0 C_ _*>0 such that ‖zKid+ℓ‖2≤C~ε∗β∗ℓ‖zKid‖2,∀ℓ≥0.\|z_K_id+ \|_2≤ C_ _* _* \|z_K_id\|_2, ∀ ≥ 0. Thus, after finite-time identification of ∗X^*, the transverse component is governed by the JSR ρ¯∗ ρ_* of the restricted optimal family. 4. If, in addition, ρ¯∗<γ ρ_*<γ, then one may choose ε∗>0 _*>0 sufficiently small so that β∗=ρ¯∗+ε∗<γ _*= ρ_*+ _*<γ. In this case, there exists a constant Dε∗>0D_ _*>0 such that ‖QKid+ℓ−Q∗‖2≤Dε∗γℓ‖QKid−Q∗‖2,∀ℓ≥0.\|Q_K_id+ -Q^*\|_2≤ D_ _*γ \|Q_K_id-Q^*\|_2, ∀ ≥ 0. Proof. Let us write ek:=Qk−Q∗,αk:=1n⊤ek,zk:=⟂ek,n:=||||.e_k:=Q_k-Q^*, _k:= 1n1 e_k, z_k:= _ e_k, n:=| S|| A|. The global convergence estimate follows directly from Theorem 1 applied to the full restricted switching family A¯=A¯1,…,A¯M A=\ A_1,…, A_M\. Since 1⊂∗X_1 ^* and Corollary 2 gives finite-time entrance into ∗X^*, this proves the first claim and shows that the convergence toward the POS is governed by ρ¯ ρ. Next, by Corollary 2, for all k≥Kidk≥ K_id, Qk∈∗Q_k ^*. Hence, for each such k, the tie-broken greedy policy πk:=πQk _k:= _Q_k belongs to Θ∗ ^*. Therefore, Qk+1=R+γPΠπkQkQ_k+1=R+γ P _kQ_k. Since πk _k is optimal, it also satisfies R+γPΠπkQ∗=Q∗R+γ P _kQ^*=Q^*. Subtracting the two equations yields Qk+1−Q∗=Aπk(Qk−Q∗)Q_k+1-Q^*=A_ _k(Q_k-Q^*), where Aπk:=γPΠπkA_ _k:=γ P _k. This proves the second claim. Now, let us define ek:=Qk−Q∗e_k:=Q_k-Q^* and zk:=⟂ekz_k:= _ e_k. Then, for all k≥Kidk≥ K_id, zk+1=⟂ek+1=⟂Aπkek.z_k+1= _ e_k+1= _ A_ _ke_k. Since ek=⟂ek+(I−⟂)eke_k= _ e_k+(I- _ )e_k and (I−⟂)ek∈span()(I- _ )e_k (1), there exists a scalar ck∈ℝc_k such that (I−⟂)ek=ck.(I- _ )e_k=c_k1. Using Aπk=γA_ _k1= 1 and ⟂=0 _ 1=0, we obtain ⟂Aπk(I−⟂)ek=ck⟂Aπk=ckγ⟂=0. _ A_ _k(I- _ )e_k=c_k _ A_ _k1=c_kγ _ 1=0. Therefore, zk+1=⟂Aπk⟂ek=A¯πkzk,z_k+1= _ A_ _k _ e_k= A_ _kz_k, where A¯πk:=⟂Aπk⟂ A_ _k:= _ A_ _k _ . Thus, after time KidK_id, the projected error evolves according to the switching family A¯∗=A¯π:π∈Θ∗ A_*=\ A_π:π∈ ^*\. Since A¯∗⊂A¯ A_*⊂ A, monotonicity of the JSR yields ρ¯∗≤ρ¯ ρ_*≤ ρ. On the other hand, Lemma 11 gives ρ¯≤γ ρ≤γ. Hence, ρ¯∗≤ρ¯≤γ ρ_*≤ ρ≤γ. Fix any ε∗>0 _*>0 such that β∗:=ρ¯∗+ε∗<1 _*:= ρ_*+ _*<1. Applying Lemma 12 to the restricted optimal family A¯∗ A_*, there exists a common Lyapunov function for this family. Hence there exists a constant C~ε∗>0 C_ _*>0 such that ‖zKid+ℓ‖2≤C~ε∗β∗ℓ‖zKid‖2,∀ℓ≥0.\|z_K_id+ \|_2≤ C_ _* _* \|z_K_id\|_2, ∀ ≥ 0. This proves the third claim. It remains to control the component along 1. Write ek=αk+zk,αk:=1n⊤ek.e_k= _k1+z_k, _k:= 1n1 e_k. Then αk+1=1n⊤ek+1=1n⊤Aπkek=1n⊤Aπk(αk+zk). _k+1= 1n1 e_k+1= 1n1 A_ _ke_k= 1n1 A_ _k( _k1+z_k). Since Aπk=γA_ _k1= 1, we get αk+1=γαk+ηk _k+1=γ _k+ _k, where ηk:=1n⊤Aπkzk _k:= 1n1 A_ _kz_k. Define L∗:=maxπ∈Θ∗1n‖⊤Aπ‖2L_*:= _π∈ ^* 1n\|1 A_π\|_2. Then |ηk|≤L∗‖zk‖2| _k|≤ L_*\|z_k\|_2. Assume now that ρ¯∗<γ ρ_*<γ. Then we may choose ε∗>0 _*>0 sufficiently small so that β∗=ρ¯∗+ε∗<γ. _*= ρ_*+ _*<γ. Iterating the recursion for αk _k from KidK_id, we obtain |αKid+ℓ|≤γℓ|αKid|+L∗∑j=0ℓ−1γℓ−1−j‖zKid+j‖2.| _K_id+ |≤γ | _K_id|+L_* _j=0 -1γ -1-j\|z_K_id+j\|_2. Using the bound on zkz_k gives |αKid+ℓ|≤γℓ|αKid|+L∗C~ε∗∑j=0ℓ−1γℓ−1−jβ∗j‖zKid‖2.| _K_id+ |≤γ | _K_id|+L_* C_ _* _j=0 -1γ -1-j _*^j\|z_K_id\|_2. Since β∗<γ _*<γ, ∑j=0ℓ−1γℓ−1−jβ∗j=γℓ−β∗ℓγ−β∗≤γℓγ−β∗. _j=0 -1γ -1-j _*^j= γ - _* γ- _*≤ γ γ- _*. Hence, |αKid+ℓ|≤γℓ|αKid|+L∗C~ε∗γ−β∗γℓ‖zKid‖2.| _K_id+ |≤γ | _K_id|+ L_* C_ _*γ- _*γ \|z_K_id\|_2. Finally, since eKid+ℓ=αKid+ℓ+zKid+ℓ,e_K_id+ = _K_id+ 1+z_K_id+ , we have ‖eKid+ℓ‖2≤n|αKid+ℓ|+‖zKid+ℓ‖2.\|e_K_id+ \|_2≤ n\,| _K_id+ |+\|z_K_id+ \|_2. Combining the previous bounds and using β∗ℓ≤γℓ _* ≤γ , we conclude that there exists a constant Dε∗>0D_ _*>0 such that ‖QKid+ℓ−Q∗‖2=‖eKid+ℓ‖2≤Dε∗γℓ‖QKid−Q∗‖2,∀ℓ≥0.\|Q_K_id+ -Q^*\|_2=\|e_K_id+ \|_2≤ D_ _*γ \|Q_K_id-Q^*\|_2, ∀ ≥ 0. This completes the proof. ∎ Consequently, Q-VI exhibits a two-stage behavior: 1. the iterates approach 1X_1 exponentially at a rate governed by ρ¯ ρ, and hence identify the POS ∗X^* in finite time; 2. after identification, the transverse component evolves according to the smaller family A¯∗ A_* and decays at a rate governed by ρ¯∗ ρ_*, where ρ¯∗≤ρ¯ ρ_*≤ ρ; 3. if ρ¯∗<γ ρ_*<γ, then the post-identification transverse decay is strictly faster than the standard γ rate; 4. nevertheless, the full error may still be dominated by the standard γ rate because of the residual component along span()span(1). Theorem 2 shows that, after the finite-time identification index KidK_id, the transverse dynamics are governed by the restricted optimal family ¯∗ A_*, rather than by the full switching family ¯ A. In general, this post-identification behavior may still involve switching among multiple optimal policies when Θ∗ ^* contains more than one element. However, in the special case where the optimal policy is unique, this residual switching disappears entirely. The post-identification dynamics then reduce to a single linear system associated with π∗π^*, which yields a sharper and more explicit description of the asymptotic behavior. This special case is summarized in the following corollary. Corollary 3 (Unique optimal policy case). Suppose that the optimal policy is unique, namely, Θ∗=π∗ ^*=\π^*\. Under the assumptions of Theorem 2, we then have πQk=π∗,∀k≥Kid. _Q_k=π^*, ∀ k≥ K_id. Consequently, for all k≥Kidk≥ K_id, Qk+1−Q∗=Aπ∗(Qk−Q∗)Q_k+1-Q^*=A_π^*(Q_k-Q^*), and zk+1=A¯π∗zkz_k+1= A_π^*z_k, where A¯π∗:=⟂(γPΠπ∗)⟂ A_π^*:= _ (γ P ^π^*) _ . Moreover, ρ(A¯π∗)=γ|λ2(PΠπ∗)|.ρ( A_π^*)=γ| _2(P ^π^*)|. Hence, in the unique-optimal-policy case, the post-identification transverse dynamics are governed by a single linear system rather than a switching family. Proof. Since the optimal policy is unique, for each state s∈s∈ S the set Φ∗(s) ^*(s) is a singleton, namely, Φ∗(s)=π∗(s) ^*(s)=\π^*(s)\. By Corollary 2, we have Qk∈∗Q_k ^* for all k≥Kidk≥ K_id. Therefore, πQk(s)∈Φ∗(s)=π∗(s) _Q_k(s)∈ ^*(s)=\π^*(s)\ for all s∈s∈ S, which implies πQk=π∗ _Q_k=π^* for all k≥Kidk≥ K_id. The stated dynamics then follow immediately from Theorem 2, and the identity ρ(A¯π∗)=γ|λ2(PΠπ∗)|ρ( A_π^*)=γ| _2(P _π^*)| follows from Lemma 9. ∎ Corollary 3 shows that, once the POS is identified, the remaining dynamics no longer involve any switching when the optimal policy is unique. In this case, the post-identification phase is completely described by a single linear system associated with π∗π^*. Therefore, the transient geometric picture becomes particularly transparent: the iterates first approach 1X_1 and identify the optimal policy in finite time, and thereafter evolve according to a fixed linear map. Moreover, the transverse convergence rate is determined explicitly by ρ(A¯π∗)=γ|λ2(PΠπ∗)|ρ( A_π^*)=γ| _2(P _π^*)|, which provides a concrete spectral characterization of the fast mode after policy identification. This shows that, in the unique-optimal-policy case, the second stage of convergence is no longer governed by a switching family but by a single stable linear subsystem. Before presenting the main example, we first provide a simple demonstration for Q-VI that illustrates the geometric phenomenon established in this paper. In particular, this example is intended to make the convergence toward the affine set 1X_1, the finite-time entrance into the POS ∗X^*, and the resulting two-stage behavior visually transparent. Since Q-learning [24] can be viewed as a stochastic version of Q-VI, it is natural to ask whether a similar geometric phenomenon also appears in the tabular Q-learning setting. Motivated by this question, we next perform an analogous experiment for Q-learning on the same toy MDP. The experimental results suggest that the same qualitative behavior persists: even in the stochastic setting, the iterates are first drawn toward a neighborhood of 1X_1, and only afterward continue refining their convergence toward Q∗Q^*. VIII Examples In this subsection, we illustrate the geometric picture developed in the previous sections using a small discounted MDP with ||=3,||=2| S|=3,| A|=2 and γ=0.95γ=0.95. The transition probability matrices and the expected one-step rewards are chosen as P1=[0.70.20.10.20.60.20.10.30.6],P2=[0.20.50.30.40.30.30.30.30.4],R=[1.00.20.60.01.20.3],P_1= bmatrix0.7&0.2&0.1\\ 0.2&0.6&0.2\\ 0.1&0.3&0.6 bmatrix, P_2= bmatrix0.2&0.5&0.3\\ 0.4&0.3&0.3\\ 0.3&0.3&0.4 bmatrix, R= bmatrix1.0&0.2\\ 0.6&0.0\\ 1.2&0.3 bmatrix, respectively, where the (s,a)(s,a)-entry of R represents the expected reward at state s under action a, i.e. R(s,a)R(s,a). For this example, the unique optimal deterministic policy is π∗=(1,1,1),π^*=(1,1,1), and the corresponding optimal Q-function is Q∗=[18.222917.302617.619417.217218.494717.5430],Q^*= bmatrix18.2229&17.3026\\ 17.6194&17.2172\\ 18.4947&17.5430 bmatrix, where the (s,a)(s,a)-entry represents the optimal Q-function value at state s under action a, i.e. Q∗(s,a)Q^*(s,a). The corresponding minimum optimality gap is Δ:=mins∈sepΔ¯s,Δ¯s:=V∗(s)−maxa∉Φ∗(s)Q∗(s,a)≈0.4022. := _s∈ S_sep _s, _s:=V^*(s)- _a∉ ^*(s)Q^*(s,a)≈ 0.4022. We consider the affine space 1=Q∗+span()X_1=Q^*+span(1), and choose the tube radius δ=0.4Δ≈0.1609δ=0.4 ≈ 0.1609, which satisfies δ<Δ/2δ< /2. To compare the convergence to the optimal Q-function and the convergence to the affine set 1X_1, we plot the normalized quantities ‖Qk−Q∗‖∞‖Q0−Q∗‖∞anddist2(Qk,1)dist2(Q0,1). \|Q_k-Q^*\|_∞\|Q_0-Q^*\|_∞ dist_2(Q_k,X_1)dist_2(Q_0,X_1). As reference curves, we also include γkγ^k and (γ|λ2|)k(γ| _2|)^k, where |λ2|| _2| denotes the modulus of the second largest eigenvalue of the state-action transition matrix PΠπ∗P _π^* associated with the optimal policy. For this example, |λ2|≈0.5618| _2|≈ 0.5618 and γ|λ2|≈0.5337γ| _2|≈ 0.5337. To visualize the geometry in two dimensions, we consider the two-dimensional affine plane Q∗+span^,d^,Q^*+span\ 1, d\, where ^:=16(1,1,1,1,1,1)⊤∈ℝ6,d^:=12(1,−1,0,0,0,0)⊤∈ℝ6. 1:= 1 6(1,1,1,1,1,1) ∈R^6, d:= 1 2(1,-1,0,0,0,0) ∈R^6. Here, 1 is the normalized all-ones direction, which is tangent to 1X_1, while d d is a transverse direction that perturbs only the first state-action pair. For any Q, write the coordinates of Q−Q∗Q-Q^* on this plane as u(Q):=⟨Q−Q∗,^⟩,v(Q):=⟨Q−Q∗,d^⟩.u(Q):= Q-Q^*, 1 , v(Q):= Q-Q^*, d . For the single-trajectory experiment, the initial condition is chosen on this tilted plane as follows: Q0=[19.549516.629217.946017.543818.821317.8696].Q_0= bmatrix19.5495&16.6292\\ 17.9460&17.5438\\ 18.8213&17.8696 bmatrix. Starting from this Q0Q_0, we run Q-VI for 5050 iterations. Figure 1 shows the normalized decay of ‖Qk−Q∗‖∞\|Q_k-Q^*\|_∞ and dist2(Qk,1)dist_2(Q_k,X_1). The figure illustrates that the distance to 1X_1 decreases more rapidly than the full Q-function error in the transient regime, which is consistent with the theoretical picture developed in this paper. Figure 2 shows the orthogonal projection of the full Q-VI trajectory onto the tilted plane. The dashed line represents the slice of 1X_1 and the shaded strip is the slice of δ T_δ. The projected trajectory starts from the initial point, enters the strip in finite time, and then converges to the origin, which corresponds to Qk→Q∗Q_k→ Q^*. To further illustrate the global geometry, we also consider 1212 initial conditions placed uniformly on the circle of radius 22 in the tilted plane. For each such initial condition, we run Q-VI for 5050 iterations and project the resulting trajectory onto the same tilted plane. Figure 3 displays these projected trajectories together with the slice of 1X_1, the slice of δ T_δ, and the initial circle. This figure provides a more global view of how trajectories from different directions are rapidly drawn toward the affine set 1X_1 before ultimately converging to Q∗Q^*. Figure 1: Normalized comparison of ‖Qk−Q∗‖∞\|Q_k-Q^*\|_∞ and dist2(Qk,1)dist_2(Q_k,X_1) for the toy MDP. The dashed curves indicate the reference rates γkγ^k and (γ|λ2|)k(γ| _2|)^k. The figure illustrates that the iterate approaches the affine set 1X_1 faster than it approaches the optimal Q-function Q∗Q^*. Figure 2: Orthogonal projection of a single full Q-VI trajectory onto the tilted plane. The dashed line is the slice of 1X_1 and the shaded strip is the slice of the tube δ T_δ. The projected trajectory starts from the initial point, enters the strip, and then converges to the origin. Figure 3: Orthogonal projections of 1212 full Q-VI trajectories onto the tilted plane, where the initial conditions are chosen uniformly on a circle of radius 22 in the plane. The dashed line is the slice of 1X_1, the shaded strip is the slice of δ T_δ, and the dotted curve is the initial circle. The figure gives a global geometric view of how trajectories are first attracted toward 1X_1 and then converge to Q∗Q^*. We next present a tabular Q-learning example on the same toy MDP used in the preceding Q-VI example. Since the underlying discounted MDP, the optimal policy π∗π^*, the optimal Q-function Q∗Q^*, the affine set 1X_1, and the tube radius δ are the same as those introduced in the previous example, we omit their repeated description here. We consider the standard asynchronous tabular Q-learning update. In the simulation, the action is sampled from the uniform behavior policy μ(a∣s)=1||μ(a s)= 1| A| for s∈s∈ S and a∈a∈ A, and the step size is chosen as αt=0.351+0.01t _t= 0.351+0.01\,t. To visualize the geometry, we consider the two-dimensional affine plane identical to the previous Q-VI case. As before, we choose 1212 initial conditions uniformly on the boundary of a circle of radius r=2r=2 in the tilted plane. Figure 4 shows the projected sample paths corresponding to these 1212 initial conditions, together with the line q=pq=p, which is the projection of 1X_1, the strip corresponding to the projected tube δ T_δ, and the boundary of the initial circle. Since Q-learning is stochastic, the trajectories are not monotone and exhibit path-dependent fluctuations. Nevertheless, a clear common trend can be observed: from a variety of initial directions, the trajectories are first drawn toward the line q=pq=p, enter the projected tube, and then continue to move toward the origin. This supports the same geometric interpretation as in the Q-VI example: even in the stochastic tabular Q-learning setting, the affine set 1X_1 acts as a transient attracting set before the iterates refine their convergence toward Q∗Q^*. Compared with the Q-VI example, the present figure displays a family of stochastic sample paths rather than a single deterministic trajectory. This makes the same geometric mechanism visually more apparent: although the noise causes trajectory-dependent oscillations, the iterates tend to approach the neighborhood of 1X_1 relatively quickly and only afterward progress toward the optimal Q-function Q∗Q^*. Figure 4: Two-dimensional projection of tabular Q-learning trajectories onto the tilted plane Q∗+span^,d^Q^*+span\ 1, d\, displayed in the rotated coordinates p=(u−v)/2p=(u-v)/ 2 and q=(u+v)/2q=(u+v)/ 2. The dashed line q=pq=p is the projection of 1X_1, and the shaded strip is the projection of the tube δ T_δ, namely |q−p|≤2δ|q-p|≤ 2\,δ. The dotted circle indicates the boundary of the common initial set in the (u,v)(u,v)-plane. Starting from 1212 different initial points on this circle, the stochastic Q-learning trajectories tend to enter the strip and then move toward the origin, which corresponds to Q∗Q^*. IX Conclusion In this paper, we revisited discounted Q-VI from a switching-system perspective and uncovered its underlying geometric structure. While classical analysis guarantees asymptotic convergence to Q∗Q^*, our results show that Q-VI identifies the optimal action class in finite time. Moreover, we established that the iterates converge rapidly toward a structured subset 1X_1 at a rate governed by a restricted JSR, which can be faster than the standard γ rate when this restricted JSR is strictly smaller than γ. The final convergence to Q∗Q^* may still be dominated by the residual all-ones component, which decays at the standard γ rate. This reveals a two-stage behavior that is not captured by conventional contraction-based arguments. Our analysis provides a refined understanding of the transient dynamics of Q-VI and highlights the importance of geometric viewpoints in reinforcement learning. References [1] R. Bellman, “Dynamic programming,” science, vol. 153, no. 3731, p. 34–37, 1966. [2] D. P. Bertsekas and J. N. Tsitsiklis, Neuro-dynamic programming. Athena Scientific Belmont, MA, 1996. [3] D. P. Bertsekas, “Dynamic programming and optimal control 4th edition, volume i,” Athena Scientific, 2015. [4] M. L. Puterman, Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014. [5] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. MIT Press, 1998. [6] D. Liberzon, Switching in systems and control. Springer Science & Business Media, 2003. [7] D. Lee and N. He, “A unified switching system perspective and convergence analysis of q-learning algorithms,” in 34th Conference on Neural Information Processing Systems, NeurIPS 2020, 2020. [8] D. Lee, J. Hu, and N. He, “A discrete-time switching system analysis of q-learning,” SIAM Journal on Control and Optimization, vol. 61, no. 3, p. 1861–1880, 2023. [9] D. Lee, “Final iteration convergence bound of q-learning: Switching system approach,” IEEE Transactions on Automatic Control, vol. 69, no. 7, p. 4765–4772, 2024. [10] H.-D. Lim and D. Lee, “Finite-time analysis of asynchronous q-learning under diminishing step-size from control-theoretic view,” IEEE Access, vol. 12, p. 149 916–149 939, 2024. [11] D. Lee, “On some geometric behavior of value iteration on the orthant: Switching system perspective,” in 2023 62nd IEEE Conference on Decision and Control (CDC), 2023, p. 4911–4916. [12] X. Guo and B. Hu, “Convex programs and lyapunov functions for reinforcement learning: A unified perspective on the analysis of value-based methods,” in 2022 American Control Conference (ACC), 2022, p. 3317–3322. [13] R. Iervolino, M. Tipaldi, and A. Forootani, “A lyapunov-based version of the value iteration algorithm formulated as a discrete-time switched affine system,” International Journal of Control, vol. 96, no. 3, p. 577–592, 2023. [14] M. Tipaldi, R. Iervolino, P. R. Massenio, and D. Naso, “A switching control strategy for policy selection in stochastic dynamic programming problems,” Automatica, vol. 171, p. 111884, 2025. [15] R. Dadashi, A. A. Taiga, N. Le Roux, D. Schuurmans, and M. G. Bellemare, “The value function polytope in reinforcement learning,” in International Conference on Machine Learning, 2019, p. 1486–1495. [16] Y. Wu and J. A. De Loera, “Geometric policy iteration for markov decision processes,” in Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022, p. 2070–2078. [17] A. Mustafin, A. Olshevsky, and I. C. Paschalidis, “On value iteration convergence in connected mdps,” arXiv preprint arXiv:2406.09592, 2024. [18] A. Mustafin, S. Colla, A. Olshevsky, and I. C. Paschalidis, “Analysis of value iteration through absolute probability sequences,” arXiv preprint arXiv:2502.03244, 2025. [19] A. Mustafin, A. Pakharev, A. Olshevsky, and I. C. Paschalidis, “Geometric re-analysis of classical mdp solving algorithms,” arXiv preprint arXiv:2503.04203, 2025. [20] M. Gargiani, A. Zanelli, D. Liao-McPherson, T. H. Summers, and J. Lygeros, “Dynamic programming through the lens of semismooth newton-type methods,” IEEE Control Systems Letters, vol. 6, p. 2996–3001, 2022. [21] G.-C. Rota and G. Strang, “A note on the joint spectral radius,” Indag. Math, vol. 22, no. 4, p. 379–381, 1960. [22] J. N. Tsitsiklis and V. D. Blondel, “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 Systems, vol. 10, no. 1, p. 31–40, 1997. [23] Z. Chen, S. Zhang, Z. Zhang, S. U. Haque, and S. T. Maguluri, “A non-asymptotic theory of seminorm lyapunov stability: From deterministic to stochastic iterative algorithms,” arXiv preprint arXiv:2502.14208, 2025. [24] C. J. Watkins and P. Dayan, “Q-learning,” Machine learning, vol. 8, no. 3, p. 279–292, 1992.