arXiv:2605.10811v1 [math.OC] 11 May 2026
Switching-Geometry Analysis of Deflated Q-Value Iteration Donghwan Lee Department of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) Daejeon 34141, South Korea [email protected]
Abstract This paper develops a joint spectral radius (JSR) framework for analyzing rank-one deflated Q-value iteration (Q-VI) in discounted Markov decision process control. Focusing on an all-ones residual correction, we interpret the resulting algorithm through the geometry of switching systems and, to the best of our knowledge, give the first JSR-based convergence analysis of deflated Q-VI for policy optimization problems. Our analysis reveals that the standard Q-VI switching system model has JSR exactly the discount factor γ ∈ (0, 1), since all admissible subsystems share the all-ones vector as an invariant direction. By passing to the quotient space that removes this direction, we obtain a projected switching system model whose JSR governs the relevant error dynamics and may be strictly smaller than γ. Therefore, the deflated Q-VI admits a potentially sharper convergence-rate characterization than the ambient-space γ-bound. Finally, we prove that the correction is equivalent to a scalar recentering of standard Q-VI. Hence, the projected trajectory, and therefore the greedy-policy sequence, is unchanged relative to standard Q-VI initialized from the same point. The benefit of deflation is not a change in the induced decision-making problem, but a more precise JSR-based description of the convergence geometry after the redundant all-ones component is removed.
1
Introduction
Q-value iteration (Q-VI) is a foundational dynamic-programming algorithm for finite discounted Markov decision processes (MDPs) [3, 16]. Its standard deterministic convergence analysis relies on the fact that the Bellman optimality operator is a γ-contraction in the infinity norm [3, 16]. Consequently, Q-VI converges to the unique optimal action-value function Q⋆ at the classical exponential rate γ ∈ (0, 1). Although this contraction argument is fundamental, it is geometrically conservative. A switching system viewpoint [10] makes this conservatism explicit. The linear switching family associated with standard Q-VI [7, 13, 14, 18] has joint spectral radius (JSR) [4, 8, 17, 19] exactly equal to γ, because every subsystem preserves the all-ones direction and acts on it with eigenvalue γ. After quotienting out this invariant direction, the transverse dynamics are governed by a projected switching family with the so-called projected JSR ρ̄, which can be strictly smaller than the ambient contraction rate γ. Nevertheless, standard Q-VI can still converge to Q⋆ no faster than γ in the worst case, since a pure all-ones error evolves exactly as γ k 1. In this paper, we study the (rank-one) deflated Q-VI update Qk+1 = F (Qk ) +
γ d⊤ F (Qk ) − Qk 1, 1−γ
1
where F is the Bellman optimality operator, Qk is the current estimate of Q⋆ , and d is either the uniform distribution or a fixed state-action distribution. Closely related deflated value-iteration schemes were proposed in the classical work of [1] and in the recent rank-one modified value-iteration framework of [9]. The main contribution of the present paper is to provide, to the best of our knowledge, the first rigorous JSR-based convergence theory for deflated Q-VI in discounted MDP control problems. Our analysis is built on an exact switching system formulation of the deflated Q-VI recursion [7, 13, 14, 18] combined with JSR theory [4, 8, 17, 19]. Beyond proving convergence, this framework clarifies the precise geometric mechanism behind the improved rate. Standard Q-VI error can be decomposed into a scalar coordinate in the all-ones direction 1 and a quotient, or transverse, component obtained after identifying Q-functions that differ only by a uniform shift c1. The scalar all-ones coordinate is the reason the ambient switching family has JSR exactly γ: every subsystem maps this direction to itself with eigenvalue γ. The rank-one residual correction cancels the autonomous evolution of this scalar coordinate. At the same time, it does not change the quotient trajectory, because the deflated iterate remains equal to the corresponding standard Q-VI iterate plus a scalar multiple of 1. Since such a uniform shift does not change statewise action comparisons, the same greedy-policy sequence is preserved. In this sense, the proposed analysis gives a sharper geometric understanding of deflated Q-VI than the classical norm-contraction argument. The main contributions are summarized as follows. (1) We derive exact switching-system error representations for both standard Q-VI and the proposed deflated Q-VI. These representations separate the dynamics along the all-ones direction 1 from the transverse, policy-dependent dynamics on the quotient space. (2) We prove that the rank-one residual correction in Q-VI eliminates the autonomous scalar dynamics in the all-ones direction. As a result, the switching system governing deflated Q-VI has JSR equal to the projected JSR ρ̄. Hence, the relevant convergence rate of the deflated Q-VI dynamics is characterized by ρ̄, which is no larger than γ and may be strictly smaller. We also show that the uniform residual average can be replaced by any fixed state-action distributional average: for every fixed admissible vector d, the same quotient JSR is preserved through an oblique-projection similarity. This fixed-d result is distinct from the time-varying distribution estimates used in adaptive rank-one or Q-learning schemes [9]. (3) We identify the structural meaning of the rank-one correction. The deflated Q-VI iterate differs from the corresponding standard Q-VI iterate only by a scalar multiple of 1. Because the all-ones direction does not affect the policy ordering of greedy actions, the projected trajectory is unchanged, and the greedy-policy sequence is preserved relative to standard Q-VI initialized from the same point. Thus, the rank-one correction should be interpreted as accelerating Q-function error convergence through re-centering, rather than as accelerating policy identification; see Figure 1.
2
Related Work
Rank-one residual corrections for value iteration were studied in [1] for linear fixed-point iterations. In the discounted Markovian setting, the all-ones residual correction has the same basic recentering structure as the deflated Q-VI considered in this paper. More recently, the rank-one modified value iteration (R1-VI) framework in [9] used rank-one approximations of transition dynamics to develop planning and learning algorithms, including Q-function variants, with convergence guarantees 2
All-Ones Coordinate a1
Standard Q-VI
Rank-One Residual Shift
Deflated Q-VI Transverse Error z = Π⊥ (Q − Q⋆ )
Q⋆
Figure 1: Geometric mechanism of the deflated Q-VI analysis, following the projected Q-VI geometry of Lee [10]. Standard Q-VI may retain a slowly decaying all-ones component. The residual correction preserves the projected trajectory and re-centers the iterate in the all-ones direction, so the full switched-family rate is governed by the projected rate ρ̄. comparable to those of standard VI and Q-learning. These works provide important algorithmic and approximation perspectives on rank-one corrections. Related deflation ideas have also appeared in spectral modifications of value iteration. For example, deflated Dynamics value iteration [12] removes dominant eigenspaces of a transition matrix and obtains convergence rates determined by the remaining spectral components. The closest geometric predecessor to the present work is [10], which analyzes standard Q-VI through projected switching dynamics and shows that the corresponding rate governs the action-ordering-relevant component, and therefore policy identification. The present paper is distinct from these works in both scope and analysis. We analyze the exact switching-system error dynamics of deflated Q-VI in the policy optimization setting. To the best of our knowledge, this provides the first rigorous JSR-based convergence proof for deflated Q-VI in discounted MDP control. The key conclusion is that the JSR of the switching system model of deflated Q-VI is exactly the projected JSR ρ̄, which can be strictly smaller than the classical contraction rate γ. At the same time, the deflated Q-VI iterate differs from standard Q-VI only by an all-ones shift, so the projected trajectory and greedy-policy sequence are unchanged.
3
Preliminaries
3.1
Notation
For a finite set Y, its cardinality is denoted by |Y|. The symbols R, Rn , and Rn×m denote the real numbers, the n-dimensional Euclidean space, and the set of n × m real matrices, respectively. All vectors are column vectors. For a matrix A, A⊤ denotes its transpose, and ker(A) := {x : Ax = 0} denotes its nullspace. The identity matrix is denoted by I, and the vector with all entries equal to one is denoted by 1. For a linear map B and a subspace W such that B(W ) ⊆ W , the notation B|W denotes the restriction of to W , namely B|W : W → W . For m ≥ 1, the probability simplex PB m m n n is ∆m := {p ∈ R : pi ≥ 0, i=1 pi = 1}. For a convex set Y ⊂ R and a vector x ∈ R , define |S||A| dist2 (x, Y) := inf y∈Y ∥x − y∥2 and dist∞ (x, Y) := inf y∈Y ∥x − y∥∞ . For x ∈ R , its empirical
3
mean and its orthogonal projection onto span(1)⊥ are defined by 1 1 ⊤ ⊤ x̄ := 1 x, Π⊥ x := I − 11 x. |S||A| |S||A| The same symbol is used for the projection matrix Π⊥ := I −
1 11⊤ , |S||A|
which satisfies Π⊥ 1 = 0.
(1)
The set-valued maximizer is denoted by Arg max, while arg max denotes a fixed tie-broken singlevalued maximizer.
3.2
Finite discounted Markov decision process
Let us consider a finite discounted Markov decision process (MDP) [2, 16] with finite state space S = {1, . . . , |S|}, finite action space A = {1, . . . , |A|}, transition probability P (s′ | s, a), reward r(s, a, s′ ), and P discount factor γ ∈ (0, 1). The expected reward associated with a state-action pair is R(s, a) := s′ ∈S P (s′ | s, a)r(s, a, s′ ), for (s, a) ∈ S × A. A deterministic stationary policy is a map π : S → A. More generally, a stochastic stationary policy is a map µ : S → ∆|A| , where µ(a | s) denotes the probability of selecting action a in state s. For a deterministic stationary policy π, the associated action-value function is " ∞ # X Qπ (s, a) := E γ t r(st , at , st+1 ) s0 = s, a0 = a, at = π(st ) ∀t ≥ 1 , t=0
where the initial action is fixed to be a, and subsequent actions are chosen according to π. The optimal Q-function and the optimal value function are defined by Q⋆ (s, a) := sup Qπ (s, a),
V ⋆ (s) := max Q⋆ (s, a). a∈A
π
Equivalently, Q⋆ is the unique fixed point of the Bellman optimality equation X Q⋆ (s, a) = R(s, a) + γ P (s′ | s, a) max Q⋆ (s′ , a′ ). ′ s′ ∈S
a ∈A
For each state s, the set of optimal greedy actions is denoted by Φ⋆ (s) := Arg maxa∈A Q⋆ (s, a). The set of all deterministic policies is denoted by Θ := {π : S → A}. Throughout the paper, we use a fixed tie-breaking rule and denote by πQ (s) := arg maxa∈A Q(s, a),
s ∈ S,
the tie-broken greedy policy induced by Q. Thus πQ ∈ Θ is well-defined for every Q.
4
3.3
Q-value iteration
The Bellman optimality operator F : R|S||A| → R|S||A| is defined componentwise by X (F Q)(s, a) := R(s, a) + γ P (s′ | s, a) max Q(s′ , a′ ) ∀(s, a) ∈ S × A. ′ a ∈A
s′ ∈S
The standard Q-value iteration (Q-VI) is the deterministic recursion k ∈ {0, 1, 2, . . .}.
Qk+1 = F (Qk ),
The Bellman operator is a γ-contraction in the infinity norm [3, 16]: e ∈ R|S||A| . ∀Q, Q
e ∞ ≤ γ∥Q − Q∥ e ∞, ∥F (Q) − F (Q)∥
Therefore, ∥Qk − Q⋆ ∥∞ ≤ γ k ∥Q0 − Q⋆ ∥∞ . The Bellman operator also satisfies the shift identity F (Q + c1) = F (Q) + γc1,
∀Q,
∀c ∈ R.
(2)
This identity is the source of the all-ones mode, 1, in standard Q-VI. If the current iterate is shifted by a uniform amount, c1, then the Bellman backup maps this shift to the uniform shift γc1. In particular, if Q = Q⋆ + c1, then F (Q) − Q⋆ = γc1. Consequently, a pure error of the form c1 is mapped to γc1, independently of rewards, transition probabilities, or the active greedy policy. In the switching system representation below, this 1 becomes a common invariant direction of every subsystem of the switching system. Since this direction, 1, changes all state-action values by the same amount, it does not affect greedy action preferences, but it still appears in the full Q-function error and forces the standard worst-case full-error rate to include the factor γ. The next section rewrites Q-VI as a switching system. This form makes it possible to separate the all-ones direction, 1, from the policy-relevant transverse directions. To keep the main exposition focused and to make the logical flow easier to follow, all proofs are deferred to the appendix.
4
Switching system model of Q-VI
This section rewrites Q-VI as an affine switching system [7, 13, 14, 18]. The affine form keeps the reward and greedy policy dependent offset explicit, while the homogeneous linear part is the object whose joint spectral radius determines the worst-case switched rate.
4.1
Switching systems and joint spectral radius
An affine switching system has the form [7, 13, 14, 18] xk+1 = Aσk xk + bσk ,
σk ∈ M := {1, . . . , M },
k ∈ {0, 1, 2, . . .},
where σk is a switching signal, Aσk is the active subsystem selected from the switching family H := {A1 , A2 , . . . , AM }, and bσk is a mode-dependent affine term. When bσk = 0, the homogeneous part reduces to a switched linear system, k ∈ {0, 1, 2, . . .}.
xk+1 = Aσk xk ,
The worst-case exponential rate of the switched linear family H is characterized by the joint spectral radius (JSR) [4, 8, 17, 19], defined as follows. 5
Definition 1 (Joint spectral radius). For a bounded set of matrices H ⊂ Rm×m , its joint spectral radius is ρ(H) := lim sup ∥Ak · · · A1 ∥1/k , k→∞ A1 ,...,Ak ∈H
where ∥ · ∥ denotes any fixed submultiplicative matrix norm. The value is independent of the chosen submultiplicative norm [8, 17]. When H is finite, the supremum for each fixed product length is a maximum over products generated by matrices in H. Thus, for fixed k, one may write maxA1 ,...,Ak ∈H instead of supA1 ,...,Ak ∈H . For a finite family H, the notation ρ(co(H)) means the JSR computed when each factor in a product is allowed to be any convex combination of matrices in H. The next three lemmas collect standard JSR facts used throughout the switching analysis. Lemma 1 (Convexification invariance of the JSR [8, Prop. 1.8]). For every finite matrix family H, the following identity holds: ρ(co(H)) = ρ(H). This result appears in [8, Prop. 1.8]. Lemma 2 (Uniform exponential product bound). Let ∥ · ∥ be any fixed submultiplicative matrix norm. If ρ(H) < 1, then every switched product is uniformly exponentially stable in that norm: for every ε ∈ (0, 1 − ρ(H)), with βε := ρ(H) + ε, there exists Cβε > 0, depending on βε and on the chosen norm, such that for every k ≥ 0 and every switching sequence σ0 , . . . , σk−1 ∈ M with Aj := Aσj ∈ H,
j = 0, . . . , k − 1,
one has ∥Ak−1 · · · A0 ∥ ≤ Cβε βεk , where the product is interpreted as the identity matrix I when k = 0. The following lemma is given in [5, Eq. (34)]. Lemma 3 (Block upper-triangular JSR [5, Eq. (34)]). Let B i Ci M := :i∈I 0 Di be a bounded family of block upper-triangular matrices. Let B := {Bi : i ∈ I} and D := {Di : i ∈ I}. Then ρ(M) = max{ρ(B), ρ(D)}. The preceding lemmas provide the technical JSR toolkit. The next subsection returns to the Q-VI model and writes its Bellman update in vectorized switched-system form.
6
4.2
Vectorized representation
Each Q-function is identified with a vector Q ∈ R|S||A| whose entries enumerate Q(s, a). The vectorized state-action transition notation, the use of stochastic policies to represent the Bellman maximization error, and the projected switching viewpoint used in this subsection are adapted from [11] and [10]. We use the compact notation P1 R(·, 1) .. |S| |A| R := , P := ... ∈ R(|S| |A|)×|S| , ∈R . P|A| R(·, |A|) where Pa = P (· | ·, a) ∈ R|S|×|S| , a ∈ A. For any stochastic policy µ : S → ∆|A| , define µ(1)⊤ ⊗ e⊤ 1 µ(2)⊤ ⊗ e⊤ 2 µ Π := ∈ R|S|×(|S| |A|) . .. .
µ(|S|)⊤ ⊗ e⊤ |S|
Then P Πµ ∈ R(|S| |A|)×(|S| |A|) is the state-action transition matrix under µ. For a deterministic policy π ∈ Θ, the same notation Ππ is used by identifying π(s) with its one-hot encoding for each s ∈ S. Thus Ππ is obtained by using the one-hot vector corresponding to π(s) in each row. For Q ∈ R|S||A| , let us define ΠQ := ΠπQ , where πQ is the tie-broken greedy policy induced by Q πQ (s) := arg maxa∈A Q(s, a),
s ∈ S.
With this notation, the Bellman operator can be written as F (Q) = R + γP ΠQ Q.
4.3
Affine switching-system representation
For each deterministic policy π ∈ Θ, define the matrix Aπ := γP Ππ ∈ R|S||A|×|S||A| . Then Q-VI can be written as the affine switching system Qk+1 = R + AπQk Qk ,
k ∈ {0, 1, 2, . . .},
where the affine term is the reward vector R, and the active subsystem is selected by the tie-broken greedy policy of the current iterate. In error coordinates ek := Qk − Q⋆ , the same recursion becomes ek+1 = AπQk ek + γP (ΠπQk − ΠπQ⋆ )Q⋆ ,
k ∈ {0, 1, 2, . . .}.
where πQ⋆ is any tie-broken greedy policy at Q⋆ . The linear part of the full deterministic switching family is H := {Aπ : π ∈ Θ}. The following proposition establishes the exact JSR of this full linear family. 7
Proposition 1 (Full Q-VI switching JSR). The deterministic switching family H = {Aπ : π ∈ Θ} satisfies ρ(H) = γ. Standard Q-VI contains an unavoidable all-ones mode with eigenvalue γ. This observation explains why the usual full-error convergence bound can be conservative for policy identification and motivates the projected representation and residual recentering studied below.
5
Exact switching system
This section gives the exact stochastic-policy switching representation of the Bellman optimality error dynamics. Let Mst := {µ : S → ∆|A| } be the set of stochastic stationary policies. For a stochastic policy µ ∈ Mst , define the matrix Aµ := γP Πµ , which satisfies ∀µ ∈ Mst .
Aµ 1 = γ1,
(3)
This identity follows directly from the stochasticity of the policy and the transition kernel. The matrices Aµ will be the subsystems of the stochastic-policy switching representation introduced below. Thus, Equation (3) implies that the all-ones direction is a common invariant direction of every stochastic-policy subsystem, with eigenvalue γ. The following representation uses the stochastic-policy linearization of the Bellman max that appears in [11] and [10, Lemma 5]. The broader viewpoint of analyzing value iteration through affine or switching dynamical systems is also close to the first-order approach of [6]. Lemma 4 (Exact stochastic-policy error representation). For every Q ∈ R|S||A| , there exists a stochastic policy µQ : S → ∆|A| such that F (Q) − Q⋆ = AµQ (Q − Q⋆ ). Consequently, with e := Q − Q⋆ , F (Q) − Q = (AµQ − I)e. In particular, the statement applies to standard Q-VI iterates and to the deflated Q-VI iterates studied below. For standard Q-VI, let Qk+1 = F (Qk ), ek := Qk − Q⋆ , and let µk := µQk be a stochastic policy supplied by Lemma 4. Then, Lemma 4 implies that standard Q-VI admits the homogeneous stochastic-policy switching system representation ek+1 = Aµk ek ,
Aµk ∈ Hst := {Aµ : µ : S → ∆|A| },
k ∈ {0, 1, 2, . . .}.
(4)
Equivalently, Qk+1 = Q⋆ + Aµk (Qk − Q⋆ ). The switching signal is selected by the Bellman maxlinearization at the current iterate; that is, the realized nonlinear trajectory uses µk = µQk . Thus Equation (4) is an exact trajectory-wise representation, while Hst is the associated enlarged stochasticpolicy family used for switched-family rate bounds. Its deterministic subfamily, namely the subset of Hst corresponding to all deterministic policies, is H = {Aπ : π ∈ Θ}. 8
6
Projected switching system for standard Q-VI
In this section, we introduce the projected switching system associated with the Q-VI error dynamics. Starting from the switching system representation developed in the previous section, we project the dynamics onto the zero-sum transverse subspace span(1)⊥ = {x ∈ R|S||A| : 1⊤ x = 0}. This projection removes the all-ones component and isolates the transverse dynamics. The resulting projected switching system captures the part of the Q-function error that is relevant to greedy action preferences, and it will play a central role in interpreting the convergence behavior of deflated Q-VI. The reason for focusing on span(1)⊥ is geometric. Adding a scalar multiple c1 to a Q-function shifts all state-action values by the same constant. Therefore, for each fixed state, all action values are shifted equally, and neither the statewise action ordering nor the tie-broken greedy action is changed. Consequently, the component of the error ek along the all-ones direction affects only the absolute numerical level of the Q-function, but not the policy selected from it. Therefore, the action-ordering-relevant part of the error is the residual component obtained after removing the uniform all-ones shift. Equivalently, the projected error on span(1)⊥ represents the transverse part of the dynamics that can influence greedy decisions. This viewpoint provides the geometric foundation for the JSR-based convergence analysis of deflated Q-VI developed below. To track this action-ordering-relevant part, define the projected subsystem Āµ := Π⊥ Aµ Π⊥ . The projection before Aµ chooses the zero-mean representative of the current error, and the projection after Aµ removes any new uniform shift generated by the subsystem. Therefore, Āµ keeps exactly the transverse dynamics that matter for greedy action comparisons and discards the uninformative all-ones coordinate. Formally, the associated projected switching system is zk ∈ span(1)⊥ ,
k ∈ {0, 1, 2, . . .}. (5) Every element of H̄st is regarded as a linear map on span(1)⊥ . The corresponding projected family with policies restricted to deterministic policies is zk+1 = Āµk zk ,
Āµk ∈ H̄st := {Āµ : µ : S → ∆|A| },
H̄ := {Āπ : π ∈ Θ}. Definition 2 (Projected joint spectral radius). The projected JSR of the deterministic projected family H̄ is 1/k ρ̄ := ρ(H̄) := lim max Āπk−1 · · · Āπ0 . k→∞ π0 ,...,πk−1 ∈Θ
Equivalently, ρ̄ is the worst-case exponential rate of products of the projected matrices. Lemma 5 (Empirical orthogonal error decomposition). For any error vector ek ∈ R|S||A| , define zk and ak as 1 1⊤ ek . (6) zk := Π⊥ ek , ak := |S||A| Then zk ∈ span(1)⊥ , and ek = ak 1 + zk = ak 1 + Π⊥ ek . Moreover, this decomposition is unique: if ek = α1 + w with w ∈ span(1)⊥ , then α = ak and w = zk . 9
In the above lemma, zk is the transverse component of the error and is relevant to action orderings. The scalar ak measures the magnitude of the uniform all-ones component. Therefore, the decomposition in (6) separates the error into its policy-relevant projected part zk and its policy-irrelevant recentering part ak 1. Lemma 6 (Projected error recursion for standard Q-VI). The standard Q-VI recursion satisfies k ∈ {0, 1, 2, . . .}.
zk+1 = Āµk zk ,
The next lemma gives the standard JSR bound for the projected switching system. This bound identifies the transverse rate that the deflated Q-VI update will later inherit as its associated switched-family JSR. Lemma 7 (Projected JSR bound [10]). The projected JSR satisfies ρ̄ ≤ γ. This result follows from the projected-product argument in [10, Lemma 8]. The inequality can be strict when the state-action dynamics mix uniformly in directions transverse to span(1). This projected representation isolates the faster transverse dynamics from the slower all-ones mode. Before introducing the deflated Q-VI update, we present the matching sharpness of this slow all-ones mode for standard Q-VI. Proposition 2 (Sharpness of the classical rate for standard Q-VI). For standard Q-VI, no uniform global convergence estimate to Q⋆ can have a rate smaller than γ. In particular, if Q0 = Q⋆ + c1,
c ̸= 0,
Qk − Q⋆ = γ k c1,
∀k ≥ 0.
then standard Q-VI satisfies
7
Deflated Q-VI
Let us first define the Bellman residual and its empirical mean by rk := F (Qk ) − Qk ,
r̄k :=
1 1⊤ rk . |S||A|
The deflated Q-VI update is Qk+1 = F (Qk ) +
γ r̄k 1, 1−γ
k ∈ {0, 1, 2, . . .}.
(7)
Equivalently, γ Qk+1 = F (Qk ) + 1−γ
1 ⊤ 1 (F (Qk ) − Qk ) 1. |S||A|
This update can be viewed as the all-ones version of the classical rank-one residual correction of Bertsekas [1]. In the fixed-policy discounted linear case, that correction chooses a scalar residual shift along a prescribed direction; when the direction is the all-ones vector, the shift has exactly the same form as Equation (7). Thus, the present update is the Q-VI analogue of a classical rank-one recentering step. 10
The same formula is also closely related to R1-VI of Kolarijani et al. [9]. In their notation, dk is the averaging distribution, or residual-weighting vector, used at iteration k, and ⟨dk , x⟩ = d⊤ k x. In the notation of the present paper, the Q-function Bellman optimality operator is F . The analogous Q-function residual correction can therefore be written as Qk+1 = F (Qk ) +
γ ⟨dk , F (Qk ) − Qk ⟩1. 1−γ
The uniform update in Equation (7) corresponds to fixing the averaging vector to (|S||A|)−1 1, while Section 10 allows an arbitrary fixed state-action distribution. The fixed-d analysis should be distinguished from the adaptive dk choices used in R1-VI/R1-QL [9]. Algorithm 1 Deflated Q-VI 1: Initialize Q0 ∈ R|S||A| . 2: for k = 0, 1, 2, . . . do
Compute the Bellman residual rk = F (Qk ) − Qk . 1 Compute its empirical mean r̄k = |S||A| 1⊤ rk . γ r̄k 1. 5: Update Qk+1 = F (Qk ) + 1−γ 6: end for
3: 4:
The update separates the policy-relevant transverse convergence from the policy-irrelevant allones direction. Standard Q-VI has a switching-system representation whose JSR equals γ, because the all-ones direction is always an eigendirection with eigenvalue γ, and Proposition 2 shows that no error rate smaller than γ is possible for standard Q-VI. The residual correction removes this all-ones direction in the associated switching system representation. Therefore, the convergence rate of the corresponding switching-system representation becomes the projected JSR ρ̄, the same quantity that controls the projected error dynamics in the previous section. As shown below, this statement concerns value-error recentering: the projected trajectory and the corresponding greedy policy sequence remain the same as in standard Q-VI initialized at the same point. The first point to verify is that the correction term in deflated Q-VI does not introduce any spurious fixed point. Lemma 8. The deflated Q-VI map γ Tdef (Q) := F (Q) + 1−γ
1 ⊤ 1 (F (Q) − Q) 1 |S||A|
has the unique fixed point Q⋆ . The above lemma shows that the deflated Q-VI map is consistent with the Bellman operator. The next lemma states the simple geometric effect: compared with standard Q-VI, the deflated iterate differs only by an added term ck 1. Lemma 9 (Scalar-shift equivalence to standard Q-VI). Let Uk+1 = F (Uk ) be standard Q-VI with U0 = Q0 , and let Qk be generated by Equation (7) from the same initialization. Then there exist scalars ck ∈ R such that Qk = Uk + ck 1, ∀k ≥ 0. Consequently, Π⊥ Qk = Π⊥ Uk ,
πQk = πUk ,
under the same tie-breaking rule. 11
∀k ≥ 0,
Lemma 9 shows that the residual correction does not accelerate policy identification relative to standard Q-VI with the same initialization. It only adds a uniform shift ck 1 to the standard Q-VI iterate, so all state-action values move together by the same amount. The benefit analyzed in this paper is faster convergence of the full Q-function error after removing the all-ones mode.
8
Exact switching representation of deflated Q-VI
The fixed-point property confirms that the modification is consistent with the original Bellman equation. This section computes the exact switching system dynamics induced by the deflated Q-VI map. This calculation is the key step that shows how the all-ones direction is removed. To proceed, let Qk be generated by Equation (7), and define ek := Qk − Q⋆ ,
zk := Π⊥ ek .
Since Π⊥ is the orthogonal projection onto span(1)⊥ , the vector zk is the component of the error ek orthogonal to the all-ones direction: zk = Π⊥ ek ∈ span(1)⊥ . The remaining component of ek lies in span(1). More precisely, if ak :=
1 1⊤ e k , |S||A|
then the full error admits the orthogonal decomposition ek = Qk − Q⋆ = ak 1 + Π⊥ ek = ak 1 + zk .
(8)
Here ak 1 is the all-ones component of the error, while zk is its transverse component in span(1)⊥ . Lemma 10 (Orthogonal decomposition of the Q-error). Let Qk be generated by Equation (7), and define ek := Qk − Q⋆ , zk := Π⊥ ek . Then zk ∈ span(1)⊥ . Moreover, if ak :=
1 1⊤ e k , |S||A|
then the full error admits the orthogonal decomposition ek = Qk − Q⋆ = ak 1 + Π⊥ ek = ak 1 + zk .
(9)
Here ak 1 ∈ span(1) is the all-ones component of the error, while zk ∈ span(1)⊥ is its orthogonal transverse component. In addition, this decomposition is unique. With this decomposition in place, we can now write the deflated Q-VI recursion in separate coordinates. The next proposition shows that the projected component zk follows the same projected switching dynamics as standard Q-VI, while the scalar component ak is determined by zk rather than by its own previous value.
12
Proposition 3 (Exact deflated switching dynamics). Let Qk be generated by Equation (7), and define 1 1⊤ ek . ek := Qk − Q⋆ , zk := Π⊥ ek , ak := |S||A| Then k ∈ {0, 1, 2, . . .},
zk+1 = Āµk zk , and ak+1 = ℓµk zk ,
ℓµ :=
1 1⊤ Aµ , |S||A|(1 − γ)
k ∈ {0, 1, 2, . . .}.
Equivalently, they can be written by the following augmented system: ak+1 a 0 ℓµ = Dµk k , Dµ := , k ∈ {0, 1, 2, . . .}. zk+1 zk 0 Āµ The deflated Q-VI update keeps the projected component zk evolving through the projected switching system and recomputes the scalar all-ones component from that projected error. The block representation makes the role of deflation explicit. The transverse state zk evolves exactly as in projected standard Q-VI, whereas the scalar component ak is now driven only by zk and no longer feeds itself through an eigenvalue γ.
9
Provable JSR reduction
The augmented system formulation in Proposition 3 immediately links the convergence rate of deflated Q-VI to the projected switching system. Motivated by Proposition 3, let us define the associated augmented switching system family of deflated Q-VI by 0 ℓµ Ddef := Dµ = : µ : S → ∆|A| , 0 Āµ where each Dµ is regarded as a linear map on R × span(1)⊥ . Its JSR is denoted by ρdef := ρ(Ddef ). Theorem 1 (Associated full switched-family JSR of deflated Q-VI). The associated augmented switching family of the deflated Q-VI iteration Equation (7) satisfies ρdef = ρ̄. Consequently, every actual deflated Q-VI trajectory has an exponential convergence rate no larger than ρ̄, in the switched-family sense made explicit in Theorem 2. Since ρ̄ ≤ γ, this certified rate is no worse than the classical worst-case full-error rate of standard Q-VI identified in Propositions 1 and 2. If ρ̄ < γ, the certified switching system rate is strictly smaller than γ. The equality ρdef = ρ̄ is most informative when the projected rate is strictly smaller than the discount factor. The following elementary MDP shows that such a strict separation can occur. Example 1. Consider a discounted MDP with one state and two actions. The next state is the same state with probability one under both actions, and the rewards can be chosen arbitrarily. Then
13
the state-action vector has dimension two. For the two deterministic policies, let e1 , e2 denote the standard basis vectors and 1 = (1, 1)⊤ . The corresponding linear parts are A1 = γ1e⊤ 1,
A2 = γ1e⊤ 2.
If z ∈ span(1)⊥ , then z1 + z2 = 0, and Ai z = γzi 1,
i = 1, 2.
Thus Ai z lies entirely in span(1), so the transverse projection removes it: Π⊥ Ai Π⊥ z = 0,
i = 1, 2.
Hence, Ā1 = Ā2 = 0, and therefore ρ̄ = 0 < γ for every γ ∈ (0, 1). In this example, standard Q-VI still has JSR γ by Proposition 1, whereas the JSR associated with the deflated Q-VI is zero by Theorem 1. Together with Proposition 2, this example separates the convergence of standard Q-VI error from the convergence of deflated Q-VI: standard Q-VI retains the sharp γ all-ones mode, while deflated Q-VI removes it from the associated switching dynamics. The following result presents an explicit finite-time error bound for the deflated Q-VI recursion. Theorem 2. Let us consider Equation (7). Fix any ε ∈ (0, 1 − ρ̄), and define βε := ρ̄ + ε. Then there exists Cβε > 0 such that, for all k ≥ 1, ∥Qk − Q⋆ ∥2 ≤ Cβε βεk−1 ∥Π⊥ (Q0 − Q⋆ )∥2 . Consequently, 1/k
lim sup ∥Qk − Q⋆ ∥2
≤ ρ̄.
k→∞
If ρ̄ < γ, then deflated Q-VI has a certified full-error convergence rate strictly smaller than the classical worst-case full-error rate of standard Q-VI. The next lemma gives a simple explicit estimate for this constant, which can be used when a completely numerical convergence bound is desired. Lemma 11 (Basic bound for the scalar lifting constant). For ℓµ :=
1 1⊤ Aµ , |S||A|(1 − γ)
one has Lℓ := sup ∥ℓµ ∥2 ≤ µ
γ . 1−γ
Consequently, if the projected switching family satisfies ∥Āµm−1 · · · Āµ0 ∥2 ≤ cβε βεm ,
14
βε := ρ̄ + ε,
for all m ≥ 0 and all stochastic-policy switching sequences, then the constant in the full-error estimate can be chosen as ! p |S||A| γ Cβε := cβε + βε . 1−γ Moreover, if Nβε is the finite threshold in Lemma 2 for this projected family, then one may use the coarse bound ( !m ) p γ |S||A| cβε ≤ max 1, max , 0≤m<Nβε βε and hence
( Cβε ≤ max 1,
max
γ
0≤m<Nβε
!m ) p |S||A| βε
! p |S||A| γ + βε . 1−γ
Pure uniform-shift errors are eliminated immediately, while general initial conditions converge at the rate of the projected switching family JSR. Corollary 1 (Pure all-ones errors vanish in one step). If Q0 − Q⋆ ∈ span(1), then deflated Q-VI satisfies Q1 = Q⋆ . Corollary 2 (Iteration complexity for Q-function error). Let εQ > 0, fix ε ∈ (0, 1 − ρ̄), and define βε := ρ̄ + ε. If Π⊥ (Q0 − Q⋆ ) = 0, then Q1 = Q⋆ . Otherwise, the bound ln (Cβε ∥Π⊥ (Q0 − Q⋆ )∥2 /εQ ) k ≥1+ − ln βε implies ∥Qk − Q⋆ ∥2 ≤ εQ .
10
Generalized deflated Q-VI
The uniform residual average in Equation (7) is convenient but not essential. Let d = (di )i∈S×A ∈ ∆|S||A| ,
d⊤ 1 = 1,
be a fixed state-action distribution, possibly with zero components. In this section, we consider the more general deflated Q-VI Qk+1 = F (Qk ) +
γ d⊤ (F (Qk ) − Qk )1 = Td (Qk ), 1−γ
k ∈ {0, 1, 2, . . .},
(10)
where Td is the generalized deflated Q-VI map Td (Q) := F (Q) +
γ d⊤ (F (Q) − Q)1. 1−γ
(11)
Nonuniform choices of d are natural in randomized implementations and reinforcement-learning settings, where state-action pairs may be sampled according to a nonuniform visitation or exploration 1 distribution. When d = |S||A| 1, the update in Equation (10) reduces to the deflated Q-VI in the previous section. In the above mapping, the correction direction remains 1. Replacing the correction direction 1 by d generally does not remove the all-ones mode and can change the JSR. 15
To proceed, let us define Πd := I − 1d⊤ and Wd := span(d)⊥ = {x ∈ R|S||A| : d⊤ x = 0}, which is the subspace of state-action vectors whose d-weighted average is zero. Since d⊤ 1 = 1, we have Π2d = (I − 1d⊤ )2 = I − 21d⊤ + 1(d⊤ 1)d⊤ = I − 1d⊤ = Πd . Thus applying Πd twice is the same as applying it once, so Πd is a projection. Moreover, range(Πd ) = Wd ,
ker(Πd ) = span(1),
because d⊤ Πd x = d⊤ x − d⊤ 1 d⊤ x = 0 for every x, and Πd x = 0 holds exactly when x = (d⊤ x)1. Therefore, R|S||A| = Wd ⊕ span(1), and Πd maps a vector to its Wd -component while removing its span(1)-component. This projection is generally oblique: the two subspaces in the direct sum need not be orthogonal. It is orthogonal only in the special case where the hyperplane Wd is perpendicular to span(1), which occurs when d is proportional to 1. This is the standard linear-algebra meaning of an oblique projection [15]. In particular, Πd 1 = 0, d⊤ Πd = 0, and every error vector admits the unique decomposition e = a1 + z,
a = d⊤ e,
z = Πd e ∈ Wd .
Throughout this section, the symbols a, z, ak , and zk refer to this d-adapted decomposition; they are not the same coordinates as the empirical-mean decomposition used in the preceding sections. The identity z = Πd e ∈ Wd means that z is the part of the error remaining after removing the uniform component a1. Indeed, z = Πd e = e − 1d⊤ e = e − a1, and therefore d⊤ z = d⊤ e − d⊤ 1 d⊤ e = a − a = 0. Thus z has zero d-average, while a1 is the uniform-shift component measured by the same averaging functional d⊤ . The decomposition is unique because applying d⊤ to e = a1 + z gives d⊤ e = a, since d⊤ 1 = 1 and d⊤ z = 0. The next lemma shows that this change of complement does not change the fixed point. Lemma 12 (Fixed point of the d-weighted deflated map). The map Td in Equation (11) has the unique fixed point Q⋆ . With uniqueness of the fixed point established, the corresponding switching system model can be derived in the oblique decomposition induced by d.
16
Proposition 4. Let Qk be generated by Equation (10), and let ek = Qk −Q⋆ . For the stochastic-policy representation in Lemma 4, define the d-adapted coordinates ak := d⊤ ek .
zk := Πd ek , Then
k ∈ {0, 1, 2, . . .}, 1 ℓµ := d⊤ Aµ , k ∈ {0, 1, 2, . . .}. 1−γ
zk+1 = Πd Aµk Πd zk , ak+1 = ℓµk zk , Equivalently,
ak+1 a = Dµk k , zk+1 zk
0 ℓµ Dµ := , 0 Πd Aµ Πd
k ∈ {0, 1, 2, . . .},
where the lower-right block is regarded as a linear map from Wd to Wd . Thus the all-ones component again has zero autonomous diagonal dynamics. Here ak , zk , ℓµ , and Dµ are the d-adapted quantities used only in this section. They should be distinguished from the empirical-mean coordinates and the uniform-deflation blocks introduced earlier. The full error is ek = Qk − Q⋆ = ak 1 + zk ,
ak = d⊤ ek ,
zk = Πd ek ∈ Wd .
The projected block is now written on the zero-d-average subspace Wd instead of the zero-sum subspace span(1)⊥ . The following theorem shows that these two projected families are similar, and therefore have the same JSR. Theorem 3 (JSR of distribution-weighted residual deflation). For any fixed d ∈ ∆|S||A| , the associated full stochastic-policy switched-family JSR of Equation (10) is ρd = ρ̄ ≤ γ. Consequently, the distribution-weighted deflated Q-VI map has the same associated switched-family rate as the uniform deflated Q-VI map in Equation (7).
11
Numerical illustrations
This section illustrates the effect of deflated Q-VI recentering on finite discounted MDPs. Three examples are used: a small synthetic MDP, a stochastic FrozenLake benchmark, and the standard Taxi-v3 benchmark. The examples isolate the slow common-shift mode of standard Q-VI and show that the residual correction removes this mode while preserving the optimal fixed point. Because Lemma 9 shows that the greedy-policy sequence is unchanged relative to standard Q-VI, the plots focus on full Q-function error rather than policy-identification speed. First, consider a small MDP with four states, S = {1, 2, 3, 4}, two actions, A = {1, 2}, and discount factor γ = 0.95. The reward function is defined by 0.7666 1.3368 0.0000 0.0000 R= 0.0000 0.0000 , 1.0406 0.0000 17
Missing figure file: ex1 Figure 2: Full Q-function error for standard Q-VI and deflated Q-VI with uniform and nonuniform distributions. The deflated Q-VI updates remove the slow all-ones component and converge substantially faster than standard Q-VI. where the entry in row s and column a is R(s, a). The transition kernel is represented by two transition matrices P1 and P2 , one for each action: 1.0000 0.0000 0.0000 0.0000 0.5483 0.4517 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 1.0000 0.0000 0.0000 0.0000 , P1 = P = 2 0.6074 0.0000 0.3926 0.0000 1.0000 0.0000 0.0000 0.0000 , 0.0000 0.0000 0.6765 0.3235 0.0000 0.0000 1.0000 0.0000 where the s-th row of Pa gives the distribution over next states when action a is chosen at state s. Three methods are compared: standard Q-VI, deflated Q-VI with the uniform distribution, and deflated Q-VI with a nonuniform distribution. The optimal Q-function, computed by policy iteration, is 18.5393 18.7081 17.0925 17.7727 Q⋆ = 17.4238 17.7727 . 17.9921 16.8840 Figure 2 plots the full Q-function error ∥Qk − Q⋆ ∥∞ over 80 iterations. Standard Q-VI has empirical tail rate 0.95, matching the discount factor γ, because the dominant remaining error is the common-shift component. Both deflated variants eliminate this slow mode and reduce the error by many orders of magnitude within a small number of iterations. Although the greedy policy induced by the initialization is already optimal in this example, the value error remains large for standard Q-VI because of the common shift. This demonstrates that policy accuracy and value accuracy can behave differently, and that deflated Q-VI specifically accelerates convergence of the Q-function itself. Next, standard Q-VI is compared with deflated Q-VI on a standard stochastic FrozenLake benchmark. In the experiment, γ = 0.99, the distribution d is uniform over state-action pairs, and the initial condition is Q0 = 101. Figure 3 shows the evolution of the Q-function error ∥Qk − Q⋆ ∥∞ on a logarithmic scale. The horizontal axis is the iteration index k, and the vertical axis is the sup-norm error with respect to the optimal Q-function Q⋆ . The deflated Q-VI update decreases the full error much faster than standard Q-VI. In particular, the standard iteration exhibits a slow decay phase, while the deflated Q-VI iteration maintains a significantly steeper convergence trend. This behavior is consistent with the fact that the residual correction removes the slowly decaying component aligned with the all-ones direction. As a result, the full Q-function itself approaches Q⋆ substantially faster. Thus, the FrozenLake experiment illustrates the main advantage of the deflated Q-VI update: although both methods are based on the same Bellman optimality operator, the deflation term accelerates convergence in the full sup-norm sense by eliminating the residual constant-shift component. Finally, the same deflation idea is evaluated on the standard Taxi-v3 benchmark. This example is larger and more structured than the preceding small MDP and FrozenLake examples, and therefore provides a useful test of whether the acceleration effect persists in a more practical finite-state control 18
Missing figure file: ex2 Figure 3: Convergence of the full Q-function error ∥Qk − Q⋆ ∥∞ for standard Q-VI and deflated Q-VI on the FrozenLake benchmark. The deflated Q-VI update achieves a substantially faster decay of the full sup-norm error. Missing figure file: ex3.eps Figure 4: Full Q-function error ∥Qk − Q⋆ ∥∞ for standard Q-VI and deflated Q-VI on the Taxi-v3 benchmark. Standard Q-VI exhibits a slow tail decay, while the deflated Q-VI update removes the common-shift mode and reaches numerical precision after a short transient. problem. Standard Q-VI is compared with deflated Q-VI, and the full Q-function error ∥Qk − Q⋆ ∥∞ is measured with respect to a numerically computed optimal Q-function Q⋆ . Figure 4 plots the error over 700 iterations on a logarithmic scale. The standard Q-VI curve decreases steadily but slowly, remaining visibly above the numerical precision level even after hundreds of iterations. This slow tail behavior is again caused by the constant-shift component, which is contracted only at the discount-factor rate. In contrast, deflated Q-VI removes this slow mode. After a short initial transient, the error drops rapidly to approximately machine precision, around 10−13 , and remains at that level for the rest of the iterations. Thus, on Taxi-v3, the separation between the two methods is especially clear: the standard iteration still has a non-negligible full Q-function error at the end of the plotted horizon, whereas the deflated Q-VI iteration has already reached the numerical accuracy floor. This experiment further supports the central claim of the deflated Q-VI update. The deflation does not change the Bellman optimality fixed point, but it removes the slowly decaying all-ones component from the iteration. Consequently, the full Q-function converges to Q⋆ substantially faster in the sup-norm sense.
12
Conclusion
This paper developed a joint spectral radius framework for rank-one deflated Q-VI in discounted MDP control. The analysis shows that the standard Q-VI switching family has JSR exactly equal to the discount factor γ, because the all-ones vector is a common invariant direction of every subsystem. After this direction is removed, the relevant transverse dynamics are governed by the projected switching family with projected JSR ρ̄, which can be strictly smaller than γ. The rank-one residual correction removes the autonomous evolution of the all-ones component from the associated deflated switching system, so the resulting switched-family rate is ρ̄. The same projected rate is preserved when the residual average is taken with respect to any fixed state-action distribution, through an oblique-projection similarity argument. At the same time, the deflated iterate differs from the standard Q-VI iterate, initialized at the same point, only by a scalar multiple of 1. Therefore, the projected trajectory and the greedy-policy sequence are unchanged. The main benefit of deflation is thus not a different decision-making trajectory, but a sharper JSR-based description of the convergence geometry and a value-error recentering mechanism for full Q-function convergence.
19
A
Proof of convexification invariance of the JSR
Restatement of Lemma 1. For every finite matrix family H, ρ(co(H)) = ρ(H). Proof. Fix the same arbitrary submultiplicative matrix norm ∥·∥ as in Definition 1. Since H ⊆ co(H), ρ(H) ≤ ρ(co(H)). It remains to prove the reverse inequality. Fix a product length k ≥ 1. Since H is finite, write H = {H1 , . . . , HP M }. For arbitrary B1 , . . . , Bk ∈ co(H), there exist coefficients λj,i ≥ 0, i = 1, . . . , M , satisfying M i=1 λj,i = 1, such that M X Bj = λj,i Hi , j = 1, . . . , k. i=1
Expanding the product gives Bk · · · B1 =
M X
M X
λk,ik Hik · · ·
ik =1 M X
=
! λ1,i1 Hi1
i1 =1
···
i1 =1
M X
k Y
ik =1
λj,ij Hik · · · Hi1 .
j=1
The coefficients in this expansion form a convex combination because M X
M Y k X
···
i1 =1
k X M Y
λj,ij =
ik =1 j=1
λj,ij = 1.
j=1 ij =1
Define the finite-length product maximum Mk (H) :=
max
A1 ,...,Ak ∈H
∥Ak · · · A1 ∥.
The maximum exists because H is finite. By convexity of the norm, M M k X X Y ∥Bk · · · B1 ∥ ≤ ··· λj,ij ∥Hik · · · Hi1 ∥ i1 =1
≤
M X
ik =1
···
i1 =1
M X
j=1
k Y
ik =1
λj,ij Mk (H)
j=1
= Mk (H). Thus, for every B1 , . . . , Bk ∈ co(H), ∥Bk · · · B1 ∥ ≤
max
A1 ,...,Ak ∈H
∥Ak · · · A1 ∥.
Taking the supremum over B1 , . . . , Bk ∈ co(H) gives sup
∥Bk · · · B1 ∥ ≤
B1 ,...,Bk ∈co(H)
max
A1 ,...,Ak ∈H
∥Ak · · · A1 ∥.
Taking the k-th root and letting k → ∞ in the definition of the JSR yields ρ(co(H)) ≤ ρ(H). Therefore the two JSRs are equal. 20
B
Proof of the uniform exponential product bound
Restatement of Lemma 2. Let ∥ · ∥ be any fixed submultiplicative matrix norm. If ρ(H) < 1, then every switched product is uniformly exponentially stable in that norm: for every ε ∈ (0, 1 − ρ(H)), with βε := ρ(H) + ε, there exists Cβε > 0, depending on βε and on the chosen norm, such that for every k ≥ 0 and every switching word σ0 , . . . , σk−1 with Aj := Aσj ∈ H,
j = 0, . . . , k − 1,
one has ∥Ak−1 · · · A0 ∥ ≤ Cβε βεk , where the product is interpreted as the identity when k = 0. Proof. Fix the chosen submultiplicative matrix norm and define Mk :=
∥Ak−1 · · · A0 ∥ ,
sup
M0 := 1.
A0 ,...,Ak−1 ∈H
By the definition of the JSR, 1/k
lim Mk
k→∞
= ρ(H).
Fix ε ∈ (0, 1 − ρ(H)) and define βε := ρ(H) + ε. Since the limit is strictly smaller than βε , there exists an integer Nβε such that 1/k Mk ≤ βε , ∀k ≥ Nβε . Equivalently, Mk ≤ βεk for all k ≥ Nβε . For the finitely many shorter lengths, define Mk Cβε := max 1, max . 0≤k<Nβε βεk Then Cβε < ∞. If k < Nβε , the definition of Cβε gives Mk ≤ Cβε βεk . If k ≥ Nβε , then Mk ≤ βεk ≤ Cβε βεk . Therefore, for every length k ≥ 0 and every switching word σ0 , . . . , σk−1 , with selected matrices Aj := Aσj ∈ H, ∥Ak−1 · · · A0 ∥ ≤ Mk ≤ Cβε βεk . This proves the claim.
C
Proof of the block upper-triangular JSR formula
Restatement of Lemma 3. Let B i Ci M := :i∈I 0 Di be a bounded family of block upper-triangular matrices. Let B := {Bi : i ∈ I} and D := {Di : i ∈ I}. Then ρ(M) = max{ρ(B), ρ(D)}.
21
Proof. This is a standard property of block triangular matrix families. The proof is included to make clear why the off-diagonal blocks do not affect the exponential rate. Use a block-compatible submultiplicative norm, for example the operator norm induced by ∥(x, y)∥ := max{∥x∥, ∥y∥}. Since the JSR is independent of the chosen submultiplicative norm, this choice is without loss of generality. For the lower bound, fix a switching word i0 , . . . , ik−1 and write Bij Cij Mij := . 0 D ij The product remains block upper triangular: Bik−1 · · · Bi0 Mik−1 · · · Mi0 = 0
∗ . Dik−1 · · · Di0
With the chosen block norm, Mik−1 · · · Mi0 ≥ Bik−1 · · · Bi0 ,
Mik−1 · · · Mi0 ≥ Dik−1 · · · Di0 .
Taking the supremum over switching words, then the k-th root and the limit, gives ρ(M) ≥ ρ(B),
ρ(M) ≥ ρ(D).
Thus ρ(M) ≥ max{ρ(B), ρ(D)}. For the upper bound, fix any q > max{ρ(B), ρ(D)}. Applying Lemma 2 to the scaled families q −1 B and q −1 D gives constants KB , KD ≥ 1 such that every length-m product satisfies Bim−1 · · · Bi0 ≤ KB q m ,
Dim−1 · · · Di0 ≤ KD q m ,
where the length-zero product is the identity. Since M is bounded, KC := sup ∥Ci ∥ < ∞. i∈I
For a length-k product, direct multiplication gives Bik−1 · · · Bi0 Mik−1 · · · Mi0 = 0
Ek , Dik−1 · · · Di0
where, with empty products interpreted as identity matrices, Ek =
k−1 X
Bik−1 · · · Bij+1 Cij Dij−1 · · · Di0 .
j=0
Therefore, ∥Ek ∥ ≤
k−1 X
Bik−1 · · · Bij+1 ∥Cij ∥ Dij−1 · · · Di0
j=0
22
m ≥ 0,
≤
k−1 X
KB q k−1−j KC KD q j
j=0
= KB KC KD k q k−1 . The diagonal blocks also satisfy Dik−1 · · · Di0 ≤ KD q k .
Bik−1 · · · Bi0 ≤ KB q k ,
Hence, for a constant Kq > 0 independent of the switching word and of k, Mik−1 · · · Mi0 ≤ Kq (k + 1)q k . Taking the supremum over all length-k switching words yields sup i0 ,...,ik−1
Mik−1 · · · Mi0
1/k
1/k ≤ Kq (k + 1) q.
Letting k → ∞ gives ρ(M) ≤ q. Since this holds for every q > max{ρ(B), ρ(D)}, letting q ↓ max{ρ(B), ρ(D)} gives ρ(M) ≤ max{ρ(B), ρ(D)}. Combining the lower and upper bounds proves the claim.
D
Proof of the full Q-VI switching JSR
Restatement of Proposition 1. The deterministic switching family H = {Aπ : π ∈ Θ} satisfies ρ(H) = γ. Proof. For every deterministic policy π, the matrix P Ππ is row-stochastic. Hence Aπ 1 = γ1 and ∥Aπ ∥∞ = γ. Therefore, for every switching word π0 , . . . , πk−1 , ∥Aπk−1 · · · Aπ0 ∥∞ ≤ γ k , which implies ρ(H) ≤ γ. For the reverse inequality, the same induced infinity norm gives Aπk−1 · · · Aπ0 1 = γ k 1 for every switching word. Thus ∥Aπk−1 · · · Aπ0 ∥∞ ≥
∥Aπk−1 · · · Aπ0 1∥∞ = γk. ∥1∥∞
Taking the supremum over switching words, the k-th root, and the limit in Definition 1 yields ρ(H) ≥ γ. Hence ρ(H) = γ.
23
E
Proof of the exact stochastic-policy error representation
Restatement of Lemma 4. For every Q ∈ R|S||A| , there exists a stochastic policy µQ : S → ∆|A| such that F (Q) − Q⋆ = AµQ (Q − Q⋆ ). Consequently, with e := Q − Q⋆ , F (Q) − Q = (AµQ − I)e. In particular, the statement applies to standard Q-VI iterates and to the deflated Q-VI iterates studied below. Proof. Let e(s, a) := Q(s, a) − Q⋆ (s, a). For each state s, let us define δs := max Q(s, a) − max Q⋆ (s, a). a∈A
a∈A
It is first shown that δs belongs to the convex hull of {e(s, a) : a ∈ A}. To this end, choose i ∈ Arg maxa∈A Q(s, a) and j ∈ Arg maxa∈A Q⋆ (s, a). Since Q(s, j) ≤ Q(s, i) and Q⋆ (s, i) ≤ Q⋆ (s, j), e(s, j) = Q(s, j) − Q⋆ (s, j) ≤ Q(s, i) − Q⋆ (s, j) = δs and δs = Q(s, i) − Q⋆ (s, j) ≤ Q(s, i) − Q⋆ (s, i) = e(s, i). Thus δs lies between two action-error values and can be written as a convex combination of action errors at state s. Hence there exists µQ (· | s) ∈ ∆|A| such that X δs = µQ (a | s)e(s, a). a∈A
Constructing this stochastic vector independently for each state gives a stochastic policy µQ with max Q(s, a) − max Q⋆ (s, a) = (ΠµQ e)(s), a∈A
a∈A
∀s ∈ S.
Since Q⋆ = F (Q⋆ ), we have F (Q) − Q⋆ = F (Q) − F (Q⋆ ) = γP ΠµQ (Q − Q⋆ ) = γP ΠµQ e = AµQ e. Subtracting Q = Q⋆ + e from both sides gives F (Q) − Q = (AµQ − I)e.
F
Proof of the empirical orthogonal error decomposition
Restatement of Lemma 5. For any error vector ek ∈ R|S||A| , define zk and ak as in Equation (6): zk := Π⊥ ek ,
ak :=
1 1⊤ ek . |S||A|
Then zk ∈ span(1)⊥ , ak is the empirical mean of ek , and ek = ak 1 + zk = ak 1 + Π⊥ ek . Moreover, this decomposition is unique: if ek = α1 + w with w ∈ span(1)⊥ , then α = ak and w = zk . 24
Proof. By the definition of Π⊥ , 1 1 ⊤ ⊤ ek = ek − zk = I − 11 1 ek 1 = ek − ak 1. |S||A| |S||A| Therefore ek = ak 1 + zk . Also, 1⊤ zk = 1⊤ ek − ak 1⊤ 1 = 1⊤ ek −
1 1⊤ ek · |S||A| = 0, |S||A|
so zk ∈ span(1)⊥ . Finally, if ek = α1 + w with w ∈ span(1)⊥ , then applying (|S||A|)−1 1⊤ gives α = (|S||A|)−1 1⊤ ek = ak , and hence w = ek − ak 1 = zk . This proves the decomposition used in Equation (6).
G
Proof of the projected error recursion for standard Q-VI
Restatement of Lemma 6. The standard Q-VI recursion satisfies k ∈ {0, 1, 2, . . .}.
zk+1 = Āµk zk , Proof. Standard Q-VI gives
ek+1 = F (Qk ) − Q⋆ = Aµk ek ,
k ∈ {0, 1, 2, . . .}.
by Lemma 4. Applying Π⊥ to both sides and using Equations (1), (3) and (6) gives zk+1 = Π⊥ ek+1 = Π⊥ Aµk (ak 1 + zk ) = ak Π⊥ Aµk 1 + Π⊥ Aµk zk = ak γΠ⊥ 1 + Π⊥ Aµk zk = Π⊥ Aµk zk . Since zk = Π⊥ ek , the vector zk already lies in span(1)⊥ , and hence Π⊥ zk = zk . Therefore Π⊥ Aµk zk = Π⊥ Aµk Π⊥ zk = Āµk zk . Thus the averaged all-ones component ak 1 has no effect on the projected error recursion; it is killed by the output projection because Aµk 1 = γ1 remains in the all-ones direction.
H
Proof of the projected JSR bound
Restatement of Lemma 7. The projected JSR satisfies ρ̄ ≤ γ. Proof. We follow the projected-product argument used in Lee [10, Lemma 8]. For every deterministic policy π, Aπ 1 = γ1. Hence Π⊥ Aπ (I − Π⊥ ) = 0,
Π⊥ Aπ Π⊥ = Π⊥ Aπ .
25
Therefore, for every switching word π0 , . . . , πk−1 , the projected product satisfies Āπk−1 · · · Āπ0 = Π⊥ Aπk−1 · · · Aπ0 Π⊥ . Indeed, the identity is immediate for k = 1. If it holds for a product of length k, then Āπk Āπk−1 · · · Āπ0 = Π⊥ Aπk Π⊥ Π⊥ Aπk−1 · · · Aπ0 Π⊥ = Π⊥ Aπk Π⊥ Aπk−1 · · · Aπ0 Π⊥ = Π⊥ Aπk Aπk−1 · · · Aπ0 Π⊥ , where the last equality uses Π⊥ Aπk Π⊥ = Π⊥ Aπk . This proves the product identity by induction. Now use the induced infinity norm. Since P Ππ is row-stochastic, ∥Aπ ∥∞ = γ for every deterministic policy π. Thus ∥Aπk−1 · · · Aπ0 ∥∞ ≤ γ k . Combining this bound with the product identity gives ∥Āπk−1 · · · Āπ0 ∥∞ ≤ ∥Π⊥ ∥2∞ γ k . Taking the maximum over all deterministic switching words, taking the k-th root, and then letting k → ∞, the constant ∥Π⊥ ∥2∞ disappears. Since the JSR is independent of the chosen submultiplicative norm, ρ̄ ≤ γ.
I
Proof of sharpness of the classical rate for standard Q-VI
Restatement of Proposition 2. For standard Q-VI, no uniform global convergence estimate to Q⋆ can have a rate smaller than γ. In particular, if Q0 = Q⋆ + c1,
c ̸= 0,
Qk − Q⋆ = γ k c1,
∀k ≥ 0.
then standard Q-VI satisfies Proof. The claim follows from the shift identity F (Q⋆ + c1) = Q⋆ + γc1. Iterating gives Qk − Q⋆ = γ k c1. If a bound with rate r < γ were valid for all initial conditions, this trajectory would require γ k ≤ Crk for all k, which is impossible for finite C.
J
Proof of the fixed-point lemma for residual deflation
Restatement of Lemma 8. The deflated map γ Tdef (Q) := F (Q) + 1−γ
has the unique fixed point Q⋆ .
26
1 ⊤ 1 (F (Q) − Q) 1 |S||A|
Proof. Since F (Q⋆ ) = Q⋆ , Tdef (Q⋆ ) = Q⋆ . Conversely, suppose that Q = Tdef (Q). Let r̄ := (|S||A|)−1 1⊤ r.
r := F (Q) − Q, Then r=−
γ r̄1. 1−γ
Taking the empirical mean gives r̄ = −
γ r̄. 1−γ
Hence r̄ = 0, and therefore r = 0. Thus F (Q) = Q. Since the Bellman operator has the unique fixed point Q⋆ , Q = Q⋆ .
K
Proof of scalar-shift equivalence to standard Q-VI
Restatement of Lemma 9. Let Uk+1 = F (Uk ) be standard Q-VI with U0 = Q0 , and let Qk be generated by Equation (7) from the same initialization. Then there exist scalars ck ∈ R such that Qk = Uk + ck 1,
∀k ≥ 0.
Consequently, Π⊥ Qk = Π⊥ Uk ,
πQk = πUk ,
∀k ≥ 0,
under the same tie-breaking rule. Proof. The claim holds at k = 0 with c0 = 0. Suppose that Qk = Uk + ck 1. By the shift identity Equation (2), F (Qk ) = F (Uk ) + γck 1 = Uk+1 + γck 1. Moreover, F (Qk ) − Qk = F (Uk ) − Uk + (γ − 1)ck 1. Taking the empirical mean and substituting into Equation (7) yields γ 1 ⊤ Qk+1 = Uk+1 + γck 1 + 1 (F (Uk ) − Uk ) + (γ − 1)ck 1 1 − γ |S||A| 1 γ 1⊤ (F (Uk ) − Uk ) 1. = Uk+1 + 1 − γ |S||A| Thus Qk+1 = Uk+1 +ck+1 1 for a scalar ck+1 . The induction is complete. Projection by Π⊥ eliminates the scalar shift, and adding a state-independent constant to all state-action values does not change any statewise greedy action under the same tie-breaking rule.
L
Proof of the orthogonal decomposition of the Q-error
Restatement of Lemma 10. Let Qk be generated by Equation (7), and define ek := Qk − Q⋆ , Then zk ∈ span(1)⊥ . Moreover, if ak :=
zk := Π⊥ ek .
1 1⊤ e k , |S||A| 27
then the full error admits the orthogonal decomposition ek = Qk − Q⋆ = ak 1 + Π⊥ ek = ak 1 + zk . Here ak 1 ∈ span(1) is the all-ones component of the error, while zk ∈ span(1)⊥ is its orthogonal transverse component. In addition, this decomposition is unique. Proof. By the definition of the projection, Π⊥ = I −
1 11⊤ . |S||A|
Therefore, zk = Π⊥ ek = I −
1 1 ⊤ ⊤ 11 ek = ek − 1 ek 1 = ek − ak 1. |S||A| |S||A|
Rearranging gives ek = ak 1 + zk = ak 1 + Π⊥ ek . It remains to verify that zk is orthogonal to the all-ones direction. Since 1⊤ 1 = |S||A|, we have 1⊤ zk = 1⊤ ek − ak 1⊤ 1 = 1⊤ ek −
1 1⊤ ek · |S||A| = 0. |S||A|
Hence zk ∈ span(1)⊥ . Finally, suppose that another decomposition is given by w ∈ span(1)⊥ .
ek = α1 + w, Multiplying both sides by (|S||A|)−1 1⊤ yields
1 1 1⊤ e k = α + 1⊤ w = α, |S||A| |S||A| because 1⊤ w = 0. Thus α = ak , and consequently w = ek − ak 1 = zk . Therefore, the decomposition is unique.
M
Proof of the exact deflated switching dynamics
Restatement of Proposition 3. Let Qk be generated by Equation (7), and define ek := Qk − Q⋆ ,
zk := Π⊥ ek ,
ak :=
1 1⊤ ek . |S||A|
Then k ∈ {0, 1, 2, . . .},
zk+1 = Āµk zk , and ak+1 = ℓµk zk ,
ℓµ :=
1 1⊤ Aµ , |S||A|(1 − γ)
k ∈ {0, 1, 2, . . .}.
Equivalently, ak+1 a = Dµk k , zk+1 zk
0 ℓµ Dµ := , 0 Āµ 28
k ∈ {0, 1, 2, . . .}.
Proof. By Lemma 4, the Bellman residual rk satisfies rk = F (Qk ) − Qk = (Aµk − I)ek . Subtracting Q⋆ from Equation (7) and using F (Qk ) − Q⋆ = Aµk ek gives ek+1 = Aµk ek +
γ r̄k 1, 1−γ
k ∈ {0, 1, 2, . . .}.
(12)
Applying Π⊥ to Equation (12) and using Equations (1), (3) and (9) gives zk+1 = Π⊥ Aµk zk = Π⊥ Aµk Π⊥ zk = Āµk zk . It remains to compute the scalar component. The residual mean is obtained from rk = (Aµk −I)ek by applying the empirical averaging functional (|S||A|)−1 1⊤ . Substituting ek = ak 1 + zk from Equation (9) gives 1 1⊤ (Aµk − I)ek |S||A| 1 1⊤ (Aµk − I)(ak 1 + zk ) = |S||A| ak 1 1 = 1⊤ (γ1 − 1) + 1⊤ Aµk zk − 1⊤ zk . |S||A| |S||A| |S||A|
r̄k =
Here Aµk 1 = γ1 by Equation (3), and 1⊤ zk = 0 because zk = Π⊥ ek ∈ span(1)⊥ . Therefore r̄k = (γ − 1)ak +
1 1⊤ Aµk zk . |S||A|
Taking empirical means in Equation (12) gives 1 γ 1⊤ Aµk zk + ak+1 = γak + |S||A| 1−γ 1 = 1⊤ Aµk zk . |S||A|(1 − γ)
(γ − 1)ak +
1 1⊤ Aµk zk |S||A|
This proves the stated block representation.
N
Proof of the associated full switched-family JSR theorem
Restatement of Theorem 1. The associated full stochastic-policy switched family of the deflated Q-VI iteration Equation (7) satisfies ρdef = ρ̄. Consequently, every actual deflated Q-VI trajectory has an upper asymptotic rate no larger than ρ̄ in the switched-family sense made explicit in Theorem 2. Since ρ̄ ≤ γ, this certified rate is no worse than the classical worst-case full Q-VI rate identified in Propositions 1 and 2. If ρ̄ < γ, the certified switched-family rate is strictly smaller than γ. Proof. By Proposition 3, the associated deflated Q-VI family is precisely Ddef . Thus, by the definition of ρdef and by Lemma 3, ρdef = max 0, ρ {Āµ : µ stochastic} = ρ {Āµ : µ stochastic} . 29
The stochastic-policy family is the convex hull of the deterministic-policy family, because every stochastic stationary policy can be written as a convex combination of deterministic stationary policies. Since µ 7→ Aµ is affine and Āµ = Π⊥ Aµ Π⊥ is linear in Aµ , {Āµ : µ stochastic} = co {Āπ : π ∈ Θ} . By Lemma 1, ρ {Āµ : µ stochastic} = ρ {Āπ : π ∈ Θ} = ρ̄. Therefore ρdef = ρ̄. Since ρ̄ ≤ γ, the rate comparison follows.
O
Proof of the explicit full convergence rate theorem
Restatement of Theorem 2. Consider Equation (7). Fix any ε ∈ (0, 1 − ρ̄), and define βε := ρ̄ + ε. Then there exists Cβε > 0 such that, for all k ≥ 1, ∥Qk − Q⋆ ∥2 ≤ Cβε βεk−1 ∥Π⊥ (Q0 − Q⋆ )∥2 . Consequently, 1/k
lim sup ∥Qk − Q⋆ ∥2
≤ ρ̄.
k→∞
If ρ̄ < γ, then deflated Q-VI has a certified full-error convergence rate strictly smaller than the classical worst-case full-error rate of standard Q-VI. Proof. By Theorem 1, the projected stochastic-policy family has the same JSR as the deterministic projected family, namely ρ̄. Fix ε ∈ (0, 1 − ρ̄) and define βε := ρ̄ + ε. Applying Lemma 2 to the projected stochastic-policy family gives a constant cβε > 0 such that, for every length m ≥ 0 and every stochastic-policy switching word, ∥Āµm−1 · · · Āµ0 ∥2 ≤ cβε βεm . Iterating the projected recursion in Proposition 3 gives zk = Āµk−1 · · · Āµ0 z0 . Therefore ∥zk ∥2 ≤ ∥Āµk−1 · · · Āµ0 ∥2 ∥z0 ∥2 ≤ cβε βεk ∥z0 ∥2 . Next, recall that ℓµ is the row vector defined in Proposition 3, ℓµ :=
1 1⊤ Aµ . |S||A|(1 − γ)
It is the linear functional that maps the previous projected error zk to the next averaged scalar component ak+1 . Since the set of stochastic policies is a finite product of compact simplexes and µ 7→ ℓµ is continuous, its Euclidean operator norm is uniformly bounded. Hence Lℓ := sup ∥ℓµ ∥2 < ∞. µ
30
For k ≥ 1, Proposition 3 gives |ak | = |ℓµk−1 zk−1 | ≤ Lℓ ∥zk−1 ∥2 ≤ Lℓ cβε βεk−1 ∥z0 ∥2 . Since ek = ak 1 + zk , ∥ek ∥2 ≤ ∥ak 1∥2 + ∥zk ∥2 p = |S||A||ak | + ∥zk ∥2 p ≤ cβε ( |S||A|Lℓ + βε )βεk−1 ∥z0 ∥2 . Taking p Cβε := cβε ( |S||A|Lℓ + βε ) and using z0 = Π⊥ (Q0 − Q⋆ ) proves the finite-time bound. It remains to prove the limsup conclusion. If z0 = 0, then Proposition 3 gives zk = 0 and ak = 0 for all k ≥ 1, so ek = 0 for all k ≥ 1 and the claim is immediate. Otherwise, the finite-time bound implies 1/k 1/k ∥ek ∥2 ≤ Cβε ∥z0 ∥2 βε−1 βε . The constant factor satisfies lim Cβε ∥z0 ∥2 βε−1
1/k
k→∞
= 1.
Therefore 1/k
lim sup ∥Qk − Q⋆ ∥2 k→∞
1/k
= lim sup ∥ek ∥2
≤ βε .
k→∞
Since this holds for every ε ∈ (0, 1 − ρ̄), letting ε ↓ 0 gives 1/k
lim sup ∥Qk − Q⋆ ∥2
≤ ρ̄.
k→∞
P
Proof of the scalar lifting bound
Restatement of Lemma 11. For ℓµ :=
1 1⊤ Aµ , |S||A|(1 − γ)
one has Lℓ := sup ∥ℓµ ∥2 ≤ µ
γ . 1−γ
Consequently, if the projected stochastic-policy family satisfies ∥Āµm−1 · · · Āµ0 ∥2 ≤ cβε βεm ,
βε := ρ̄ + ε,
for all m ≥ 0 and all stochastic-policy switching words, then the constant in the full-error estimate can be chosen as ! p |S||A| γ Cβε := cβε + βε . 1−γ
31
Moreover, if Nβε is the finite threshold in Lemma 2 for this projected family, then one may use the coarse bound ( !m ) p γ |S||A| , cβε ≤ max 1, max 0≤m<Nβε βε and hence
( Cβε ≤ max 1,
max
γ
0≤m<Nβε
!m ) p |S||A| βε
! p |S||A| γ + βε . 1−γ
Proof. For every stochastic policy µ, the matrix P Πµ is row-stochastic. Hence Aµ = γP Πµ is nonnegative and every row of Aµ sums to γ. Therefore the nonnegative row vector 1⊤ Aµ has total mass ∥1⊤ Aµ ∥1 = 1⊤ Aµ 1 = γ|S||A|. Since ∥v∥2 ≤ ∥v∥1 for every vector v, ∥ℓµ ∥2 =
1 1 γ ∥1⊤ Aµ ∥2 ≤ ∥1⊤ Aµ ∥1 = . |S||A|(1 − γ) |S||A|(1 − γ) 1−γ
Taking the supremum over µ gives the first claim. The stated value of Cβε follows by substituting this bound in Theorem 2. For the coarse bound onp cβε , note that ∥Āµ ∥2 ≤ ∥Aµ ∥2 ≤ p on Lℓ into the estimate µ µ γ |S||A|, because ∥P Π ∥∞ = 1, ∥P Π ∥1 ≤ |S||A|, and ∥M p ∥2 ≤ ∥M ∥1 ∥M ∥∞ . Therefore every length-m projected product has Euclidean norm at most (γ |S||A|)m . Combining this finite-length bound with the construction of cβε in Lemma 2 gives the displayed upper bounds.
Q
Proof of the pure all-ones error corollary
Restatement of Corollary 1. If Q0 − Q⋆ ∈ span(1), then deflated Q-VI satisfies Q1 = Q⋆ . Proof. If Q0 − Q⋆ ∈ span(1), then z0 = 0. By Proposition 3, z1 = 0 and a1 = ℓµ0 z0 = 0. Thus Q1 − Q⋆ = 0.
R
Proof of the iteration complexity corollary
Restatement of Corollary 2. Let εQ > 0, fix ε ∈ (0, 1 − ρ̄), and define βε := ρ̄ + ε. If Π⊥ (Q0 − Q⋆ ) = 0, then Q1 = Q⋆ . Otherwise, the bound ln (Cβε ∥Π⊥ (Q0 − Q⋆ )∥2 /εQ ) k ≥1+ − ln βε implies ∥Qk − Q⋆ ∥2 ≤ εQ . Proof. If Π⊥ (Q0 − Q⋆ ) = 0, then Corollary 1 gives Q1 = Q⋆ . Otherwise, Theorem 2 gives ∥Qk − Q⋆ ∥2 ≤ Cβε βεk−1 ∥Π⊥ (Q0 − Q⋆ )∥2 . Since 0 < βε < 1, the stated lower bound on k implies Cβε βεk−1 ∥Π⊥ (Q0 − Q⋆ )∥2 ≤ εQ . Substituting this inequality into the explicit rate bound proves the claim. 32
S
Proof of the fixed-point lemma for the d-weighted map
Restatement of Lemma 12. The map Td in Equation (11) has the unique fixed point Q⋆ . Proof. Since F (Q⋆ ) = Q⋆ , Td (Q⋆ ) = Q⋆ . Conversely, suppose that Q = Td (Q). Let r := F (Q) − Q, Then r=−
r̄d := d⊤ r.
γ r̄d 1. 1−γ
Multiplying by d⊤ and using d⊤ 1 = 1 gives r̄d = −
γ r̄d . 1−γ
Hence r̄d = 0, and therefore r = 0. Thus F (Q) = Q. Since the Bellman optimality operator has the unique fixed point Q⋆ , Q = Q⋆ .
T
Proof of the exact d-projected switching dynamics
Restatement of Proposition 4. Let Qk be generated by Equation (10), and let ek = Qk − Q⋆ . For the stochastic-policy representation in Lemma 4, define ak := d⊤ ek .
zk := Πd ek , Then
k ∈ {0, 1, 2, . . .}, 1 ℓµ := d⊤ Aµ , k ∈ {0, 1, 2, . . .}. 1−γ
zk+1 = Πd Aµk Πd zk , ak+1 = ℓµk zk , Equivalently,
ak+1 a = Dµk k , zk+1 zk
Dµ :=
0 ℓµ , 0 Πd Aµ Πd
k ∈ {0, 1, 2, . . .},
where the lower-right block is regarded as a linear map from Wd to Wd . Thus the all-ones component again has zero autonomous diagonal dynamics. Proof. By Lemma 4, F (Qk ) − Qk = (Aµk − I)ek . The error recursion induced by Equation (11) is ek+1 = Aµk ek +
γ 1d⊤ (Aµk − I)ek , 1−γ
k ∈ {0, 1, 2, . . .}.
Applying Πd eliminates the correction term because Πd 1 = 0. With ek = ak 1 + zk and Aµk 1 = γ1, zk+1 = Πd Aµk zk = Πd Aµk Πd zk . Since zk ∈ Wd and Πd Aµk Πd maps Wd into Wd , this is precisely its action on zk . 33
Next, taking the d-average gives γ d⊤ (Aµk − I)ek 1−γ 1 γ = d⊤ Aµk ek − d⊤ ek . 1−γ 1−γ
ak+1 = d⊤ Aµk ek +
Substituting ek = ak 1 + zk and using Aµk 1 = γ1, d⊤ 1 = 1, and d⊤ zk = 0 yields ak+1 =
1 d⊤ Aµk zk . 1−γ
This proves the block representation.
U
Proof of the distribution-weighted JSR theorem
Restatement of Theorem 3. For any fixed d ∈ ∆|S||A| , the associated full stochastic-policy switched-family JSR of Equation (10) is ρd = ρ̄ ≤ γ. Consequently, the distribution-weighted deflated Q-VI map has the same associated switched-family rate as the uniform deflated Q-VI map in Equation (7). Proof. By Proposition 4, the associated switched family is block upper triangular with diagonal blocks 0 and Πd Aµ Πd , where the latter block acts on Wd . By Lemma 3, the full switched-family JSR equals the operator JSR of this lower-right family on Wd . More explicitly, this means ρWd ({Πd Aµ Πd : µ stochastic}) := lim
sup
k→∞ µ0 ,...,µk−1
1/k
(Πd Aµk−1 Πd ) · · · (Πd Aµ0 Πd ) op,d ,
where each factor is regarded as a linear map Wd → Wd , and ∥ · ∥op,d is any induced operator norm on Wd . Thus ρd = ρWd ({Πd Aµ Πd : µ stochastic}) . It remains to compare this value with ρ̄. Recall that span(1)⊥ = {x ∈ R|S||A| : 1⊤ x = 0},
Wd := span(d)⊥ = {x ∈ R|S||A| : d⊤ x = 0}.
The map Sd : span(1)⊥ → Wd , Sd x := Πd x, is a linear bijection with inverse Sd−1 y = Π⊥ y. Indeed, if x ∈ span(1)⊥ and Πd x = 0, then x = (d⊤ x)1, and the constraint 1⊤ x = 0 implies x = 0. For y ∈ Wd , Πd Π⊥ y = Πd y = y; for x ∈ span(1)⊥ , Π⊥ Πd x = Π⊥ x = x. This remains true even when some components of d are zero; only d⊤ 1 = 1 is needed. For any deterministic policy π and any y ∈ Wd , Sd (Π⊥ Aπ Π⊥ )Sd−1 y = Πd Π⊥ Aπ Π⊥ y = Πd Aπ Π⊥ y = Πd Aπ y = Πd Aπ Πd y. The second equality uses Πd Π⊥ = Πd . The third equality follows because y − Π⊥ y ∈ span(1) and Πd Aπ 1 = γΠd 1 = 0. The last equality uses y ∈ Wd , so Πd y = y. Thus the deterministic 34
family {Πd Aπ Πd : π ∈ Θ}, regarded on Wd , is similar to the orthogonally projected family {Π⊥ Aπ Π⊥ : π ∈ Θ}, regarded on span(1)⊥ . Similarity preserves the JSR. The stochastic-policy family is the convex hull of the deterministic-policy family, and Lemma 1 gives the same JSR after convexification. Therefore, writing ρspan(1)⊥ for the analogous operator JSR on span(1)⊥ , ρd = ρWd ({Πd Aπ Πd : π ∈ Θ}) = ρspan(1)⊥ ({Π⊥ Aπ Π⊥ : π ∈ Θ}) = ρ̄. Finally, ρ̄ ≤ γ by Lemma 7.
References [1] Dimitri P. Bertsekas. Generic rank-one corrections for value iteration in markovian decision problems. Operations Research Letters, 17(3):111–119, 1995. [2] Dimitri P Bertsekas. Dynamic programming and optimal control 4th edition, volume ii. Athena Scientific, 2015. [3] Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific Belmont, MA, 1996. [4] Vincent D Blondel and Yurii Nesterov. Computationally efficient approximations of the joint spectral radius. SIAM Journal on Matrix Analysis and Applications, 27(1):256–272, 2005. [5] A. Cicone. A note on the joint spectral radius. arXiv preprint arXiv:1502.01506, 2015. [6] V. Goyal and J. Grand-Clément. A first-order approach to accelerated value iteration. Operations Research, 71(2):517–535, 2023. [7] J. P. Hespanha and A. S. Morse. Stability of switched systems with average dwell-time. In Proceedings of the 38th IEEE Conference on Decision and Control, pages 2655–2660, 1999. [8] Raphaël Jungers. The joint spectral radius: Theory and applications, volume 385. Springer Science & Business Media, 2009. [9] A. S. Kolarijani, T. Ok, P. Mohajerin Esfahani, and M. A. S. Kolarijani. Rank-one modified value iteration. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 31182–31201, 2025. [10] Donghwan Lee. Beyond the bellman fixed point: geometry and fast policy identification in value iteration. arXiv preprint arXiv:2604.17457v4, 2026. [11] Donghwan Lee. Lyapunov-certified direct switching theory for q-learning. arXiv preprint arXiv:2604.19569v2, 2026. [12] J. Lee, A. Rakhsha, E. K. Ryu, and A.-m. Farahmand. Deflated dynamics value iteration. Transactions on Machine Learning Research, 2025. [13] Daniel Liberzon. Switching in systems and control. Springer Science & Business Media, 2003. [14] Hai Lin and Panos J Antsaklis. Stability and stabilizability of switched linear systems: A survey of recent results. IEEE Transactions on Automatic Control, 54(2):308–322, 2009. 35
[15] Carl D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM, 2000. [16] Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014. [17] Gian-Carlo Rota and Gilbert Strang. A note on the joint spectral radius. Indag. Math, 22(4): 379–381, 1960. [18] Robert Shorten, Fabian Wirth, Oliver Mason, Kai Wulff, and Christopher King. Stability criteria for switched and hybrid systems. SIAM Review, 49(4):545–592, 2007. [19] John N Tsitsiklis and Vincent 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, 10(1):31–40, 1997.
36