Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features
Authors: Zixuan Xie
Xinyu Liu
Rohan Chandra
Shangtong Zhang
Venue: NeurIPS 2025 poster ()
Keywords: temporal difference learning
convergence rate
reinforcement learning
linear function approximation
Primary area: reinforcement_learning

Abstract: Linear TD($\lambda$) is one of the most fundamental reinforcement learning algorithms for policy evaluation. Previously, convergence rates are typically established under the assumption of linearly independent features, which does not hold in many practical scenarios. This paper instead establishes the first $L^2$ convergence rates for linear TD($\lambda$) operating under arbitrary features, without making any algorithmic modification or additional assumptions. Our results apply to both the discounted and average-reward settings. To address the potential non-uniqueness of solutions resulting from arbitrary features, we develop a novel stochastic approximation result featuring convergence rates to the solution set instead of a single point.

Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features
Zixuan Xie
Xinyu Liu" University of Virginia xinyuliu@virginia.o
University of Virginia
xie. zixuan@maal virginia. edu
Rohan Chandra
Shangtong Zhang University of Virginia shangtong@virginia. edu
University of Virginia
rohanchandra@@iirgini...c
Abstract
Linear TD(A) is one of the most fundamental reinforcement learning algorithms for policy evaluation. Previously, convergence rates are typically established under the assumption lincarly independent features, which does not hold in many practical scenarios. This paper instead establishes the first L convergence rates for linear TD(A) operating under arbitrary features, without making any algorithmic modification additional assumptions. Our results apply to both the discounted and average-rewart settings. To address the potential non-uniqueness of solutions resulting from arbitrary features, develop novel stochastic approximation result featuring convergence rates to the solution set instead of a single point.
Introduction
Temporal difference learning (TD, Sutton [1988]) is fundamental algorithm in reinforcement learning (RL, Sutton and Barto (2018]), enabling efficient policy evaluation by combining dynamic programming [Bellman, 1966] with stochastic approximation (SA, Benveniste et al. [1990], Kushner and Yin [2003], Borkar [2009]). Its linear variant, linear TD(A) [Sutton, 1988], emerges as a practical extension, employing linear function approximation to tackle large continuous state spaces where tabular representations become impractical. Linear TD(A) takes the dot product between features and weights compute the approximated value. Establishing theoretical guarantees for linear TD(A), particularly convergence rates, has been a major focus of research. Most existing works (Table 1), however, require the features used in linear TD be linearly independent. As argued in Wang and Zhang [2024], this assumption is impractical in many scenarios. For example, in continual learning with sequentially arriving data [Ring, 1994, Khetarpal et al., 2022, Abel al., 2023], there is no way to rigorously verify whether the features are independent or not. See Wang and Zhang [2024] for more discussion on the restrictions of the feature independence assumptions. Furthermore, Dayan [1992], Tsitsiklis and Roy [1996, 1999] also outline the elimination of the linear independence assumption as future research direction.
While efforts have been made to eliminate the linear independence assumption [Wang and Zhang, 2024], they only provide asymptotic (almost sure) convergence guarantees in the discounted setting. By contrast, this paper establishes the first L convergence rates for linear TD(A) with arbitrary features in both discounted and average-reward settings. This success is enabled by novel stochastic approximation result (Theorem 3) concerning the convergence rates to a solution set instead of single point, driven by novel Lyapunov function. This result provides unified approach
Equual contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

applicable to both discounted (Theorem 1) and average- reward (Theorem 2) settings, Notably, we do make any algorithmic modification and do not introduce any additional assumptions. Table provides a detailed comparison of existing theoretical analyses for linear TD(A), contextualizing our contributions within the landscape of prior work.
Noise Type
Setting
Features
Rate
Tsitsiklis and Roy [1996]
7
Independent
Markovian Markovian i.idd
Bhandari et al. [2018]
<
Independent
Lakshminarayanan and Szepesvári [2018]
7
Independent
Srikant and Ying [2019]
<<1
Independent
Markovian
Wang and Zhang [2024]
7<1
Arbitrary
Markovian
Chen et al. [2025a]
9<1
Independent
i.i.d.
Mitra [2025]
7
Independent
Markovian
Theorem
<
Arbitrary
Markovian
Tsitsiklis and Roy [1999]
7
Independent
Markovian
Zhang et al. [2021c]
=
Independent
Markovian
Chen et al. [2025b]
=
Independent
Markovian
Theorem 2
7=1
Arbitrary
Markovian
Table 1: Comparison of finite-sanen sample analyses for linear TD(A). "Setting" indicates the problem setting: 7 < 1 stands for the discounted setting and y = stands for the average reward setting. "Features" describes assumptions assumed. "Arbitrary" indicates no assumption is made on features. "Noise Type" indicates the data generation process: Markovian samples independent and identically distributed (i.i.d.) samples. "Rate" is checked if a convergence rate is provided.
the features. "Independent" indicates linear independence is
2 Background
Notations. We use (x, = TTyy to denote the standard inner product in Euclidean spaces and ||-I| to denote the lg norm for vectors and the associated induced operator norm (i.e., the spectral norm) for matrices, unless stated otherwise.
function f is said to be L-smooth (w.r.t. II-I)) if Vw, w',
f(w") S f(w) + (VS(w), w' -w) + _ ||w - w|2 2. For a matrix A, col(A) denotes its column space, ker(A) denotes its kernel, and At denotes its Moore-Penroee inverse. When is a point and U is set, we denote dxx, U/= inf ||x yl as the Euclidean distance from æ to U. For sets U, V, their Minkowski sum + = {u+v и E U, u V): and U- denotes the orthogonal complement of U. We use 0 and to denote the zero vector and the all-ones vector respectively, where the dimension clear from context. For any square matrix A E Rdxd (not necessarily symmetric), we say A negative definite (n.d.) if there exists a & > 0 such that T Ar < =||==1 Va E IRd, For any set E C Rd, we say A is n.d. on E if there exists a E >> such that x Ar < =|| Vz E E. A is negative semidefinite (n.s.d.) if E = 0 in the above definition.
Markoy Decision Processes. We consider an infinite horizon Markov Decision Process (MDP, Bellman [1957]) defined by a tuple A,,,, where S is finite set of states, A is finite set of actions, p S x x A + [0. 1] is the transition probability function, r : S A - IR is the reward function, and Po S [0. denotes the initial distribution. In this paper,
focus the policy evaluation problem, where the goal is to estimate the value function of an arbitrary policy A S [0, 1]. At the time step an initial state Sn is sampled from po. At each subsequent time step I, the agent observes state S, E S, executes an action A, ~ T-|[S;), receives reward R441 = r(S,, At), and transitions the next state S.41 p(-1S,, At). We use Pa to denote the state transition matrix induced by the policy म, i.c., [r[s, s'] = =' ग (a)s))(ss) [s, a). Let dy E IS be the stationary distribution of the Markov chain induced by the policy स. We use Dz to denote the diagonal matrix whose diagonal d,.
Linear Function Approximation. In this paper, we use linear function approximation to approximate value functions Ux S + R (to be defined shortly). We consider feature mapping S - Rd and weight vector E ddd We then approximate U.e (s) with ass) We use X R (|]d to denote

---

the feature matrix, where the s-th row of X is x0s) T. The approximated state-value function across all states can then be represented as the vector Xw E pl The goal is thus to find w such that X'w closely approximates Un-
Discounted Setting, In the discounted setting, we introduce a discount factor E [0, 1). The (dis- counted) value function U4 + IR for policy и is defined as 7 (s) E[E 7 Re+e+1 S - 8] We define the Bellman operator T : Iils| + glll as To = T + >PP. where Tx E R is the vector of expected immediate rewards under и, with components (x Eg T (Ta ((a)s)((ss a). With [0, 1), the X-weighted Bellman operator Tx is defined Tx = (1 X) Em= Ammm+te Tx + PPxu, where
TA (A)) =1 (1)) Tx:
=1 Em= (Ay) pm+ (1 A)(1 1 -
This represents weighted average of multi-step applications of T. is well-known that U, is the unique fixed point of TA [Bertsekas and Tsitsiklis, 1996]. Linear TD(A) a family of TD learning algorithms that use eligibility traces to estimate (s) of the fixed policy π with linear function approximation. The algorithm maintains a weight vector Rd and an eligibility trace vector e, E IRd, with the following update rules:
W+++1 wi + are (Re+1 (x((++)) wy x(St) weees,
e - + xs.),, e-1 1-1-0 =.
(Discounted TD)
Here, {ar} is the learning rate. The eligibility trace e, tracks recently visited states, assigning credit for the prediction error to multiple preceding states. Let
= Dx I)X, b= x D W. = [w[AAw + bb
If X has a full column rank, Tsitsiklis and Roy [1996] proves that W. is a singleton and {w²) converge to -b- almost surely. A key result used by Tsitsiklis and Roy [1996] is that the matrix Da(7PA- - 1) ) is n.d. [Sutton, 1988]. As a result, the A matrix is also n.d. when X has a full column rank. Wang and Zhang [2024] prove, without making any assumption on X, that W. is always nonempty and the } converges to W, almost surely. A key challenge there is that without making assumptions on X, A is only n.s.d.
Average-Reward Setting, In the average-reward setting, the overall performance of a policy i is measured by the average reward J = lim E ΣT- Re The corresponding (differential)
value function is defined as ez (s) limy +00 T -i=0 [r Axti) J+)[S, s]. We define the Bellman operator T R S1 RISl| Tu = Tr J,1 + P.v. Similarly, the X-weighted counterpart T is defined as T = rλ - 1 + Pxv. Although F is fixed point of T it is not the unique fixed point. In fact,
1
गि2
c1
c c
R}
(2)
are all the fixed points of T [Puterman, 2014]. Linear average-reward TD(A) is an algorithm for estimating both Jn and , using linear function approximation and eligibility traces. The update rules are
e = X 1 + x(S)), e- =-1 0,
Wr+1 = w. + az R1+1 - Jr + x(S++1) wt x(Si) wreer,
J+1 J, + (c(2411-5) Jt).
(Average Reward TD)
where } and (B.) are learning rates. Let
Ā= X= D, f)x, 3 = X (r 1 1), W. = =ww(Aw + 00.
(4)
If X has a full column rank and & col(X), Tsitsiklis and Roy [1999] proves that W. is a singleton and {w:) converge - '5 almost surely. This is made possible by an important fact from the Perron-Frobenin theorem (see, e.g., Seneta [2006]) that
(5) Zhang et al. [2021c] further provides a convergence rate, still assuming X has a full column rank but without assuming & col(X). When X does not have full column rank, to our knowledge, it is not clear whether W. is always nonempty or not, much less the behavior of {wr).
(w|w> Dx I) = 0} {c1|c E R}.
3

---

