Sign-Separated Finite-Time Error Analysis of Q-Learning
arXiv:2605.16103v1 [cs.AI] 15 May 2026
Donghwan Lee Department of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) Daejeon 34141, South Korea [email protected] May 18, 2026
Abstract This paper develops a sign-separated finite-time error analysis for constant step-size Qlearning. Starting from the switching-system representation, the error is decomposed into its componentwise negative and positive parts. The negative part is dominated by a lower comparison linear time-invariant (LTI) system associated with a fixed optimal policy, whereas the positive part is controlled by a linear switching system. The resulting bounds show that the negative-side LTI certificate is no slower than the positive-side switching certificate and may produce a faster exponential envelope. The analysis identifies a max-induced asymmetry in Q-learning error dynamics. This asymmetry is connected to overestimation: positive action-wise errors can be selected and propagated by the Bellman maximum, whereas negative errors admit an optimal-policy lower comparison. Finite-time bounds are provided for both deterministic and stochastic constant-step-size recursions.
1
Introduction
Q-learning [30] is a foundational algorithm in reinforcement learning (RL) [23] for solving Markov decision processes (MDPs) with unknown transition kernels. Its convergence has been studied extensively over the past several decades. Classical analyses primarily establish asymptotic convergence [4, 7, 13, 26]. These results are fundamental, but asymptotic convergence alone does not quantify the finite-time progress of the iterates toward the solution. This limitation has motivated a growing body of finite-time convergence analyses, which provide explicit bounds on the iterates’ approach to the optimal Q-function. Recent advances in finite-time analysis include [1, 5, 6, 9, 15, 20, 24, 29]. Most existing results view Q-learning as a nonlinear stochastic approximation scheme [10] and rely on the contraction property of the Bellman optimality operator. An alternative viewpoint treats Q-learning as a discrete-time stochastic switching system [16, 18]. This perspective was developed in [11, 13, 14, 17] and was used to prove finite-time bounds for constant-step-size Q-learning. In that formulation, the error dynamics are affine rather than linear, because the greedy policy selected by the current iterate may differ from an optimal policy. The affine term is controlled through upper and lower comparison systems. The upper comparison system remains a switching system, whereas the lower comparison system can be restricted to optimal-policy modes. Although this comparison-system approach gives valid finite-time bounds, it controls the Q-learning error through auxiliary systems rather than directly exploiting the switching structure of the original error recursion. As a result, intrinsic switching-system quantities such as the joint spectral radius (JSR) [3, 8, 21, 27] are difficult to apply directly to the original Q-learning dynamics. 1
Error e+ k 0
k
−e− k
Figure 1: Schematic sign-separated envelopes. The positive component is certified by the full switching-family rate, whereas the negative component is certified by an optimized fixed-mode LTI rate. The exact switching-system representation removes this obstacle by representing the Bellman maximization error exactly as an average of action-wise Q-errors under a suitably chosen stochastic policy [12]. The corresponding deterministic convergence rate can then be characterized by the JSR of the resulting direct switching family. Because the JSR is the exact worst-case exponential rate of a switched linear family, the direct switching viewpoint provides a sharp drift-based framework for understanding transient Q-learning behavior. This paper refines that viewpoint in [12] by separating the Q-learning error into its componentwise negative and positive parts. The sign separation exposes an asymmetry induced by the Bellman max operator. This asymmetry is closely related to the overestimation mechanism in value-based RL [25, 28]: the maximum can select actions with positive estimation errors, whereas negative errors can be compared against an optimal-policy lower system. The negative side is compared with a fixed LTI system associated with an optimal policy, yielding a certificate with rate ρ⋆− . The positive side is controlled by a linear switching system over the set of deterministic policies, because suboptimal actions with large positive error can enter through the maximization. Its certified rate is ρ+ = ρdir α . Since ρ⋆− ≤ ρ+ , and the inequality can be strict, the finite-time bounds give a certificate-level sense in which negative errors may decay faster than positive errors. The resulting envelopes are illustrated in Figure 1. We first develop the sign-separated comparison systems for the deterministic conditional-mean recursion, where the max-induced residuals and the lower and upper comparison mechanisms are most transparent. We then extend the same sign-separated structure to constant-step-size stochastic Q-learning under an i.i.d. observation model. The finite-time rate certificates use two Lyapunov constructions: a fixed-mode Lyapunov function for the negative-side LTI comparison system and a product-defined JSR Lyapunov function for the positive-side direct switching family. The aim is to provide a switching-system perspective on the convergence behavior of Q-learning. The framework is not meant to replace analyses based on Bellman contractions or stochastic approximation, nor does it assert uniformly improved sample complexity over all problem instances. Instead, the sign-separated direct-switching viewpoint complements existing analyses by identifying the switched drift and by showing when the optimized negative-side rate is sharper than the positiveside direct switching rate. The present paper focuses on the i.i.d. observation model. The method of [12] can be used to extend the analysis to Markovian observations, but the i.i.d. setting keeps the sign-separated switching-system argument transparent.
2
2
Preliminaries
2.1
Notation
We use the following notation. The symbols R, Rn , and Rn×m denote the set of real numbers, the n-dimensional Euclidean space, and the set of n × m real matrices, respectively. For a matrix A, A⊤ denotes its transpose. The identity matrix with appropriate dimensions is denoted by I. For a finite set S, its cardinality is denoted by |S|. The Kronecker product of A and B is denoted by A ⊗ B. For a square matrix A, ρ(A) denotes its spectral radius. For a set Y ⊂ Rn and a vector x ∈ Rn , dist∞ (x, Y) denotes the infinity-norm distance from x to Y: dist∞ (x, Y) := inf y∈Y ∥x − y∥∞ . We write ∆|A| for the probability simplex over a finite n o P|A| action set A: ∆|A| := p ∈ R|A| : pi ≥ 0, p = 1 . Throughout the paper, Arg max denotes i=1 i the set-valued maximizer, while arg max denotes a fixed tie-broken single-valued maximizer. All vector inequalities are understood componentwise unless otherwise stated. For a scalar x, define x+ := max{x, 0}, x− := max{−x, 0}. Thus, x+ is the positive part of x, while x− is the magnitude of the negative part of x. For a vector x, x+ and x− are defined componentwise, and therefore x = x+ − x− ,
|x| = x+ + x− ,
x+ ≥ 0,
x− ≥ 0.
For H = {Ao1 , . . . , AN }, the notation co(H) denotes the convex hull co(H) := nP a finite matrix family PN N i=1 λi Ai : λi ≥ 0, i=1 λi = 1 .
2.2
Switching Systems
Let us consider the discrete-time switched linear system [16, 18, 22] k ∈ {0, 1, 2, . . .},
zk+1 = Aσk zk + ξk ,
where each index i ∈ {1, 2, . . . , M } is called a mode and corresponds to one matrix Ai . The sequence σk ∈ {1, 2, . . . , M } is the switching signal; it specifies which mode is active at time k. Equivalently, saying that mode σk = i is active means that the update from zk to zk+1 uses the dynamics matrix Ai . The prescribed set of all possible mode matrices H := {A1 , A2 , . . . , AM } is called the switching family, and ξk is an additive disturbance. In this paper, a mode denotes the currently applied dynamics matrix; in the Q-learning applications below, modes are induced by policy selectors. When ξk = 0, the deterministic part reduces to k ∈ {0, 1, 2, . . .}.
zk+1 = Aσk zk ,
If the switching family has a single element, say H = {H}, then there is no genuine mode variation and the switched system reduces to the usual linear time-invariant (LTI) recursion zk+1 = Hzk + ξk , or, in the disturbance-free case, zk+1 = Hzk . Thus, LTI systems are included as the singleton-family special case of switching systems. The worst-case exponential rate of a switched linear family is characterized by the joint spectral radius (JSR) [3, 8, 21, 27], defined as follows.
3
Definition 1. For a bounded set of matrices H ⊂ Rm×m , its JSR is denoted by ρ(H) := lim
sup
k→∞ A1 ,...,Ak ∈H
∥Ak · · · A1 ∥1/k ,
where the value is independent of the chosen submultiplicative norm. When H is finite, the supremum for each fixed product length is a maximum over all products generated by matrices in H. If H = {H} consists of a single matrix, then this definition reduces to the usual spectral radius: ρ({H}) = lim ∥H k ∥1/k = ρ(H). k→∞
2.3
Markov Decision Processes
We consider an infinite-horizon discounted Markov decision process (MDP) [19], in which an agent sequentially chooses actions to maximize cumulative discounted rewards. The state and action spaces are finite and are denoted by S := {1, 2, . . . , |S|} and A := {1, 2, . . . , |A|}, respectively. At state s ∈ S, the decision maker selects an action a ∈ A. The next state s′ is drawn according to P (s′ |s, a), and the transition incurs reward r(s, a, s′ ), where r : S × A × S → R. We write r(sk , ak , sk+1 ) =: rk+1 for k ≥ 0. The expected one-step reward is X R(s, a) := E[rk+1 | sk = s, ak = a] = P (s′ |s, a)r(s, a, s′ ). s′ ∈S
A deterministic policy π : S → A maps each state s to an action π(s). Throughout the paper, the discount factor satisfies γ ∈ (0, 1). Let Θ denote the set of all admissible deterministic policies. For a policy π, the Q-function under π is defined as " ∞ # X Qπ (s, a) = E γ k rk+1 s0 = s, a0 = a, π , k=0
for all s ∈ S and a ∈ A. The corresponding value function is V π (s) := Qπ (s, π(s)). The optimal Q-function is Q∗ (s, a) := sup Qπ (s, a), s ∈ S, a ∈ A. π∈Θ ∗ A deterministic policy π ∗ is optimal if Qπ (s, a) = Q∗ (s, a) for all (s, a) ∈ S × A.
Once Q∗ is known, an optimal tie-broken greedy policy can be recovered as π ∗ (s) = arg maxa∈A Q∗ (s, a). The corresponding optimal value function is V ∗ (s) := max Q∗ (s, a). a∈A
For each state s ∈ S, define the set of optimal greedy actions by Φ∗ (s) := Arg maxa∈A Q∗ (s, a). The set of all optimal deterministic policies is then Θ∗ := {π ∈ Θ : π(s) ∈ Φ∗ (s), ∀s ∈ S}. The definition above is equivalent to the usual set of optimal deterministic policies in a finite discounted MDP. If π ∈ Θ∗ , then V ∗ satisfies the Bellman evaluation equation for π. Uniqueness of the discounted evaluation fixed point gives V π = V ∗ , and hence Qπ = Q∗ . Conversely, if π is optimal, then V π = V ∗ , and the policy-evaluation equation implies V ∗ (s) = Q∗ (s, π(s)) for every state. Thus π(s) ∈ Φ∗ (s) for all s, so Θ∗ is exactly the set of optimal deterministic policies. 4
2.4
Definitions
In this paper, we consider a finite discounted Markov decision process (MDP) [19] with state-space S = {1, . . . , |S|}, action-space A = {1, . . . , |A|}, transition probability P (s′ | s, a), real-valued one-step reward r(s, a, s′ ), expected reward X R(s, a) := P (s′ | s, a)r(s, a, s′ ), s′ ∈S
and discount factor γ ∈ (0, 1). State-action functions are viewed as vectors in R|S||A| using the action-block ordering (1, 1), (2, 1), . . . , (|S|, 1), (1, 2), (2, 2), . . . , (|S|, |A|). All matrices and vectors indexed by state-action pairs use this ordering. For Q ∈ R|S||A| , Q(·, 1) .. Q= Q(s, a) = (ea ⊗ es )⊤ Q, , . Q(·, |A|) where es ∈ R|S| and ea ∈ R|A| are the standard basis vectors. Let us define the matrix P1 R(·, 1) .. |S||A| R := , P := ... ∈ R|S||A|×|S| , ∈R . P|A| R(·, |A|) where Pa = P (· | ·, a) ∈ R|S|×|S| . For the finite MDP above, let us define Rmax :=
max
(s,a,s′ )∈S×A×S
|r(s, a, s′ )|.
Because the state and action spaces are finite and rewards are real-valued, Rmax < ∞. Let Θ denote the set of deterministic stationary policies π : S → A. For any stochastic policy µ : S → ∆|A| , we define µ(1)⊤ ⊗ e⊤ 1 µ(2)⊤ ⊗ e⊤ 2 µ Π := ∈ R|S|×|S||A| . .. . µ(|S|)⊤ ⊗ e⊤ |S| For a deterministic policy π ∈ Θ, we use the same notation Ππ by identifying π(s) with its one-hot encoding. Then P Πµ ∈ R|S||A|×|S||A| is the transition matrix of the state-action pair induced by µ. For Q ∈ R|S||A| , define VQ (s) := max Q(s, a), a∈A
VQ := (VQ (1), . . . , VQ (|S|))⊤ .
The Bellman optimality operator is written as F (Q) := R + γP VQ . With this notation, Q∗ is the unique fixed point of F , and V ∗ = VQ∗ . For any Q ∈ R|S||A| , let πQ (s) := arg maxa∈A Q(s, a) denote the tie-broken greedy policy with respect to Q. We also use the shorthand ΠQ := ΠπQ . 5
The advantage function at state s and action a is A∗ (s, a) := V ∗ (s) − Q∗ (s, a) ≥ 0. Consequently, A∗ (s, a) = 0
2.5
a ∈ Φ∗ (s).
⇐⇒
Q-Learning
We consider the standard asynchronous Q-learning recursion [2, 23] with a constant step-size α under an i.i.d. observation model. At step k, a state-action pair (sk , ak ) is sampled independently across k according to P(sk = s, ak = a) = d(s, a) := p(s)b(a | s),
(s, a) ∈ S × A,
where p is a state-sampling distribution and b is a behavior policy. Then s′k ∼ P (· | sk , ak ) is sampled independently conditional on (sk , ak ), and the reward sample is taken as rk+1 := r(sk , ak , s′k ),
k ∈ {0, 1, 2, . . .}.
The asynchronous Q-learning update is Qk+1 (sk , ak ) = Qk (sk , ak ) + α rk+1 + γ max Qk (s′k , u) − Qk (sk , ak ) , u∈A
k ∈ {0, 1, 2, . . .},
All other coordinates (s, a)e(sk , ak ) remain unchanged: Qk+1 (s, a) = Qk (s, a),
(s, a) ̸= (sk , ak ),
k ∈ {0, 1, 2, . . .}.
Let {Fk }k≥0 be the natural filtration of this Q-learning process, F0 := σ(Q0 ),
Fk := σ Q0 , {(st , at , s′t , rt+1 ) : 0 ≤ t ≤ k − 1} ,
k ≥ 1.
Then Qk is Fk -measurable. Moreover, the fresh observation (sk , ak , s′k , rk+1 ) is independent of Fk and is revealed between times k and k + 1. Let D := diag(d(s, a))(s,a)∈S×A ∈ R(|S| |A|)×(|S| |A|) . Write es,a for the standard basis vector corresponding to coordinate (s, a), equivalently ea ⊗ es under the chosen Kronecker ordering. For the sampled coordinate, define the random vector ′ ζk := esk ,ak rk+1 + γ max Qk (sk , u) − Qk (sk , ak ) . u∈A
Since Qk is Fk -measurable and the observation at time k is independent of Fk , E[ζk | Fk ] = D(F (Qk ) − Qk ). Accordingly, the martingale-difference noise is ′ wk := esk ,ak rk+1 + γ max Qk (sk , u) − Qk (sk , ak ) − D(F (Qk ) − Qk ). u∈A
6
(1)
Therefore, the vector form of Q-learning is Qk+1 = Qk + α{D(F (Qk ) − Qk ) + wk },
k ∈ {0, 1, 2, . . .},
where wk is defined in Equation (1). With ek := Qk − Q∗ , the Q-learning error recursion is ek+1 = ek + αD{γP (VQk − V ∗ ) − ek } + αwk ,
k ∈ {0, 1, 2, . . .}.
Assumption 1. The following standing conditions hold throughout the paper. (i) d(s, a) > 0 for every (s, a) ∈ S × A. (ii) The step size satisfies α ∈ (0, 1). (iii) The initial Q-table Q0 ∈ R|S| |A| is deterministic. For the stochastic finite-time analysis, define the uniform noise constant using the reward bound Rmax from Section 2.4: 2 2 p Rmax Rmax + (1 + γ) max ∥Q0 ∥∞ , Wmax := 1 + |S| |A| . (2) 1−γ The conditional moment estimates for wk , wk− , and wk+ are proved in Appendix C.1 from bounded rewards, the boundedness of the iterates, and the i.i.d. observation model. The processes wk− and wk+ need not be martingale differences; the finite-time bounds below use only the fact that their conditional second moments are bounded by Wmax .
3
Deterministic Q-Learning
Before the stochastic Q-learning analysis, we study the corresponding noise-free deterministic analysis. The deterministic recursion is the conditional-mean counterpart of the asynchronous stochastic Q-learning update: Qk+1 = Qk + αD(F (Qk ) − Qk ),
k ∈ {0, 1, 2, . . .}.
With ek := Qk − Q∗ , we have ek+1 = ek + αD{γP (VQk − V ∗ ) − ek },
k ∈ {0, 1, 2, . . .}.
(3)
Since VQk = ΠQk Qk , the deterministic recursion also has the affine switching-system representation [11, 13, 14] Qk+1 = AπQk Qk + αDR, k ∈ {0, 1, 2, . . .}, where, for each deterministic policy π ∈ Θ, Aπ := I − αD + αγDP Ππ . Equivalently, in error coordinates, the error recursion can be written as ek+1 = AπQk ek − αγDP V ∗ − ΠπQk Q∗ , k ∈ {0, 1, 2, . . .}. Thus, deterministic Q-learning is an affine discrete-time switching system whose mode is selected by the greedy policy induced by the current iterate [11, 13, 14]. The affine offset can also be removed exactly by the stochastic-policy linearization of the Bellman maximization error as in [12]. 7
Lemma 1. Along every trajectory of the deterministic recursion, there exists a sequence of stochastic policies {µk }k≥0 such that the deterministic error recursion can be written exactly as the linear switching system ek+1 = Aµk ek ,
Aµk := I − αD + αγDP Πµk ,
k ∈ {0, 1, 2, . . .}.
Moreover, each Aµk belongs to co(Mα ). The corresponding switching family is Mα := {Aπ : π ∈ Θ}. The corresponding JSR is ρdir α := ρ(Mα ).
3.1
Lower and Upper Comparison Systems
We first recall the lower and upper comparison-system framework of [11, 13, 14]. The detailed Bellman-max expansion and residual-sign derivation are given in Appendix C.2. We record only the comparison systems and the resulting order statement. For the lower comparison, choose a single optimal policy whose associated LTI subsystem has the smallest spectral radius: ⋆ π− ∈ arg minπ∈Θ∗ ρ(Aπ ). The minimizer exists because Θ∗ is finite. Define ⋆ , A⋆− := Aπ−
ρ⋆− := ρ(A⋆− ) = min∗ ρ(Aπ ). π∈Θ
Then, the lower comparison system is ℓk+1 = A⋆− ℓk ,
ℓ0 = e0 ,
k ∈ {0, 1, 2, . . .}.
(4)
It corresponds to dropping a nonnegative Bellman-max residual from the exact error identity relative ⋆. to the fixed optimal policy π− For the upper comparison system, let us define the state-wise maximizer of the current error πk+ (s) ∈ arg maxa∈A ek (s, a),
s ∈ S.
Then, the upper comparison system is uk+1 = Aπ+ uk , k
u0 = e0 ,
k ∈ {0, 1, 2, . . .}.
(5)
It corresponds to dropping a nonnegative residual in the opposite direction, where the active mode is selected by the largest state-wise error component. Thus, Equation (4) is a fixed-mode LTI comparison, whereas Equation (5) is a linear switching comparison driven by πk+ . Lemma 2. Under Assumption 1, with ℓk and uk defined in Equations (4) and (5), we have ℓk ≤ ek ≤ uk ,
k ∈ {0, 1, 2, . . .}.
Proof. The proof is provided in Appendix C.2.
8
3.2
Sign Comparison Systems
− The sign comparison systems below follow from the same residual signs. Write ek = e+ k − ek . The lower residual identity gives ⋆ ⋆ − ∗ π− ek+1 = A⋆− e+ k − A− ek + αγDP VQk − V − Π ek ,
where the last term is nonnegative. Indeed, A⋆− e+ k and the residual term are nonnegative, and ≥ A⋆− e− 0. It follows that each coordinate of e k+1 has the form ai − bi , with ai ≥ 0 and bi = k − ⋆ − (A− ek )i ≥ 0. Since (ai − bi ) ≤ bi , we obtain ⋆ − e− k+1 ≤ A− ek .
Similarly, the upper residual identity gives − πk+ ∗ ek+1 = Aπ+ e+ k − Aπ + ek − αγDP Π ek − (VQk − V ) , k
k
where the subtracted residual is nonnegative. Therefore, we similarly obtain + e+ k+1 ≤ Aπ + ek . k
These inequalities lead to the following comparison systems for the negative and positive parts. The detailed one-step proof is included in Appendix C.2. Lemma 3. Under Assumption 1, define − zk+1 = A⋆− zk− ,
z0− = e− 0,
k ∈ {0, 1, 2, . . .},
(6)
+ zk+1 = Aπ+ zk+ ,
z0+ = e+ 0,
k ∈ {0, 1, 2, . . .}.
(7)
and k
Then − e− k ≤ zk ,
+ e+ k ≤ zk ,
k ∈ {0, 1, 2, . . .}.
Proof. The proof is provided in Appendix C.2. The formal deterministic comparison lemmas and their proofs are given in Appendix C.2. These sign-separated recursions are the finite-time objects used below: the negative part evolves under fixed-mode LTI dynamics, whereas the positive part is propagated by switching-system dynamics. The positive-side comparison uses the full switching family M+ α := {Aπ : π ∈ Θ} = Mα , with dir ρ+ := ρ(M+ α ) = ρα .
For comparison with the optimized negative-side LTI certificate, define the optimal-policy switching family ∗ M− α := {Aπ : π ∈ Θ }, with JSR ρ− := ρ(M− α ). Since Θ∗ ⊆ Θ, we have ρ⋆− ≤ ρ− ≤ ρ+ . Thus, the optimized negative-side LTI certificate is no slower than the optimal-policy switching certificate at the level of spectral-radius certificates, and it can be strictly faster than the positive-side direct switching certificate. 9
3.3
Deterministic Finite-Time Rates
We first apply the fixed-mode Lyapunov construction to the negative comparison system. Because this system is LTI, the resulting bound uses the spectral-radius certificate of LTI systems. 3.3.1
Construction of the negative-side fixed-mode Lyapunov function
The Lyapunov construction in this subsection is adapted from [12]. Here it is specialized to the singleton family generated by the optimized negative-side mode A⋆− . We first state the properties of this construction that are used in the finite-time argument. Fix ε > 0 such that β− := ρ⋆− + ε ∈ (0, 1). For each integer T ≥ 0, define ⋆ v−,T (x) :=
T X
−2t β− ∥(A⋆− )t x∥22 ,
x ∈ R|S| |A| .
t=0
Then the following properties hold. (1) For every T ≥ 0, −2 ⋆ ⋆ 2 ⋆ v−,T +1 (x) = ∥x∥2 + β− v−,T (A− x),
∀x ∈ R|S| |A| .
⋆ (λx) = |λ|2 v ⋆ (x), and (2) For every T ≥ 0, every x ∈ R|S| |A| , and every λ ∈ R, we have v−,T −,T ⋆ ⋆ v−,T (x) ≤ v−,T +1 (x). ⋆ > 0, which is the Euclidean norm-equivalence constant associated (3) There exists a constant C− with the fixed-mode negative-side Lyapunov construction, such that
∀x ∈ R|S| |A| ,
⋆ ⋆ ∥x∥22 ≤ v−,T (x) ≤ C− ∥x∥22 ,
∀T ≥ 0.
(4) For every x ∈ R|S| |A| , the limit ⋆ ⋆ v− (x) := lim v−,T (x) = T →∞
∞ X
−2t β− ∥(A⋆− )t x∥22
t=0
exists and is finite. Moreover, ⋆ ⋆ ∥x∥22 ≤ v− (x) ≤ C− ∥x∥22 ,
(5) The function p⋆− (x) :=
∀x ∈ R|S| |A| .
p ⋆ v− (x) is a norm on R|S| |A| .
⋆ satisfies the fixed-mode Lyapunov identity (6) The function v−
⋆ 2 ⋆ 2 ⋆ v− (A⋆− x) = β− v− (x) − ∥x∥22 ≤ β− v− (x),
∀x ∈ R|S| |A| .
Equivalently, p⋆− (A⋆− x) ≤ β− p⋆− (x),
10
∀x ∈ R|S| |A| .
Statements 1–4 ensure that the finite power-based functions converge to a well-defined Lyapunov function uniformly comparable to the Euclidean norm. Statement 5 shows that its square root is a genuine norm. Statement 6 provides the deterministic contraction inequality used for the negative-side fixed LTI comparison system. We now convert the negative sign comparison system into an explicit finite-time bound. The next result applies the fixed-mode Lyapunov identity to the negative-side comparison system and shows that the optimized LTI rate associated with an optimal policy enters the certified envelope. Theorem 1. Assume Assumption 1 and fix ε > 0 such that ρ⋆− + ε < 1, and define β− := ρ⋆− + ε. ⋆ be the fixed-mode Lyapunov function Let v− ⋆ v− (x) :=
∞ X
−2t β− ∥(A⋆− )t x∥22 ,
t=0 ⋆ ≥ 1 be the fixed-mode norm-equivalence constant associated with v ⋆ on R|S| |A| , satisfying and let C− − ⋆ ⋆ ∥x∥22 ≤ v− (x) ≤ C− ∥x∥22 .
Then, for every k ≥ 0, q ⋆ β k ∥e− ∥ . C− − 0 2
∥e− k ∥∞ ≤
(8)
Consequently, the deterministic negative part is certified at the optimized single-policy LTI rate ρ⋆− = min∗ ρ(Aπ ). π∈Θ
Proof. The proof is provided in Appendix C.3. The positive side is handled with the product-defined Lyapunov function for the full direct switching family, since its comparison mode can vary over all deterministic policies. 3.3.2
Construction of the positive-side JSR Lyapunov function
The Lyapunov construction in this subsection is also adapted from [12]. Here it is built from all finite products generated by the positive-side direct family M+ α = {Aπ : π ∈ Θ}. We recall here the properties of the product-defined construction that are used in the finite-time argument. Fix ε > 0 such that β+ := ρ+ + ε ∈ (0, 1). For a sequence of deterministic policies σ = (π0 , . . . , πt−1 ) ∈ Θt , write Aσ := Aπt−1 · · · Aπ0 , 11
and for t = 0 interpret Θ0 as the singleton empty word and Aσ = I. For each integer T ≥ 0, define v+,T (x) :=
T X t=0
−2t β+ max ∥Aσ x∥22 ,
x ∈ R|S| |A| .
σ∈Θt
Then the following properties hold. (1) For every T ≥ 0, −2 v+,T +1 (x) ≥ ∥x∥22 + β+ max v+,T (Aπ x), π∈Θ
∀x ∈ R|S| |A| .
(2) For every T ≥ 0, every x ∈ R|S| |A| , and every λ ∈ R, we have v+,T (λx) = |λ|2 v+,T (x), and v+,T (x) ≤ v+,T +1 (x). (3) There exists a constant C+ > 0, which is the Euclidean norm-equivalence constant associated with the positive-side product-defined JSR Lyapunov construction, such that ∀x ∈ R|S| |A| ,
∥x∥22 ≤ v+,T (x) ≤ C+ ∥x∥22 ,
∀T ≥ 0.
(4) For every x ∈ R|S| |A| , the limit v+ (x) := lim v+,T (x) = T →∞
∞ X
−2t β+
t=0
max
π0 ,...,πt−1 ∈Θ
2
Aπt−1 · · · Aπ0 x 2
exists and is finite. Moreover, ∥x∥22 ≤ v+ (x) ≤ C+ ∥x∥22 , (5) The function p+ (x) :=
∀x ∈ R|S| |A| .
p v+ (x) is a norm on R|S| |A| .
(6) The function v+ satisfies the stronger Lyapunov inequality 2 2 v+ (Aπ x) ≤ β+ v+ (x) − ∥x∥22 ≤ β+ v+ (x), ∀x ∈ R|S| |A| ,
∀π ∈ Θ.
Equivalently, ∀x ∈ R|S| |A| ,
p+ (Aπ x) ≤ β+ p+ (x),
∀π ∈ Θ.
Statements 1–4 ensure that the finite product-based functions converge to a well-defined Lyapunov function uniformly comparable to the Euclidean norm. Statement 5 shows that its square root is a genuine norm. Statement 6 provides the deterministic contraction inequality applied to every positive-side switching family. The same argument gives the positive-side counterpart. Unlike the negative part, the positive part must be controlled uniformly over all deterministic-policy modes; hence the rate is governed by the full direct JSR. Theorem 2. Assume Assumption 1. Fix ε > 0 such that ρ+ + ε < 1, and define β+ := ρ+ + ε. 12
Let v+ be the product-defined JSR Lyapunov function v+ (x) :=
∞ X
−2t β+
t=0
max
π0 ,...,πt−1 ∈Θ
2
Aπt−1 · · · Aπ0 x 2 ,
where the t = 0 product is the identity, and let C+ ≥ 1 be the product-family norm-equivalence constant associated with v+ on R|S| |A| , satisfying ∥x∥22 ≤ v+ (x) ≤ C+ ∥x∥22 . Then, for every k ≥ 0, ∥e+ k ∥∞ ≤
p k C+ β+ ∥e+ 0 ∥2 .
(9)
Consequently, the deterministic positive part is certified at the full direct switching rate ρ+ = ρdir α = ρ({Aπ : π ∈ Θ}). Proof. The proof is provided in Appendix C.3. The two bounds show that the certified upper bound for the negative-part error can converge faster than the certified upper bound for the positive-part error. This comparison concerns upper bounds only; it does not mean that the actual error dynamics must always follow the same trend. The examples in Appendix B illustrate both possibilities: one trajectory exhibits the slower positive-side decay suggested by the certificates, while another trajectory shows that the realized positive and negative errors can decay at the same rate. Corollary 1. Let |S| |A|
R+
:= {x ∈ R|S| |A| : x ≥ 0}.
Under the assumptions of Theorem 1, for every ε > 0 satisfying ρ⋆− + ε < 1, with β− := ρ⋆− + ε and ⋆ associated with v ⋆ on R|S| |A| , every k ≥ 0 with the same fixed-mode norm-equivalence constant C− − satisfies q |S| |A| ⋆ β k ∥e− ∥ . dist∞ (ek , R+ ) ≤ C− − 0 2 Consequently, the deterministic full error iterate ek approaches the nonnegative orthant at the certified exponential rate ρ⋆− , with no stochastic noise floor. Proof. The proof is provided in Appendix C.3. The deterministic analysis therefore assigns the two sides of the error to different finite-time envelopes. The negative part is bounded by the optimized fixed-mode LTI rate ρ⋆− , while the positive part is bounded by the full switching-family rate ρ+ . Since ρ⋆− ≤ ρ+ , the certified convergence bound for the negative part is no slower than, and may be faster than, the corresponding positive-part bound. This is the deterministic core of the sign-separated asymmetry developed further in the stochastic analysis below.
13
4
Stochastic Q-Learning and Sign-Separated Analysis
This section presents the stochastic switching-system form of Q-learning and then introduces the sign-separated lower and upper comparison systems. Since VQk = ΠQk Qk , the stochastic recursion can be written as Qk+1 = AπQk Qk + αDR + αwk , k ∈ {0, 1, 2, . . .}. Equivalently, in error coordinates, the error recursion is ek+1 = AπQk ek − αγDP V ∗ − ΠπQk Q∗ + αwk ,
k ∈ {0, 1, 2, . . .}.
Thus, constant-step-size stochastic Q-learning is an affine stochastic switching system with an additive noise increment. As in the deterministic switching-system representation, the affine offset can be removed by representing the Bellman-max error through a stochastic policy [12]. The following stochastic linear switching-system representation follows the direct switching theory in [12]. Lemma 4. Under the standing Q-learning assumptions, along every trajectory of the stochastic Q-learning recursion, there exists a sequence of Fk -measurable stochastic policies {µk }k≥0 such that the stochastic error recursion can be written exactly as the linear stochastic switching system ek+1 = Aµk ek + αwk ,
Aµk := I − αD + αγDP Πµk ,
k ∈ {0, 1, 2, . . .}.
Moreover, each Aµk belongs to co(Mα ). This representation and the associated lower/upper comparison systems build on the switchingsystem analyses of [11–14]. The Bellman-max sandwich and the deterministic residual identities are the same as in Section 3.1; the only additional term is the stochastic increment αwk . Throughout this section, Qk , ek , the greedy selectors introduced below, and all Bellman-max residuals are Fk -measurable.
4.1
Lower, Upper, and Sign-Separated Comparison Systems
As in the deterministic analysis, the stochastic lower comparison system is an LTI system, whereas the upper comparison system is a linear switching system. The lower stochastic residual identity is ⋆ ek+1 = A⋆− ek + αγDP VQk − V ∗ − Ππ− ek + αwk , k ∈ {0, 1, 2, . . .}, (10) ⋆
where the residual satisfies VQk − V ∗ − Ππ− ek ≥ 0. Accordingly, as in the deterministic lower comparison, we keep the same stochastic increment αwk and remove this nonnegative residual. This gives the optimized lower comparison system ℓk+1 = A⋆− ℓk + αwk ,
ℓ0 = e0 ,
k ∈ {0, 1, 2, . . .}.
(11)
The system in Equation (11) is a fixed-mode LTI comparison system driven by the same noise as the original error recursion; the nonnegative residual removed from Equation (10) is what makes it a lower comparison. For the upper comparison, let us define the predictable state-wise maximizer πk+ (s) ∈ arg maxa∈A ek (s, a),
s ∈ S.
The upper stochastic residual identity is + ek+1 = Aπ+ ek − αγDP Ππk ek − (VQk − V ∗ ) + αwk , k
14
k ∈ {0, 1, 2, . . .},
(12)
+
where Ππk ek − (VQk − V ∗ ) ≥ 0. Removing the subtracted nonnegative residual gives the direct upper comparison system uk+1 = Aπ+ uk + αwk , k
u0 = e0 ,
k ∈ {0, 1, 2, . . .}.
(13)
Unlike the lower comparison, Equation (13) is a linear stochastic switching system, because the mode πk+ can change with the current error. The switching signal πk+ is predictable with respect to the one-step update from time k to time k + 1, because it is Fk -measurable. Lemma 5. Under the standing Q-learning assumptions, with ℓk and uk defined in Equations (11) and (13), we have ℓk ≤ ek ≤ uk , k ∈ {0, 1, 2, . . .}. Proof. The proof is provided in Appendix C.4. The order relations imply − e− k ≤ ℓk ,
+ e+ k ≤ uk ,
k ∈ {0, 1, 2, . . .},
− ⋆ − e− k+1 ≤ A− ek + αwk ,
k ∈ {0, 1, 2, . . .},
+ + e+ k+1 ≤ Aπ + ek + αwk ,
k ∈ {0, 1, 2, . . .}.
and the following inequalities hold:
k
The formal sign-control and one-step domination lemmas are stated and proved in Appendix C.4. These one-step inequalities define the stochastic sign comparison systems used in the finite-time bounds. The negative sign comparison keeps only the fixed-mode LTI propagation of the previous negative part and the negative part of the noise increment: − zk+1 = A⋆− zk− + αwk− ,
z0− = e− 0,
k ∈ {0, 1, 2, . . .}.
(14)
The positive sign comparison keeps the switching propagation selected by πk+ and the positive part of the noise increment: + zk+1 = Aπ+ zk+ + αwk+ , k
z0+ = e+ 0,
k ∈ {0, 1, 2, . . .}.
(15)
The next lemma states that these two auxiliary systems dominate the actual negative and positive parts pathwise. Lemma 6. Under the standing Q-learning assumptions, with zk− and zk+ defined in Equations (14) and (15), for all k ∈ {0, 1, 2, . . .}, − + e− e+ k ≤ zk , k ≤ zk . Proof. The proof is provided in Appendix C.4.
15
4.2
Finite-Time Rates for Sign-Separated Components
We next derive finite-time bounds for the two sign components. The Lyapunov constructions are the same as in the deterministic finite-time analysis; the additional step is to track the stochastic increments. The negative comparison system is the fixed LTI system generated by A⋆− , whereas the positive comparison system is controlled by a switching family. Theorem 3. Assume Assumption 1, and let Wmax be the noise constant defined in Equation (2). Fix ε > 0 such that ρ⋆− + ε < 1, and define β− := ρ⋆− + ε. ⋆ be the fixed-mode Lyapunov function Let v− ⋆ v− (x) :=
∞ X
−2t β− ∥(A⋆− )t x∥22 .
t=0
Then ⋆ 2 ⋆ v− (A⋆− x) = β− v− (x) − ∥x∥22 ,
∀x ∈ R|S| |A| ,
⋆ ≥ 1, the fixed-mode norm-equivalence constant associated with v ⋆ on R|S| |A| , and there exists C− − such that ⋆ ⋆ ∥x∥22 ≤ v− (x) ≤ C− ∥x∥22 .
Then, for every k ≥ 0, q ⋆ β k ∥e− ∥ + αC ⋆ E[∥e− ∥ ] ≤ C− ∞ − − 0 2 k
s
Wmax 2 . 1 − β−
(16)
Consequently, the negative part is certified at the optimized single-policy LTI rate ρ⋆− = min∗ ρ(Aπ ). π∈Θ
Proof. The proof is provided in Appendix C.5. Since the distance to the nonnegative orthant is exactly the infinity norm of the negative part, the previous theorem immediately gives the following orthant-distance estimate. Corollary 2. Let |S| |A|
R+
:= {x ∈ R|S| |A| : x ≥ 0}.
Under the assumptions of Theorem 3, for every ε > 0 satisfying ρ⋆− + ε < 1, with β− := ρ⋆− + ε and ⋆ associated with v ⋆ on R|S| |A| , every k ≥ 0 with the same fixed-mode norm-equivalence constant C− − satisfies s h i q Wmax |S| |A| − k ⋆ ⋆ β ∥e ∥ + αC E dist∞ (ek , R+ ) ≤ C− − 0 2 − 2 . 1 − β− Consequently, the full error iterate ek approaches the nonnegative orthant at the certified exponential rate ρ⋆− = min∗ ρ(Aπ ), π∈Θ
up to the constant-step-size noise floor of order O(α). 16
Proof. The proof is provided in Appendix C.5. The positive component is estimated analogously, except that the Lyapunov function must dominate every product generated by the corresponding switching family instead of the single-mode LTI system. Theorem 4. Assume Assumption 1, and let Wmax be the noise constant defined in Equation (2). Fix ε > 0 such that ρ+ + ε < 1, and define β+ := ρ+ + ε. Let v+ be the product-defined JSR Lyapunov function v+ (x) :=
∞ X t=0
−2t β+
max
π0 ,...,πt−1 ∈Θ
2
Aπt−1 · · · Aπ0 x 2 ,
where the t = 0 product is the identity. Then, for every π ∈ Θ, 2 v+ (Aπ x) ≤ β+ v+ (x) − ∥x∥22 , ∀x ∈ R|S| |A| , and there exists C+ ≥ 1, the product-family norm-equivalence constant associated with v+ on R|S| |A| , such that ∥x∥22 ≤ v+ (x) ≤ C+ ∥x∥22 . Then, for every k ≥ 0, s p k E[∥e+ C+ β+ ∥e+ 0 ∥2 + αC+ k ∥∞ ] ≤
Wmax 2 . 1 − β+
(17)
Consequently, the positive part is certified at the full direct JSR rate ρ+ = ρdir α = ρ({Aπ : π ∈ Θ}). Proof. The proof is provided in Appendix C.5. Combining Theorems 3 and 4, the negative part is certified at the optimized single-policy LTI rate ρ⋆− = min∗ ρ(Aπ ), π∈Θ
whereas the positive part is certified at the full JSR rate ρ+ = ρdir α = ρ({Aπ : π ∈ Θ}). Since ρ⋆− ≤ ρ− ≤ ρ+ , the optimized negative-side LTI certificate is no slower than the optimal-policy switching certificate and can be strictly faster than the positive-side direct switching certificate. This comparison follows from the sign of the Bellman-max residuals: for every optimal policy π ∈ Θ∗ , VQ − V ∗ ≥ Ππ e,
17
Thus, the residual relative to a fixed optimal policy is nonnegative and does not enlarge the negative-part upper comparison. Choosing ⋆ π− ∈ arg minπ∈Θ∗ ρ(Aπ )
therefore gives the fastest spectral-radius certificate among fixed LTI lower comparisons associated with optimal policies. In contrast, the positive side must allow all actions through VQ − V ∗ ≤ max e(s, a), a∈A
Thus, suboptimal actions with positive error can enter the positive-side switching dynamics. This is the structural source of the max-induced overestimation-like asymmetry. These conclusions are structural comparison statements, not a universal positive-bias theorem for Q-learning. They do not by themselves imply E[ek ] ≥ 0 or E[VQk − V ∗ ] ≥ 0. Rather, they show that negative errors are dominated by an optimized LTI comparison associated with an optimal policy, while positive errors may be propagated by the switching family and may also be sustained by the nonnegative residual ⋆ αγDP VQk − V ∗ − Ππ− ek . When ρ⋆− < ρ+ , the negative component has a strictly faster certified exponential envelope than the positive component, although a particular sample path or problem instance need not exhibit strictly faster realized decay of e− k . Under a constant step-size, the stochastic bounds also contain an O(α) noise floor; hence the natural interpretation is entry into a small neighborhood rather than exact convergence to zero in general.
5
Conclusion
This paper developed a sign-separated finite-time analysis of constant-step-size Q-learning from the switching-system viewpoint. By decomposing the error into its negative and positive components, the analysis shows that the Bellman maximum induces different comparison mechanisms on the two sides of the error. The negative component is bounded by an optimized fixed-mode linear system associated with an optimal policy, whereas the positive component requires a switching-system bound over the full deterministic-policy family. The deterministic analysis gives pure exponential envelopes for the two sign components. The stochastic analysis extends the same structure to the i.i.d. observation model and adds the usual constant-step-size noise floor. The results are certificate-level comparison bounds, not a claim that every trajectory must display the same sign-separated trend. The framework complements contraction-based and stochastic-approximation analyses by showing how the Bellman maximum can create asymmetric transient behavior in Q-learning.
References [1] Carolyn L Beck and Rayadurgam Srikant. Error bounds for constant step-size Q-learning. Systems & control letters, 61(12):1203–1208, 2012. [2] Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific Belmont, MA, 1996. [3] 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. 18
[4] Vivek S Borkar and Sean P Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447–469, 2000. [5] Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants. arXiv preprint arXiv:2102.01567, 2021. [6] Eyal Even-Dar and Yishay Mansour. Learning rates for Q-learning. Journal of machine learning Research, 5(Dec):1–25, 2003. [7] Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence of stochastic iterative dynamic programming algorithms. Advances in neural information processing systems, 6, 1993. [8] Raphaël Jungers. The joint spectral radius: Theory and applications, volume 385. Springer Science & Business Media, 2009. [9] Michael Kearns and Satinder Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. Advances in neural information processing systems, 11, 1998. [10] Harold Kushner and G. George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003. [11] Donghwan Lee. Final iteration convergence bound of Q-learning: Switching system approach. IEEE Transactions on Automatic Control, 69(7):4765–4772, 2024. [12] Donghwan Lee. Lyapunov-certified direct switching theory for Q-learning. arXiv preprint arXiv:2604.19569, 2026. [13] Donghwan Lee and Niao He. A unified switching system perspective and convergence analysis of Q-learning algorithms. In 34th Conference on Neural Information Processing Systems, NeurIPS 2020, 2020. [14] Donghwan Lee, Jianghai Hu, and Niao He. A discrete-time switching system analysis of Q-learning. SIAM Journal on Control and Optimization, 61(3):1861–1880, 2023. [15] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. IEEE Transactions on Information Theory, 68(1):448–473, 2021. [16] Daniel Liberzon. Switching in systems and control. Springer Science & Business Media, 2003. [17] Han-Dong Lim and Donghwan Lee. Finite-time analysis of asynchronous Q-learning under diminishing step-size from control-theoretic view. IEEE Access, 12:149916–149939, 2024. [18] 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. [19] Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014. [20] Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Conference on learning theory, pages 3185–3205, 2020.
19
[21] Gian-Carlo Rota and Gilbert Strang. A note on the joint spectral radius. Indag. Math, 22(4): 379–381, 1960. [22] 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. [23] Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT Press, 1998. [24] Csaba Szepesvári. The asymptotic convergence-rate of Q-learning. In Advances in Neural Information Processing Systems, pages 1064–1070, 1998. [25] Sebastian Thrun and Anton Schwartz. Issues in using function approximation for reinforcement learning. In Michael Mozer, Paul Smolensky, David Touretzky, Jeffrey Elman, and Andreas Weigend, editors, Proceedings of the 1993 Connectionist Models Summer School, pages 255–263. Lawrence Erlbaum, 1993. [26] John N Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine learning, 16(3):185–202, 1994. [27] 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. [28] Hado van Hasselt. Double q-learning. In Advances in Neural Information Processing Systems, volume 23, pages 2613–2622. Curran Associates, Inc., 2010. [29] Martin J Wainwright. Stochastic approximation with cone-contractive operators: Sharp l∞ bounds for Q-learning. arXiv preprint arXiv:1905.06265, 2019. [30] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279–292, 1992.
20
Appendix A
Auxiliary Lyapunov constructions
The following lemma records the product-defined Lyapunov construction used in the finite-time arguments. Lemma 7. Let H := {A1 , A2 , . . . , AM } ⊂ Rm×m ,
ρ := ρ(H),
and fix any ε > 0 such that βε := ρ + ε ∈ (0, 1). For a sequence of switching modes σ = (σ1 , . . . , σk ) ∈ {1, . . . , M }k , write Aσ := Aσk · · · Aσ1 , and for k = 0 interpret {1, . . . , M }0 as the singleton empty word and Aσ = I. For each integer t ≥ 0, define t X vεt (x) := βε−2k max ∥Aσ x∥22 , x ∈ Rm . k=0
σ∈{1,2,...,M }k
Then the following statements hold. (1) For every t ≥ 0, vεt+1 (x) ≥ ∥x∥22 + βε−2
vεt (Ai x),
max
i∈{1,...,M }
∀x ∈ Rm .
(2) For every t ≥ 0, every x ∈ Rm , and every λ ∈ R, vεt (λx) = |λ|2 vεt (x),
vεt (x) ≤ vεt+1 (x).
(3) There exists a constant Cε > 0 such that ∥x∥22 ≤ vεt (x) ≤ Cε ∥x∥22 , (4) For every x ∈ Rm , the limit
∀x ∈ Rm ,
∀t ≥ 0.
vε∞ (x) := lim vεt (x) t→∞
exists and is finite. Moreover, ∥x∥22 ≤ vε∞ (x) ≤ Cε ∥x∥22 , (5) The function pε (x) :=
∀x ∈ Rm .
p vε∞ (x) is a norm on Rm .
(6) The function vε∞ satisfies the stronger Lyapunov inequality vε∞ (Ai x) ≤ βε2 vε∞ (x) − ∥x∥22 ≤ βε2 vε∞ (x), ∀x ∈ Rm ,
∀i ∈ {1, . . . , M }.
Equivalently, pε (Ai x) ≤ βε pε (x),
∀x ∈ Rm , 21
∀i ∈ {1, . . . , M }.
Proof. For each k ≥ 0, set ak :=
max
σ∈{1,2,...,M }k
∥Aσ ∥2 ,
where a0 = 1. Since βε > ρ(H), the definition of the JSR implies that Cε :=
∞ X
βε−2k a2k
k=0
is finite. Hence vεt (x) ≤
t X
βε−2k a2k ∥x∥22 ≤ Cε ∥x∥22 .
k=0
The lower bound follows from the k = 0 term, which is ∥x∥22 . This proves Statement 3. Statement 2 follows from homogeneity of the Euclidean norm and from the fact that vεt+1 is obtained from vεt by adding one nonnegative term. For Statement 1, fix i ∈ {1, . . . , M }. For every k ≥ 0, each product Aσ Ai , with σ ∈ {1, . . . , M }k , is a product of length k + 1 from H. Therefore βε−2 vεt (Ai x) = ≤
t X k=0 t+1 X
βε−2(k+1) βε−2r
r=1
max
σ∈{1,...,M }k
max
τ ∈{1,...,M }r
∥Aσ Ai x∥22
∥Aτ x∥22
= vεt+1 (x) − ∥x∥22 . Taking the maximum over i gives Statement 1. Statement 4 follows because vεt (x) is monotone nondecreasing in t and uniformly bounded above by Statement 3. For Statement 5, define gk (x) := βε−k
max
σ∈{1,...,M }k
∥Aσ x∥2 ,
k ≥ 0.
Each gk is a seminorm and g0 (x) = ∥x∥2 is a norm. Since pε (x) = ∥(g0 (x), g1 (x), . . .)∥ℓ2 , positivity follows from g0 , homogeneity is immediate, and the triangle inequality follows from the triangle inequality for each gk and Minkowski’s inequality in ℓ2 . Consequently, pε is a norm. Finally, applying Statement 1 and passing to the limit t → ∞ gives vε∞ (x) ≥ ∥x∥22 + βε−2
max
i∈{1,...,M }
vε∞ (Ai x).
This is equivalent to Statement 6, and taking square roots gives the norm inequality.
B
Examples
The first example shows a case in which the positive component realizes the slower certificate rate. Example 1. The following one-state, two-action example shows that the positive part can have a strictly slower realized decay than the negative part, and also that the certificate rates can satisfy ρ⋆− < ρ+ . Let S = {1} and A = {1, 2}, and let both actions be self-loops: P (1 | 1, 1) = P (1 | 1, 2) = 1. Let R(1, 1) = R(1, 2) = 0, γ = 0.9, and α ∈ (0, 1), and use the sampling distribution d(1, 1) = 0.9,
d(1, 2) = 0.1. 22
Then Q∗ (1, 1) = Q∗ (1, 2) = 0. It follows that both actions are optimal and Θ∗ = {π1 , π2 },
πi (1) = i,
i ∈ {1, 2}.
With the ordering (1, 1), (1, 2), write xk Qk (1, 1) ek = = . yk Qk (1, 2) The selection matrices are Ππ1 = 1 0 , and
Ππ2 = 0 1 ,
0.9 0 D= . 0 0.1
Therefore the two direct modes are 1 − 0.09α 0 A1 := Aπ1 = , 0.09α 1 − 0.1α
1 − 0.9α 0.81α A2 := Aπ2 = . 0 1 − 0.01α
Since these matrices are triangular, their spectral radii are ρ(A1 ) = 1 − 0.09α,
ρ(A2 ) = 1 − 0.01α.
Therefore, the optimized negative-side LTI certificate is ρ⋆− = min∗ ρ(Aπ ) = 1 − 0.09α. π∈Θ
On the other hand, ∥A1 ∥∞ = ∥A2 ∥∞ = 1 − 0.01α, hence ρ({A1 , A2 }) ≤ 1 − 0.01α. Since A2 itself has spectral radius 1 − 0.01α, we also have ρ({A1 , A2 }) ≥ 1 − 0.01α. Consequently, ρ+ = ρ({A1 , A2 }) = 1 − 0.01α, and hence ρ⋆− = 1 − 0.09α < 1 − 0.01α = ρ+ . Choose
−A e0 = , B
A > 0,
B > 0.
If yk > xk , then the Bellman max selects action 2, and the recursion is ek+1 = A2 ek ,
k ∈ {0, 1, 2, . . .}. 23
Solving this triangular recursion gives yk = B(1 − 0.01α)k , and
81 81 k xk = B(1 − 0.01α) − A + B (1 − 0.9α)k . 89 89
Moreover, 8 81 k yk − xk = B(1 − 0.01α) + A + B (1 − 0.9α)k > 0 89 89 for every k ≥ 0. Hence the branch ek+1 = A2 ek is valid for all k ≥ 0. Since yk > 0 and yk > xk , the positive part satisfies k ∥e+ k ∥∞ = yk = B(1 − 0.01α) . The negative part is + ∥e− k ∥∞ = (−xk ) =
+ 81 81 k k , A + B (1 − 0.9α) − B(1 − 0.01α) 89 89
and therefore ∥e− k ∥∞ ≤
81 A + B (1 − 0.9α)k . 89
Consequently, on this deterministic trajectory, the positive part decays exactly at the slow factor 1 − 0.01α, whereas the negative part is bounded by the faster (1 − 0.9α)-geometric term and eventually vanishes. The second example clarifies that the certificate asymmetry need not force different realized decay rates on every trajectory. Example 2. The comparison rates above are certificate rates, and they need not imply that one sign component has a strictly faster realized decay on every deterministic trajectory. The following two-state, two-action example gives a simple trajectory on which the positive and negative errors have exactly the same magnitude and the same decay factor. Let S = {1, 2} and A = {1, 2}. For every state and action, let the transition be a self-loop, P (s | s, i) = 1,
s ∈ {1, 2}, i ∈ {1, 2},
and let the rewards be R(s, 2) = −1,
R(s, 1) = 0,
s ∈ {1, 2}.
Then V ∗ (s) = 0,
Q∗ (s, 1) = 0,
Q∗ (s, 2) = −1,
hence action 1 is the unique optimal action in each state and the action gap of action 2 is equal to one. Consider the deterministic recursion Equation (3) with uniform sampling 1 d(s, i) = , 4
s ∈ {1, 2}, i ∈ {1, 2},
step size α ∈ (0, 1), and discount factor γ = 0.9. With the ordering (1, 1), (2, 1), (1, 2), (2, 2), 24
choose e0 = (c, −c, c, −c),
c > 0.
The deterministic error remains on the one-dimensional symmetric trajectory ek = (xk , −xk , xk , −xk ). To verify this, suppose the identity holds at time k. In state 1, Qk (1, 2) = −1 + xk ,
Qk (1, 1) = xk , and hence VQk (1) − V ∗ (1) = xk . In state 2, Qk (2, 1) = −xk ,
Qk (2, 2) = −1 − xk ,
and hence VQk (2) − V ∗ (2) = −xk . Therefore, for each i ∈ {1, 2}, α α(1 − γ) ek+1 (1, i) = xk + (γxk − xk ) = 1 − xk , 4 4 α(1 − γ) α xk , ek+1 (2, i) = −xk + (−γxk + xk ) = − 1 − 4 4 for k ∈ {0, 1, 2, . . .}. Since γ = 0.9, 1−
α(1 − γ) = 1 − 0.025α. 4
Therefore, xk = (1 − 0.025α)k c,
ek = (1 − 0.025α)k (c, −c, c, −c).
Consequently, k e− k = (1 − 0.025α) (0, c, 0, c),
k e+ k = (1 − 0.025α) (c, 0, c, 0),
and hence − k ∥e+ k ∥∞ = ∥ek ∥∞ = (1 − 0.025α) c,
while − ∥e+ k ∥2 = ∥ek ∥2 =
√
2 (1 − 0.025α)k c.
For this trajectory, the Bellman-max residuals vanish. The realized positive and negative sign components therefore decay with exactly the same factor. This does not contradict the comparison results above; it shows only that the certified sign-separated asymmetry is a property of the available comparison envelopes, not a statement that every deterministic trajectory must exhibit strictly faster + realized decay of e− k than of ek .
C
Proofs
C.1
Noise moment bounds
We begin the noise analysis with the boundedness and martingale-difference estimates needed later.
25
Lemma 8. Under Assumption 1, let Rmax := max′ |r(s, a, s′ )|, s,a,s
and define 2 2 p Rmax Rmax + (1 + γ) max ∥Q0 ∥∞ , Wmax := 1 + |S| |A| . 1−γ
Then, for every k ∈ {0, 1, 2, . . .},
Rmax ∥Qk ∥∞ ≤ max ∥Q0 ∥∞ , 1−γ
,
and the increment wk is Fk+1 -measurable and satisfies E[wk | Fk ] = 0,
E[∥wk ∥22 | Fk ] ≤ Wmax .
Proof of Lemma 8. Since the state and action spaces are finite, Rmax < ∞. We first prove the pathwise bound on Qk . Suppose Rmax ∥Qk ∥∞ ≤ max ∥Q0 ∥∞ , . 1−γ If a coordinate is not sampled, it remains unchanged. If (sk , ak ) is sampled, then |Qk+1 (sk , ak )| ≤ (1 − α)|Qk (sk , ak )| + α |rk+1 | + γ max |Qk (s′k , u)| u Rmax Rmax ≤ (1 − α) max ∥Q0 ∥∞ , + α(Rmax + γ max ∥Q0 ∥∞ , ). 1−γ 1−γ o o n o n n max max max ≥ Rmax /(1 − γ), then Rmax + γ max ∥Q0 ∥∞ , R1−γ ≤ max ∥Q0 ∥∞ , R1−γ If max ∥Q0 ∥∞ , R1−γ , n o max and therefore |Qk+1 (sk , ak )| ≤ max ∥Q0 ∥∞ , R1−γ . Since the other coordinates remain bounded o n o n max max , induction gives ∥Qk ∥∞ ≤ max ∥Q0 ∥∞ , R1−γ for all k ≥ 0. by max ∥Q0 ∥∞ , R1−γ The sample temporal-difference term satisfies Rmax ′ rk+1 + γ max Qk (sk , u) − Qk (sk , ak ) ≤ Rmax + (1 + γ) max ∥Q0 ∥∞ , . u∈A 1−γ Also, for every coordinate, R(s, a) + γ
Rmax P (s | s, a)VQk (s ) − Qk (s, a) ≤ Rmax + (1 + γ) max ∥Q0 ∥∞ , . 1−γ ′
X s
′
′
Because 0 < d(s, a) ≤ 1, this implies p Rmax ∥D(F (Qk ) − Qk )∥2 ≤ |S| |A| Rmax + (1 + γ) max ∥Q0 ∥∞ , . 1−γ n o max The sampled vector in Equation (1) has Euclidean norm at most Rmax + (1 + γ) max ∥Q0 ∥∞ , R1−γ . Hence, pathwise, p Rmax ∥wk ∥2 ≤ 1 + |S| |A| Rmax + (1 + γ) max ∥Q0 ∥∞ , , 1−γ 26
and therefore 2 2 p Rmax Rmax + (1 + γ) max ∥Q0 ∥∞ , E[∥wk ∥22 | Fk ] ≤ 1 + |S| |A| = Wmax . 1−γ The Fk+1 -measurability follows from the fact that the fresh observation is revealed between times k and k + 1, while D(F (Qk ) − Qk ) is Fk -measurable. Finally, using conditional independence of the fresh observation from Fk , E esk ,ak rk+1 + γ max Qk (s′k , u) − Qk (sk , ak ) Fk u∈A ! XX X P (s′ | s, a)VQk (s′ ) − Qk (s, a) = d(s, a)es,a R(s, a) + γ s′ ∈S
s∈S a∈A
= D(F (Qk ) − Qk ). Together with the definition of wk , this gives E[wk | Fk ] = 0. The next lemma transfers the same second-moment control to the positive and negative noise components. Lemma 9. Under the conditions of Lemma 8, for every k ∈ {0, 1, 2, . . .}, E[∥wk− ∥22 | Fk ] ≤ Wmax ,
E[∥wk+ ∥22 | Fk ] ≤ Wmax .
Proof of Lemma 9. Componentwise, − 2 2 0 ≤ (wk,i ) ≤ wk,i ,
+ 2 2 0 ≤ (wk,i ) ≤ wk,i .
− + 2 − 2 + 2 . If w 2 Indeed, if wk,i ≥ 0, then wk,i = 0 and (wk,i ) = wk,i k,i < 0, then (wk,i ) = wk,i and wk,i = 0. 2 . Summing over coordinates gives Hence each signed-part square is either zero or exactly wk,i ∥wk− ∥22 ≤ ∥wk ∥22 and ∥wk+ ∥22 ≤ ∥wk ∥22 . Taking conditional expectations and applying Lemma 8 proves the claim.
C.2
Deterministic comparison lemmas
For any Q and e = Q − Q∗ , the Bellman-max term can be expanded state by state as VQ (s) − V ∗ (s) = max{Q∗ (s, a) + e(s, a)} − V ∗ (s) a∈A
= max{e(s, a) − A∗ (s, a)}. a∈A
If π ∈ Θ∗ , then A∗ (s, π(s)) = 0, and therefore VQ − V ∗ − Ππ e ≥ 0. For the upper comparison, if π + (s) ∈ arg maxa∈A e(s, a), then A∗ (s, a) ≥ 0 gives +
Ππ e − (VQ − V ∗ ) ≥ 0. Substituting these two decompositions into the deterministic error recursion produces the lower and upper residual identities below. The first deterministic comparison lemma records the lower residual identity and its sign. 27
Lemma 10. Under Assumption 1, the deterministic error recursion satisfies ⋆ k ∈ {0, 1, 2, . . .}, ek+1 = A⋆− ek + αγDP VQk − V ∗ − Ππ− ek , and
⋆
VQk − V ∗ − Ππ− ek ≥ 0. ⋆ ∈ Θ∗ , we have Q∗ (s, π ⋆ (s)) = V ∗ (s). Hence Proof of Lemma 10. For each state s, because π− − ⋆ ⋆ (s)) = max{Q∗ (s, a) + ek (s, a)} − V ∗ (s) − ek (s, π− (s)) VQk (s) − V ∗ (s) − ek (s, π− a∈A ∗
⋆ ⋆ ⋆ ≥ Q (s, π− (s)) + ek (s, π− (s)) − V ∗ (s) − ek (s, π− (s))
= 0. Using
⋆
⋆
VQk − V ∗ = Ππ− ek + VQk − V ∗ − Ππ− ek
in Equation (3), we obtain ⋆
ek+1 = ek + αD{γP Ππ− ek − ek } ⋆ + αγDP VQk − V ∗ − Ππ− ek ⋆ ⋆ = I − αD + αγDP Ππ− ek + αγDP VQk − V ∗ − Ππ− ek ⋆ = A⋆− ek + αγDP VQk − V ∗ − Ππ− ek . This proves the lower residual identity. The next lemma records the corresponding upper residual identity. Lemma 11. Under Assumption 1, the deterministic error recursion satisfies + ek+1 = Aπ+ ek − αγDP Ππk ek − (VQk − V ∗ ) , k ∈ {0, 1, 2, . . .}, k
where πk+ (s) ∈ arg maxa∈A ek (s, a), and
s ∈ S,
+
Ππk ek − (VQk − V ∗ ) ≥ 0. Proof of Lemma 11. Since A∗ (s, a) = V ∗ (s) − Q∗ (s, a) ≥ 0, we have VQk (s) − V ∗ (s) = max{ek (s, a) − A∗ (s, a)} ≤ max ek (s, a) = ek (s, πk+ (s)). a∈A
Therefore, Π
πk+
a∈A
ek − (VQk − V ∗ ) ≥ 0. Using +
+
VQk − V ∗ = Ππk ek − Ππk ek − (VQk − V ∗ )
in Equation (3), we obtain +
ek+1 = ek + αD{γP Ππk ek − ek } + − αγDP Ππk ek − (VQk − V ∗ ) + + = I − αD + αγDP Ππk ek − αγDP Ππk ek − (VQk − V ∗ ) + = Aπ+ ek − αγDP Ππk ek − (VQk − V ∗ ) . k
This proves the upper residual identity. Combining the two one-sided comparisons gives the main deterministic order statement. 28
Restatement of Lemma 2. Under Assumption 1, with ℓk and uk defined in Equations (4) and (5), ℓk ≤ ek ≤ uk , k ∈ {0, 1, 2, . . .}. Proof of Lemma 2. We prove the two inequalities directly from the residual identities. First, set δk := ek − ℓk . Using Lemma 10 and the lower comparison recursion in Equation (4), we obtain δk+1 = ek+1 − ℓk+1 h i ⋆ = A⋆− ek + αγDP VQk − V ∗ − Ππ− ek − A⋆− ℓk ⋆ = A⋆− (ek − ℓk ) + αγDP VQk − V ∗ − Ππ− ek ⋆ = A⋆− δk + αγDP VQk − V ∗ − Ππ− ek . Since δ0 = e0 − ℓ0 = 0, A⋆− ≥ 0, D ≥ 0, P ≥ 0, and ⋆
VQk − V ∗ − Ππ− ek ≥ 0, induction gives δk ≥ 0, that is, ℓk ≤ ek ,
k ∈ {0, 1, 2, . . .}.
Second, set qk := uk − ek . Using Lemma 11 and the upper comparison recursion in Equation (5), we obtain qk+1 = uk+1 − ek+1 h i + = Aπ+ uk − Aπ+ ek − αγDP Ππk ek − (VQk − V ∗ ) k k + = Aπ+ (uk − ek ) + αγDP Ππk ek − (VQk − V ∗ ) k + = Aπ+ qk + αγDP Ππk ek − (VQk − V ∗ ) . k
Since q0 = u0 − e0 = 0, Aπ+ ≥ 0, D ≥ 0, P ≥ 0, and k
+
Ππk ek − (VQk − V ∗ ) ≥ 0, induction gives qk ≥ 0, that is, ek ≤ uk ,
k ∈ {0, 1, 2, . . .}.
Combining the two inequalities yields ℓk ≤ ek ≤ uk ,
k ∈ {0, 1, 2, . . .}.
The following lemma connects these order comparisons to the componentwise sign parts. 29
Lemma 12. Under Assumption 1, with ℓk and uk defined in Equations (4) and (5), − e− k ≤ ℓk ,
+ e+ k ≤ uk ,
k ∈ {0, 1, 2, . . .}.
Proof of Lemma 12. Fix a coordinate i and a time k. From Lemma 2, ℓk,i ≤ ek,i ≤ uk,i . The positive-part map x 7→ x+ = max{x, 0} is monotone increasing on R. Therefore, the upper comparison inequality gives + + + e+ k,i = (ek,i ) ≤ (uk,i ) = uk,i . For the negative part, the lower comparison inequality ℓk,i ≤ ek,i implies −ek,i ≤ −ℓk,i . Applying the same monotonicity to the positive-part map gives − + + e− k,i = (−ek,i ) ≤ (−ℓk,i ) = ℓk,i .
Since the coordinate i was arbitrary, these scalar inequalities hold componentwise, and hence − e− k ≤ ℓk ,
+ e+ k ≤ uk ,
k ∈ {0, 1, 2, . . .}.
The next lemma gives the one-step sign domination that drives the sign-separated systems. Lemma 13. Under Assumption 1, the deterministic negative part satisfies ⋆ − e− k+1 ≤ A− ek ,
k ∈ {0, 1, 2, . . .},
and the deterministic positive part satisfies + e+ k+1 ≤ Aπ + ek ,
k ∈ {0, 1, 2, . . .}.
k
− Proof of Lemma 13. From Lemma 10 and ek = e+ k − ek , − ⋆ − ek+1 = A⋆− e+ k − A− ek + rk ,
⋆ rk− := αγDP VQk − V ∗ − Ππ− ek ≥ 0.
− Because A⋆− ≥ 0 and e+ k , ek ≥ 0, the vectors − ⋆ + a− k := A− ek + rk ,
⋆ − b− k := A− ek
− are nonnegative and satisfy ek+1 = a− k − bk . Hence, component by component, − + − (ek+1,i )− = (b− k,i − ak,i ) ≤ bk,i .
Thus, − ⋆ − e− k+1 ≤ bk = A− ek .
Similarly, from Lemma 11, − + ek+1 = Aπ+ e+ k − Aπ + ek − rk , k
k
+ rk+ := αγDP Ππk ek − (VQk − V ∗ ) ≥ 0. 30
Set − + b+ k := Aπ + ek + rk .
+ a+ k := Aπ + ek ,
k
k
+ + + Then a+ k , bk ≥ 0 and ek+1 = ak − bk . Hence + + + (ek+1,i )+ = (a+ k,i − bk,i ) ≤ ak,i ,
which yields + + e+ k+1 ≤ ak = Aπ + ek . k
The pathwise deterministic sign comparison now follows by induction. Restatement of Lemma 3. Under Assumption 1, if zk− and zk+ are defined by Equations (6) and (7), then − + e− e+ k ∈ {0, 1, 2, . . .}. k ≤ zk , k ≤ zk , Proof of Lemma 3. At k = 0, the inequalities hold by definition. If they hold at time k, then Lemma 13 and the nonnegativity of A⋆− and Aπ+ give the inequalities at time k + 1. The result k follows by induction.
C.3
Deterministic finite-time proofs
We now prove the deterministic negative-side finite-time bound. Restatement of Theorem 1. Assume Assumption 1. Fix ε > 0 such that ρ⋆− + ε < 1, and define β− := ρ⋆− + ε. Let ⋆ v− (x) :=
∞ X
−2t β− ∥(A⋆− )t x∥22 ,
t=0 ⋆ ≥ 1 be the fixed-mode norm-equivalence constant associated with v ⋆ on R|S| |A| , and let C− − satisfying ⋆ ⋆ ∥x∥22 ≤ v− (x) ≤ C− ∥x∥22 .
Then, for every k ≥ 0, ∥e− k ∥∞ ≤
q ⋆ β k ∥e− ∥ . C− − 0 2
Consequently, the deterministic negative part is certified at the optimized single-policy LTI rate ρ⋆− = min∗ ρ(Aπ ). π∈Θ
⋆ give Proof of Theorem 1. For the negative side, Equation (6) and the definition of v− − ⋆ ⋆ 2 ⋆ v− (zk+1 ) = v− (A⋆− zk− ) ≤ β− v− (zk− ).
31
Iterating and using z0− = e− 0, ⋆ 2k ⋆ − ⋆ 2k − 2 v− (zk− ) ≤ β− v− (e0 ) ≤ C− β− ∥e0 ∥2 .
By Lemma 3, − − ∥e− k ∥∞ ≤ ∥zk ∥∞ ≤ ∥zk ∥2 ≤
q ⋆ (z − ), v− k
which proves Equation (8). The positive-side deterministic bound uses the product-defined switching Lyapunov function. Restatement of Theorem 2. Assume Assumption 1. Fix ε > 0 such that ρ+ + ε < 1, and define β+ := ρ+ + ε. Let v+ (x) :=
∞ X t=0
−2t β+
max
π0 ,...,πt−1 ∈Θ
2
Aπt−1 · · · Aπ0 x 2 ,
where the t = 0 product is the identity, and let C+ ≥ 1 be the product-family norm-equivalence constant associated with v+ on R|S| |A| , satisfying ∥x∥22 ≤ v+ (x) ≤ C+ ∥x∥22 . Then, for every k ≥ 0, ∥e+ k ∥∞ ≤
p k C+ β+ ∥e+ 0 ∥2 .
Consequently, the deterministic positive part is certified at the full direct switching rate ρ+ = ρdir α = ρ({Aπ : π ∈ Θ}). Proof of Theorem 2. The product-defined Lyapunov function satisfies 2 v+ (Aπ x) ≤ β+ v+ (x),
∀π ∈ Θ.
Therefore, along the deterministic switching signal πk+ , + 2 v+ (zk+1 ) = v+ (Aπ+ zk+ ) ≤ β+ v+ (zk+ ). k
Iterating and using z0+ = e+ 0, 2k 2k + 2 v+ (zk+ ) ≤ β+ v+ (e+ 0 ) ≤ C+ β+ ∥e0 ∥2 .
By Lemma 3, + + ∥e+ k ∥∞ ≤ ∥zk ∥∞ ≤ ∥zk ∥2 ≤
q v+ (zk+ ),
which proves Equation (9). The deterministic orthant-distance estimate is an immediate consequence of the negative-part bound.
32
Restatement of Corollary 1. Let |S| |A|
R+
:= {x ∈ R|S| |A| : x ≥ 0}.
Under the assumptions of Theorem 1, for every ε > 0 satisfying ρ⋆− + ε < 1, with β− := ρ⋆− + ε ⋆ associated with v ⋆ on R|S| |A| , and with the same fixed-mode norm-equivalence constant C− − every k ≥ 0 satisfies q |S| |A| ⋆ β k ∥e− ∥ . dist∞ (ek , R+ ) ≤ C− − 0 2 Proof of Corollary 1. Let n := |S| |A|. We first compute the distance to the nonnegative orthant. For any x ∈ Rn and any y ∈ Rn+ , if xi < 0, then yi ≥ 0 and therefore |xi − yi | ≥ −xi = x− i . Taking the maximum over coordinates and then the infimum over y ∈ Rn+ gives dist∞ (x, Rn+ ) = infn ∥x − y∥∞ ≥ ∥x− ∥∞ . y∈R+
On the other hand, choose y = x+ ∈ Rn+ . Since x − x+ = −x− , we have dist∞ (x, Rn+ ) ≤ ∥x − x+ ∥∞ = ∥x− ∥∞ . Thus dist∞ (x, Rn+ ) = ∥x− ∥∞ . Applying this identity with x = ek gives dist∞ (ek , Rn+ ) = ∥e− k ∥∞ . Finally, Equation (8) yields dist∞ (ek , Rn+ ) = ∥e− k ∥∞ ≤
q ⋆ β k ∥e− ∥ , C− − 0 2
which proves the claim.
C.4
Stochastic comparison lemmas
The first stochastic comparison lemma adds the Q-learning noise term to the deterministic residual identities. Lemma 14. Under the standing Q-learning assumptions, the Q-learning error satisfies Equations (10) and (12), with the residual inequalities stated there. Proof of Lemma 14. The deterministic identities in Lemmas 10 and 11 gain only the additive term αwk in the stochastic recursion. This proves Equations (10) and (12). The stochastic lower and upper comparisons follow because the shared noise cancels in the difference recursions. 33
Restatement of Lemma 5. Define the optimized lower comparison system ℓk+1 = A⋆− ℓk + αwk ,
ℓ0 = e0 ,
k ∈ {0, 1, 2, . . .},
u0 = e0 ,
k ∈ {0, 1, 2, . . .}.
and the direct upper comparison system uk+1 = Aπ+ uk + αwk , k
Then ℓk ≤ ek ≤ uk ,
k ∈ {0, 1, 2, . . .}.
Proof of Lemma 5. Subtracting Equation (11) from Equation (10) yields ⋆ ek+1 − ℓk+1 = A⋆− (ek − ℓk ) + αγDP VQk − V ∗ − Ππ− ek . The noise cancels. Since e0 − ℓ0 = 0, all factors are nonnegative, and the residual is nonnegative, induction gives ℓk ≤ ek . Subtracting Equation (12) from Equation (13) gives + uk+1 − ek+1 = Aπ+ (uk − ek ) + αγDP Ππk ek − (VQk − V ∗ ) . k
The noise again cancels. Since u0 −e0 = 0, all factors are nonnegative, and the residual is nonnegative, induction gives ek ≤ uk . The next lemma converts the stochastic order comparisons into sign-part inequalities. Lemma 15. Under the standing Q-learning assumptions, with ℓk and uk defined in Equations (11) and (13), − + e− e+ k ∈ {0, 1, 2, . . .}. k ≤ ℓk , k ≤ uk , − + + Proof of Lemma 15. Since ℓk ≤ ek , we have −ek ≤ −ℓk , and hence e− k = (−ek ) ≤ (−ℓk ) = ℓk . + Since ek ≤ uk , monotonicity of the componentwise positive-part map gives e+ k ≤ uk .
The following one-step estimate separates the deterministic propagation from the signed noise increments. Lemma 16. Under the standing Q-learning assumptions, the negative part satisfies − ⋆ − e− k+1 ≤ A− ek + αwk ,
k ∈ {0, 1, 2, . . .}.
+ + e+ k+1 ≤ Aπ + ek + αwk ,
k ∈ {0, 1, 2, . . .}.
The positive part satisfies k
− Proof of Lemma 16. From Equation (10) and ek = e+ k − ek , − ⋆ − ek+1 = A⋆− e+ k − A− ek + rk + αwk ,
⋆ rk− := αγDP VQk − V ∗ − Ππ− ek ≥ 0.
− The nonnegative vector A⋆− e+ k + rk cannot increase the negative part. Componentwise, ⋆ − e− k+1 ≤ A− ek − αwk
34
+
.
+ ⋆ − − Since A⋆− e− k ≥ 0, the scalar inequality (a − ξ) ≤ a + ξ for a ≥ 0, applied with a = (A− ek )i and ξ = αwk,i , gives − ⋆ − e− k+1 ≤ A− ek + αwk .
Similarly, from Equation (12), + rk+ := αγDP Ππk ek − (VQk − V ∗ ) ≥ 0.
− + ek+1 = Aπ+ e+ k − Aπ + ek − rk + αwk , k
k
+ The nonnegative vector Aπ+ e− k + rk cannot increase the positive part; hence k
+ + e+ ≤ A + αw . +e k k+1 π k k
≥ 0, the scalar inequality (a + ξ)+ ≤ a + ξ + for a ≥ 0, applied componentwise, proves Since Aπ+ e+ k k + + e+ k+1 ≤ Aπ + ek + αwk . k
The pathwise stochastic sign comparison is obtained by iterating the one-step estimates. Restatement of Lemma 6. Define the sign comparison systems − = A⋆− zk− + αwk− , zk+1
z0− = e− 0,
k ∈ {0, 1, 2, . . .},
+ zk+1 = Aπ+ zk+ + αwk+ ,
z0+ = e+ 0,
k ∈ {0, 1, 2, . . .}.
and k
Then, for all k ∈ {0, 1, 2, . . .}, − e− k ≤ zk ,
+ e+ k ≤ zk .
Proof of Lemma 6. At k = 0, the inequalities hold by definition. If they hold at time k, then Lemma 16 and the nonnegativity of A⋆− and Aπ+ give k
− − ⋆ − e− k+1 ≤ A− zk + αwk = zk+1 ,
and + + + e+ k+1 ≤ Aπ + zk + αwk = zk+1 . k
The result follows by induction.
C.5
Stochastic finite-time proofs
We next prove the stochastic finite-time bound for the negative component. Restatement of Theorem 3. Assume Assumption 1, and let Wmax be defined as in Lemma 8. Fix ε > 0 such that ρ⋆− + ε < 1, and define β− := ρ⋆− + ε. Let ⋆ v− (x) :=
∞ X
−2t β− ∥(A⋆− )t x∥22 .
t=0
35
Then ⋆ 2 ⋆ v− (A⋆− x) = β− v− (x) − ∥x∥22 ,
∀x ∈ R|S| |A| ,
⋆ ≥ 1, the fixed-mode norm-equivalence constant associated with v ⋆ on R|S| |A| , and there exists C− − such that ⋆ ⋆ ∥x∥22 ≤ v− (x) ≤ C− ∥x∥22 .
Then, for every k ≥ 0, q ⋆ β k ∥e− ∥ + αC ⋆ E[∥e− ∥ ] ≤ C− ∞ − 0 2 − k
s
Wmax 2 . 1 − β−
Consequently, the negative part is certified at the optimized single-policy LTI rate ρ⋆− = min∗ ρ(Aπ ). π∈Θ
Proof of Theorem 3. Let p⋆− (x) := Then p⋆− is a norm. Since
q ⋆ (x). v−
⋆ 2 ⋆ v− (A⋆− x) = β− v− (x) − ∥x∥22 ,
we have p⋆− (A⋆− x) ≤ β−
q ⋆ (x) − ∥x∥2 . v− 2
From Equation (14), − = A⋆− zk− + αwk− . zk+1 ⋆ (w − ) ≤ C ⋆ ∥w − ∥2 , we obtain Using the triangle inequality for p⋆− , squaring, and using v− − k 2 k − 2 ⋆ 2 ⋆ ∥zk− ∥22 E[v− (zk+1 ) | Fk ] ≤ β− v− (zk− ) − β− q − 2 ⋆ ⋆ (C ⋆ − 1)W + 2αβ− C− max ∥zk ∥2 + α C− Wmax . −
Using 2ab ≤ a2 + b2 with a = β− ∥zk− ∥2 ,
b=α
q ⋆ (C ⋆ − 1)W C− max , −
gives − ⋆ 2 ⋆ ⋆ 2 E[v− (zk+1 ) | Fk ] ≤ β− v− (zk− ) + α2 (C− ) Wmax .
Taking total expectation and iterating, ⋆ ⋆ 2k − 2 E[v− (zk− )] ≤ C− β− ∥e0 ∥2 +
⋆ )2 W α2 (C− max . 2 1 − β−
By Lemma 6, q − − ⋆ (z − ). ∥e− ∥ ≤ ∥z ∥ ≤ ∥z ∥ ≤ v− ∞ ∞ 2 k k k k √ √ √ Jensen’s inequality and a + b ≤ a + b prove Equation (16). The stochastic orthant-distance bound follows from the same identity between distance and the negative part.
36
Restatement of Corollary 2. Let |S| |A|
R+
:= {x ∈ R|S| |A| : x ≥ 0}.
Under the assumptions of Theorem 3, for every ε > 0 satisfying ρ⋆− + ε < 1, with β− := ρ⋆− + ε ⋆ associated with v ⋆ on R|S| |A| , and with the same fixed-mode norm-equivalence constant C− − every k ≥ 0 satisfies s h i q Wmax |S| |A| ⋆ β k ∥e− ∥ + αC ⋆ E dist∞ (ek , R+ ) ≤ C− − 0 2 − 2 . 1 − β− Proof of Corollary 2. Let n := |S| |A|. As in the deterministic case, for any x ∈ Rn and any y ∈ Rn+ , the coordinates with xi < 0 satisfy |xi − yi | ≥ −xi = x− i . Hence dist∞ (x, Rn+ ) = infn ∥x − y∥∞ ≥ ∥x− ∥∞ . y∈R+
Choosing y = x+ ∈ Rn+ gives the reverse inequality because ∥x − x+ ∥∞ = ∥ − x− ∥∞ = ∥x− ∥∞ . Therefore, dist∞ (x, Rn+ ) = ∥x− ∥∞ . With x = ek , this identity gives the pathwise equality dist∞ (ek , Rn+ ) = ∥e− k ∥∞ . Taking expectations and applying Theorem 3, we obtain E dist∞ (ek , Rn+ ) = E[∥e− k ∥∞ ] s q Wmax ⋆ β k ∥e− ∥ + αC ⋆ ≤ C− − − 0 2 2 . 1 − β− This proves the corollary. Finally, the positive-side stochastic bound uses the switching-family Lyapunov inequality. Restatement of Theorem 4. Assume Assumption 1, and let Wmax be defined as in Lemma 8. Fix ε > 0 such that ρ+ + ε < 1, and define β+ := ρ+ + ε. Let v+ (x) :=
∞ X t=0
−2t β+
max
π0 ,...,πt−1 ∈Θ
2
Aπt−1 · · · Aπ0 x 2 ,
where the t = 0 product is the identity. Then, for every π ∈ Θ, 2 v+ (Aπ x) ≤ β+ v+ (x) − ∥x∥22 , ∀x ∈ R|S| |A| ,
37
and there exists C+ ≥ 1, the product-family norm-equivalence constant associated with v+ on R|S| |A| , such that ∥x∥22 ≤ v+ (x) ≤ C+ ∥x∥22 . Then, for every k ≥ 0, s E[∥e+ k ∥∞ ] ≤
p k C+ β+ ∥e+ 0 ∥2 + αC+
Wmax 2 . 1 − β+
Consequently, the positive part is certified at the full direct JSR rate ρ+ = ρdir α = ρ({Aπ : π ∈ Θ}). Proof of Theorem 4. Let p+ (x) :=
p
v+ (x).
Then p+ is a norm. The product-defined Lyapunov function satisfies, for all π ∈ Θ, 2 v+ (Aπ x) ≤ β+ v+ (x) − ∥x∥22 . Indeed, appending the fixed matrix Aπ to any product of length t produces a product of length t + 1, and therefore v+ (Aπ x) ≤
∞ X
−2t β+
t=0 2 = β+
∞ X r=1
max
π0 ,...,πt ∈Θ
−2r β+
∥Aπt · · · Aπ0 x∥22
max
π0 ,...,πr−1 ∈Θ
2
Aπr−1 · · · Aπ0 x 2
2 = β+ v+ (x) − ∥x∥22 . From Equation (15), + zk+1 = Aπ+ zk+ + αwk+ . k
Using the triangle inequality for p+ , squaring, and using Lemma 9, we obtain + 2 2 E[v+ (zk+1 ) | Fk ] ≤ β+ v+ (zk+ ) − β+ ∥zk+ ∥22 p + 2αβ+ C+ (C+ − 1)Wmax ∥zk+ ∥2 + α2 C+ Wmax .
Using 2ab ≤ a2 + b2 with a = β+ ∥zk+ ∥2 ,
b=α
p C+ (C+ − 1)Wmax ,
gives + 2 2 E[v+ (zk+1 ) | Fk ] ≤ β+ v+ (zk+ ) + α2 C+ Wmax .
Taking total expectation and iterating, 2k + 2 E[v+ (zk+ )] ≤ C+ β+ ∥e0 ∥2 +
2W α 2 C+ max . 2 1 − β+
By Lemma 6, q + + ∥e+ ∥ ≤ ∥z ∥ ≤ ∥z ∥ ≤ v+ (zk+ ). k ∞ k ∞ k 2 √ √ √ Jensen’s inequality and a + b ≤ a + b prove Equation (17).
38