Regularized Q-Learning
Authors: Han-Dong Lim
Donghwan Lee
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
Q-learning
convergence
Primary area: reinforcement_learning

Abstract: Q-learning is widely used algorithm in reinforcement learning (RL) community. Under the lookup table setting, its convergence is well established. However, its behavior is known to be unstable with the linear function approximation case. This paper develops a new Q-learning algorithm, called RegQ, that converges when linear function approximation is used. We prove that simply adding an appropriate regularization term ensures convergence of the algorithm. Its stability is established using a recent analysis tool based on switching system models. Moreover, we experimentally show that RegQ converges in environments where Q-learning with linear function approximation has known to diverge. An error bound on the solution where the algorithm converges is also given.

Regularized Q-Learning
Han-Dong Lim Electrical Engineering, KAIST 1 Limaries300kaist.ce .c.
Donghwan Lee Electrical Engineering, KAIST donghwan@kaist.acc. ac.rr
Abstract
Q-learning is widely used algorithm in reinforcement learning (RL) community. Under the lookup table setting, its convergence well established. However, its behavior is known to be unstable with the linear function approximation case. This paper develops new Q-learning algorithm, called RegQ. that converges when linear function approximation is used. We prove that simply adding an appropriate regularization term ensures convergence of the algorithm. Its stability is established using recent analysis tool based switching system models. Moreover, experimentally show that RegQ converges in environments where Q-learning with linear function approximation known to diverge. An error bound on the solution where the algorithm converges also given.
Introduction
Recently, RL has shown great success various fields. For instance, Mnih et (2015) achieved human level performance in several video games in the Atari benchmark Bellemare et al. 2013). Since then, researches on deep RL algorithms have shown significant progresses Laan et al.). Although
great success has been achieved in practice, there is still gap between theory and the practical success. Especially when off- off-policy, function approximation, and bootstrapping are used together. the algorithm may show unstable behaviors. This phenomenon is called the deadly triad (Sutton and Barto 2018 Famous counter-examples are given in Baird [1995] Tsitsiklis and Van Roy 1997].
For policy evaluation, especially for temporal-differeen several algorithms resolve the deadly triad issue. BBradtke and Barto [1996) uses the least-square method to compute a solution of TD-learning, but it suffers from O(h)) time complexity, where number of features, Maei [001] Sutton al. 2009 developed gradient descent based methods which minimize the mean square projected Bellman error. Ghiassian et al. [2020) added regular- ization term to TD Correction (TDC) algorithm, which uses single time scale step-size. Lee et al.) (2022) introduced several variants of the gradient TD (GTD) algorithm under control theoretic frame- works. Sutton al. [0166] re-weights some states match the on-policy distribution to stabilize the off-policy TDDlleannigg BBhardwajj Diddigi et al. [2020) uses la regularization to propose new convergent off-policy TD-learning algorithm. Mahadevan al.] (2014) studied regularization on the off-policy TD-learning through the lens of primal dual method.
(TD) learning algorithm, there has been
First presented by Watkins and Dayan 1992. Q-learning also suffers from divergence issues under the deadly triad. While there are convergence results under the look-up table setting (Watkins and Jaakkola et al. 1994 Borkar and Meyn 2000 Lee and He 2020 even with the simple
Dayan 1992
linear function approximation. the convergence is only guaranteed under strong assumptions [Melo]
al. 2008
Lee and He 2020 Yang and Wang 2019].
The main goal of this paper is to propose a practical Q-learning algorithm, called regularized Q- learning (RegQ), that guarantees convergence under linear function approximation. We prove its convergence using the ordinary differential equation (O.D.E) analysis framework in Borkar and Meyn
(2000) together with the switching system approach developed in Lee and He (020). As in Lee
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