3 Main Results
We start with our assumptions. As promised, we do not make any assumption on X. Assumption 3.1. The Markov chain associated with Pa is irreducible and aperiodic. Assumption LR. The learning rates at [x+taa} and Bt Cga where & E (0.5, 1), 0,
tu > and cg are constants.
Discounted Setting. Wang and Zhang [2024] proves the almost sure convergence of (Discounted TD) with arbitrary features by using || w.ll2 with arbitrary and fixed w. W. as a Lyapunov function and analyzing the property of the ODE dw(() Wang and Zhang [2024] conducts their analysis in the complex number field. In this work, instead of following the ODE-based analysis originating from Tsitsiklis and Roy [1996], Borkar and Meyn [2000], we extend Srikant and Ying [2019] to obtain convergence rates by using d( d(wu, W.)² 2 as the Lyapunov function. To our knowledge, this is the first time that such distance function to a set is used as the Lyapunov function to analyze RL algorithms, which is our key technical contribution from the methodology aspect. According to Theorem I of Wang and Zhang [2024], W. is nonempty, and ap- parently convex and closed. Let [ww) = arg min., ew, ||w w. be the orthogonal projection to W.. We then define L(w) = _d(w, W.)² 1 fll [(w)] 1 observations are
de Aw()). Since A is only n.s.d.,
Two important and highly non-trivial
(i) VL(w) = w I(w) (Example 3.31 of Beck [2017]).
(ii) L(w) is 1-smooth w.r.t ||-|| (Example 5.5 of Beck [2017]).
Both (i) and (ii) result from the fact that W. is nonempty, closed, and convex. Using L(w) as the Lyapunov function together with more characterization of ( (Section 5.2), we obtain
Theorem 1.
Let Assumptions 3.1 and LR hold and [0, Then for sufficiently large to and a, there exist some constants Crimi and K₁ aC, > 1 such that the iterates {wit generated by (Discounted TD) satisfy for all t
[(w, W.) S Orimi
to( d(wp, w²,2+ (1422g)min2e 11,,,11 ))
The proof is in Section 5.2. Notably, Lemma 3 of Wang and Zhang [2024] states that for any We, war E W., it holds that Xw. = XWee. We then define
0r Ww=
(6)
for any w. E W.. Theorem then also gives the _ convergence rate of the value estimate, ie., the rate at which Xw, converges to 0z. The value estimate 0, is the unique fixed point of projected Bellman equation. See Wang and Zhang [2024] for more discussion on the property of Cg. Additionally, by choosing a sufficiently large a, we can ensure [x]]
2 2 1, so the rate is determined by the exponent 2 - 1. For the standard choice & = 1, the resulting rate becomes (lnt//), which matches existing analyses that assume linearly independent features [Bhandari et al., 2018, Srikant and Ying, 2019]. An analogous observation holds for Theorems 2 and 3 as well, since their corresponding x is also proportional to a.
Average Reward Setting. Characterizing W. is much more challenging. We first present a novel decomposition of the feature matrix X. To this end, define m = rank(X) < min (IS], If m O. all the results in this work are trivial and we thus discuss only the case m 2 1.
Lemma 1. There exist matrices X1, X2 such that
X1 X2 with the following properties (1)
rank(Xi) = m X and 1 & X1 (2) X2 = 10T with 0 E Rd.
The proof is in Section B.1 with being the indicator function. Essentially, X₂ is rank one matrix with identical rows 0 (i.e., the i-th column of X₂ is 0,1). To our knowledge, this is the first time that such decomposition is used to analyze average-reward RL algorithms, which is our second
TTii theorem only discusses the case of A = 0. The proof for general À E [0, 1] is exactly the same up to change of notations.

---

technical contribution from the methodology aspect. This decomposition is useful in three aspects. First, we have = x = (Px - T)X, (Lemma 14). Second, this decomposition is the key to prove that W. is nonempty (Lemma 15). Third, this decomposition is the key to characterize W. in that W. - [w.} + [ with w being any vector in W (Lemma 16). To better understand this characterization, we note that ker(X,) [w[X " cl, E R} (Lemmaa 16). As result, adding any We E ker(X1) to a weight vector w changes the resulting value function Xw only by cl. Two values and 12 be considered "duplication" if 02 el (ef. (2)). So intuitively, ker ker(X1) is the source of the "duplication". With the help of this novel decomposition, we obtain
Theorem 2.
Let Assumptions 3.1 and LR hold and [0. 1). Then for sufficiently large a, to and ca, there exist some constants CTimz and R2 = aCio 1 such that the iterates {we} generated by (Average Reward TD) satisfy for all t
IE (Je Ja)² d(we, w.) SCmmmm (4) (4) [Jo- Jx)² d(wo. W.)²
Crimz
In(e+to) (1tt))ml11081.1111-1-
The proof is in Section 5.3.
Stochastic Approximation. We now present general stochastic approximation result to prove Theorems and 2. The notations in this part are independent of the rest of the paper. We consider a general iterative update rule for weight vector Idd, driven by a time-homogencous Markov chain {Yr} evolving in a possibly infinite space y:
W++1 = we + H (wr, Y1+1),
(SA)
where Rdd y + IRd defines the incremental update.
Assumption A1. There exists constant Cai such that suppey (0, 8)ll co,
|| (W1,,)) (w2,, v)ll SCarll -wyll Vwi, W2, y.
Assumption A2. (Vi) has a unique stationary distribution dy- Let h(w))= = Ey (w, v)]- Assumption Al then immediately implies that [k(ww)) - (l==)) <CAil|
-wzl Ywi, W2.
In many existing works about stochastic approximation [Borkar and Meyn, 2000, Chen et al., 2023b, Qian et al., 2024, Borkar et al., 2025], it is assumed that h(w)) = O adopts a unique solution. To work with the challenges of linear TD with arbitrary features, we relax this assumption and consider a
set W. Importantly, W, does not need to contain all solutions to h(w) = O. Instead, we make the following assumptions on W. Assumption A3. W, is nonemply, closed, and convex.
Notably, W. does not need to be bounded. Assumption A3 ensures that the orthogonal projec- tion to W. is well defined, allowing us to define I'(w) = arg min ew, || w. [I. L(w) = 1 I| - Il2) As discussed before, Assumption A3 ensures that VL(w) = w - I(w) and 1-smooth w.r.t. I|-II [Beck, 2017]. We further assume that the expected update h(w)) decreases L(w;) in the following sense, making L(w) a candidate Lyapunov function.
Assumption A4. There exists a constant Ca4 > such that almost surely,
(VL(w,), h(w))) S -Ca+L(wi).
Lastly, we make the most "unnatural" assumption of W.. Assumption A5. There exists a matrix X and constants CAs and T E [0, 1) such that (1) Vic, E W., [| < CAs: (2) Yw, y. |nl (w, y)ll < CAs(]]Xw]] + 1); (3) For any n 2 1:
[l(ww) E H ww Y++I) (I w|| + 1)
This assumption technically motivated but trivially holds our analyses of (Discounted TD) and (Average Reward TD). Specifically, Assumption Al immediately leads to at-most- linear growth
5

---

[[ r)ll I ( + 1) for some constant CAL.1. However, this bound is insufficient for our analysis because ||m|| < [-w--(w) + [[(()]] but T(w) W. can be unbounded. By Assumption A5, we can have Xxw]l < I The inequality (7) is related to geometrical mixing of the chain and we additionally include Xw in
< |||||| [( |I + CAs-
the bound for the same reason. We now present our general results regarding the convergence rate of (SA) to W..
Theorem 3. Let Assumptions Al A5 and LR hold. Denote = aCAs. then there exist some constants to and CTima, such that the iterates {wi} generated by (SA) satisfy for all
B[L(w:)] S CTim3, ( (e) [e] T(wo) + CTima,2 [f+t))mmm22 Jmii 1.1=]
In(+++la)
The proof is in Section 5.1. We remark that once we have the recursion in Lemma 5, our theoretical framework can be readily extended to the constant step-size setting (akin to Chen et al. [2023b]). demonstrating its broad applicability.
4 Related Works
Most prior works regarding the convergence of linear TD summarized in Table rely on having linearly independent features. In fact, the reliance on feature independence goes beyond linear TD and exists in almost all previous analyses of RL algorithms with linear function approximation. see. e.g., Sutton et al. [2008, 2009], Maei [2011], Hackman [2012]. Bo et al. [2015]. Yu [2015, 2016], Zou al. [2019]. Yang et al. [2019], Zhang al. [2020b]. Xu al. [2020a]] Zhang et al. [2020a]. Xu et al. [2020b]. Wu et al. [2020]. Chen et al. [2021]. Long et al. [2021], Qiu et al. [2021]. Zhang et al. [2021a.b], Xu et al. [2021], Zhang al. [2022], Zhang and Whiteson [2022]. Zhang al. [2023], Chen et al. [2023a]. Nicolò et al. [2024], Yue et al. [2024], Swetha et al. [2024]. Liu et al. [2025a], Qian and Zhang [2025], Maity and Mitra [2025], Yang et al. [2025]. Chen al. [2025b], Shaan and Siva [2025], Liu et al. [2025c]. But as argued by Dayan [1992]. Tsitsiklis and Roy [1996, 1999], Wang and Zhang [2024], relaxing this assumption an important research direction. This work can be viewed as extension of Wang and Zhang [2024]. Zhang et al. [2021c]. In terms of (Discounted TD), we extend Wang and Zhang [2024] by proving a finite sample analysis. Though we rely on the characterization of W. from Wang and Zhang [2024], the techniques sample analysis are entirely different from the techniques of Wang and Zhang [2024] for almost sure asymptotic convergence. In terms of (Average Reward TD), we extend Zhang et al. [2021c] by allowing X to be arbitrary. Essentially, key to Zhang et al. [2021c] is their proof that A is n.d. on subspace E, assuming X has a full column rank. We extend Zhang et al. [2021c] in that we give a finer and more detailed characterization of the counterparts of their E through the novel decomposition of the features (Lemma 1) and establish the n.d. property under weaker conditions (i.e., without assuming X has full column rank). Importantly, despite relaxing the feature- induure-indeenndenee assumption, our convergence rate remains on par with existing full-rank features [Bhandari et al., 2018, Srikant and Ying, 2019]. Our improvements are made possible by the novel Lyapumov function L(w) and we argue that this Lyapunov function can be used to analyze many other linear RL algorithms with arbitrary features.
for finite
sample results obtained under
In terms of stochastic approximation, our Theorem is novel in that allows convergence to possibly unbounded set. By contrast, most prior works about stochastic approximation study convergence to a point [Borkar and Meyn, 2000, Chen et al., 2020, Zhang et al., 2022, Chen et al., 2023b, Qian et al., 2024, Liu et al., 2025a, Borkar et al., 2025, Chen et al., 2025a]. In the case of convergence to a set, most prior works require the set to be bounded [Kushner and Yin, 2003, Borkar, 2009, Liu et al., 2025a.b]. Only few prior works allow stochastic approximation to converge to an unbounded set, see, e.g., Bravo and Cominetti [2024], Chen [2025], Blaser and Zhang [2025], which apply to only tabular RL algorithms.
5 Proofs of the Main Results
5.1 Proof of Theorem
Proof. From the 1-smoothness of (ww) and (SA), we can get
L(w++1) S L(w:) + aw I(wa), k(w)))

---

