Revisiting a Design Choice in Gradient Temporal Difference Learning
Authors: Xiaochi Qian
Shangtong Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: gradient temporal difference learning
Primary area: reinforcement learning

Abstract: Off-policy learning enables a reinforcement learning (RL) agent to reason counterfactually about policies that are not executed and is one of the most important ideas in RL. It, however, can lead to instability when combined with function approximation and bootstrapping, two arguably indispensable ingredients for large-scale reinforcement learning. This is the notorious deadly triad. The seminal work Sutton et al. (2008) pioneers Gradient Temporal Difference learning (GTD) as the first solution to the deadly triad, which has enjoyed massive success thereafter. During the derivation of GTD, some intermediate algorithm, called $A^\top$TD, was invented but soon deemed inferior. In this paper, we revisit this $A^\top$TD and prove that a variant of $A^\top$TD, called $A_t^\top$TD, is also an effective solution to the deadly triad. Furthermore, this $A_t^\top$TD only needs one set of parameters and one learning rate. By contrast, GTD has two sets of parameters and two learning rates, making it hard to tune in practice.  We provide asymptotic analysis for $A^\top_t$TD and finite sample analysis for a variant of $A^\top_t$TD that additionally involves a projection operator. The convergence rate of this variant is on par with the canonical on-policy temporal difference learning.

Published as a conference paper at ICLR 2025
REVISITING A DESIGN CHOICE IN GRADIENT TEMPORAL DIFFERENCE LEARNING
Xiaochi Qian
Shangtong Zhang Department of Computer Science University of Virginia
Department of Computer Science University of Oxford x xiaochi. joe. qi an@ i com
shangtoong@iirg in a. edu
ABSTRACT
Off-policy learning enables reinforcement learning (RL) agent to reason coun- terfactually about policies that are not executed and is one of the most important ideas in RL. It, however, can lead to instability when combined with function ap- proximation and bootstrapping, two arguably indispensable ingredients for large- scale reinforcement learning. This is the notorious deadly triad. The seminal work Sutton et al. (2008) pioneers Gradient Temporal Difference learning (GTD) as the first solution to the deadly triad, which has enjoyed massive success thereafter. During the derivation of GTD, some intermediate algorithm, called A TD, was invented but soon deemed inferior. In this paper, revisit this A TD and prove that a variant of A TD, called A, TD, is also an effective solution to the deadly triad. Furthermore, this A, 'TD only needs rate. By contrast, GTD has two sets of parameters and two learning rates, making it hard to tune in practice. We provide asymptotic analysis for A, TD and finite sample analysis for variant of A, TD that additionally involves a projection op- erator. The convergence rate of this variant is on par with the canonical on-policy temporal difference learning.
of parameters and one learning
INTRODUCTION
Off off-policy learning (Watkins, 1989; Precup et al., 2000; Maei, 2011; Sutton et al., 2016; Li, 2019) is arguably one of the most important ideas in reinforcement learning (RL, Sutton & Barto (2018), 8)). Different from on-policy learning (Sutton, 1988), where an RL agent learns quantities of interest of policy by executing the policy itself, off-policy RL agent learns quantities of interest of a policy by executing a different policy. This flexibility offers additional safety (Dulac-Arol) et al., 2019) and data efficiency (Lin, 1992; Sutton et al., 2011).
Off-policy learning, however, can lead to instability if combined with function approximation and bootstrapping, two other arguably indispensable techniques for any large-scale RL applications. The idea of function approximation (Sutton, 1988) is to represent quantities of interest with parameter- ized functions instead of look-up tables. The idea of bootstrapping (Sutton, 1988) is construct update targets for an estimator by using the estimator itself recursively. This instability resulting from off-policy learning, function approximation, and bootstrapping is called the deadly triad (Baird, 1995; Sutton & Barto, 2018; Zhang, 2022).
The seminal work Sutton et al. (2008) pioneers the first solution to the deadly triad, called Gradient Temporal Difference learning (GTD). Thereafter, GTD has been massively studied and enjoyed cel- ebrated success (Sutton al., 2008: 2009; Maei et al., 2009; Maei & Sutton, 2010; Maei al., 2010; Maei, 2011; Mahadevan et al., 201 4; Liu et al., 2015; Du et al., 2017; Wang et al., 2017; Yu, 2017; Xu al., 2019; Wang Zou, 2020; Wai et al., 2020; Ghiassian et al., 2020; Zhang et al., 2021a)- During the derivation of GTD in Sutton et al. (2008), an intermediate algorithm called A TD was invented but soon deemed inferior. In Sutton et al. (2008), it is said that "although we find this algorithm interesting, we do not consider it further here because it requires O(K2) memory and computation per time step". Here, K refers to the feature dimension linear function approxima- tion. In this paper, propose a variant of A TD. called A, TD, which has OKK) computation per step, and the memory cost is OKK In? f). Here, refers to the time step. Admittedly, In² diverges

---