and He [2020]. we construct upper and lower comparison systems, and prove its global asymptotic stability based on switching system theories. Compared to the standard Q-leaming in Watkins and Dayan [992]. difference lies in the additional l2 regularization term, which makes the algorithm
relevantly simple. Moreover, compared to the previous works in Carvalho et al. 2020]. Maei et al. [2010), our algorithm is single time-scale, and hence, shows faster convergence rates experimentally. Our algorithm directly uses bootstrapping rather than cireumventing the issue in the deadly triad. Therefore, it could give new insight into training reinforcement learning algorithms with function approximation without using the so-called target network technique introduced in Mnihh et al. 2015] The main contributions of this paper are summarized as follows:
1. A new single time-scale Q-learning algorithm with linear function upproximation pro- posed.
2. We provide a theoretical analysis on the solution of the projected Bellman equation where regularization term is included.
3. We prove the convergence of the proposed algorithm based on the O.D.E approach together with the switching system model in Lee and He 2020
4. We experimentally show that our algorithm performs faster than other two time-scale Q-
learning algorithms in Carvalho et al. 2020
Maei al. (2010)
Related works:
Several works MMelo et al. 2008 Lee and He 2020 Yang and Wang 2019 have relied on strong assumptions to guarantee convergence of Q-learning under linear function approximation, MMel et al.) (2008) adopts an assumption on relation between behavior policy and target policy to guarantee convergence, which is not practical in general. [ee
Leee and He [020] assumes a similar assumption to that Melo et al. [2008) to ensure the convergence with the so-called switching system approach. Yang and Wang 2019 considered a transition matrix that can be represented by the feature values, which restricts the class of Markov chain.
Motivated by the empirical success of the deep Q-learning in Mnih et 2015 recent works
in Zhang et al. [202T] Carvalho et al. [2020). AAgrral et al. Chen et al. [2023 use the target network to circumvent the bootstrapping issue and guarantee convergence, Carvalho al. (2020) designed a two time-scale learning method motivated by the target network method. Zhang et al. [222] uses l2 regularization with the target network, while a projection step is involved, which makes difficult to implement practically. Moreover, it also relies on a two time-scale learning method. [Chnn et al. 2023] used target network and truncation method to address the divergence issue. AAgrwal et al. additionally uses the so-called experience replay technique with the target network. Furthermore, the optimality is only guaranteed under a specific type of Markov chain. Even though, the target network update can guarantee stability, it often leads to slow convergence rate (Kim et al. 2019]]
Maci et al. (010 suggested the so-called Greedy-GQ (gradient Q-learning) algorithm, but due to non-convexity of the objective function, it could converge to a local optima. [u et al. [202T] used linear programming approach Manne 1960] to design convergent Q-learning algorithm under deterministic control systems. Devraj and Meyn [2017) proposed Q-learning algorithm that minimizes asymptotic variance. However, requires the assumption that the number of changes of policy are finite, and involves matrix inversion at each iteration. Meyn (2023) introduced an optimistic training scheme with modified Gibbs policy for Q-learning with linear function approximation, which guarantees existence of a solution of the projected Bellman equation, but not the convergence. Geist et al. (2019). Xi ct al. (024) considered regularization on the policy which address a different scenario than the regularization in work.
le regularization has been actively explored in the RL literature, Farahm et al. (0016) proposed a regularized policy iteration algorithm that addresses a regularized policy evaluation problem, followed by a policy improvement step. The authors derived a performance error bound. Zhang et al. [2021) studied regularized projected Bellman equation and proves that inside a certain ball, the solution of
the regularized projected Bellman equation exist and is unique. Manek and Kolter [2022] studied fixed
points of aff-policy TD-learning algorithm with regularization showing that the bias of the solution
caused by the regularization can be large under certain scenario. Nonetheless, the regularization
method has been widely used in practice Farebrother et al. 20118 Piché et al. [2021].

---

2 Preliminaries and Notations
2.1 Markov Decision Process
We consider an infinite horizon Markov Decision Process (MDP), which consists of a tuple M = (8, A, p,r, 7), where the state space S and action space A are finite sets, P denotes the transition probability, : S x A x S + IR is the reward, and 7 (0, 1) is the discount factor. Given a stochastic policy + P(A), where P(A) is the set of probability distributions over A, agent at the current state 8& selects an action 0g T(-)ss), then the agent's state changes to the next state 8k+1 P(|sk, ug), and receives reward rk+1 = r(sk, ak; 8k+1). A deterministic policy a special stochastic policy, which can be defined simply as a mapping S A.
The objective of MDP is to find deterministic optimal policy, denoted by n², such that the cumulative discounted rewards over infinite time horizons is maximized, i.e., x² = arg max, E -== 7 rk x] where (so, do $1,01,--- is mate-action trajectory generated by the Markov chain under policy æ,, and [[] is an expectation conditioned on the policy The Q-function under policy x is defined as (s, a) = [- 2 Su = s, a. (s. E S x A, and the optimal Q-function is defined as (*, a) Q (s, a) for all (s, E A. Once Q" is known, then an optimal policy can be retrieved by the greedy action, i.e., π (s) arg max Q* (s, a). Throughout, we assume that the Markov chain is time homogeneous so that the MDP is well posed, which is standard in the literature. It is known that the optimal Q-function satisfies the so-called Bellman equation expressed as follows:
rm|=
('(s, = rk+1 + max 'Q" (**+,1, (sk, =ss,a) = TsQ"(s,
(1)
#211EA EA
where T is called the Bellman operator.
2.2 Notations
In this paper, we will use an O.D.E. model [Borkar and Meyn 2000 of Q-learning to analyze its convergence. To this end, it is useful to introduce some notations In order to simplify the overall expressions. Throughout the paper, e, and e, denote a-th and s-th canonical basis vectors in IR Al and IRS!, respectively, and @ stands for the Kronecker product. Let us introduce the following notations:
P1
R1
Q1
P:
:
RISILAIIIS
R:
E E AI
Q
R SIAA|
PlA (d1,a)
R
D1
Da :=
E RISIXISS
D
E R S|[AAx|S||A1
d())
Dj
where Pa E [R a E the state transition matrix whose i-th row and j-th column component denotes the probability of transition to state j when action a is taken state i, pa E R[S|[4|((5111) represents the state-action transition matrix under policy x, i.e.,
(es & ea) pm (cor 8 exr) P(sk+1 = s', ax+1 a'Isk = s, = s,
= Q(: R A and Rs(s) := as a), S. Moreover, d(-,)) .) is the state- action visit distribution, where i.i.d. random variables {(s), 1 are sampled, i.c., d(s, a) = Flss s, a a). (s, a) S A. With slight abuse of notation, will be also used denote the vector d E IR 5I such that (e, @ cg) d(s,a), a(s E S x A. this paper, we represent policy in matrix form in order to formulate a switching system model. In particular, for given policy म, define the matrix T E TR S|
1ITt = [(ET(1) @ ei)
(ex(2) 8
(ex(1))) & e(ss)]]
Then, we can prove that for any deterministic policy, m we have IT [Q(1, T(1) (2))
For simplicity, let IQQ = II when (s)) = arg max,eA as) Moreover, we can prove that for any deterministic pol- icy pd PII" E IR A|x(S141 where px is the state-action transition probability
((1S),
3

---

matrix. Using the notations introduced, the Bellman equation in T can be compactly written as Q yPIIo Q- + R =; TQ", where Rq. is the greedy policy defined as Tg- (8) = arg ma (8,0). a).
2.3 Q-learning with linear function approximation
Q-learning is widely used model-free learning to find Q", whose updates are given as
Q4+1(5k, ax) <- Qu(sk; as) + agok.
(2)
where 6g = Mk+1 +y aa (s(++1, (sksk, ax) is called the TD error. Each update uses an L..d. sample (Sk, dke rk+1, Sk+1), where (5k, ax) is sampled from a state-action distribution d(.,))
Here, we assume that the step-size is chosen to satisfy the so-called the Robbins-Monro condi- tion [Robbins and Monro 1951 Or > 0, Ex=0 04 00, Ex= oz < co. When the state-spaces and action-spaces are too large, then the memory and computational complexities usually become in- tractable. In such a case, function approximation commonly used to approximate Q-function [Mnih] et al. 2015 Hessel et al. 2018). Linear function approximation is one of the simplest function approximation approaches. In particular, we use the feature matrix X E [R and parameter vector A to approximate Q-function, i.e., Q X0, where the feature matrix is expressed
as := : 1)) ... |AI) ... x(S)), [AA)] E || Here, x(-.)) E IR is called the feature vector, and
positive integer with < |S|]A] The corresponding greedy policy becomes (x) arg aa I(s, a)² 0. Note that the number of policies characterized by the greedy policy finite. This is because the policy invariant under constant multiplications, and there exists a finite number of sectors on which the policy is invariant. Next, we summarize some standard assumptions adapted throughout this paper.
Assumption 2.1. The state-action visit distribution is positive, i.e., d(s, a) > for all (s, as E SxX Assumption 2.2. The feature matrix, X, has full column rank, and a non-negative matrix. Moreover, columns of X are orthogonal.
Assumption 2.3 (Boundedness on feature matrix and reward matrix). There exists constants, X max O and Rmaxx > 0, such that || ||x*)|s>) < X Xmax and [| 20 < -Rmax-
We note that except for the orthogonality of the feature matrix in Assumption 2.2 the assumptions in the above are commonly adopted in the literature, e.g. Carvalho et al. [2020] Lee and He (2020). Moreover, under Assumption 2.T D is nonsingular matrix with strictly positive diagonal elements.
Lemma 2.4 Gosavii 20066).
Under Assumption
2.3 Q', is bounded, i.e.,
||Q*||
Rmaa 1-y
The proof of Lemma 2.4 comes from the fact that under the discounted infinite horizon setting, Q" can be expressed as an infinite sum of geometric sequence.
2.4 Switching System
In this paper, we consider a particular system, called the switched linear system [Liberzon] 2003
i = Ao, Ty = 2 R., t EER.
where Ia E R" is the state, M := := (1,2,.... .., is called the set of modes, or E M is called the switching signal, and (A,, .M} are called the subsystem matrices. The switching signal can be either arbitrary or controlled by the user under a certain switching policy.
Stability and stabilization of (3) have been widely studied for decades. Still, finding practical and effective condition for them is known to be a challenging open problem. Contrary to lincar time-invariant systems, even if each subsystem matrix A, is Hurwitz, the overall switching system may not be stable in general. This tells us that tools in linear system theories cannot be directly applied to conclude the stability of the switching system.
Another approach is to use the Lyapunov theory [Khalil] 2002). From standard results in control system theories, finding Lyapunov function ensures stability of the switching system. If the switching system consists of matrices with strictly negatively row dominant diagonals, defined in Definiiton A.5 in the Appendix, or negative-definite matrices, we can always find a common (piecewise) quadratic Lyapunov function to ensure its stability. We use this fact to prove the convergence of the proposed algorithm.

---

Lemma 2.5. Consider switched system in 3 Suppose one of the following two conditions hold:
1) Each Aa for a M has a strictly negatively row dominating diagonal, i.e., [Aa]it 2 PM [Aolyl < for all s isis n.
2) Ao + A2 x 0 for all a E.M
Then, the origin of is asymptotically stable.
The proof is given in Appendix A.4
3 Projected Bellman equation
In this section, we introduce the notion of projected Bellman equation with a regularization term, and establish connections between it and the proposed algorithm. Moreover, briefly discuss the existence and uniqueness of the solution of the projected Bellman equation. We will also provide an example illustrate the existence and uniqueness of the solution.
3.1 Projected Bellman equation (PBE)
When using the linear function approximation, since true action value may not lie in the subspace spanned by the feature vectors, solution of the Bellman equation may not exist in general. To resolve this issue, a standard approach is consider the projected Bellman equation (PBE) defined as
XØ* = ITX0",
(4)
where - = DX) is the weighted Euclidean projection with respect to state-action visit distribution onto the subspace spanned by the feature vectors, and TX0" = =PPIxx X60 R. In this case, there are more chances for solution satisfying the PBE to exist. Still, there may exist cases where the PBE does not admit solution. To proceed, letting
A == x DX - DPIlxx X, b= XTD,
we can rewrite equivalently as
X0 X(x" DX) x D(yPPIxe-X00 X00 + R) + Asx 0" =b
(5)
Furthermore, we use the simplified notation C XXX. A potential deterministic algorithm to solve the above equation is
0++1= = 0g + or (b Anxa, 0z).
(6)
iteratively solves the linear or nonlinear equation, which is a widely used algorithm called Richardson iteration [Kelley| 1995). If it converges, i.e., 02 - 0* as k oo, then it is clear that 0* solves (5). this paper, the proposed algorithm a stochastic algorithm that solves the modified equation
(Arxez + nI)6;
where I is the x h identity matrix, and 7 2 is a weight on the regularization term. We can use n/C instead of n/ the regularization term but n/C is known solve MDP with modified discount factor Chen et al. 2023). Similar to (6). the corresponding deterministic algorithm
Ok+1 0z + or (b (A + n)T)0k))
(8)
it converges, i.e., 02 + 07 as + oc, then is clear that 8; solves
3.2
Regularized projected Bellman equation
The equation
7 can be written as the regularized projected Bellman equation (RPBE)
X6; I',,T
(9)
where
T X(X DX + -
(10)
5

---

(50X)
Eait sinds
Blowing up plase
x (IX)
s/,
Strinking
Fyr ((2)
9-
[T' Fyell
(a) Regularized projection: C(X) (b) Regularized projection: One di- (c) Boundedness the projection means the range space X
mensional case
Figure I: Illustrative explanation the regularized projection. The Figure Ic implies that as 1j oc,
yI', can potentially move outside of the unit ball satisfying || S 1, and this phase is indicated with the term "blowing up" phase. The quantity | actually blows up initially as 7) - op. However, since lim,--oo 1 = O, we know that yl', will eventually converge to the origin and move inside the unit ball. This behavior is indicated by the "shrinking" phase in the figure.
The proof of the equivalence between and ( are given Lemma A.12 the Appendix
Section A.3 The matrix r can be viewed as modified projection operator which will be called the regularized projection. can interpreted as the projection with a regularization term
(,(x)) arg minger* (1 || X01 [1012) The concept illustrated in Figure la Before
moving forward, some natural questions that arise here are as follows: How does 6* and B differ? Furthermore, which conditions can determine the existence and uniqueness of the solution of and ? Partial answers are given in the sequel.
First, let assume that the solution of (4) and (9), 0" and 0% respectively, exist and unique. To understand the difference between 0" and 0r an important property of N is introduced:
Lemma 3.1. (a) The projection F satisfies the following properties:
lim F, and lim r, =
11000
7-0
(b) We have 1 S || 1| ( DX) (xx)-1l22115 for all
0.
The proof given in Appendix A.5 From the above result, one can observe that as 7) - co, the projection is attracted to the origin illustrated in Figure lb Moreover, as 0, we will expect that 0* + 0* Furthermore, one can observe that the bound in item (b) of Lemma 3. cannot be controlled by simply scaling the feature function, and therefore, it more depends on the inherent structures of the feature matrix X. The concept is illustrated in Figure Ic We will provide a more in-depth discussion on the eиror bound of 6 8* in Section 3.3
Now, we will discuss the existence and uniqueness of the solutions. Considering the non-existence of the solution of (4) [De Farias and Van Roy 2000). (9) may not also have solution. However, for RPBE (9), we can prove that under mild conditions, its solution exists and is unique. We provided
an example where the solution does not exist for + but does exist for (9) in Appendix A. Let us
first state a general condition such that the solution of (9) exists and is unique:
T|[F, < 1,
(11)
Lemma 3.2. Suppose that M holds. Then the solution of RPBE in 4 exists and is unique.
The proof is given in Appendix A.6) which uses Banach fixed-point theorem (Agawall et al. 2018 From Lemma 3.2 we can see that the condition, 7 1||[', < 1, important to guarantee the uniqueness and existence of the solution. We will clarify under what situations the condition (II)
can be met, and provide related discussions Lemma 3.3 3.4
(33] where each lemma illustrate
different scenarios when (IT) is met. In particular, Lemma 3.3 shows that with simple feature scaling, 7 can be easily chosen such that (1T) holds. Furthermore, Lemma 3.4 considers a case when 77 is in a
small neighborhood of zero, and Lemma 3.5 considers the case when (IT) should hold for all 2 0.
We note that Zhang et al. 2021 also studied the solution of the regularized projected Bellman equation. Nonetheless, the result of [Zhang et al. (202T) only ensures unique solution within certain ball whereas we consider the whole Rhth space.
Lemma 3.3. For 1 x T [X + || DX lo. we have ||T < 1.

---

The proof is given in Lemma A. in Appendix. From Lemma
3.3 we can satisfy the condition in [11] with scaling the values of the feature matrix X. For example, le, if max( |>|| l1x>)
it is enough to choose > 2 to meet the condition in I Lemma 3.3 It is worth noting that scaling the values of feature matrix a commonly employed technique in the both theoretical literature or in practice.
Lemma 3.4. Suppose
|| < so that the solution point of PBE in ( exists and is unique. Then, (1 1->1[FII__))] )l(((" Dx)= DX)"""xX"""""
15]
the condition 0 S +|l(X DX) "1 "X>=|XX|>>>] XX
implies y||F <
The proof is in Appendix A.7 We note that the condition, >||T|| loo <
in Lemma 3.4 is used to guarantee the existence and uniqueness of the solution of PBE in (4). which is provided in Melo et al. [2008). Therefore, without any special conditions, we can guarantee the existence and uniqueness of the solution the neighborhood of O.
Lemma 3.5. Suppose the feature vector satisfies X DX al for positive real number such that a ||S||||] 2 Assume that |||||2 S and D A() Then, (11) holds for all rj >> 0.
The proof is given in Appendix A.8
simple example where the above statement holds by letting X 1. This is only conceptual example and there could be many other examples in existence.
3.3 Error analysis
As promised in the previous section, we provide discussion the behavior and quality of 07, i.e., the error bound analysis in 0 - Oz depending on Even though Manek and Kolter [2022) provided a specific example when the bias be large in the policy evaluation case, throughout the analysis, show that the error can be small under particular scenarios.
Let us first examine the case when 17 and + As discussed in Section 3.2 we consider 7 + 0 if we can guarantee the existence of 07 and when is nearby the origin, for example in the As 17 + 0, (4) and (9) coincide, implying that 87 + 8"
case of Lemma 3.4 and 3.5
Furthermore, as gets larger, by Lemma 3.3 we can always guarantee existence and uniqueness of 0r after certain threshold. As from the discussion of Lemma 3.1. we expect 0f - O, which is stated in the following lemma whose proof is given in Appendix A.9
Lemma 3.6. We have lim, 07 0.
Note that even if solution satisfying (7) exists, Xθ; may be different from Q'. However, can derive a bound on the error, X8"; Q" using simple algebraic inequalities and contraction property of the Bellman operator. We present the error bound of the solution in the following lemma:
Lemma 3.7. Suppose
holds. Then, we have :| [0;; - Q" llo0 S - |[, - 101
The proof is given in Appendix A.10 We provide a discussion on the error bound in the following:
1) r + 0: Consider the case when 0; and 0" exists and unique, for example the condition in Lemma 3.4 is satisfied. Since r, -> I from Lemma 3.1 we exactly recover the error bound by fixed point of original projected Bellman equation (1) = 0) in 4 which is IIFQ*=Q"'la provided in Melo
et al. 22008. Thus, our bound in Lemma 3.7 is tight when 17 0.
2) n oo: As from Lemma 3.3 0r always exist when 17 gets larger than certain value. Noting that I, 0, we have || QT $ ||Q" Considering that 0; - 0 as 1 > co from Lemma 3.6 we should have ||X 0 Q*I
1|0" Thus, our bound in Lemma 3.7 tight when 7) - oc.
3) The error bound is close to zero: An upper bound on Lemma 3.7 can be obtained by simple algebraic manipulation:
T1,0¹ - 1o <
1
||x;; - 12 <
||,00 - -Q - (T2)
711 T,lbol
(12)
Suppose that the features are well designed such that (T2) in 12 will small. For example, if Q" in the range space of X, then the error term in (T2) vanishes. Moreover, we can make (TI) arbitrarily
7

---

small as follows: as - O, we have |[T,, 1a--jjp Fl - 0 while > > O. This yields (TI) in (12) to be sufficiently small. In the end. we will have | Q" lce S e for any c 0.
4) When the PBE does not admit a fixed point around "j = O: In this case, we should always choose 17 > greater than certain number, and (T1) cannot be entirely vanished, while (T2) can be arbitrarily close to zero when Q" is close to the range space of X. The error in (TI) cannot be overcame because can be seen as a fundamental error caused by the regularization for PBE. However, (TI) can be still small enough in many cases when | I 1, is small.
4 Algorithm
In this section, will introduce main algorithm, called RegQ. and elaborate the condition the regularization term to make the algorithm convergent. The proposed algorithm is motivated by TD-learning In particular, for on-policy TD-learning, one can establish convergence using the property of the stationary distribution. On the other hand, for an off-policy case, the mismatch between the sampling distribution and the stationary distribution could cause its divergence (Sutton et al. 2016). To address this problem, [Bhardwaaj Diddigi et al. (2020) adds regularization term to TD-learning in order to make it convergent. Since Q-learning can be interpreted an off- off-policy TD- TD-learning, we add regularization term to Q-learning update motivated by [Bharadwaj Diddigi al. 2020 This modification leads to the proposed RegQ algorithm as follows:
0 = 02 + axxxx(ss,, ag)dg; - n00x)
(13)
The pseudo-code is given in Appendix A.16 Note that it can be viewed as a gradient descent step applied to the TD-loss L(0) == I (yre Qo(sk, ax))² + 1 11112 where
Fk+1
yinax.e Qu, ( a)) is the TD-target, and Qa, X0,- Furthermore, letting 1j = the above update is reduced to the standard Q-learning with linear function approximation in (2). The proposed RegQ is different from Bharadwaj Diddigi et al. (2020) in the sense that regularization term is applied to Q-learning instead of TD-learning. Rewriting the stochastic update in deterministic manner, can be written follows:
0k+1 0g az (A + +n])6s + m++1),
(14)
where m 8g.2(5k ag) n8. (b (ATxe, + +I))²²) is Martingale difference sequence. Without mg4+1 (I4) is reduced to the deterministic version in (8). In convergence analysis. will apply the O.D.E. approach, and in this case, Anxe, + ryl will determine the stability of the corresponding O.D.E. model, and hence, convergence of 13) Note that (14) can interpreted as a switching system defined in (3) with stochastic noises. As mentioned earlier, proving the stability of a general switching system is challenging in general. However, we can find common Lyapunov function to prove its asymptotic stability. In particular,
make - -AAxx, + mI) to have strictly negatively row dominant diagonal or negative-definite under the following condition:
nd pd (ea 8 &.)2
2 --7
>> min
X|X DI + 1|X DXI +XXXIXXI
XC)
2d(s,
(S1)
(s,a)SSXA
($2)
(15)
The conditions in (S1) and (S2), which make (Axx% + m/L) to have strictly negatively row dominant diagonal or negative definite matrix, respectively, do not necessarily imply each others, which are discussed Appendix [A Now, we can use the Lyapunov argument to establish stability of the overall system. Building the fact, in the next section, prove that under the stochastic update (13), we have 0% + 6 as + oc with probability one, where 8;, satisfics RPBE in 7 15).. we guarantee convergence to optimal policy without errors.
77 0 satisties
5 Convergence Analysis
Recently, Lee and He [020] suggested switching system framework to prove the stability of Q-learning in the linear function approximation cases. However, its assumption the behavior
8

---

policy and feature matrix seems too stringent to check in practice. Here, we develop more practical Qllearning algorithm by adding an uppropriately preconditioned regularization term. We prove the convergence of the proposed Q-learning with regularization term (13) following lines similar to Lee land He (020). Our proof mainly relies on Borkar-Meyn theorem. Therefore, we first discuss about the corresponding O.D.E. for the proposed update in (T3). which is
0. = - DX 77)0 + 7X D PIT X0, + DR: f(O.)
(16)
Then, using changes of coordinates, the above O.D.E. can be rewritten d
at (0, 07) =(-Arx, ( 8.) + + -
(17)
dt
where 8r satisfies 77). Here, assume that equilibrium point exists and is unique. We later prove that if an equilibrium exists, then it is unique. To apply Borkar-Meyn theorem in Lemma A.I we discuss about the asymptotic stability of the O.D.E. in (7).. Note that (17) includes an affine term, i.e., cannot be expressed as a matrix times vector 8: 6-- It is in general hard to establish asymptotic stability of switched linear system with affine term compared to switched linear system (3) To circumvent this difficulty, Leee and He (0200 proposed upper and lower comparison systems, which upper bounds and lower bounds the original system. Then, the stability of the original system can be established by proving the stability of the upper and lower systems, which are easier to analyze. Following similar lines, check global asymptotic stability of the original system, we also introduce upper and lower comparison systems. Then, we prove global asymptotic stability of the two bounding systems. Since upper and lower comparison systems can be viewed as switched linear system and linear system, respectively, the global asymptotic stability is easier to prove. We stress that although the switching system approach in Lee and He [2020) is applied in this paper, the detailed proof is entirely different and nontrivial. In particular, the upper and lower comparison systems are given as follows:
D- 7x DPllxo X)0 =1 - 72 + 7 DP X)0
where 0r and 0g denote the states of the upper and lower systems, respectively. We defer the detailed construction of each system to Appendix A2.1] The stability of overall system can be proved by establishing stability of the upper and lower comparison systems.
Theorem 5.1. Suppose r satisfies (75), and Assumption 2.7 2.2 and 2.3 hold. Moreover, assume that a solution of RPBE in 77 exists. Then, it is also unique, and the origin is the unique globally
asymptotically stable equilibrium point of (17
The detailed proof is given in Appendix A.12 and Meyn's 's theorem in Lemma A. following theorem is given in Appendix AA13
Building on the previous results, we now use Borkar establish the convergence of RegQ. The full proof of the
2.2 and 2.3 holds. Assume that solution of RPBE in 77) exists. Then, y is unique, and under the stochastic update
Theorem 5.2. Suppose y satisfies (5), then with Assumption 2.
O2 - 0* as
k + 3o with probability one, where 0f satisfies (7)
We note that rj is larger than the term (51) 15 then 0r exists and unique by Lemma 3.3
6 Experiments
In this section, we briefly present the experimental results under well-known environments in Tsitsiklis and Van Roy (199), ,. [aird [1995], where Q-learning with linear function approximation diverges. As from Figure 2b, our algorithm shows faster convergence rate than other algorithms. Further details on the experiments are deferred Appendix B In Appendix B.6] we also compare performance under the Mountain Car environment [Sutton and Barto, 2018 where Q-learning performs well. In Appendix B.5] we show experimental results under various step-size and п) Moreover, the trajectories of upper and lower systems to illustrate the theoretical results are given in Appendix (B7
7 Conclusion
In this paper, we presented a new convergent Q-learning with linear function approximation (RegQ), which is simple to implement. We provided theoretical analysis on the proposed RegQ, and demon- strated its performance on several experiments, where the original Q-learning with linear function

---

100
304
12
12"0
180
12"
Coupledd Sreetyd00
10"1
Caspled0
Skenty330
(rgget)
(rrget)
Aag0
Nego
20
10
20
2053
sampp
(a) Results in 0 20
(b) Results in Baird seven star counter example
Figure 2: Experiment results
approximation diverges. Developing new Q-learning algorithm with linear function approximation without bias would be interesting future research topic. Moreover, considering the great success of deep learning, it would be interesting to develop deep reinforcement learning algorithms with appropriately preconditioned regularization term instead of using the target network.
8
Acknowledgements
The work was supported by the Institute of Information Communications Technology Planning Evaluation (IITP) funded by the Korea government under Grant 2022-0-00469, and the BK21 FOUR from the Ministry of Education (Republic of Korea).
References
Naman Agarwal, Syomantak Chaudhuri, Prateek Jain, Dheeraj Mysore Nagaraj, and Praneeth Netrapalli. Online Target Q-learning with Reverse Experience Replay: Efficiently finding Optimal Policy for Linear MDPs. In International Conference Learning Representations.
Praveen Agarwal, Mohamed Jieli, and Bessem Samet. Fixed Point Theory in Metric Spaces. Recent Advances and Applications, 2018.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37. Elsevier, 1995.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279 2013.
Raghuram Bharadwaj Diddigi, Chandramouli Kamanchi, and Shalabh Bhatnagar. A convergent off-policy temporal difference algorithm. In ECA! 2020, pages 1103-1110. IOS Press, 2020.
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-46,, 2000.
Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning, Machine learning, 22(1):33-57 1996.
Diogo Carvalho, Francisco Melo, and Pedro Santos. A new convergent variant of Q-learning with linear function approximation. Advances in Neural Information Processing Systems, 33: 19412-19421, 2020.
Zaiwei Chen, John-Paul Clarke, and Siva Theja Maguluri. Target network and truncation overcome the deadly triad in-learning. SIAM Journal on Mathematics of Data Science, 5(4):1078-110)) 2023.
10

---

Daniela Pucci De Farias and Benjamin Van Roy. On the existence of fixed points for approximate value iteration and temporal-diie -ifffeenee learning. Journal of Optimization theory and Applications. 105(3):589- 608, 2000.
Adithya M Devraj and Sean Meyn. Zap Q-learning. Advances in Neural Information Processing Systems, 30, 2017.
Amir-massoud Farahm, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor. Regularized policy iteration with nonparametric function spaces. Journal of Machine Learning Research, 17 1139):1-66, 2016.
Jesse Farebrother, Marlos C Machado, and Michael Bowling. Generalization and regularization in dqn. arXiv preprini arXiv:/810.00123, 2018.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pages 2160-2169. PMLR, 2019.
Sina Ghiassian, Andrew Patterson, Shivam Garg, Dhawal Gupta, Adam White, and Martha White. Gradient cumporal-different learning with regularized corrections. In International Conference on Machine Learning, pages 3524-3 3534. PMLR, 2020.
Abhijit Gosavi. Boundedness of iterates in Q-learning. Systems & control letters, 55(4)3347-399 2006.
William W Hager. Updating the inverse of matrix. SIAM review, 31(2):211-23) 1989.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-second AAAI conference artificial intelligence, 2018
Morris W Hirsch and Hal Smith. Monotone dynamical systems. In Handbook of differential equations: ordinary disferential equations, volume 2, pages 239-357. Elsevier, 2006.
RA Horn and CR Johnson. Matrix analysis second edition, 2013.
Tommi Jaakkola, Michael I Jordan, and Satinder P Singh. On the convergence stochastic iterative dynamic programming algorithms. Neural computation, 185-1121, 1994.
Carl T Kelley. Iterative methods for linear and nonlinear equations. SIAM, 1995.
Hassan K Khalil, Nonlinear systems; 3rd ed. Prentice-Hall, Upper Saddle River, NJ, 2002. URL https://cdas cern. ch/record/1173048 The book can be consulted by contacting: PH-AID:
Wallet, Lionel.
Seungehan Kim, Kavosh Asadi, Michael Littman, and George Konidaris. Deepmellow: removing the need for a target network in deep g-learning. In Proceedings of the twenty eighth international joint conference on artificial intelligence, 2019.
Qingfeng Lan, Yangehen Pan, Alona Fyshe, and Martha White. Maxmin Q-learning Controlling the Estimation Bias of Q-learning In International Conference on Learning Representations.
Donghwan Lee and Niao He. A unified switching system perspective and convergence analysis of Q-learning algorithms. Advunces Neural Information Processing Systems, 33: 15566-1557,, 2020.
Donghwan Lee, Han-Dong Lim, Jihoon Park, and Okyong Choi. New Versions of Gradient Temporal- Difference Learning. IEEE Transactions on Automatic Control, 680)):00665503,, 2022.
Daniel Liberzon. Switching in systems and control. Springer Science & Business Media, 2003.
Fan Lu, Prashant G Mehta, Sean P Meyn, and Gergely Neu. Convex Q-learning. In 202/ American Control Conference (ACC), pages 4749-4756. IEEE, 2021.
Hamid Reza Maei. Gradient temporal-differene learning algorithms. 2011.

---

Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S Sutton. Toward off- off-policy learning control with function approximation. In ICML, 2010.
Sridhar Mahadevan, Bo Liu, Philip Thomas, Will Dabney, Steve Giguere, Nicholas Jacek, Ian Gemp, and Ji Liu, Proximal reinforcement learning: A new theory of sequential decision making in primal-dual spaces. arXiv preprint arXiv:1405.677 2014.
Gaurav Manek and J Zico Kolter. The pitfalls of regularization in off-policy td learning. Advances in Neural Information Processing Systems, 35:35621-35633 2022.
Alan S Manne. Linear programming and sequential decisions. Management Science, 6(3):259-267, 1960.
Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro. An analysis of reinforcement learning with function approximation. Proceedings of the 25th international conference on Machine learning, pages 2008.
Sean Meyn. Stability of Q-learnng Through Design and Optimism. arXiv preprint arXiv:2307.02632 2023.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. nature, 51 51807540):5295333 2015.
Alexander P Molchanov and Ye Pyatnitskiy. Criteria of asymptotic stability of differential and difference inclusions encountered in control theory. Systems & Control Letters, 13(1):59-644 64, 1989.
Alexandre Piché, Joseph Marino, Gian Maria Marconi, Christopher Pal, and Mohammad Emtiyaz Khan. Beyond target networks: Improving deep q-learning with functional regularization. 2021.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Hamid Reza Maei, Doina Precup. Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. In Proceedings of the 26th Annual International Conference on Machine Learning. pages 993-1000, 2009.
Richard Sutton, Rupam Mahmood, and Martha White. An emphatic approach the problem of off-policy cemporal-differenct learning. The Journal of Machine Learning Research, 17(1): 2603-2631, 2016
John Tsitsiklis and Benjamin Van Roy. Feature-based methods for large scale dynamic program- ming. Machine Learning, 22(1):59-9)) 94, 1996.
John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal--difference learning with function approximation. IEEE transactions on automatic control, 42(5):677-690,, 1997.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-29) 292, 1992.
Jiachen Xi, Alfredo Garcia, and Petar Momcilovic. Regularized Q-learning with Linear Function
Approximation. arXiv preprint arXiv:2401.15196 2024.
Lin Yang and Mengdi Wang. Sample-optimal parametric Q-lcarning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with target network. In International Conference on Machine Learning, pages 22621-12631. PMLR, 2021.
12

---

A Appendix
A.1
O.D.E analysis
The dynamic system framework has been widely used to prove convergence of reinforcement learning algorithms, e.g., Sutton et al. (2009) Maci et al. 2010), Borkar and Meyn 2000). Lee and He (2020). Especially, [Borkar and Meyn [2000] is of the most widely used techniques prove stability of
stochastic approximation using O.D.E. analysis. Consider the following stochastic algorithm with a nonlinear mapping IR" R"
0 f(6x) ma:
(18)
where my IR" is an i.i.d. noise vector. For completeness, results in Borkar and Meyn 2000
briefly reviewed in the sequel. Under Assumption A.2 given in Appendix A.2 we now introduce Borkar and Meyn theorem below.
Lemma A.1 (Borkar and Meyn theorem). Suppose that Assumption A.2 2 in the Appendix A.2 holds, and consider the stochastic algorithm in (18). Then, for any initial 0g E Ik"" supk20 |0x|| < 0o with probability one. In addition, 02 - 8 as + co with probability one, where 6" satisfies f( =
The main idea of Borkar and Meyn theorem is as follows: iterations of stochastic recursive algorithm follow the solution of its corresponding O.D.E. in the limit when the step- size satisfies the Robbins- Monro condition. Hence, by proving the asymptotic stability of the O.D.E.. we can induce the convergence of the original algorithm. In this paper, we will use an O.D.E. model of Q-learning, which is expressed as special nonlinear system called switching system.
A.2 Assumption for Borkar and Meyn Theorem
Assumption A.2.
1. The mapping f :R" + R" is globally Lipschitz contimuous, and there exists a function fxo R" IR" such that
Mcr)
lim 100
(x)) sox())
Yx E R..
(19)
c
2. The origin in R" is an asymptotically stable equilibrium for the O.D.E. i, = foo
3. There exists unique globally asymptotically stable equilibrium l R for the O.D.E. à.- = f(xx), ie., De - 8 as t + co.
The sequence {m,, Gk hE21 where Gn. is sigma-algebra generated by {(0,, m; k 2 i}, is Martingale difference sequence. In addition, there exists a constant Co < such that for any initial Og E RR, we have [[llm=++11|? I Co(1 + 10021²), 2 O.
5. The step-sizes satisfies the Robbins-Mone Monro condition [Robbins and Monro 1951
O = 00,
o < 00.
0=
0=
A.3 Auxiliary lemmas
Lemma A.3 (Woodbury matrix identity (Hager 1989 ). For A, B E RRaxn suppose A and T A-1B
is invertible, then A + B is invertible and we have
()- A - A A- B(I + A -
A-
Lemma A.4 (Gelfand's formula, Corollay 5.6. in Horn and Johnson 2013 11-11, for A E guxnn we have
For any matrix norm
p(A) lim ||
0000
where p(-) denotes the spectral radius of given matrix.
13

---

Definition A.5 (Theorem 3 in Molchanov and Pyatnitskiy 1989)). ). A matrix A E R is said have strictly negatively row dominating diagonal if [ 2j.............. [Ali < for all
1 IsiS n.
Lemma A.6 (Theorem in Molchanov and Pyatnitskiy 1989
Consider switched system in (3)
where M =: {1, ,,..., M is the set for switching modes. there exists number m 2 n, a full-row rank matrix Iaxm and a of matrices {Ca [Rmx") JoEM such that
1) Each Lo for M has strictly negatively row dominating diagonal:
[C] +
Σ
|[9|b] < O.
JE(1,2.....
2) The following holds for all E M:
A = LL
Then, the origin of asymptotically stable.
Lemma A.7 (Gerschgorin circle theorem [Horn and Johnson
2013). Let E R= whose i-th row
and j j-th colunn element is aij. Let (A(A) 5E(1.2....m\(4)
Σ
Oij. Consider the Gerschgorin circles
f E C: 12 anl S R.(A)): ==
The eigenvalues of A are in the union of Gerschgorin discs
G(A) = UZ E - a;a 1 S (A)A)).
Now, we state the lemma to guarantee positive definiteness Ax + my. Instead we prove positive definiteness of Anxo + XmaalCy (CT C. We follow the similar lines in Bharadwaj Diddigi et al. [2020]
Lemma A.8. Ler
((1+ (m)x((C)
7J )
M =
1
7pxxx
Under the following condition:
yd paxo (ea ea) 2 2-7
Amax (C)
max TEO (s.0)ESXA
2d(s,a) a)
2
where is the set of all deterministic policies, and @ is the Kronecker product, M is positive definite.
Proof. For simplicity of the notation, will denote d, d(s, a) and e; C, & C. for some i E (/2....|||||4] where i corresponds to some 8, E S x A.
We use Gerschgorin circle theorem for the proof. First, denote mij
[Max]] Then, one gets
mi di ((1+
17 Xm)x(()) 7e, p
myj = - d47e paxe. for i *
paxe
Except for the diagonal element, the row and column sums, respectively, become
Σ | 7d, (1- e. pxxees).
jES;
Σ
|mjal = nd paxse; - Nd.c paxe
jEs,
14

---

where S; = f1, 21.2..... { \ {a}. We need to show that x + M is positive definite. To this end, we use Lemma A.7 to have the following inequality:
2mgl -
Σ
mesl +
Σ
myjl-
jeS,
jES;
Considering the lower bound of A, we have
À 2 2mz
Σ
mmal
majal
jES;
JES:
2d ((1+
Amaa (C) - -y0 paxcee)
"
-7di(1 - es paxees)) (7dd palpp - -dd,e, paxo es)
2d
17 AAaax( (C) + (2 -ydd yd paxses.
Hence, for À > 0, we should have
n (C) ydl paxses
2 2-7
2d
2
Taking >
max # (E(1.2...((((1A]] definite. This completes the proof.
Amax
yd pax00
2d.
2/2)
we can make Maxe always positive
We first introduce a lemma to bound the inverse of a matrix norm:
Lemma A.9. [Page 351 in Horn and Johnson [2013 If M [Rax" satisfies || for some matrix norm ||- ||, then I M is non-singular, and
- M)- 1- M
Lemma A.10. Suppose that
| NOTDx|la2 <n.
Then, we have
(x DX + +n- '1 S 17 1-IXTDXII
1
Proof. We have
11(15 x xX)
[[xTXXX DX + -1
17
X DX DX+1X
17
1
1
77
7
|X
The first inequality follows from Lemma A.9
This completes the proof.
Lemma A.11. Fo > 7/|X D1
|X
6o + ||X DX loo, have
7 ||L Il < 1.
15

---

Proof. From the definition of , in (0)) we have
[[ nl
-7 |X D(X DX
+ 111)-1X(1
1
S> ||
DI
|X
00
"1 ||x |
<1.
The first inequality follows from Lemma A.10 The last inequality follows from the condition
> X|| Di + +XX
This completes the proof.
Lemma A.12. The equation 7 can be written as
X = L
Proof. Let expand the terms in 7
DDR (nl= X DX)0 7XX1 DP X6; - X D(R+7Pllxe;
(1) X DX)0;
X(nI + x -X) D(R PPIxe;; X = X
The last line follows from that X is full-column rank matrix. This completes the proof.
D| strictly negatively dominating diagonal.
Lemma A.13. For any E Rh, if > > Iox + ||X DX 1oo, then - -Aaxo n/ has
Proof. For 1 i h, we have
[-Anxo n/]üt +
Σ
||Axx nllil S 11+ Σ
[Axxolis
16(1.2....66M11
j=1
I - 17 + ||A 1lac
< - 11 + || || DX +7 +
<0.
The second last inequality follows the fact that ||P1lx,lbx S 1.
Lemma A.14 (Continuity of o with respect to 7)). Let njo be a non-negative real valued constant. Suppose 7/[ lloo < 1. Then, 4r; continuous at no--
Proof. Note that r, is continuous function of 1/. and we have,
I Do-tn I'm + O(n),
where O(-) stands for the big O notation. Therefore.
| no +
Xx 1lo0 =I[T no TXe* No t1 - I T TX 11
< || mo TX T(## ) 11 + O())
no [[ no lloc + O(7).
S no
The first equality follows from the definition of 4 t-- and no The second inequality follows from triangle inequality. The last inequality follows from the contraction property of the Bellman operator. Therefore, have
110% 0 lloo s CIIX6
lbx I O()):
where the first inequality holds because full-column rank matrix, and C is universal constant. This completes the proof.
D
16

---

A.4 Proof of Lemma 2.5
Proof. The first item follows from Lemma A.6 The second item follows from the fact that if all the subsystem matrices are negative-definte, then it will have V(z) = | as common Lyapunov function. This completes the proof.
A.5 Proof of Lemma 3.1
DX + m11 + D Proof. Let us prove the first item. When, 7/ + 0, we have (XT Therefore, we have I', + I' as 1/ 0.
Moreover, note that from Lemma A.10 for sufficiently large we have DXTDX + 1/1) is invertible. Therefore, we get
=| D(X DX + n1) -x]
<||
D
|
100 17 1 DX
where the first inequality follows from Lemma A.10 completes the proof of the first item.
As - oo, we get (Tyl - 0. This
Now, we will prove the second item. First of all, using Woodbury matrix identity (Hager 1989 in
Lemma A.3 we have
(X + -
(X DX + 17 'x (XXXXxTXXXXX)XXXXXx>>
2(XTDX)
where the inequality comes from the fact that (X DX + + (x DX)(X DX))- is positive semidefinite. Then, we have
|| = =||XT -IXXTD(XXTX D(X DX +
-Vis Al x D(X DX n1) X112
Sv S x Al |T|x 11 [|(X DX + 1)1)
Next, since the spectral norm is monotone, for any two symmetric positive semidefinite matrices A and B, A i/2 B implies || 2 [B]] which comes from the properties of the spectral norm for symmetric positive semidefinite matrices. Therefore, one gets
||, <|| DlI [[(X DX + -/)= 112 v /SS A
< <|| X Pll2 | [ -
1112 V 18 Al,
which is the desired conclusion.
A.6 Proof of Lemma 3.2
Proof. To show the existence and uniqueness of the solution of (9). we use Banach fixed-poin theorem. Note that enough show the existence and uniqueness of the solution of the following equation:
= (
YER.
(20)
This is because a solution y E Rº satisfying the above equation is in the image of X. We can find unique 0 such that XO 1y" because X is a full-column rank matrix. To this end, we will apply the Banach fixed point theorem:
11 - 32 = ||x DX + -1) DP1:i yn V1 - > DPH,,
DX + n1 - bo 31 II V2lloo
xXXX(X + - |10 111 Volloo
< 1l91 - y2lloc.
The second inequality follows from the non-expansiveness property of the max-operator. Now, we can use Banach fixed-point theorem to conclude existence and uniqueness of (20). This completes the proof.
17

---

A.7 Proof of Lemma 3.4
For the proof, suppose that T|
< 1. If the condition
S
7
(1 (1-211Fl1 [1 (X (x)
holds, ensures DX)
since
DXX 30 x X D + )
(1-7
1. Then, using Gelfand's formula in Lemma A.4
DX) "I XII X DI +01-
we can easily prove that the spectral radius (X) less than one. Next, note that for any
two square matrices A and B, (A - B) Li=o(A By A-1 if the spectral radius of A B is
less than one. Using this fact, one has
y ml
xX(X"
DX nI) x'
=7
X
mx DX "x' D
a
x(x ",-=""-"""- x=D +7 -x- Σ n
XX
XX + | X D
|
I m m || X
1X
where the second line uses the matrix inverse property. Therefore, 7 1| < 1 holds
T| + mm (X "I |X |TD|
<1.
1- 77 ([XI|(XX)XXX
Rearranging terms, one gets the desired conclusion.
A.8 Proof of Lemma 3.5
From the definition H in 100.. we have
y |l
Sy |
[xx + 11)
|X 11.0 D
S A
at
<1.
The second inequality follows from the assumption that XTDX al and || S 1. The last inequality follows from condition a|S||A] 1.
A.9 Proof of Lemma 3.6
Proof. Since we are going to consider the case - oo, assume that > DXTDX
y X
D | llc- From
have
|10||1
(X DX m!) (X DR+ x DPIlxe;X0 X07
1
x RTDR+ 7
X0
11
||XT
XTDXII
1
1
|
T DII || |0
||X DX
11 | DX
18

---

The first inequality follows from Lemma A.I0 y |||x"
Therefore, considering that >
|
D11 || Ioxo we have
n x DX II
-7
-
DI
|Ix
|10,
1
X DR
17 1x
IX
which leads to
0
x
DR|
DX - D|
X
As + the right-hand side of the above equation goes to zero, i.c., 87 - O.
A.10 Proof of Lemma 3.7
Proof. The bias term of the solution can obtained using simple algebraic inequalities.
| - Q" 11x 1
- rQ0ll [x
+ 1" Q" 11
S [ [(xx,) - Q' + 1-, 1l
= | T((0,) -T(Q)) - 1' - 10
Σ> || [X6 - 11 + +T,,0- - 1o
The first inequality follows from triangle inequality. The third equality follows from the fact that Q* the solution of optimal Bellman equation. The last inequality follows from the contraction property of the Bellman operator. Noting that 7 || < 1, we have
1
|0 - Q- I 1- -- TT
|1, - Q-
This finishes the proof.
A.11 Proofs to check Assumption A.2 for Theorem 5.2.
In this section, provide omitted proofs to check Assumption A.2 in Appendix Section A.2 the Borkar and Meyn Theorem in Lemma in the Appendix.
apply
First of all, Lipschitzness of (0) ensures the unique solution of the O.D.E.. Lemma A.15 (Lipschitzness). Let
f(0) - DPIxx DR.
(21)
Then, f(0) is globally Lipschitzness continuous.
Proof. Lipschitzness of f(0) can proven as follows:
[l) f(0'))l== = [[xx"xx + n/ lz + + DP Ixx X0')
< | DX 1//1==0100 -0 + + D 1l 11xo
2 (J T + ///1/0 + T | 0'
The last inequality follows from non-expansiveness property of max-operator. Therefore f(0) is Lipschitz continuous with respect to the |l.o.
Next, the existence of limiting O.D.E. of (66) can be proved using the fact that policy is invariant under constant multiplication when linear function approximation is used.
Lemma A.16 (Existence of limiting O.D.E. and stability). Let
f(0) (-XT DX - 1/)0 D DR. DR.
(22)
If n satisfies 15 there exists limiting O.D.E. of [2 and its origin is asymptotically stable.
19

---

Proof.
The existence of limiting O.D.E. can be obtained using the homogeneity of policy, II Nx(())
1xx--
f(c0) - (x* DX + nT)(c0) + yX +X'
lim f(cx) -
This be seen as switching system and, from Lemma A.8 and Lemma A.13
can apply
Lemma 2.5 Therefore, the origin is asymptotically stable
Lastly, we check conditions for martingale difference sequences. Lemma A.17 (Martingale difference sequence, mg. and square integrability). We have
Bim++1 F = 0,
miIlmx+ + 11 < Co(1 + 10x113)
where Co maxmm1x12)))m max 12 Maxxx 12 max 4m
Proof. To show {m,, k E NJ is martingale difference sequence with respect to the sigma-algebra generated by Gu. we first prove expectation of m4+1 is zero conditioned on Gu:
E E|m++1|9A] 0.
This follows from definition of b, C' and A
The boundedness E[] [T]]m < oo for E N also follows from simple algebraic inequalities. Therefore {m,,k & E NJ is martingale difference sequence.
Now, we show that the following hods:
E|l mx+ [2 s Co(11O 1).
Using simple algebraic inequalities, we have
E| m 12 Gx]
[[]6,,I(5k ax) + 170x E [5 ax) + n
[[166,0(8 ax) + x00x 112 + 1 (5x.00 (Nk, ax) + n011113
21 ax) + x C.]
41|11022005 (8k, || + 10 | [
12x 2mx B1| Px 11 max 20 0x + || (1)0 11
12X2 max R2 12 X= |
| 10
Co + 1 122)
max + 447). The fourth incquality follows from the fact that Ia + b+ 2 < 3) a|l 3 + 3|ec|2 Together with the above inequality, the square integrability
where Co == max(12x2
mux R2
! 12
of m, for E follows from the recursive update of 0g in (14). This completes the proof.
A.12 Proof of Theorem 5.1
Before moving onto the proof of Theorem 5.1
in order prove the stability using the upper and
lower systems, we need to introduce some notions such as the quasi-monotone function and vector comparison principle. We first introduce the notion of mnasimoootonee increasing function, which is necessary prerequisite for the comparison principle for multidimensional vector system.
Definition A.18 (Quasi- QQuasi-monotone function). Consider a vector-valued funcittoo f R - R with fn)" where Js R + R for E .,.,....,,, is said to be quasi-monotone
: Ifi f2 increasing if f((x) E S(ly) holds for all (1, 2........ n. and x. E RR. such that I, Yi and I S yj for all j #
20

---

Based on the notion of quasi-monotone function, we introduce the vector comparison principle.
Lemma A.19 (Vector Comparison Principle, Hirsch and Smith 2006]). Suppose that f are globally Lipschitz continuous. Let ir. be solution of the system
d
dt tt = f(xe), ERR, V 0.
Assume that [ quasi-monotone increasing, and let vs be a solution of the system
d
dt f(ve),
zo: V2
where [(v) S f(v) holds for any u E ER. Then, 02 S 34 for all & 2 O.
The vector comparison lemma can be used to bound the state trajectory of the original system by those of the upper and lower systems. Then, proving global asymptotic stability of the upper and lower systems leads global asymptotic stability of original system. We now give the proof of Theorem 5.1
Proof. First we construct the upper comparison part. Noting that
X 2 7x* DPIlxeX0,
(23)
and
XX DP X(0 07) 2 DD -7))
(24)
we define
f(y) and f(y) as follows:
f(v) (-x" - T + 7x DPIIX
f(y) = --x" n/ + yx² DPII oz) + x x DP(IIx(+40)) Ixxe)XX67
Using 23 and 24p. we have _(v) S f(v)-
is the corresponding O.D.E. of original system in 17) and becomes O.D.E. of the upper system. f becomes switched linear system.
Now, consider the O.D.E. systems
d
8: f(0!)) dt
8 0o.
d
0. E(O.). dl
Next, we prove quasi-monotone increasing property of f. For any y E TR²,, consider a non-negative vector p Rh such that its i-th element is zero. Then, for any
I h, have
of((+p)) (- (-x"
7/ 7x² DPII x tot X (3 +p)
= -x" + +n) - n + 70 x DPI x X
2 -x + +1) DPII,, = o()
where the inequality comes from of XT = due to Assumption 2.2 and e = since i-th element of is zero.
we can conclude that 0, S 6r. The condition (S1) in 15 ensures the switching matrices to have strictly negatively row dominating diagonal. Therefore, from Lemma A. and from Lemma 2.5) the global asymptotically stability of the origin follows. Likewise, the condition (S2) in (15) ensures that the matrices are all negative-definite, implying that the switching system shares ((0) = |00| as common Lyapunov function. Therefore, we can conclude that the upper comparison system is globally asymptotically stable.
Therefore by Lemma A.19 19
21

---

For the lower comparison part, noting that
x 2 7X" DPIT x X0,
can define [(v) and f(y) such that [(v) - [(y) as follows:
[(u) -x DXy y- + > D Xy+ X DR,
f(y) -X' -X my + 7x ; Xy+ X DR.
The corresponding O.D.E. system becomes
dt f: f(Ot):
- 0 f(0)), 63 < 0o.
(25)
dt
Proving the quasi- monntoiintt of f is similar to previous step. Consider a non-negative vector p E IR" such that its i-th element zero. Then, have
fly + ct (-(X- DX DX + nf) + + xx DPITX(*tD) x + X DR)
c= + +
+ 7x" DPIT x X(y + DR)
=e + 110 + DPIIx, + X (1))
The second equality holds since X is diagonal matrix and p; 0. Therefore by Lemma A. 19 we can conclude that 02 S Oz. The lower comparison part is linear system without affine term. Hence, following the similar lines in proving the stability of upper comparison system, we can conclude that (25) is globally asymptotically stable.
To prove uniqueness of the equilibrium point, assume there exists two different equilibrium points 0f and 85. The global asymptotic stability implies that regardless of initial state, 0g -> 0f and 0, 02. However this becomes contradiction if 0f * 05. Therefore, the equilibrium point is unique.
A.13 Proof of Theorem 5.2
Proof. To apply Lemma A.1 let check Assumption A.2
1. First and second statement Assumption A.2 follows from Lemma A.16
2. Third statement of Assumption A.2
follows from Theorem 5.1
3. Fourth statement of Assumption
A.2 follows from Lemma A.17
Since we assumed Robbins Monro step-size, can now apply Lemma
complete the proof.
A.14 Example for non-existence of solution of PBE
Let us define MDP whose state transition diagram is given in Figure 3
The cardinality of state
space and action space are |S| 3, |A| 2 respectively. The corresponding state transition matrix,
and other parameters are given as follows:
1
2
0
-2
O
1
O
1
Ri
=
0
Rg
0
2 0
0
1
0
1
0
0
P
P2
1
1
7
1
1
7 = 0.99,
d(s, a)
Vs E S, V. E A.
6'
22

---

s=2
s=1
2, xx1.2)
[001
Figure 3: State transition diagram
where the order of elements of each column follows the orders of the corresponding definitions. Note have same transition probabilities and reward. It is similar for the state = 3. In this MDP, there are only two deterministic policies available, denoted by тı and 22. that selects action = and action a = at state = respectively, i.c., (1) = 1 and (1) 2. The actions at state 2 and not affect the overall results.
that for this Markov decision process, taking action a = 1 and action a = state 8
do
The motivation of this MDP is as follows. Substitute xxo- in (5) with T1 and πτ. Then each of its solution becomes
0 0
0.85 0.72
0 05?
1.26
0-1 =
002 =
2
1.44
If Mi is the corresponding policy the solution of (5). means that action a greedily selected at state = 1. Therefore, (1, > Q11(1, 2) should be satisfied. However, since = x01, 1) x -0.85 and (1, = x11, 2) (c1 R -0.72, this contradiction. The same logic applies to the case for πT. Therefore, neither of them becomes solution of (5). On the other hand, considering (7) with = 4 which satisfies (I5), the solution for each policy becomes gr ~ 0.069, 0g1 z 0.032 and 0 x -0.669, 052 x 0.035, respectively, For and π2. we have Q 1) < T 2) and QTI (1, < (1,2) respectively, Hence, 6e2 satisfies (7) and becomes the unique solution.
A.15 Discussion on 15
In this section, provide further discussion 15 The two conditions (S1) and (S2) make matrix to have strictly negatively row dominating diagonal negative definite, respectively. We first provide a case where a matrix with strietly negatively row dominating diagonal is not necessarily a negative definite matrix, and vice versa. We will consider MDPs with y = 0.99.
A matrix with strictly negatively row dominating diagonal but not negative- Consider the following MDP with only single action for each state:
13
4
0
1
0 1
X
=
P
D
=
1
II =
2
where the matrix II represents the policy. Then, we have
78
-77
- - 7X DPIXX R
24
224.2
This is matrix with strictly negatively row dominating diagonal but M +M is not negative definite matrix.
A negative-definite matrix but not with strictly negatively row dominating diagonal: Consider the following MDP with single action for each state:
0
1 0 1
X
P
D
πT
0
5
0
Then, have
M:= -x DX
- +
DPIIX v
-025
-225
2225
20
23

---

M+M is negative definite matrix but M does not have strictly negatively row dominating diagonal.
Now, we provide example where the condition (S1) and (S2) in 115 does imply each other, iee, there are cases such that (S1) 2 (52) or (S2) 2 (S1):
As for the condition in (15), consider the following MDP with single action for each state:
0 II
[ 0
X
D
100
Pa
2
0
1
100
where P1 and P2 are two different transition matrices and the matrix represents the policy. First, considering P1, we have
(S1) x 7.9, (52) 196.
Meanwhile, considering P2 as the transition matrix, we have
(S1) ~ 7.9, (52) = 2. Therefore, (S1) and (S2) does not necessarily imply each other.
A.16 Pseudo-code
Algorithm Regularized Q-learning
1: Initialize 0g E R
2: Set the step-size (ax k=o and the behavior policy μa.
3: for iteration & = 0, l.... do
4: Sample $ d' and ag p.
5: Sample s P(sk. a): and rk+1 r(sks ak, sk)).
6: Update 0₂ using (13).
7: end for
B Experiment
B.1 Experiments
In this section, present experimental results under well-known environments in Tsitsiklis and Van Roy 1996]. Baird 1995], where Q-learning with linear function approximation diverges. In Appendix B.6 also compare performance under the Mountain Car environment (Sutton and
Barto 2018 where Q-learning performs well. In Appendix (B.5) we show experimental results under various step-sizes and 1). We also show trajectories of the O.D.E. of upper and lower comparison systems to illustrate the theoretical results.
B.2 0 + 20, Tsitsiklis and Van Roy 1996
Even when there are only two states, Q-learning with linear function approximation could di- verge [Tsissiklis and Van Roy] 1996). Depicted in Figure 4a| in Appendix B.4 from state one (0), the transition is deterministic absorbing state two (20). and reward is zero every time steps. Therefore, the episode length is fixed to be two. Learning rate for Greedy GQ (GGQ) and Coupled Q Learning (CQL), which have two learning rates, set 0.05 and 0.25, respectively in Carvalho ctt al.] [2020), Maei et al. [2010) Since CQL requires normalized feature values, we scaled the feature value with in Carvalho et al. (2020), and initialized weights as one. We implemented Q-learning with target network IZhang el al. 202T], which also have two learning rates, without projection for practical reason (Qtarget). We set the learning rate 0.25 and 0.05 respectively, and the weight v as two. For RegQ, we set the learning rate as 0.25, and the weight 7) as two. is averaged over five runs. In Figure 2a
we can see that RegQ achieves the fastest convergence rate.
B.3 Baird Seven Star Counter Example, Baird 1995
Baird 1995 considers an overparameterized example, where Q-learning with linear function ap- proximation diverges. The overall state transition is depicted in Figure 4b given in Appendix B.4

---

There are seven states and two actions for each state, which are solid and dash action. The number of features are h 15. At each episode, it is initialized random state with uniform probability. Solid action leads to seventh state while dashed action makes transition uniformly random to states other than the seventh state. At seventh state, the episode ends with probability 100 The behavior policy selects dashed action with probability 6 and solid action with probability ē. Since CQL in Carvalho et al. 2020) converges under normalized feature values, we scaled the feature matrix with v5 The weights set except for 0- 2. The learning rates and the weight 7, set same the previous experiment. As Figure 2b Our RegQ shows the fastest convergence compared to other convergent algorithms.
B.4 Diagrams for 0 - 20 and Baird Seven Star Counter Example
The state transition diagrams of A + 20 and Baird seven-star example are depicted in Figure 4a and Figure 4b respectively.
20
(a)
20
0g
0.
811
812
015
8
==1
==
8
==
8
91
7-0g
260
6g
28
20
20g + 0g
28 8
28
(b) Baird seven star counter example
Figure 4: Counter-examples where Q-learning with linear function approximation diverges
B,5 Experiments with varying hyperparameters
25

---

221
201
107
11o 0
110 10--0114 0'
4x10
1011
1x101
2x
0.25
2.55
0.5
2.1
Styps
Staps
(a) ThetaTwoTheta learning rate 0.01
(b) ThetaTwoTheta learning rate 0.05
68
0'
19--01 1
10.
2x
60
50
3t0ps
(d) Baird learning rate 0.05 Figure 5: Learning curve under differrnn learning rate and regularization coefficient
(c) Baird learning rate 0.01
In Figure 5 have ran experiments under 7 E 22-2,2-1,1, 1,2), and learning rate 0..01, 0.05. Overall, we can see that the convergence rate gets faster as increases.
B.6 Mountain car [Sutton and Barto 2018 experiment
Mountain Car is environment where state consists of position, and velocity, which are both continuous values. The actions are discrete, accelerating to left, staying neutral, and accelerating to the right. The goal is to reach the top of the mountain quickly as agent gets -1 reward every time step. We tile-coding [Sutton and Barto 2018 to discretize the states. We experimented under various tiling numbers and with appropriate 7j. it achieves performance as Q-learning does. We ran 1000 episodes for the training process, and the episode reward was averaged for 100 runs during test time. From Table I with appropriate RegQ performs comparable to Q-learning.
Table 1: Result of episode reward, step size 0.1. The columns correspond to 17. and rows correspond to number of tiles.
0.01
0.05
0.1
199.993 0.005
-200.0
199.28 1 0.074
199.993
0.005
4 4
196.631
0.179
-189.903 + 0.225
-194.178
0.166
-1966631 + 0.179
8 x 8
185.673 + 0.305
-163.08 + 0.248
-185.103
+ 0.219
-185.673 + 0.305
16 16
166.893
0.33
-158.152 + 0.251
-167.934
0.238
-166.893 + 0.33
26

---

B.7 O.D.E. experiment
Let us consider MDP with |S]
2, |A|
2, and the following parameters:
1
0
0
1141
X
D
0
0
2
0
0.5
0.5
[
P
R
7 0.99.
0.5
0.5
0.25
0.75
For this MDP, we will illustrate trajectories of the upper and lower system. Each state action pair is sampled uniformly random and reward is one for every time step. 2.25 is chosen to satisfy conditions of Theorem 5.T From Figure [ we can see that the trajectory of the original system is bounded by the trajectories of lower and upper system.
0.22
Rep baariig
0.22
-322
-80
-33
-05
-22
3.5
35
(a) 0 09
(b) 02 82
Figure 6: O.D.E. results
27

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have rigorously proved the result convergent Q-learnigg algorithm, and provided thorough analysis the quality of its solution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have cleary stated the Assumptions used througout the paper. Moreover, as a limitation, we discuseed that the convergence solution is biased, and provided thorough analysis on its error bound.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer:
[Yes]
Justification:
We have provided thorough analysis in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The experimantal envirnoments are fairly simple and well-known in the community, thus making it easy to reproduce.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We have attached the code the supplementary files.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipps.c/ppbllc//uuui http:///ggiddeeeeCouSuuumbbbbii cotobmisssiii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have stated the choice of step-size, which the only hyper-parament
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We have plotted the error bar.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
30

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: NA
Justification: Our experiments can simply run normal computer because we do not require any heavy computation including using GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp////.errppp..ccpacpbi/////
Answer: [Yes]
Justification:
The authors have checked NeurlPS Code Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theoretical paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We did not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papprssiiiitt. thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
There are no such risks.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "gclMYTyUZp", "reviewer": "Reviewer_haoJ", "summary": "Q-learning is a popular RL algorithm. With function approximation, though, it is known that this algorithm can diverge. This issue is attributed to the `deadly triad': off-policy learning, bootstrapping, and function approximation. This work addresses this issue in the context of linear function approximation. Specifically, this work proposes a novel called Regularized Q-learning, in which a suitable regularization term is added to the standard update rule. The key result (Theorem 5.2) is that this modified algorithm almost surely converges. The proof is based on the switching systems.", "questions": "L1. The current work only studies the setting where the $(s_k, a_k, r_{k + 1}, s_{k + 1})_{k \\geq 0}$ sequence is sampled in an IID fashion in each iteration. Do you think the results carry over to the scenario with Markovian samples?\n\nL2. Are there any realistic examples of the feature matrix $X$ for which the condition in (11) is guaranteed?\n\nMinor issues:\n\nM1. Line 90: Shouldn't you emphasize what s_0's distribution is? \n\nM2. Line 96: Which Markov chain is assumed to be time-homogeneous?\n \nM3. Line 176: \"... true action value may not lie...\" Do you mean the \"optimal\" value function may not lie in the subspace...?\n\nM4. Line 181: `In this case, there are more chances...' Do you have any evidence for this statement?", "limitations": "Yes, the authors have discussed the limitations of their work. However, there are more serious issues with the work which I have highlighted.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. The paper introduces a new Q-learning algorithm called Regularized Q-learning (RegQ), which ensures convergence under linear function approximation. This addresses the known instability issue in traditional Q-learning with function approximation.\n\nS2. The paper uses the switched system theory to derive RegQ's convergence.", "weaknesses": "W1. The present work studies **only** the case of Q-learning with linear function approximation under a **fixed behavior policy**. This approach is extremely restrictive and practically not very useful since the quality of the resulting policy critically depends on the choice of the behavior policy. Specifically, as stated by Melo, Meyn, and Ribeiro (2008), for the approximate Q-learning algorithm to discover the optimal policy, the behavior policy would need to be close to the optimal policy itself, which is not feasible. For other choices of behavior policy, the policy estimated by the algorithm could be significantly different from the optimal policy. While Lemma 3.7 provides some guarantees, it is unclear how this result relates the greedy policy, with respect to $X \\theta_{\\eta}^*,$ to the optimal policy.\n\nThis is why $\\epsilon$-greedy exploration is commonly used in practice. However, the current work does not address this important case. Under $\\epsilon$-greedy exploration, several recent studies [1] -- [3] have shown that Q-learning with function approximation suffers from various significant issues beyond instability. Notably, this algorithm can converge to non-locally optimal policies, sometimes even the worst, and exhibit policy oscillation. It remains unclear if the regularization term proposed in the present work would effectively address these issues with $\\epsilon$-greedy exploration.\n\nReferences:\n\n[1] Patterson, A., Neumann, S., White, M. and White, A., 2023. Empirical design in reinforcement learning. arXiv preprint arXiv:2304.01315.\n\n[2] Young, K. and Sutton, R.S., 2020. Understanding the pathologies of approximate policy evaluation when combined with greedification in reinforcement learning. arXiv preprint arXiv:2010.15268.\n\n[3] Gopalan, A. and Thoppe, G., 2022. Demystifying Approximate Value-based RL with $\\epsilon $-greedy Exploration: A Differential Inclusion View. arXiv preprint arXiv:2205.13617.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1** *The work studies only the case of a fixed behavior policy. This approach is extremely restrictive and practically not very useful .... Specifically, as stated by Melo, Meyn, and Ribeiro (2008), ..., the behavior policy would need to be close to the optimal policy, ...., the policy estimated by the algorithm could be significantly different from the optimal policy. While Lemma 3.7 provides some guarantees, it is unclear how this result relates ... to the optimal policy. .... , the current work does not address  $\\epsilon$-greedy exploration. Under $\\epsilon$-greedy exploration, several recent studies ... have shown that Q-learning ... suffers from various issues beyond instability. .... It remains unclear if the regularization term proposed in the present work would effectively address these issues with $\\epsilon$-greedy exploration.*\n\n**A1** We thank the reviewer for the insightful comments. In the following, we clarify the concerns raised by the reviewer:\n\n1) We would like to first note that our assumption of a fixed behavior policy is standard in the literature [4,5]. It is important to note that even under such fixed behavior policy assumption, the convergence of Q-learning with linear function approximation has not been fully explored yet. We proposed a simple and convergent algorithm compared to previous works that guarantee convergence under linear function approximation.\n\n2) We would like to emphasize that our work does not rely on the assumption used in Melo, Meyn, and Ribeiro (2008). Specifically, we do not require the behavior policy to be close to the optimal policy. In fact, we only require the state-action probability induced by the fixed behavior policy to be non-zero, which is a standard assumption in the literature [4,5].\n\n3) Lemma 3.7 provides a tight bound on the error of the estimated solution and the true solution, $Q^*$. If the error bound with $Q^*$ is small enough, then the estimated policy will be close to the optimal greedy policy.\n\nAs the reviewer suggested, an interesting avenue for future research would be to investigate these properties under an epsilon-greedy behavior policy. Following the reviewer's comments, we have added the discussion in the revised manuscript.\n\n**Q2** *The current work only studies the setting where the state-action sequence is sampled in an IID fashion in each iteration. Do you think the results carry over to the scenario with Markovian samples?*\n\n**A2**  Thank you for the valuable comments. We believe our result can be also extended to the Markovian sample cases. In [6], the authors demonstrated an extension of the Borkar and Meyn Theorem to the Markovian sample cases. Since our proof relies on Borkar and Meyn Theorem, our result can also be extended to establish convergence under Markovian samples. According to the reviewer's comment, we have incorporated this result into the revised manuscript. \n\n**Q3** *Are there any realistic examples of the feature matrix for which the condition in (11) is guaranteed?*\n\n**A3** We thank the reviewer for the constructive comments. If we scale the feature matrix such that $\\max(||X||,||X^{\\top}||)<1$, then choosing $\\eta>2$ satisfies the condition (11) by Lemma 3.3 in the manuscript. Scaling the values of feature matrix is a commonly employed technique in the both theoretical literature or in practice. Consequently, the condition in (11) can be easily met in practice. Following the reviewer's comments, we have added the related discussion in the revised manuscript.\n\n**Q4** *l 90 :  Shouldn't you emphasize what $s_0$'s distribution is?*\n\n**A4** Thank you for pointing out important insights on the paper. In our analysis, we assume that the state-action distribution to satisfy $d(s_0,a_0)>0$ for all $(s_0,a_0)\\in{\\cal S}\\times{\\cal A}$. Moreover, if we assume an ergodic Markov chain, the initial distribution does not matter because for any initial distribution, it will converge to stationary distribution of the Markov chain. We have added the discussion in the main manuscript. \n\n**Q5** *l 96 : Which Markov chain is assumed to be time-homogeneous?*\n\n**A5** Thank you for the insightful comments. A Markov chain is said to be time homogeneous if the transition probability does not change over time. We will clarify this in the revision.\n\n**Q6** *l 176 : \"... true action value may not lie...\" Do you mean the \"optimal\" value function may not lie in the subspace...?*\n\n**A6** Thank you for the valuable comments. As the reviewer mentioned, it means that optimal action-value function, $Q^*$, may not lie in the subspace. We will clarify this in the revised manuscript.\n\n\n**Q7** *l 181: `In this case, there are more chances...' Do you have any evidence for this statement?*\n\n**A7** Thank you for carefully investigating our manuscript. This is an intuitive result based on the following facts: The Bellman equation $X \\theta^* = {\\cal T} X \\theta^*$ hardly admits a solution because the right-hand side in general does not lie in the column space of $X$ due to the Bellman operator $\\cal T$. This situation can be partially alleviated by projecting the right-hand side ${\\cal T} X \\theta^*$ onto the column space of $X$ using the projection operator $\\Gamma$: $X \\theta^* = \\Gamma {\\cal T} X \\theta^*$. \nAccording the reviewer's comment, the corresponding discussions will be modified in the revised manuscript in order to further clarify this intuition.\n\n**References**\n\n[4] Sutton, Richard S., et al. \"Fast gradient-descent methods for temporal-difference learning with linear function approximation.\" Proceedings of the 26th annual international conference on machine learning. 2009.\t\n\n[5] Lee, Donghwan, and Niao He. \"A unified switching system perspective and ODE analysis of Q-learning algorithms.\" arXiv preprint arXiv:1912.02270 (2019).\t\n \n[6] Liu, Shuze, Shuhang Chen, and Shangtong Zhang. \"The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise.\" arXiv preprint arXiv:2401.07844 (2024).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fouwZneYFc", "reviewer": "Reviewer_yA4E", "summary": "The paper introduces a new regularized Q-learning algorithm \"RegQ\" suitable for linear function approximation, which essentially adds an $\\ell^2$ regularization term to the TD error in semi-gradient Q-learning. The authors prove that this addition ensures convergence of the algorithm and analyze the error with respect to the unregularized solution.", "questions": "1. Where does equation (6) come from? To solve an equation like $A\\theta = b$ iteratively, I would construct a loss function $L(\\theta) = \\frac{1}{2}||A\\theta - b||^2$ and do gradient descent: $\\theta_{k+1} = \\theta_k - \\alpha_k\\nabla L(\\theta_k)$, where $\\nabla L(\\theta_k) = A^\\top(A\\theta - b) + E$, with $E$ containing additional terms if $\\nabla A \\neq 0$. Equation (6) looks similar at first but is in fact quite different. Could you explain how you arrived at equation (6)?\n2. How should equation (15) be interpreted? How \"large\" does $\\eta$ actually have to be to ensure convergence?", "limitations": "The authors adequately address the limitations of their work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper centers on an important issue in reinforcement learning: the deadly triad, which is the failure of off-policy TD algorithms when combined with function approximation. This issue has been addressed in practical (deep) RL by expensive methods such as target networks. This paper proposes a simpler solution (specifically for the case of linear function approximation): regularization of the TD error. The paper is very clearly written and provides extensive sections on the background and related work. Their assumptions seem reasonable, and their analysis is rigorous. The overall contribution is highly significant.", "weaknesses": "1. The biggest weakness of this paper is the limited experiment section. I understand that this is a theoretical work, and of course don't expect any large-scale experiments. However, the two experiments they do list are not properly explained. (What are these baseline algorithms?) The takeaway from the experiments is that their method has a faster convergence rate, but it is not explained why. The convergence rate is not mentioned elsewhere in the paper, where the focus lies on proving convergence, where other methods do not converge! It would be great to show an environment where RegQ converges while the baseline methods do not, or where the error of RegQ's approximate solution $\\theta_\\eta^\\star$ is smaller than the baselines'.\n2. Please comment on Assumption 2.2 (orthogonality of columns of $X$). Could it be relaxed? In high-dimensional ($|\\mathcal S||\\mathcal A|$) spaces, $h \\ll |\\mathcal S||\\mathcal A|$ _random_ vectors are nearly orthogonal with high probability. Could this be used to show that the result will hold with high probability when using random features?\n3. Figure 1c is not properly explained. What are the \"shrinking\" and \"blowing up\" phases? Why does the vector $x$, located on the _unit circle_ have norm $0$?\n4. For Lemma 3.5, it is assumed that $X^\\top D X = aI$. I understand that this is just an example of when a solution to the RPBE exists, but it should be clarified that this assumption is very unrealistic (earlier you wrote that $h \\ll |\\mathcal S||\\mathcal A|$, which is a contradiction).\n5. In line 245, you state that, as $\\theta^\\star = \\theta_\\eta^\\star$ if $\\eta = 0$, it holds that $\\theta^\\star \\to \\theta_\\eta^\\star$ if $\\eta \\to 0$. You are implicitly assuming that $\\theta_\\eta^\\star$ is a continuous function of $\\eta$ (at $\\eta = 0$), which you should at least mention, if not prove.\n6. (minor) In the introduction, you do not mention at all that you also analyze the error $\\theta_\\eta^\\star - \\theta^\\star$, which to me is a very important part of your work, and would not be out of place in the \"summary of main contributions\" at the end of your introduction.\n7. (minor) As you talk about the deadly triad and how it has been addressed practically in deep RL, you might also want to cite \"Deep reinforcement learning and the deadly triad\" by van Hasselt et al. (2018).\n8. (typo) In line 215, you swap (9) and (4), changing the meaning in a significant way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful feedback, and the time and effort for reviewing our paper. Following the reviewer's comments, we have added the related discussion in the revised manuscript:\n\n**Q1** *The biggest weakness of this paper is the limited experiment  ... . The two experiments they list are not properly explained. (What are these baseline algorithms?) The takeaway from the experiments is that their method has a faster convergence rate, but it is not explained why. ... It would be great to show an environment where RegQ converges while the baseline methods do not, or where the error of RegQ's approximate solution is smaller than the baselines.*\n\n**A1.** Thank you for the insightful comments. The baseline algorithms are Q-learning variants that converges under linear function approximation, which are explained in Appendix Section D. The algorithms are Coupled Q-learning (CQL), GreedyGQ, and algorithms with target-network update (targetQ). As the reviewer suggested, we have newly provided an example, where RegQ converges while one of the baseline algorithm, CQL, does not converge in the PDF file attached in the global response. This is because CQL requires the norm of the feature matrix to be smaller than one. Meanwhile, we could not verify practical examples showing divergence of GreedyGQ or targetQ while RegQ diverges or vice-versa. This is because the Q-learning variants are developed to guarantee convergence to some solutions. However, we summarized the difference on the theoretical points in G1 in the global response. \n\nLastly, the experiment results show that RegQ has a faster convergence rate under some scenarios. An intuitive reason for this is because the baseline algorithms are basically a two-time scale algorithms whereas RegQ uses a single-time step-size.  A detailed exploration of convergence rates is a promising direction for future research. Following the reviewer's comments, we have added the related discussions in the revised manuscript.\n\n**Q2** *Please comment on Assumption 2.2 (orthogonality of columns of $\\Phi$). Could it be relaxed?*\n\n**A2** Thank you for the insightful comments on the our paper. The assumption is required for the construction of comparison systems in the switched system analysis, and it seems that relaxing this condition in the current phase is non-trivial. However, the orthogonality assumption is not very restrictive and can be met easily in practice. For instance, we can use orthogonal Fourier basis functions as feature functions. Additionally, it may be possible to develop more advanced techniques in the future that can relax this assumption through coordinate transformations. This could be an interesting agenda for future research. Moreover, as the reviewer suggested, initialization of random vectors can guarantee such condition with high probability. We believe the suggested arguments can be used to justify the assumption.\n\n**Q3** *In Figure 1c, what are the \"shrinking\" and \"blowing up\" phases? Why does the vector $x$, located on the unit circle have norm $0$?*\n\n**A3** Thank you for the careful investigation of our manuscript. This a typo and the correct expression is $||x||_{\\infty}=1$. We will correct this in the revised manuscript. Regarding the terms shrinking and blowing up phases, we have provided a response G2 in the global rebuttal. \n\n**Q4**  *For Lemma 3.5, it is assumed that $X^\\top D X = aI$. .. just an example ... but it should be clarified that this assumption is very unrealistic (earlier you wrote that  $h\\ll  |{\\cal S}||{\\cal A}|$, which is a contradiction).*\n\n**A4** Thank you for pointing out the issue. Following the reviewer's comments, we will clarify this point in the manuscript that such cases are unrealistic and differ from the case of $h\\ll  |{\\cal S}||{\\cal A}|$.\n\n **Q5** *In line 245, you state that, as* $\\theta^*=\\theta_{\\eta}^*$ *if $\\eta=0$, it holds that* $\\theta^*\\to \\theta^*_{\\eta}$ *if $\\eta\\to 0$. You are implicitly assuming that is a continuous function of $\\eta$ at 0.*\n\n**A5**  We have provided a proof in G3 in the global response. We would like to note that before guaranteeing the continuity of $\\theta^*_{\\eta}$, it should at least exist in a neighborhood of $\\eta = 0$. Therefore, to guarantee the existence of $\\theta^*_{\\eta}$ around $\\eta = 0$, we have added the condition $\\gamma||\\Gamma||_\\infty<1$. Then, under the existence, we can prove the continuity of $\\theta^*_{\\eta}$ at $\\eta=0$. Moreover, this result can be easily extended to the case that the solution $\\theta^*_{\\eta}$ exists for a positive $\\eta > 0$.\n\n **Q6** *Where does equation (6) come from?*\n\n**A6**  Equation (6) is not a gradient of any objective function. It iteratively solves an equation $A\\theta=b$ by $\\theta_{k+1}\\leftarrow \\theta_k + \\alpha(A\\theta_{k}-b)$., which is a widely used algorithm called a Richardson iteration [1]. It simply updates by the difference of the left and right term of the equation. \n\n**Q7** *How should equation (15) be interpreted? How \"large\" does $\\eta$ actually have to be to ensure convergence?*\n\n**A7**  In equation (15), the terms (S1) and (S2) correspond to the condition for the stability of the switched system in each item of Lemma 2.5 to be satisfied, respectively. As noted in Appendix A.15, each condition covers different scenarios. However, the bound can be always chosen to be small because it only needs to be larger than the minimum of two quantity, (S1) and (S2). As show in Lemma 3.3, $\\eta>2$ only needs to be met if we use feature scaling, which is widely used in practice. However, we note that there are several cases when (S2) can be smaller than (S1), as noted in the Appendix A.15. \n\nWe thank again the reviewer for the constructive comments. Following the reviewer's comments, we have incorporated the above discussions in the revised manuscript.\n\n**References**\n[1] Kelley, Carl T. Iterative methods for linear and nonlinear equations. Society for Industrial and Applied Mathematics, 1995.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TqGnBbhiKG", "reviewer": "Reviewer_mviV", "summary": "This paper proposes a new Q-learning variant with linear function approximation called RegQ, and proves that its ODE form converges (even when associating it with linear function approximations).\n\nQ-learning is famously known to be affected by the 'deadly triad': it tends to diverge in practice when combined to off-policyness, function approximation and bootsrapping. Analyzing formally the convergence of Q-learning combined with simple linear function approximations helps understanding more precisely the mechanisms at play in the deadly triad, and paves the way toward RL with more solid foundations.\n\nAuthors show empirically that RegQ is faster than two related algorithms with guaranteed convergence. Besides, RegQ relies on a single time-scale, while the other baseline algorithms use two time-scales.", "questions": "- Although there are empirical evaluations, including one on Mountain Car, more ambitious empirical tests with regularized variants of Q-learning-based deep RL algorithms would be interesting.\n\n- Could the proposed algorithm fit the framework of regularized MDPs introduced in [\"A Theory of Regularized Markov Decision Processes\", Geist et al., 2019]? If yes, could results in [\"A Theory of Regularized Markov Decision Processes\", Geist et al., 2019] be directly applied to the proposed method, including for instance the analysis of the changes on the optimal policy due to regularization (error bound)? Including a discussion on this existing framework in the paper seems relevant.\n\nTypos:\n\nl9: 'has known to diverge' -> 'was known to diverge'\n\nl64: \"guarantees convergence\" => \"guarantee convergence\"", "limitations": "Limitations are well addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- One of the most appealling properties of the framework proposed in this paper is its simplicity: just regularizing projected Bellman equations allows to obtain convergence proofs without relying on several artificial assumptions.", "weaknesses": "- In the related work, the paper lists several existing works proving the convergence of Q-learning under linear function approximation with some theoretical assumptions.\nThe assumptions made in the present paper are weaker than most of the ones of existing works, which include restrictions on the Markov chain types, dependency between behavior and target policy, other guarantees than convergence, etc. However, the closest work is by Lee and He (2019), and the present paper does not explicitely state in what way the assumptions are now weaker than in Lee and He. It states that Lee and He's assumption on the behavior and feature matrix seems too stringent to check in practice, but nothing more precise. When Lee and He improved the sufficient condition of Melo et al. (2008), they showed that their new condition was strictly weaker than the previous one, and I believe that a similar analysis should be made. More structure in the comparison would make the paper look less like an incremental modification of Lee and He (2019).\n\n- The presented work follows the direction proposed in Lee and He (2019) by reducing the convergence analysis to that of a switching system, establishing simpler upper and lower bound systems and applying the Borkar and Meyn theorem to obtain a proof of the asymptotic convergence. There are of course différences in the approach, but they are in the details.\n\n- It can be regretted that the most interesting and novel parts of the paper are in Appendix, which shows that the conference format. might not be the best fit for it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1** *In the related work, the paper lists several existing works proving the convergence of Q-learning under linear function approximation with some theoretical assumptions. The assumptions made in the present paper are weaker than most of the ones of existing works, which include restrictions on the Markov chain types, dependency between behavior and target policy, other guarantees than convergence, etc. However, the closest work is by Lee and He (2019), and the present paper does not explicitely state in what way the assumptions are now weaker than in Lee and He. It states that Lee and He's assumption on the behavior and feature matrix seems too stringent to check in practice, but nothing more precise. When Lee and He improved the sufficient condition of Melo et al. (2008), they showed that their new condition was strictly weaker than the previous one, and I believe that a similar analysis should be made. More structure in the comparison would make the paper look less like an incremental modification of Lee and He (2019).*\n\n**A1.** We thank the reviewer for the valuable insights. Lee and He (2919) considered the following condition: \n$$\\phi^\\top_i D + \\phi^\\top_i \\gamma DP \\Pi_{\\pi}\\sum_{j\\in \\{1,2,\\dots,n\\}}\\phi_j<0 ,\\quad \\pi \\in \\Theta_{\\Phi},$$\nwhere $\\Theta_{\\Phi}:= \\{ \\pi\\in\\Theta : \\pi(s)=arg\\max_{a\\in\\mathcal{A}} (\\Phi\\theta)(s,a) ,\\forall s \\in \\mathcal{S},\\theta\\in\\mathbb{R}^n \\}$, $\\Theta$ is the set of greedy policies, and \n\\begin{align*}\n \\phi_i= \\begin{bmatrix}\n    \\phi_i(1,1) & \\phi_i(2,1) & \\cdots & \\phi_i(|\\mathcal{S}|,|\\mathcal{A}|)]^{\\top} \\end{bmatrix}.\n\\end{align*}\n The above condition is strict because it needs to hold for all the policy $\\pi\\in\\Theta_{\\Phi}$. In contrast, we do not require such condition. We only require the regularization coefficient $\\eta$ to be larger than certain value, which can be easily met by scaling the feature matrix. In particular, the condition on $\\eta$ can be met by scaling the norm of feature matrix to be smaller than one, and $\\eta$ only needs to be larger than two. This follows from Lemma 3.3 in the manuscript. Moreover, we note that feature scaling is widely used in practice. Following the reviewer's comments, we will incorporate the discussion in the revised manuscript.\n\n\n**Q2** *The presented work follows the direction proposed in Lee and He (2019) by reducing the convergence analysis to that of a switching system, establishing simpler upper and lower bound systems and applying the Borkar and Meyn theorem to obtain a proof of the asymptotic convergence. There are of course differences in the approach, but they are in the details.*\n\n\n**A2** We appreciate the reviewer's constructive feedback. While our approach aligns with the principles outlined by Lee and He (2019), the following points are new in the literature:\n\n1) We established the theoretical conditions for regularization term to ensure convergence of the algorithm; Moreover, as mentioned in A1, simply adding a regularization term allows to weaken the assumptions used in prior works including Lee and He (2019);\n\n2) We characterized the existence and uniqueness of the regularized projected Bellman equation depending on $\\eta$;\n\n3) A tight error bound between the solution regularized projected Bellman equation and true solution, $Q^*$ is provided.\n\nEach of the above points has not been studied previously, and our work provided a thorough analysis for the above points . Following the reviewer's comments, we will clarify this in the revised manuscript.\n\n\n**Q3** *It can be regretted that the most interesting and novel parts of the paper are in Appendix, which shows that the conference format. might not be the best fit for it.*\n\n**A3** We thank the reviewer for the valuable comments. As the reviewer mentioned, the proofs are deferred to the Appendix due to the space limit. However, we highlight that our contribution lies is the analysis of the properties of RPBE and the development of RegQ. We have provided thorough analysis of RPBE in Section 3, and have further elaborated on this, including additional details on Figure 1c of the manuscript in G1 of the global rebuttal. Additionally, as answered in A1 and A2, we will clarify the points regarding the analysis of RegQ. Following the reviewer's comments, we have incorporate these clarifications in the revised manuscript.\n\n**Q4** *Although there are empirical evaluations, including one on Mountain Car, more ambitious empirical tests with regularized variants of Q-learning-based deep RL algorithms would be interesting.*\n\n**A4** We thank the reviewer for the insightful comments. In the revised manuscript, we will consider more ambitious empirical evaluations on the variants of Q-learning-based deep RL algorithms.\n\n**Q5** *Could the proposed algorithm fit the framework of regularized MDPs introduced in [\"A Theory of Regularized Markov Decision Processes\", Geist et al., 2019]? If yes, could results in [\"A Theory of Regularized Markov Decision Processes\", Geist et al., 2019] be directly applied to the proposed method, including for instance the analysis of the changes on the optimal policy due to regularization (error bound)? Including a discussion on this existing framework in the paper seems relevant.*\n\n**A5** Thank you for the insightful comments. The domain of the regularization term used in Geist et al., 2019 is restricted to a probability simplex, for example an entropy regularization. The work focuses on the regularization over the policy space instead of the Q-function, and also focuses on the policy iteration algorithms instead of reinforcement learning or Q-learning. The $l$-2 type regularization we consider does not fall into this category, and the extension is non-trivial. We will incorporate the discussion in the revised manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NMwr7kKyV8", "reviewer": "Reviewer_cMMt", "summary": "This paper introduces a novel approach, RegQ, which is a framework for dealing with linear approximation of Q-function. Compared to the instability of the traditional Q-learning with function approximator, which is known as the deadly triad, RegQ addresses this problem by regularization term, making the algorithm more stable. Also the theoretical approach ensures convergence of linear function approximation.", "questions": "In equation (13), what delta_k means?\nAlso, in line 290, why m_k+1 is an i.i.d. noise? Is it an assumption, or can it be proved?\n\nIn Figure2, the y-axis means the max norm of Q-values. I’m wondering about the value of y axis. At the initial stage of the episode, all of the algorithms have already shown 1e-18, and 1e-20 values, and what the authors claim is RegQ converges when others fail. My question is this: why initial point or other algorithms( which is shown 1e-18 error) is not considered as converged? Also, since values are \ntoo small, how could authors prevent the contamination by the floating point error? It will be easy to understand if the authors give more explanation about experiments.\n\nIn Figure 1c, I can’t find the details about the phases: ‘Blowing up phase’, and ‘Shrinking phase’.\nI read the author’s error analysis, but there’s no explanation about the phase. Is it just a intuitive naming on the convergence behavior? If not, could you elaborate more about it in the theoretical context?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper gives a novel approach with theoretical rigor.\nThe most noteworthy strength of this paper is that it tackles a practical problem: the instability of Q-learning with linear function approximator, compared to other theoretical paper that gives impractical solutions.\nAlthough the theory is highly technical, this paper gives a good logical explanation, also Figure 1 helps readers to understand the proposed projection operator.", "weaknesses": "Most of the concerns arose from the lack of experiment scope, prior work comparison, and implementation. \nAuthors claim about the strengths of the RegQ algorithms, but lots of claims are not confirmed by experiments.\nAlso, the claims are given with the comparison of the prior work, but experimental results are not sufficient to validate those claims.\nIt might be helpful to gain confidence about the novelty of the paper, \nAlso, it is hard to get a precise understanding of the algorithm since there are lack of implementation details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1.** *Most of the concerns arose from the lack of experiment scope, prior work comparison, and implementation. Authors claim about the strengths of the RegQ algorithms, but lots of claims are not confirmed by experiments. Also, the claims are given with the comparison of the prior work, but experimental results are not sufficient to validate those claims. It might be helpful to gain confidence about the novelty of the paper. Also, it is hard to get a precise understanding of the algorithm since there are lack of implementation details.*\n\n**A1.** Thank you for the constructive comments. We would like to first note that due to the page limits, all the experiments are included in the Appendix B.. Similarly, the implementation details are given in the Appendix B. Moreover, we want to clarify that our main focus is on the theoretical analysis of proposed RegQ algorithm and regularized projected Bellman equation. We proposed a **convergent** algorithm under linear function approximation and mild assumptions and provided a thorough analysis on the conditions for the convergence. The comparison with prior works are mainly in theoretical sense, e.g., weaker assumption on the behavior policy or relaxing additional assumptions used in prior works. Moreover, the analysis on the properties of regularized projected Bellman equation is new in the literature.\n\nThe experiments are provided to verify the convergence of the proposed algorithm and provide further insights on its behavior, e.g., convergence rate. Our claim is that RegQ can show faster convergence rate than other algorithms under certain scenarios, which is verified in Section 6. An intuitive reason why our algorithms shows faster convergence is that the baseline algorithms ( CQL, targetQ, and GreedyGQ ) are basically a two-time scale algorithm whereas our proposed algorithm uses a single-time scale step-size. Moreover, regarding the implementation detail, a pseudo-code is given in Appendix A.16. Following the reviewer's comments, we have added the discussion in the revised manuscript.\n\n\n**Q2.** *In equation (13), what $\\delta_k$ means? Also, in line 290, why $m_{k+1}$ is an i.i.d. noise? Is it an assumption, or can it be proved?*\n\n\n**A2.** We thank the reviewer for the constructive comments. For the first question, $\\delta_k$ is the TD error, which is defined below in the equation (2) in the manuscript. $m_{k+1}$ is not an i.i.d. noise but the Martingale difference sequence, which includes the i.i.d. noise scenario as a special case, and which is shown in Lemma A.14 in the Appendix. We will correct the typo in the revision. We would like to note that the Martingale difference sequence scenario is an assumption, and it cannot cover the case that the transitions are sampled from a single trajectory (or Markovian sampling scenario). \nIn [1], the authors demonstrated an extension of the Borkar and Meyn Theorem to the Markovian sample cases. Since our proof relies on Borkar and Meyn Theorem, our result can also be extended to establish convergence under Markovian sample cases. We have incorporated this result into the revised manuscript. \n\n**Q3.** *In Figure2, the y-axis means the max norm of Q-values. I’m wondering about the value of y axis. At the initial stage of the episode, all of the algorithms have already shown 1e-18, and 1e-20 values, and what the authors claim is RegQ converges when others fail. My question is this: why initial point or other algorithms( which is shown 1e-18 error) is not considered as converged? Also, since values are too small, how could authors prevent the contamination by the floating point error? It will be easy to understand if the authors give more explanation about experiments.*\n\n**A3.** Thank you for the valuable comments. We agree with the reviewer. For clarification on the error bound, we have provided the first 50 steps in Figure 1a and 2a in the pdf file attached to the global response. The confusion arose because in the original manuscript,  we have plotted the x-axis by episode, which consists of number of updates. In the corrected plot, we plotted the x-axis with number of updates. The initial point is not the convergence point because the error is larger than one, as can be seen in the corrected plot. According to the reviewer's comment, the figures have been replaced with the new ones in the revision, and more details of the figures have been newly added.\n\nMoreover, we would like to clarify that our claim does not mean that other algorithms fail while RegQ converges. Our claim is that under certain situations, the convergence rate of RegQ can be faster than that of other algorithms. An intuitive reason why our algorithms shows faster convergence is that the baseline algorithms ( CQL, targetQ, and GreedyGQ ) are basically a two-time scale algorithm whereas our proposed algorithm uses a single-time step-size. Following the reviewer's comment, we will update our manuscript.\n\n**Q4.** *In Figure 1c, I can’t find the details about the phases: ‘Blowing up phase’, and ‘Shrinking phase’. I read the author’s error analysis, but there’s no explanation about the phase. Is it just a intuitive naming on the convergence behavior? If not, could you elaborate more about it in the theoretical context?*\n\n**A4.** Thank you helping us to improve the clarity of our manuscript. Regarding the terms shrinking and blowing up phases, we have provided a response G2 in the global rebuttal. To clarify this further, the related discussions have been newly added in the revision.\n\n**References**\n\n[1] Liu, Shuze, Shuhang Chen, and Shangtong Zhang. \"The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise.\" arXiv preprint arXiv:2401.07844 (2024).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KKdWxkAGsb", "reviewer": "Reviewer_x1RW", "summary": "This paper provides Q-learning convergence (asymptotic) in linear architectures with regularization power. Their algorithm is tested on mountain car example.", "questions": "na", "limitations": "na", "rating": 5, "confidence": 3, "soundness": 1, "presentation": 1, "contribution": 3, "strengths": "Q-learning convergence in linear architectures is an important problem in RL.", "weaknesses": "-  The analysis follows ODE style analysis from Borkar and Meyn. So it is asymptotic. However, non-asymptotic guarantees (rate of convergence) can be provided when assuming non-zero stationary distribution (like Assumption 2.1). For e.g. see Chen et al, 22. There are research on extension to QL like TD-Learning convergence in linear architectures. So I think with the current tools one can give such finite time guarantees with some more effort. This work relies on old works such as Gosavi [2006] and Melo et al., [2008]. *Although, I would be curious to know where the current hurdles are.*\n  - A recent work titled \"Regularized Q-Learning with Linear Function Approximation\" (https://arxiv.org/pdf/2401.15196) are providing non-asymptotic results for a similar problem. I have not looked at the details, but since this appeared in arxiv in Jan 2024, please do include what the contributions are of this work compared to this one.\n\n- Section 3.2 can be further improved w.r.t writing. I believe Lemma 3.3, 3.4, 3.5 are provided as independent results to satisfy Eq.(11) (which is crucial for existence and uniqueness of RPBE solution). But I am curious to know why 3 different Lemmas are provided.\n  - How is eq.(15) constructed for $\\eta$? I understand Lemma 3.3 helps for (S1). But I am not sure how (S2) came about. \n  - It is mentioned at line 228 that $\\eta>2$ is enough for Lemma 3.3. But $\\eta<1$ for Lemma 3.4. I really hope Lemma 3.3 and 3.4 are **not required** to be satisfied simultaneously for the current results to hold.\n  - Where is Lemma 3.1 used? We are in linear architecture setting. So Lemma 3.1 (b) inequality which involves $S\\times A$ must be avoided. Linear architectures are helpful only when one can replace rate of convergences involving $S\\times A$ can be replaced by feature-size $h\\ll SA$.\n\nMy score reflects this review provided here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1** *The analysis follows ODE style analysis from Borkar and Meyn. So it is asymptotic. However, non-asymptotic guarantees (rate of convergence) can be provided when assuming non-zero stationary distribution (like Assumption 2.1). For e.g. see Chen et al, 22. There are research on extension to QL like TD-Learning convergence in linear architectures. So I think with the current tools one can give such finite time guarantees with some more effort. This work relies on old works such as Gosavi [2006] and Melo et al., [2008]. Although, I would be curious to know where the current hurdles are*\n\n**A1** Thank you for the valuable comments. As the reviewer mentioned, we believe finite-time analysis of RegQ is possible. However, our primal goal is to develop a new Q-learning algorithm with linear function approximation that converges under relaxed or different scenarios. We consider proving the asymptotic convergence of Q-learning with linear function approximation as an initial step and the finite-time bound can be also proved following the spirit of related literature. We appreciate the provision of interesting research topics, which remain for future exploration. According to the reviewer's comment, the related discussions will be added in the revision. \n\nMoreover, we would like to note that our work does not rely on the work of Melo et al.,[2008]. We also note that Melo et al.,[2008] requires strong assumptions on the behavior policy to be met, whereas we do not requires such assumptions. Furthermore, we provided a comparison with existing algorithms in G1 of the global response, which clarifies current hurdles and the novelty of our approach. Following the reviewer's comment, we will add the associated discussions in the revised manuscript.\n\n**Q2** *A recent work titled \"Regularized Q-Learning with Linear Function Approximation\" are providing non-asymptotic results for a similar problem. I have not looked at the details, but since this appeared in arxiv in Jan 2024, please do include what the contributions are of this work compared to this one.*\n\n\n**A2** Thank you for the insightful comment. The regularization considered in ``Regularized Q-Learning with Linear Function Approximation'' requires to be bounded, e.g., an entropy regularizer. The $l$-2 type regularization which we consider in our work does not fall into this category, and the extension is non-trivial. Following the reviewer's recommendation, we will incorporate the discussions on the comparisons in the revised manuscript.\n\n\n**Q3** *Section 3.2 can be further improved w.r.t writing. I believe Lemma 3.3, 3.4, 3.5 are provided as independent results to satisfy Eq.(11) (which is crucial for existence and uniqueness of RPBE solution). But I am curious to know why 3 different Lemmas are provided.*\n\n\n**A3** Thank you for helping us to improve the clarity of our manuscript. We provided three different lemmas because each addresses different scenarios for (11) to hold. Lemma 3.3 covers when $\\eta$ is larger than certain threshold, Lemma 3.4 considers the case when $\\eta$ is nearby the origin, and Lemma 3.5 applies for for all $\\eta$. Following the reviewer's comment, we will improve the clarity in the revised manuscript.\n\n\n**Q4** *How is eq.(15) constructed for $\\eta$? I understand Lemma 3.3 helps for (S1). But I am not sure how (S2) came about.*\n\n**A4** We thank the reviewer for the insightful comments. The conditions in (S1) and (S2)  is used to guarantee $(A_{\\pi_{X\\theta_k}} + \\eta I)$ to have strictly negatively dominant diagonal or to be a negative definite matrix, respectively. In particular (S2) comes from the item 2 in Lemma 2.5, which guarantees the asymptotic stability of a switched system. The proof for the derivation of (S2) is given in Lemma A.6. in the Appendix of the manuscript. Note that the conditions (S1) and (S2) do not necessarily imply each others, which are discussed in Appendix A.15 of the manuscript. We will add the above discussion in the revised manuscript.\n\n\n**Q5** *It is mentioned at line 228 that $\\eta>2$ is enough for Lemma 3.3. But $\\eta<1$ for Lemma 3.4. I really hope Lemma 3.3 and 3.4 are not required to be satisfied simultaneously for the current results to hold.*\n\n\n**A5** Thank you for the valuable comments. Lemma 3.3 and Lemma 3.4 are only sufficient conditions but not necessary conditions for (11) to hold. Therefore, the two statements do not contradict each other. Moreover, we would like to note that Lemma~3.4 does not require the condition $\\eta<1$. It only assumes the scenario $|| \\gamma \\Gamma ||_\\infty < 1$. Following the reviewer's comment, we will clarify these points in the revised manuscript.\n\n**Q6** *Where is Lemma 3.1 used? We are in linear architecture setting. So Lemma 3.1 (b) inequality which involves $S\\times A$ must be avoided. Linear architectures are helpful only when one can replace rate of convergences involving $S\\times A$ can be replaced by feature-size $h<<SA$*\n\n**A6** We thank the reviewer for the insightful comments. Lemma 3.1 is provided for a theoretical understanding on how $\\Gamma_{\\eta}$ behaves as a function of $\\eta$. \n\nThe inequality in Lemma 3.1 (b) demonstrates that $\\Gamma_{\\eta}$ remains bounded for all $\\eta$ and does not diverge. We do not directly use the upper bound in Lemma 3.1 for our analysis, and it is not related to the rate of convergence. We will clarify this in the revised manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate the reviewers’ constructive comments for our manuscript. The comments are valuable for improving the quality of our paper and provide important guidance for our research. 

In the following, we address the concerns commonly raised by the reviewers.

**G1** Reviewers yA4E and x1RW  raised concerns regarding the comparison with existing works that guarantee the convergence of Q-learning with linear function approximation under mild conditions. The algorithms compared include Coupled Q-learning (CQL), GreedyGQ, and algorithms with target-network updates (targetQ).

1) GreedyGQ algorithm is guaranteed to converge to some solution. However, the solution is not a solution of the projected Bellman equation, of which its quality is difficult to quantify. However, we provide a tight bound for our solution in the error bound in Lemma 3.7. Moreover, it is a two-time scale algorithm which is known to be slower than a single-time scale algorithm like ours.


2)  CQL is also a two-time scale algorithm whereas our algorithm is a single-time scale algorithm. As noted previously, two-time scale algorithms are often known to be slower than single-time scale algorithm. This is demonstrated experimentally in Section 6 in the manuscript. Moreover, as can be in the Figure 1c in the PDF file attached in the global response, the algorithm is sensitive to the scaling of the feature matrix, and the solution is not a solution of the projected Bellman equation, of which its quality is difficult to quantify.


3) To guarantee the convergence of targetQ (which uses target network update), it requires a projection or truncation method. This causes additional complexity in its implementation. The resulting solution lacks interpretability, as it may lie on the boundary of the projection or truncation ball. Lastly, the target network update can slow down the convergence rate, which can be verified in Section 6 in the manuscript.

**G2** Reviewers yA4E and cMMt raised concerns regarding the terminology of shrinking and blowing phase in Figure 1(c). We consider the scenario that $|| \gamma\Gamma ||\_{\infty} < 1$ holds, which implies that $|| \gamma \Gamma_0 ||\_\infty < 1$ because $\Gamma = \Gamma_\eta$ when $\eta = 0$. The figure implies that as $\eta\to\infty$, $\gamma \Gamma_\eta$ can potentially move outside of the unit ball, and this phase is indicated with the term **blowing up** phase. However, since $\lim\_{\eta\to\infty } {|| \gamma \Gamma _\eta ||\_\infty } = 0$, we know that $\gamma \Gamma\_\eta$ will eventually converge to the origin and move inside the unit ball. This behavior is indicated by the **shrinking** phase in the figure.

- Additional proofs

**G3**  (Response to Q5 of Reviewers yA4E )

**Lemma** ( Continuity of $\theta^*_{\eta}$ in terms of $\eta$ )
Let $\eta_0$ be a non-negative real valued constant. Suppose $\gamma||\Gamma_{\eta_0}||\_{\infty}<1$. Then, $\theta^*_{\eta}$ is continuous at $\eta_0$.

*Proof)*
Note that $\Gamma_{\eta}$ is continuous function of $\eta$, and we have, 
\begin{align*}
    \Gamma_{\eta_0+\eta} = \Gamma_{\eta_0} + O(\eta),
\end{align*}
where $O(\cdot)$ stands for the big O notation. Therefore, 
\begin{align*}
    || X\theta^*_{\eta_0+\eta}-X\theta_{\eta_0}^*||\_{\infty} =& || \Gamma_{\eta_0+\eta}\mathcal{T}X\theta^*_{\eta_0+\eta}-\Gamma_{\eta_0} \mathcal{T}X\theta^*_{\eta_0} ||\_{\infty}\\\\
     \leq &  ||\Gamma_{\eta_0} {\cal T} X (\theta^*_{\eta_0+\eta}-\theta^*_{\eta_0}) ||\_{\infty}+O(\eta)\\\\
     \leq & \gamma ||\Gamma_{\eta_0} ||\_{\infty} ||X (\theta^*_{\eta_0+\eta}-\theta_{\eta_0}^*)||\_{\infty}+O(\eta).
\end{align*}

The first equality follows from the definition of $\theta^*_{\eta_0+\eta}$ and $\theta^*_{\eta_0}$. The second inequality follows from triangle inequality. The last inequality follows from the contraction property of the Bellman operator.
Therefore, we have
\begin{align*}
 ||\theta^*_{\eta_0+\eta}-\theta^*_{\eta_0}||\_{\infty} \leq C   ||X\theta^*_{\eta_0+\eta}-X\theta^*_{\eta_0}||_{\infty} \leq O(\eta),
\end{align*}
where the first inequality holds because $X$ is full-column rank matrix, and $C$ is a universal constant. This completes the proof.
*Q.E.D*

We sincerely appreciate the reviewer's feedback. In response to the comments, we have incorporated the relevant discussions into the revised version.

Meta-review: The reviewers of the paper agreed that the contribution is both interesting and very relevant, as Q-learning with function approximation is a widely used algorithm. The reviewers pointed out that the theoretical analysis is the same as in Lee and He 2019, and this was a major reason to reject the paper. The reviewers compared their reviews, discussed the contributions of the paper, and there most critical reviewers were not against acceptance at the end.
Decision: Accept (poster)