+ ta - I(ws), (u, Yt) h(w))) +
YOII.
(8)
We then bound the RHS by one. (w (w-wiy r(w), h(w)) is already bounded in Assumption A4. Lemma 2. There exists a positive constant C2. such that for any w,
[Xw]] < C2([lw r'(w)ll + +)..
The proof is in Section C.I. With Lemma 2 and Assumption A5, the last term in (8) can be bounded easily.
Lemma 3. There exists a constant C3 such that || (ur. Y.) & Cs(Ilu; = + 1).
The proof is in Section C.2. To bound (w) [(ws), H (wr, Yi) h(w,)), leveraging (7), we define
Ta = min 2 0 CAST" o))
as the number of steps that the Markov chain needs to mix to am accuracy a. In addition, we denote a shorthand Ott -ii ag. Then with techniques from Srikant and Ying [2019], we obtain
Lemma 4. There exists constant C4 such thut
[l [(w)), (w,, Vi) -((w)))) S Ci0t -t (1 ((w))ll + 1).
The proof's is in Section C.3. Plugging all the bounds back to (8), we obtain Lemma 5. There exists some D. O00000000 -t,,t-),, such that
B[L(w++1)] S (1 Ca4a))BB[(uu)) + D..
The proof is in Section C.4. Recursively applying Lemma then completes the proof of Theorem (See Section C.5 for details).
In the following sections, first map the general update (SA) to (Discounted TD) and (Average Reward TD) by defining H(w, y), hww), and L(w) properly. Then we bound the remaining term (V[(w,) h(w:) complete the proof.
5.2 Proof of Theorem
Proof. We first rewrite (Discounted TD) in the form of (SA). this end, we define Ye4r - (St, Ar, (.,1,,1)),,) which evolves in infinite space y = S x A x S x {e ||l|| S C.) with
C. max, [[=()]]] being the straightforward bound of sup, ||e/|l We define the incremental update
1-nA
H R R as
H (ww, v) (r(s, yr((s) w x(s) w)e, using shorthand = (s, a, s', e). We now proceed to verifying the assumptions of Theorem 3. Assumption A1 verified by the following lemma.
(10)
Lemma 6. There exists some finite Cg such that
|| (H(.. v) Hww,, v)ll <Col|wr well
Vwi, u2, V-
Moreover, sup (0, r)ll co.
The proof is in Section D.I. For Assumption A2, Theorem 3.2 of Yu [2012] confirms that {Yi} has unique stationary distribution dy. Yu [2012] also computes that
1((w) Ry-dy (we, v)] = Aw +b.
Assumption A3 trivially holds by the definition of W..
For Assumption A4, the key observation is that Al'(w) + always holds because I'()) e W.. Aw b (Aw + b) (AI + b) A(w I(w)). Thus the term
Then we have h(w)) (VL(w), h(w)) can be written (w- [(w))* A(w I(w)). We now prove that for whatever X, always holds that A is n.d. on ker(A))

---

Lemma 7. There exists a constant C O such that for Ve E ker(A)), w Au - -C Furthermore, for any w E Rd, it holds that w - ((w) E ker(A)*
The proof is in Section D.3. We then have
(w2 [(w)) A(we P(w:))) < -Cillw; r(wx)]l
which satisfies Assumption A4. For Assumption A5, (6) verifies Assumption A5(I), Assumption A5(2) is verified by the following lemma.
Lemma 8. There exists a constant Cg such that for Vus, y. H (wr, y)ll s Ca[]] + 1).
The proof in Section D.4, Assumption A5(3) is verified following a similar procedure as Lemma 6.7 in Bertsekas and Tsitsiklis [1996] (Lemma 18). Invoking Theorem 3 then completes the proof. n
5.3 Proof of Theorem 2
Proof. We recall that in view of Lemma 1, ker(Xi) creates "duplication" in value estimation. We, therefore, define the projection matrix IT E Raxd that projects vector into the orthogonal comple- - ||www'l] It can be computed that II X
ment of ker (x) i... Iw = arg mior We now examine the sequence {Ilw}} with {wi, being the iterates of (Average Reward TD) and consider the combined parameter vector W.
Jr
E Rl+d The following lemma characterizes
[1
the evolution of wt Let Yr (Sc, Ac, 01) then
eSxAxSx {o IR ||l|| S
[x(x)
1-A
Lemma 9. W1+1 Wy + ar (A(()))) + b(Y:)), where we have, with (s,a,s',e).
A(y)
CC
Te(x(s') 2())7)
0 ((v) -
cor(s,a) ((ss
Te
This view is inspired Zhang et al. [2021c] and the proof is in Section E.1. We now apply Theorem to }.
The verification of Assumptions Al and A2 is identical to that in Section 5.2 and is thus omitted. Jz
For Assumption A3, we define W. = {
w E W. } It is apparently nonempty, closed, and
Il
convex.
For Assumption A4, we define Ā = Ey A(y) and Ey-dy b(v) and therefore realize
the h in (SA) as h(w)- Aö + b. Noticing that (T + 5 o (Lemma 19), then have (w)) A( (. The term (VL(w), h hwr) can thus be written as (w T(m)) A(w T(w)).
Next, we prove that when Cg is large enough, is n.d. on R x -
Lemma 10. Let ca be sufficiently large. Then there exists constant Cio O such that Vz R x - 2² Az -
The proof Section E.3. By definition, we have Wi E R x ker(Xi)+ and [(w) E IR x ker(Xi)+
So / I(w) e IR ker(X,) yielding
r r( A(ū, I((.))) < -Cilll -
which verifies Assumption A4.
1 O X
For Assumption A5, we define
Assumption A5(1) is verified below.
Lemma 11. There exists a positive constant Cii, such that for any W., || | = Cu

---

The proof is in Section E.4. With H y) A(y) and (3) is similar Lemmas 8 and 18 and thus omitted. Invoking Theorem 3 then yields the convergence rate of E [[(())),, i.e., the convergence rate of d(w W.)² by the definition of L. The next key observation is that dl d(, W.)² = (J, Jn,²² 2 d(w,, W, (Lemma 20), which completes the proof.
ū + b(y). the verification of Assumption A5(2)
Experiments
We now empirically examine linear TD with linearly dependent features. Following the practice of Sutton and Barto [2018], we use diminishing learning rates a₁ r+to and 3r s+ match our Assumption LR with g = and to = 10 We use a variant of Boyan's chain [Boyan, 1999] with 15 states ([S) 15) and 5 actions (IAi 5) under a uniform policy (a|s) = 1/ AA where the feature matrix X E R is designed to be of rank (more details in Section F). 3 The weight convergence to a is indeed observed. It is within expectation that different À requires different a. B.
8 which closely
A=
0=5.5
0=0.9
a.0=2.005
000
0.0=0:055
0.0.001
0.0002
20
0.00.01
y=0.9
d(w.
4
10
2
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
Steps
x10*
Steps
x10*
Steps
x10*
Figure 1: Convergence of (Discounted TD) with 7 = 0.9, oz E (0.005, 0.01). Curves are averaged over 10 runs with shaded regions (too small to be visible) indicating standard errors.
A= 8=0.01
A= 8=0.01
A=0.9, 8=0.01
0.0.01 0.01
am0.01
3-
a- 0.02
0.8
0-0.02
1.6
d(w, W1
0.6
1.4
0.4
1
0-0.01
1.2
0-0.1
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Steps
x10
Steps
x10
Steps
x10
Figure 2: Convergence of (Average Reward TD) with Bn 0.01, on (0.01, 0.02, 0.1). Curves averaged over 10 runs with shaded regions (too small to be visible) indicating standard errors.
7 Conclusion
This paper provides the first finite sample analysis of linear TD with arbitrary features in both discounted and average reward settings, fulfilling the long standing desiderata of Dayan [1992]. Tsitsiklis and Roy [1996. 1999], enabled by a novel stochastic approximation result concerning the convergence rate to set. The key methodology contributions include novel Lyapunov function based on the distance to a set and a novel decomposition of the feature matrix for the average-reward setting. We envision the techniques developed in this work can easily transfer the analyses of other linear RL algorithms. That being said, one limitation of the work is its focus on linear function
'The code for this paper is available https: /tte:::///ttttt htt.aub....oo/eeeene//eeeeeeeeee

---

approximation. Extension to neural networks with neural tangent kernels (cf. Cai et al. [2023]) is a possible future work. Another limitation is that this work considers only L convergence rates but the convergence mode of random variables are versatile. Establishing almost sure convergence rates, I," convergence rates, and high probability concentration bounds (cf. Qian et al. [2024]) also a possible future work. Finally, another promising direction is the integration of Polyak-Ruppert averaging (cf. Patil et al. [2023], Naskar et al. [2024J), which potentially leads to parameter-free convergence rates.
Acknowledgments and Disclosure of Funding
This work is supported in part by the US National Science Foundation under the awards III-2128019, SLES-2331904 and Node under the award VV-1Q26-001, and an Nvidia academic grant program award.
the Commonwealth Cyber Initiative's Central Virginia
References
David Abel, André Barreto, Benjamin Van Roy, Doina Precup. Hado van Hasselt, and Satinder Singh. definition of continual reinforcement leamnig. In Advances in Neural Information Processing Systems, 2023.
Amir Beck. First-order methods in optimization. MOS-SIAM Series on Optimization, 2017.
Richard Bellman. A markovian decision process. Journal of Mathematics and Mechanics, 1957.
Richard Bellman. Dynamic programming. Science, 1966.
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adantive Algorithms and Stochastic Approximations, Springer, 1990.
Dimitri P Bertsekas and John Tsitsiklis. Muuro-Dynamic Programming. Athena Scientific Belmont, MA, 1996.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Proceedings of the Conference on Learning Theory, 2018.
Ethan Blaser and Shangtong Zhang. Asymptotic and finite sample analysis of nonexpansive stochastic approxi- mations with markovian noise. ArXiv Preprint, 2025.
Liu Bo, Liu Ji, Ghavamzadeh Mohammad, Mahadevan Sridhar, and Petrik Marek. Finite-sample analysis of proximal gradient td algorithms. In Proceedings of the Conference on Uncertainty in Artificial Intelligence. 2015.
Vivek Borkar, Shuhang Chen, Adithya Devraj, Joannis Kontoyiannis, and Sean Mcyn. The ode method for asymptotic statistics in stochastic approximation and reinforcement learning. The Annals of Applicd Probability, 2025.
Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint. Springer, 2009.
Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforce- ment learning. STAM Journal on Control and Optimization, 2000.
Justin A. Boyan. squares temporal difference learning. Proceedings of International Conference on Machine Learning, 1999.
Mario Bravo and Roberto Cominetti. Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds. SIAM Journal on Control and Optimization, 2024.
Qi Cai, Zhuoran Yang. Jason D Lee. and Zhaoran Wang. Neural temporal difference and q learning provably converge to global optima. Mathematics of Operations Research, 2023.
Xuyang Chen, Jingliang Duan, Yingbin Liang, and Lin Zhao. Global convergence of two-timescale actor-critic for solving linear quadratic regulator. Proceedings of the AAAI Conference on Artificial Intelligence, 2023a.
Zaiwei Chen. Non- asnmmtttiioiic guarantees for reware lelarnnng with adaptive stepsizes. ArXiv Preprint, 2025.
10

---

Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam, Finite-sample analysis of contractive stochastic upproximation using smooth convex envelopes. In Advances in Neural Information Processing Systems, 2020.
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite-sample analysis of off-policy td-learning generalized hellman operators. In Advances in Neural Information Processing Systems, 2021.
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. A Iyapunov theory for finit-saaplle guarantees of markovian stochastic approximation. Operations Research, 2023b.
Zaiwei Chen, Siva Theja Maguluri, and Martin Zubeldia. Concentration of contractive stochastic approximation: Additive and multiplicative noise. The Annals of Applicd Probability, 2025a.
7aiwei Chen, Sheng Zhang. 7he Zhang, Shaan UI Haque, and Siva Theja Maguluri. A non-asymptotic theory of seminorm аyаршноv stability: From deterministic stochastic iterative algorithms. ArXiv Preprint, 2025b.
Peter Dayan. The convergence of id(A) for general X. Machine Learning, 1992.
Leah M Hackman. Faster gradient-td algorithms. Master's 's thesis, University of Alberta, 2012.
Khimya Khetarpal. Matthew Riemer, Irina Rish, and Doina Precup. Towards continual reinforcement learning: review and perspectives. Journal of Artificial Intelligence Research, 2022.
Harold Kushner and George Yin. Stochastic approximation and recursive algorithms and applications. Springer Science & Business Media, 2003.
Chandrashekar Lakshminarayanan and Csaba Szepesvári. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In Proceedings International Conference on Artificial Intelligence and Statistics, 2018.
Shuze Liu, Shuhang Chen, and Shangtong Zhang. The ODE method for stochastic approximation and reinforce- ment learning with markovian noise. Journal Machine Learning Research, 2025a.
Xinyu Liu, Zixuan Xie, and Shangtong Zhang. Extensions of robbins-siegmund theorem with applications in reinforcement learning. ArXiv Preprint, 2025b.
Xinyu Liu, Zixuan Xic, and Shangtong Zhang. Lincar q-learning does not diverge 12: Convergence rates to a bounded set. In Proceedings of the International Conference on Machine Learning, 2025c.
Yang Long, Zheng Gang. Zhang Yu, Zheng Qian, Pengfei, and Pan Gang. On convergence gradient expected sarsa(A). In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Hamid Reza Maci Gradient lemporal-differeeee differeecce learning algorithms. PhD thesis, University of Alberta, 2011.
Sreeject Maity and Aritra Mitra. Adversarially-rooust td learming with markovian data; Finite-time rates and fundamental limits. ArXiv Preprint, 2025.
Aritra Mitra, A simple finite-time analysis of td learning with linear function approximation. IEEE Transactions on Automatic Control, 2025.
Ankur Naskar, Gugan Thoppe, Abbasali Koochakzadch, and Vijay Gupta. Federated td learning in heterogencous environments with average rewards: A two-timescale approach with polyak- ruppert averaging. In IEEE Conference on Decision and Control, 2024.
Dal Fabbro Nicolò, Adibi Arman, Mitra Aritra, and J. Pappas George. Finite-time analysis of asynchronous multi-agent td learning. ArXiv Preprint, 2024.
Gandhary Patil, Prashanth L. A., Dheeraj Nagaraj. and Doina Precup. Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation. In Proceedings of the International Conference on Artificial Intelligence Statistics, 2023.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Xiaochi Qian and Shangtong Zhang. Revisiting design choice in gradient temporal difference learning. In Proceedings of the International Conference on Learning Representations, 2025.
Xiaochi Qian. Zixuan Xie, Xinyu Liu, and Shangtong Zhang. Almost sure convergence rates and concentration of stochastic approximation and reinforcement learning with markovian noise. ArXiv Preprint, 2024.
11

---

Shuang Qiu, Zhuoran Yang. Jieping Ye, and Zhaoran Wang, On finite-time convergence of actor-critic algorithm. IEEE Journal Selected Areas in Information Theory. 2021.
Mark Bishop Ring. Continual learning in reinforcement environments, PhD thesis, The University of Texas Austin, 1994.
Eugene Seneta. Non-negative matrices and Markov chains. Springer Science Business Media, 2006.
U1 Haque Shaan and Theja Maguluri Siva. Stochastic approximation with unbounded markovian noise: anneral-purpose theorem. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2025.
Rayadurgam Srikant and Lei Ying. Finitc-time error bounds for lincar stochastic approximation andtd learning. In Proceedings of the Conference Learning Theory, 2019.
Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement Leamiin:: An Introduction (2nd Edition). MIT press, 2018.
Richard Sutton, Csaba Szepesvári, and Hamid Reza Maci. A convergent o(n) temporal-din -iffereeeee algorithm for off-policy learning with linear function approximation. Advances Neural Information Processing Systems, 2008
Richard S. Sutton, Hamid Reza Maci, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for approximation. In Proceedings of the International Conference Machine Learning. 2009.
learning with linear function
Ganesh Swetha, Uddin Mondal Washim, and Aggarwal Vaneet. Order-optimal global convergence for average reward reinforcement learning via actor-critic approach. ArXiv Preprint, 2024.
John N. Tsitsiklis and Benjamin Roy. Analysis of -hifrre-difffeeence learning with function approximation. In IEEE Transactions on Automatic Control, 1996.
-ampora-difference John N. Tsitsiklis and Benjamin Van Roy. Average cost temporal difference learning. Automatica, 1999.
Jiuqi Wang and Shangtong Zhang, Almost sure convergence of linear temporal difference learning with arbitrary features. ArXiv Preprint, 2024.
Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. In Advances in Neural Information Processing Systems, 2020.
Tengyu Xu, Zhe Wang, and Yinghin Liang. Improving sample complexity hounds for (natural) actor-critic algorithms. In Advances in Neural Information Processing Systems, 2020a.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Non -on-asympto convergence analysis of two time-scale (natural) actor-critic algorithms. ArXiv Preprint, 2020b.
Tengyu Xu, Zhuoran Yang, Zhaoran Wang, and Yinghin I Liang. Doubly robust off-policy actor-critic: Conver- gence and optimality. In Proceedings of the International Conference on Machine Learning, 2021.
Peng Yang, Jin Kaicheng, Zhang Liangyu, and Zhang Zhihua. Finite sample analysis of distributional td learning with linear function approximation. ArXiv Preprint, 2025.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably glohal convergence of actor-critie: A case for linear quadratic regulator with ergodic cost. In Advances in Neural Information Processing Systems, 2019.
Huizhen Yu. Least squares temporal difference methods: An analysis under general conditions. SIAM Journal on Control and Optimization, 2012.
Huizhen Yu. On convergence of emphatic temporal-diffcee did-fffffffeeeeeee learning. In Proceedines of the Conference on Learning Theory, 2015.
Huizhen Yu. Weak convergence properties of constrained emphatic cemporal-difference and slowly diminishing stepsize. Journal of Machine Learning Research, 2016.
differennc learning with constant
Wang Yue, Zhou Yi, and Zou Shaofeng. Vinite-time error bounds for greedy-gg. gq. Machine Learning, 2024.
12

---

Shangtong Zhang and Shimon Whiteson. Truncated emphatic temporal difference methods for prediction and control. Journal of Machine Learning Research, 2022.
Shangtong Zhang, Bo Liu, and Shimon Whiteson. GradienDICE: Rethinking generalized offine estimation of stationary values. In Proceedings of the International Conference Machine Learning. 2020a.
Shangtong Zhang, Bo Liu, Hengshuai Yao, and Shimon Whiteson. Provably convergent two-timescale off- policy actor-critic with function approximation. In Proceedings of the International Conference on Machine Learning. 2020b.
Shangtong Zhang, Yi Wan, Richard Sutton, and Shimon Whiteson. Average-reward off-policy policy evaluation with function approximation. Proceedings the International Conference on Machine Learning, 2021a.
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking deadly triad with a target network. In Proceedings of the International Conference on Machine Learning, 2021b.
Shangtong Zhang, Remi Tachet, Romain Laroche. Global optimality finile sample analysis softmax off-policy actor critic under state distribution mismatch. Journal of Machine Learning Research, 2022.
Shangtong Zhang, Remi Tachet Des Combes, and Romain Laroche. the convergence of sarsa with linear function approximation. In Proceedings of the International Conference on Machine Learning, 2023.
Sheng Zhang, Zhang, and Siva Theja Maguluri. Finite sample analysis average-reward td learning and q-learning. In Advances in Neural Information Processing Systems, 2021c.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis sarsa with linear function approxima- tion. In Advances in Neural Information Processing Systems, 2019.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction accurately reflect the paper's contributions, establishing novel 2 convergence rates for linear TD(A) with arbitrary features in both discounted and average-reward settings without additional assumptions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The Conclusion section explicitly discusses two limitations of the work:
the focus on linear function approximation, which may not extend directly to non-linear methods like neural networks:
the restriction to L convergence rates, excluding other convergence modes such as almost convergence, IP convergence, high-probability bounds.
These points address the scope of the theoretical results and potential extensions, aligning with NeurIPS guidelines for reflecting on limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well sell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
14

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All main theoretical results (Theorems 1, 2, and 3) presented with their complete proofs in Section 5 and the Appendices B, C, D, E. The necessary assumptions for these results are explicitly stated (e.g., Assumptions 3.1, LR, A1-A5).
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Section 6 describes the experimental setup, and Appendix F provides further details the environment (Boyan's chain variant, state/action space, feature matrix design, reward function, and policy). The specific learning rates used are also mentioned in the figure captions (Figures and 2). This information should be sufficient for others to reproduce the main experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
15

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The paper provides access to the code via footnote in the Experiments section. All experimental settings, including the environment, hyperparameters, and the full feature matrix, are detailed in Sections to ensure reproducibility.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.
www.iissssnoiicoyooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/nips. wwtppcccccc/ccccccccccccccccclct httii//guuiees/oeeuSutntn CCodeeubeeiieeeee wwmiiissioooollo onoiinicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies the experimental setup in Section 6 and F, including the Markov Decision Process, policy, feature matrix, and learning rate schedules.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
16

---

Answer: [Yes]
Justification: The experimental results presented in Figures and 2 show curves that are averaged over 10 independent runs. The captions explicitly state that shaded regions. indicating standard errors, are present, though they are too small to be seen. This provides information about the variability of the results across different runs.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments involve running linear TD(A) under both discounted and average-reward setting for up to 1.5 x 10 steps, averaged over 10 runs. These were conducted on a server with an AMD EPYC 9534 64-Core Processor. Each individual run completed in approximately minute. Memory requirements are negligible. The information is detailed in Section F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https /tt//nnuris.../ cttpss.ccp/uuiie
Answer: [Yes]
Justification: This research on linear TD(X) convergence conforms the NeurIPS Code of Ethics, as we submit anonymized code with instructions to ensure reproducibility. aligning with data-related and artifact accessibility requirements. The theoretical nature of our work.
17

---

tested on synthetic Boyan's 's chain, poses no foreseeable harms (e.g., safety, discrimina- tion, or surveillance risks), and all assumptions (e.g., Assumptions 3.1, LR, A1-A5) are transparently stated, with no human subjects or sensitive data involved. Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper provides foundational theoretical analysis of the linear TD(A) algorithm, focusing on its L convergence rates under relaxed assumptions. As a primarily theoretical contribution to an existing algorithmic framework, it does not introduce new applications or systems with societal impacts that need specific discussion. Any societal impact would be indirect, arising from the broader application of reinforcement learning.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
This paper presents theoretical analysis and does not release any new data, pretrained models, or code that would pose a high risk for misuse. The experiments are based on a standard, well-defined reinforcement learning environment (Boyan's 's chain) and do not involve datasets generative models.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
18

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper focuses theoretical analysis and uses foundational algorithms linear TD(A) and a variant of Boyan's chain [Boyan, 1999] described in prior academic literature. These not external datasets, code packages, pre-trained models that would carry specific licenses. All prior work and conceptual contributions are properly credited through citations.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithhae thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- eepackaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release any assets. The contributions mathematical results and insights into an existing algorithm.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
19

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve any crowdsourcing experiments or research with human subjects. The work is purely theoretical and computational, focusing on the analysis a reinforcement learning algorithm.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve any research with human subjects. Therefore, Institutional Review Board (IRB) approval or equivalent was not required.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMS if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
The methodology, theoretical analysis, and experimental design in this paper do not involve the use of L.LMs. Any LLM usage was limited to aiding in writing, editing, formatting, and did not impact the scientific content originality of the research.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: : http///eerrppeeeeee for what should or should not be described.
20

---

A Auxiliary Lemmas and Notations
Lemma 12 (Discrete Gronwall Inequality, Lemma 8 in Section 11.2 of Borkar [2009]). For non- negative real sequences {Zn, Z 0) and {an: n 2 0} and scalar L 2 0, it holds
Tn+1 C
0 vn = En+1 S (C + mn) exp(L Ei= ai)
Vn.
Lemma (Lemma 11 of Zhang et [2022]). For sufficiently large to, holds that
Tax = Olog(( + 40)), at Ot- = =0 |oog( + (o)
(t
to)
Lemma 13 ensures that there exists some 1 > 0 (depending on (o) such that for 2 holds that / 2 Tas- Also, it ensures that for sufficiently large to. we have at-Toytt1 < 1. Throughout the appendix, always assume to is sufficiently large and 2 E. We will refine (i.e., increase) F along the proof when necessary.
B Proofs in Section
B.1 Proof of Lemma
Proof. Let v; E Rd denote the i-th column of X. Without loss of generity, let the first m columns be linearly independent.
Case 1: When 1 col(X), there must exist m scalars {cr} such that Eis C 1. Apparently, at least one of {c;} must be nonzero. Without loss of generity, let am + 0. We then have
-i=
m
Im
qa;).
Cy
In other words, Im can expressed as linear combination of {I1,..., "21....,2m-1) and 1. Since X has column rank m, and thus further by linear combination of {æ1,-... Im and 1. Let Zj = [Ii...., 2m-1] be the first 1 columns of X and Z₂ = [mm.... .......,, [Td] be the rest. We now know that there exists some C' e R (m (d- (i.e., coefficients of the lienar combination) such that
able express (Jmm+1,-... -.. va by linear combination (.i,.... Tm
Zz C [0m1, 1........ 0,1),
where Om.... Oa are scalars (i.e., "coordinates" along the l-axis), egg., Om 1, This means that we can express X
X 1
+ + 111 ... 8.1
(11)
with 01 = =0 O. Now define
X1 = 22 2IC], X₂ = 10,1....,00 021].
note that 1 & col(Z)). Otherwise, there would exist scalars {d{} such that 5 dx;
Then we get Σm (c: c));; + Cm 0, which is impossible because {ri)a=,,..., are linearly independent. Since col(X,) col( Z1), we then have 1 & col(Xi),
Case 2: When 1 & col(X), we can trivially define X1 = X and X₂ Additionally, we can still further decompose X1
X1
[21 2,C),
(12)
where Z1 now the first m columns of X. Apparently, we still have & col(X1).
Lemma 14. Let Assumption 3.1 hold. Then A= = X,Dx - 1)x, x, D* - -1,11) 1).
Proof. Apply the decomposition shown in Lemma 1, we can get
A = xx) T () X2)
21

---

=X] - - -10- =X, 1)X1,
- 1]
where the last equality holds because (Px 1)1 and 1 [D=(PA 1) d Px d Similarly, for b we can obtain
Jn
b = (Xi + T
-)
1 X
J.
Jr 1)
Dr
1) + X2 Dr 1-x
1->
Jn
Ja
=x,
1) + +
(d (1 \P;)) rx
I-X
1 1-X
=x, (r( 1) + (
Jn
1
d x 1-X X
Jr
1-X
x
Jn
Dr
I-X
Here. the fourth inequality holds because di XP*) (1 X)d which gives d
(L-A)d - - The last inequality holds since Jn d Tx. This completes the proof. n
Lemma 15. Let Assumption 3.1 hold. Then W. nonempry.
Proof. In view of (11) and (12), we have X1 = 1 Z10 Notably, Z1 has full column rank
and 1 & col(Z1). Decompose w = [w] w2)
accordingly and recall (4) and Lemma 14, we can rewrite
Aw + b 0 as
Zi (2,C) D= -
W1
- DT(rx 11x1) - (T 1-A 1211]
-
1)
Z
W2
which thus gives us the following simultaneous equations
+ 1z = - -Z -
- 1)
Da 1)Zm + (Z,C) ((C))DD(PP. (12/::-112i0m -(2i)) Dz 1)x
We now prove the claim by constructing a solution. Choose any W2 E ker CI (e.g., w2 = 0), the equations then become
(PA = -, Dr - 1 C. -
-)),w -C - 11)
Since Z1 is full rank and & Z1, Lemma of Tsitsiklis and Roy [1999] shows Z,T D, - 1)2, is n.d. and thus invertible. Choose w11 - (Px 1)21) -zz (x 11x1 then satisfies the equations. This completes the proof.
Lemma 16. Let Assumption 3.1 hold. Then
W. = [w.} + ker(X1) and (er(X;) = Xw R..
Proof. For any solution W., W.r W., ., according to the definition of W, in (4), we have Aw.+ +5 = and Aw.. + = O. That is (w. - w..) = O. By multiplying (w. - w..)" on both side we can get
(w, - ww)) x D
(w. W.x) 0.
According to the CeroonFrobbnius theorem with Assumption 3.1, v TD - I) = 0 if and only if u cl for some R. Therefore, must have X(w, Wax) = cl for some R. That is. (Xi + (w, W.-) cl. Recall the definition of X2 in (11), we have Xy(w. w..) (0 (w.
(0T(w,
22

---

w. This means (ww,- w.+) = c'1 with c' = c- (w, - -.,.). Since 1 & col(X)),, we must have c' = O. That is, ux W E ker(X1).. Thus, we have established that W, = {w.} + (
Furthermore, if w ker(X1) we have Xw (X1 + X2) (0" w)1. If Xw = cl, we have X1W cl Xyw (c f But & col(X1). So we must have TTw i.c. w E ker( This completes the proof of ker(X;) = { ww/w= cl R.).
C Proofs in Section 5.1
Lemma 17. For sufficiently large lo- there exists a constant C17 such that the following statement holds. For any 2 i and any i [t Tai t). it holds that
Iu Wt We-
Ta - P(w:)ll + 1).
Proof. In this proof, to simplify notations, we define shorthand 1 = Ta, and C2 = max, ||{(s)]]- Given Lemma 13, we can select a sufficiently large to such that for any 2 F,
exp exp(CasC2att-tnnt-11 <3, 1
CAsC2a1- t-1 <
6
We then bound
||e;
weal || as
Iwj - W/, 11 5
lay (wk, Yx+1)ll
asCAs([IXuy Xwe 1| +1
(Assumption A5)
Xx 11) CsCas((XEu== - Xwa,l)
k=h
as CAss +1) Σ
as axCin.(11ux - ww,,l)
k=t
1 + 1xxpp((rnnnaa
(Lemma 12)
where C17,1 = CAsCz. We then have
- |ww-wa,l
CCASa (1 Xw,, [x + 1)exx(Cin,jan,t-1))
<CASC22 exppCrn.dr,.--aa,,.-
we, + exp(Crn.ett.=))((xxl.l + 1)C
1
$ 2 [u wt, + C1 (I|xw, + 1),
where C17,2 = 3CAS. Thus, have
||l, Wi, || <
Xw,l| + +1 < ( - I(w;)]l + 1) + 1)
< - l'(w;)] || + 1),
where C1 = 2Cn,2((C + 1). This completes the proof.
C.1
Proof of Lemma
Proof.
X w = | Nww XT(w) + XT
< X [(w [(w))] + [[T(()]]
< ||ll| [(w)]] + CAs
(Assumption A5)
23

---

C.2
Proof of Lemma 3
Proof. According the definition of (w,, Y)) (10),
[[( 12)
Xwxs + 1)2 (By Assumption A5)
[2C +1)
< 22 I(w))l + 1)2 1)
(2C [(w;)] 1) + 1)
<03(,, r(w)))1 + 1),
where C 222
- 1). This completes the proof.
C.3 Proof of Lemma
Proof. We first decompose (w: - [(we), (w,, Yi) h(wx)) into three components similarly to Srikant and Ying [2019] as
(w - I(w;), (w,, Yi) h(w+))
((w; - [(w))) (Wi-Ta, I( (wi, Yi) h(ww))
T
(Wi-ra: -I(wi-TO,) ) H(we, Yi) H H(Wi- 1e) h h(we-ra,)) h(w)))
T2
+ (Wi-To. - -I(W)-T, H(W Yi) h(wr-To.))
T3
We leverage Lemma 2 and (9) bound them one by one follows.
Bounding Ti:
Ti
(wr [[w))
(we-ra, [(We-T,)))
))|l
(w,, Y)) h(w))l
Th
T12
For the first term, we have
Tn W/ I(w)) - W/-Tai - P(Wl- ml)
W/ W Wi || + [[(w]) I [(Wi-Ta)) ||
2|wus W Wc- (Since W. is convex)
20na to. 1-1 (11wu -(woll 1) (Lemma 17)
For the second term, we have
Ti2 < CAs(I 1 CAs( | 1) - [(ww)] + +1) +)
< 2C
< C - [(wx)l] 1),
where C4,1 2CAs(C2 + 1). Therefore, we can get
Ti s DC1:C,,144-.,,--1 - I(w;)ll + 1)
Choosing C4,a 4C,,,4,,1 then yields the bound
Ti < 1- I(w)]]? + 1).
Bounding Tz:
T2 (Wi-Tal 1' (W Hw,, Yi) H (w Yi) + h(WW h(w)))
< Wi Wit
T( [1) T(W4-T.)))
H(w,, Yi) H H(w Fop Yi) + hehhhwww h(Wi-T,)) h(we))l
T2
T2a
24