Published as a conference paper at ICLR 2025
to eventually. However, argue that this memory cost is negligible in any empirical implemen- tations. For example, our universe has an age of around 14 billion years. Consider a modern GHz CPU. Suppose that RL agent runs 1 step every CPU clock and starts from the very beginning of our universe. Then until now it roughly has run T = 14 x 10 x 3. 1536 x 10" x 3 x 109 xs 1027 steps. We then have In T = 4000. In light of this, we claim that A TD does not have any real drawback in terms of memory compared with GTD. A, TD,, however, has only and one learning rate. By contrast, GTD has two sets of parameters and two learning rates, making it hard to tune in practice (Sutton et al., 2008). We prove that A, TD eventually converges to the same solution as GTD. We also demonstrate that if an additional projection operator is used, A, TD also enjoys the same convergence rate as the canonical on on-policy TD. The assumptions our analysis are all standard.
of parameters
2 BACKGROUND
In this paper, all vectors are columns. We use ||.|| to denote the E vector and matrix norm. We use functions and vectors interchangeably when it does not confuse. For example, if f is function from S to R, also use f to denote vector in R (1), whose s-th element is f()..
We consider an infinite horizon Markov Decision Process (MDP, Puterman (2014)) with a finite state space S, finite action space A, reward function
S x A + R. transition function p: SS x S x .A + [0, 1], and a discount factor y E [0, 1). At time step 0, a state So is sampled from some initial distribution po- At time step f, agent state S, takes an action A, ~ (-1Sst). Here t A x S + [0. 1] is the policy being followed. A reward R241 = r(,,, A,) is then emitted, and a successor state Sc+1 sampled from p(-|S,, At).
The return at time step / is defined as G. -0=07" 7' which allows us to define the state value function as (s) = Ex Ge|S s]. The value function us is the unique fixed point of the Bellman operator Ta = To + +Pp0. Here rr E RS is the reward vector induced by n, defined (s) = E. ((lss)r(s,)) Pr E RiSiiisl is the transition matrix induced by n, i.e. a))
(=( = E.
Estimating Ur is one of the most important tasks in RL and is called policy evaluation. Linear function approximation is commonly used for policy evaluation (Sutton, 1988). Consider a feature function x S + = that maps a state s K-dimensional feature x(s). We then use x(s) w to approximate 2x (s). Here w R.K is the learnable weight. Let X R|si*K be the feature matrix, whose s-th row is r(s) The goal is then to adapt w such that Xw = Uz. Linear TD (Sutton, 1988) updates w iteratively as
W1+1 = we 04 (Re+1 + 1 xz wx) Z4-
Here, we use Ia = ((.)) as shorthand. Under mild conditions, the iterates {wr} in (1) converge almost surely (Tsitsiklis Roy. 1996).
It is commonly the case that we want to estimate without actually sampling actions from æ due to various concerns, e.g., safety (Dulac-Arnold et al., 2019), data efficiency (Lin, 1992; Sutton al., 2011). Off-policy learning makes this possible. In particular, instead of sampling A, according T (-]S:), off-policy method samples A, according to another policy μ. Here, the policy π is called the target policy and the policy μ is called the behavior policy. For the rest of the paper, we always consider the off policy setting. i.c.,
A, p (S)).. Re+1 = r(Sr, Ar), S ~ p(11St, At).
Since the behavior policy μ is diffferent from the target policy π, importance sampling ratio used to account for this discrepancy, which defined as p(s, a) a(a a) In particular, we use as shorthand
s(a
P: = p( A.). Off-policy linear TD then updates iteratively
Wi+1 = wi + auPt (Re+1 + 7 Wi x, wx) xz.
(3)
It is well-known (Sutton et al., 2008) that if off-policy linear TD converged, it would converge to w, satisfying
Aw. b 0,
(4)
2

---

Published as a conference paper at ICLR 2025
where
A A Dx - b= X D
(5)
Here, du is the stationary distribution of the Markov chain induced by the behavior policy μ4, and D a diagonal matrix with the diagonal being d,. Unfortunately, the possible divergence of off-policy linear TD in (3) is well documented (Baird, 1995; Sutton et al., 2016; Sutton & Barto, 2018). This divergence exercises the deadly triad.
Instead of using off-policy linear TD in (3) to find W., one natural approach for policy evaluation in the off-policy setting is then solve Aw b directly, probably with stochastic gradient descent on the objective L(w) = ||_Aw + bll The on-policy version of this objective (i.e., with μ x) is first introduced in Yao & Liu (2008) to derive preconditioned TD. The off-policy version considered in this paper first used by Sutton et al. (2008) to derive GTD, and this objective called the norm of the expected TD update (NEU) in Sutton et al. (2009). The gradient of I(w) can be easily computed as ((w) = 2A (Aw + b). One can, therefore, update w as
Wh+1 = w. a,A (Aw, - b).
Since do not know A and b, we need estimate A AT(Aw, b) with samples. The idea of A TDD in Sutton et al. (2008) is to estimate as
A
~
1 e-l
=2)
and to estimate Aw, as
Aw, + b 2 Po (Ret1 + 7 1w - xx we)xx.
As said in Sutton al. (2008), A TD is "essentially conventional TD(0) prefixed by an estimate of the matrix T. Apparently, computing and store this estimate of A requires OK*)) computation and memory per step, if we use moving average implementation. And it is unclear whether this A TD is convergent. Having deemed this A TDD inferior, Sutton et al. (2008) rewrite the gradient as
V((w) A (Aw b) A Dr (Tx(xw) Xw)
and use a secondary weight / E R to approximate X Dn (Xa) - Xw), yielding the follow- ing well-known GTD algorithm
R + 70 Wt It Wt:
M(1 = + a₁ (pidgTi 14).
u++1 ww, + axpi - 72++1)
(GTD)
The convergence and finite sample analysis of GTD is well established (Sutton et al., 2008; 2009; Liu et al., 2015; Wang et al., 2017; Yu, 2017).
3 TD REVISITING THE DESIGN CHOICE OF A TDD
In this paper, refine the idea of TDD via estimating AT with single sample time t+ ft) as
AT x Pt+S()) (#++50) 77++1(1+)) (045
where f:N + N is an increasing gap function. This yields the following novel algorithm:
å - RR+1 + y w: x Wt.
Wr+1 -w; asPt+(() (1++)(1) (1++(()+) oT. Prdza..
(A) TD)
We call it A, TD to highlight that it uses a single sample to estimate AT, In (A) TD), the term Pe (R41 + , - 2r, wx) is a scalar, the computational complexity of which only O (K). we compute the remaining term (I++5()) - (+0++(0++) =1+/10) computational complexity is still O (K). In other words, the computational complexity of (A, TATTD)
from right to left, the
3

---

Published as a conference paper at ICLR 2025
is the same as (GTD). The price pay here is that we cannot start (4) TD) until the (f(0) + 1) step, and we need to maintain a memory storing
It. Pt, 2t+ Pt+1, IT()), PS()) ((0)+++
The size of this memory is O (f()). We will soon prove that the memory can be as small as (t)). We argue that this memory overhead is negligible in any empirical implementations. The gain is that we now do not need an additional weight vector, making the algorithm easy to use. We will have a few assumptions on the gap function f shortly to facilitate the theoretical analysis. But one example could simply be
f(I) - (t+ 1)J,
where [:] is the floor function. In other words, the choice of the gap function is simple and does not depend on any unknown problem structure. To understand how this gap function works, we consider case where ft) Ovt.. Then we essentially estimating A' and Aw; + with the same sample (ma, Re+1, T++1)- We will then for sure run into the well-known double sampling issue'. By using the gap function, we use the sample time t f(t) to estimate A and the sample time & to estimate Aw; + b. Despite that those two samples are still correlated due to the Markovian nature of the data stream (2), the increasing f(t) gradually reduces the correlation. The theoretical analysis in the following two sections confirms that such a simple gap function is enough to guarantee the desired convergence to w, with a desired convergence rate.
We do note that throughout the paper we consider the canonical RL setting where only Markovian samples are available. If instead i..d. samples are available, addressing the aforementioned doubling sampling issue then becomes more straightforward - one can simply use two independent samples to estimate A and Aw, + A TD with i.i.d. samples are thoroughly investigated in Yao (2023) and we refer the reader to Yao (2023) for more details.
4 ASYMPTOTIC CONVERGENCE ANALYSIS OF A TD TD
In this section, we provide an asymptotic convergence analysis of (ATTD).
TD). The major techni- cal challenge lies in the increasing gap function. If f(t) was constant function, say [(t) = lo- then one could start analyzing (A, TD) via constructing an augmented Markov chain with states Y, = {Se, Ac.... ......... Setto Actto S1+to+1.. evolving in finite space (S x A))o+t S. Sup- pose the origin Markov chain {Sr} is ergodic, this new chain {Y,} would also be ergodic, match- ing the ergodicity assumption of classical convergence results (e.g.. Proposition 4.7 of Bertsekas & Tsitsiklis (1996)). When f(t) is increasing, the augmented chain, however, is now Y = As. , AL+s(D); ((+/(0+1) which evolves in an infinite space U._ (S x A) x S. Even if the original chain {S.} is ergodic, the new chain {Yi} still behaves poorly in that never visits the same augmented state twice. This rules out the possibility of applying most, if not all, ex- isting convergence results in the stochastic approximation community (e.g., Benveniste et al. (1990); Kushner & Yin (2003); Borkar (2009); Liu et al. (2025)). To proceed, we instead use the skeleton iterates technique introduced by Qian et al. (2024). The key idea of this skeleton iterates technique is to divide the non non-negative real axis into intervals of length {Tm)) } and examine the updates interval by interval. Importantly, we will require this {Tm} to diminish, in a rate coordinated with the gap function ft) and the learning rate Oz,
Besides the skeleton iterates technique, another important ingredient is the mixing of joint state distributions in Markov chains. Consider general Markov chain (Yi). Assume the chain is ergodic and let dy denote its invariant distribution. Then the convergence theorem (see, e.g., Levin & Peres (2017)) yields .o Pr(Y.- v) dy(v). This convergence is uniform in y and is geometrically
is well well-known that in general [| + E[X]E[Y].
2 We note that when f(t) = to. another key assumption does not hold. To see this, let A. - pers(y
x2)" If ft) = to. the expected updates would be governed by -B [T A. However, this expectation is not equal to -A due to the correlation between Áctoo and A.. So this expectation is unlikely to be negative definite. But canonical results typically require this expectation to be negative define. To summarize, if f(t) fo, the ergodicity assumption the Markov chain in the canonical results can be fulfilled but the negative definiteness of the expected update matrix cannot he fulfilled.
4

---

Published as a conference paper at ICLR 2025
fast. Exploiting this convergence, able to prove the convergence of joint state distributions, i..,
lim Pr(y; = y, to = =dy(ddd()))))) 100
Intuitively, this means the dependence between Y, and Ye+ diminishes as t goes to infinity (cf. Lemma 7.1 in Vempala (2005)). In (A, TD), this means the bias resulting from the correlation of the two samples time + f(t) and time diminishes gradually. Having introduced the two main technical ingredients in our analysis, we are now ready to formally describe our main results. We start with (standard) assumptions we make.
Assumption The Markov chain induced by the behavior policy μ is finite, irreducible, and aperiodic. And covers i.e., V(s, a), T(als) 0 p(als) 0.
Assumption 4.2 The feature matrix X has a full column rank. The matrix A defined in (5) is nonsingular.
Assumptions 4.1 and 4.2 are standard in the analysis of linear TD methods (see, e.g., Tsitsiklis & Roy (1996); Wang et al. (2017)).
Co Assumption 4.3 The learning rates { have the form of a It-tp, for some E (3: 1].
Assumption 4.3 considers learning rates of a specific form. This is mostly for ease of presentation.
Assumption 4,4 The gap function ft) N + N is increasing and satisfies V/X E [0, 1), Ei=o < co. Moreover, there exist constants 7 E (0, 3v-2) and C+ > O such that Vt, (t) <
2v
C,a
Assumption 4.4 is the most "unnatural" assumption make and prescribes how the gap function should be chosen. Intuitively, those conditions prevent the gap function from growing too fast. Despite seemingly complicated, Lemma 15 in the appendix confirms that simply setting
ft) [h(t) In(t 1)]
(10)
with any non-negative increasing function h(t) converging as + fulfills the first condition of Assumption 4.4. Here [x] is the floor function denoting the largest integer smaller than x. A concrete example satisfying Assumption 4.3 and 4.4 is
=1, h(t) In(t 1), ftt |In (1), 0.1.
(11)
We now ready present our main results.
Theorem Let Assumptions 4.1, 4.2, 4.3, & 4.4 hold. Then the iterates {wi} generated by (AT TD) satisfies
lim w. w. a.s. 1000
where We is the TD TD fixed point defined in (4).
Proof Following Qian et al. (2024), we define a sequence m
Tme (n+1)m+11nn
16 m)
(12)
where C. is defined in Assumption 4.3 and v is some constant such that
(13)
2
Here и and т are defined Assumption 4.3 and 4.4 respectively. Notably, despite that we follow the skeleton iterates technique in Qian et al. (2024), our analysis is more challenging than Qian et al. (2024) in that they only need to coordinate {T,,) } with the learning rate a, but we need to coordinate {T..) with both the learning rate oa and the gap function f()). As result, Qian al. (2024)

---

Published as a conference paper at ICLR 2025
only require 7 E (2 2_x) but we further require 17 2(1-r) which significantly complicates the analysis.
We now follow Qian et al. (2024) and divide the real line into intervals with approximate length {Tm). To this end, define sequence {fm} to = 0, at Tm }. 0, 1, tm+1 = min { k: EE= k-1
(14)
For simplicity, define
Om
2t=6
Oz, m = 0,1,
Now, the real line has been divided into intervals of lengths {āmm m= The following properties of this segmentation will be used repeatedly.
Lemma 2 For all m 2 and 2 lmm we have On S T
The proof is provided in Section C.I.
Lemma For all m 2 O, we have Om S 2T
The proof is provided in Section C.2. We do note that the above two lemmas analogous to Lemmas 1 & 2 of Qian et al. (2024) but the analysis is more challenging due to the requirement of 7 > 2[1-) Following Qian al. (2024), we now investigate the iterates {w,} interval by interval.
Telescoping (A7 (D) yields
Wtm+1 Whm Ei=t Em=+i- 04( A (45)) A.w; AT s(1
(15)
where we have used shorthand À. = pert (00001144111 vz) and by = p 1. For of presenta- tion, we define for all m >> 0,
Qm Wr, A
(16)
Then, our goal is to show that }qm} converges to O. Plugging in (16) into (15) yields
4m++1 9m + E/ 1t=lm
ar(
A (1t500) Aew, -AT be)
= 9m + E Emmtt-1
1m+1-1
az -Ap+ Ac (w. + A- - AT+1() (br A.A-1b)
= 9m + 91.m + 92.m + 93.m + 91,m
where
1m arl 1a(--A A Aqm) = Am AAqm
91,m
1=tm
Σ
1m+1-1
AT A - E [ATrs(O)Ail3 A 1) am
92.m
Ott L=tm
tm++1-1 tm
a.E
Alts(n) (b.- A(A-11)) [F (mm+)())))
Σ
1m+1-1
ai E A AelF
AT Alts qm
9a,m
m=lm
Ei=t
ar
E
[ (b, (AA-1) FF, FF.m+ [((m)))))))))))))))))m)))))))(
AJ - A:A--)-
1m=1-1 1t=m
A4 [9m - (wi + A-1b)]
91.m
Here F, denotes the o-algebra until time t, i.c., F, = o (Wo, So, Ao...., A4-1, St). We use the following lemmas to bound each term above. In Qian et al. (2024), they do not have terms like f(t) (cf. f(t) 0). As a result, their w++1 is adapted to Fe. But in analysis, due to the dependence on Fee) Wi+1 is not adapted to F, and is only adapted to F++s(t)- This greatly complicates the analysis, and we will repeatedly use Lemma 14 to address this challenge. Moreover, Assumption 4.2 implies that the matrix T A is positive definite. i.c., there exists a constant such that for all w,
T A Aw 2 3||
(17)
This 3 plays key role in the following bounds. The finiteness of the MDP and Assumptions 4.1 4.2 ensure the existence constant H < oc such that
{||A,
6. ||A]]. |bbll A SH. H.
sup, max

