Heavy-Ball Q-Learning with Residual Weighting Correction

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Heavy-Ball Q-Learning with Residual Weighting Correction

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Heavy-Ball Q-Learning with Residual Weighting Correction Donghwan Lee Department of Electrical Engineering Korea Advanced Institute of Science and Technology (KAIST) Daejeon 34141, South Korea (email: [email protected])

arXiv:2606.27112v1 [cs.LG] 25 Jun 2026

Abstract This paper proposes a corrected heavy-ball Q-learning method for reinforcement learning (RL) and establishes its convergence. It also identiﬁes conditions under which the method is theoretically guaranteed to converge faster than standard Q-learning. The same construction is then extended to Q-learning with linear function approximation, where analogous convergence and acceleration statements are derived. The analysis is based on a switched linear system (SLS) representation of Q-learning algorithms and on the joint spectral radius (JSR) of the associated switching families. This SLS viewpoint is not commonly used in standard analyses of Q-learning, and it provides a complementary framework and new insight into how heavy-ball momentum can accelerate Q-learning. Keywords. Q-value iteration, heavy-ball momentum, Bellman residual, joint spectral radius, switched linear systems, constant-preserving diagonal weighting

Introduction

Q-learning [1] is one of the most fundamental and widely used methods in reinforcement learning (RL) [2]. In the tabular discounted setting, it learns the optimal Q-function through Bellman optimality updates without requiring an explicit transition model, and it also underlies modern deep variants such as deep Q-learning [18]. The usual convergence argument relies on the contraction property of the Bellman optimality operator, but this contraction can be weak when the discount factor is close to one. Therefore, many methods have tried to improve the speed of Q-learning or closely related value-iteration recursions. Examples include speedy Q-learning [3], momentum-based Q-learning [13], proportional-integral-derivative (PID)-type value iteration [4], ﬁrst-order accelerated value iteration [5], and rank-one correction or deﬂation methods [8, 11]. However, theoretical guarantees that a modiﬁed recursion is faster than standard Q-learning remain comparatively limited, especially for control problems in which the active greedy policy can change along the trajectory. This paper proposes a corrected heavy-ball Q-learning method obtained by modifying the simplest heavy-ball Q-learning recursion. The correction is designed so that the associated mean mappings share a common eigenvector. Along this common eigenvector, we derive conditions under which the corrected heavy-ball recursion has a smaller certiﬁed rate than the standard Q-learning recursion. The common eigenvector makes the analysis tractable and is the reason such a theoretical acceleration guarantee can be obtained. In the directions orthogonal to this common eigenvector, the present argument does not give the same acceleration guarantee. The contribution is therefore a precise certiﬁcate in one analytically identiﬁable direction, rather than a full-direction acceleration theorem, and this gives a useful perspective on the geometry of the heavy-ball Q-learning. For this analysis, we model the heavy-ball Q-learning mean dynamics as a switched linear system (SLS) [25–27]. The greedy action in the Bellman maximum determines the active mode of the SLS, and the resulting matrix family is analyzed through the joint spectral radius (JSR) [20, 1

28]. This switching-system viewpoint provides a new route for studying the proposed heavy-ball Q-learning recursion and gives additional intuition about when acceleration can be certiﬁed. We also extend the method to linear function approximation and obtain analogous conclusions. The main analysis is written for deterministic mean dynamics, which keeps the role of the common eigenvector clear. The same update can be implemented as a model-free stochastic RL recursion. We also give a short discussion of the independent and identically distributed (i.i.d.) observation version. A Markovian observation version can be developed with standard stochastic approximation tools, as in [22], but that extension is not developed here.

Related work

Momentum-based modiﬁcations of value iteration have been studied from several perspectives. The proportional-integral-derivative (PID) accelerated value iteration framework in [4] interprets value iteration as a feedback-control system and introduces proportional-derivative (PD), proportional-integral (PI), and related PID variants. In ﬁxed-policy settings, the PD/heavyball term changes the eigenvalues of the value-iteration error dynamics through a second-order companion polynomial associated with each eigenvalue of the transition matrix. Momentum value computation and accelerated value iteration were also studied in [5], which connects value iteration with ﬁrst-order optimization methods and analyzes momentum-type value-iteration updates for policy evaluation. Momentum-based accelerated Q-learning has also been studied in stochastic approximation settings [13, 14]. Other acceleration mechanisms for dynamic programming iterations are related but technically diﬀerent. Adaptive relaxation and lookahead methods for value iteration were studied in [6, 7]; Anderson acceleration applies a general ﬁxed-point acceleration scheme to dynamic programming iterations [15]; momentum value iteration in [16] averages successive Q-functions rather than using the heavy-ball Q-value iteration update analyzed here; and anchored/Halperntype value iteration gives another provably accelerated Bellman-error mechanism for both Bellman consistency and optimality operators [17]. Speedy Q-learning is also relevant because it uses two successive Q-estimates to obtain faster ﬁnite-sample bounds in a model-free setting [3]. These works support the broader idea that past iterates or modiﬁed Bellman updates can accelerate Bellman-type recursions. In contrast, this paper proposes a modiﬁed heavy-ball Q-learning recursion that yields a theoretically veriﬁable acceleration certiﬁcate. To the best of our knowledge, the algorithm studied here has not appeared previously, and the convergence and acceleration analysis developed below is new. Unlike much of the existing momentum-based value-iteration and Q-learning literature, which focuses mainly on policy evaluation or stochastic approximation bounds, this paper treats the control setting for a simple constant-stepsize heavy-ball Q-learning recursion. The proof technique is also diﬀerent: we represent the recursion as a switched linear system and compare the resulting switching families through the joint spectral radius rather than relying on ﬁxed-policy spectral or contraction arguments. The slow constant direction of discounted dynamic programming iterations has a long history. Rank-one correction and extrapolation methods exploit the dominant stochastic matrix direction to improve value-iteration behavior [8]. Recent rank-one or deﬂation-based methods also use dominant-direction information, including rank-one modiﬁed value iteration and deﬂated dynamics value iteration [9, 10]. More recent deﬂation-based approaches remove or quotient out the component along the common eigenvector in order to expose faster transverse dynamics; see, for example, the switching-geometry analysis of deﬂated Q-value iteration (Q-VI) [11]. The present paper is related in that every standard Q-VI switching matrix treats the constant-vector direction in the same way. This shared direction ﬁxes the ambient-space benchmark rate, even though the remaining policy-dependent directions may decay faster. The mechanism studied here is diﬀerent: heavy-ball momentum does not deﬂate or remove this direction, but turns it 2

into a second-order linear time-invariant dynamics. The JSR is a standard measure of worst-case exponential growth for products of matrices under arbitrary switching; see, for example, [20]. Value-iteration updates naturally lead to SLS representations because the greedy action can change with the iterate. The SLS analysis used here is close to the direct switching representation of Q-learning [22]. The projected-error viewpoint is also related to recent JSR analyses of Q-VI geometry, including [11, 23].

Preliminaries

3.1

Notation