---

For the first term, we have:
T21
W1 (Ta T(W)-ra,)) (T(wn) - r(w)))]
Wt-Tor -[(w)) + [(ww)) - [(w)-Ta))) ||
[ r(w=)]l + ||u: -Wi-aal
$ ww: I(w]) Wk-Taa we + ww W1-5a
x
|0: r(w))ll + 2 10 - Wi
|0: r(w+)ll + 1- ((w))) +) (Lemma 17)
C222 w/ r(w)]l + +1). (Lemma 13)
(13)
For the second term, we have:
T22 1 H(w, Yi) H( Y,) + ((((wr)) h M(w
$ 22CAI ( will
(C I(w))ll + 1). (Lemma 17)
(14)
Combine the result in (13) and (14), we have:
T2 S
[(w))l +1))))+))3+.
Choosing C4,6 24,4224,3317 then yield the bound
T2 S C4,600- ( 1(w:)]l2 1).
Bounding T3:
T3 -w: (Wi-To [(We- H (wa- :..::). - h(we-ra))) ))
Take expectation on both sides, we can get
[[ E (wi-ra, l'Wi--ra) (W Yr) 11 (( )
E [Wi-Tar P(Wl (Wi Yi) - h(Wi-Toi }){
Wx- Fare Y
E
(Wi-Tmr T(We-Ta, ), H (Wi-Ta Yi) h h(We-Ta))) )
$
Wi-To I(W)-Ta))) |||
HWW Yi) h h(we-To (a M
Ta
T52
We have
Ta2 Sai( XW +1)
(By (7) and (9))
Sa. Xw XWi-Ta - Xwi + |Xw,, || + 1)
Say ( - Xwi
+ Ca(luu T(w)]l + +1) +
<a. (C17C2a
I(w,)) + + Callur I(w:) 12+1)
S0 - [(w)]] + 1
Thus, together with (13), we obtain
E[Ta] < Cs [(w;)]l + 1),
where C4 = C4,204,4. Finally, denote C4 = C4,a + C4.b + CA,e then completes the proof.
25