---

Published as a conference paper at ICLR 2025
Lemma If e 2T HI² S 2, then for all t such that tm St tm+ have
|| (we + A- - 8T H1 (11 1).
The proof is provided in Section C.3.
Lemma 5 2f2H S 3, then ll + 91.m 11 S 3Tm )lqm
The proof is provided in Section C.4. Lemma m S 1, then
l192.ll S Im
1211- (H + (c, L(fx)) +x) (1 + 1),
where L(Sx)) Ei=ox x 100, Cr is defined in Assumption 4.4, and C's is defined in Lemma 14. Notably, L(S,) is fimite due to Assumption 4.4.
The proof is provided in Section C.5.
Lemma
|93.ml| ||
8T Hl 1) and E [9s.m F Fim f(ttm) O.
The proof is provided in Section C.6.
Lemma 8 If 2T H² 2, then I94,mll S ( +).
The proof provided in Section C.7. Putting all the bounds together, the following lemma shows that the sequence
[m ll m20 is supermartingale sequence.
ln(2) 2H
Lemma Tm S min
thenn there exists a scalar D such that
2H
E 11m+till 11 smm)) ((
< ( (1-3Tm, 3Tm DT DT2(I-))
-7) |1qm 112 DT (
where is defined in Assumption 4.4, In particular, when DT BT. have
E 112 S (1- I|gmll² + 27-2117)
(18)
The proof is provided in Section C.8. The supermartingale convergence theorem can then take over show the convergence of {gm
Lemma limm |/gm|l a.s.
The proof is provided Section C.9. With all the established lemmas, we can draw our final conclusion using Lemma 4. Since both Tn and qm converges to 0 almost surely, the difference between Wi + - and gm converges to almost surely. As a result, we can conclude that (w, A-1b) =_...... converges 0, i.e. {wi} converges to -A- almost surely, which com- pletes the proof.
FINITE SAMPLE ANALYSIS OF A, TD
Theorem proves the asymptotic convergence (A, TD). The price we pay memory of size (In² t) (cf. (9)). If the convergence is fast, e.g., O (2). the memory increases reasonably slowly, and argue that the memory overhead is acceptable. If. however, the convergence is too slow, the memory may still become too large. To make sure that (4, TD) a practical algorithm, therefore, requires performing finite sample analysis. To this end, we, in this section, provide finite sample

---

Published as a conference paper at ICLR 2025
analysis of a variant of (A!'D), which adopts additional projection operator and updates {w;} iteratively as
6. = Re+1 + +004 - Jz. we
(19)
W++1 = wr + asPet(() (1++10) - (0++100+11 Fet (e s(0)
where .IRK R.K is a projection operator onto ball of a radius The update (19) dif- fers from (D) only in that it adopts an additional projection operator T. We, therefore, call it Projected A, TD. We show that the convergence rate of our Projected A, TD is on par with the con- vergence rate of the canonical on-policy linear TD in Bhandari et al. (2018), up to few logarithm terms. Notably, adding a projection operator a common practice in finite sample analysis of TD algorithms (see, e.g., Liu al. (2015); Wang et al. (2017); Bhandari et al. 22018); Zou et al. (2019)) to simplify the presentation. Techniques from Srikant & Ying (2019) can indeed be used to perform finite sample analysis of the original (A, TD). This, however, complicates the presentation, and we, therefore, leave it for future work. We now present our main results.
Il & B. Consider learning rates in the form of Co Let Assumptions 4.1, 4.2, & 4.4 hold. Then there exists a constant Co such that as long as Ca 2 Co. the iterates {wi} generated by Projected Direct GTD (19) satisfy
Theorem 11 Let B be large enough such that ||
ag ++1'
[ - w. w[]]]]
((())
TE
The proof of Theorem 11 is provided in Section A. Theorem 11, together with (10), confirms that the convergence rate of Projected A, TD reasonably fast. particular, the configuration in (11) is used, the convergence rate of Projected A, TD is on-par with the on-policy linear TD (Bhandari et al., 2018) up to logarithmic factors.
TD
EXPERIMENTS
Boyan's chain
Baird's counterexample
33-
GTD2
GTD2
Vraae
Vtrece
22
HTD
HTD
TRC
TACC
Aj ID. nt) = [log' (t+ 11 200)
Aj 10. nc) [log' [t+ 11 100]
RMSSPBE
RMSPBE
324
Steps
Steps
Figure 1: Comparison of (A, TD) with previous TD algorithms. All curves are averaged over 10 random seeds with shaded regions showing standard errors. The curves of Vtrace and HTD are invisible in Boyan's 's chain because they reduce to TD in the on-policy setting. The curves of Vtrace, HTD, and TD are almost invisible in Baird's counterexample because they diverge very quickly.
We now empirically compare (A, TDD with a few other TD algorithms with linear function approx- imation, including (naive) off-policy TD, GTD2 (Sutton et al., 2009), TDC (Sutton et al., 2009), Vtrace (Espeholt et al., 2018), HTD (White & White, 2016), and TDRC (Ghiassian et al., 2020). Those baselines also used in Ghiassian et al. (2020). We consider two benchmark tasks, Boyan's chain (Boyan, 2002) and Baird's counterexample (Baird, 1995), which are also used Ghiassian al. (2020). Notably, Boyan's chain is on-policy problem while Baird's counterexample is an
8

---

Published as a conference paper at ICLR 2025
off off-policy problem. Following Ghiassian et al. (2020), report the square root of the mean squared projected Bellman error (RMSPBE) at each time step. We base our implementation on the open- sourced implementation from Ghiassian et al. (2020). So refer the reader Ghiassian et al. (2020) for details of the baselines and the tasks, as well as the exact definition of RMSPBE. For each algorithm, tune its learning rate in {2-20- ..... 22-1,,,, 1} and report the results with the best learning rate (in terms of minimizing RMSPBE at the last step). As can be seen in Figure 1, in the on-policy setting, (A/TD) TD) outperforms both GTD2 and TDC in terms of the final performance. In the off- off-policy setting, (A, TD) remains convergent and achieves the same final performance as GTD2, TDC, and TDRC.
Boyan's
Baird's counterexample
((() |log(t+ 1) 100]
f(r) = [log(t++ (++++))))))))
23-
((() llog' (t + 100
ftt) |log" [)++1)+11
f(t)= llog (t+ + 100
ftt) |log* +1]
RMSPBE
RMSPBE
Steps
Steps
with different gap functions. All curves are averaged over 10 random seeds with shaded regions showing standard errors.
Figure 2:
We also investigate different choices of the gap function. As be seen in Figure 2, when we set the gap function to f(t) Olog t). which does not respect Assumption 4.4, (ATTD) remains convergent and achieves a similar performance. This suggests that Assumption 4.4 might be overly conservative. Pushing Assumption 4.4 to its limit and finding the slowest gap function is an interesting and rewarding future work. We conjecture that certain knowledge of the transition function of the MDP can be incorporated into the design of the gap function, the gap function can be greatly slowed down.
7 RELATED WORK
It is worth mentioning that the memory in A, AT is conceptually different from the buffer for expe- rience replay (Lin, 1992; Mnih et al., 2015), though both store previous transitions. A replay buffer typically used to sample mini-batch data randomly. But A, TD only deterministically uses the first and the last entries in the memory.
Instead of minimizing NEU, Feng al. (2019) propose minimize a kernel loss based the Bellman error (cf. Baird (1995)). In the Markovian setting we consider in this paper, Feng et al. (2019) develop gradient estimator of this kernel loss. This gradient estimator is consistent as the size of the replay buffer grows to infinity. However, other than the consistency, no convergence analysis is provided. Indeed, as demonstrated in Section 4, analyzing the almost sure convergence of such algorithms is extremely challenging, and no standard stochastic approximation tools apply. We conjecture that our new analysis techniques Section 4 could further help build an almost sure convergence of their algorithms under certain kernels with some moderate regularization.
GTD is one of the many possible methods to address the deadly triad issue. Other methods include emphatic TD methods (Mahmood al., 2015; Sutton et al., 2016; Hallak et al., 2016; Zhang & Whiteson, 2022; He et al., 2023), target networks (Zhang et al., 202 lb; Fellows et al., 2023; Che al., 2024), and density ratio methods (Hallak & Mannor, 2017; Liu et al., 2018 8; Nachum al.,

---

Published as a conference paper at ICLR 2025
2019: Zhang et al., 2020). We refer the reader to Ghiassian & Sutton (2021); Ghiassian et al. (2024) for more thorough empirical study of off off-ic prediction algorithms.
CONCLUSION
In this paper, we revisit the derivation of the seminal GTD algorithm. We demonstrate that the idea behind the A TD algorithm can lead to a new off-policy policy evaluation algorithm A TT that as competitive as GTD terms of both asymptotic convergence, convergence rate, and per-step computation cost. A, TD does incur additional memory cost, which we argue is negligible in any empirical implementations. The main advantage of A, TD over GTD is that has only one set of parameters and one learning rate. It is well documented that the two learning rates in GTD are hard to tune in many empirical problems. As said in Sutton et al. (2008), "we are still exploring different ways of setting the step-size parameters" (of GTD). It is worth noting again that the main contribution of this work is the rediscovery of the A TDD idea, leading to the A, TD algorithm. That being said, the empirical study in this work is only preliminary and leave empirical study for future work.
thorough
ACKNOWLEDGEMENTS
This work is supported in part by the US National Science Foundation (NSF) under grants III- 2128019 and SLES-2331904.
REFERENCES
Leemon C. Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings the International Conference on Machine Learning. 1995.
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive Algorithms and Stochastic Ap- proximations. 1990.
Dimitri P Bertsekas and John N Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific Bel- mont, MA, 1996.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learn- ing with linear function approximation. In Proceedings of the Conference on Learning Theory, 2018.
Vivek S Borkar. Stochastic approximation: dynamical systems viewpoint. Springer, 2009.
Justin A Boyan. Technical update: Least-squares temporal difference learning. Machine learning, 2002.
Fengdi Che, Chenjun Xiao, Jincheng Mei, Bo Dai, Ramki Gummadi, Oscar A Ramirez, Christo- pher K Harris, A Rupam Mahmood, and Dale Schuurmans. Target networks and over- parameterization stabilize off-policy bootstrapping with function approximation, ArXiv Preprint, 2024.
Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduc- tion methods for policy evaluation. In Proceedings of the International Conference on Machine Learning. 2017.
Gabriel Dulac-Amold, Daniel Mankowitz, and Todd Hester. Challenges of real-world reinforcement learning. ArXiv Preprint, 2019.
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: scalable distributed deep-rl with importance weighted actor-learner architectures. In Proceedings of the International Conference on Machine Learning, 2018.
Mattie Fellows, Matthew JA Smith, and Shimon Whiteson. Why target networks stabilise temporal difference methods. In Proceedings of the International Conference Machine Learning, 2023.
10

---

Published as a conference paper at ICLR 2025
Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the bellman equation. In Advances in Neural Information Processing Systems, 2019.
Sina Ghiassian and Richard S Sutton. An empirical comparison of off-policy prediction learning algorithms in the four rooms environment. ArXiv Preprint, 2021.
Sina Ghiassian, Andrew Patterson, Shivam Garg, Dhawal Gupta, Adam White, and Martha White. Gradient temporal-different learning with regularized corrections. In Proceedings of the Inter- national Conference on Machine Learning, 2020.
Sina Ghiassian, Banafsheh Rafiee, and Richard S Sutton. Off-policy prediction learning: An empir- ical study of online algorithms. IEEE Transactions Neural Networks and Learning Systems, 2024.
Assaf Hallak and Shie Mannor. Consistent on-line off-policy evaluation. In Proceedings of the International Conference on Machine Learning, 2017.
Assaf Hallak, Aviv Tamar, Rémi Munos, and Shie Mannor. Generalized emphatic temporal dif- ference learning: Birs-variance analysis. In Proceedings of the AAAI Conference Artificial Intelligence, 2016.
Jiamin He, Fengdi Che, Yi Wan, and A Rupam Mahmood. Loosely consistent emphatic temporal- difference learning. In Uncertainty in Artificial Intelligence, 2023.
Harold Kushner and G George Yin. Stochastic upproximation and recursive algorithms and appli- cations. Springer Science & Business Media, 2003.
David A Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Soc., 2017.
Lihong Li. A perspective on off-policy evaluation in reinforcement learning. Frontiers of Computer Science, 2019.
Long Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching- Machine Learming. 1992.
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient TD algorithms. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2015.
Qiang Liu, Lihong Li. Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. In Advances in Neural Information Processing Systems, 2018.
Shuze Liu, Shuhang Chen, and Shangtong Zhang. The ODE method for stochastic approximation and reinforcement learning with markovian noise. Journal of Machine Learning Research, 2025.
Hamid Reza Maei. Gradient Alberta, 2011.
learning algorithms. PhD thesis, University of
Hamid Reza Maei and Richard S Sutton. Gq (lambda); general gradient algorithm for temporal- difference prediction learning with eligibility traces. In Proceedings of the Conference on Artifi- cial General Intelligence, 2010.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard S. Sutton. Convergent temporal-difference learning with arbitrary smooth function ap- proximation. In Advances in Neural Information Processing Systems, 2009.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S. Sutton. Toward off off-po learning control with function approximation. In Proceedings of the International Conference on Machine Learning. 2010.
Sridhar Mahadevan, Bo Liu, Philip S. Thomas. William Dabney, Stephen Giguere, Nicholas Jacek, Ian Gemp, and Ji Liu. Proximal reinforcement learning: A new theory of sequential decision making in duil spaces. ArXiv Preprint, 2014.

---

Published as a conference paper at ICLR 2025
A Rupam Mahmood, Huizhen Yu, Martha White, and Richard S Sutton. Emphatic temporal- difference learning. ArXiv Preprint, 2015.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 2015.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, 2019.
Doina Precup, Richard S. Sutton, and Satinder Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the International Conference on Machine Learning, 2000.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley Sons, 2014.
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.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Proceedings of the Conference on 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 Learning: An Introduction (2nd Edition). MIT press, 2018.
Richard S. Sutton, Csaba Szepesvári, and Hamid Reza Maci. A convergent o(n) temporal-differene algorithm for off- off-policy learning with linear function approximation. In Advances in Neural Information Processing Systems, 2008
Richard S. Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-differenc learning with linear function approximation. In Proceedings of the International Conference on Machine Learning. 2009.
Richard S. Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M. Pilarski, Adam White, and Doina Precup. Horde: a scalable real-time architecture for learning knowledge from unsuper- vised sensorimotor interaction. In Proceedings of the International Conference Autonomous Agents and Multiagent Systems, 2011. Richard S. Sutton, Ashique Rupam Mahmood, and Martha White. An emphatic approach to the problem of off-policy temporal-diiffrrnnce learning. Journal of Machine Learning Research, 2016.
John N. Tsitsiklis and Benjamin Van Roy. Analysis of temporal-di -ifferel learning with function approximation. In IEEE Transactions on Automatic Control, 1996.
Santosh Vempala. Geometric random walks: survey. Combinatorial and computational geometry, 2005.
Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Provably efficient neural gtd for off-policy learning. In Advances in Neural Information Processing Systems, 2020.
Yue Wang and Shaofeng Zou. Finite-sample analysis of greedy-gg with linear function approxi- mation under markovian noise. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2020.
Yue Wang, Wei Chen, Yuting Liu, Zhiming Ma, and Tie- Yan Liu. Finite sample analysis of the GTD policy evaluation algorithms in markov setting. In Advances in Neural Information Processing Systems, 2017.
12

---

Published as a conference paper at ICLR 2025
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. PhD thesis, King's College, Cambridge, 1989.
Adam White and Martha White, Investigating practical linear temporal difference learning. ArXiv Preprint, 2016.
Tengyu Xu, Shaofeng Zou, and Yingbin Liang. Two time-scale off-policy td learning: Non- asymptotic analysis over markovian samples. In Advances in Newral Information Processing Systems, 2019.
Hengshuai Yao. A new gradient algorithm with only one step-size: Convergence rate analysis using 1-X smoothness. ArXiv Preprint, 2023.
Hengshuai Yao and Zhi-Qiang Liu. Preconditioned temporal difference learning. In Proceedings of the International Conference on Machine Learning, 2008.
Huizhen Yu. On convergence of some gradient-based comporal-different algorithms for off- aff-policy learning. ArXiv Preprint, 2017.
Shangtong Zhang. Breaking the deadly triad in reinforcement learning. PhD thesis, University of Oxford, 2022.
Shangtong Zhang and Shimon Whiteson. Truncated emphatic temporal difference methods for pre- diction and control. Journal of Machine Learning Research, 2022.
Shangtong Zhang, Bo Liu, and Shimon Whiteson. GradientDICE: Rethinking generalized offline es- timation of stationary values. Proceedings of the International Conference on Machine Learn- ing. 2020.
Shangtong Zhang. Yi Wan, Richard S. Sutton, and Shimon Whiteson. reerage-reward off- policy evaluation with function approximation. In Proceedings of the International Conference Machine Learning, 2021a.
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with target network. In Proceedings of the International Conference on Machine Learning, 2021b.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. Advances in Neural Information Processing Systems, 2019.
13

---

Published as a conference paper at ICLR 2025
A PROOF OF THEOREM 11
Proof We first define a few shorthands. We use g(w) and ge(w) to denote the true gradient and its stochastic estimate time f, respectively, i.c.,
g(w) A (Aw + bb, g:(w) A (Arw + be).
We further define
Ar(w) (w w., gr (w) o(w)),
where recall that w" is defined in (4). The following lemma states several useful properties of the functions defined above.
Lemma There exist constants Cg and CLap such that for all w, w/ with [| |w''l s B, we have
max (0(w)),((r)) Ar(w)) Cgr
(w - w/ (((w) g(w')) S -B1 - w'l2 max (1) - di (w') (w')l, ([ - g(w')ll, ll)] - Ac(w'))B s Czmpllw - w'll recall that B is defined in (17). The proof is provided in section C.10.
Lemma For all time and 0 < t,, we have the following bound
t
2BBB + 1)0M {1 (x110 + xx-(e-R(/(-h)
f(I - k) k k S(I k)
|I (wx)ll < CCCCorip In
1-k
The proof is provided in section C.11.
We are now ready to decompose the error as
|we+1 - w.ll?
[[w + auge(w))) - wx 12]
[[we + (wgr(w:)) - I(w-)11
|lace + (nge( -w-ll w=
=E
|lure w.|l2 + alll + 20r w., sc(w)))
Since g(w.) O, we have
(we W., (wz))
=(w; - w., 96 (ww)) - g(wr) ) + +g(w))) - g(w.))
-Ar(w,) + (w: w. ((w.) - g(w.)).
yielding
E || w.ll
<
||we w-ll + a 1 (w:) 22r We, (0n,g((us) (w:))
< ||
11 + +allg(()))) 2anAe(we) + 2ar w. - -
14

---

Published as a conference paper at ICLR 2025
Applying Lemma 12, get
E
|| || w=ll2]
B
|lwr - w.ll2 + 0² Aare)( 20, w.ll
= (1 20, - w. 11 + c (l
Plugging in 0t
Co E+1
and multiplying both sides by (L + 1), we have
(1+ ||wee+1 -=
1(++1) (1 1 2/3
Co
w. w. (1+1) ( Co 2
) 0g (t+ [[A((w:)) t+1
C.
E Blllwx
++1
(++1)
C2C²
s (t + 2280a) B[1 we w. w=1l
2C, 2C,,[A((w))]-
t+1
Let Co 23. Then Co 2 Co. 23Ca
23CD 1. Hence, + 1 -3CC. S t. Since
|| - w. w.1]²]] 2 O, we have
E
C.O² 9 + 2C 2C,EE(,(w,))
(t + 1)E | - wall?] - & tE - w.l + t
Applying the inequality recursively,
TE
WT
w-1²?
C2 1+1
2C, E(A)(())))
T-1 [[A((w))]
2C
Σ
(lA,(w))) 2C
1=0
(C 2C.
Σ
[[Ar(w))]]+ + 2C.
[[A.(w)]]
t=0
where the last inequality comes from the bound for harmonic numbers. Applying Lemma 12 again yields
TE ||r w.1l"]
<C20g(I((T) 1] 2C, Σ Cg + 2C,
Σ
B[Ar(wr)]
1=++1
T-1
-CaC +1] + 2kCaC, + 2C
Σ
[[A))
(20)
1=
Now, we will use Lemma 13 to bound the last summation. Firstly, we take = 2fT).
Secondly, Assumption 4.4 suggests that for some E (0, 3V-2). )
f(t) < C,a," = = (
Co
C+(++1)
(e+1p)
C
Since 5 TV
32-2
3v 2 < 1. Hence, there exists constant To such that for all T > To. v
we have
2C, CT+ T.
2f(T) <
C₁
15

---

Published as a conference paper at ICLR 2025
For the rest of the argument, will assume that T To, and we will then have 2f(T) < T.
As f is increasing, for all E (kt, T),, we have
= 2f(T) 2 2f(t) 2 f(t k)..
So for t ki B[A+(w))] & Crip In
1
+ +2B + 1)0M (x/()= -x00xx*00 --x-((--b))
(Lemma 13)
kt-k)
1
$ CCCaCCipp In
+ 4B(B + 1)Casx 10)
t- k
where the last inequality uses the fact that for all E (k,T),
k f(t k) 2f(T) f(t - k) > 2f(() f(t) f(t).
Summing them up then yields
[t)
(t_) (- + +4B(B + 1)
CyCaCripli In
1=+1
T
SCyCCrrm
(In(t) In(t k)) 4B + 1)0M Σ
x(0
1=k+1
t=k+1
0C
SCyCaCLip
In(() Σ In(t - k)) + +B + 1)0M
1()
1mb+1
T T-k-1
SCyCaCrip
In(()) Σ In(())
+ +BB(B + 1)L(xxx)
k
ECyCaCLsp
In(t) Σ In(t)
+
1=1
SC,CoCrip
In(() In[t (T -k- + 1BB(+1))((..
T-1
t
CCyCaCrip
log
+ +4B(B 1)
t- (T-T-K - -11) 1)
t=
SC,Co Clep
log(T) + 4B(B + 1)L(fx))
SC,Ca tink log(T)) + + 1)),xx)
(21)
where second last inequality holds because
1
log
< log(TT)
1- (T - -1]
holds for all - k- < T and L(f.x)= = -i f(1) < co due to Assumption 4.4.
Plugging (21) into (20) then yields
B[]lwr- - w.ll?
<Cac) 2kC.C, + 2Ca Criph log()) + (BBB)))g)()(+(B1))))))) ()
Ca +1] +1]+2kC.CC + 22, Czip log C
8C. B(B + 1)L(fx)),
16