The set of real numbers is denoted by R; Rm is the m-dimensional Euclidean space; and Rm×n is the set of all m × n real matrices. For a matrix A, A⊤ denotes its transpose. The identity matrix is denoted by I. For a ﬁnite state set S and a ﬁnite action set A, es and ea denote the standard basis vectors associated with s ∈ S and a ∈ A, respectively. For the state-action index i = (s, a), write ei = es ⊗ ea . More generally, standard basis vectors in other Euclidean spaces use the same notation when the dimension is clear from context, and ⊗ denotes the Kronecker product. For a ﬁnite set S, |S| denotes its cardinality. For ﬁnite tabular state and action sets, set n := |S||A|. P m = 1} for the probability simplex in Moreover, we write ∆m := {q ∈ Rm : qi ≥ 0, m i=1 qi n o R . For PN PN a ﬁnite matrix family H = {A1 , . . . , AN }, co(H) := i=1 λi Ai : λi ≥ 0, i=1 λi = 1 denotes its convex hull. We also use standard matrix notation that appears repeatedly below. For a vector x, kxk2 is the Euclidean norm. For a square matrix A, ρ(A) denotes its ordinary spectral radius. After the matrix-family radius is introduced in Deﬁnition 3.1, the notation ρ(H) is used for that quantity when the argument is a switching family. For a matrix B, range(B) denotes its column space, B ≻ 0 means that B is symmetric positive deﬁnite, and λmax (B) denotes the largest eigenvalue when B is symmetric. For square matrices A and B of the same size, we write A ∼ B when they are similar, that is, when B = S −1 AS for some nonsingular matrix S. Expectations are denoted by E[·].

3.2

Switched linear systems

The stability certiﬁcates used later are stated in the language of switched systems, so we ﬁrst recall the basic model before specializing it to the Bellman-induced switching families. Consider the discrete-time switching aﬃne system (SAS) [25–27] xk+1 = Aσk xk + bσk , where each index i ∈ {1, 2, . . . , M }, equivalently each aﬃne pair (Ai , bi ), is called a mode, and σk is the switching signal that selects the active mode at time k. The matrix Aσk is selected from the prescribed family H := {A1 , A2 , . . . , AM }, which is called a switching family; bσk is a mode-dependent aﬃne term. When bσk = 0, the deterministic part reduces to a switched linear system (SLS), xk+1 = Aσk xk . The worst-case exponential rate of the SLS family is characterized by the joint spectral radius (JSR), deﬁned as follows. Deﬁnition 3.1. For a bounded set of matrices H ⊂ Rm×m , its JSR is ρ(H) := lim

sup

k→∞ A1 ,...,Ak ∈H

kAk · · · A1 k1/k .

We note that the JSR is independent of the chosen submultiplicative norm [20, 28]. When H is ﬁnite, the supremum for each ﬁxed product length is a maximum over products generated by matrices in H. For a ﬁnite 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. Throughout

the later JSR certiﬁcates, ρ(H) denotes this same JSR value when the argument is a switching family. Three standard JSR facts used below, convex-hull invariance, similarity invariance, and block upper triangular decomposition, are collected in Section A.2.

3.3

Joint spectral radius and Lyapunov certiﬁcates

The JSR in Deﬁnition 3.1 turns arbitrary switched products into a single worst-case exponential rate. An SLS is uniformly exponentially stable under arbitrary switching if there exist constants C ≥ 1 and η ∈ (0, 1) such that kAσk−1 · · · Aσ0 xk2 ≤ Cη k kxk2 for every horizon k ≥ 0, every initial state x ∈ Rm , and every switching sequence. A common Lyapunov function for H is a positive deﬁnite function that decreases along every mode. In the analysis below, the Bellman maximum induces stochastic-policy switching, and the Lyapunov functions are built from products of the corresponding mode matrices. The following ﬁnite-family piecewise-quadratic construction [22, 29] is the Lyapunov certiﬁcate used in the deterministic arguments. Lemma 3.3. Let H = {A1 , A2 , . . . , AM } ⊂ Rm×m and ﬁx ǫ > 0 such that βǫ := ρ(H)+ǫ ∈ (0, 1). For a word σ = (σ1 , . . . , σk ) ∈ {1, . . . , M }k , write Aσ := Aσk · · · Aσ1 , with the convention that the empty word gives Aσ = I. Deﬁne Vǫ∞ (x) :=

∞ X

βǫ−2k

k=0

max

σ∈{1,...,M }k

kAσ xk22 ,

x ∈ Rm .

Then Vǫ∞ is ﬁnite for every x, and there exists Cǫ > 0 such that kxk22 ≤ Vǫ∞ (x) ≤ Cǫ kxk22 , The function pǫ (x) :=

∀x ∈ Rm .

Vǫ∞ (x) is a norm on Rm , and every mode satisﬁes

pǫ (Ai x) ≤ βǫ pǫ (x),

∀x ∈ Rm ,

i = 1, . . . , M.

Proof. The construction and proof are given in [22, 29]; we omit the proof here. Throughout the sequel, whenever this construction is applied to a switching family with JSR less than one, we call the resulting Vǫ∞ a JSR Lyapunov function for that family, and we call the associated norm pǫ a JSR Lyapunov norm. The following lemma is the common bridge from a JSR bound to convergence of the corresponding error recursion. Lemma 3.4. Let H = {A1 , . . . , AM } ⊂ Rn×n be ﬁnite and suppose ρ(H) < 1. Consider any error recursion xk+1 = Ak xk ,

Ak ∈ co(H),

k ∈ {0, 1, . . .}.

Then, for every ǫ > 0 such that βǫ := ρ(H) + ǫ < 1, the Lyapunov function Vǫ∞ and norm pǫ from Lemma 3.3, applied to H, satisfy Vǫ∞ (xk+1 ) ≤ βǫ2 Vǫ∞ (xk ),

pǫ (xk+1 ) ≤ βǫ pǫ (xk ).

Consequently, if Cǫ is the constant from Lemma 3.3, then pǫ (xk ) ≤ βǫk pǫ (x0 ),

kxk k2 ≤ βǫk pǫ (x0 ) ≤

and hence xk → 0. 4

Cǫ βǫk kx0 k2 ,

Proof. The claim follows from the standard JSR Lyapunov-norm construction, together with the convex-hull invariance of the JSR; see [22, 29]. We omit the proof. The rest of the paper uses this JSR implication as the main convergence certiﬁcate. Once an error recursion has been written as an SLS whose mode family has JSR below one, convergence and an exponential rate bound follow from Lemma 3.4. After each deterministic mean recursion is introduced, the corresponding sampled stochastic RL recursion is also given. For the sampled version, a JSR bound below one for the associated conditional-mean switching family gives the drift part needed for stochastic convergence and ﬁnite-time error bounds, as in [22]. This paper treats only the independent and identically distributed (i.i.d.) sampling case to keep the formulas transparent. The same conditional-mean and noise decomposition can be combined with Markovian-observation stochastic-approximation arguments, as in [24], to extend the setting beyond i.i.d. samples.

3.4

Discounted Markov decision processes

We consider a ﬁnite discounted Markov decision process (MDP), the standard model for reinforcement learning (RL) control [30, 31], with state-space S = {1, . . . , |S|}, actionspace A = {1, . . . , |A|}, transition probability P (s′ | s, a), real-valued one-step reward P ′ | s, a)r(s, a, s′ ), and discount factor r(s, a, s′ ), expected reward R(s, a) := s′ ∈S P (s γ ∈ (0, 1). State-action functions are viewed as vectors in Rn 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. Deﬁne P1  ..  P :=  .  ∈ Rn×|S| , 

R(·, 1)   .. n R :=  ∈R , . 



P|A|



R(·, |A|)

where Pa = P (· | ·, a) ∈ R|S|×|S|. Let Θ denote the set of deterministic stationary policies π : S → A. For any stochastic policy µ : S → ∆|A| , deﬁne µ(1)⊤ ⊗ e⊤ 1  µ(2)⊤ ⊗ e⊤   2   ∈ R|S|×n. Πµ :=  ..   .   



µ(|S|)⊤ ⊗ e⊤ |S|

For a deterministic policy π ∈ Θ, the same notation Ππ is used by identifying π(s) with its one-hot encoding. For Q ∈ Rn , deﬁne VQ (s) := max Q(s, a), a∈A

VQ := (VQ (1), . . . , VQ (|S|))⊤ .

The Bellman optimality operator is F (Q) := R + γP VQ . Let Q⋆ denote the unique ﬁxed point of the Bellman optimality operator, Q⋆ = F (Q⋆ ). For a tie-broken greedy policy πQ satisfying πQ (s) ∈ arg max Q(s, a),

s ∈ S,

a∈A

one has VQ = ΠπQ Q and

F (Q) = R + γP ΠπQ Q.

The following lemma is used repeatedly to write Bellman diﬀerences as linear maps depending on stochastic policies.

Lemma 3.5. For any two vectors Q, Q̄ ∈ Rn , there exists a stochastic policy µQ,Q̄ such that VQ − VQ̄ = ΠµQ,Q̄ (Q − Q̄). Consequently, F (Q) − F (Q̄) = γP ΠµQ,Q̄ (Q − Q̄).

(3.1)

Moreover, for every stochastic policy µ, P Πµ ∈ co {P Ππ : π ∈ Θ} , and P Πµ is row-stochastic and satisﬁes P Πµ 1 = 1. Proof. The proof can be found in [22]. We use d to denote a state-action sampling distribution on S × A. In the i.i.d. observation model, d is the sampling distribution of (sk , ak ); in the Markovian observation model, d is the stationary state-action distribution of the behavior-induced chain. Throughout the paper, we assume that the sampling distribution satisﬁes d(s, a) > 0 for every (s, a) ∈ S × A. This distribution forms the full-support state-action weight vector d ∈ Rn with d⊤ 1 = 1, and we deﬁne D := diag(d), dmax := max d(s, a). (s,a)∈S×A

Corrected Q-learning

In this section, we ﬁrst introduce the deterministic standard Q-learning (QL) update in Algorithm 1 as the baseline against which the subsequent convergence rates will be compared. Algorithm 1 Deterministic standard Q-learning Require: Q0 ∈ Rn , stepsize α > 0, and D = diag(d) for k = 0, 1, 2, . . . do Update Qk+1 ← Qk + αD{F (Qk ) − Qk }. end for This deterministic recursion is a natural starting point for stochastic RL extensions with sampled coordinate updates. However, after inserting D, the common all-ones eigenvector argument in [12], which is central to the acceleration analysis developed below, no longer applies in general: the corresponding matrices need not map the all-ones vector to a scalar multiple of itself unless the diagonal weights in D are uniform. Motivated by this obstruction, this section introduces a modiﬁcation that keeps a nonuniform diagonal weighting on the Bellman residual components while restoring the common eigenvector needed for the SLS-based JSR analysis below. Deﬁnition 4.1. Deﬁne the matrix Πd := 1d⊤ . For a scalar δ > 0, deﬁne the correction matrix H := δΠd + D(I − Πd ) = D + (δ1 − d)d⊤ .

(4.1)

The next lemma states the property that makes this correction useful: multiplication by H maps a constant vector to a constant vector. 6

Lemma 4.1. The matrix H in Equation (4.1) satisﬁes H1 = δ1.

(4.2)

Proof. Using d⊤ 1 = 1, one has Πd 1 = 1d⊤ 1 = 1 and (I − Πd )1 = 1 − 1 = 0. Substituting these identities into Equation (4.1) gives H1 = δΠd 1 + D(I − Πd )1 = δ1, which completes the proof. Lemma 4.2. The matrix H in Equation (4.1) is nonsingular. Proof. Take an arbitrary x ∈ Rn and separate it into its d-weighted constant part and the remaining d-mean-free part. Set a := d⊤ x and z := x − a1. Then x = a1 + z = (d⊤ x)1 + z,

d⊤ z = d⊤ x − ad⊤ 1 = 0.

This decomposition is unique: if x = a1 + z with d⊤ z = 0, then multiplying by d⊤ gives a = d⊤ x. Hence Πd x = a1 and (I − Πd )x = z. The identity Hx = 0 is therefore equivalent to δ(d⊤ x)1 + Dz = 0. Multiplication by d⊤ D −1 gives 0 = δ(d⊤ x)d⊤ D−1 1 + d⊤ z = δ(d⊤ x)d⊤ D−1 1. Because d has full support, D−1 exists and d⊤ D −1 1 = i di (1/di ) = n > 0. Since δ > 0, we obtain d⊤ x = 0. Then Dz = 0, and the positivity of the diagonal entries of D implies z = 0. Hence x = 0, so H is nonsingular. P

Algorithm 2 Deterministic corrected Q-learning Require: Q0 ∈ Rn , stepsize α > 0, and H from Equation (4.1) for k = 0, 1, 2, . . . do Update Qk+1 ← Qk + αH{F (Qk ) − Qk }. end for The proposed construction replaces the stochastic weighting matrix D in the update of Algorithm 1 with the correction matrix H. The resulting algorithm is given in Algorithm 2 and is called corrected Q-learning (CQL). To analyze its ﬁxed point, deﬁne the corresponding map g(Q) := Q + αH{F (Q) − Q}. (4.3) The next lemma shows that the correction does not move the Bellman ﬁxed point Q⋆ . Lemma 4.3. The map g in Equation (4.3) has the unique ﬁxed point Q⋆ . Proof. If Q̄ is a ﬁxed point of g, then H{F (Q̄) − Q̄} = 0. By Lemma 4.2, F (Q̄) − Q̄ = 0 since H is nonsingular. The discounted Bellman optimality operator has the unique ﬁxed point Q⋆ , so Q̄ = Q⋆ . Conversely, F (Q⋆ ) = Q⋆ immediately implies that Q⋆ is ﬁxed by g. Subtracting Q⋆ = F (Q⋆ ) from the update in Algorithm 2 gives the error recursion Qk+1 − Q⋆ = (Qk − Q⋆ ) + αH{F (Qk ) − F (Q⋆ ) − (Qk − Q⋆ )}.

(4.4)

We next show that the error recursion in Equation (4.4) admits an exact SLS representation. 7

Lemma 4.4. The error recursion in Equation (4.4) satisﬁes the SLS ⋆ Qk+1 − Q⋆ = ACQL µk (Qk − Q ).

(4.5)

where for any stochastic policy µ, ACQL := I + αH(γP Πµ − I) µ

(4.6)

Proof. Consider the error recursion in Equation (4.4). By Equation (3.1), we have F (Qk ) − F (Q⋆ ) = γP Πµk (Qk − Q⋆ ), and therefore Qk+1 − Q⋆ = {I + αH(γP Πµk − I)}(Qk − Q⋆ ) ⋆ = ACQL µk (Qk − Q ),

which is Equation (4.5). The corresponding switching family associated with deterministic policies is n

ACQL := ACQL :π∈Θ . π ∈ co(ACQL ). Using the idenIt follows directly that, for every stochastic selector µk , ACQL µk tity in Equation (4.2), one can prove that every switching mode in co(ACQL ) has a common eigenvector. Lemma 4.5. For every stochastic policy µ, it holds that ACQL 1 = 1 − αδ(1 − γ) 1. µ

(4.7)

Proof. For every stochastic policy µ, one has (γP Πµ − I)1 = γ1 − 1 = −(1 − γ)1. Using Equation (4.2), we obtain ACQL 1 = [I + αH(γP Πµ − I)] 1 µ = 1 − α(1 − γ)H1 = (1 − αδ(1 − γ)) 1. This proves the claim. Therefore, the all-ones direction is again a common invariant direction, equivalently a common eigenvector, with scalar factor 1−αδ(1−γ). Throughout the paper, we require this factor to lie strictly between zero and one so that each mode in co(ACQL ) is stable before any momentum is added. Assumption 4.1. The parameters α and δ satisfy 0 < 1 − αδ(1 − γ) < 1. The correction matrix H should be viewed as a structural correction rather than as a universal accelerator. It is introduced in place of D to recover the common eigenvector property in Equation (4.7) for all switching modes. This property alone does not imply that CQL is always faster than QL. The value of H is that it creates the decomposition needed to certify the acceleration of the heavy-ball CQL recursion introduced next. Indeed, adding a heavy-ball momentum term directly to QL may also improve convergence, and in some instances it may even be faster than CQL with a heavy-ball momentum term. The diﬃculty is that, without the common eigenvector in Equation (4.7), an analogous JSR-based certiﬁcate is harder to obtain

for the heavy-ball QL without the modiﬁcation. The subsequent theory and numerical examples show cases in which CQL with momentum is both theoretically certiﬁed and empirically observed to be faster than the corresponding corrected or standard baseline. The analysis in this paper separates this all-ones direction from its orthogonal complement. For this purpose, we introduce the following projection and the associated projected SLS. Let U ∈ Rn×(n−1) have orthonormal columns spanning span{1}⊥ , so that U ⊤ U = In−1 , U ⊤ 1 = 0, and U U ⊤ = I − n−1 11⊤ . Deﬁne the projected standard family o

:π∈Θ . ĀCQL := ĀCQL π

ĀCQL := U ⊤ ACQL U, π π

(4.8)

The matrix ĀCQL is the mode induced by ACQL on the orthogonal component. The next lemma π π makes this statement precise at each iteration. Lemma 4.6. Let Qk follow Algorithm 2. The projected error U ⊤ (Qk − Q⋆ ) satisﬁes the SLS ⊤ ⋆ U ⊤ (Qk+1 − Q⋆ ) = U ⊤ ACQL µk U U (Qk − Q ),

(4.9)

where each projected mode belongs to co(ĀCQL ). ⋆ −1/2 1 and the columns Proof. By Equation (4.5), Qk+1 − Q⋆ = ACQL µk (Qk − Q ). Because q = n of U are orthonormal and orthogonal to q, the matrix [q U ] is orthogonal. Hence

q⊤ qq ⊤ + U U ⊤ = [q U ] ⊤ = I. U Therefore, Qk − Q⋆ = (qq ⊤ + U U ⊤ )(Qk − Q⋆ ) = q q ⊤ (Qk − Q⋆ ) + U U ⊤ (Qk − Q⋆ ) 1 = 11⊤ (Qk − Q⋆ ) + U U ⊤ (Qk − Q⋆ ). n Equivalently, the ﬁrst term is the component along span{1}, and the second term is the component in span{1}⊥ . The common-vector identity in Equation (4.7) gives ACQL µk 1 = {1−αδ(1−γ)}1, ⊤ CQL hence U Aµk q = 0. Therefore ⊤ ⋆ ⊤ ⋆ U ⊤ (Qk+1 − Q⋆ ) = U ⊤ ACQL µk {qq (Qk − Q ) + U U (Qk − Q )} ⊤ ⋆ = U ⊤ ACQL µk U U (Qk − Q ),

which is Equation (4.9). The map P Πµ 7→ U ⊤ [I + αH(γP Πµ − I)]U is aﬃne in P Πµ . The CQL ). convex-hull statement in Lemma 3.5 then implies U ⊤ ACQL µk U ∈ co(Ā This decomposition gives a direct expression for the full JSR ρ(ACQL ) in terms of the constant scalar block corresponding to the common eigenvector and the projected SLS family ĀCQL . Lemma 4.7. The JSR ρ(ACQL ) satisﬁes n

ρ(ACQL ) = max 1 − αδ(1 − γ), ρ(ĀCQL ) . Proof. Let

q := n−1/2 1,

(4.10)

S := q U .

Since U ⊤ U = In−1 , U ⊤ 1 = 0, and U U ⊤ = I − n−1 11⊤ , the matrix S is orthogonal. Indeed, "

q⊤q q⊤U S S= = In , U ⊤q U ⊤U ⊤

SS ⊤ = qq ⊤ + U U ⊤ = n−1 11⊤ + I − n−1 11⊤ = In . 9

For every deterministic policy π, Equation (4.7) gives ACQL q = 1 − αδ(1 − γ) q. Therefore, in π the orthogonal basis S, we can derive

⊤

ACQL S= π

q ⊤ ACQL q q ⊤ ACQL U π π ⊤ CQL U Aπ q U ⊤ ACQL U π

# #

U 1 − αδ(1 − γ) q ⊤ ACQL π , = 0 ĀCQL π q = 1 − αδ(1 − γ) U ⊤ q = 0, and q = 1 − αδ(1 − γ), U ⊤ ACQL where we use the fact that q ⊤ ACQL π π by Equation (4.8). Thus all matrices in ACQL are simultaneously similar to U = ĀCQL U ⊤ ACQL π π block upper triangular matrices with scalar diagonal block 1 − αδ(1 − γ) and projected block ĀCQL . By the similarity invariance in Lemma A.4, we may compute the JSR in this common π basis. Applying Lemma A.5 gives

ρ(ACQL ) = max |1 − αδ(1 − γ)| , ρ(ĀCQL ) . By Assumption 4.1, 1 − αδ(1 − γ) > 0, so the absolute value can be removed. The decomposition immediately implies that the projected SLS family ĀCQL cannot have a larger JSR than the full SLS family ACQL . Corollary 4.1. The following inequality holds: ρ(ĀCQL ) ≤ ρ(ACQL ). Proof. The claim follows directly from Lemma 4.7. The same decomposition also gives the corresponding lower bound for the constant scalar mode. Corollary 4.2. Under Assumption 4.1, we have 1 − αδ(1 − γ) ≤ ρ(ACQL ). Proof. The claim follows directly from Lemma 4.7. This paper focuses on the case in which the projected SLS family ĀCQL is strictly faster than the full SLS family ACQL . In that regime, the decomposition in Equation (4.10) shows that the standard rate is governed by the common all-ones eigenvalue. The proposed modiﬁcations can then improve convergence along the corresponding invariant direction without being blocked by the projected SLS dynamics represented by ĀCQL . Assumption 4.2. Throughout the paper, we assume that the following strict inequality holds: ρ(ĀCQL ) < ρ(ACQL ). Under this assumption, the decomposition in Equation (4.10) shows that ρ(ACQL ) is exactly the eigenvalue of the common all-ones eigenvector. Lemma 4.8. Under Assumption 4.2, ρ(ACQL ) = 1 − αδ(1 − γ). Proof. The claim follows directly from Lemma 4.7.

(4.11)

Combining Assumption 4.2 and Lemma 4.8 with Assumption 4.1, we obtain the equivalent form ρ(ĀCQL ) < 1 − αδ(1 − γ) < 1. The projected modes given in Equation (4.8) have a useful structural feature: the tuning parameter δ aﬀects only the common all-ones direction, not the projected dynamics. This result is formally summarized in the following. Lemma 4.9. For every deterministic policy π, the projected standard mode satisﬁes ĀCQL = In−1 + αU ⊤ D(I − Πd )(γP Ππ − I)U. π

(4.12)

Consequently, the matrices in ĀCQL do not contain δ. Proof. From Equations (4.1) and (4.6), ĀCQL = U ⊤ {I + α [δΠd + D(I − Πd )] (γP Ππ − I)} U π = In−1 + αδU ⊤ Πd (γP Ππ − I)U + αU ⊤ D(I − Πd )(γP Ππ − I)U. Since U ⊤ Πd = U ⊤ 1d⊤ = 0, the middle term is zero. This proves Equation (4.12). The right-hand side of Equation (4.12) contains the MDP term P Ππ , the stepsize α, the diagonal weighting D, and Πd = 1d⊤ , but it does not contain δ. Intuitively, changing δ moves only the all-ones common eigenvalue in Equation (4.7), while leaving the projected SLS family in Equation (4.8) unchanged by Equation (4.12). This separation is useful when choosing δ: it allows dynamics along the common eigenvector direction to be tuned without changing the projected JSR term that appears in Equation (4.10).

Heavy-ball corrected Q-learning

Before introducing the corrected heavy-ball recursion, it is useful to contrast it with the deterministic heavy-ball Q-value iteration studied in [12]. That work considers the unweighted heavy-ball Q-value iteration update Qk+1 = Qk + α{F (Qk ) − Qk } + η(Qk − Qk−1 ).

(5.1)

Its acceleration mechanism is to improve the convergence rate along the common eigenvector direction. A stochastic heavy-ball Q-learning analogue, however, has the conditional mean dynamics Qk+1 = Qk + αD{F (Qk ) − Qk } + η(Qk − Qk−1 ), in which the diagonal sampling matrix D multiplies the Bellman residual. As noted after Algorithm 1, this multiplication generally destroys the common eigenvector property unless D is uniform. The corrected matrix H in Equation (4.1) is introduced precisely to retain nonuniform sampling weights while restoring the common eigenvector direction needed by the JSR analysis below. This section studies the eﬀect of adding a heavy-ball momentum term to the CQL update in Algorithm 2. The resulting update is given in Algorithm 3 and is called heavy-ball corrected Q-learning (HBCQL).

Algorithm 3 Deterministic HBCQL Require: Q−1 , Q0 ∈ Rn , stepsize α > 0, momentum η ≥ 0, and H from Equation (4.1) for k = 0, 1, 2, . . . do Update Qk+1 ← Qk + αH{F (Qk ) − Qk } + η(Qk − Qk−1 ). end for To proceed, deﬁne the augmented map #

Q + αH{F (Q) − Q} + η(Q − Q− ) . g(Q, Q ) := Q −

The augmented map has the same ﬁxed point in both blocks as the corrected standard map in Equation (4.3). Lemma 5.1. A pair (Q̄, Q̄− ) is a ﬁxed point of g, in the sense that #

Q̄ , g(Q̄, Q̄ ) = Q̄− −

if and only if Q̄ = Q̄− = Q⋆ . Proof. If (Q̄, Q̄− ) is a ﬁxed point of g, then the second block gives Q̄ = Q̄− . Substituting this identity into the ﬁrst block gives H{F (Q̄) − Q̄} = 0. ⋆ − ⋆ By Lemma 4.2, H is nonsingular, so F (Q̄) = Q̄ and hence " Q̄#= Q . Therefore Q̄ = Q as well. ⋆ Q . Conversely, F (Q⋆ ) = Q⋆ immediately gives g(Q⋆ , Q⋆ ) = Q⋆

Subtracting Q⋆ = F (Q⋆ ) from the HBCQL update in Algorithm 3 gives the error recursion Qk+1 − Q⋆ = (Qk − Q⋆ ) + αH{F (Qk ) − F (Q⋆ ) − (Qk − Q⋆ )} + η{(Qk − Q⋆ ) − (Qk−1 − Q⋆ )}. (5.2) The next lemma shows that the error recursion in Equation (5.2) can be expressed as an SLS. Lemma 5.2. The error recursion in Equation (5.2) satisﬁes "

Qk − Q⋆ Qk+1 − Q⋆ , = AHBCQL µk ⋆ Qk−1 − Q⋆ Qk − Q

(5.3)

where for a stochastic policy µ, AHBCQL := µ

ACQL + ηI µ I

−ηI . 0

Proof. Using Equation (3.1), Qk+1 − Q⋆ = [I + αH(γP Πµk − I) + ηI] (Qk − Q⋆ ) − η(Qk−1 − Q⋆ ) = (ACQL + ηI)(Qk − Q⋆ ) − η(Qk−1 − Q⋆ ). µk Stacking this identity with the identity Qk − Q⋆ = Qk − Q⋆ gives Equation (5.3). Since the upper-left block depends aﬃnely on P Πµk and the convex-hull statement in Lemma 3.5 holds, ∈ co{AHBCQL : π ∈ Θ} = co(AHBCQL ). AHBCQL π µk

The corresponding SLS family is deﬁned and denoted by n

AHBCQL := AHBCQL :π∈Θ . π

(5.4)

∈ co(AHBCQL ). For the augmented Moreover, for every stochastic selector µk , one has AHBCQL µk heavy-ball recursion, the one-dimensional common eigenvector argument on span{1} becomes an argument with respect to a two-dimensional invariant subspace. To show this, deﬁne the subspace (" # ) a1 I := : a, b ∈ R . (5.5) b1 If the augmented error belongs to this subspace, then the next augmented error also belongs to it, and the scalar coeﬃcients are updated by the following 2 × 2 matrix: C :=

1 − αδ(1 − γ) + η −η . 1 0

This invariance is summarized in the next lemma. Lemma 5.3. For every stochastic policy µ, the subspace I in Equation (5.5) is invariant under AHBCQL . More precisely, for every a, b ∈ R, µ AHBCQL µ

a1 a 1 = + , b1 b+ 1

" #

a+ a =C . b+ b

(5.6)

1 = 1 − αδ(1 − γ) 1. Hence, we obtain Proof. Using Equation (4.7), we have ACQL µ AHBCQL µ

(ACQL + ηI)a1 − ηb1 a1 µ = b1 a1 "

1 − αδ(1 − γ) + η −η 1 0

#" #

" #

1 − αδ(1 − γ) + η a1 − ηb1 . a1

The scalar coordinates therefore satisfy "

a+ = b+

a a =C , b b

which proves both invariance and Equation (5.6). Thus, the common eigenvector direction span{1} of CQL is lifted, in HBCQL, to the invariant subspace I of the augmented state. On span{1}, CQL follows the ﬁrst-order scalar dynamics

xk+1 = 1 − αδ(1 − γ) xk ,

xk ∈ span{1},

whereas HBCQL follows the second-order dynamics on I governed by the matrix C in Equation (5.6) as follows: xk+1 = Cxk , xi ∈ I. The preceding lemma therefore implies that the augmented SLS family of HBCQL cannot have a JSR smaller than the spectral radius of C. To explain this, deﬁne, for any stochastic policy µ, the following projected mode and its associated SLS family: ĀHBCQL := µ

U ⊤ ACQL U + ηIn−1 −ηIn−1 µ , In−1 0

:π∈Θ . ĀHBCQL := ĀHBCQL π

(5.7)

The next lemma shows that the projected augmented error associated with Equation (5.3) can be represented by an SLS. 13

Lemma 5.4. Let Qk follow Algorithm 3. Then "

U ⊤ (Qk+1 − Q⋆ ) U ⊤ (Qk − Q⋆ ) HBCQL = Ā , µk U ⊤ (Qk − Q⋆ ) U ⊤ (Qk−1 − Q⋆ )

(5.8)

and the mode matrix in Equation (5.8) belongs to co(ĀHBCQL ). Proof. By Equation (5.3), ⋆ ⋆ Qk+1 − Q⋆ = (ACQL µk + ηI)(Qk − Q ) − η(Qk−1 − Q ). −1/2 1. Therefore As in the proof of Lemma 4.6, U ⊤ ACQL µk q = 0 for q = n ⊤ ⋆ ⊤ ⋆ U ⊤ (Qk+1 − Q⋆ ) = (U ⊤ ACQL µk U + ηIn−1 )U (Qk − Q ) − ηU (Qk−1 − Q ).

Stacking this identity with the identity U ⊤ (Qk − Q⋆ ) = U ⊤ (Qk − Q⋆ ) gives Equation (5.8). The aﬃne convex-hull relation for U ⊤ ACQL µk U and Equation (5.7) imply that the projected heavy-ball HBCQL mode belongs to co(Ā ). As in the CQL analysis, we can now decompose the augmented SLS family in Equation (5.4) into the constant-error subspace in Equation (5.5) and the projected dynamics in Equation (5.7). Lemma 5.5. The HBCQL SLS family in Equation (5.4) satisﬁes n

ρ(AHBCQL ) = max ρ(C), ρ(ĀHBCQL ) . Proof. Let

q := n−1/2 1,

(5.9)

S := q U .

The matrix S is orthogonal. By the proof of Lemma 4.7, each deterministic standard mode has S

⊤

ACQL S= π

U 1 − αδ(1 − γ) q ⊤ ACQL π . 0 ĀCQL π

Conjugating the current and previous coordinates by the same orthogonal basis gives "

S⊤ 0 S 0 S ⊤ (ACQL + ηI)S −ηI π AHBCQL = π ⊤ 0 S I 0 0 S

U −η 0 1 − αδ(1 − γ) + η q ⊤ ACQL π  CQL 0 Āπ + ηIn−1 0 −ηIn−1    = ,  1 0 0 0  0 In−1 0 0 



where the block coordinates are ordered as current constant, current projected, previous constant, and previous projected. Permuting the second and third block coordinates gives the similar matrix   1 − αδ(1 − γ) + η −η q ⊤ ACQL U 0 π  1 0 0 0    .    0 0 ĀCQL + ηI −ηI n−1 n−1 π 0 0 In−1 0 The upper-left block in this matrix is "

1 − αδ(1 − γ) + η −η = C, 1 0 14

and the lower-right block is "

+ ηIn−1 −ηIn−1 ĀCQL π = ĀHBCQL . π In−1 0

The only nonzero coupling from the constant second-order block to the projected second-order U in the current coordinate. Thus, equivalently, block is the row q ⊤ ACQL π AHBCQL ∼ π

U q ⊤ ACQL π Eπ := 0

C Eπ , 0 ĀHBCQL π

0 . 0

The same similarity and permutation are used for every π ∈ Θ, so the whole family is simultaneously block upper triangular with diagonal families {C} and ĀHBCQL . By the similarity invariance in Lemma A.4, we may compute the JSR in this common basis. Applying Lemma A.5 gives ρ(AHBCQL ) = max{ρ(C), ρ(ĀHBCQL )}.

The decomposition in Equation (5.9) gives the following two lower bounds. Corollary 5.1. The following inequality holds: ρ(C) ≤ ρ(AHBCQL ). Proof. The claim follows from Equation (5.9) because the maximum is at least its ﬁrst entry. Corollary 5.2. The following inequality holds: ρ(ĀHBCQL ) ≤ ρ(AHBCQL ). Proof. The claim follows from Equation (5.9) because the maximum is at least its second entry. A natural question is whether the HBCQL recursion can improve the convergence rate. The common eigenvector direction can be accelerated by a suitable positive momentum. The next theorem gives a suﬃcient condition under which HBCQL has a strictly smaller JSR than CQL. Theorem 5.1. Under Assumptions 4.1 and 4.2, there exists η0 > 0 such that every 2

0 < η < min{ 1 − αδ(1 − γ) , η0 } satisﬁes

(5.10)

ρ(AHBCQL ) < ρ(ACQL ) = 1 − αδ(1 − γ) < 1.

Proof. By Assumption 4.1,

(5.11)

0 < 1 − αδ(1 − γ) < 1. From Equation (4.10) and Assumption 4.2, the projected block cannot attain the maximum; hence ρ(ACQL ) = 1 − αδ(1 − γ), ρ(ĀCQL ) < 1 − αδ(1 − γ). At η = 0, Equation (5.7) gives, for each π ∈ Θ, ĀHBCQL = π η=0

0 ĀCQL π . In−1 0

For every word π1 , . . . , πk with k ≥ 1, the corresponding product is ĀHBCQL πk

η=0

· · · ĀHBCQL π1

CQL 0 ĀCQL πk · · · Āπ1 = CQL 0 , ĀCQL η=0 πk−1 · · · Āπ1

where the lower-left block is interpreted as In−1 when k = 1. Equivalently, the zero-momentum projected family is block lower triangular with diagonal families ĀCQL and {0}. Hence Lemma A.5 gives ρ ĀHBCQL

η=0

= max{ρ(ĀCQL ), 0} = ρ(ĀCQL ).

By continuity of the JSR for ﬁnite matrix families, there exists η0 > 0 such that ρ(ĀHBCQL ) < 1 − αδ(1 − γ),

If, in addition,

0 < η < η0 . 2

0 < η < 1 − αδ(1 − γ) , then Proposition A.1 gives

ρ(C) < 1 − αδ(1 − γ). Using Equation (5.9), ρ(AHBCQL ) = max{ρ(C), ρ(ĀHBCQL )} < 1 − αδ(1 − γ) = ρ(ACQL ). This proves Equation (5.11). For admissible stochastic Bellman-diﬀerence selectors, the convexhull statement in Lemma 3.5 and Lemma A.3 show that passing to the convex hull does not change the JSR. Since the resulting JSR is less than one, the uniform exponential stability statement follows from Lemma 3.4. Theorem 5.1 implies that, under its hypotheses, HBCQL converges to Q⋆ and has a strictly smaller JSR certiﬁcate than the CQL recursion in Algorithm 2. Note that Theorem 5.1 assumes the strict inequality in Assumption 4.2. Because this condition may be hard to verify directly, the following corollary gives a simple suﬃcient interval for δ that automatically guarantees Assumption 4.2. Corollary 5.3. Suppose that ρ(ĀCQL ) < 1. For any 0<δ<

1 − ρ(ĀCQL ) , α(1 − γ)

(5.12)

Assumption 4.2 holds. After such a δ has been ﬁxed, any momentum parameter satisfying Equation (5.10) also satisﬁes the hypotheses of Theorem 5.1. Proof. For ﬁxed MDP data, α, D, and d, the projected matrices satisfy ĀCQL = In−1 + αU ⊤ D(I − Πd )(γP Ππ − I)U, π by Equation (4.12). Hence ρ(ĀCQL ) is independent of δ. The strict projected-gap condition is therefore ρ(ĀCQL ) < 1 − αδ(1 − γ), together with 0 < 1 − αδ(1 − γ) < 1. The interval in Equation (5.12) gives 0 < αδ(1 − γ) < 1 − ρ(ĀCQL ) ≤ 1, and therefore ρ(ĀCQL ) < 1 − αδ(1 − γ) < 1. Thus both the constant-mode range and projected-gap requirements hold. Once δ is ﬁxed, Equation (5.10) is precisely the remaining small-momentum condition in Theorem 5.1. 16

Hyperparameter conditions for improving over standard Qlearning

The previous theorem compares HBCQL with CQL (η = 0). We also state a useful suﬃcient condition under which HBCQL is faster than the standard QL benchmark in Algorithm 1, obtained by setting the momentum term to zero and not applying the correction. Since D is nonsingular, the ﬁxed point of Algorithm 1 is Q⋆ . Subtracting Q⋆ = F (Q⋆ ) from the update given in Algorithm 1 gives the error recursion Qk+1 − Q⋆ = (Qk − Q⋆ ) + αD{F (Qk ) − F (Q⋆ ) − (Qk − Q⋆ )}.

(6.1)

The next lemma uses Equation (3.1) to derive an SLS model associated with the error recursion in Equation (6.1). Lemma 6.1. If Qk follows Algorithm 1, then the error recursion in Equation (6.1) satisﬁes the SLS ⋆ (6.2) Qk+1 − Q⋆ = AQL µk (Qk − Q ), where for any stochastic policy µ, µ AQL µ := I + αD(γP Π − I).

(6.3)

Proof. Using Equation (3.1), the error recursion in Equation (6.1) can be written as Qk+1 − Q⋆ = {I + αD(γP Πµk − I)}(Qk − Q⋆ ) ⋆ = AQL µk (Qk − Q ),

which proves Equation (6.2). The aﬃne dependence on P Πµk and the convex-hull statement in QL ). Lemma 3.5 give AQL µk ∈ co(A The corresponding SLS family is n

AQL := AQL π :π ∈Θ .

(6.4)

We now compare CQL with the standard QL benchmark. The correction in CQL is designed to preserve a common eigenvector, but this structural property alone does not imply an improvement over QL. The next result gives a suﬃcient condition under which the JSR of CQL is no larger than that of the QL benchmark. Lemma 6.2. Assume 0 < αd(s, a) ≤ 1

for every (s, a) ∈ S × A,

and dmax ≤ δ <

1 − ρ(ĀCQL ) . α(1 − γ)

Then ρ(ACQL ) ≤ ρ(AQL ). The interval for δ is nonempty if and only if ρ(ĀCQL ) < 1 − αdmax (1 − γ).

Proof. The upper bound on δ gives ρ(ĀCQL ) < 1 − αδ(1 − γ). Since JSRs are nonnegative, the same upper bound gives 1 − αδ(1 − γ) > 0. Also, dmax ≤ δ and full support of d imply δ > 0, so 1 − αδ(1 − γ) < 1. Hence Assumption 4.1 holds, and the decomposition in Equation (4.10) yields ρ(ACQL ) = 1 − αδ(1 − γ). By Lemma A.2, every deterministic direct mode satisﬁes ρ(AQL π ) ≥ 1 − αdmax (1 − γ),

π ∈ Θ.

Since the JSR of a family is at least the spectral radius of each one-step mode, ρ(AQL ) ≥ 1 − αdmax (1 − γ). Using dmax ≤ δ, we obtain ρ(ACQL ) = 1 − αδ(1 − γ) ≤ 1 − αdmax (1 − γ) ≤ ρ(AQL ), which proves the claimed comparison. Finally, dmax <

1 − ρ(ĀCQL ) α(1 − γ)

is equivalent to ρ(ĀCQL ) < 1 − αdmax (1 − γ), and this proves the nonempty-interval statement. The remaining question is whether HBCQL can be faster than the QL benchmark itself. Combining the previous comparison with the heavy-ball improvement theorem Theorem 5.1 gives the following suﬃcient condition for a strict JSR comparison of HBCQL against QL. Lemma 6.3. Assume 0 < αd(s, a) ≤ 1

for every (s, a) ∈ S × A,

and

1 − ρ(ĀCQL ) . α(1 − γ) Then the hypotheses of Theorem 5.1 are satisﬁed, namely Assumptions 4.1 and 4.2 hold. Let η0 > 0 be the corresponding small-momentum radius guaranteed by Theorem 5.1. If dmax ≤ δ <

0 < η < min{ 1 − αδ(1 − γ) , η0 }, then

ρ(AHBCQL ) < ρ(AQL ). Proof. Because 0 < αd(s, a) for every (s, a) and dmax ≤ δ, we have δ > 0. The upper bound on δ gives ρ(ĀCQL ) < 1 − αδ(1 − γ). Since the left-hand side is nonnegative, this also gives 0 < 1 − αδ(1 − γ) < 1. Hence Assumptions 4.1 and 4.2 hold, and Theorem 5.1 applies. Therefore ρ(AHBCQL ) < ρ(ACQL ) for the stated range of η. Combining this strict inequality with Lemma 6.2 gives ρ(AHBCQL ) < ρ(AQL ).

The previous lemma packages two requirements into the interval for δ: the upper bound gives the hypotheses of Theorem 5.1, while dmax ≤ δ gives the comparison between CQL and QL. The following corollary separates these two roles. It assumes the projected gap directly and states the conclusion in terms of the hyperparameters. Corollary 6.1. Assume the following hyperparameter conditions hold: (i) 0 < αd(s, a) ≤ 1 for every (s, a) ∈ S × A; 1 (ii) dmax ≤ δ < α(1−γ) ;

(iii) Assumption 4.2 holds; (iv) 0 < η < min{ρ(ACQL )2 , η0 }, where η0 > 0 is the small-momentum radius from Theorem 5.1. Then ρ(AHBCQL ) < ρ(AQL ). In particular, with the boundary choice δ = dmax , condition (ii) reduces to 0<α≤

1 dmax

If Assumption 4.2 is also veriﬁed for this choice, then it is suﬃcient to choose n

0 < η < min ρ(ACQL )2 , η0 . Proof. By Lemma A.2, every deterministic direct mode satisﬁes ρ(AQL π ) ≥ 1 − αdmax (1 − γ),

π ∈ Θ.

Therefore ρ(AQL ) ≥ 1 − αdmax (1 − γ). On the other hand, δ ≥ dmax implies 1 − αδ(1 − γ) ≤ 1 − αdmax (1 − γ). Condition (ii) gives 0 < 1 − αδ(1 − γ) < 1, so Assumption 4.1 holds. Condition (iii) and Lemma 4.8 give ρ(ACQL ) = 1 − αδ(1 − γ). Then condition (iv), together with Theorem 5.1, gives ρ(AHBCQL ) < ρ(ACQL ). Combining these inequalities yields ρ(AHBCQL ) < ρ(ACQL ) = 1 − αδ(1 − γ) ≤ 1 − αdmax (1 − γ) ≤ ρ(AQL ), which proves the claim. The simpliﬁed conditions follow by setting δ = dmax .

Numerical illustration

This section gives an example for Algorithms 2 and 3. The purpose of this example is to show in a reproducible ﬁnite example how the heavy-ball momentum term can accelerate convergence. We consider an MDP with S = {1, 2}, A = {1, 2}, and γ = 0.9. The transition-to-next-state probabilities are   0.85 0.15 0.70 0.30   Ps =  . 0.25 0.75 0.10 0.90 The one-step reward entries are r(1, 1, 1) = r(1, 1, 2) = 1.0, r(1, 2, 1) = r(1, 2, 2) = 0.2, r(2, 1, 1) = r(2, 1, 2) = 0.1, and r(2, 2, 1) = r(2, 2, 2) = 0.8. The nonuniform sampling vector is set to d = (0.45, 0.05, 0.40, 0.10)⊤ and D = diag(d), and the shared numerical parameters are α = 1.10,

δ = 0.80,

η = 0.30.

For the simulation, we use the initial values Q−1 = Q0 = (3, −2.5, 1.5, 0)⊤ , and the optimal Q-function is obtained by value iteration and is Q⋆ ≈ (9.16923, 8.28615, 7.93692, 8.55385)⊤ . For comparative analysis, deﬁne the relative error eQ k =

kQk − Q⋆ k2 . kQ0 − Q⋆ k2

Figure 1 compares Algorithm 2 and Algorithm 3. The ﬁgure shows that HBCQL reduces the relative error faster than CQL on this instance. Deterministic CQL Deterministic HBCQL 10−6 threshold

10−1

Relative error

10−3

10−5

10−7

10−9

100

150 Iteration

200

250

300

Figure 1: The HBCQL in Algorithm 3 reaches the same relative Q-error threshold in fewer iterations than the CQL in Algorithm 2.

Stochastic heavy-ball corrected Q-learning

This section studies a model-free stochastic counterpart of the HBCQL recursion in Algorithm 3. We ﬁrst recall standard tabular Q-learning. Given Qk , draw ik = (sk , ak ) ∼ d, draw s′k ∼ P (· | sk , ak ), and deﬁne ∆k := r(sk , ak , s′k ) + γ maxb∈A Qk (s′k , b) − Qk (sk , ak ). The standard sampled update changes the sampled coordinate only: Qk+1 = Qk + αk ∆k eik . 20

Equivalently, it can be written as Qk+1 (s, a) =

(

Qk (s, a) + αk ∆k , (s, a) = ik , Qk (s, a), (s, a) 6= ik .

The complete procedure is stated in Algorithm 4. Algorithm 4 Stochastic standard Q-learning Require: Q0 ∈ Rn , stepsizes αk > 0, and full-support sampling distribution d for k = 0, 1, 2, . . . do Draw ik = (sk , ak ) ∼ d Draw s′k ∼ P (· | sk , ak ) and compute ∆k Update Qk+1 ← Qk + αk ∆k eik . end for Throughout this section, samples are drawn i.i.d. from the full-support distribution d. Markovian sampling is not treated here in order to keep the presentation focused, but the same conditional-mean switching viewpoint can be combined with Markovian stochasticapproximation tools, as in [22]. A replay buﬀer can also be used to approximate the independent sampling required below, following the experience-replay idea used in deep Q-networks (DQN) [18]. We now consider a sampled counterpart of the HBCQL in Algorithm 3. At time k, we sample ik ∼ d,

jk ∼ d,

where jk is independent of ik and of the transition sample used below. After ik = (sk , ak ) is selected, draw s′k according to P (· | sk , ak ) and form ∆k := r(sk , ak , s′k ) + γ max Qk (s′k , b) − Qk (sk , ak ). b∈A

(8.1)

The stochastic HBCQL is written as

Qk+1 = Qk + α∆k eik + δ1 − ejk + η(Qk − Qk−1 ).

(8.2)

For each state-action pair (s, a), this is equivalently written as

Qk+1 (s, a) = Qk (s, a) + α∆k 1{(s,a)=ik } + δ − 1{(s,a)=jk } + η{Qk (s, a) − Qk−1 (s, a)}. The complete pseudocode is given in Algorithm 5.

Algorithm 5 Heavy-ball CQL Require: Q−1 , Q0 ∈ Rn , stepsize α > 0, momentum η ≥ 0, scalar δ > 0, and full-support d for k = 0, 1, 2, . . . do Draw ik = (sk , ak ) ∼ d and jk ∼ d independently Draw s′k ∼ P (· | sk , ak ) and compute ∆k by Equation (8.1) for all (s, a) ∈ S × A do Update

Qk+1 (s, a) ← Qk (s, a) + α∆k 1{(s,a)=ik } + δ − 1{(s,a)=jk } + η{Qk (s, a) − Qk−1 (s, a)}. end for end for

Setting η = 0 in Algorithm 5 gives the sampled stochastic version of CQL. Compared with classical Q-learning, the update uses two independent state-action indices, ik and jk . This increases the sampling burden, but it is not the double-sampling issue associated with residualgradient methods in [32]: only one next-state sample is drawn from the selected pair ik , while the second draw is an independent state-action index used to approximate the centering term. In practice, the second index can be drawn from a replay buﬀer. Equivalently, with the noise

ξk+1 := ∆k eik + δ1 − ejk − H{F (Qk ) − Qk }, one has E[ξk+1 | Qk , Qk−1 ] = 0, and the recursion in Equation (8.2) can equivalently be written as Qk+1 = Qk + αH{F (Qk ) − Qk } + η(Qk − Qk−1 ) + αξk+1 . (8.3) The noise form in Equation (8.3) shows that Equation (8.2) is an unbiased stochastic approximation of the deterministic HBCQL update in Algorithm 3. The next lemma gives the corresponding conditional-mean identity. Lemma 8.1. The following conditional-mean identity holds: E[Qk+1 − Qk | Qk , Qk−1 ] = αH{F (Qk ) − Qk } + η(Qk − Qk−1 ).

(8.4)

Proof. The sampling identities are E[∆k | Qk ] = d⊤ {F (Qk ) − Qk }.

E[∆k eik | Qk ] = D{F (Qk ) − Qk },

Because jk ∼ d is independent of the random variables used to form ∆k , E[∆k ejk | Qk ] = d⊤ {F (Qk ) − Qk } d.

Therefore,

E ∆k eik + δ1 − ejk | Qk

= D{F (Qk ) − Qk } + δ1d⊤ {F (Qk ) − Qk } − dd⊤ {F (Qk ) − Qk } h

= D + (δ1 − d)d⊤ {F (Qk ) − Qk } = H{F (Qk ) − Qk }. Taking the conditional mean of Equation (8.2) gives Equation (8.4). The conditional-mean update in Equation (8.4) is exactly the deterministic HBCQL recursion analyzed in the previous section. Hence its right-hand side admits the same SLS representation as Equation (5.3). Therefore, the deterministic HBCQL JSR certiﬁcates apply to the conditional-mean recursion associated with Equation (8.2). When the corresponding JSR is smaller than one, ﬁnite-time error bounds can be derived by applying the Lyapunov-based SLS analysis in [22]. The convergence and acceleration conclusions established for deterministic HBCQL therefore transfer to this conditional-mean recursion, so we omit the repeated argument.

Numerical illustration

This section adds an experiment for Algorithm 5, where we use the same MDP and parameter settings as in Section 7. The only change is that the Bellman residual is now observed through transition samples rather than evaluated as a full vector. We compare two choices of this update, η = 0 (CQL counterpart) and η = 0.45 (HBCQL), against standard tabular Q-learning with the same samples. All three methods are run with common random numbers, so diﬀerences between the curves are not due to diﬀerent random seeds. The numerical parameters are α = 0.020,

δ = 0.80, η ∈ {0, 0.45}, and K = 4000. The reported curve is the median over 400 independent Monte Carlo paths of the relative error kQk − Q⋆ k2 . kQ0 − Q⋆ k2

emc k =

Because the stepsize is constant, the stochastic methods should be interpreted as approaching a noise neighborhood of Q⋆ , not as converging exactly to zero error. Figure 2 shows the median relative Q-error curves. The CQL update (η = 0) is already much faster than standard Q-learning in this nonuniformly sampled example. Adding the heavy-ball term gives a further transient acceleration: the median ﬁrst passage time below 10−2 drops from about 2693 iterations to about 1556 iterations. Stochastic QL Stochastic CQL, η = 0 Stochastic HBCQL, η = 0.45 10−2 threshold

Median relative error

100

10−1

10−2 0

500

1000

1500

2000 Iteration

2500

3000

3500

4000

Figure 2: The plotted quantity is the median relative Q-error over 400 Monte Carlo paths.

Corrected Q-learning with linear function approximation

The correction method from the previous sections can be extended to deterministic Q-learning with linear function approximation, referred to as linear Q-learning (LQL). Let the parameter vector be θ ∈ Rm , and approximate the Q-vector by Φθ ∈ Rn , where the feature matrix Φ ∈ Rn×m has one row for each state-action pair and one column for each feature. We impose the standard rank condition on the feature matrix. Assumption 10.1. The feature matrix Φ ∈ Rn×m has full column rank. To use the ideas from the previous sections, we introduce the following assumption. Assumption 10.2. There exists c ∈ Rm such that Φc = 1. This assumption is easy to enforce in tabular feature constructions: one may include an intercept feature, namely a column of Φ ﬁlled with ones. Then the corresponding coordinate vector can be chosen as c. The standard deterministic LQL update is summarized in Algorithm 6.

Algorithm 6 Deterministic LQL Require: θ0 ∈ Rm , stepsize α > 0, features Φ, and D = diag(d) for k = 0, 1, 2, . . . do Update θk+1 ← θk + αΦ⊤ D{F (Φθk ) − Φθk }. end for The corresponding map is deﬁned as g(θ) := θ + αΦ⊤ D{F (Φθ) − Φθ}. Its ﬁxed points, g(θ) = θ, are characterized by the associated residual equation below. Lemma 10.1. A parameter vector θ̄ ∈ Rm is a ﬁxed point of g if and only if Φ⊤ D{F (Φθ̄) − Φθ̄} = 0.

(10.1)

Proof. A ﬁxed point of g satisﬁes θ̄ = θ̄ + αΦ⊤ D{F (Φθ̄) − Φθ̄}. Because α > 0, this is equivalent to Equation (10.1). Conversely, suppose that Equation (10.1) holds. Substituting this identity into the update in Algorithm 6, with θk = θ̄, gives θk+1 = θ̄ + αΦ⊤ D{F (Φθ̄) − Φθ̄} = θ̄ + α · 0 = θ̄. Thus the update leaves θ̄ unchanged, so θ̄ is a ﬁxed point of g. Subtracting the ﬁxed-point identity in Equation (10.1) from the update in Algorithm 6 gives θk+1 − θ̄ = θk − θ̄ + αΦ⊤ D{F (Φθk ) − F (Φθ̄) − Φ(θk − θ̄)}.

(10.2)

The next lemma states an SLS error system associated with the above error recursion. Lemma 10.2. Assume that θ̄ is a ﬁxed point of g. Then the error recursion in Equation (10.2) satisﬁes the SLS (10.3) θk+1 − θ̄ = ALQL µk (θk − θ̄), where for any stochastic policy µ, ALQL := Im + αΦ⊤ D(γP Πµ − I)Φ. µ

(10.4)

Proof. By Lemma 3.5, there is a stochastic policy µk such that F (Φθk )− F (Φθ̄) = γP Πµk Φ(θk − θ̄). Substituting this identity gives θk+1 − θ̄ = {Im + αΦ⊤ D(γP Πµk − I)Φ}(θk − θ̄) = ALQL µk (θk − θ̄), which proves Equation (10.3). For the matrix in Equation (10.4), the modes generally do not share a common eigenvector. Consequently, the common-eigenvector acceleration argument used in the tabular analysis does not apply directly. To remove this obstruction, we introduce the corrected map below.

Deﬁnition 10.1. We deﬁne the correction matrix G := Φ⊤ D + (δc − Φ⊤ D1)d⊤ = δcd⊤ + Φ⊤ D(I − 1d⊤ ),

d⊤ 1 = 1.

(10.5)

The map G has a structure similar to the tabular correction, as summarized in the following result. Lemma 10.3. The map in Equation (10.5) satisﬁes G1 = δc.

(10.6)

Proof. Starting from Equation (10.5) and using d⊤ 1 = 1, we compute G1 = Φ⊤ D1 + (δc − Φ⊤ D1)d⊤ 1 = Φ⊤ D1 + δc − Φ⊤ D1 = δc. Equivalently, from the second expression in Equation (10.5), G1 = δcd⊤ 1 + Φ⊤ D(I − 1d⊤ )1 = δc. The corresponding deterministic corrected linear Q-learning (CLQL) is given in Algorithm 7. Note that this is exactly the tabular correction when Φ = I and c = 1. Algorithm 7 Deterministic CLQL Require: θ0 ∈ Rm , stepsize α > 0, features Φ, and G from Equation (10.5) for k = 0, 1, 2, . . . do Update θk+1 ← θk + αG{F (Φθk ) − Φθk }. end for Deﬁne the corresponding feature-space map g(θ) := θ + αG{F (Φθ) − Φθ}.

(10.7)

The next lemma characterizes the ﬁxed points of this map. Lemma 10.4. A parameter vector θ ⋆ ∈ Rm is a ﬁxed point of the map g in Equation (10.7) if and only if G{F (Φθ ⋆ ) − Φθ ⋆ } = 0. (10.8) Proof. A ﬁxed point of g satisﬁes θ ⋆ = θ ⋆ + αG{F (Φθ ⋆ ) − Φθ ⋆ }. Because the stepsize is positive, this is equivalent to G{F (Φθ ⋆ ) − Φθ ⋆ } = 0, which is Equation (10.8). Conversely, if Equation (10.8) holds, substituting it into the update in Algorithm 7 gives θk+1 = θk = θ ⋆ . Unlike the tabular matrix H, the map G is generally not nonsingular. It is often rectangular, since it maps a Bellman residual in Rn to a parameter update in Rm , and even in the square case its rank depends on Φ, D, d, and c. Hence, the feature-space analysis in the sequel uses the ﬁxed-point equation in Equation (10.8) and explicitly assumes uniqueness. Assumption 10.3. The map g in Equation (10.7) has a unique ﬁxed point denoted by θ ⋆ . The ﬁxed point condition in Equation (10.8) should be compared with the standard LQL update in Algorithm 6. A ﬁxed point corresponding to the standard LQL satisﬁes Φ⊤ D{F (Φθ)− Φθ} = 0, which is the usual D-weighted projected Bellman equation: the Bellman residual is orthogonal to every feature column in the D-weighted inner product. By contrast, a ﬁxed point 25

of the update in Algorithm 7 satisﬁes G{F (Φθ) − Φθ} = 0. Thus the two ﬁxed-point equations generally need not have the same solution. Next, subtracting the ﬁxed-point equation in Equation (10.8) from the update in Algorithm 7 gives the error recursion θk+1 − θ ⋆ = (θk − θ ⋆ ) + αG{F (Φθk ) − F (Φθ ⋆ ) − Φ(θk − θ ⋆ )}.

(10.9)

We next rewrite this error recursion as an SLS. Lemma 10.5. The error recursion in Equation (10.9) satisﬁes the SLS (θk − θ ⋆ ), θk+1 − θ ⋆ = ACLQL µk

(10.10)

where µk is a stochastic policy and for any stochastic policy µ, ACLQL := Im + αG(γP Πµ − I)Φ. µ Proof. By Lemma 3.5, there is a stochastic policy µk such that F (Φθk )−F (Φθ ⋆ ) = γP Πµk Φ(θk − (θk − θ ⋆ ), which θ ⋆ ). Substitution gives θk+1 − θ ⋆ = {Im + αG(γP Πµk − I)Φ}(θk − θ ⋆ ) = ACLQL µk proves Equation (10.10). The corresponding SLS family is n

ACLQL := ACLQL :π∈Θ . π As in the tabular case, every mode in ACLQL has a common eigenvector as shown below. Lemma 10.6. For every stochastic policy µ, ACLQL c = (1 − αδ(1 − γ)) c. µ

(10.11)

Proof. Since Φc = 1 and P Πµ 1 = 1, one has (γP Πµ − I)Φc = (γP Πµ − I)1 = −(1 − γ)1. Using Equation (10.6), ACLQL c = [Im + αG(γP Πµ − I)Φ] c µ = c − α(1 − γ)G1 = c − αδ(1 − γ)c = (1 − αδ(1 − γ)) c. This completes the proof. By Equation (10.11), the direction span{c} is a common eigenvector direction of the SLS family ACLQL . As in the tabular analysis, we decompose the feature-space dynamics into this common direction and the induced dynamics on the quotient space. This decomposition provides the same type of convergence benchmark as in the tabular analysis. Let ĀCLQL denote the quotient family induced by ACLQL on Rm / span{c}. Proposition 10.1. Under Assumption 4.1, it holds that n

ρ(ACLQL ) = max 1 − αδ(1 − γ), ρ(ĀCLQL ) . Proof. Choose W ∈ Rm×(m−1) so that S := [c W ] is nonsingular, and write S

−1

ℓ⊤ . = L 26

(10.12)

Then Lc = 0 and LW = Im−1 . By Equation (10.11), each deterministic mode satisﬁes ACLQL c = 1 − αδ(1 − γ) c. π

Consequently, S

−1

ACLQL S= π

" "

i ℓ⊤ CLQL h Aπ c W L

ℓ⊤ ACLQL c ℓ⊤ ACLQL W π π = CLQL LAπ c LACLQL W π "

# #

1 − αδ(1 − γ) ℓ⊤ ACLQL W π = . CLQL 0 LAπ W The lower-right block is the matrix of the induced quotient mode in the basis given by W , so write : π ∈ Θ}. ĀCLQL = LACLQL W, ĀCLQL = {ĀCLQL π π π · · · ACLQL , the same similarity gives For any product ACLQL π1 πk S

−1

ACLQL · · · ACLQL S= πk π1

1 − αδ(1 − γ) 0

Bk · · · ĀCLQL ĀCLQL π1 πk

for some upper-right block Bk . Hence the whole family is simultaneously block upper triangular with diagonal families {1 − αδ(1 − γ)} and ĀCLQL . The block-triangular JSR identity in Lemma A.5 gives n o ρ(ACLQL ) = max |1 − αδ(1 − γ)|, ρ(ĀCLQL ) .

Under Assumption 4.1, 1 − αδ(1 − γ) > 0, so this is exactly Equation (10.12).

The decomposition in Equation (10.12) immediately gives the following lower bounds. Corollary 10.1. The following inequality holds: ρ(ĀCLQL ) ≤ ρ(ACLQL ). n

Proof. Using Equation (10.12), we have ρ(ACLQL ) = max 1 − αδ(1 − γ), ρ(ĀCLQL ) . The maximum is at least its second entry, so ρ(ĀCLQL ) ≤ ρ(ACLQL ). Lemma 10.7. Under Assumption 4.1, the following inequality holds: 1 − αδ(1 − γ) ≤ ρ(ACLQL ). Proof. The claim follows directly from Equation (10.12), since the maximum is at least its ﬁrst entry. As in the tabular case, acceleration is certiﬁed under a strict JSR gap between the full SLS family ACLQL and the projected SLS family ĀCLQL as summarized in the following assumption. Assumption 10.4. Suppose that the following strict inequality holds: ρ(ĀCLQL ) < ρ(ACLQL ).

(10.13)

Under Assumption 10.4, the decomposition in Equation (10.12) shows that ρ(ACLQL ) is identical to the eigenvalue associated with the common eigenvector direction.

Lemma 10.8. Under Assumption 10.4, we have ρ(ACLQL ) = 1 − αδ(1 − γ) .

Proof. By Equation (10.12),

(10.14)

ρ(ACLQL ) = max 1 − αδ(1 − γ), ρ(ĀCLQL ) . The strict inequality in Equation (10.13) rules out the second entry as the maximum. Therefore, ρ(ACLQL ) = 1 − αδ(1 − γ). This is exactly Equation (10.14). We now add the heavy-ball momentum term to the CLQL recursion in Algorithm 7. The resulting algorithm is summarized in Algorithm 8 and is called heavy-ball corrected linear Qlearning (HBCLQL). Algorithm 8 Deterministic HBCLQL Require: θ−1 , θ0 ∈ Rm , stepsize α > 0, momentum η ≥ 0, features Φ, and G from Equation (10.5) for k = 0, 1, 2, . . . do Update θk+1 ← θk + αG{F (Φθk ) − Φθk } + η(θk − θk−1 ). (10.15) end for The next lemma writes the resulting second-order error recursion as a ﬁrst-order augmented SLS. Lemma 10.9. Around any ﬁxed point θ ⋆ of the map in Equation (10.7), the heavy-ball error satisﬁes # " # " ⋆ θ − θ θk+1 − θ ⋆ k (10.16) = AHBCLQL µk θk−1 − θ ⋆ θk − θ ⋆ for a stochastic Bellman-diﬀerence selector µk , where AHBCLQL := µ

ACLQL + ηIm −ηIm µ . Im 0

(10.17)

Proof. Subtracting θ ⋆ from Equation (10.15) gives θk+1 − θ ⋆ = (θk − θ ⋆ ) + αG{F (Φθk ) − F (Φθ ⋆ ) − Φ(θk − θ ⋆ )} + η{(θk − θ ⋆ ) − (θk−1 − θ ⋆ )}. By the ﬁxed-point error identity in Lemma 10.5, (θk − θ ⋆ ) + αG{F (Φθk ) − F (Φθ ⋆ ) − Φ(θk − θ ⋆ )} = ACLQL (θk − θ ⋆ ). µk Therefore θk+1 − θ ⋆ = (ACLQL + ηIm )(θk − θ ⋆ ) − η(θk−1 − θ ⋆ ). µk Stacking θk+1 − θ ⋆ and θk − θ ⋆ yields Equation (10.16) with the mode in Equation (10.17). depends linearly on P Πµ , so the convex-hull statement in Lemma 3.5 gives The matrix ACLQL µ ∈ co(AHBCLQL ). AHBCLQL µk 28

The corresponding SLS family is given by n

AHBCLQL := AHBCLQL :π∈Θ . π

(10.18)

As in the tabular case, the augmented feature-space dynamics preserve the subspace I :=

ac : a, b ∈ R bc

)

⊂ R2m .

maps any vector Indeed, for every policy µ, Equations (10.11) and (10.17) imply that AHBCLQL µ in I to another vector in I. If the augmented error belongs to this subspace, then the next augmented error also belongs to it, and the scalar coeﬃcients are updated by the following constant matrix: " # 1 − αδ(1 − γ) + η −η C := . 1 0 Using the quotient basis from Proposition 10.1, deﬁne "

ĀCLQL + ηIm−1 −ηIm−1 π ĀHBCLQL := , π Im−1 0

:π∈Θ . ĀHBCLQL := ĀHBCLQL π

The block-triangular decomposition in the same basis gives ρ(AHBCLQL ) = max{ρ(C), ρ(ĀHBCLQL )}.

(10.19)

The next theorem gives conditions under which HBCLQL converges faster than CLQL. Theorem 10.1. Under Assumptions 4.1 and 10.4, there exists η0 > 0 such that every 2

0 < η < min{ 1 − αδ(1 − γ) , η0 } satisﬁes

ρ(AHBCLQL ) < ρ(ACLQL ) = 1 − αδ(1 − γ) .

Proof. From Equations (10.13) and (10.14), ρ(ACLQL ) = 1 − αδ(1 − γ),

(10.20)

ρ(ĀCLQL ) < 1 − αδ(1 − γ).

At η = 0, the quotient augmented family induced by Equation (10.18) has matrices "

0 ĀCLQL π , I 0

and therefore has JSR ρ(ĀCLQL ). By continuity of the JSR for ﬁnite matrix families [20, Chapter 1], there exists η0 > 0 such that ρ(ĀHBCLQL ) < 1 − αδ(1 − γ),

0 < η < η0 .

If 0 < η < 1 − αδ(1 − γ) , then Proposition A.2 gives ρ(C) < 1 − αδ(1 − γ). Using Equation (10.19), ρ(AHBCLQL ) = max{ρ(C), ρ(ĀHBCLQL )} < 1 − αδ(1 − γ) = ρ(ACLQL ). This proves Equation (10.20). This result establishes a condition in which HBCLQL improves over CLQL. Conditions under which both HBCLQL and CLQL improve over LQL can be obtained by the same argument as in the tabular case; the details are omitted to avoid repetition. 29

Numerical illustration

This example compares Algorithms 6 to 8. We use the same two-state, two-action MDP as in Section 7, together with the feature matrix speciﬁed below. Throughout this comparison, we use the parameters α = 2.5, δ = 2, η = 0.1, and 



1 1 1 1 1 −1   Φ= , 1 −1 1  1 −1 −1

and one veriﬁes that c = (1, 0, 0)⊤ satisﬁes Φc = 1. The feature recursions use θ−1 = θ0 = (3, −2.5, 1.5)⊤ . In this example, the ﬁxed points of LQL and CLQL coincide numerically: θ ⋆ ≈ (6.21874, 0.75652, 0.02213)⊤ ,

Φθ ⋆ ≈ (6.99739, 6.95313, 5.48435, 5.44009)⊤ .

For the comparison, we deﬁne the relative error eθk =

kθk − θ ⋆ k2 . kθ0 − θ ⋆ k2

Figure 3 compares the three algorithms. CLQL reaches the 10−6 threshold after 22 iterations, compared with 28 iterations for LQL. Adding the small heavy-ball momentum term further reduces the hit time to 15 iterations. All three ﬁnal relative parameter errors are at the 10−15 scale by the end of the run.

Relative

parameter error

Deterministic LQL Deterministic CLQL Deterministic HBCLQL

−1

−3

−5

−7

−9

−11

−13

−15

Iteration

Figure 3: The plot contains exactly the three method curves in Algorithms 6 to 8. The momentum parameter remains deliberately small in this illustration. Larger values of δ or η can make the numerical comparison even more aggressive, but this moderate setting already shows the intended ordering: CLQL is faster than the direct feature recursion, and HBCLQL is faster than CLQL on this instance.

Sampled stochastic heavy-ball linear function approximation

Based on the deterministic HBCLQL analysis, this section extends the sampled model-free construction to linear function approximation. For comparison, we ﬁrst recall sampled Q-learning 30

with linear function approximation. Let Qk = Φθk . Given θk , draw ik = (sk , ak ) ∼ d, draw s′k ∼ P (· | sk , ak ), and deﬁne ∆k := r(sk , ak , s′k ) + γ max(Φθk )(s′k , b) − (Φθk )(sk , ak ). b∈A

(12.1)

The corresponding standard linear Q-learning update is given in Algorithm 9. Algorithm 9 Stochastic LQL Require: θ0 ∈ Rm , stepsizes αk > 0, features Φ, and full-support sampling distribution d for k = 0, 1, 2, . . . do Draw ik = (sk , ak ) ∼ d Draw s′k ∼ P (· | sk , ak ) and compute ∆k by Equation (12.1) Update θk+1 ← θk + αk ∆k Φ⊤ eik . end for We now consider a stochastic HBCLQL counterpart. Set Qk = Φθk and start from θ−1 , θ0 ∈ Rm . At time k, we draw ik ∼ d and jk ∼ d independently. If ik = (sk , ak ), draw s′k ∼ P (· | sk , ak ) and form ∆k := r(sk , ak , s′k ) + γ max(Φθk )(s′k , b) − (Φθk )(sk , ak ). (12.2) b∈A

The parameter is then updated as in Algorithm 10. Algorithm 10 Stochastic HBCLQL Require: θ−1 , θ0 ∈ Rm , stepsize α > 0, momentum η ≥ 0, scalar δ > 0, features Φ, constant direction c, and full-support d for k = 0, 1, 2, . . . do Draw ik = (sk , ak ) ∼ d and jk ∼ d independently Draw s′k ∼ P (· | sk , ak ) and compute ∆k by Equation (12.2) Update

θk+1 ← θk + α∆k Φ⊤ eik + δc − Φ⊤ ejk + η(θk − θk−1 ). end for

The update in Algorithm 10 is an unbiased stochastic approximation of the deterministic HBCLQL recursion in Equation (10.15). The next lemma summarizes this conditional-mean relation. Lemma 12.1. The following equation holds: E[θk+1 − θk | θk , θk−1 ] = αG{F (Φθk ) − Φθk } + η(θk − θk−1 ). This is the sampled conditional-mean counterpart of Equation (10.15). Proof. The conditional identities are E[∆k Φ⊤ eik | θk ] = Φ⊤ D{F (Φθk ) − Φθk }, E[∆k Φ⊤ ejk | θk ] = d⊤ {F (Φθk ) − Φθk } Φ⊤ D1, E[∆k | θk ] = d⊤ {F (Φθk ) − Φθk }.

(12.3)

Therefore h

E ∆k Φ⊤ eik + δc − Φ⊤ ejk | θk

= Φ⊤ D{F (Φθk ) − Φθk } + δc − Φ⊤ D1 d⊤ {F (Φθk ) − Φθk } = G{F (Φθk ) − Φθk }.

Taking the conditional mean of the update in Algorithm 10 gives the second claim. By the same argument used in Lemma 10.9, the right-hand side of Equation (12.3) is represented by the SLS in Equation (10.16). Therefore, the convergence and acceleration certiﬁcates for stochastic HBCLQL hold at the conditional-mean level by the deterministic analysis in Section 10. A full stochastic RL analysis, including martingale noise, constant-stepsize neighborhoods, and Markovian sampling, can be developed by combining this drift representation with Lyapunov-based stochastic approximation arguments as in [22]. We do not repeat those technical steps here.

Numerical illustration

Consider again the example in Section 11, where the MDP, feature matrix, sampling distribution d, constant direction c, initial parameter, and ﬁxed point θ ⋆ are the same as in that section. We use the constant stepsize α = 0.002, the correction parameter δ = 2, and the momentum parameter η = 0.1 for HBCLQL. Stochastic CLQL is obtained from Algorithm 10 by setting η = 0, while stochastic LQL uses Algorithm 9. The three methods are run for 12,000 iterations over 400 independent sample paths. To make the comparison depend on the update rule rather than sampling variation, the same sampled state-action pairs, centering samples, and next-state draws are used across the methods whenever applicable. The quantity in Figure 4 is the median, over the 400 paths, of the relative parameter error θ ek deﬁned in Section 11. In this run, stochastic HBCLQL reaches median error 10−1 , 5 × 10−2 , and 2 × 10−2 after 4074, 5418, and 7177 iterations, respectively. Stochastic CLQL reaches the same thresholds after 4560, 6036, and 8202 iterations, while stochastic LQL reaches the ﬁrst two thresholds after 6840 and 9219 iterations and does not reach 2 × 10−2 within 12,000 iterations. Thus the sampled experiment preserves the early-stage ordering observed in the deterministic example in Section 11. At later iterations, stochastic ﬂuctuations produce a small neighborhood around the ﬁxed point, so the ﬁnal curves need not remain strictly ordered.

Stochastic LQL Stochastic CLQL (η = 0) Stochastic HBCLQL

Median relative error

100

10−1

2000

4000

6000 Iteration

8000

10000

12000

Figure 4: Sampled stochastic version of the example in Section 11. The curves give the median relative parameter error over 400 independent paths.

Conclusion

This paper proposed CQL and combined it with heavy-ball momentum. The analysis used SLS and JSR tools to separate the dynamics along a common eigenvector direction from the dynamics along the orthogonal directions. Under the stated projected-gap and small-momentum conditions, HBCQL has a smaller JSR certiﬁcate than CQL, and analogous statements hold for linear function approximation.

References [1] Christopher J. C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3–4):279– 292, 1992. doi:10.1007/BF00992698. [2] Richard S. Sutton and Andrew G. Barto. Reinforcement learning: an introduction. Second edition, MIT Press, Cambridge, MA, 2018. [3] Mohammad Ghavamzadeh, Hilbert J. Kappen, Mohammad G. Azar, and Rémi Munos. Speedy q-learning. In Advances in Neural Information Processing Systems 24, pages 2411– 2419, 2011. [4] Amir-Massoud Farahmand and Mohammad Ghavamzadeh. Pid accelerated value iteration algorithm. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, pages 3143–3153, PMLR, 2021. [5] Vineet Goyal and Julien Grand-Clément. A ﬁrst-order approach to accelerated value iteration. Operations Research, 71(2):517–535, 2023. Published online March 24, 2022; doi:10.1287/opre.2022.2269. [6] Meir Herzberg and Uri Yechiali. Accelerating procedures of the value iteration algorithm for discounted markov decision processes, based on a one-step lookahead analysis. Operations Research, 42(5):940–946, 1994. doi:10.1287/opre.42.5.940. [7] Oleksandr Shlakhter, Chi-Guhn Lee, Dmitry Khmelev, and Nasser Jaber. Acceleration operators in the value iteration algorithms for markov decision processes. Operations Research, 58(1):193–202, 2010. doi:10.1287/opre.1090.0705. [8] Dimitri P. Bertsekas. Generic rank-one corrections for the value iteration in markovian decision problems. Operations Research Letters, 17(3):111–119, 1995. doi:10.1016/01676377(95)00007-7. [9] Arman Shariﬁ Kolarijani, Tolga Ok, Peyman Mohajerin Esfahani, and Mohamad Amin Shariﬁ Kolarijani. Rank-one modiﬁed value iteration. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, pages 31182–31201, PMLR, 2025. [10] Jongmin Lee, Amin Rakhsha, Ernest K. Ryu, and Amir-Massoud Farahmand. Deﬂated dynamics value iteration. Transactions on Machine Learning Research, 2025. [11] Donghwan Lee. Switching-geometry analysis of arXiv:2605.10811v2, 2026. doi:10.48550/arXiv.2605.10811.

deﬂated

q-value

iteration.

[12] Donghwan Lee. Spectral analysis of heavy-ball q-value iteration. Manuscript, 2026. [13] Bowen Weng, Huaqing Xiong, Yingbin Liang, and Wei Zhang. Analysis of q-learning with adaptation and momentum restart for gradient descent. In Proceedings of the TwentyNinth International Joint Conference on Artiﬁcial Intelligence, pages 3051–3057, 2020. doi:10.24963/ijcai.2020/422. [14] Bowen Weng, Huaqing Xiong, Lin Zhao, Yingbin Liang, and Wei Zhang. Finite-time theory for momentum q-learning. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artiﬁcial Intelligence, Proceedings of Machine Learning Research, Vol. 161, pages 665– 674, PMLR, 2021. [15] Matthieu Geist and Bruno Scherrer. Anderson acceleration for reinforcement learning. In Proceedings of the 14th European Workshop on Reinforcement Learning (EWRL 2018), Lille, France, 2018. 34

[16] Nino Vieillard, Bruno Scherrer, Olivier Pietquin, and Matthieu Geist. Momentum in reinforcement learning. In Proceedings of the Twenty Third International Conference on Artiﬁcial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 108, pages 2529–2538, PMLR, 2020. [17] Jongmin Lee and Ernest K. Ryu. Accelerating value iteration with anchoring. In Advances in Neural Information Processing Systems 36, pages 53924–53963, 2023. doi:10.52202/0752802346. [18] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015. doi:10.1038/nature14236. [19] Carl D. Meyer. Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics, Philadelphia, 2000. ISBN 978-0-89871-454-8; doi:10.1137/1.9780898719512. [20] Raphaël M. Jungers. The joint spectral radius: theory and applications. Lecture Notes in Control and Information Sciences, Vol. 385, Springer, Berlin, Heidelberg, 2009. doi:10.1007/978-3-540-95980-9. [21] Eliahu I. Jury. Theory and application of the z-transform method. John Wiley & Sons, New York, 1964. [22] Donghwan Lee. Lyapunov-certiﬁed direct switching arXiv:2604.19569v3, 2026. doi:10.48550/arXiv.2604.19569.

theory

for

q-learning.

[23] Donghwan Lee. Beyond the bellman ﬁxed point: geometry and fast policy identiﬁcation in value iteration. arXiv:2604.17457v4, 2026. doi:10.48550/arXiv.2604.17457. [24] Zaiwei Chen, Siva T. Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. A lyapunov theory for ﬁnite-sample guarantees of markovian stochastic approximation. Operations Research, 72(4):1352–1367, 2024. Published online October 6, 2023; doi:10.1287/opre.2022.0249. [25] Daniel Liberzon. Switching in systems and control. Systems & Control: Foundations & Applications, Birkhäuser Boston, 2003. doi:10.1007/978-1-4612-0017-8. [26] 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. doi:10.1109/TAC.2008.2012009. [27] Robert Shorten, Fabian Wirth, Oliver Mason, Kai Wulﬀ, and Christopher King. Stability criteria for switched and hybrid systems. SIAM Review, 49(4):545–592, 2007. doi:10.1137/05063516X. [28] Gian-Carlo Rota and Gilbert Strang. A note on the joint spectral radius. Indagationes Mathematicae, 22:379–381, 1960. doi:10.1016/S1385-7258(60)50046-1. [29] Jianghai Hu, Jinglai Shen, and Wei Zhang. Generating functions of switched linear systems: analysis, computation, and stability applications. IEEE Transactions on Automatic Control, 56(5):1059–1074, 2011. doi:10.1109/TAC.2010.2067590. [30] Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming. Wiley Series in Probability and Statistics, John Wiley & Sons, New York, 1994. doi:10.1002/9780470316887. 35

[31] Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-dynamic programming. Athena Scientiﬁc, Belmont, MA, 1996. [32] Leemon Baird. Residual algorithms: reinforcement learning with function approximation. In Proceedings of the Twelfth International Conference on Machine Learning, pages 30–37. Morgan Kaufmann, 1995.

Auxiliary results

A.1

Nonnegative matrix row-sum bounds

The following standard row-sum bound is the form of the Collatz–Wielandt inequality used below; see, for example, [19, Chapter 8]. Lemma A.1. Let B ∈ Rm×m be nonnegative. Then min

1≤i≤m

m X

Bij ≤ ρ(B) ≤ max

1≤i≤m

j=1

m X

Bij .

(A.1)

j=1

Proof. The Collatz–Wielandt inequality for nonnegative matrices gives min i

(Bx)i (Bx)i ≤ ρ(B) ≤ max i xi xi

for every vector x with strictly positive entries. Taking x = 1 gives Equation (A.1). Lemma A.2. Assume 0 < αd(s, a) ≤ 1

for every (s, a) ∈ S × A.

in the direct family Equation (6.4) is nonnegative. Moreover, its row Then each matrix AQL π indexed by (s, a) has row sum 1 − αd(s, a)(1 − γ), (A.2) and every deterministic policy π satisﬁes ρ(AQL π ) ≥ 1 − αdmax (1 − γ).

(A.3)

Proof. For a deterministic policy π, the mode in Equation (6.3) is π AQL π = I − αD + αγDP Π .

The diagonal part I − αD is nonnegative by the assumption 0 < αd(s, a) ≤ 1, and DP Ππ is nonnegative because D is nonnegative diagonal and P Ππ is row-stochastic. Hence AQL is π nonnegative. Since every row of P Ππ sums to one, the row indexed by (s, a) has sum 1 − αd(s, a) + αγd(s, a) = 1 − αd(s, a)(1 − γ), which proves Equation (A.2). Applying Lemma A.1 gives ρ(AQL π ) ≥ min{1 − αd(s, a)(1 − γ)} = 1 − αdmax (1 − γ), (s,a)

which proves Equation (A.3).

A.2

Standard JSR lemmas

Lemma A.3. For a ﬁnite matrix family H, one has ρ(co(H)) = ρ(H), where the left-hand side is computed over all convex combinations of matrices in H. Proof. This is the convex-hull invariance property of the JSR; see, for example, [20, Chapter 1]. We omit the proof. 37

Lemma A.4. Let S be nonsingular. For every bounded matrix family H ⊂ Rm×m , ρ

S −1 AS : A ∈ H

= ρ(H).

This standard property follows from norm equivalence in the deﬁnition of the JSR; see, for example, [20, Chapter 1]. Lemma A.5. Let T be a bounded family of block upper triangular matrices of the form #

Bi Ei . Ti = 0 Di Then ρ(T ) = max {ρ ({Bi : Ti ∈ T }) , ρ ({Di : Ti ∈ T })} . The same statement holds with any ﬁnite number of diagonal blocks. Proof. This is the block upper triangular decomposition property of the joint spectral radius; see, for example, [20, Chapter 1]. We omit the proof.

A.3

Feature-space two-point diﬀerence identity

The following identity is the two-point version of the ﬁxed-point error system in Lemma 10.5. It is placed in the appendix because the main feature-space development only needs the ﬁxed-point form. Lemma A.6. For any two parameter vectors θ, θ̄ ∈ Rm , there exists a stochastic Bellmandiﬀerence selector µθ,θ̄ such that the map in Equation (10.7) satisﬁes T (θ) − T (θ̄) = ACLQL µθ,θ̄ (θ − θ̄), where T (θ) := θ + αG{F (Φθ) − Φθ}. Proof. By Lemma 3.5, there exists a stochastic policy µθ,θ̄ such that F (Φθ) − F (Φθ̄) = γP Πµθ,θ̄ Φ(θ − θ̄). Subtracting the two feature updates gives T (θ) − T (θ̄) = (θ − θ̄) + αG{F (Φθ) − F (Φθ̄) − Φ(θ − θ̄)} = (θ − θ̄) + αG(γP Πµθ,θ̄ − I)Φ(θ − θ̄) = {Im + αG(γP Πµθ,θ̄ − I)Φ}(θ − θ̄) = ACLQL µθ,θ̄ (θ − θ̄), which proves Equation (A.4).

A.4

Jury stability criterion

Lemma A.7. For the real quadratic p(z) = z 2 − az + b, all roots of p belong to {z ∈ C : |z| < 1} if and only if 1 − a + b > 0,

1 + a + b > 0,

This is the second-order Jury stability criterion [21]. The proof is omitted; see [21]. 38

1 − b > 0.

(A.4)

A.5

Scalar heavy-ball acceleration conditions

Proposition A.1. Under Assumption 4.1,

ρ(C) < 1 − αδ(1 − γ) Proof. By Assumption 4.1,

⇐⇒

0 < η < 1 − αδ(1 − γ) .

0 < 1 − αδ(1 − γ) < 1. The characteristic polynomial of C is λ2 − (1 − αδ(1 − γ) + η) λ + η = 0. The inequality ρ(C) < 1 − αδ(1 − γ) is equivalent to all roots of the polynomial obtained by setting λ = (1 − αδ(1 − γ))z lying in the open unit disk. After dividing by (1 − αδ(1 − γ))2 , this polynomial is z2 −

1 − αδ(1 − γ) + η η z+ = 0. 1 − αδ(1 − γ) (1 − αδ(1 − γ))2

For a real quadratic z 2 − az + b, the second-order Jury criterion in Lemma A.7 says that all roots lie in the open unit disk if and only if 1 − a + b > 0,

1 + a + b > 0,

1 − b > 0.

Here these three inequalities become η 1 − αδ(1 − γ) + η + 1 − αδ(1 − γ) (1 − αδ(1 − γ))2 ηαδ(1 − γ) > 0, = (1 − αδ(1 − γ))2 η 1 − αδ(1 − γ) + η + 1+ 1 − αδ(1 − γ) (1 − αδ(1 − γ))2 η η =2+ + > 0, 1 − αδ(1 − γ) (1 − αδ(1 − γ))2 η > 0. 1− (1 − αδ(1 − γ))2 1−

Because 0 < 1 − αδ(1 − γ) < 1, the ﬁrst two inequalities hold exactly when η > 0, while the third is equivalent to η < (1 − αδ(1 − γ))2 . This proves the claimed equivalence. Proposition A.2. Under Assumption 4.1,

ρ(C) < 1 − αδ(1 − γ)

⇐⇒

0 < η < 1 − αδ(1 − γ) .

Proof. Under Assumption 4.1, 0 < 1 − αδ(1 − γ) < 1, and "

1 − αδ(1 − γ) + η −η C= . 1 0 Its characteristic polynomial is λ2 − (1 − αδ(1 − γ) + η) λ + η. The same rescaling λ = 1 − αδ(1 − γ) z used in Proposition A.1 gives the second-order Jury inequalities [21] ηαδ(1 − γ) > 0, (1 − αδ(1 − γ))2 η η + 2+ > 0, 1 − αδ(1 − γ) (1 − αδ(1 − γ))2 η > 0. 1− (1 − αδ(1 − γ))2 39

Since 0 < 1 − αδ(1 − γ) < 1, these inequalities are equivalent to 0 < η < 1 − αδ(1 − γ) , which proves the claimed equivalence.

Record · ID 310829 · SHA-256 00e6e4886c8372f8
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.