---

C.4
Proof of Lemma 5
Proof. We recall that
I|,, - r(w))ll== = 2w:w)).
Aligning Assumption A4, Lemmas 3 and 4 with (8), get
B[L(w++1]]
Ci 2 az + ([,) 5(1 Cxaa))((((u)) + Ca (2 +1+
2
<(1 2Craa + 2C20, + Cra,) C.a C3 0j.
Furthermore, we aim to derive an upper bound for [ww)) that depends on the initial expected loss [[L(w))] and decreases over time. First, let's denote the coefficients as Ct and D₃:
C. = 1 - 20 + 2040)00-T..-- + Cza
C3 2 aq.
D, Caarar 1- +
For sufficiently large to and inequality further becomes:
> 7, obtain 4C40 C3as CA.. Thus, the recursive
E[L(wr+1)] S (1 ((( + De.
where D, = Olara Ter
C.5 Proof of Theorem 3
Proof. To express [[;] in terms of [[[((w)),, we recursively apply the inequality:
t II (1 Caras)) Dj.
B[L(w:)] IIo Caua;) +
Σ
i=
j=ī
#=1+1
Denote E = (1 CMa;))((L(x)) Eg = Ej=
(ITi -Cxass)
In(+tt))
and k
(+le)
CA4Q. Recall we have a₁ (e+to: For Ei, set to > CAia, we have
Casa
II Crao;
[[[[wz)]
(i + to)
i=7
([L(w))]
+ to
i=7
i l0
=E[[(w>)]
+ to
1=7
[x]
8 to f 8 to
<E[T(1>)]
For Ez, we have
i + to -
In(j + to) ( + 10)
E3 =
i 40
j=
i=1+1
[-
+ to - K i to i=j-1
(4)
Σ
i lg -
In[j + (o)
i
==
j=t- [x|+1
i=j+1
26

---

1++++ to
In(j + to) (++1))
In(t + to)
|x|] (1 [5] + 10)
1
j=7
[xj Σ
(t tq)
In(t + tt)
CTmm3.1
(o+to) + |+|]
( + to - -x))
(t ( + to to)2c
j=
Case 1: [x]] -2
In(t + tb)
In(t + to)
E2 v (t to - []][k]]] (1hm3,2(1 - [K]] + (o))ml) -2 + | (1 K + 40)
In(1 + (0)
In(t + (o)
(t -x:)2-1 CThm333 + [K]] (t (t- 1 2o
1n(1+10)
IChhm3,4
(t + to)
Case 2: [K]] - 25 00 0
In(t + to)
In(t + to)
E2 S (1 + 10 xx)x]]
CThm3, |1:| + 11+++ | (t - A 1 + t
In(l + to)
In(1 (g)
(t + to -x)_ CThm3, [x]]
(t - K + to )26
In(t to))+ (t (t) (1++))11)))
SCThm3,6
Starting from the update of W2+1, we have
||wt+ll| || S wwll || + aallHl Y++1)l S weell + a.CAi([wull) + 1).
That is, ||w S CAC + CaoC + 1)]|w]|| ||- Applying discrete Gronwall inequality, we obtain || S (CA1 + [|wal]) exp Ei + ao0xx)) = (CA1 + l|wlll) exp(1 + TooCxi)-
Denoting CThm3,1 exp(2i (2 + 2tao and TThm3,2 Amax(Crrmmsaa CThm3,6) then completes the proof.
D Proofs in Section 5.2
D.1 Proof of Lemma
Proof.
Let y s',a,s',e) E y and C2 = max, |z())]]- We have
[[H(w,v) H(w', v)ll [|(()=((')_ - x(s) ()s) (w w')ll s 2C w'll
Furthermore,
sup H[, sup ||r(s, S max ((s, a)lCa: y
yey
8.8
which completes the proof.
D.2 Proof of Lemma 18
Lemma 18. There exist a constant Cix and [0, 1) such that Yw
(w, Y++n)ly) 1((w)] < Cixt" ([] + 1).
Proof. Given the Markov property, we only need to prove the case of 1. Recall that we use y as, 8', e). Define shorthand
6((s, a, s'), w) =r(s, a) + yr(s') r(s) ww.
27

---

6n+1(w) =ō((Sn, An: Sn+1), w).
By (10), we can get
[w,, Yn+1) =dn+1(w)en
By expanding en, we get
E H wz Yn+1) [i]
E E (orl((w)ee en Xil
( Σ (12))==0(51) x((k)
So
k=0
Now define a two-sided Markov chain {Se, A,) 1,., (s), Pr(A, = a S = 8) = r(lss), i.e,, the new chain always stay in the stationary distribution of the original chain. Similarly, define
2,-10....1110 such that Pr(S,
(m+1(w) 8((Sn, An, Sn+1),
We then have
E
8n+1
W
(7)) - (Sx)
E
(w)
(7 (r1)m~RZ(($A) (S(b)
k=-o0 00
fa(n)
E
8
(w)
(1a) (11)m=>a((
((k)) Soo
EE
Ön+1 (7a))=
k=
k=
11())
E
8n- 1 (w)
Σ (7
f2(n)
In the proof of Lemma 6.7 of Bertsekas and Tsitsiklis [1996], is proved that
fo(n) Aw
which coincides with h(w). Thus the rest of the proof is dedicated to proving that (n and fa decay geometrically. For f2(n), we have (w)()())) & CIs.1(I)Xur + 1) for some C (cf. (16)). We then have
[[2(m)]] SC18, (I +1)
Σ (7A)==
k=-00
=[Is. + +))
(T2)*.
For (n), since (S:) adopts geometric mixing, there exists some E 10, 1) and C1R.2 such that
Σ Pr(SA = 5) Pr Pr(St = s) s C18.277..
Then have
Bi (0)+(()))(SS)(55)) - EE [ (w)x
Σ Pr(SA = =[So)=((5)) E( (w) = ss Σ de (l = =s].
28

---

Noticing that (w)) = =s] = =
S = =] due to the Markov property, we obtain
(1))+ E (w) - CI + 1).
This means
[12(xz)] - ([ +1) Σ (
k=0
Noticing that
n
nmax (,),
k=0
then completes the proof.
D.3
Proof of Lemma
Proof. We start with proving Vw ker(A)+ w Aw -CB||uo]]* This is apparently if O. Now fix any E ker(A)* and * 0. which implies that Aw * O. Now we prove by contradiction that w
T Aw * O. Otherwise, if w Aw = O. we have w X D> - T)Xw: 0. Since (y 7) n.d., we then get X 0, further implying Aw 0, which a contradiction. We have now proved that w Aw o 0. We next prove that Aww 0. This is from the fact that A is n.d., i... for V2 E R 2 Az < 0. But w Aw & O. So we must have w Auw < 0. Finally, we use an extreme theorem argument to complete the proof. Define Z = /w u E ke) ||w||| 1}. Because z E implies z E ker(A)+ and z +f O, we have Vz E Z, Az < Since clearly compact, the extreme value theorem confirms that the function + As obtains its minimum value in Z, denoted as -C; < 0, i.e., we have
Vz 2,= Az -Cr.
(15)
For any E ker(A)+ and +f O, we have proof of the first part.
E Z, w Aw < -C which completes the
We now prove that Vw E Rd, (ww) (e)( We recall that T is the orthogonal projection to W. fw Au + 0}. Since is the orthogonal projection W., we know -[w) W.t. Fix any w. E W. and let E ker(A), we then have A(w, + 2) + b = 0 so w. + E W. We then have
(w -u-rii ((w), 2) = (w I(w), wa + 2) (w I(w), w.) 0 =0,
confirming that r(w) ker(A)+, which completes the proof.
D.4 Proof of Lemma
Proof. Let y (s, a, s E V. since (z(s)Tu) max.es (e(s)Twl w| |Xw]], according (10), we have
(H = [le(r(s,)) + + x(s) w)
(16)
< (l)
+ w
$ CC (1+1))
$ <C([] 1),
where C3 = C. + 1). For [[](w)]], we have
[|h(w)]l = BByddy [(w, y)]l - Egwdy/ (w, v)ll < [s[[[[]]]] + 1);
which completes the proof.
29

---

E Proofs in Section 5.3
E.1 Proof of Lemma 9
Proof. The update { [e] in (Average Reward TD) is
J+t1 = Je at (caRet1-caJ.)) caJi).
This matches the first row of A(Yi) + b(Y))
ccg
0 -lle, [lee(x(S(11 -((((()))--(((TT]
Je
cs CoRe+1 Rotilles
+
[110
Now consider the update for We
W+++ = we + Oz [o+1 - Je + x(S+11) T "e - xxs:) (w)) ex.
Applying the projection matrix II on both sides yields
Tw Mw, =0 IT (( (Re- J₁ + 15 x((e) Twx)) et)
R8+1 - Jc + x((++1) We - -(()) (e llet
(B++1 - J1 + x( 1ww, x(Si) Hur, lle.
To see the last equality, we recall Lemma and recall II = X1 We then have
XIIw =X,Ilw + 10 II0 IIw
=X1 10 II..
This means that
x(s') Iwe =(s)) Iw = x1 (s') - w- x1) w,
where we use x (s) to denote the s-th row of X1. We also have
x(s') w r(s) w =<1 0)
(x(s) + O)T w
-s) (s) w.
which confirms the last equality and then completes the proof.
E.2 Proof of Lemma 19
Lemma 19. Ar(w) + ==0
JT
Proof. According to the definition of T ()), [(w) W. =
W.
We have
[Iw
Ā Ey-dy A(w)
C3
Cg
-lle
-x(s)(
-IE
IIA
b Eyndy blu)
car(s, a) als,
CgJ [IIEddy [e]Jx 11b
(17)
Therefore, for the first row of Är (T) + b. we get cD Jn) 0. For the second row, we can get
-I [e] + NAATo + IT [e] + ITb
[[ATT + 5)
=IT(X, Dr, T)X, [Tw D)
-II(X, D, ----Xx +b)
-II(AW + D)
=0,
where the second equality comes with the definition of II. This completes the proof.
30

---

E.3 Proof of Lemma 10
21
Proof. If 2 = O, the lemma trivially holds. So now let Let 2
E IR x ker(X1) + O. With
[2]
(17), we have
Á IIE of .enddyyyyyyll [e]
Cg
0
cg -IlEdy [e]
0 III; Dz 1)x
(Lemma 14)
IIA
For simplicity, define Edy
[e], B x Dx((P, - 1) We then have
x Az
cg II (1(-921- B22)
= -c + 22 11(-221 + B22).
Recall that
X X1 and is symmetric, we can get 22 11(-q=1- + B22) = (IIz2) (-qz1+ B22) = 23 (-qz1 + B22),
where the last equality holds because 22 E ker (X+). Thus,
T = - - 2 921 + 2,2 B22
We now characterize 22 Bzg. Apparently, 27 B2g S 0 always holds because (x - 1) is n.s.d. In view of (5), the equality holds only if x = el. But & col(X,) and 2/ E ker( (o()x)) So the equality holds only when 22 O. Now we have proved that V22 ker(X))) 22 o 0, holds that 2/2 B2 O. Using the normalization trick and the extreme value theorem again (cf. (15)), confirm that there exists some constant C such that V22 E k=r(X
22 B2g S -C00.1112111
Since * we now discuss two cases.
Case 1: 21 = 0, 22 * O. In this case, we have TĀ = 2 B22 0.
Case 2: 21 + 0. In this case, we have
TÃ =a + 21 y 22 B2g < -c 2 | 22 ||lllll 1 =|
By completing squares, is easy to see that when eg is sufficiently large (depending on || and 1I it holds T Ä= because 31 # O.
Combining both cases, have proved that V2 R x ker(X1) 22 + 0, it holds that
z Az < O.
Using the normalization trick and the extreme value theorem again (cf. (15)) then completes the proof.
E.4 Proof of Lemma 11
Proof. By definition, W. = {
J= Nw
w E W.
In view of Lemma 16, let W. be any fixed vector
[w
in W Then any w. E W. can be written as
Jr [T wo)
W.
with some wo ke)(X1). We then have
Jx XII(W. (., wo)
Jm
Xw.
XIlw
where the last equality holds because II is the orthogonal projection to - This means that X Yw, is constant regardless of w., which completes the proof.
31

---

E,5
Proof of Lemma 20
Lemma 20. (Je - J=)² + d(w,, .)2 d( W.)
Proof. We recall that II is the orthogonal projection to ker( Let II' be the orthogonal projection to (er(X1). We recall from Lemma 16 that W. = {w.. + ker(X1) with ve, being any fixed point in W. Thus for any w. E W., we can write it as w. + wo with some wo E ker(X1). Then for any
w E RRd, we have
d(w, W.)²
inf W.W. ||w0 woll
inf wocker(X)))
|| W. woll
inf woEker(X.)
[1l + 11'w
11 1l' -woll
inf (X)
IIl
Ilw
+ [I''
II' wol |
ITw - Iw,,1²
where the last equality holds because select wo W'' Nw.. Define IIW - [Ilw| W.). Then we have
d(Hle, IW.) = inf
|[[ - Nw.ll
w.eW.
inf
|Te N( + wo)l
mX
[[w Ilw,lI.
where the last equality holds because wi E (er(Xi) i and II is the projection to ker(X,)+ so Illo We now have Vus, d(w, W.) = d(Iww, IW, .). Then we have
d(w,, W.)
=(h, -z)² + d (1, IIW.Y
(J. -J=)² + d(ITu, IIW.) )
=(h+ J=)² 2 d(w,, W.)
which completes the proof.
F Details of Experiments
We use a variant Boyan's chain [Boyan, 1999] with 15 states (8o, 81,...,814)) 814) and 5 actions (ao...., ..., a4). The chain has deterministic transitions. For 82...., 814, the action goes to 8;-1 and the actions aj to 04 go to 8;-2; $1 always transitions to Sp; Sp transitions uniformly randomly to any state. The reward function is
r(s, a) {1
if == 80
otherwise
32

---

We use a uniform random policy <(als) = 0.5.
The feature matrix X E IR 16x5
is designed to be of
rank 3.
00.07
0.11
0.18
0.14
0.617
0.13
0.19
0.32
0.26
0.45
0.11
0.17
0.28
0.22
0.39
0.24
0.36
0.60
0.48
0.84
0.18
0.28
0.46
0.36
1.00
0.20
0.30
0.50
0.40
1.06
0.31
0.47
0.78
0.62
1.45
X
0.29
0.45
0.74
0.58
1.39
0.42
0.64
1.06
0.84
1.84
0.40
0.62
1.02
0.80
1.78
0.47
0.73
1.20
0.94
2.39
0.53
0.81
1.34
1.06
2.23
0.58
0.9
1.48
1.16
2.78
0.60
0.92
1.52
1,20
2.84
0.67
1.03
1.70
1.34
3.45
Each experiment runs for 1.5 10t steps, averaged over 10 runs. These experiments were
ducted on a server equipped with an AMD EPYC 9534 64-Core Processor, with each run taking approximately minute to complete. Memory requirements negligible.
33


Reviews:
[{"review_id": "2WUHunpLtJ", "reviewer": "Reviewer_6BhZ", "summary": "This paper focuses on linear TD($\\lambda$) and establishes its convergence rates with arbitrary features, for both the discounted and average reward setting.", "questions": "- Please discuss the obtained convergence rates in light of the literature (if they were expected or not, for example, and how they differ);\n- Please discuss the tightness of the obtained bounds;\n- Please clarify the intent of the experiment and how it connects with the results.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The result is novel and addresses a gap in the literature. The paper is also clear and sound. \n\nThe paper would benefit from having more interpretation on the results obtained. Theorems 1 and 2 show the inequalities but: there is no discussion on whether the rates are expected or not; there is no comparison with other rates in the literature for similar problems (independent features, for example); there is no discussion on the tightness of the obtained bounds. Finally, the experimental results are not particularly insightful: there is no connection with the theoretical results on the plots; what are the experiments showcasing? Simply that the algorithm converges? Was that not already established in the literature by Wang and Zhang?", "was_revised": true, "final_justification": "The authors answered my questions satisfactorily and they will include them in the paper. I believe that strengthens the paper significantly and therefore I increased my score.", "rebuttal": "Thanks for the thoughtful questions. We provide responses below and will include all the clarification in revision. \n\n> Please discuss the obtained convergence rates in light of the literature\n\nThe convergence rate of linear TD with linearly independent features has been previously studied. In particular, Bhandari et al. (2018) established a rate of $\\mathcal{O}(1/\\sqrt{T})$ for a constant step-size $\\alpha_t = \\frac{1}{\\sqrt{T}}$ and a faster $\\mathcal{O}(1/t)$ rate for a decaying step-size $\\alpha_t \\propto 1/t$. Srikant and Ying (2019) provided an $\\mathcal{O}(1/T)$ rate for the constant step-size setting. Our work focuses on the decaying step-size case, providing a rate of $\\mathcal{O}(1/t^{\\min(2\\xi-1, \\lfloor\\kappa_1\\rfloor-1)})$ for $\\alpha_t \\propto \\alpha/t^\\xi$, where $\\xi \\in (0.5, 1]$.\n\nSince $\\kappa_1$ is proportional to the step-size coefficient $\\alpha$ ($\\kappa_1=\\alpha C_7$, see Appendix C.5), by choosing a sufficiently large $\\alpha$, we can ensure $\\lfloor\\kappa_1\\rfloor - 1 \\ge 2\\xi - 1$, meaning the convergence rate is determined by the exponent $2\\xi - 1$. Therefore, for the standard choice of $\\xi=1$, our rate becomes $\\mathcal{O}(1/t)$. This result matches the best-known rate for TD with decaying step-sizes and aligns with the standard rate for Stochastic Gradient Descent (SGD). This indicates that relaxing the linear independence assumption does not hurt the convergence rate.\n\nRef:\n\nJ. Bhandari, et al. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, 2018.\n\nR. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, 2019.\n\n> Please discuss the tightness of the obtained bounds\n\nAdmittedly, we did not prove the tightness of our bounds. But as discussed above, our rate matches the best-known rate for TD and the standard rate for SGD (the optimal $\\mathcal{O}(1/t)$ rate of SGD for strongly convex problems under standard assumptions), despite our relaxed assumptions.Furthermore, Kane (2023) highlights the exponential hardness of RL with linear function approximation, supporting the significance of our polynomial rates as a state-of-the-art benchmark.\n\nRef: \n\nD. Kane, et al. Exponential hardness of reinforcement learning with linear function approximation. In Conference on Learning Theory, 2023.\n\n> Please clarify the intent of the experiment and how it connects with the results.\n\nOur experiments serve two key purposes.\n\nFirst, they provide the first empirical verification for linear TD($\\lambda$) with dependent features, a gap left by recent theoretical work (cf. Wang & Zhang (2024)). Our experiments fill this critical gap by demonstrating empirical convergence in both discounted and average-reward settings using linearly dependent features. As noted by Sutton and Barto (2018, p. 282), Emphatic TD’s “variance on Baird’s counterexample is so high that consistent experimental results are nearly unattainable,” although ETD's theoretical convergence has been well established. So we believe it is important to verify that linear TD with linearly dependent features does converge empirically.\n\nSecond, our plots offer a novel perspective by visualizing convergence to a solution set ($d(w_t, W^*)$), rather than a single point. This directly illustrates the behavior predicted by our theory for the arbitrary feature case and showcases the algorithm's stability via small standard errors.\n\nTo further strengthen the paper, we will add experiments with decaying step-sizes to match our theory. We choose to use constant step size in the current version mostly to better align with practices. There is no difficulty in extending our analysis to constant step size. In particular, once we have the recursion in Lemma 5, the convergence rate with a constant step size can be easily established using standard techniques (cf. Chen et al. (2021)). \n\nRef:\n\nR. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.\n\nZ. Chen et al. A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants. arXiv preprint, 2021."}, {"review_id": "iMxtHAlnZl", "reviewer": "Reviewer_9yVY", "summary": "This paper studies finite sample bounds for TD($\\lambda$) with linear function approximation where the feature matrix is not made up of linearly independent columns. First, this paper derives bounds for a general stochastic approximation algorithm where the limit is set-valued. Thereafter, it uses this result to get finite sample bounds for policy evaluation using TD($\\lambda$) in the exponential and average-reward scenarios. Later, this work provides simulations in synthetic settings to demonstrate the validity of the theoretical results.", "questions": "Please address the weaknesses pointed out above. Additionally, answer the following questions: \n\n1. Do you think your analysis will carry over if Polyak-Ruppert averaging is additionally used? If yes, then please elaborate.\n2. Do you think your analysis will carry over to (tabular) Q-learning?\n3. How do you think your work advances the current state of the art? In particular, there have been several works that question the performance of Q-learning algorithms with function approximation. For instance, see \n    - Patterson, A., Neumann, S., White, M. and White, A., 2024. Empirical design in reinforcement learning. Journal of Machine Learning Research, 25(318), pp.1-63.\n    - K. Young and R. S. Sutton, “Understanding the pathologies of approximate policy evaluation when combined with greedification in reinforcement learning,” arXiv preprint arXiv:2010.15268, 2020.\n    - Gopalan, A. and Thoppe, G., 2022. Does DQN learn?. arXiv preprint arXiv:2205.13617.'\n    \n    To me, it feels like the work, while interesting, does not really address the key issues confronting the field. Nevertheless, I believe the stochastic approximation convergence to a set-valued map is interesting (in its own right). Hence, I vote for borderline accept.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. Extremely well-written paper.\n2. Gets rid of one restrictive assumption (of the feature matrix being linearly independent). Moreover, despite the solution set being set-valued, the value function estimate remains the same! Also, the algorithm need not change in any way!\n\n**Weaknesses:**\n\n1. *Lack of Optimality:* From the main results, it is unclear for what step sizes one gets the optimal convergence rate. \n\n2. *Parameter-dependent optimal step sizes:* From existing literature, it is known that the optimal convergence rate for such bounds is obtained for step sizes of the form $c/(t + 1),$ where $c$ depends on unknown problem parameters. This work continues to carry forward this limitation, while existing works have already suggested techniques to overcome them using Polyak-Ruppert averaging, e.g., see\n     \n     - G. Patil, L. Prashanth, D. Nagaraj, and D. Precup, “Finite time analysis of temporal difference learning with linear function  approximation: Tail averaging and regularisation,” in International Conference on Artificial Intelligence and Statistics, pp. 5438–5448, PMLR, 2023.\n\n     - Naskar, A., Thoppe, G., Koochakzadeh, A. and Gupta, V., 2024, December. Federated TD Learning in Heterogeneous Environments with Average Rewards: A Two-timescale Approach with Polyak-Ruppert Averaging. In 2024 IEEE 63rd Conference on Decision and Control (CDC) (pp. 387-393). IEEE.", "was_revised": true, "final_justification": "This paper studies linear TD learning with arbitrary features, relaxing the common assumption of linear independence in the feature matrix. The paper is very well-written, which is a key reason I have assigned it an above-average score.\n\nHowever, the broader RL literature continues to face a significant gap between theory and practice. This work does not make substantial progress toward bridging that gap, which is why I have not rated it more highly.", "rebuttal": "Thanks for the thoughtful questions. We provide responses below and will include all the clarification in revision. \n\n> Lack of optimality.\n\nThank you for this point. The convergence rate of linear TD with linearly independent features has been previously studied. In particular, Bhandari et al. (2018) established a rate of $\\mathcal{O}(1/\\sqrt{T})$ for a constant step-size $\\alpha_t = \\frac{1}{\\sqrt{T}}$ and a faster $\\mathcal{O}(1/t)$ rate for a decaying step-size $\\alpha_t \\propto 1/t$. Srikant and Ying (2019) provided an $\\mathcal{O}(1/T)$ rate for the constant step-size setting. Our work focuses on the decaying step-size case, providing a rate of $\\mathcal{O}(1/t^{\\min(2\\xi-1, \\lfloor\\kappa_1\\rfloor-1)})$ for $\\alpha_t \\propto \\alpha/t^\\xi$, where $\\xi \\in (0.5, 1]$.\n\nSince $\\kappa_1$ is proportional to the step-size coefficient $\\alpha$ ($\\kappa_1=\\alpha C_7$, see Appendix C.5), by choosing a sufficiently large $\\alpha$, we can ensure $\\lfloor\\kappa_1\\rfloor - 1 \\ge 2\\xi - 1$, meaning the convergence rate is determined by the exponent $2\\xi - 1$. Therefore, for the standard choice of $\\xi=1$, our rate becomes $\\mathcal{O}(1/t)$. This result matches the best-known rate for TD with decaying step-sizes and aligns with the standard rate for Stochastic Gradient Descent (SGD). This indicates that relaxing the linear independence assumption does not hurt the convergence rate. While the question of strict optimality remains open (Kane, 2023), our rate establishes a strong benchmark for state-of-the-art performance in this setting.\n\nRef: \n\nJ. Bhandari, et al. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, 2018.\n\nR. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, 2019.\n\nD. Kane, et al. Exponential hardness of reinforcement learning with linear function approximation. In Conference on Learning Theory, 2023.\n\n\n> Weakness of parameter-dependent optimal step sizes and whether your analysis will carry over if Polyak-Ruppert averaging is additionally used.\n\nThank you for these insightful questions. We agree that incorporating Polyak-Ruppert averaging is a promising path to achieving parameter-free rates, and we believe the techniques from the cited works (Patil et al. (2023); Naskar et al. (2024)) are applicable to our setting. In the current manuscript, due to page limits, we focus on establishing the first $L^2$ rates for this general setting to clearly present our core contribution. We are grateful for this excellent suggestion and will add a discussion on this promising direction in our revision, acknowledging your valuable pointer.\n\n> Do you think your analysis will carry over to (tabular) Q-learning?\n\nThank you for this question. Our work focuses on the challenge of linearly dependent features, which does not arise in standard tabular $Q$-learning due to its full-rank (e.g., one-hot) representations. \n\nThe more relevant extension is to linear $Q$-learning, where our methodology shows significant potential. Recent breakthroughs establish that linear $Q$-learning iterates converge to a bounded set (cf. Meyn (2024); Liu (2025)), rather than to a single point. This makes our techniques for analyzing convergence to a solution set directly applicable to the problem.\n\nHowever, our approach alone is not sufficient. The key challenge is the `max` operator in the $Q$-learning update, which breaks the crucial (semi-)contraction properties leveraged in our on-policy analysis. Therefore, a full analysis of linear $Q$-learning would require combining our set-valued convergence tools with new methods designed to handle the non-linear dynamics introduced by the `max` operator.\n\nRef:\n\nS. Meyn. The Projected Bellman Equation in  Reinforcement Learning. IEEE Transactions on Automatic Control, 2024.\n\nX. Liu, et al. Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set. International Conference on Machine Learning, 2025.\n\n> How do you think your work advances the current state of the art? \n\nThank you for this crucial question. Our primary contribution lies in policy evaluation, where we establish the first $L^2$ convergence rates for linear TD($\\lambda$) with arbitrary features. This strengthens a fundamental building block of RL, as reliable policy evaluation with provable convergence properties is a prerequisite for effective control in algorithms like policy iteration and actor-critic.\n\nThe important papers you cited (Patterson (2024); Young and Sutton (2020); Gopalan and Thoppe (2022)) highlight critical challenges in control that arise from the interaction with function approximation. We view these as vital research opportunities. A rigorous understanding of the evaluation component, which our work provides, is a necessary first step to formally analyze and address the instabilities they discuss.\n\nWe will expand our discussion in the revised manuscript to better connect our foundational results to these important control-focused challenges. Thank you for the valuable pointers."}, {"review_id": "HTShmXu5IQ", "reviewer": "Reviewer_qPpb", "summary": "This paper studies the theoretical properties of linear TD(λ), a fundamental reinforcement learning algorithm for policy evaluation. Most prior finite-sample analyses assumed the features used for value function approximation are linearly independent, a strong assumption often violated in practice. This work removes the linear independence assumption and establishes the first L2 convergence rates for linear TD(λ) with arbitrary features, in both discounted and average-reward settings. The main technical innovation is a novel stochastic approximation result, using a Lyapunov function based on the distance to the solution set, which enables convergence analysis even when the solution is not unique. The results require no algorithmic modification and are achieved under standard Markovian assumptions and learning rate schedules.", "questions": "- The paper \"Two-Timescale Networks for Nonlinear Value Function Approximation\" (Chung et al., ICLR 2019) [1] includes a convergence analysis for gradient TD(λ) with nonlinear value function approximation and arbitrary features. Would the authors consider clarifying how their results complement or differ from this line of research?\n- Could you discuss the implications of your results for nonlinear function approximation, and whether your techniques might extend to that setting?\n- Could the authors provide more discussion on the practical implications of their results, such as guidance for feature selection, learning rate tuning, or diagnosing convergence in real-world applications?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The paper resolves a long-standing open problem by removing the linear independence assumption and proving finite-sample convergence rates for linear TD(λ) with arbitrary features, significantly broadening the theoretical foundation for TD learning.\n- Analyzing convergence to a solution set via a distance-based Lyapunov function is elegant and general, and may inspire further advances in RL theory.\n- The results apply to both discounted and average-reward settings, and the analysis is unified and clearly presented.\n- The work is carefully contextualized with respect to prior literature, including Wang & Zhang [2024], and provides a detailed comparison (Table 1) to highlight its novelty.\n- The paper is well written, with clear motivation, rigorous proofs, and strong theoretical contributions.\n\n## Weaknesses\n\n- While the paper establishes the first finite-sample convergence rates for linear TD(λ) with arbitrary features, it is important to note that similar finite-sample convergence results have been proven for gradient TD(λ) algorithms with nonlinear value function approximation (see Chung et al., ICLR 2019) [1]. They also **do not assume linear independence (Section 4 Point 2)**. Although the algorithms and technical settings differ, this related work demonstrates that convergence guarantees are possible even in more general, nonlinear settings.\n- The analysis is limited to on-policy linear TD(λ) and does not address off-policy learning or nonlinear function approximation, which are important in modern RL applications.\n\n[1] Chung, W., Nath, S., Joseph, A. G., & White, M. (2019). Two-Timescale Networks for Nonlinear Value Function Approximation. International Conference on Learning Representations (ICLR) 2019.", "was_revised": true, "final_justification": "Great paper, and the authors addressed all my concerns.", "rebuttal": "Thanks for the thoughtful questions. We provide responses below and will include all the clarification in revision. \n\n> Could you clarify how your results for standard TD($\\lambda$) complement or differ from the convergence analysis of gradient TD($\\lambda$) in Chung et al. (2019), which also handles arbitrary features, even though it is in a nonlinear setting?\n\nThank you for this excellent question. While both Chung et al. (2019) and our work consider arbitrary features, they are fundamentally distinct.\n\nFirst, their analysis provides an asymptotic result with a weaker convergence notion (`liminf`), whereas we establish explicit $L^2$ rates. They show convergence to a set of asymptotically stable equilibria without characterizing this set or proving its existence, a significant challenge in itself (cf. Wang and Zhang (2024)). In contrast, our work proves the non-emptiness of the solution set and provides rates of convergence to this well-defined set. Additionally, their algorithm requires a projection operator, while our analysis applies to the unmodified TD($\\lambda$).\n\nThe second core distinction is that GTD is a stochastic gradient descent (SGD) method on the Mean-Squared Bellman Error, allowing it to leverage standard optimization theory. In contrast, TD($\\lambda$) is a semi-gradient method. Its expected update is not the gradient of any objective function, making its analysis fundamentally more challenging. We provide stronger guarantees for this classic algorithm by addressing analytical challenges absent in the more structured GTD framework.\n\n\n> Given that the analysis is limited to the linear on-policy setting, what are the implications of your results for nonlinear function approximation, and could your techniques be extended to that more general setting?\n\nThank you for this forward-looking question. Our methodology is directly applicable to the off-policy setting, requiring only the standard adaptation of incorporating importance sampling ratios into the analysis. \n\nAn extension to nonlinear function approximation is also possible via the Neural Tangent Kernel framework (cf. Cai (2019)). This path linearizes a sufficiently wide neural network, and recasts the TD update as a linear recursion within a high-dimensional feature space (an RKHS). In principle, our finite-sample $L^2$ analysis could then be applied.\n\nHowever, a direct application faces several technical challenges. For instance, rigorously bounding the spectrum of the kernel matrix under Markovian data and managing the computational overhead of kernel methods (e.g., using random features as in Rahimi and Recht (2008)) would require significant analytical extensions to account for new error terms and sampling complexities. A full treatment of these issues is beyond this paper's scope, but we believe our work provides a solid foundation for this exciting future research direction.\n\nRef: \n\nQ. Cai, et al. Neural temporal-difference learning converges to global optima. In NeurIPS, 2019.\n\nA. Rahimi and B. Recht. Random features for large-scale kernel machines. In NeurIPS, 2008.\n\n\n\n> Could you provide more discussion on the practical implications of your results, such as guidance on feature selection, learning rate tuning, or diagnosing convergence?\n\nWe appreciate this important practical question. Our theory offers direct guidance for practitioners. For feature selection, our analysis removes the strict requirement of linear independence, freeing practitioners to use correlated features, which is especially valuable in dynamic settings like continual learning. For learning rate tuning, our results support a step-size of the form $\\alpha_t = \\alpha / (t+t_0)^\\xi$, suggesting an effective starting point with $\\xi \\in (0.5, 1]$ (e.g., closer to 1 for faster convergence) and then tuning $\\alpha$ and $t_0$ for performance. Crucially, for diagnosing convergence, our theory advises monitoring the value estimate $Xw_t / (\\mathbf{1}^\\top Xw_t)$ for convergence to a unique solution, rather than the potentially drifting weight vector $w_t$. We will incorporate this guidance into the revised manuscript to highlight its utility."}, {"review_id": "AbekHQBx68", "reviewer": "Reviewer_KJgY", "summary": "This paper is a theoretical study of the convergence guarantee of TD($\\lambda$) under linear approximation. In particular, the paper provides a finite sample analysis and the analysis does not require the linear independence of features, which is a property assumed by many previous papers. The paper is technical heavy and I was not able to check the entire proofs with many details left to the appendix. It is proved that both the value function estimate and the linear weight converge to the desired target in an L2 sense while the rate of convergence is problem dependent. Such results are established in both discounted and average reward settings. Moreover, the authors also extend the results to stochastic approximation.\n\nThe authors also did numerical experiments in a simple MDP environment to validate their results.", "questions": "- For the linear independence assumption, it seems that we can always expand the state space by at most $d$ null states (with no reward effect) and define feature values on them to make the expanded features linearly independent. And then we can simply apply the results from previous papers with the linear independence assumption. I guess this approach may have some conflicts with the irreducible assumption of the MDP. I would like to know if the authors have thought of this approach and why it is technically not doable. An alternative approach is to simply remove enough features until the remaining features are linearly independent.\n- In terms of the rate of convergence, in addition to my concern mentioned in the weakness part (that the upper bound may not go to zero as t goes to infinity), I am wondering if the constants $C_{thm1}$ and $\\kappa_1$ are absolute constants, in other words, if they depend on other constants like $|S|$ and $d$.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n- solid theoretical improvement from previous results: This paper is a followup study of Wang and Zhang 2024, which provides asymptotic convergence results under the same setting. And the current paper provides finite convergence sample analysis.\n- generality of the results: the paper studies both the discounted and average reward settings, as well as the stochastic approximation.\n\nWeakness:\n- motivation of the linearly dependent features: In the case of large scale problems, we usually have $|S|\\gg d$, especially when the states are embedded in a high-dimensional space. Therefore, it seems that the linear independence of features holds almost surely if the features are randomly generated, which is the case for neural networks (considering the local linearization like NTK).\n- rate of convergence: In Theorem 1, the leading term of the upper bound has the order $-\\text{min}(2\\xi-1, \\lfloor \\kappa_1 \\rfloor -1)$. Considering that $\\xi$ is chosen in the learning rate setup and could be as large as 1, the best order is $\\lfloor \\kappa_1 \\rfloor -1$. However, $\\kappa_1$ is only guaranteed to be greater than 1. In the case that $\\lfloor \\kappa_1 \\rfloor -1=0$, the upper bound seems to provide no information. (Please correct me if my understanding of the theorem is wrong.)\n- experiments setup: The theoretical analysis is based on diminishing learning rate and the decay speed plays a key role in the analysis. However the experiments use constant learning rates.", "was_revised": true, "final_justification": "Since the authors provided detailed modification of the theorems/proof and experiment results, I have changed my score to acceptance. I hope that the authors will add them to the revised version as promised.", "rebuttal": "Thanks for the thoughtful questions. We provide responses below and will include all the clarification in revision. \n\n> Motivation of the linearly dependent features.\n\nThank you for raising this sharp point. You are correct that in certain theoretical regimes, such as with infinite state spaces, features generated by a wide network can be linearly independent (Cai et al., 2019). However, in finite state-space settings (e.g., Atari games or Go game), the feature dimension $d$ of a modern wide network (in particular, very wide networks used in NTK literature) can easily exceed the number of states $|S|$. By basic linear algebra, this immediately implies that the feature vectors corresponding to the state space must be linearly dependent.\n\nMoreover, even when the feature dimension $d$ does not exceed $|S|$, the learning process itself often induces strong correlations among features, as they adapt to the data and task. In fact, the challenge of handling linearly dependent features from learned representations was a key technical motivation for the analysis in Chung et al. (2019). Their work underscores that addressing this issue is a practical necessity.\n\nThus, our work provides crucial guarantees for a prevalent and often unavoidable scenario in modern reinforcement learning.\n\nRef: \n\nChung, W. et al. Two-Timescale Networks for Nonlinear Value Function Approximation. ICLR, 2019.\n\n\n\n>  The experiments use constant learning rates while the theory uses diminishing ones.\n\nThank you for noting this discrepancy. We used constant learning rates as they are common in empirical studies. We agree that aligning our experiments with our theory is important and will add a new set of experiments with diminishing learning rates in the revision. Additionally, we will add a discussion showing that once we have the recursion in Lemma 5, our theoretical framework can be readily extended to the constant step-size setting (akin to Chen et al., 2021), demonstrating its broad applicability. \n\nRef:\n\nZ. Chen et al. A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants. arXiv preprint, 2021.\n\n> For the linear independence assumption, why not expand the state space or remove features to enforce it?\n\nThank you for these creative suggestions. We have considered similar approaches, but they introduce significant technical challenges that prevent their straightforward application.\n\nYour idea of expanding the state space to enforce linear independence is intriguing. However, adding \"null states\" would likely break the irreducibility of the underlying Markov chain (Assumption 3.1), as these new states may not be reachable from the original set, or vice-versa. This would invalidate key parts of all previous analyses that rely on the mixing properties derived from a single, irreducible chain. If we modify the transition function to make them reachable, it would alter the stationary distribution and the effect of discounting, thereby changing the value function of existing states. \n\nAlternatively, removing features to achieve linear independence is often impractical. This approach requires simultaneous access to all states, which becomes challenging in continual learning settings or prohibitively expensive with large state spaces. Such modifications present significant computational and data accessibility barriers in real-world applications.\n\nRef: \n\nJ. N. Tsitsiklis and B. Van Roy, Average cost temporal-difference learning. Proceedings of the 36th IEEE Conference on Decision and Control, 1997, pp. 498-502.\n\n> In terms of the rate of convergence ... they depend on other constants like $|S|$ and $d$.\n\nThank you for your careful reading of our theorem and for these important questions. Indeed, for the bound to guarantee convergence to zero, the exponent $\\min(2\\xi - 1, \\lfloor \\kappa_1\\rfloor - 1)$ must be positive. Our result holds for any $\\xi \\in (0.5,1]$, so $2\\xi-1>0$. Since $\\kappa_1$ is proportional to the step-size coefficient $\\alpha$ ($\\kappa_1=\\alpha C_7$, see Appendix C.5, and we recall that we use $\\alpha_t = \\alpha / t^\\xi$), by choosing a sufficiently large $\\alpha$, we can ensure $\\lfloor\\kappa_1\\rfloor - 1 \\ge 2\\xi - 1$, meaning the convergence rate is determined by the exponent $2\\xi - 1$. We will revise the theorem statement to clarify these conditions and eliminate ambiguity.\n\nTo place our result in context, prior work on linear Temporal Difference (TD) learning has established key benchmarks. Bhandari et al. (2018) reported a rate of $\\mathcal{O}(1/\\sqrt{T})$ for a constant step-size $\\alpha_t = 1/\\sqrt{T}$ and a faster $\\mathcal{O}(1/t)$ rate for a decaying step-size $\\alpha_t \\propto 1/t$, while Srikant and Ying (2019) achieved $\\mathcal{O}(1/T)$ for constant step-sizes. Our work, focusing on decaying step-sizes, derives a rate of $\\mathcal{O}(1/t^{2\\xi - 1})$ for $\\alpha_t \\propto \\alpha/t^\\xi$, where $\\xi \\in (0.5, 1]$ and $\\alpha$ is sufficiently large. For $\\xi = 1$, our $\\mathcal{O}(1/t)$ rate matches the best-known rate for TD with decaying step-sizes and aligns with the standard convergence rate of Stochastic Gradient Descent (SGD). This demonstrates that relaxing the linear independence assumption does not compromise performance. \n\nFor the two constants, $\\kappa_1$ would depend on the specific $A=X^\\top D_\\pi(\\gamma P_\\lambda -I) X$; $C_\\text{thm1}$ relates to $\\alpha_0, C_x, C_e$, and $\\bar t$. Both constants depend on the state space size $|S|$ and the dimension $d$. Such dependencies on problem parameters like $|S|$ and $d$ are standard in the analysis of linear TD (Srikant and Ying (2019); Mitra (2025)).\n\nRef: \n\nJ. Bhandari, et al. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, 2018.\n\nR. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, 2019.\n\nAritra Mitra. A simple finite-time analysis of td learning with linear function approximation. IEEE Transactions on Automatic Control, 2025."}]

Author rebuttal:

Meta-review: The work is technically solid and addresses a real gap since linear independence often fails in practice with modern neural networks. The authors develop novel techniques for analyzing convergence to solution sets and show their rates match existing benchmarks despite relaxed assumptions.

All reviewers found the contribution valuable. Initial concerns about presentation and experiments were well-addressed in rebuttals, with authors committing to add diminishing learning rate experiments and clarify rate interpretations in revision.

While somewhat incremental (building on Wang & Zhang 2024's asymptotic results), the finite-sample analysis required non-trivial innovations and provides useful theoretical foundations for this fundamental RL algorithm.
Decision: Accept (poster)