---

Published as a conference paper at ICLR 2025
Since have defined & = 2f(,), we have that for T 2 To.
E Flllr w=ll
C. (2C) 4 (LP) log(T)
8C, BC, + 1)
T
T
T
T
Thus, for all T, we have
[(TT IT()
WT w.1l =
T
which completes the proof.
B AUXILIARY LEMMAS
Lemma 14 Let Assumption 4. hold. Then there exists constant Cm > 0 and x [0, 1) such that
E
A
A
< Caxx',
(22)
I
A
A
Ar
E
EB [g
S
<CMX"
(23)
18
AT A,11
AT A
S Cs
(x*
[1
+x
t<l
121'
(24)
Similarly,
E
Al
< CMxX',
E
-E (A
E b1
I CMMX"
E
AT AT 8,
A
CM
{1
t 1<1
+x
t2l'
Proof For the simplicity of display, we include the proof only for the first half of the lemma. The second half is identical up to change notations and is, therefore, omitted avoid verbatim.
Define an augmented chain {Yr} evolving in
y ((,,,, E Ax d,(()) m(als) > 0,p(s'ls,,) 0}
as
Y = (S, Ar, S141).
According to the definition of Fe, it can easily seen that Y, is adapted to Fe+1. Assumption 4.1 immediately ensures that (Y,) } is also ergodic with a stationary distribution
dv = d, (s)p(als)p(( 8'1 a).
Here we have used as shorthand for (s, s'). Define functions
Á(v) = (p ())())))))))))))))))))))))))))) (1a(6') =(s))
b(y) p (()))
It can then be easily computed that
A, AYY), A = Σ dy (y))
V
17

