Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set
Authors: Xinyu Liu
Zixuan Xie
Shangtong Zhang
Venue: ICML 2025 poster (2025)
Keywords: linear $Q$ learning
convergence rate
reinforcement learning
the deadly triad
Primary area: theory->reinforcement_learning_and_planning

Abstract: $Q$-learning is one of the most fundamental reinforcement learning algorithms.
It is widely believed that $Q$-learning with linear function approximation (i.e., linear $Q$-learning) suffers from possible divergence until the recent work Meyn (2024) which establishes the ultimate almost sure boundedness of the iterates of linear $Q$-learning.
Building on this success,
this paper further establishes the first $L^2$ convergence rate of linear $Q$-learning iterates (to a bounded set).
Similar to Meyn (2024),
we do not make any modification to the original linear $Q$-learning algorithm, do not make any Bellman completeness assumption,
and do not make any near-optimality assumption on the behavior policy.
All we need is an $\epsilon$-softmax behavior policy with an adaptive temperature.
The key to our analysis is the general result of stochastic approximations under Markovian noise with fast-changing transition functions.
As a side product,
we also use this general result to establish the $L^2$ convergence rate of tabular $Q$-learning with an $\epsilon$-softmax behavior policy,
for which we rely on a novel pseudo-contraction property of the weighted Bellman optimality operator.