---

Published as a conference paper at ICLR 2025
Assumption 4.1 ensures that the chain {Yi} mixes geometrically fast. In other words, there exist constants X E [0, 1) and Co > 0 such that for any and k.
max Σ
Pr(Y++ s/Y, y) dr dr( Cox
This is a well-known result, and we refer the reader to Theorem 4.7 of Levin & Peres (2017) for detailed proof. Then we have
Ad All
Σ Pr(Yi = y))(y)) - Ed y/
Σ |Pr(YY =)) - -orr((())) |Aw
< max
|
Σ |Pr(Y = 8) - dy)ll
y
SHCox':
which completes the proof of (22). Similarly, we have
E
AT
A4t
Ar]
E
[Atte] EE [A]]
Σ Pi -V(())
Pi(M (Ii(V==AA(o))) m)(co))
Pr(Ye+#= = - ((
-
V¹
(r = Y, = v) - Pr((Y+*= = Pr), v)) (OTTAAC)))))
1/'
< <max|
[A(s') T|
max |(w)|
ΣΣ
(Pr(Y 5 :) Pr
= s/) Pr(Y, p = =n))
<H 11 ΣI
Pr(Y 5/, v) - Pr(Ye4* = 5¹) Pr(Y, = 1))l
V'
SH²
Σ
Pr((Y++ = s/Yi = y) Pr(Y, = y) - Pr((Y+++ = 1/) Pr(Yi = 8)
< Σ Σ
|r -//V. = -y) - Pr(Ye+# Pr = v)
<H²
ΣD Σ
Pr(Y++ -/Y,, y) - Pr(Y++# = =
SH² Σ Σ
Pr((+++ //Y.= = v) +1dy - Pr((Y++ = 3/11
SH2
Σ
Pr((Y++ 5 v) -
fy-dd((/)) dr')) + Σ Pr = -/) -3)- -
-d-(6'1)
<H²)
Σ
(Cox* MorK+Gor CNx
71
22H191/Cox
18

---

Published as a conference paper at ICLR 2025
which proves (23). This also suggests 1I,
B A
F - E
ALth
Fi
E A Fi
- 2
To see this, we consider the two cases of whether 1 < separately.
Case 1: I Then, by the Markov property,
AT A Fi]
A 1 Fi
E [ I Fi
AT Yi] - E AAtE Yi
E
Ae vi]
$2HP1y/CoX Cox
Case 2: 1 1126 Then Ag deterministic given Fi. and
E
A
A
Fi|
E
Aet
Fi
E
[
Fil Fi]
E A
[A,
Fil
Fi
E Aett
I
A Fi
E Aetp |
Fi
A
Fil
E
[At+
Fi
E
A.
F
Lastly, combining the geometrical convergence suggested in (22) and the geometrically decaying correlation implied by (23), we can prove (24) in the following manner. First,
E
A
A
ATll
<
E
A15
Fi
E
A
+E
+
E
[AA/F]]
A A
<
E
(AT
E Actx Fi
E [
+ ||8[AArAA [ArtAA
T - AA A
E [Ar
<2A2D1 +
ALtA FF
EE [A
1 A+E
Aetx
A - A A
<211111c6X* & +
E ÁLHN 1F
(IE)
[ A A) || + (B
A F
- -A) A
<2H411166x* +
AAHA [r
| [A
All + 18
Actt Fi
A)T ||AI
<2H4DICOXX & + 1/ [A.
Al
+ H
E | [Fi All
22H + H (|
[A
A
+
B
Ac4* |Fi
-Al)
We now bound the last term. For t < 1, we use the trivial bound
E
|. - A + E A -Al s 4H.
For 2 I, both Y, and Y++h are not adapted to Fi. We, therefore, have
E | - A + E | - all < HCxx + HC
1tk-1 14k-1 22HCox 1-!
Combining the results, we obtain
t<l I [ Ac17] A ATAll $2HAD/COX & + 2Hx
S4H²
t2 l
/2H + +42
t<l 121'
(Since S 1)
12 + 2
19

---

Published as a conference paper at ICLR 2025
which completes the proof of (24).
Lemma 15 If the gap function {(1) [t(tt In(1)] where a non-negative, increasing function tending to infinity, then Et=o (() for all x (0, 1).
Proof Firstly, we should note that for all I, [h(() In(()) h(()) In(() Therefore, take arbitrary (0,1), 1),
100 x
h(e) Σ lnl)) pl(x))()))
2=0
t=
Since h increasing in and tending to infinity, there exists T such that got all t 2 T, f(t) 2 In(x]. Then, for all 2 T, (l(()))(t) t- Thus, by comparison test and p-test, we can conclude that E
x5t) Et <0.
C PROOF OF TECHNICAL LEMMAS
C.I PROOF LEMMA
Proof We proceed via induction m. In particular, we prove the following two inequalities for all m:
+++
fm 16 max (onax(Ca)) 1)'
(25)
a2 ST Vt 2 tm
(26)
Base Case m=0: Obviously we have
09+1
to = 0 16 max 1)²
so (25) holds for m 0. Since 7 E (0, 1). we have
16 max (Ca 1)
To =
2 8 Smax(Ca, 1). 1 7+1
Hence, for all t 2 = 0,
Ca S C. S 8 ma,, 1)² < TØ.
ai (1+ 1)"
So (26) holds.
Induction Step: Suppose (25) and (26) hold for m = k. We now verify them for m = k: + 1.
Letting m in (26) yields
h+ 1
T
<
at
(Defintion of {tm) in (14))
t=t
14-1-1
T (tx+1 tz).R.
Dividing both sides by T3 yields
1
(1) + 1) + 1)"
tk+1 1/ 2
Tk
16 max Ca. 1)
20

---

Published as a conference paper at ICLR 2025
Consequently, have
1)(k (1++))(k 1)"
tK+1 24
16 max (Ca: 1)
kut1
(n + 1) + 1)a
16 max(C.,1)
16 10mmax 1)
where the last inequality results from inductive hypothesis (25). Since 16 max (Ca,1] is monotoni- cally increasing in k; we have
(++1)(++1)
(1 + 1)(k + 1)" (n7 + () + 1)a A+1
(k: + 1) 16 16
k0+1
16 max (Ca,
16 (aaxx(a..1)
16 max 1)
k
We have thus verified (25) for m k + i.c.
k
(k 1)7+I
kU+1
(I: + 1)
1++1 16 (C,, 1)
16 max(Ca,
16 max 16 max (Ca; 1)
To verify (26) for m = h: + 1, we will make use of our just proven (25) with m = k + 1. Take
arbitrary /. 2 1k+1- As 04 = Co is a monotonically decreasing in f, we have
(B+1)
Ca (l++1 + 1)
S Ca
at S Own
k++
Using (25) with m we get
Co
Ca
16 Co max max(Ca, 1)2
/ k + 2
(r+1)
0t S
5
k+1
16 C...) IJ (k+ + 1)nt2)
(k + 2)(++1w
k +
As 2 for and n, U (0, 1]. we have
k: + (x+1)e
2((+1ju
kc k+1
Moreover, since C. < max 1), we have
Ca max 1)2 maxx(Ca; 1)
Thus we have
16 max 1)2
k 2
(x+1)
2(n+5)u ()) (k + 2)(x+1)e
a₁ I
(k + 2)(T+12v
k+1
Using 7. v E (0, 1], we have
0 S 5)V S 6,
max(Ca, 1) < max(Ca., 1)²
The definition of 1j in (13) implies
21 < (1 + 1)v.
Hence, we get
2(0+5)u max Ca. 1)
64 64maxxCor 1)2
ai S
(k + +)(++))
(Ir + 2)
The second inequality in (13) together with the fact that E (0. implies that < 1. Consequently, we have (17 1)2 Therefore,
256 and
(1+7)²
16 16 1) (1) + 1) + 2) We have now verified that (26) holds for m = k + 1, which completes the induction.
64 max CCa, 1)2 (k: + 2)2n
256 max CCa, 1)2 (1 + 1) + 2)3n
=T
21

---

Published as a conference paper at ICLR 2025
C.2 PROOF OF LEMMA
Proof The fact that v E (0, 1) and (13) implies
1
S
2
The fact that v) E [0, 1] implies
16
>
77 +
Consequently, have
16 max 1)
Co
Tm +
8
80m
(m + 1)7 (m + 1)
The definition of {tm. } in (14) implies that fm+1
tm for all m 0, so have
tm 2 m.
C Moreover, because at (1+1)
is decreasing in t, for all t 2 tm m, we have
Tm
On S 0m S
8
The definition of (fm) } in (14) also implies that Σ which completes the proof. Note here we have used the convention that Ei=; 0r 0 j.
2t=tm
mm
Tm- Then we have
fm+11 -1
Amit1 1-2
+ Tm
9Tm
am
Σ
+ 0114111
S
Tm
2T
8
t=
t=hm
C.3 PROOF OF LEMMA 4
Proof For all 2 0,
W1+1 + A-
(1 + A-1b) + on AT (Ar(wr + A-1b) - A,A -- + br)
W/ + A A + az ATt (1AA//l1u + + -||AAAA--1 b/ +1bboll
w. A- a,H (H wez + -- |||| + H + H)
w. A- +a, 2² (I/us w, + A- 2)
(27)
Therefore, by adding 2 to both sides, get
||0+1 + - b1l +2 (1 22 (1wu, +lu,+40 A-bbll +
Applying the inequality iteratively, we have that for all t satisfying tmm t S tm+1
6m+1
| + A- + 2 < (1w: [We.. + +--=b|| +
o, S BmH (lwe.. + A A-1b/| + +2),
f=
where for the last two inequalities, used the fact that
fm
II
(1 (1+, < exp
Σ
orH2
=exp (
j=hn
f=hm
22

---

Published as a conference paper at ICLR 2025
As am 2Tm (Lemma 3) and e²Tmm²² 5 2, |lure + A A-10
+ S e anlt (||wrm + A 1 + +2)
S 2mm H? (1|wemm + A + 2)
$ (1 Wem + +A-1bl + 2)
Hence,
w/ + A 1b|
A- s 2 (1/wemm + + 1)
(28)
Therefore, for all fm S S fm+1, we have
[| Iw: A A1b) 9m ||
(w: AA-b) -wue. + A-1
(w,+1 + +A=16) -(w, =A'b))
(10511 + A- - (ue + A-
Σ
|ajAJrso) (A,(ur +A (l(ww++-1pp
AAA b + b/)l OrH2 22|ww,.. + A 1b6 +4)
==mm
Amt1-1
+A 1-1 + +2)
(Similar to (27))
1m41-1
(Using (28))
==1m
20 H22
(I|Wi.. + A Ab/l + 2)
< 4T H!2
(1) [mmm + A A-bll + 2))
(Using Lemma 3)
< 8T H22
Wim + A -1bll
bll +1)
= 8T H (11gmll + 1),
which completes the proof.
C.4 PROOF OF LEMMA
Proof
11 + 91,ml 1| 1m Am A Aqm 11= || Am TA) 4m 1|
9m (1 AmATA) A) (1 Am A T A) gm
1m 2| 20 A
Aqm 0z A| Aqm 1|2
< || 4m 2 20m
9ml
122 + 2z A
T || |||| 11 11?
< || 4m
2 25
811gm
|mml
12 + - H 9m 1|
< 4m 2 20
311mm
2 + 20 Tm H ||
(Lemma 3)
< 4m 2 25 311gml
+ ām amm 8|
(Assumption of this Lemma)
< (1 _ām) ) || 11?
< (1 3Tm) |1 12
(Definition of Tm in (14))
23

---

Published as a conference paper at ICLR 2025
C.5 PROOF OF LEMMA 6
Proof
1mi111
Σ at AATA- - E (ATrroo)A AclFe emn (entr(em))) )) om
192ml|
||
fmil-1
Σ arB
(AT+110) (b--AA-'b)) (inntrcee)]
A.A-16)
+
fmi1-1
O+e
AT A
E [A Aelem |Mamll
t Am
fm+1
Σ
acl
ael|E/
(Att10) (b- AAA [Fe
+
tm
Im+1 1
Σ
AT A- E [Acts0o) Ac(Fem+(((m)) |
fm+1-1 -1
ae|lB Actscoshe A AbFFen Ill
+
t=
fm+1-1
Σ
| [AT A.t. A.A- Fi +(0m)
0r
t=
1m+1-1
0t
A A
E [o0 Arl + 1(mm)) |lamll
ar |
| ATt ATb ()FFet(((mm)))
fm+1 1
+
at B [ T A -
AT, T
Ar em ((tm)))))) A A-1ol
Em
fmp1
AT A
E
|lamll
1=
fm+1
ar ||B Attrccobe
-----AA7 AT ATb|F b|FFF
1
at
E
AA A
Ao A ||||| A '61l-
To bound the last three terms, we will consider separately whether bm + f(mm) < bmti. If Im + f(mm) Im+1, then applying Lemma 14 yields
fm41-1 11
fm41-1
1122mll1 11 5
arCs I1gmll +
anC +
Σ
MCCM H
t=
by
t=tm
Amii- 11 Σ
=CM (114mll + 1)
I=
24

---

Published as a conference paper at ICLR 2025
Ca_ Since a2 (1+1)r
is decreasing function in we have
Fm 1-1
l192.l ll - Cas (1 gmll
||
+ +++
Σ
Car(ll
||
+ H + 1)(1m+1 - mm at
I Cam(l1mml
+ + (mmm)))))
Assumption 4.4 suggests S(1) S C,
ll 11 - (M ll + + 1) at
3 C + HI + 1)at
Because 04 S T2 for 1 2 mm (Lemma 2),
|| S CCC-((lum + H + 1)T ()
CC + 1) + 1).
For the general case where Im + f(mm) < 4m+1, we break the summation Eiar -1 into two parts, +i0m)))) and him
ie.
2i=tm
((= and apply Lemma 14 separately. We have
em (n+
|192mll m|
$
Σ
at
A - E [A+rs)) I Fe Fent ||ll I A AA
t=
1m-1-1
Σ
ael|At
A A - E [Ttsso) Fr 510ml ||
fmm+s((e
Im ((tm))
Σ
E
A be AT Fem+
t=tm
Im 1-1
Σ
ar
E
AT - A F Fen+s(mm)
t= f(tm)
+ f(tm))
Σ
R
AT A
ATr A F F(m+)((mm)
|||| b-
are
E
ATA A - Aotr Ae F Fem+
||am|||||1 1|l1|111100 |-
((tm)
En f(mm
6m+1
arCMllamll+ +
Σ
acOm (x + x" x-mimm ((6ml)) l1amll
tm + F(tm)
Amti-
OrC +
Σ
C,COs (x100) + x(=mmm+((mm))
t= tt
(mtm(m))-1
1m41-1
CnCasH
Σ
acOm (x500 + ((btttt((
t=im+S(to)
I'm f(tm)))))
tm+1
SCar(1lgmll H+
Σ
04
Σ an (x + x² + (ant((bml))
1=t
25

---

Published as a conference paper at ICLR 2025
Cs is decreasing function in t and at I Tm for f 2 tm (Lemma 2), get Because og (1+2)=
cm +0 E
fm+1-1
1 || 2 CM (1 + + +
atm + +I2
Σ
(x + x(-lm=t((mm)))
t=
t= (fmm)
tm+1-
1m
S Car(1aml H 1)
[(lm)a + +
x ((0)
Σ
ton ((tmm)
tm + ((bm)
by +5(mm)
+ b
S CM 11 1)
f(bm)at + T
f(t)
t=0
Assumption 4.4 suggests that f(1) S C-a," and L(S. x) Ei=x(1)) < co. Therefore,
Cra atm +12 (1x:)+2>1
1122mll| I CM((1eml] 11 1)
1=0
Ctat + [(fx))+ 1111 )
1
(a H + 1)
Carlllmm 11
H + 1)
C,12(1-7) + +I
[(fix)+ 1
1-x)
When Tm S 1, we then have
(1 ((++ + 1 + (1gmml 1),
I1gamlll S CMI2(1-F) (H +1)
which completes the proof.
26

---

Published as a conference paper at ICLR 2025
C.6
PROOF OF LEMMA 7
Proof Firstly, have
8m+1-1
119,ml
1
Σ
at
E
Al AolFe. (msts(m))) A Aot Ae) gm
1=
fm4t-11
Σ an
(E
[B[AL111) (be- --A-A |Fimts(emm Aits(o (b--A,A-1))
1m+1
Σ at (| (mem
+00m))) || 100 llamll
t=
1m41-1
at [| (be- A.A-1b) [Fents(mm)] + || ||| (10.11 + //.AAAAA -bl)
AL
+
t=
Ami
Σ
ag
E
[| Fim Ftmtt(emm) + H. H) llamll
tmi1 -
A AT-s(0) o6 [
(bc- A. A,A- (Bl-AA--))(FFittttee + H(H m)
kmt -
Σ
E
A s(e)
rces
AellFeem + H²2) l1amll
an
fm#1
Σ at E
(11xo11 + || -0/1 (Fim+(((m)) + +HH2
Am41-1
tmti
Σ
O4 (H2 + 1²2) |1
Σ on (H(H+) + H) 2H²)
20 H2 (11 || + 2)
<AT 122 (mlmmll + +2)
(Lemma 3)
<8T 22 9m + 1).
Secondly,
[gs.ml F + =
holds trivially, which completes the proof.
C.7
PROOF OF LEMMA 8
Proof
g
Σ
AIATHrC) Amlan (wr A A-1b)]
t=tm
1mii -1
ass A |
1l (wi + A-1b) ||.
t=
27

---

Published as a conference paper at ICLR 2025
Then, by Lemma have
fm=1-1
1194.
Σ
atH H. 8T (11amll + 1)
t=fm
8āmI
H' (llqml) + 1),
which completes the proof.
C.8 PROOF LEMMA
Proof
[1m++1 112 =1lmm + 91,m + 92,m + 93.m + 94.m 11
=1lym 91,ml 11 + 1192, + 33.m + 94.ml
2(4m + 91.m) (g2,m ( 93.m 94.m)
S11gm + 91,mll ll 1192, + 93,m + 94.ml
+ 2(qm + 91,m) 93,m + 4m + 91,m I111g,, + 91,mll
Lemma 5 implies that 1l + 91,ml 112 S (1 - 3T,, 1lmmllmll and llam + 91, = ( Lemma 6
suggests that |l = O (Th (1)(1))) (1 + 1)) Lemma 7 suggests that [|9s.m || = O (1lmml
1)), and Lemma 8 suggests that [94.ml O (T ml |I + 1)). Hence,
|192,. 93.m 94.ll < 1192.m || + 93. + |194.l|| = ( 1)),
and
l12.. + 94.mll (T +1)+
Moreover, both qm and Il.m am Aqm are adapted to Fem+s((m) and 7 implies that m F (5 = O. We, therefore, have
E [(am 91,m) g3.m Femt(((m)) 0.
Lastly, putting everything together, we have
E
||am+1|
11 Fr +((mm)
<(1
ml
OTTm 1))² + ((1mml)) (T2(2-=)(11)) (11mml + +1))
<(1 -mT,)
+ (7((117)((1gg))) 1)²)
5(1 (T.m. 1l4ml
o (78(1-7)(11gm)) 1))
where the last inequality comes from the fact that (1 qm 1)2 S 2(11mm 1). In conclusion, there exists constant D such that
E [g 11mm+1112/5 112 (((m)))))))) S s<1 (1-33Tm (1 DT2((-T) || DT2(1--))
which completes the proof.
C.9 PROOF OF LEMMA 10
Proof To prove the lemma, we will invoke a supermartingale convergence theorem stated as follows.
Theorem 16 (Proposition 4.2 in Bertsekas & Tsitsiklis (1996)) Let Ym. Xm- and Zm- 2 be three sequences of random variables and F... m 2 0, be sets of random variables such that F.. C Fm for all Suppose that
28

---

Published as a conference paper at ICLR 2025
1. The random variables Ym- Xm, and Zm are non-negative and are functions of the random variables in Fm..
2. For each m, we have E Ffm=1/mm S Ym Xm + Zun
3. There holds Em= Z' 0C.
Then, we have Em=o Xm < xc almost surely, and the sequence Ym converges almost surely to non non-negative random variable Y.
In our case, we let
Y 1m 1
X m
3T m 11
2
Zm DT-(111))
Fm. =ftm)((m))>
The first condition of Theorem 16 holds trivially. For the second condition of Theorem 16 hold, we rely (18) in Lemma 9. According to the definition of Tm in (12), we have
lim Tm 0.
As result, the condition
B ln(2)
Tm S min
2.14 2H2
in Lemma 9 holds for sufficiently large m. Moreover, since
3 1
(Assumption 4.4)
2
1
(Assumption 4.3)
2 1
2'
we have
2(1 -T) 1.
Consequently, the condition
(T2((-r) m
< ST m:
which is equivalent to
3
(2(1-))-1 < 21)
also holds for sufficiently large limm Tm 0. Crucially, D is deterministic because D only depends on H, 88 Cr, CM. L(f. x), and X. which are all deterministic quantities. Therefore, there always exists a finite and deterministic mo such that the subsequence {Xm, Ym, Zm } Jm 2mo verifies the second condition. Since 1) > 21- i.e. 2(1 T)n 1, by p-test, we can deduce that
C
16 max (aax((C.)) 1) 2(1-r)
Σ
7m
2T m
Σ
(n + 1)(m + 1)m
(16 CCa, 1))2(1-7) (17 + 1)2
(n + 1)2(1-7) 00..
m=0
29

---

Published as a conference paper at ICLR 2025
The third condition of Theorem 16, therefore, also holds. All the conditions of Theorem 16 are verified for the subsequence (Xm; m. Zm) m22m" which implies that the sequence { {Ilgmll m20 converges and
2 Tm 1m 11 < 00.
3
As < 1, we have
00 Σ Tm
16 max Ca. 1) (1) (m + 1)9
16 ma 1)
oc.
17 7+1
(m 1)a
m=
0c Thus, 11 2| must converge to zero. Otherwise, Σ m== Xm = infinity. Thus, Im converges to 0 almost surely, which completes the proof.
3
Imm amal diverges to
C.10 PROOF OF LEMMA 12
Proof First, we prove the bounds for each function.
Bound for ge(-):
(w))l AAT 500 1o
(A,w w + 6/) S (ATtsco) A1 + +18%,1))
$ HHHB + H) (B 1).
Bound for g(-):
[g(w)) =
-| I| (Aw + b)]l s [|<T](([)]]] + (M-) < H(HB + B) = H²(B 11.
Bound for Ar(-):
|A<())] 1(w w.s (w) [ww)I < || w. (wl.. (
S ([|w]I I|w.
(I) s (B [
(B)
Hence, by taking C, max HB + B( + 1)), we have the result stated. Second, we prove the functions are Lipschitz. gc(-) - Lipschitz:
(l:(w) - ge = | - -ATt +b,) + AT 110 (Arw' + +boill A - w')
< A ||l|AA/lllla w s H2llw - w'll
g(-) is H²-Lipschitz:
lØ(w) g(w')ll = -1I-AA(AAA (Aw + 6) + A (Aw' + 6)]l = I|AT A(w' - w
< [|||||||||w w|ll - 122l|w w|].
30

---

Published as a conference paper at ICLR 2025
A is 23B 1)-Lhscchi
[M((w) Ar(w'')
=I( w. () (ww) (w' W. ge(w') [(w'))]
=I(w w.. 9 ()) g(w) (9l(w)) g(w'))) + (w Wa (w' - w. (e -
<l w. (w) F(w) (glww) 0(w')) )))) + +1 w', (w'w)) g(w'M
<lww u.. (w) g(w) (gr(w") -5(ww)))l |||++ --Ilw=''llll w'lllla -g(w')l
<(||]|| + [1.x1)((l9(( (w²) 96 [((w)]l + ( (w)) (1((w"))\llw - w
<(B + (B))((l) (w)ll+ [lō(w) ((w')) +1)
H² + 1)]ll w'll
<2B(119,('') - - (Ø((w)
1)]| w'll
22B(H w|l H w|l) + 2 1 w'll
-3B 1>][ - w/ll
Therefore, by taking CLip max 2 + 1)}. we have the result stated.
Lastly, we prove the following inequality regarding the inner product.
(w g(w) g(w')) (w w', AAAAAA + b) + A (Aw' + +b] =- w/) AAA A A(w - w') S - B1|ur w' 112
where the last inequality holds due to (17).
C.11 PROOF OF LEMMA 13
Proof For any i 2 0, since w, lies in the ball for projection, we have
||0411 - wi || = [[[[, + (u:)) will
[[[,, (u:)) I(w;)]l
S
[[T(w; + (wg; - w::)
(T(-) is non-expansive)
(w:))ll
< [la.g((w)))
(w;)ll
I a,Cy
(Lemma 12)
Therefore, by telescoping, we can deduce that for all 0 < k < t
t-1
1-1
||., - Wt xl1 S
Σ | - wi|l S
Σ
Cyas = Cg
Σ Uls- i=t-k
Because F4-
is a decreasing function in t, for all E [t, t + 1}, F+1 1 J.
As a consequence,
and
E41
Σ i=
Σ
Σ
1 = In()) - Im(t -n)(t))
t-k 7
t- k
In addition, given that ar
Cv 1+1
we have
C.
t (!1))
|/:, W2-All S C, Σ a. -==0, C2
Σ
i+1 1
< C.C.
In
kt
imt-k
imt
Applying Lemma 12 again, we get
[A(()))) Ae(wx-k) C.C.CCipp In t- Kr
31

---

Published as a conference paper at ICLR 2025
and hence
Ad(w)) S A CgCC (1-1)
(29)
We now bound the expectation of Ae(we-k) conditioning on Ft-k+ ((t-A)- In particular, we have
E
E [Wit- k W 96 (w'e x) -(wr x)) F (+
=E ( (wi= W/, A Afts()) (Aewe + +bb,) A (Awi-x - -b)) [F(-
=E
( (wi=k war (A - AA w2-k (A
- -ATb) 1=
As expectation and dot product are linear and w/- is adapted to F f(t-((tt we can further reduce our expectations as
E -F
A A1 - -ATA) wi-k (I A1t - -Abb)
wi-k Whe
S||w;- w.il (B (A FolF
Ael
A A) W [E AT
-Abb)
<([[u>=<|| I|l. II) (I( (E --
AATA] a) we-k
+ | A be
AAT -Abbl)
<([[w]=X|| + mml II) E A
A ATAlllu-al E AT (0
-A
S(B + B) (|E AFF A Al + EE by -ATo/)
<2B (|L/ [ A A A + |B (h bTb))
Applying Lemma 14, we get
{1 (x1(t) + ((-(
t<t k f(t k) t-k + f(t k) St
A[A 2B 1)CMs
Taking total expectations then yields
(W < 2B + 1)Ca {1 (x)()) + (1--(--0(000))
<< [(| - k)
(30)
2 f(t - k)
Plugging (30) into the expectation of (29) yields
[[,(w < CyCaCrap In ( L ( +BBBB + 1)CM
[1
k < 5(1 k)
k-kk k)
(x5(0)
k f(t k))
which completes the proof.
32


Reviews:
[{"review_id": "8HcgeZMtnZ", "reviewer": "Reviewer_VCek", "summary": "The paper aims to develop a convergent algorithm for off-policy temporal difference learning under linear function approximation. The proposed algorithm directly minimizes the L2-norm of expected TD updates (NEU) $||Aw+b||^2$, improving the memory requirement of estimating matrix $A$ from the previous ATD algorithm. Meanwhile, the proposed algorithm reduces the number of learning rates from two to one compared to GTD, another NEU minimization algorithm. It maintains the convergent property with a convergent rate $\\tilde{O}(1/t)$. Moreover, the algorithm is tested on Baird’s counterexample and is shown to avoid divergence in the deadly triad.", "questions": "Is it necessary to take an increasing function f(t)? Besides removing the dependence between data at step t and t+f(t) to establish the convergence proof, is there any other reason to use an increasing function?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem to tackle is well stated, which is to stabilize off-policy learning and improve the previous algorithm ATD and GTD: the proposed algorithm saves memory compared to the ATD algorithm and increases the convergence rate compared to GTD. Also, the paper is clearly written and easy to follow, with rigorously stated assumptions and lemmas.", "weaknesses": "The approach needs to be more motivated. GTD is known to suffer from a low convergent rate compared to TD. More experiments to compare the convergence speed and some intuition on why the proposed algorithm can fasten the learning would be great.\n\nAlso, the algorithm needs to fit better into the literature. ETD, introduced by Mahmood and colleagues (2015), is another stable off-policy algorithm. Also, a target network is suggested to help convergence (Zhang et al., 2021; Fellows et al., 2023; Che et al., 2024). Che et al. (2024) compare their TD algorithm with GTD on Baird’s counterexample, showing much faster convergence.\n\nReference\n\nMahmood, A. R., Yu, H., White, M., & Sutton, R. S. (2015). Emphatic temporal-difference learning. arXiv preprint arXiv:1507.01569.\n\nZhang, S., Yao, H., & Whiteson, S. (2021, July). Breaking the deadly triad with a target network. In International Conference on Machine Learning (pp. 12621-12631). PMLR.\n\nFellows, M., Smith, M. J., & Whiteson, S. (2023, July). Why target networks stabilise temporal difference methods. In International Conference on Machine Learning (pp. 9886-9909). PMLR.\n\nChe, F., Xiao, C., Mei, J., Dai, B., Gummadi, R., Ramirez, O. A., ... & Schuurmans, D. (2024). Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation. arXiv preprint arXiv:2405.21043.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BJWLZU7NQP", "reviewer": "Reviewer_N6bs", "summary": "This paper proposes a new variant of the gradient temporal difference (GTD) learning algorithm for online off-policy policy evaluation with linear function approximation. The idea is to use two samples distanced away from each other to address the double sampling issue encountered during the derivation of GTD. The paper shows that when the distance between the two samples $f(t)$ used to estimate the gradient increases with a proper rate (e.g., $f(t)=\\ln^2(t+1)$), the new algorithm converges asymptotically, while its variant with a projection operator has a convergent rate comparable to on-policy TD. The consequence of this new GTD variant is that 1) it reduces the need for an additional set of weights and step size, and 2) it requires an additional memory of size $O(\\ln^2(t))$. Preliminary experiment results on Baird’s counterexample show the effectiveness of the proposed algorithm.", "questions": "Here are a few questions that might affect the evaluation:\n1. Do the choices of $f(t)$ depend on the induced Markov chain’s mixing time? If yes, where is it in the result? If not, why?\n2. What is the convergence rate for GTD? Is it the same as the canonical on-policy TD as well?\n3. In Line 182, when $f(t)$ was a constant function, what would happen by following the classical convergence results mentioned in Line 186? What’s the consequence of using such a $f(t)$?\n4. In Line 227, the paper claims the technique of using a variable interval $T_m$ has not been used in any stochastic approximation and RL literature. Has it been used or studied in other fields? If yes, then it is worth mentioning the relevant literature.\n5. In Line 482, the paper claims that the finite sample analysis **confirms** that the proposed algorithm converges reasonably fast, but this analysis is based on a variant of the proposed algorithm with a projection step. Does the efficiency of the variant with the projection step guarantee or generally suggest the efficiency of the base algorithm?\n6. Is the proposed algorithm more or less sensitive to the learning rate compared to GTD? Since GTD has two hyperparameters, comparison methods like those in Ghiassian & Sutton, 2021 might be useful here.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The strengths of the paper include its originality, quality, and clarity:\n1. The idea in this paper is novel to the best of my knowledge. It’s neat to use two samples distanced away from each other to estimate the terms involving two $A$ matrices, which are independent if their gap is large. The sublinear memory requirement also renders this idea a practical approach.\n2. The quality of the paper is also a strength. The asymptotic convergence of the proposed algorithm is novel and may bring value to the community.\n3. The paper is very well written and easy to follow.", "weaknesses": "The paper has weaknesses in its significance and relevant work discussion:\n1. The paper may be limited in its significance. \n  - On the theory side, the finite time analysis is based on a variant of the proposed algorithm with a projection step, which is absent in the actual algorithm. Thus, the comparison between its convergence rate in this case with that of on-policy TD may not be very valuable. Note that finite sample analysis of the actual algorithm is possible, as also pointed out in the paper. Obtaining such a result can strengthen the paper.\n  - On the empirical side, the experiments presented in this paper only focus on Baird’s counterexample and are rather limited. Having more experiments, even in simple environments like FourRoom (Ghiassian & Sutton, 2021; Ghiassian et al., 2024), would help strengthen the claim that the proposed algorithm is effective. In addition to testing the proposed algorithm in environments like FourRoom, a comparison with other GTD algorithms can also make the paper stronger. Other researchers may find it useful to know how the proposed algorithm compares to others in terms of sample efficiency, stability, and hyperparameter sensitivity.\n2. The paper also lacks a thorough related work discussion on off-policy policy evaluation (OPPE) with linear function approximation. There have been many follow-up works on the GTD algorithm (Mahadevan et al., 2014; Ghiassian et al., 2020; Yao, 2023). While some of them are cited in the paper, the relationship between these later ideas building on GTD and the proposed method is not thoroughly discussed, which could be useful and inspire future research. Note that Yao (2023) also introduces a GTD variant with one step-size, so it may be necessary to clarify its distinction with your approach. In addition, the paper may also benefit from discussing another line of work that addresses the deadly triad, the ETD family (Sutton et al., 2016; Hallak et al., 2016, 2017; He et al., 2023). Specifically, how does the proposed approach compare to these methods in terms of the optimality of the fixed point and the convergence property? Having a more thorough discussion of these relevant works would strengthen the paper’s positioning.\n\nGhiassian, S., Patterson, A., Garg, S., Gupta, D., White, A., & White, M. (2020). Gradient temporal-difference learning with regularized corrections. ICML.\n\nGhiassian, S., & Sutton, R. S. (2021). An empirical comparison of off-policy prediction learning algorithms in the four rooms environment. arXiv preprint arXiv:2109.05110.\n\nGhiassian, S., Rafiee, B., & Sutton, R. S. (2024). Off-Policy Prediction Learning: An Empirical Study of Online Algorithms. IEEE Transactions on Neural Networks and Learning Systems.\n\nHallak, A., Tamar, A., Munos, R., & Mannor, S. (2016). Generalized emphatic temporal difference learning: Bias-variance analysis. AAAI.\n\nHallak, A., & Mannor, S. (2017). Consistent on-line off-policy evaluation. ICML.\n\nHe, J., Che, F., Wan, Y., & Mahmood, A. R. (2023). Loosely consistent emphatic temporal-difference learning. UAI.\n\nMahadevan, S., Liu, B., Thomas, P., Dabney, W., Giguere, S., Jacek, N., ... & Liu, J. (2014). Proximal reinforcement learning: A new theory of sequential decision making in primal-dual spaces. arXiv preprint arXiv:1405.6757.\n\nSutton, R. S., Mahmood, A. R., & White, M. (2016). An emphatic approach to the problem of off-policy temporal-difference learning. JMLR.\n\nYao, H. (2023). A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using $ L $-$\\lambda $ Smoothness. arXiv preprint arXiv:2307.15892.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rcba1PtbFx", "reviewer": "Reviewer_R5Yw", "summary": "This paper proposed a new solution to solve double sampling issue in off-policy reinforcement learning. Specifically, this paper provided another method to estimate $A^T A$ and $A^T b$ by introducing a function $f(t)$. The authors also provided finite-time analysis for their method as well as some numerical results.", "questions": "Please see my comments in Weaknesses section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper expand the idea from $A^TTD$ and proposed a new method to solve double sampling issue in off-policy learning. Compared with $A^TTD$, this methods required less memory. The authors also provided the convergence analysis of their method.", "weaknesses": "This paper is really interesting to me. However, I have several questions. \n\n1. The advantage of selecting $f(t)$ as an increasing function over a constant one is not immediately clear. The authors state in lines 186–187 that classical convergence analysis can be applied to establish the convergence rate. Thus, it seems that a constant $f(t)$ could also ensure convergence. Additionally, the experimental results suggest that setting $f(t)=2$ is sufficient to resolve Baird’s counterexample, which further supports the idea of choosing $f(t)$ as a constant.\n\n2. Relying on samples from several steps prior may introduce additional errors during policy improvement. Although this paper focuses exclusively on policy evaluation, it is important to mark that policy evaluation serves the purpose of policy improvement. In cases where the policy is continuously updated, the samples used to estimate $A^T$ may become inaccurate, introducing further errors.\n\n3. A minor issue appears in lines 206–207, where I believe the correct notation should be $\\bar{h}(\\omega_{t_m})$ instead of $h(\\omega_{t_m})$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)