Linear Q-Learning Does Not Diverge in L
Convergence Rates to a Bounded Set
Xinyu Liu 1
Zixuan Xie
Shangtong Zhang'
Abstract
(1989) uses a look-up table for representing the action-value function. To improve generalization and work with large or even infinite state spaces, linear function approximation is used to approximate the action value function, yielding linear Q-learning
Q-lcarning is one of the most fundamental rein- forcement learning algorithms. It is widely be- lieved that Q-learning with linear function ap- proximation (i.e., linear Q-learning) suffers from possible divergence until the recent work Meyn (2024) which establishes the ultimate almost sure boundedness of the iterates of linear Q-learning. Building on this success, this paper further es- tablishes the first L convergence rate of linear Q-learning iterates (to a bounded set). Similar to Meyn (2024), we do not make any modification to the original linear Q-learning algorithm, do not make any Bellman completeness assumption, and do not make any near-optimality assumption on the behavior policy, All we need is an e-softmax behavior policy with an adaptive temperature. The key to our analysis is the general result of stochas- tic approximations under Markovian noise with fast-changing transition functions. As side prod- uct, we also this general result to establish the 2 convergence rate of tabular Q-learning with an e-softmax behavior policy, for which we rely on a novel pseudo-contraction property of the weighted Bellman optimality operator.
Linear Q-learning is, however, widely believed to suffer from possible divergence (Baird, 1995; Sutton & Barto, 2018). In other words, the weights of linear Q-learning can possibly diverge to infinity as learning progresses. However, Meyn (2024) recently proves that when an e-softmax be- havior policy with adaptive temperature is used, linear Q-learnng does not diverge. Instead, the weights are even- tually bounded almost surely. Or more specifically, let {we] be the weights of linear Q-learning. Meyn (2024) proves that sup; |ws]] < C' almost surely for some determinis- tic constant C. Building on this success, we further provide nonasymptotic analysis of linear Q-learning by establish- ing the first 1.2 convergence rate of linear Q-learning to bounded set. Specifically, we establish the rate at which B[]|well diminishes to a bounded set. Notably, this work differs from many previous analyses of linear Q-learning (prior to Meyn (2024)) in that, except for the aforemen- tioned behavior policy, we do not make any modification to the original linear Q-learning algorithm (e.g.. no target network, weight projection, experience replay, no i.i.d. data, regularization). We also the weakest possible assumptions (e.g.. no Bellman completeness assumption, no near-optimality assumption on the behavior policy). Table I summarizes the improvements.
1. Introduction
Reinforcement learning (RL, Sutton & Barto (2018)) emerges as a powerful paradigm for training agents to make decisions sequentially in complex environments. Among various RL algorithms, Q-learning (Watkins, 1989; Watkins & Dayan, 1992) stands out as one of the most celebrated (Mnih et al., 2015). The original Q-learning in Watkins
Our L convergence rate made possible by a novel result concerning the convergence of stochastic approximations under fast-changing time-inhomogeneous Markovian noise, where the transition function of the Markovian noise evolves as fast as the stochastic approximation weights, i.e., there is only a single timescale. By contrast, Zhang et al. (2022) obtain similar results only with a two-timescale framework, where the transition function of the Markovian noise evolves much slower than the stochastic approxima- tion weights.
'Equal contribution 'Department of Computer Science, Uni- versity of Virginia. Correspondence to: Xinyu Liu <xinyuliu@ exinyulu@@virgnia..du virginia.edu.>
Zixuan Xie <xic.zixuan @ @emal. virginia.edu>> Shangtong Zhang <shangtong @ virginia.edu>>.
As side product, we also use this general stochastic ap- proximation result to establish the L convergence rate of tabular Q-learning with an e-softmax behavior policy. To
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Convergence Rates of Lincar Q-Lcarning
Behavior Policy
Type
Algorithm Modification
Assumptions
Rate
B
M
10T
T-E
Melo et al. (2008)
linear
/
/
/
P
Lee & He (2020)
linear
/
dy
Chen et al. (2022)
linear
/
/
/
Carvalho et al. (2020)
linear
/
/
/
dy
Zhang et al. (2021)
linear
/
/
Nolsmmm
Gopalan & Thoppe (2022)
linear
/
/
d arg
Chen et al. (2023)
linear
/
1
Han-Dong & Donghwan (2024)
linear
1
dy
Meyn (2024)
linear
Fan et al. (2020)
neural
dy
Xu & Gu (2020)
neural
Pax
/
Cai et al. (2023)
neural
du-
Zhang et al. (2023b)
neural
Me,arg max
Theorem
linear
/e.ssolmmxx
Table 1. Summary of notable analyses of linear Q-lcariing We additionally include Q-lcarning with neural networks for completeness. The exact definitions of the terminologies used in the columns and more detailed exposition of the table are in Section 4. ">PE" is checked target network is not used. "ø" is checked experience replay is not used. "H" is checked weight projection is not used. "J[ut]]"" is checked if additional regularization is used. "T--xi"" is checked if Bellman completeness assumption is not used. "X" checked if no restrictive assumptions on the features are used. "Rate" is checked if a convergence rate is provided. For the "Behavior Policy" column, "x" indicates that fixed behavior policy used. "ys." indicates that fixed behavior policy is used and assumption of the behaivor policy is made. are max" indicates that an e-greedy policy is used, "Ae,sotmmx" indicates that an e-softmax policy used. Let po E {M,, pl.. pe,arg max: se, } be any type the aforementioned behavior policy. Then dan indicates that i.i.d. samples from the stationary distribution of po is provided directly instcad of obtaining Markovian samples by executing Po-
strong near-optimality
Bchavior Policy
au(Sr
Rate
Watkins (1989); Watkins & Dayan (1992); Jaakkola et al. (1993)
Tsitsiklis (1994); Littman & Szepesvári (1996)
any
Szepesvári (1997)
dy
Even-Dar et al. (2003)
any
Lee & He (2020)
dy
Devraj & Meyn (2022)
Chen et al. (2021); Li et al. (2024); Zhang & Xie (2024)
Theorem 2
Me. softmmx
Table Summary of notable analyses of tabular Q-learning. The exact definitions of the terminologics used in the columns and a more detailed expesition of the table are in Section 4. "(u4(ee=tt;7"" is checked if count based learning is not required. Notably, analyses of the synchronous variant of tabular Q-learning is not surveyed in this paper.
our knowledge, this is the first time that such convergence rate is established. The key to this success is the identi- fication of a novel pseudo-contraction property of the weighted Bellman optimality operator. Table summa- rizes the improvements over previous works.
be L-smooth (w.r.t. some norm |1-11.) if Vw, w',
s(w') s (ww) + (VS(w), w/ - w) + 1'll -wl (1)
Since all norms in finite dimensional spaces are equivalent, when say a function is smooth in this paper, it means it is smooth w.r.t. any norm (with L depending on the choice of the norm). In particular, to simplify notations, we in this paper use ||=|| to denote an arbitrary vector norm such that its square ||-11 is smooth. We abuse ||-Il to also denote the corresponding induced matrix norm. We use ||-Il, to denote the dual norm of ||-I]- We use |l-Ilz and I|-I1 to denote
2. Background
Notations. We use (x. = x TTy to denote the standard inner product in Euclidean spaces. A function f is said to
2

---

Convergence Rates of Lincar Q-Learning
the l and infinity norm. We use functions and vectors exchangeably when it does not confuse. For example, f can denote both function S + IR and vector in IR S] simultaneously.
Here we have abused Mi to also denote the behavior policy used in (linear Q-learning), which is defined as
exp exp(xw=((.a) Σ3 _, exp(pe bT
Mw iss = | + (1
(3)
We consider an infinite horizon Markov Decision Process (MDP, Bellman (1957)) defined by a tuple (S, A. P. T, 7: po), where S is a finite set of states, A a finite set of actions, p: : S 8 x A + [o, 1] is the transition probability func- tion, : S x A + R is the reward function, y E 10 is the discount factor, and po S - [0, 1] denotes the ini- tial distribution. At the time step 0, an initial state So is sampled from Po- At the time step f, an action Ag is sam- pled according to some policy π : A x S + [0. 1]. i.e., A, ~ (-((.)). A reward R = r(,,, At) is then emitted and successor state 1 is sampled from p(-|S,, Ad). We use Pa to denote the transition matrix between state action pairs for an arbitrary policy π, i.e., Px [(s, a), (s'.a') p(s'|s, a)x (a'ls'). We use f- S x A + R to denote the action value function of a policy ग. which is defined as 9a (s, a) = Eg [E= RS+ = fundamental task in RL is control, where the goal is to find the optimal action value function, denoted as qa. sat- isfying q- (s) 2 4 (=(8a))Vr a. It is well-known that the qu is the unique fixed point of the Bellman optimality operator T RISIIA + RISHAA defined as (Tg)(s, a)
where E (0, and the temperature parameter Ko is de- fined as
No
| 2
T
(4)
150
otherwise
with No > O being a constant. To our knowledge, this behaivor policy is first used in Meyn (2024). The soft- max approximation of the greedy operator ensures the continuity of thu- The adaptive temperature Ko further ensures the Lipschitz continuity of the expected updates of (linear Q-learning). Both are key to our finite sample analysis and are discussed in details shortly in the proofs.
3. Main Results
Assumption 3.1. The Markov chain { induced by uni- formly random behavior policy is irreducible and aperiodic.
A, =14=004 a). One
Notably, since c is required to be strietly greater than O, Assumption 3.1 ensures that for any w and any q, the Markov chain induced by ju and My also irreducible and aperiodic. This is common assumption to analyze imm-inhhomgennsuu Markovian noise (Zhang et al., 2022).
Σ. E6'Pl''s,, a) [r(s, + y max." ((s',a'}
Tabluar Q-Learning. Q-learning is the most celebrated method to estimate 9.. In its simplest form, it uses a lookup table q E IR SI1AA to store the estimate of q. and generates the iterates {g:} as
Assumption LR. The learning rate is Or ((+t))r where E, (0.5, 1J. 0, to > 0 are constants.
Theorem 1 (L² Convergence Rate of Linear Q- Q-Learning). Let Assumptions 3. and LR hold. Then sufficiently small in (3), sufficiently large Kg in (4), and sufficiently large to in as there exist some constant such that the iterates
(tabular Q-learning) 6, = Ru+1 + t max, (S(41,,, a²) (S.., g++1 (S., A.) = (S,, At) + ar
A.- ~ Mg. (-18)),
(wi) generated by (linear Q-learning) satisfy the following statements Vt f.
Here, {ar} are learning rates and My is the behavior policy. In this paper, we consider an e-softmax behavior policy defined as
(1) When = 1, there exist some constants BI,,, B1,2, and
B₁, such that
1 + +1 () exp(g(sa)) En explq
(2)
IE
|| 12
B S (c+to) "1,2"
/ + B1,3.
(2) When Ca E (0. 1), there exist some constants BJ,a, B1,s and B1,6 such that
where e E (0, controls the degree of exploration.
Linear Q-Learning. To promote generalization or work with large state spaces, Q-learning can be equipped with lin- ear function approximation, where we approximate 9-(s,, a) with a(s a) T Tw. Here 8 x AA + RRd is the feature fune- tion that maps a state action pair to d-dimensional feature and w E Rd is the learnable weight. Linear Q-learning generates the iterates {w;} } as
E
um 12
27
S BI,eexp (-
B1,3 (- T-ca + to))
/olll2
+ B1,6.
The proof of Theorem in Section 5.2. The precise constraints on Ku and specified in Lemma 16 in Ap- pendix. The constants B and B1,6 depend on 7, (S), [.4.. max,.0 Ir(s, a)), and max, || a)122- with the detailed dependency specified in Section C.4. Theorem confirms the main claim of the work, with B1,3 and Bi,6 correspond- ing to the bounded set.
(linear Q-learning) 8, = Re+1 + 7 max x (SS11,, T We x(S,, Ar) T.)T,,, We: 1 = wi + (5,,0((S, At).
A, ~ Mun (-1St)
3

---

Convergence Rates of Lincar Q-Lcarning
Theorem 2 (L2 Convergence Rate of Tabular Q-Learning). Let Assumptions 3.1 and LR hold. Then for sufficiently large to in an, there exist some constant i such that the iterates }wi} J generated by (tabular Q-leaming) satisfy the following statements Vt. 2 [.
and 5.3. Specifically, our Assumption 3.1, combined with the use of e-softmax behavior policy where 6 <>> 0, en- sures that any policy Pw E Ap induces an irreducible and aperiodic Markov chain. Consequently, Assumption A1 ensures that for any w, the Markov chain induced by P. has a unique stationary distribution, which we denote as dy.w- This allows us to define the expected update as h(w) = Eyrddy. [H (w, y)]. One important implication of uniform ergodicity is uniform mixing, which plays key role in our analysis in Section 5.1. We next present a few assumptions about Lipschitz continuity.
(1) When Ea = 1, there exist some constants B2,1, B2,2 and B2,3 such that
18 1l 9-1120)
go 10 + Bag lnfe+to) (1+22)) 2122 1100
B1.1
(e++a) m (1.01p0))
Assumption A2. There exists constant CA2 such that H [[ v) (H(2,,)) w)ll s Caallwi w2ll Vwi, w2, y- Assumption A3. There exists a constant CAs such that
(2) When & E (0.5, 1), for any c E (0.5, sa), there exist some constants B2, B2,5, and B2,6 such that
B B[10= [1.1:3)
(-
Broa 1e++oy to) - 1-11.0
wn - Pwal 11 S I+1| [en | H|/l
Ca.
||w wall,
$ B2,1 exp + B2, + (1)) 10)2
I-ta
[h(w1) - h(w22)l <CAs |11
wel
Vw1. W2.
Assumption A3', For any given wo, there exists a constant UAs such that the iterates {wr) generated by (SA) satisfy
The proof of Theorem 2 is in Section 5.3. The constants B2,4 and B2,6 depends on Ea. and e'x. Comparing Theorems 1 & 2, it is now clear that (tabular Q-learning) converges to the optimal action value function while (linear Q-learning) con- verges only to a bounded set, despite the (linear Q-learning) adopts a more complicated behavior policy with an adap- tive temperature. We note that the softmax function in (3) and (2) can be replaced by any Lipschitz continuous fune- tion. We use the softmax function here because softmax policy is commonly used approximation for the greedy policy.
sup t
||wel
< UA a.s.
Furthermore, there exist a constant CAs' such that
|P Puall CAP w| wwel Vwi, W2. and for any W1, w2 satisfying max {1lwil || S UAS
l1h(w)) h(w2)ll S CAN w2l1-
Notably, Assumption A3 uses a stronger Lipschitz condition for Pw than Assumption A3'. Moreover, Assumption A3 requires hww) to be Lipschitz continuous on IR while As- sumption A3' requires h(w) to be Lipschitz continuous only on compact subsets. The price that Assumption A3' pays to weaken Assumption A3 is an additional assumption that the iterates are bounded by a constant almost surely. The partic- ular multiplier 1/(1+ + || || + ||w>l]) is inspired by Assump- tion 5.1(3) of Konda (2002) for analyzing actor critic algo- rithms. We will use Assumption A3 for (linear Q-learning) and Assumption A3' for (labular Q-learning. Let Wret be any fixed vector in Rd. We now introduce
Stochastic Approximation. We now present a general stochastic approximation result, which will be used to prove Theorems and 2. In particular, we consider general iterative update rule for weight vector Rd, driven by stochastic process {hi} evolving in finite space V:
w = wi + az (we, Y(+1),
(SA)
where H: : Rd y + Rd defines the incremental update. The key difficulty in our analysis results from the fact that we allow (Y,} to be a sime-inhomogeneous Markov chain with transition functions controlled by {w.}.
Assumption A1. There exists a family of parameterized transition matrices Ap = {Pw E TR ww E [Rd] such that Pr(Y++1 Y.)= = Pu. Ye+1). Furthermore, let Ap denote the closure of Ap. Then for any P E Ap, the time- homogeneous Markov chain induced by P is irreducible and aperiodic.
L(w) 1 [ wrerll
(5)
to present our general results regarding {we} in (SA).
Theorem 3. Let Assumptions A1, A2, and LR hold. Let at least one of Assumptions A3 and A3' hold. Then there exist some constant i and some function f(t 0( In (1((t++++1) such that the iterates {wi) generated by (SA) satisfy Vt 2 f
(8+to)
Assumption Al is standard uniform ergodicity condition (cf. Marbach & Tsitsiklis (2001) and Assumption 3.2 in Zhang et al. (2022)). It is readily satisfied in our frame- work, and we provide its formal verification in Section 5.2
(W[+)l <(1 + [(w)) + +.. f(t).
4

---

Convergence Rates of Lincar Q-Lcarning
The proof of Theorem 3 is in Section 5.1. Theorem 3 gives a recursive bound of I(w;). We will realize Wrer differently and bound (VL(wz), h(wr)) differently for (linear Q-learning) and (tabular Q-learning).
the first L convergence rate of (linear Q-learning) without making any algorithmic modification or strong assumptions the behavior policy. This setting is known to be compu- tationally challenging. Kane et al. (2023) show that finding the optimal policy is NP-hard even if q. is linear in the given features. This inherent difficulty highlights the importance of establishing convergence to a bounded set, as our work does, especially under minimal assumptions. Despite that Q-learning with neural network is also analyzed in previous works, those work do not supercede our work since they also need to make algorithmic modifications. Some of them even need the Bellman completeness assumption, i.e., for any w, the vector 7 TX w still lies in the column space of X.
4. Related Works
Previous analyses of (linear Q-learning) typically involve different modifications to the algorithm. The first is target network (Mnih et al., 2015), where slowly changing copy of {w:} is stored. This copy is called the target network and is referred to as {we). Then the TD error 6, in (linear Q-learning) is computed us- ing max, x(S(+1, a') ww instead of max, #($(41, d' The second is a replay buffer (Lin, 1992). After ob- taining the tuple (St, As, R 1(41), intead of apply- ing (linear Q Q-learning) directly, they store the tuple into a buffer, sample some previous tuple (s, r,,,, from the buffer, and then apply the update based on the sampled tuple. The third is projection, where the update to w, is modified as wi+1 = II(wr + At)) Here II is a projection operator that projects the weights into some com- pact set make sure {w,} is always bounded. The fourth is regularization. One example is change the update to we as W = We + (5, A.) a, V | where the last term corresponds to ridge regularization. Such regu- larization is also used to facilitate boundedness of [w:)- Besides the algorithmic modification, strong assumptions on the features X are also sometimes made. For exam- ple. Lee & He (2020) assume all column vectors of X are orthogonal to each other and and each elements of X is either 0 or 1. Finally, different assumptions on the data are also used to facilitate analysis. For example, Lee & He (2020); Carvalho et al. (2020); Han-Dong & Donghwan (2024) assume that (St, A,, Re+1, St+1) is sampled in an i..dd manner from a fixed distribution. Gopalan & Thoppe (2022) further assume that (St. A,, Re+1, S(-1) sampled from the stationary distribution of the current e-greedy pol- icy, i.e., not only the samples are i..dd., but also the sampling distribution changes every time step. Melo et al. (2008); Chen et al. (2022) make strong assumptions on the behavior policy. Melo et al. (2008) use a special matrix condition as- suming Σn - 22 (w) is positive definite for any w. Here En is the feature covariance matrix induced by the fixed behaivor policy and [x(ww) is the feature covariance matrix induced by the greedy policy w.r.t. w. Chen et al. (2022) assume [max, (0(s, a) (T)Tw)))) w) < ([(((s,)) a) Yy.... Since those assumptions are made w.r.t. all possible w. for them to hold, one typically needs to ensure that the behaivor policy μ is close to the optimal policy in certain sense. See Section 6 of Chen et al. (2022) for more discussion about this. Similar strong assumptions are also later on used for analyzing Q-learning with neural networks (Cai et al., 2023; Xu & Gu, 2020). As can be seen in Table 1, this work is
There is a rich literature in analyzing (tabular Q-learning). Early works (Watkins, 1989; Watkins & Dayan, 1992; Jaakkola et al., 1993; Tsitsiklis, 1994; Littman & Szepesvári, 1996) implicitly or explicitly rely on the use of count-based learning rates, where the O₁ in (tabular Q-learning) is re- placed by Ap.))....)) Here v(s, a, t) counts the number of visits to the state action pair (s, a) until time t. The count- based learning rate allows them to work with a wide range of behavior policies. Convergence rates are also later on established by Szepesvári (1997); Even-Dar et al. (2003). However, to our knowledge, such count based learning rate is rarely used by practitioners. Recent works (Chen et al., 2021; Li et al., 2024; Zhang & Xie, 2024) are able to re- move the count based lcarning rate. They, however, need to assume that a fixed behaivor policy is used. By contrast, practitioners usually prefer an e-greedy policy. In this work, we use an e-softmax policy to approximate the e-greedy policy and establish the L convergence rate, without using count based learning rate.
Meyn (2024) is the closest to this work in terms of the results. However, the underlying techniques are dramatically different. Meyn (2024) uses the ODE based analysis that connects the iterates with the trajectories of certain ODEs (Benveniste et al., 1990; Kushner & Yin, 2003; Borkar, 2009; Borkar et al., 2025; Liu et al., 2025). This work relies on bounding the norm of the iterates recursively (Zou et al., 2019; Chen et al., 2021; Zhang et al., 2022).
Previously, Zhang et al. (2023a) demonstrate convergence rates of linear SARSA (Rummery & Niranjan, 1994) to a bounded set. Our analysis is also largely inspired by Zhang et al. (2023a). However, our analysis is more challenging in two aspects. First, Zhang et al. (2023a) use projection to ensure the weights are bounded while we do not. Sec- ond, linear SARSA is an on-policy algorithm, but linear Q-leaming is an off-policy algorithm.
The key technical challenge of this work lies in the time- inhomogeneous nature of the Markovian noise. Previously, this is often tackled in two-timescale framework, where the transition function of the Markovian noise is controlled by
5

---

Convergence Rates of Lincar Q-Lcarning
secondary weight, say (0e), and Og evolves much slower than Wy (Konda & Tsitsiklis, 1999; Wu et al., 2020; Zhang et al., 2020; 2022). This is recently improved by Olshevsky & Gharesifard (2023); Chen & Zhao (2023) to allow 8e and Wy to evolve in the same timescale. Our analysis is more challenging in that we actually have 02 = Wi. This setting also previously considered in Zou et al. (2019); Zhang al. (2023a) but they all rely on projection operator. By contrast, our (SA) does not have any projection.
chain (Yr akin to Zou et al. (2019). The chain {Y. is constructed be identical to (Y) up to time step To.. after which it evolves independently according to the fixed transition matrix F By contrast, {Y}} continues to evolve according to the changing transition matrix Pur-T.,' Pur-T., to, This choice of Ta, ensures that the discrepancy between the two chains is sufficiently small. We now further decompose T3 with this auxiliary chain as
(V (u Yo+1) h( (V rar HWW V(42) - 11 11(1otoa))
(10)
5. Proofs of the Main Results
5.1. Proof of Theorem 3
Tai
Proof. We start by recalling that we use ||-|| to denote an arbitrary norm where I1-112 is smooth. In particular, 11l-11 is smooth w.r.t. |1-I1 for some I.. In (1), identifying f(wr as L(w),, w/ as w4-1, and w as we yields
+ (1 Y(-1) H (Wi-rai Y(+1))
Taa
L(w++1) (ww) + a (VL(w)), H(w, Y(+1))
We now bound the terms one by one.
Lei
2 [( 1+11
Lemma 1. There exists a constant C₁ such that
((w)) + at a (V)(w),, h(w)))
Ti S Cja (I(w)) + 1)-
a, (W,)), H (w,, Y2+1) h(w)))
Lei [[ 1+11
The proof is in Section B.1.
(6)
Lemma 2. There exists a constant C2 such that
We now proceed to bounding the noise term including H (w,, Y++1) h(w,). To this end, we notice that according to Lemma 1 of Zhang et al. (2022), Assumption AI implies that the Markov chains in Ap mix both geometrically and uniformly. In other words, there exist constants Co > 0 and E (0, 1), such that
T2 S - + 1).
The proof is in Section B.2.
Lemma 3. There exists a constant C's such that
supwr. Ey (P((,''') -y, dy,, S C
B[Tai] < (,L,(B( + 1).
We then define
The proof is in Section B.3.
To min 2 0 COT S [
(8)
Lemma 4. There exists a constant C4 such that
to denote the number of steps that the Markov chain needs to mix to an accuracy a. This allows us to decompose the noise term as
B[Ta2] s Cath -- In(1 + to + 1)(B[L(wx)) + 1).
The proof is in Section B.4.
(VL(wr) H (Wi, 1 h((w)) = (VL(w)) - VL(Wi- H(w,, Y(41)= h(w)))
(9)
Remark 1. We prove Lemma 4 considering Assumption A3 or A3' in two cases. Under Assumption A3', our proof is similar to those in Zou et al. (2019); Zhang et al. (2022). The technical novelty here lies the proof under Assump- tion A3. The proof under Assumption A3 involves bounding the term Pa. Pw.-o,ll ||- In Zou al. (2019), a sim- ilar term is bounded by | wz-az via the standard Lipschitz continuity of P., (cf. Assumption A3'). Zou et al. (2019) further rely on a projection operator to bound |w;, - w,-ov ll directly. However, (SA) does not have such a projection operator. In Zhang et al. (2022), a similar term is bounded under the assumption that the transition
(V ) (ww, Yo+1) - H HWWi-To Y(41)
+ +h(wi-rO,) h(w:))
T/
+ (VL(Wi-To))) ), H (wi (1a Y(+1) - h h(We-ro.))
T3
Both Ti and T3 can be bounded with Lipschitz conti- nuity. To bound Ta, we introduce an auxiliary Markov
6

---

Convergence Rates of Lincar Q-Lcarning
matrix is controlled by another of weights {0t}, which involve much slower than {ur.). Their bound is made pos- sible essentially because of this two-timescale setup. How- ever, (SA) only has a single timescale where the transition matrix evolves as fast as }me) We instead use a stronger form of Lipschitz continuity in Assumption A3.
The proof is in Section C.I, where the adaptive temperature No plays key role. For the second half of Assumption A3, we use dn. E [RIS|AA| to denote the stationary state-action distribution induced by the policy pw- Then it is easy to see that to o, 8') = dy (8, (1))p(((1s)) a). Then it can be computed that
Assembling the bounds in the above lemmas to (9) and further to (6), complete the proof of Theorem 3. The detailed steps are presented in Section B.5.
h(w) = Byrdy, i [H ([W = A(w) + b(w), (12)
where
A(w) = X (7Pro 1)x, b(w) = XTDpu!!
(13)
In the following sections, we first map the general up- date (SA) to (linear Q-learning) and (tabular Q-learning) by defining Hww, y). h(w), l(w), and the norm |I-I] prop- erly. We then bound the remaining term (VL(w)) h(w,)) in Theorem 3 separately to complete the proof.
(14)
Here, we use X E |I to denote the feature matrix, the (s, a)-indexed row of which is x(s, a) We use prw.. R|S|LAI((S|IA] to denote diagonal matrix whose diagonal is dr We use Tar to denote the greedy policy, i.e.
5.2. Proof of Theorem 1
Proof. We first rewrite (linear Q-learning) in the form of (SA). To this end, we define Y2+1= (St, Ar, St+1), which evolves in finite space
{
if a = arg max 2(8, b)
Th (a)s)))
otherwise
y = {(s E E, A, ES) (p(((ss)) 0}.
where tie-breaking in arg max can be done through any fixed and deterministic prodecure. We recall that PT... E [|S|[AA||(S||A denotes the state-action transition matrix of the policy Tw- We then have
We further define
Hf (w., y)
(11)
(r( + max. a(5' (6),,'')T =(s,a) w) a(s,a)]w)x(s.d)) a).
Lemma 6. There exists a constant Co such that
where we have used y = (s, s'). We now proceed to
[1((1)) - h(w2))l2 S Collwi - w2lll2 Vwi, W2.
verify the assumptions of Theorem 3. We identify the norm
used in Theorem 3 as the lg norm I|- For Assumption AI, we define Pwe as
The proof is Section C.2. Assumption A3 is then verified.
Remark 2. To prove the above lemma, we need bound term involving Dam. D pe Ilg |/ l|a- for which we rely on the factor 1/([|w1 + ||w> + 1) in Lemma 5 to cancel the multiplicative term ||w1]|g- Notably, as discussed at the end of Section 2, an <-greedy policy, due to its discontinu- ities w.r.t. w, will invalidate Lemma and consequently prevent the establishment of Lemma 6. Furthermore, despite that nu is not continuous, Px.. Pt.,Xw Xw Lipschitz continuous, thanks to the adaptive temperature Rw-
Pw ao, s6), (s1,a), a1, 5i]] pp (a (8) (s))p(((ss) a (
where I is the indicator funciton. Then it easy to see that
Pr(Ye+ilV)) =m,, =,, (A.))))))((((411111 Ax) =Pu. -P St), (S,, A, S(1) =Pu Yr, Y1+1..
Thanks Assumption 3.1 and the fact 0 in (3), it is easy to see that for any P E Λp, P induces irreducible and aperiodic chain in V) Assumption A1 is then verified. Assumption A2 trivially holds according to the definition of H (w, y) in (11) since max is Lipschitz and y is finite.
We now identify Wiet 0 and thus have L(w) 21/w|12 Invoking Theorem then yields
([[(()+1) <(1 + +[())E(T(w:)) + (V) f(t)-
(15)
For Assumption A3, the first half is trivially implied by the following lemma.
Since VL(w)) = w., we now bound the inner product term of the RHS with the following lemma.
Lemma 5. There exists constant C3s such that
Lemma 7. There exist constants 3 > and C7 > 0 such that
Maw (als) Mayg (a|s)] <
Csllw Vwi, W2, 8, a.
welll wall,
(w, hww) S -B1lu]12 + C>1lurl12 Vw.
7

---

Convergence Rates of Lincar Q-Lcarning
The proof in Section C.3, which is an extension of Lemma A.9 of Meyn (2024). Notably, this lemma is the place where we require sufficiently large and sufficiently small in (3), Plugging the bound in Lemma 7 back to (15) yields
The pseudo contraction property motivates to identify the ||-|| in Theorem 3 as Il-Ilss Unfortunately, Il- is not smooth. We then follow Chen al. (2021) and use the Moreau envelope of ||-11 defined as
B[L(w++1)] S (1 - Bo, + [())) + O(az).
M(4) = inf
{1 {2llu]l + 24 1g
Since f(t) is dominated by ae, it can be seen that [[(( remains bounded as t - oo. By telescoping the above inequality, we can also obtain an explicit convergence rate of IE (w)) to a bounded set. All those details are in Sec- tion C.4, which completes the proof.
where 0 a constant to be tuned. Due to the equiva- lence between norms, there exist positive constants 4 and Wit such that la 1u114/12- S |/ S uaa l111222 The properties of (g) are summarized below.
Lemma 9. (Proposition A.I and Section A.2 of Chen et al. (2021))
5.3. Proof of Theorem 2
Proof. It is obvious that (tabular Q-learning) is a special case of (linear Q-learning) with X identified as the identity matrix I. Most of the proofs here are similar Section 5.3.
(i). (qq is 2 -smooth w.r.. 11-112-
(ä). There exists norm I1-Il such that M (g) = 2 =41l
We, therefore, focus on the different part.
(ii)) Define lim = /(1 (1 + sli). tim = / Eug,). then
Assumption Al can be similarly verified with
limllull.. S |101 S ummllyllm.
Pgl(so- ao s6), ($1, 01, Lay(ails [1), (
01, s()]
(iv). (VM(g). l') S || ll''llm
(VM g) 2 ||
where By is defined in (2). For the other assumptions, by using X = in (12), we obtain
We then identify the norm ||-I| in Theorem 3 as II-IIm and further identify Whet as qa. As a result, we have realized L(w) as
h(g) = = (TPr, - 1)g + DUsT = p2 (Tq 10--) -)) =T'q 1--- 4,
M(g) = b11 2. M(a - 9-).
(16)
Assumption A2 again trivially holds. We now proceed to verify Assumption A3'. The boundedness of (4: } can be easily obtained via induction (ef. Gosavi (2006)).
where we have defined the operator T' as
T'q = D' (Tg q) +
Lemma 10. For any there exists a constant Cjo such that sup, [|gell S C.o a.s.
Here call T' the weighted Bellman optimality operator. The operator T' is highly nonlinear since D,,, depends on the stationary distribution of the chain induced by the policy Hg. This operator T' is unlikely to be a contraction. The key insight that we rely on here that T' still a pseudo- contraction w.r.t. the infinity norm Illloo.
The proof Section D.2. The Lipschitz continuity of P follows directly from the Lipschitz continuity of jy in (2), which is direct result from the fact that the softmax func- tion is Lipschitz continuous. The Lipschitz continuity of h(q) on a compact set is also simpler to prove than Lemma 6.
Lemma 8. Let Assumption 3.1 hold. For any e >> O, the weighted Bellman operator T is a ggeudo-contraction and q. is the unique fixed point. In other words, for any g, it holds that
There exists a constant Cn such that for any Q1, 92 satisfying max Ell Il ll Cio. it holds that
Lemma 11.
[1((1)) - h(g2)ll,, & Cnll4 -22lm--
IT'g 80l120 S &Bmll4 - lolooc
The proof is in Section D.3. Assumption A3' is now verified. Invoking Theorem 3 then yields
where 3m = 1 -1- dn (s, 1).
[[L(g(+1)
(17)
The proof is in Section D.
f())- The cecudo-contraction property of T' allows us to bound the inner product in the RHS as below.
<(1 + +a
This lemma is, to our knowledge, the first time that this pseudo contraction property is identified. The inf strictly greater than 0 because >
Remark 3.
8

---

Convergence Rates of Lincar Q-Lcarning
Lemma 12. There exists a positive constant C12 such that
7. Conclusion
This paper establishes novel L convergence rates for both linear and tabular Q-learning A key novelty of the result that allow the behavior policy to depend on the current action value estimation, without making any algorithmic modification or strong assumptions. Technically, such a behavior policy is hard to analyze because it brings in time- inhomogeneous Markovian noise, for which we provide Theorem as a general tool. A possible future work is to characterize Q-learning with such a behavior policy from other aspects, e.g., almost sure convergence rates, high prob- ability concentration, and L" convergence rates, following recent works like Chen al. (2025); Qian et al. (2024).
(VL(q)) < -C12Liq) vt.
The proof is in Section D.4. Plugging the bound in Lemma 12 back to (17), we get
[[L((++1) <(1 C2a + [())) + f(1).
Since f(t) dominated by at, telescoping the above in- equality then generates the desired convergence rate. The detailed steps are in Section D.5, which completes the proof.
n
Impact Statement
6. Experiments
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We test unmodified linear Q-learning (without target net- works, experience replay, weight projection, regulariza- tion) on Baird's 's counterexample, challenging benchmark for temporal difference methods, especially Q-learning (See Chapter 11 of Sutton & Barto (2018)). For clearer experi- mental results, we use a constant learning rate a 0.1, we also select Ko = 100 and e 0.1.
A Acknowledgments and Disclosure of Funding
This work is supported in part by the US National Science Foundation under grants III-2128019 and SLES-2331900
In Baird's counterexample, we have seven states, two ac- tions, zero reward r(s, a) 0 for all state-action pairs, and discount factor 7 0.99. The environment uses specific feature representation and all transitions lead to state 7 with probability 1, regardless of action.
References
Baird, L. C. Residual algorithms: Reinforcement learn- ing with function approximation. In Proceedings of the International Conference Machine Learning, 1995.
0.035
Average
0.330
Max
Min
Beck, A. First-order methods in optimization. SIAM, 2017.
0.325
Bellman, R. A Markovian decision process. Journal of mathematics and mechanics, 1957.
|
0.020
0.015
Benveniste, A., Métivier, M., and Priouret, P. Adaptive Algorithms and Stochastic Approximations. Springer, 1990.
0.010
0.005
0.000
200
Borkar, V. Stochastic approximation: a dynamical systems viewpoint. Springer, 2009.
Stop
Borkar, V., Chen, S., Devraj, A., Kontoyiannis, I., and Meyn, S. The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning. The Annals of Applied Probability, 2025.
Figure 1. Convergence of (linear Q-learning) with y = 0.99, 0.1. The graph shows the evolution 3 over time steps, demonstrating stable convergence behavior. The blue line rep- resents the average of the squared L norm of weights over 10 independent runs, and the shaded area indicates the range between minimum and maximum values.
Cai, Q., Yang, Z., Lee. D., and Wang, Z. Neural Temporal Difference and Learning provably converge to global optima. Mathematics of Operations Research, 2023.
Figure 1 shows the evolution of ||w:|| over 1500 itera- tions. We observed that the weights of unmodified linear Q-learning remain stably bounded throughout training, sup- porting our theoretical findings. Appendix provides com- parisons with versions incorporating other modifications.
Carvalho, D.,, Melo, F. S., and Santos, P. A new convergent variant of Q-learning with linear function approximation. Advances in Neural Information Processing Systems, 2020.

---

Convergence Rates of Lincar Q-Lcarning
Chen, X. and Zhao, L. Finite-time analysis of single- timescale actor-critic. In Advances in Neural Information Processing Systems, 2023.
Konda, V. R. Actor-Critic Algorithms. PhD thesis, Mas-
sachusetts Institute of Technology, 2002.
Konda, V. R. and Tsitsiklis, J. N. Actor-critic algorithms. In Advances in Neural Information Processing Systems, 1999.
Chen, Z.,, Maguluri, S. T., Shakkottai, S., and Shanmugam, K. A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-Icarning variants. ArXiv Preprint, 2021.
Kushner, H. and Yin, G. G. Stochastic approximation and recursive algorithms and applications. Springer Science & Business Media, 2003.
Chen, Z., Zhang, S., Doan, T. T., Maguluri, S. T., and Clarke, J.PP. Performance of Q-learning with linear func- tion approximation: Stability and finite time analysis. Automatica, 2022.
Lee, D. and He, N. A unified switching system perspec- tive and convergence analysis of Q-Learning algorithms. In Advances in Neural Information Processing Systems. 2020.
Chen, Z., Clarke, J. P., and Maguluri, S. T. Target network and truncation overcome the deadly triad Q-Learning. SIAM Journal on Mathematics of Data Science, 2023.
Li, G., Cai, C., Chen, Y., Wei, Y., and Chi, Y. Is Q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 2024.
Chen, Z.,, Maguluri, S. T., and Zubeldia, M. Concentration of contractive stochastic approximation: Additive and multiplicative noise. The Annals of Applied Probability, 2025.
Lin, L. J. Self-improving reactive agents based on reinforce- ment learning, planning and teaching. Machine Learning. 1992.
Devraj, A. M. and Meyn, S. P. Q-learning with uniformly bounded variance. IEEE Transactions on Automatic Control, 2022.
Littman, M. L. and Szepesvári, C. A generalized reinforcement-leamiin model: Convergence and applica- tions. Proceedings the International Conference on Machine Learning, 1996.
Even-Dar, E., Mansour, Y., and Bartlett, P. Learning rates for Q-learnigg Journal of Machine Learning Research, 2003.
Liu, S., Chen, S., and Zhang, S. The ODE method for stochastic approximation and reinforcement learning with markovian noise. Journal of Machine Learning Research, 2025.
Fan, J., Wang, Z., Xie, Y., and Yang, Z. A theoreti- cal analysis of deep Q-Learning In Proceedings of the Annual Conference on Learning for Dynamics and Control, 2020.
Marbach, P. and Tsitsiklis, J. N. Simulation-base optimiza- tion of markov reward processes. IEEE Transactions on Automatic Control, 2001.
Gopalan, A. and Thoppe, G. Approximate Q-learning and SARSA(0) under the c-greedy policy: a differential inclu- sion analysis. ArXiv Preprint, 2022.
Melo, S., Meyn, S. P., and Ribeiro, M. An analysis of reinforcement learning with function approximation. In Proceedings of the International Conference on Machine Learning, 2008
Gosavi, A. Boundedness of iterates in Q-learning Systems & Control Letters, 2006.
Han-Dong, I. and Donghwan, I.. Regularized Q-learing. In Advances in Neural Information Processing Systems, 2024.
Meyn, S. The projected bellman equation in reinforce- ment learning. IEEE Transactions on Automatic Control, 2024.
Jaakkola, T., Jordan, M., and Singh, Convergence of stochastic iterative dynamic programming algorithms. In Advances in Neural Information Processing Systems, 1993.
Mnih, V., Kavukeuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M. A., Fid- jeland, A., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. Human-level control through deep reinforcement learning. Nature, 2015.
Kane, D., Liu, S., Lovett, S., Mahajan, G., Szepesvári, C. and Weisz, G. Exponential hardness of reinforce- ment learning with linear function approximation. In Proceedings of the Annual Conference on Learning Theory, 2023.
Olshevsky, A. and Gharesifard, B. A small gain analysis of single timescale actor critic. SIAM Journal on Control and Optimization, 2023.
10

---

Convergence Rates of Lincar Q-Lcarning
Qian, X., Xie, Z., Liu, X., and Zhang, S. Almost sure convergence rates and concentration of stochastic approx- imation and reinforcement learning with markovian noise. ArXiv Preprint, 2024.
Zhang, Y. and Xie, Q. Constant stepsize Q-learning: Dis- tributional convergence, bias and extrapolation. ArXiv Preprint, 2024.
Zou, S., Xu, T., and Liang, Y. Finite-sample analysis for SARSA with linear function approximation. In Advances in Neural Information Processing Systems, 2019.
Rummery, G. A. and Niranjan, M. On-line Q-learning using connectionist systems. University of Cambridge, Depart- ment of Engineering Cambridge, UK, 1994.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction (2nd Edition). MIT press, 2018.
Szepesvári, C. The asymptotic convergence-raie of Q- learning. In Advances in Neural Information Processing Systems, 1997.
Tsitsiklis, J. N. Asynchronous stochastic approximation and Q-learning. Machine learning, 1994.
Watkins, J. and Dayan, Q-learning. Machine Learning, 1992.
Watkins, J. C. H. Learning from delayed rewards. PhD thesis, King's College, Cambridge, 1989.
Wu, Y., Zhang, W., Xu, P., and Gu, A finite-time analysis of two time-scale actor-critic methods. In Advances in Neural Information Processing Systems, 2020.
Xu, P. and Gu, Q. A finite-time analysis of Q-Learning with neural network function approximation. In Proceedings of the International Conference on Machine Learning, 2020.
Zhang, S., Liu, B., Yao, H., and Whiteson, S. Provably con- vergent two-timescale off-policy actor-critic with func- tion approximation. Proceedings the International Conference on Machine Learning, 2020.
Zhang, S., Yao, H., and Whiteson, triad with target network. In Proceedings of the International Conference on Machine Learning, 2021.
S. Breaking the deadly
Zhang, S., Tachet, R., and Laroche, Global optimality and finite sample analysis of softmax off off-policy actor critic under state distribution mismatch. Journal of Machine Learning Research, 2022.
Zhang, S.,
Des Combes, R. T., and Laroche, R. On the con- vergence of SARSA with linear function approximation. In Proceedings of International Conference on Machine Learning, 2023a.
Zhang, S., Li, H., Wang, M., Liu, M., Chen, P.-Y,, Lu, S., Liu, S., Murugesan, K., and Chaudhury, S. On the convergence and sample complexity analysis of deep q-networks with e-greedy exploration. Advances in Neural Information Processing Systems, 2023b.

---

Convergence Rates of Lincar Q-Lcarning
A. Auxiliary Lemmas and Notations
Lemma 13 (Definition 5.1 and Lemma 5.7 of Beck (2017)). The following statements about a differentiable function f() are equivalent:
(1) f(x) L-smooth w.e. a norm ||-||-
(i)) [VV(() - vs(w))l. _ - yyl-
- f(x) (V/()))))))))))))))))))))))))))) x)1 S 1 y/l.. (ii) (
Lemma 14 (Discrete Gronwall Incquality, Lemma 8 in Section 11.2 of Borkar (2009)). For non-negative real sequences {Z n 2 0} and {an; n 0} and scalar 0, it holds
En+1 SC SC+LE 0:
Vn = In+1 (C 2a)
0:) Vn.
Lemma 15 (Lemma 9 of Zhang al. (2021)). Let U be a of policies and Ap = {Pp E RISILAIXISIIII p E U} be the set of induced state action transition matrices. Let Åp be the closure of Ap. Assume for each P E Åp. the chain S x A induced by P is irreducible and aperiodic. Let dp, be the stationary distribution of the chain induced by Pv. Then dp, is Lipschitz continuous in μt on U.
Recall the definition of A(w) in (13). We have
Lemma 16 (Lemma A.9 of Meyn (2024)). There exists positive constant Kn such that for Kn > Ko and < (1 7)² - 7) + 72), there exists positive constant B > O such that w A(w)w S -Bllwll holds for all ||ll|2 2 1. To be more specific,
pru X) x) e)) 1og((A))
B = (11 (1-
Amin AX D
V Ammx (XT RTDDpa X)
Kg
where Amin() (-) and )max(-) denote the minimal and maximal eigenvalue of the matrix, respectively.
We define shorthand
03
C2 max (1)
C || Cee
||
s,a
We F, = (wo, Vi, -,.... Yi) denote the filtration representing the history up time step t. Recall the definition of To in (8). We have
Lemma 17 (Lemma 11 of Zhang et al. (2022)). For sufficiently large to. it holds that
Toy = Olog(( + to)), 01-1 = o log(t + to)
(1 10)
Lemma 17 ensures that there exists some i > 0 (depending on (o) such that for all t > L, it holds that / 2 Tay Throughout the appendix, we always assume is sufficiently large and t 2 f. We will refine (i.c., increase) f along the proof when necessary.
B. Proofs in Section 5.1
Lemma 18. There exists constant C18 such that for any w. 4,
(w, y)ll <Ci([1 + 1), [[((w))] < <C1s([1wd + 1).
Proof. Recall Assumption A2, we have
H (w, 9) - HO, v)ll S Cx2lluel Vu,.
12

---

Convergence Rates of Lincar Q-Lcarning
According to the triangle inequality, obtain
(w, v)ll & [[ v) (O, v)ll + (0,
Therefore, we can further obtain
(w, (w, v)ll Ca2llool (0 y>1l-
Thus, choosing CIS.1 = maxy {Cx2, HO, y)) completes the proof for bounding (we, ((w,,)) Similar result can be obtained for h(w) under Assumption A3 by choosing C18.2 max {CA3, h(()) and under Assumption A3' by choosing C18,2 max {CAs', h()).. Therefore, we can choose Ci8 = max (C18,1, C18,2)-
Lemma 19. For sufficiently large to, there exists a constant C19 such that the following statement holds. For any t 2 and any E [t - Ta t) holds that
wuy We-ra. d-- -2-1 + 1), [w Wt-Ta, S C19as- +- (1lws wolll + 1), [ || S Cio(1lur - Wrrll + 1).
(18)
(19)
(20)
Proof. In this proof, to simplify notations, we define shorthand t t - To. Given Lemma 17, we can select a sufficiently large to such that for any t f.
Sxp(Ci80t-5aa 1-1 <3,
C180t- <
6
We then bound |ur Wey || as
|w; why 11
Hmw, Y++1)ll
ag CxCis(1lux - wi, ll + ||w, |l + 1)
aCCis((lur, || 1) Σ
Os Cis(Ilux w/, I))
k=h
< C C (1 + 1) exp(Cisar,
(Lemma 14)
We then have
||l; wx, Ci800, (1 wr,ll ||w:|| + 1) exp(Cisare,
1
2 [: Wh, 11 C19220, + 1),
where we have defined C 3Css- Thus, we have
||u wo, ll S 2019,20r,;-1((::: 1),
which gives proof of (18). Furthermore, we obtain (19) as
|w; Wr, || < 20 i- [| 1)
< 2019,2a1, wherll [|weell + 1)
s C19,00 (1|w; Wrell + 1).
For (20), taking i = in the above incquality yields
||w
|| S I|w. - we, S -4 1 Wrelll + 1).
13

---

Convergence Rates of Lincar Q-Lcarning
That is
||m, |l S -- - Wherl + 1) + l/ue - Wrell + ||wselll 2 ( wrerll + 1) + 1lws Werll + ||wselll
which completes the proof.
B.1. Proof Lemma
Proof. According to (9),
Ti (VL(w) - VL(W)-7.,
H(r, Y(+1) h(wwr)
V((w)) VL(Wi-r,,)Il. Ill. | Y(+1) h(w))ll-
For the first term,
[L(m)) - VL(w:-Tul )l
(By (5) and Lemma 13) LCi9as -- w 1) (Lemma 19).
2|1200 w¹ woeroll ||
For the second term,
[Wwe, Y++1 - hww))]l s Cis(I|uall + 1) Cis([lucel 1) 201s(I]wr - whrll + Cref + 1).
Combining the two inequalities yields
(VL(w,)) VL(W:-r.,) (w,, Y++1) - h(ww))
LC LC Wrell Ciet 1) 201s(1 weall + Cret 1)
C1110t-an whrll + 1)²
201,10% 1 (1/w+= wrerl + 1).
Choosing C = 4Ci,1 then completes the proof.
B.2. Proof of Lemma
Proof. According (9),
T2 = -(VI(ww H(m, Y441 H (WW-Faa Ye41) + h(W) h((e)))
Ill. [wrr Y++1) H (Wi-ray Yet1) + h(Wrrraa)) h(wr)l]-
For the first term, it is trivial to see (((wer) O. We can then obtain
V VL(Wi- L(We-rr. )l1
V L (w' (Wi ) L(Wart)) Il.
T. Wi-Tas Wicrll (Lemma 13)
<L We will + +ll werll)
Recall for f sufficiently large, we have C190t- 1. Applying Lemma then yields
VL(Wi )l. <L [[][w well + ||w, warll) <L( we Wherll + ||w waell)
<L(2||w: wherll 1).
(21)
14

---

Convergence Rates of Lincar Q-Lcarning
For the second term,
(Wr, Y++1) ((u- Y+41) h(we-ro,) h(we)l
5(CA2 + max {Cas, CAS' }) 21 - wr|
(CA + max (CA3, CAs' }) 1-1 [|/ + 1) (Lemma 19)
<C1o(CA2 + max (CA3, CAs (11 1-1 [m - Whelll + Cjet + 1).
Combining the two inequalities together yields
(VL(wr-F..)) (w,, Y++1) TW Y(+1) + h(We- M(wwe) [( We - Well + 1) C19(CA2 + max (CA3, CAs - whelll + Cre + 1)
52 0k t-1 (1/wr
Weell + 1)2.
Choosing C2 402,1 then completes the proof.
B.3. Proof of Lemma 3
Proof. For the first component of T3 in (10), we have
E Tsi Fo-ro
= E V L (wi H(u Yot1) - h(wr-ra)) )) [FL-Ta))
Vi(wi- Tun )R H( Vet1) - h(Wi- Fap }FFe 1)
VL(we-Ta )l. [V (Wr 8et1) - NWW2-Ta, -W
|
The first term is bounded in (21). For the second term, we have
E H(w Y1t1) - h(we-Tm.)) }| |
([WW)-T,))))P = :1(F Σ H (wi- Top 3) 3)dy. (v)
Σ H(we-Fa, (P)(() y)Fi-ra)) - dy.m sot (v))
(Wr- w)|l 2ill
p(Y++1 = y)Fo-ram) - dy dy. (w)l
8
$ max H(W:-To 8) Σ p(ye+1 y)Fe-ra,) dy.wo-rar (2)
So,Cis<[[ut-aal 11 (By (7), (8) and Lemma 18)
Sa,Cis([|ur-aa Wi will + ||we Weerll + Cret + 1).
Combining the two bounds yields
E (WW H (Wi V441) ( F)
(LCiaa((2luur - Whelll Crer + (19)(Ci) -- (11 well + 1) + ||,,- - Whelll + Cee + 1)
(Lemma 19)
<LCisCigar((lus worill Cief C19 + C2,1)² <LCisCiga 2 + C3
Choosing C3 = 1.Ci8C19C3,2 then completes the proof.
15

---

Convergence Rates of Lincar Q-Lcarning
B.4. Proof of Lemma 4
We start with an auxiliary result.
Lemma 20. Then there exist a constant C20 such that
E Hur Y(+1)= (W Ye+1) Fi-tar] S C200 it In(t + to + 1)(lerx - Wrerl + 1).
Proof. In this proof, all Pr are probabilities implicitly conditioned on Fi- For simplicity, we define P. = Pan.
Pr(Y = y')= = Σ - =y} y)= :0= P/ = =y), Pr(Y;= = v/) = -Epre [p((V-1 = v) Pr Pr- (v.2)).
Pr Yc-1
Consequently,
Σ Pr(Y, = v) -Pr))-Prr5- v\) s Σ
- Pr Pr(fi-1 v)) P. (v.0
2/91"
We now consider two cases.
Case 1. Under Assumption A3
Pr(Yi-1= = y)) Pr (P
= =v) -) Po, (v.1))
< P = Pi 30) - p( = 1))((v.)))) w/|+ + -0 - -((8-1 = p) (,.0
||w:= W Wt ||
< Pr(Yi-1 y) Pr (Y1-1 = u) Pr(v. 1/) + Cas
Pr (T =v)
||well + ||
+
< Pr(Yi y) Pr (v-11 Pr(Vi-1
= u) P.(u.D/) + CAsCio
weel
+ 1)
Pr (Vo- = -)) v)
(Lemma 19)
|w/l
Wk
< Pr(Y = y) Pr (Y = /))PP)PP /((v.a/) + C2
where C - CAsC19.
Case 2. Under Assumption A3'
Pr(Y,-1 = y)Pr(y.))) v/) Pr (r-1 = P Pr-to, (v.33)
Pr((y-1 = Py.. Pr Vi-1 -y) Pr v') + Pr (r((%-11)) Pr(y. Pr(v 10== =n) Pt Pt-ru, (v.D0)
Pr(Yn-1 = y) - Pr (Y-- = v)
(P(l..5)) 5/) + Car Ww Wi Pr YY-1 = 21
< Pr(Yi-1 = y) - Pr Y = y
P((u,v) + C
+ 1) Pr (vr-1 =
(Lemma 19)
< Pr((Y-1 = 4) Pr Fr- v)
P.(u.v') + Ci --
1) Pr Yr-1 = y)
< Pr(Yo-1 y) - Pr Y = v) P((y. + -20,20(--,,
where C2. = CAS C19 A3' + 1).
Thus, denote C2a,3 = max (C20,1, ),0,2), we have
Σ Pr(Y = v¹) Pr Pr((v v/) $ Σ
P -) Pr(Pi-1- = =)] + (0t
y
16

---

Convergence Rates of Lincar Q-Lcarning
Applying the above inequality recursively yields
- - Σ - [y/=-/]
-Pr(Vi- =/)
- C20,3/D9
E
ai-Toed
jut-Tne
For the summation term, we have
Ej Taed
Toe Tae To-Tor
Tas at-Te O
In(t + +tg To- = O (In(t + to)).
at
a4
Then there exists constant C20,4 such that
Σ
at-
S 01- 1-1 C In(++ to),
J=b-Tai
Consequently,
E
: - H(wr-ra,
H w Wi-ro, v(+1)
H(Wi-Ta P') Pr (Fot1= 8/)
H H(wr-ro, 1/) Pr(Y++1 = = Σ y¹
1
Peppprrrpe (8et1 = =
H (Wrr-or Pr(Y++1 = 3/) H HW 11) Pr
V
< <C18[] Wy- We || + +1) Σ
Pr(Ye+1 = -²) Pr (F(Fet1 (f(Y1+=11) =
SC180t ( werl + 1) 1)020.3 (3/12,, In(1 t0 + 1).
Choosing Cz Cia(C19 + 1)C2,, | then completes the proof.
We are now ready to present the proof of Lemma 4.
Proof. For the second component of T3 in (10), we have
E 32 Fr F..ra.]
V VVL(w, [w (WW H HWW Y(+1) H ((W Pet1) [r
T Wi - Fu, ) H(W V441) H H(ut V Fi-taa))
(WW lll [[[((Wr-ra Y141) H (w (Wi Ye+1) (
From Lemma 20, we have
E HWI-To Y441) H H(u Ye+1) (aa))(FFra))) Fo-rar]
< -n + 1)(l Wherll 1).
Thus, there exists constant Ca such that
Ts2 < E VL(W 1l. H(W Y Hw Y(t1)
< L(2l|wr Wrerll + Cret + C200 In + tu + 1)(l whell + 1) (By (21))
20 In(l to + 1)( [[] Wherl Cref C19)²
< 04a - In(t + to + 1)[ w + 1).
This completes the proof.
17

---

Convergence Rates of Lincar Q-Lcarning
B.5. Proof of Theorem
Recall the decomposition (9), combining the bounds for Tí, T2, T3i and T32 from the above lemmas, we have:
( (wr, Y(+1) - Fi
(BL +1 C2ar -T (( (
11 In([ 1) ((x c- -ap +1)
+1).
+ C +3 is constant. Recall (6) and combine all the results, we have
where D3 =
E ([
[B(L(w))| F
La 2
+ ta, Hw:. Y(+1) ((x))))))))))))))))))))
E
[H Y++1)11
2
La
+ 1) +
C (1 + |100 - uwerlll
2
+ +aDD3au-oo To. In +6
1)
+ 1) 2 (B 1).
Denoting S(1) = Dranas --1 In(1 + 60 + 2Lo
o(
(o+ and taking the total expectation then (1+t,)<r
completes the proof of Theorem 3.
C. Proofs in Section 5.2
C.1. Proof of Lemma 5
Proof. Since softmax is Lipschitz continuous, only need to bound [Kw, I(s a) w1 Kw, a) Twy/.
Case 1: |lills 2l2 < 1 and ||wa||2 < 1. In this case, Nww = Kwz feg. Define C2 = sups,a ar(ss,))ls Then we have
Nun x(s, a)
Twi W1
Konny 2(5, a) Tw2l
SNO Cx -w2ll2
3R
|ml| wella-
+ ||11l2 || ll
Case 2: || 2 and
||22||22 2 1. Without loss of generality, let ||w>||
2 || |2//|- In this case, Kin
1w1 11
Kwzg
Ko
Then we have
|| llz
|| llz
|| w22ll
Mar
Ko
S
|| |/
w22 122l
|wo 2 ww2 l1
Therefore,
Kmn, x(5, a) Two, w1 - Kun, (s, a) TTozl
Kwn (888 a)" (wi w2))l1 + | a)TT)a Twp |mw Kwwz
| w2 1
Callwi w2ll2 + Cz C2||w2112
| l
|m W2
Grip ||w| well2
3||w1 ll2
Gro
|m wa lly
+ |/00 112 + ||
18

---

Convergence Rates of Lincar Q-Learning
Case 3: ||il|22 1 and ||w2l22 2 1, and vice versa. In this case, Kiw
Hig and Fiw2
walll2
S
Kig-
We obtain that
Miarg
K0
1
1212 12
Similarly, we have
Kwy 13, a) ".w w1 (s, (s,,))(s)) uo2l
Kwy ( a) (wi w2)1l2 + |r((s (s
w1 New, Rowa
CgC₂
[01 - W2l12 2 + Callwa1l22 112 1 ||22 ll2
|002|
KoC2
|w] - [01--wlls + Caro 1
Cg
CzAo (11w22l22 1)
|01 - se2-wulle +
|022|
| ll
3 311002| 2 ||w w22
| - w2ll2
||w 1l2 + |222
where (*) obtained because || ll2 < 1, and according to the triangle inequality ||w] - wz2l2 2 ||w2ll2 - 1|will2 22
||z2ll2 since ||w2ll2 2 This completes the proof.
C.2. Proof of Lemma 6
Proof. According to the definition in (13) and (14), we can apply the triangle inequality to get
[1((w)) h(w2))l2
= [[A(w))) + b(wi) A(w2)ws - b(w2)ll2
<||XT DMw, (T(Xw1)- Xw1) x DDHi,, (T(Ww)) Xx2))l2
<||x² T Dang (T(Xw1)- T(Xw2) - (Xwi Xw2)) || (D (Dass Du (T Xw2)ll2
The first term in the RHS can be bounded by ||w - wall easily because | ll2 and T is a contraction (and thus Lipschitz continuous w.r.t. any norm). For the second term in the RHS, according Lemma 15, Dp... is Lipschitz continuous on Mas that is
|| -D Mag ll2 S C6,1lluwn -Mwozla 22-
Here interpret pw as vector in RIS||A| It is easy to see that
(T(wa)) Xwall S C6.2 + Co.2|u2ll
for some C. Then Lemma 5 implies that for some C6.3, we have
(D Hmj D pm, (T(Xwz) - Xw2) 1
< X || 1o - Hww 11 (C,,2 + Co
1 1+ 122l
5C.. + || 11 + |1 112
||00 - W2ll2
<C6.allu - 22l122
which completes the proof.
19

---

Convergence Rates of Lincar Q-Lcarning
C.3. Proof of Lemma 7
Proof. From Lemma 16, we know that ||l|| 2 there exist positive constants 3, which satisfy
T A(w)w S -51
Therefore, for ||ll| 2 1, recall b(w) X D Puu 7, we have constant CT,1 A that ensures
(w, A(w)w + ((w) - -311 + C7,11100112-
For ||w||2 I 1, recall || can be bounded by another constant C7,2 = (z + 1), thus
(u,, A(w) b(w)) = (Ch,1 + G22)llol22 - - + (Ch,1 C2 + () Thus, for C = C7,1 C2 + 3 |8 + (IS1IAIC,) + 3, it always holds that (w;, A(w, + b(w,)) - - 11 C:wwdl
This completes the proof.
C.4. Proof of Theorem
Proof. Combining (15) and Lemma 7, we have
E[L(w++1)] <E[L(w;)] o, (w)) h(wx)))) (())1
B[L(w:)))
<E[[(w:)] + a [| C:E[I [12)) f()) +[((ww)))
=(1 280 [(0) + C,C [1 ((t)
2a C2
5(1 23a, + [ww)) + a.. //::l 112 +
+ f(t)
(using y /xy)
20²
<(1 3a, + [(:)][[(w))] + Di, (since f(1) 5
ar for sufficiently large
B
<11 (1,2a,)E(L(ur [[[[(w;)] + D1,
where D1,1 = C and 21,2 = 3/2 Unfolding the recursion from time to yields
1-1
t-1
[[L(w]] < II 20) + Dr.1
Σ
II
(1 D1,20)).
k=
k=
j=++1
Case 1: 6a = 1. We can derive that
t-1
[-1
II (1 11-i22as) S eexp
- D122
Σ
1=++1
j=k+1
1
< exp
- -
k+1 to dr
exp
(- (-Di,2a(In(t + In(k: 1 tt)))
k + 1 40
Di.2
t to
Substituting back, obtain
B[L(w:)] <
to +
D..a
B[L(w))] + D1.1
Σ
(k+1+to to
Di
t +tto to
k +to
+ to
km
20

---

Convergence Rates of Lincar Q-Lcarning
The second term becomes
k + +0
21,20
2
[-1 E
( + to) 0120011
k to
t to
(t to+ P1,20
k=t
k=d
Denote = D1,2a and S(1) = (E+ta]
Ex 10)
When c o 1:
Σ (ke (t) L" (x+
(1 1o)
1-1
1
(c+
1
S(1) -
(1 (0)
c
c
2. When c= 1:
ko t-č
S(() S to k=ł
< 1.
t to
Thus, we conclude that S(t S
_ that is Di.g
tu + Di,a9
E[L(wr)] -
E[L(w;)] + D1.12
t
D1,2a
D1.3
(t) Di.a B[L(w;)] + D1.4.
Furthermore, the last constant can be expanded as D1,1 S 3 2d the [[[(w))] term, since U is deterministic, starting from the update of Wr+1, we have
372 I (() (SS For
|| < well + arl H (w,, Y4+1)ll = || + o. a + 1).
That is, ||w++1|| S Ci + Cao + w)]lw/ll. Applying discrete Gronwall inequality, obtain
7-1 E1+ + (11+o (Cis + | exp(F Foo
||rT|| s (Cis + ||mll] exp
Furthermore, combining this with the current bound, denote B₁, D1,3 exp(2i(1 + aoCi))), B1,2 D1.2 and Bi = (1+ta) 2C18 exp + a0)))) + D1.s) then completes the proof of the first case.
2 Dis
Case 2: ta E 10.
(1- - D1,20r,) s exp
-D
Σ aj
k
j=k+1
1
< exp
D1.20
(xr (0) dr
k+1
D D1.20
[[t (1++ (1)
2-6
(k: (0) 1o)
exp
Ca
Di I-co
(k + 1 1-)
exp
exp
D1.20
(1 + 1n))-ec
21

---

Convergence Rates of Lincar Q-Lcarning
Substituting back, obtain
D1.20 ((f+tt))) to) B[L(w;)]
B|L(w)] S exp
-
1- Ea
1-1
(-Di,20 2
+ D1,1
a
exp
(11 caca ca
[ + (0) (0) +00))))
(k + to)er
k=
For the second term,
11 21,2a - t0) to)
(-
(k 10)
exp
1-
k=
D 21.20
(k: + 1 + 1o) 106=
exp
exp
Duza I-c,
(t + tb)
k=
(k + to)
1- ca
To make the notation cleaner, we define M
Da.a T-fa"
then
t+o
RHS
exp (M(k + 1)
exp
(M(L+ 10)
hta
k=1+1
4+6-11
2
exp (M + 1)1-
exp (M(L 10)
kk+ 1)
k=I+to
2
1+
x 'u exp (Mx dx.
exp (M + 10) 10)21-c))
Now we perform substitution simplify the integral, let u = Mx then du M - ( dx, thus
++o+1 x s0 exp (Ma--ca )dx = M(1 ca) JM
M(++4++1) "
exp exp (M(L + 60 + 1))--o0)
M(1 (a)
Finally, we have
D1,20
B[L(w:]] S exp
[(1 + (tt)
-F -(F+ to)) [oa+ [[[((w))
1- Ca
1-1
exp (-D1ga
D1.20 [(t+ - (k+ 1 to) t-a)
+ D1.1
(k + 10)co
Exx
k=
21,20
< exp
(t + to)
- - to) (0)(
E[[(wr)]
1 Co
a
exp (M( + (0) 1-Fa)
D1.1
exp (M (t + 10) 1-)o) M(1 - Ea)
11220
2 Di
exp
En
(1 + 10)
1-ca (T (o) (6w)
B[L(WE)] +
M(1 - (c)
D D1y0
2 21.1
[[t + to)
1- (f+ to) [rr)]
[[[(wE)] +
exp
1 Ea
D1.2
D 11,20
[t + to)
1-6a (f + to) t0)
B[[[wE)] + D1.5-
cxp
Ca
The last constant can be expanded as D1.5 200
2'ي ((())AAC.))(+ AAC.C,, Then Theorem I
g2
follows from using the Gronwall inequality to bound L(w;) with Woll and the equivalence of norms, with B1 B1.s, and Bis selected similarly.
22

---

Convergence Rates of Lincar Q-Lcarning
D. Proofs in Section 5.3
D.I. Proof Lemma
Proof. It is obvious that 9r is the unique fixed point because infq,e,a dny (5, a) > thanks to the fact that > 0. We also have
I q - 10
|[ Du, (9+ - q+) 10- loc
Pi, Tq Dpp + 1 9- D/o (4+ - am)
|D (Tq 9.) (I-IIppp 10,,) - q-)l1
max dn, (8, a -., a) + - - (o)
s.0
max n 8, - (1 dn (5, 1a)aall -
8,
max d, (s.a)//l9 80lloo + (1 - dup a),a) - 80
max(1 (1 - 7) 7d (8, k)) 90
8.0
1 (1 - 7) inf dny (8) 119 g-llo0
9,3,a
which completes the proof.
D.2. Proof of Lemma 10
Proof. Recalling the update rule for tabular Q-learning in (SA) and (11), we have
||a+tllbo s (1 - a: 11 + as(C, + xx) = =11 ar yag)l1 + arCr.
If q: ll., unbounded, then l1 also unbounded, that is for each constant M |0 we can find some time such that 1 lx < MM |1 Therefore,
M < (1 (1-ac or ) + a,Cr,
which is equivalent to
ar(1 a((1-)M < arC,.
Since C, is constant, will get contradiction for M
Ca -
This completes the proof.
D.3. Proof of Lemma 11
Proof. Recalling the definition of h(w) in (16), we have
[I((q)) - h(g2)ll>> = ||' qı - Q - (T' - 92)ll
|Dnn (Tq) - q1) - -Du,, (T (2) + DDa, (T42 (22) -Dua (T - -1)
Drn, (Tq) q1) Dpm (T -92)llo | pun (T 92) Dun (T92 92)
< (1 - Tqz) - ( - (2) 22 + 1 - Maz al T 92 92lboc
The first term the RHS can be bounded with ||q: - 42 ae easily. For the second term in the RHS, D D can be bounded with l|q] o2lloo thanks to Lemma 15. Noticing that T 92llas is bounded because d2 lies compact set then completes the proof.
D.4. Proof of Lemma 12
Proof. Recall that Bm (1 - 7) in a drg, as, we have
(VM(4 q.), h(()))
23

---

Convergence Rates of Lincar Q-Lcarning
(VM(u q.); T' 9t)
= =VV q.), T'q 9r 9- qt)
= =VVM (q: 4.), T'g. q.) - (V M (g: 9.), 9: 9-)
< <11e: 4- (ml arll|/'4 a: - qo qm - 11 - q. (Lemma 9)
1 IT q: q-
$ 9g q- Il
11 qa l
lim
1
S
qu m.
8m
q: 20
l1q:
q. ll
Lim
1
Uim
Pm
119c
Lim
Since 8m < 1, we can choose sufficiently small & (defined in Lemma 9) such that C12 = 1 the proof.
Mam
8m > 0, which completes
Lim
D.5. Proof of Theorem 2
Proof. Combining (17) and Lemma 12 yields
B[[(++1)
+ (.F() + f()(1 + B[T(a)))
- =(1-2C12a; + [()) + f(t)
In 2 + to)
<(1 D2, an E(I(( + D2.2
(1 + 200
Recall we have:
at (t + 10) a1--t-1= ( In(t + to)
(t. + k0
where Ea E (0.5, 1] and to 0 is chosen sufficiently large. Then for any 0.5 t'a < Eor for t large enough, the recursive inequality can be simplified to:
a²
B[L(++1)] < (1 D2, D2.10r) + D2.2 + t0)
Thus,
B[L(4:) <
(1 aas) [(LLun)) + D2,2 Σ
2
II j=k+1
(1 D2
(1 + 40 2
20)
k=
Therefore we have:
[-1
II (1 D210a) S exp
-D2,1
Σ
ag
1+++
j=
Case 1: 6a 1. With the step size 0t
a the sum be approximated by integral:
j+bo
aj 2 J
Σ
dx a(n(( + to) - In(k + + to)).
k+1 x +
j=++1
Thus, the product term becomes:
r-1
(k (k+1+1 1 to
Da.10
II j=
(1- D210;) S eeppp- (In(t + to) ln(k+1+ =
to
24

---

Convergence Rates of Lincar Q-Lcarning
Substituting back into the recursive inequality:
i + to + to
D
a²
h: ++ to
D1.
E[L(q)]
B[L(A)] + 22
(k tq)²
t + to
kmt
Now the summation term can be bounded by:
a
k 1
D
2+
2k
D2.10
2
1446-1
Σ
Σ
D
(k + to)2 k=1
+ to
to
(1 + (0) D2.1a
k=
k=tot
Define:
I+lo-1
s(t) =
Σ
k
D11a-2
k=l--
The behavior of S(t) depends on the value 22,10
1. When D2,10 < 1, then a -2 -1. The sum Stt) converges to a constant as + oo:
S(t) S D2.3-
Therefore,
S(taa((t 2 D2.3 (1 + 40) Pria
(1+ (0) Pr.ia
2. When D211 1, then D2,1a - -1. The sum S(t) behaves like the harmonic series:
s(t) < In(t + to 1).
Thus,
2an In(t + to 1+ 10 3. When D2,10 > 1, then D2,10 - -1. The sum S(t) grows polynomially:
2 S
1 to
S(t) S (t + (o)
Po.00- 1210-1
D21a-1
Therefore,
2PI.I
2D,10 (t+ to) Dt.a-
22.1
(t + to) Pana
(D2,1a 1)( + to) Da,1a
(D2,aa - +)
Substituting the bounded summation term back into the recursive inequality, obtain:
2tu
Da
[[L(g:) + )Pt.0n(())
B[L(go] <
++ to
( 1o) Di.
D2.1
D2.5
In(t In(t to)
<
([L(gg)]+
(22)
(I (1+10 (1+4)) Pain
(t to m (I,
For the B[L(g)) term, since 7 is deterministic, following the similar derivation above, we obtain
to
Dr,aa
a
k + 1 to
D
E[L(gr)] 5
E[L(go)] D2.2
[+ lg
(k: 10)2
1 la
k=0
25

---

Convergence Rates of Lincar Q-Lcarning
Similarly, the summation term be bounded by:
E-1
a²
++1+
D
2
i+to-1
Σ k=
k P210-2
(k +
to)3
t
(t + to)
D2,10
k=to
2
max(1
D:10-2
to to 1 1)
(1 lo)
Therefore, B[L(ge] (20)) + D2.7 Combining this with (22), denote B2,1 = D2,02200 B2 = D2,1 and B2,3 = 2,7 D2,5 then completes the proof of the first case.
Case 2: ca E (0.5, 1). With the step size aj (i+t)) the sum can be approximated by an integral:
Σ j=
aj 2 a
1 dr (r + to)
a [t (t) (k + 1 1 to)
k41
Thus, the product term becomes:
D2.10K [[t + to) - (k: + 1 to) toa)
II j=++1
(1-D2,19)) S exp
ta
Substituting back into the recursive inequality, we can get:
E[L(x)] exp
D2,10
(1+
exp
D2.10
1/ (1-c)) [[L(ge]
Ea
a
D2,1a 6a
D2.2
Σ
(k + to)
2d
exp
[[t (tt toe- (k+ + 1 to))
k=
Denote D2.6 = exp
(21101-ra
Now we bound the summation term. Since 2é', > 1, this term can be bounded by:
I-ca
a
D2,10
exp
(t)
(k: + t0)1-en)
kk + (0)
1-6a
-1
2
D2,10
[[t (t) 1-ro - (1c + + ttt
kk + to 24%
exp
1-
k=
a²
12110 I- [[| + (n) 1-6 (k: + 1 (0) 1-60
(k: 20 exp
1-++bá
51
2
exp
D2,10x
(f ( + (2++1++6))
(t (t+
a²
10
2%
1-
2
(k: + 2
k= [
a²
1-1
a²
<1
exp(
(o(-D227( + +10)2=00) +
dx.
2-
2
14151-1 (x + to 2e%
to
a
2
<1
exp( -D2,7(t + to) (ra)
(t (t))
22'
2- (g
2c
<D2,s(t to) 1-26.
Substituting the bounded summation term back into the recursive inequality, obtain:
D2.10 (1- ca
E[L(g))] < exp
(t to))-aa
D26E(L(ge)] + D2. + 1o)²
26

---

Convergence Rates of Lincar Q-Lcarning
D2.1a
I exp
(-1- (1 + to) D2aB - D2 + 10))
6a
Then Theorem 2 follows from using the Gronwall inequality to bound [(g) with llool and the equivalence of norms, with B2,,, B2,,, and B2,6 selected similarly.
E. Comparsion with other algorithms
We compare unmodified linear Q-learing algorithm with several variants that incorporate common modifications. All experiments are conducted in the Baird's counterexample environment with 10 independent runs algorithm. All algorithms use the same e-softmax behavior policy with adaptive temperature parameter Kg 10 and e 0.1 as described in our main paper.
We compare the following algorithms:
1. No Modification: The original linear Q-learning algorithm as analyzed in our theoretical results.
2. Target Network: A separate target network used for computing the TD error, with the target network updated every 10 timesteps.
3. Weight Projection: After each update, the weights are projected onto ball with radius 10, ensuring ||well2 S 10 at all times(Chen al., 2023).
4. Ridge Regularization: A ridge regularization term is added to the update rule with coefficient 77 = 0.01 et al., 2021), penalizing large weight values.
Figure 2 shows the evolution of weight norms ||w/112 | for all four algorithms. While all methods eventually maintain bounded weights, our unmodified approach achieves comparable performance without the computational overhead or hyperparameter tuning required by the other methods.
0.035
Target Network
Weight Projection
0.030
Ridge Regularization
No Modification
0.025
0.020
||well3
0.015
0.010
0.005
0.000
200
400
600
800
1000
1200
1400
Time Step
Figure 2. Each scenario independently 10 times, with the solid lines representing the averages of the squared T,2 norm of weights, and the shaded areas indicating the ranges between minimum and maximum values. This comparison illustrates the impact of different modification strategies on the algorithm's convergence behavior.
27


Reviews:
[{"review_id": "gRFEtDvWm9", "reviewer": "Reviewer_vZu3", "summary": "The authors propose the analysis of Q-learning with linear functional approximation that identifies under an assumption of $\\varepsilon$-softmax parametrization with an adaptive temperature that keeps the norm of the logits fixed, the rate of convergence to a bounded region.  Additionally, the authors provided the analysis for a case of finite MDPs and showed the algorithm's convergence to the optimal Q-value.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and positive evaluation. We appreciate the opportunity to address the specific questions and comments.\n> Hardness results in Liu (et al., 2023).\n\nThanks for the excellent suggestion. The hardness results indeed provide key context and may suggest that convergence to a set with the current rate might be the best we can hope. We will add this discussion and cite Liu et al. (2023) in Section 4 in next version. \n\n>  Large constant ... making the non-asymptotic rates potentially no more informative than Meyn's (2024) asymptotic result.\n\nWe understand the concern but want to make two points. (1) Meyn's results are only almost sure boundedness and convey no information about the variance. Even ignoring the rates, our results still provide a uniform bound of the variance across time steps. We argue that this is already valuable. (2) Although the constant is large, we argue it's the first result of this kind. It provides an explicit exponential decay rate, showing the dependency on key factors like $\\gamma$, step-size, and exploration parameters ($\\epsilon$, $\\kappa_0$). We believe this will lay a foundation for future refinements.\n\n>  Notation discrepancy for constants between the main text (using B) and the Appendix (using D).\n\nThanks for noting this. We use $B$ for main theorem constants and $D$ for intermediate ones in the Appendix. Some translation uses the equivalence between norms. We will clarify all these in next version.\n\n> Is it possible to provide some bounds on the value of a constant $\\beta$?\n\nWe appreciate the suggestion. We adopt the explicit bound for $\\beta$ from Meyn (2024), Lemma A.9: $\\beta = \\left[ (1 - \\gamma) - \\epsilon \\gamma \\sqrt{\\epsilon^{-1} + (1 - \\epsilon)^{-1}} \\right] \\lambda_{\\min}(X^\\top D_{\\mu_w} X) - \\gamma (1 - \\epsilon) \\frac{\\log (|\\mathcal{A}|)}{\\kappa_0} \\sqrt{\\lambda_{\\max}(X^\\top D_{\\mu_w} X)}$, where $\\lambda_{\\min}(\\cdot)$ and $\\lambda_{\\max}(\\cdot)$ namely denote the minimal and maximal eigenvalue of the matrix. This bound is positive for sufficiently small $\\epsilon$ and large $\\kappa_0$. We will add this to the revised manuscript (Appendix C.3).\n\n> Could you provide an exact value of the constant $B_{1,3}$ in the main text?\n\nThank you for the suggestion. We have $B_{1,3} \\leq 2\\left(\\frac{D_{1,3}}{(t + t_0)^{D_{1,2} \\alpha}}\\times 2C_{18} \\exp(2\\bar{t}+2\\bar{t}\\alpha_0  C_{18})+D_{1,4}\\right)$, where the parameters $D_{1,3}$, $D_{1,2}$, $C_{18}$, $D_{1,4}$, $t_0$, and $\\alpha$ are fixed constants from our analysis. Those constants are well defined and we can easily assemble them. We will add this in the revision but unfortunately we cannot display it here right now because it's too long. \n \nThanks again for your helpful questions, which have allowed us to enhance the technical clarity of our manuscript. We hope these responses fully address your points.", "claims_and_evidence": "1. The authors established the first $L^2$ convergence rate of linear Q-learning to a bounded set.\n\nThis result has been proven in Theorem 1. However, the dependence of the target weight norm on a number of state-action pairs is enormous, and it is especially harmful in the case of linear functional approximation since it is used in the case of an infinite number of state-action pairs. Additionally, the value of $\\beta$ (it is important since convergence rates depend on $\\exp(\\beta)$) was never specified in the paper with dependence on $\\kappa$ and $\\varepsilon$.\n\n2. The authors provide an analysis for a general stochastic approximation with time-inhomogeneous Markov noise under a novel type of assumption.\n\nThe authors provided the proof of the result in Theorem 3. While Assumption 3 might be seen as a strong one, the authors showed that it holds in the case of specific adaptive softmax parameterization in Linear Q-learning.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I did not check the theoretical results in detail. The main idea of the main result (Theorem 3) (stepping back on mixing time and coupling two chains, one the original and the second one is homogeneous) looks reasonable to me and should give the desired result, given Assumption 3 or 3'.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper can find its place in the current literature on stochastic approximation of Q-learning with linear functional approximation.", "essential_references_not_discussed": "I think that for a general exposition of the problem, it is important to discuss the hardness results of the proposed setting, i.e., (Lui et al., 2023). In particular, the fact of NP-hardness of finding the optimal policy under linear Q*-assumption gives a hint that convergence to the optimal policy in polynomial time should not be possible.\n\n\nLiu, S., Mahajan, G., Kane, D., Lovett, S., Weisz, G., & Szepesvári, C. (2023, July). Exponential hardness of reinforcement learning with linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory (pp. 1588-1617). PMLR.", "other_strengths_and_weaknesses": "Given the large value of the constant that bounds the maximal possible value, this result does not provide a lot of insights into the quality of the final solution. For me, these convergence rates do not give any additional insights into the algorithm behavior beyond the asymptotical result of Meyn (2024).", "other_comments_or_suggestions": "There is a discrepancy in notation between the main text and Appendix: in Appendix, the constants are denoted by a letter $D$, whereas in the main text, the letter $B$ is used.", "questions_for_authors": "- Is it possible to provide some bounds on the value of a constant $\\beta$?\n- Could you provide an exact value of the constant $B_{1,3}$ in the main text?", "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": "vx6mtibzeE", "reviewer": "Reviewer_bV3r", "summary": "The paper provides a theoretical analysis of Q-learning with linear approximation and a tabular setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive feedback and careful reading of our manuscript, which has improved our manuscript. We will incorporate your suggestions into the revised version. Below are our responses:\n\n> Assumption A1 seemed non-trivial, and the citation to Zhang (2021) Lemma 9 appears incorrect.\n\nWe apologize for the confusion. In short, Lemma 9 of Zhang (2021) is not meant to verify A1.\n\nA1 is much more trivial than it looks like. To our knowledge, A1 has been used at least three times previously: (1) A3.1 and A3.2 in Zhang et al. (2022) JMLR, (2) A5.1 in Zhang et al. (2021) ICML, and (3) Marbach & Tsitsiklis (2001) (TAC) (same concept with different wording). A1 is readily satisfied under simple conditions, e.g., when our Assumption A3.1 (ergodicity under the uniform random policy) holds and an exploring policy (like $\\epsilon$-greedy or $\\epsilon$-softmax with $\\epsilon > 0$) is used. The intuition is that $\\epsilon > 0$ ensures that all the state-action transition matrices in the closure share the same connectivity, i.e., any policy in that closure will choose all actions with a strictly positive probability. So all transition matrices share the same ergodicity with the uniform random policy. Our verification of A1 is in Line 332 - 346. This is also how Zhang et al. (2021, 2022) verify this assumption, see more discussion in Zhang (2022) in the text below their A3.2 and A4.4. We will add more details in the revision. \n\nLemma 9 of Zhang (2021) states the Lipschitz continuity of the stationary distribution w.r.t. the policy parameters under their A5.1. We restate it as our Lemma 15. We will clarify this further in our revision.\n\nRef: Marbach, P. and Tsitsiklis, J. N. Simulation-based optimization of markov reward processes. IEEE Transactions on Automatic Control, 2001.\n\n> Lemma 6 uses norm equivalence; does this require finite state and action spaces, and is this assumption necessary?\n\nYes and yes. Analyzing the underlying time-inhomogeneous Markov chain in a general state space is inherently difficult, even if it is compact. We need to introduce lots of (hard to verify) assumptions to ensure uniform mixing and will complicate the presentation a lot, especially as key constants like $β$ depend on $\\log |\\mathcal{A}|$, posing challenges for infinite action spaces. \n\n> The final bound in Lemma 7's proof seems inconsistent, particularly for the case where $\\\\|w\\\\|\\_2 < 1$.\n\nThanks for spotting this oversight. In the case when $\\\\|w\\\\|\\_2 \\leq 1$, we have $\\\\|w\\\\|^2\\_2\\leq \\\\|w\\\\|\\_2$, which then gives us $\\langle w, A(w)w + b(w)\\rangle \\leq (C_{7,1} + C_{7,2})\\\\|w\\\\|\\_2 \\leq -\\beta \\\\|w\\\\|^2\\_2 + (C_{7,1} + C_{7,2} + \\beta)\\\\|w\\\\|\\_2$. Thus, we can redefine $C_7 = C_{7,1} + C_{7,2} + \\beta$ to ensure\n$\\langle w, A(w)w + b(w)\\rangle \\leq -\\beta \\\\|w\\\\|^2\\_2 + C_7\\\\|w\\\\|\\_2$ for both cases. We will correct this definition in the next version.\n\n\n> Typo in an exponent's base on page 19.\n\nYou are correct. The base of the exponent should be $(\\frac{t_0+\\bar{t}}{t+t_0}) ^{D_{1,2}\\alpha}$. We will correct the term and subsequent constant $D_{1,3}$ in the revised manuscript.\n\n\n> Details are needed on how the conditions for Gronwall's inequality are met in the final step of Theorem 1's proof.\n\nThank you for questioning about the proof details. Below, we provide a detailed explanation to address this concern, and we will include this in Section C.4 of the revised manuscript.\nStarting from the update of $w_{t+1}$, we have $\\\\|w_{t+1}\\\\|\\leq \\\\|w_t\\\\| + \\alpha_t \\\\|H(w_t,Y_{t+1})\\\\|\\\\\\\\\n\\leq \\\\|w_t\\\\| + \\alpha_t C_{18}(\\\\|w_t\\\\|+1)$. \n\nThat is, $\\\\|w_{t+1}\\\\| \\leq \\alpha_0 C_{18} + \\sum_{i=0}^t(\\alpha_0 C_{18}+1)\\\\|w_i\\\\|$. Applying discrete Gronwall inequality, we obtain\n$\\\\|w_{\\bar{t}}\\\\| \\leq (C_{18} + \\\\|w_0\\\\|) \\exp(\\sum_{t=0}^{\\bar{t}-1} (1+\\alpha_0 C_{18})) = (C_{18} + \\\\|w_0\\\\|) \\exp(\\bar{t}+\\bar{t}\\alpha_0 C_{18})$. \n\nFurthermore, combining this with the bound on $B_{1,3}$ from Section C.4, we have $B_{1,3} = 2\\left(\\frac{D_{1,3}}{(t + t_0)^{D_{1,2} \\alpha}}\\times 2C_{18} \\exp(2\\bar{t}+2\\bar{t}\\alpha_0  C_{18})+D_{1,4}\\right)$, where $D_{1,4}$ is a constant bounded in Section C.4. We will include this detailed derivation in the revised manuscript.\n\n\n> An inequality involving $\\frac{1}{k^\\epsilon}$ on page 20 seems incorrect.\n\nThank you for this precise catch. We will correct it by introducing an appropriate constant factor $2^{\\epsilon_\\alpha}$ and update Appendix C.4 accordingly.\n\n> It would strengthen the paper to explain why the analysis doesn't apply to epsilon-greedy policies.\n\nWe agree with this suggestion. The `argmax` makes the $\\epsilon$-greedy policy discontinuous. This means the stationary distribution is also discontinuous in $w$, violating the Lipschitz continuity needed for $h(w)$ (Assumption A3/A3'). Our adaptive $\\epsilon$-softmax policy is smooth by design, satisfying this requirement.\n\nWe hope these responses address your points and you could consider updating your evaluation.", "claims_and_evidence": "The claims made in the manuscript are clear and well-written.", "methods_and_evaluation_criteria": "No numerical experiments.", "theoretical_claims": "Please see questions.", "experimental_designs_or_analyses": "No numerical experiments.", "relation_to_broader_scientific_literature": "The contribution of this paper is nontrivial since it resolves a long-standing problem of convergence of Q-learning in a more realistic setting, i.e., using a soft-max policy without assuming a strong assumption on the policies, i.e., Lipschitz policy.", "essential_references_not_discussed": "Relevant and important literatures are nicely summarized and provided.", "other_strengths_and_weaknesses": "Strength: The paper is well-structured and written very clearly for readers to follow. The theoretical result they establish would gain interest among the RL community.\n\nWeakness: There are still some remaining things to be polished and details to fill in. Please see the questions.", "other_comments_or_suggestions": "See the questions.", "questions_for_authors": "I have the following set of questions, which would help further determine my opinion on this manuscript. I really liked the manuscript, and the current rating won't be my final rating as long as the authors address the questions below.\n\n1. I was at first confused by the statement of Assumption A1, as this sounded more like a non-trivial lemma. I later realized this is Lemma 9 of Zhang from the appendix. However, when I check Zhang (2021) Lemma 9, it doesn't seem like the citation is correct. Can you please verify this?\n\n2. In the proof of  Lemma 6, the authors use the contraction property of the Bellman optimality operator $\\mathcal{T}$. If I am not mistaken, this operator is contraction with respect to $\\ell_\\infty$-norm, and authors are invoking the equivalence of the norm in finite-dimensional Euclidean space. So for the argument in Lemma 6 to go through, it seems that the finiteness of state space $S$ and action space $A$ is must; is this correct? Also, could you please \n\n3. I couldn't quite follow the derivation of the ultimate bound in the proof of 7. It seems that the bound $C_7 \\|w\\|_2$, which works for $\\|w\\|_2 \\le 1$ case, is larger than the penultimate bound. Can you please clarify this step?\n\n4. On page 19, in the first term of the RHS in expression between line 1023-1025, shouldn't it be $(\\frac{t_0 + \\bar t}{t+t_0})^{D_{1,2}\\alpha}$ instead of $(\\frac{t_0}{t+t_0})^{D_{1,2}\\alpha}$ ?\n\n5. Can you also please provide the details on how the condition of Gronwall's inequality is met for the last step of the Theorem 1 proof? I wonder how one is able to make sure the condition holds for all $n$ in Grownwall's inequality.\n\n6. On page 20, in lines 1087-1092, I believe this inequality doesn't hold as $1//k^{\\epsilon} > 1//(k+1)^{\\epsilon}$. It should be an easy fix though, by introducing some constant factor.\n\n7. Could you also please highlight which part of the proof would go wrong with the epsilon-greedy policy? I think this would also strengthen the paper.", "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": "pMt8ftO6lq", "reviewer": "Reviewer_2Mh8", "summary": "This paper provides the first L² convergence rate analysis for linear Q-learning with no algorithmic modifications. The authors show that linear Q-learning converges to a bounded set without requiring target networks, weight projection, experience replay, or regularization techniques that are typically employed to ensure stability. The key innovation is using an ϵ-softmax behavior policy with an adaptive temperature parameter. The paper also establishes convergence rates for tabular Q-learning with an ϵ-softmax behavior policy. The technical approach leverages a novel general result on stochastic approximations under Markovian noise with fast-changing transition functions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We're grateful for your thoughtful inquiry and positive assessment. We address your points below: \n\n> Could empirical evidence be provided ...?\n\nThis paper studies the same algorithm as Meyn (2024), which already provides extensive empirical results on its behavior. So we feel there is no need to redo it again. \n\n> ... compare performance with methods using algorithmic modifications.\n\nThanks for the great suggestion. We will add this comparison in the next version and believe this will be a great add-on. While our theoretical contributions are already significant, this addition should certainly enhance the overall paper.\n\n> How should practitioners select $\\epsilon$, $\\kappa_0$, and $t_0$?\n\nWe appreciate this practical query. Since our algorithm aligns with Meyn (2024), practitioners can draw from its empirical insights: $\\epsilon \\leq 0.2$ ensures stability for high $\\gamma$ (e.g., 0.99), per Lemma A.9; $\\kappa_0=1$ serves as a reasonable starting point; and for our step size $\\alpha_t=\\alpha/(t+t_0)^{\\epsilon_\\alpha}$, we suggest $t_0 \\geq 10$ with $\\epsilon_\\alpha=0.85$ for balance. Our revision will clarify these, blending Meyn’s findings with our theoretical framework.\n\n> For linear $Q$-learning, what are the implications of converging to a bounded set and the quality of policies?\n\nThanks for this insightful question. The immediate implication is that we now know that the variance of the parameters is uniformly bounded across time steps. Assessing the quality of the learned policy is challenging without making further artificial assumptions (see Meyn (2024) for more discussion) and is indeed an opportunity for future work.\n\n> How does it scale to high dimensions or non-linear methods?\n\nThe approach scales to high-dimensional linear settings. Theorem 1 holds regardless of dimension $d$. The adaptive temperature $\\kappa_w$ is crucial, ensuring sufficient smoothness (Lemmas 5, 6) and controlled exploration even if weight norm $\\\\|w\\\\|_2$ grows large.\n\nExtending to non-linear methods (e.g., neural networks) is feasible if we would like to introduce overparameterized networks and do linearization around initial weights (cf. Cai (2019)). We will additionally have some terms controlled by the width of the network. We believe such an extension is mostly a matter of labor and won't shed new technical insights. \n\nRef: Q. Cai et al. Neural Temporal-Difference Learning Converges to Global Optima. Advances in Neural Information Processing Systems, 32, 2019.\n\n\n> Could it extend to Expected SARSA or Q($\\lambda$)?\n\nFor Expected SARSA, Yes. Replacing $\\max_a$ with an expectation over $\\mu_w$ (for on-policy) or some $\\pi_w$ (for off-policy) fits our framework (Theorem 3), maintaining Lipschitz continuity (Lemma 5). \nFor Q($\\lambda$), the existence of off-policy eligibility traces will significantly complicate the behavior of the chain (we have to construct an auxiliary chain to contain the trace). But we envision the techniques from Yu (2012) can help.\n\nRef: H. Yu. Least squares temporal diﬀerence methods: An analysis under general conditions. SIAM Journal on Control and Optimization, 2012.\n\n> The constants in the bounds are not fully characterized. How tight/optimal are the rates?\n\nThank you for raising this point. We will revise the Appendix to show how intermediate constants(e.g., $D$) combine into the final $B$ bounds presented in the main theorems, accounting for norm conversions.\n\nTightness is unclear due to unknown parameters and RL’s hardness with linear function approximation (cf. Liu (2023)). We offer the first $L^2$ rates for linear Q-learning under weak assumptions as a benchmark. Liu (2023) suggests polynomial convergence is unlikely, supporting our state-of-the-art rates. For tabular Q-learning, we improve prior work with an $\\epsilon$-softmax policy, without count-based steps. Optimality remains open.\n\nRef: Liu, S. et al. Exponential hardness of reinforcement learning with linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory (pp. 1588-1617). PMLR.\n\n> Limited discussion on adaptive $\\epsilon$-softmax vs $\\epsilon$-greedy and why adaptive temperature is crucial.\n\nThe motivation for not using the $\\epsilon$-greedy policy is detailed at the very end of our response to the 2nd reviewer (bV3r). In short, it's because `argmax` is discontinuous.\n\nThe adaptive temperature $\\kappa_w$ further ensures the required smoothness beyond continuity, even when $\\\\|w\\\\|$ is large. This smoothness allows us to apply our analysis framework (Theorem 3) to prove $L^2$ rates. We will add this discussion in the revision.\n\nThank you again for the constructive feedback and positive evaluation. We hope these responses have adequately addressed your insightful questions.", "claims_and_evidence": "The paper makes two primary claims:\n\n1. Linear Q-learning with an ϵ-softmax behavior policy and adaptive temperature converges to a bounded set with a provable L² convergence rate.\n2. Tabular Q-learning with an ϵ-softmax behavior policy has a provable L² convergence rate to the optimal action-value function.\n\nThese claims are rigorously supported by theoretical analysis and proofs. The first claim extends recent work by Meyn (2024), which established almost sure convergence to a bounded set but did not provide a convergence rate. The second claim appears to be novel in establishing convergence rates for tabular Q-learning with an ϵ-softmax policy and without count-based learning rates.\nThe evidence is primarily theoretical, with detailed mathematical proofs for both claims. The authors also provide comparative tables that position their work against existing literature, highlighting how their analysis avoids algorithm modifications and restrictive assumptions that previous works relied upon.", "methods_and_evaluation_criteria": "The paper's methodology is primarily theoretical and builds on established techniques for analyzing stochastic approximation algorithms. Key methodological contributions include:\n\n1. A general stochastic approximation result for time-inhomogeneous Markovian noise in a single-timescale setting, which is more challenging than the two-timescale settings analyzed in prior work.\n2. The identification of a pseudo-contraction property for the weighted Bellman optimality operator, which enables the convergence analysis for tabular Q-learning.\n3. Technical innovations in bounding terms involving adaptive temperature in the ϵ-softmax policy.\n\nThe paper does not include empirical evaluation, which is a limitation. While the theoretical contributions are significant, experimental validation would strengthen the work by demonstrating practical convergence behavior and comparing it to existing approaches with algorithmic modifications.", "theoretical_claims": "The paper's theoretical claims are generally well-founded and rigorously proven. The proofs follow a logical structure, first establishing a general stochastic approximation result (Theorem 3) that is then applied to both linear Q-learning (Theorem 1) and tabular Q-learning (Theorem 2).\nStrengths:\n\n- The analysis handles the challenging single-timescale case where the transition matrix evolves as fast as the weights.\n- The paper identifies the novel pseudo-contraction property of the weighted Bellman optimality operator.\n- The convergence rates are explicit and account for different learning rate regimes.\n\nLimitations:\n\n- The constants in the convergence bounds (B1,3, B1,6, B2,3, B2,6) are not fully characterized, making it difficult to assess the tightness of the bounds.\n- The analysis requires sufficiently small ϵ and sufficiently large κ0 and t0, but does not provide explicit guidance on how to set these hyperparameters in practice.\n- The paper lacks discussion on the optimality of the obtained convergence rates.", "experimental_designs_or_analyses": "As mentioned, the paper does not include empirical evaluation, which is a notable weakness.", "relation_to_broader_scientific_literature": "Tables 1 and 2 provide comprehensive comparisons with previous work on linear and tabular Q-learning, clearly highlighting the novel aspects of this research.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Additional strengths:\n\n- The paper's analysis is technically sophisticated yet clearly presented.\n- The focus on the original Q-learning algorithm without modifications is valuable for understanding fundamental convergence properties.\n- The general stochastic approximation result (Theorem 3) may have applications beyond Q-learning.\n\nAdditional weaknesses:\n\n- The paper does not discuss the implications of converging to a bounded set rather than to the optimal policy or value function for linear Q-learning.\n- There is limited discussion of the practical significance of the ϵ-softmax behavior policy with adaptive temperature compared to more commonly used ϵ-greedy policies.\n- The paper could benefit from more intuitive explanations of why the adaptive temperature mechanism is crucial for convergence.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. Could you provide empirical evidence to validate the theoretical convergence rates and compare the performance with methods that use algorithmic modifications?\n2. How should practitioners select the hyperparameters ϵ and κ0 to ensure convergence in practical applications?\n3. For linear Q-learning, what can be said about the quality of the policies derived from the bounded set to which the algorithm converges? How far might these policies be from optimal?\n4. How does the proposed approach scale to high-dimensional state spaces or function approximation methods beyond linear?\n5. Could the analysis be extended to other off-policy algorithms such as Expected SARSA or Q(λ)?\n6. How tight are the derived bounds, and do you believe the convergence rates are optimal?\n\n\n### Post-rebuttal response ###\nI appreciate the authors' thorough responses to my questions. While they've addressed my technical concerns regarding comparisons to Meyn (2024), hyperparameter selection, and theoretical implications, I maintain my original score. My assessment balances the paper's strong theoretical contribution against the absence of empirical validation and limited insight into policy quality. Though the authors committed to adding algorithmic comparisons, these aren't yet in the manuscript. The paper deserves publication, but these limitations warrant my original assessment.", "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": "AjfKylDy7a", "reviewer": "Reviewer_DQiq", "summary": "This paper challenges the widely held belief that linear Q-learning can diverge and instead proves that linear Q-learning converges to a bounded set. Unlike previous studies that required algorithmic modifications (e.g., target networks, experience replay), this work establishes the first L2 convergence rate for linear Q-learning without modifying the original algorithm. The key technique is a novel stochastic approximation result under fast-changing Markovian noise, proving that linear Q-learning remains stable when using an ϵ-softmax behavior policy with an adaptive temperature. The paper also extends the results to tabular Q-learning, establishing its L2 convergence rate for the first time.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive evaluation and perfect score for our manuscript. We appreciate the opportunity to clarify the comparison of our tabular $Q$-learning convergence rate with existing literature:\n> Comparing the convergence rate for the tabular case with existing rates in the literature would be useful. Is the proposed method faster, or is its performance simply comparable to existing approaches?\n\nComparing our tabular $Q$-learning convergence rate (Theorem 2) with existing literature reveals that our method achieves an $L^2$ rate simply comparable to prior approaches. Theorem 2 shows exponential decay, similar to rates in works like Even-Dar et al. (2003) and Chen et al. (2021), which also exhibit exponential convergence under different assumptions (e.g., count-based rates or fixed policies). \n\nThe primary novelty of our result lies not necessarily in achieving a strictly faster rate in terms of the exponent's constants (as comparing these constants, which depend on complex problem parameters like $B_{2,5}$ and $B_{2,6}$  across different analytical frameworks is inherently difficult), but rather in demonstrating this competitive exponential convergence under a practical adaptive $\\epsilon$-softmax behavior policy and without using count-based learning rates.\n\nTherefore, while the exponential convergence form aligns with existing benchmarks, the significance stems from achieving this strong type of guarantee under arguably more standard algorithmic settings used in practice. We view our rate as highly competitive, prioritizing the demonstration of robust convergence under these practical conditions.\n\n> It would be helpful to update the references to reflect their most recent status. \n\nThank you for the thoughtful and valuable suggestions. We appreciate the recommendation to update references to their latest status and will ensure all citations reflect the most recent publication details.\n\n> Improving the readability of the presentation would be beneficial, especially given the extensive mathematical content.\n\nImproving readability is also a great point, and we will refine the presentation to make the mathematical content more accessible. For example, we will add detailed derivations in the revised Appendix (e.g., Sec C.4) showing how intermediate constants like $D$ combine, considering factors like norm conversions, to form the final $B$ bounds presented in the main theorems.\n\n> It would be valuable to include experiments to demonstrate the results. In particular, testing the well-known Baird example of the deadly triad would be interesting. \n\nWe do agree experiments would be a great add-on. However, we note that we study exactly the same algorithm as Meyn (2024) and Meyn (2024) already includes extensive experimental validation, including Baird example. We feel there is no need to redo it, as our work focuses on novel convergence rates that complement Meyn's empirical results.\n\n> It would be helpful to provide an intuitive explanation for the choice of the specific exploration policy using softmax.\n\nWe’re grateful for the suggestion to explain the softmax exploration policy intuitively. The adaptive $\\epsilon$-softmax policy choice is technically motivated. Our analysis framework (Theorem 3) requires Lipschitz continuity of the expected update $h(w)$ (Assumption A3/A3'). Our policy ensures this (Lemmas 5, 6), enabling the analysis. Standard $\\epsilon$-greedy is discontinuous due to `argmax` and typically violates this assumption, preventing the direct application of our proof technique. The adaptive temperature $\\kappa_w$ is the crucial mechanism ensuring this smoothness holds globally, even if $\\\\|w\\\\|$ is large (by making the policy appropriately less sensitive). This is also key to our proof technique. An $\\epsilon$-greedy policy would fail to use our novel single-timescale SA result. We will clarify this more in the revision.\n\nWe truly appreciate your support and positive evaluation of our research.", "claims_and_evidence": "The paper claims that:\n1.\tLinear Q-learning does not diverge, but instead converges to a bounded set.\n2.\tAn L2 convergence rate for linear Q-learning is derived without algorithmic modifications.\n3.\tTabular Q-learning also has an L2 convergence rate, confirmed via a novel pseudo-contraction property.\nThe results are well-supported theoretically.", "methods_and_evaluation_criteria": "The paper introduces:\n1.\tA novel stochastic approximation framework to analyze single-timescale Markovian noise.\n2.\tϵ-softmax behavior policy with adaptive temperature to ensure sufficient exploration.\n3.\tL2 convergence analysis for both linear and tabular Q-learning.\n4.\tA pseudo-contraction property of the weighted Bellman operator, proving tabular Q-learning’s stability.\nEvaluation is based on:\n•\tTheoretical convergence proofs.\n•\tComparisons with prior work, showing that previous analyses required restrictive assumptions.\n•\tMathematical guarantees on stability and error bounds.", "theoretical_claims": "The paper establishes:\n1.\tLinear Q-learning is stable: It does not diverge but converges to a bounded set.\n2.\tL2 convergence rates: Error bounds decrease over time, ensuring stability.\n3.\tTabular Q-learning also has an L2 convergence rate, supported by a novel pseudo-contraction property.\n4.\tSingle-timescale stochastic approximation: Unlike prior two-timescale methods, the analysis holds even when transition functions evolve at the same rate as weights.\nThe mathematical proofs are rigorous.", "experimental_designs_or_analyses": "The paper does not include empirical experiments but instead evaluates the method using:\n1.\tTheoretical analysis: Proving L2 convergence rates mathematically.\n2.\tComparisons with prior work, highlighting weaker assumptions and stronger guarantees.\n3.\tAlgorithmic stability proofs without relying on experience replay, target networks, or weight projection.", "relation_to_broader_scientific_literature": "This work contributes to:\n•\tQ-learning stability analysis: It disproves prior beliefs that linear Q-learning can diverge.\n•\tStochastic approximation theory: Extends single-timescale convergence analysis.\n•\tReinforcement learning theory: Strengthens understanding of off-policy learning stability.", "essential_references_not_discussed": "The references in the paper are appropriate.", "other_strengths_and_weaknesses": "Strengths:\n•\tFirst L2 convergence rate for linear Q-learning.\n•\tStrong theoretical results without modifying the algorithm.\n•\tNovel single-timescale analysis of Markovian noise.\nWeaknesses:\n•\tNo empirical validation", "other_comments_or_suggestions": "•  It would be helpful to update the references to reflect their most recent status. In other words, some cited papers have since been published in journals or presented at conferences, and their reference details should be updated accordingly. \n•  Improving the readability of the presentation would be beneficial, especially given the extensive mathematical content. \n•  It would be valuable to include experiments to demonstrate the results. In particular, testing the well-known Baird example of the deadly triad would be interesting. \n•  It would be helpful to provide an intuitive explanation for the choice of the specific exploration policy using softmax.", "questions_for_authors": "Comparing the convergence rate for the tabular case with existing rates in the literature would be useful. Is the proposed method faster, or is its performance simply comparable to existing approaches?", "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:

Meta-review: The authors did a good job of addressing the concerns raised by the reviewers, and everybody converged to a positive recommendation on this one. I encourage the authors to clarify any issues that caused confusion among the reviewers in their final version.
Decision: Accept (poster)