Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
Authors: Yue Wang
Shaofeng Zou
Yi Zhou
Venue: NeurIPS 2021 Poster (2021)
Keywords: TDC
finite-sample analysis
tracking error bound
Markovian noise
non-convex

Abstract: Temporal-difference learning with gradient correction (TDC) is a two time-scale algorithm for policy evaluation in reinforcement learning. This algorithm was initially proposed with linear function approximation, and was later extended to the one with general smooth function approximation. The asymptotic convergence for the on-policy setting with general smooth function approximation was established in [Bhatnagar et al., 2009], however, the non-asymptotic convergence analysis remains unsolved due to challenges in the non-linear and two-time-scale update structure, non-convex objective function and the projection onto a time-varying tangent plane. In this paper, we develop novel techniques to address the above challenges and explicitly characterize the non-asymptotic error bound for the general off-policy setting with i.i.d. or Markovian samples, and show that it converges as fast as $\mathcal O(1/\sqrt T)$ (up to a factor of $\mathcal O(\log T)$). Our approach can be applied to a wide range of value-based reinforcement learning algorithms with general smooth function approximation.

Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
Yue Wang
Shaofeng Zou Department of Electrical Engineering University at Buffalo Buffalo, NY, USA
Department of Electrical Engineering University at Buffalo Buffalo, NY, USA
ywang2948buffalo.c edu
szou3@buffalo. edu
Zhou
Department of Electrical and Computer Engineering University of Utah
Salt Lake City, Utah, USA yi yi.zhou@utah. edu
Abstract
Temporal-difference learning with gradient correction (TDC) two time-scale algorithm for policy evaluation in reinforcement learning. This algorithm was initially proposed with linear function approximation, and was later extended to the one with general smooth function approximation. The asymptotic convergence for the on- on-policy setting with general smooth function approximation was established in [Bhatnagar et al. [009]. however, the non-asymptotic convergence analysis remains unsolved due challenges in the non-linear and two-time soo-imm-scalee update structure, non-convex objective function and the projection onto time-varying tangent plane. In this paper, we develop novel techniques to address the above chal- lenges and explicitly characterize the non-asymptotic error bound for the general off- off-policy setting with i.i.d. or Markovian samples, and show that converges as fast as ((1/VT) (up to factor of (log T)). Our approach can be applied to a wide range of value-based reinforcement learning algorithms with general smooth function approximation.
Introduction
In reinforcement learning (RL), agent interacts with a stochastic environment in order to maximize the total reward (Sutton and Barto 2018). Towards this goal, is often needed to evaluate how good policy performs, and more specifically, learn its value function. Temporal difference (TD) learning algorithm is one of the most popular policy evaluation approaches. However, when applied with function approximation approach and/or under the off-policy setting. the TD learning algorithm may diverge (Baird) [995] Tsitsiklis and Van Roy 1997]. To address this issue, family of gradient- learning with gradient correction
TD (GTD) algorithms, e.g., GTD, GTD2, temporal-differenn (TDC) and Greedy-GQ- GQQ were developed for the case with linear function approximation [Maei] 2011 Sutton et al. [2009b] Maei et al. [200 (Sutton al. 2009a b). These algorithms were later extended to the case with general smooth function approximation in [Bhatnagar al., 22009, where asymptotic convergence guarantee was established for the on-policy setting with i.i.d. samples.
Despite the success of the GTD methods in practice, previous theoretical studies only showed that these algorithms converge asymptotically, and did not suggest how fast these algorithms converge and how the accuracy of the solution depends on various parameters of the algorithms. Not until
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

recently have the non non- -anayttpttoiic error bounds for these algorithms been investigated, e.g., [Dalal ct al. 2020, Karmakar and Bhatnagar 2018 Wang and Zou| 2020 Xu et al., 2019, Kaledin et al. 2020 Dalal et al. 2018 Wang et al., 2017], which mainly focus on the case with linear function approximation. These results thus cannot be directly applied to more practical applications with general smooth function approximation, e.g., neural networks, which have greater representation power, do not need to construct feature mapping, and are widely used in practice.
In this paper, we develop a non-asymptotic analysis for the TDC algorithm with general smooth function approximation (which we refer to as non- lineii TDC) for both i.i.d. and Markovian samples. Technically. the analysis in this paper is not straightforward extension of previous studies on those GTD algorithms with linear function approximation. First of all, different from existing studies with linear function approximation whose objective functions are convex and the updates are linear, the objective function of the non-linear TDC algorithm non-convex, and the two time-scale updates are non-linear functions of the parameters. Second, the objective function of the non-linear TDC algorithm, the mean-square projected Bellman error (MSPBE), involves a projection onto time- varying tangent plane which depends on the sample trajectory, whereas for GTD algorithms with linear function approximation, this projection is time-invariant. Third, due to the two time-scale structure of the algorithm and the Markovian noise, novel techniques to deal with the stochastic bias and the tracking error need to be developed.
1.1 Challenges and Contributions
In this section, we summarize the technical challenges and our contributions.
Analysis for two time-scale non-linear updates and non-convex objective. Unlike many existing
results two time-scale stochastic approximation, e.g., (Konda al. [0004] Gupta et al., 2019
Kaledin et al. [2020] and the studies of linear GTD algorithms in [Xu et 2019 Ma et al. 2020
Wang et al.) 2017 Dalal et al.) 2020]. the objective function of the non-linear TDC is non-convex,
and its two time-scale updates are non-linear. Therefore, existing studies on linear two time-scale algorithms cannot be directly applied. Moreover, the convergence to global optimum cannot be guaranteed for the non-lineas TDC algorithm, and therefore, we study the convergence to stationary points. In this paper, we develop a novel non-asymptotic analysis of the non-linear TDC algorithm, which solves RL problems from a non-convex optimization perspective. We note that our analysis is not a straightforward extension of analyses of non-convex optimization, as the update rule here is two time-scale and the noise is Markovian. The framework we develop in this paper can be applied to analyze a wide range of vasue RL algorithms with general smooth function approximation.
Time-varying projection. For the MSPBE, a projection of the Bellman error onto the parameterized function class is involved. However, unlike linear function approximation, the projection onto general smooth class of functions usually does not have a closed-fone solution. Thus, a projection onto the tangent plane at the current parameter is used instead, which incurs a time-varying projection that depends on the current parameter and thus the sample trajectory. This brings in additional challenges in the bias and variance analysis due to such dependency. We develop novel approach to decouple such a dependency and characterize the bias by exploiting the uniform ergodicity of the underlying MDP and the smoothness of the parameterized function. The new challenges posed by the time-varying projection and the dependence between the projection and the sample trajectory are not special to the non-linear TDC investigated in this paper, and they exist in a wide range of value-based algorithms with general smooth function approximation, where our techniques can be applied.
A tight tracking error analysis. Due to the two time-scale structure of the update rule, the tracking error, which measures how fast the fast time-scale tracks its own limit, needs to be explicitly bounded. Unlike the studies on two time-scale linear stochastic approximation [Dalal et al.) [2020] Kaledin et al.) 2020 Konda et al., [004]. where a linear transformation can asymptotically decouple the dependence between the fast and slow time-scale updates, it is non-trivial to construct such transformation for non-linear updates. To develop a tight bound on the tracking error, we develop novel technique that bounds the tracking error as a function of the gradient of the MSPBE. This leads to tighter bound on the tracking error compared to many existing works on two time-scale analysis, e.g., (Wu et al.) 2020 Hong et al. 2020). A Although we do not decouple the fast and slow time-scale updates, we still obtain desired convergence rate of (1 TT) (up to factor of log T), which matches with the complexity of stochastic gradient descent for non-convex problems GGadiiii and Lan 2013

---

1.2 Related Work
TD, Q-learning and SARSA. The asymptotic convergence of TT with linear function approximation was shown in (Tsitsiklis and Van Roy [997], and the non-asymptotic analysis of TD was developed
in (Srikant and Ying 2019| Lakshminarayanaa ynaa and Szepesvar 2018 Bhandari et al. 2018 Dalal
et al. 2018 |un et al. 20200] Moreover, [Cai et al. [019] further studied the non-asymptotic error bound of TD learning with neural function approximation. Q-learning and SARSA are usually used for solving the optimal control problem and were shown to converge asymptotically under some conditions [Melo et al. 2008 Perkins and Precup 2003). Their non-asymptotic error bounds were also studied in Zou et al. 2019]. The non-asympioti analysis of Q-learning under the neural function approximation was developed in [Cai et al. 2019 Xu and Gu 2020]. Note that all these algorithms are one time-scale, while the TDC algorithm we study is two time-scale algorithm.
GTD methods with linear function approximation. A class of GTD algorithms were proposed to address the divergence issue for off- pfolicy training [Baird 1995] and arbitrary smooth function approximation lsstsiikis and Van Roy 1997]. e.g., GTD, GTD2 and TDC [Maei] 2011 [Sutton et al.
2009b Maei et al. 22100 [Sutton et al. 2009a bj. Recent studies established their non-asympion ptotic
convergence rate, e.g.. [Dalal et al. 2018 Wang et al., 2017 Liu et al.) 2015| Gupta et al.
2019
Xu et al.
2019 Dalal et a 2020 Kaledin et al.) 2020 Ma et al., [020] Wang and Zou 2020
Ma et al., 2021 under i.i.d. and Markovian settings. These studies focus on the case with linear
function approximation, and thus the objective functions are convex, and the updates are linear. In this paper, we focus on the non-linear TDC algorithm with general smooth function approximation, where the two time-scale update rule is non non-linear, the objective is non-convex, and the projection is time-varying, and thus new techniques are required to develop the non -on-asympootic analysis.
Non-linear two time-scale stochastic approximation. There are also studies on asymptotic con- vergence rate and non-asymptotic analysis for non-linear two time-scale stochastic approximation, e.g., [Mokkadem et al. 2006 Doan, 2021]. Although the non-linear update rule is investigated, it is assumed that the algorithm converges to the global optimum. In this paper, we do not make such an assumption the global convergence, which may not necessarily hold for the non-linear TDC algorithm, and instead, we study the convergence to stationary points, which is a widely used convergence criterion for non-convex optimization problems. We also note that there is a resent work studying the batch-based non-lineat TDC in Xu and Liang 2021], where at each update, a batch of samples is used. To achieve sample complexity of O(e "), a batch size of O(E is required in (Xul and Liang, 2021] to control the bias and variance. We note that by setting the batch size being one in [uu and Liang 2021), J. the desired sample complexity cannot be obtained, and their error bound will be a constant. In this paper, we focus on the non-linear TDC algorithm without using the batch method, where the parameters update in online and incremental fashion and at each update only one sample is used. Our error analysis is novel and more refined as it does not require a large batch size of 22) while still achieving the same sample complexity.
2 Preliminaries
2.1 Markoy Decision Process
A Markov decision process (MDP) is tuple (S,,A,,,, 7), where S and are the state and action spaces, P = ((s (s, a) is the transition kernel, r 8 x A x 8 + R+ is the reward function bounded by Tmaxx and y E [0, 1] the discount factor. A stationary policy x maps a state s E 8 to a probability distribution π 8, E 8. and an action o, E A is taken. Then the system transits to the next state 81+1 following the transition kernel P P(-Ist, 0z), and the agent receives a reward r r(st, at 81-
over the action space A. At each time-step t, suppose the process is at some state
For a given policy æ and any initial state s E 8, we define its value function V/ (s) E i 7'r(S, Ac, Se = s, s]. The goal of policy evaluation is to use the samples gen- crated from the MDP to estimate the value function. The value function satisfies the Bellman equation: V=(s)= ==(s)=TTTT VTV for any s E S, where the Bellman operator 7 is defined as
(V)())= = Σ
P(6'|s, a)T((l))r(s, a, +)
Σ E'E
P(d(s.)))((a))))())
(I)
E'EA
Hence the value function V is the fixed point of the Bellman operator Td'
Bertsekas 2011
3

---

2.2 Function Approximation
In practice the state space 8 usually contains large number of states or is even continuous, which will induce heavy computational overhead. A popular approach is to approximate the value function using a parameterized class of functions. Consider parameterized family of functions (Vo 8 + R E T e.g., neural networks. The goal is to find a Vo with compact representation to approximate the value function V* In this paper, we focus on general family of smooth functions, which may not be linear in 0.
3 TDC with Non-Linear Function Approximation
In this section, we introduce the TDC algorithm with general smooth function approximation in [Bhatnagar et al. 2009) for the off-policy setting with both i.i.d. samples and Markovian samples, and further characterize the hon-asymptotic error bounds.
Consider the the following mean-squat projected Bellman error (MSPBE):
J(0) Epp- [IVo()) [o
where Stt is the stationary distribution induced by the policy æ, and HI is the orthogonal projection onto the tangent plane of Vo at 0: (v((s) E R& and V((()) = (o((s){) and (o(s) = (s).
Note that the projection is onto the tangent plane instead of {Ve 0 E R² since the projection onto the latter one may not be computationally tractable if V8 is non-linear.
In [Bhatnagar et al. 2009], the authors proposed a two scale TDC algorithm to minimize the MSPBE J(0). Specifically, a stochastic gradient descent approach is used with the weight doubling trick (for the double sampling problem) [Sutton et al.] [009a]] which yield a two time-scale update rule. We note that the algorithm developed in [Bhatnagar al. 2009) was for the on-policy setting with i..dd samples from the stationary distribution, and the asymptotic convergence of the algorithm to stationary points established.
In the off- off-policy setting, the goal is to estimate the value function V of the target policy л using the samples from different behavior policy xb. In this case, the MSPBE can be written as
(()) = E (o(s) IIT" (s)
and we use the approach of importance sampling. Following steps similar to those in Maei 2011 J(f) can be further written as
((] En jp(S, A)ōs.A.s (O) AT [p(,
(4)
where (0) r(s, a, s') + (V Vo(s) the TD error. (s) VVa(s) the character
vector, p(8, a) a(als) is the importance sampling ratio for a given sample O = (s, r, 8') and
Ta[a|s]
Ag En [ds (S))
To compute (())). we consider its i-th entry, i.e, the partial derivative w.r.t. the i-th entry of #:
(0)
00
O Ogi (pō))
0 Ogi (00
--Epbb
Aō 'pp [pōd] + (p5 T
(Ap'Epr Epro (poø)).
(n)
(b)
where to simplify notations, we omit the dependence on 0, S, A and S'. To get an unbiased estimate of the terms in (5), several independent samples are needed, but this is not applicable when there is only one sample trajectory. Hence employ the weight doubling trick [Sutton et al. 2009a]. Define w())= A A (p(S, A)ds,A.s (S)) then term (a) can be written as follows:
i - E
00 (poo))
Ag A Enr, [póØ]

---

Euu (p(r(1o((")): (cbo w(O) Bapr [no(v w()); (6)
and term (b) can be written as follows:
(Ø6)) ) (Ap (Ar (oōci) 2B @ (oTW0X) 20 Φ J000s
(A (poet) T Ey
(7)
(00
Hence the gradient can be re-written (J( Ex
- A)oo w()).
where h) E, m. (()(5,)),,,..... - (S)) Thus with this weight doubling trick [Suttonn et al. 2009a], a two time-scale stochastic gradient descent algorithm can be constructed. In Algorithm| we present the algorithm for the Markovian setting. The algorithm under the i.i.d.
setting is slightly different, hence we refer the readers to Algorithm 2 Appendix B
Algorithm 1 Non-Linear Off-Policy TDC under the Markovian Setting
Input: T, a, 8, n, Tb. (Vol0 E ] Initialization: 0g.w0
1: Choose W ~ Uniform(O, (0.,,..,,T11
2: for t= 0, 1, W do
3: Sample O2 = (*1; ae: re: 81+1) following Tb
4: 6e(O,) = r(t,, ae sc+1) + VV, Vo, (st)
m(a.(a.)
5: Pt (..))))))
6:
he(O,, wi) = (pt) - de, (s) (st) [w)) Vo (se)ar
TW: 7: Wi+1 IRR (wr + B( (st) (8t) We + (0)) (st)))
8: 0,+1 = 0. + a (prō (p:))(00)))0 (br) (8x) dp, (+1+1) (st) Tur - hi (Or, wi))
we
9: end for
Output: Ow
In Algorithm RR. (v) = arg minl j I. ||I w|ll denotes the projection operator, where R.,
Panuxe Co (Tmax + 7)C,) (the constants are defined in Section 3.I. As we will show (44) in
Au
the appendix that for any 0 E RR,, w(0) is always upper bounded by Rw, i.e., [|=(0]] < R... The projection step the algorithm is introduced mainly for the convenience of the analysis. Motivated by the randomized stochastic gradient method in [Ghadimi and Lan 2013), which is designed to analyze non-convex optimization problems, in this paper, we also consider a randomized version of the non-linear TDC algorithm. Specifically, let W be an independent random variable with uniform distribution over {0, I..., T 1}. We then run the non-linear TDC algorithm for steps and output Ow.
3.1 Non-asymptotic Error Bounds
In this section, we present our main results of the non-asymptotic error bounds on the convergence of the off off-policy non-linear TDC algorithm. Our results will be based on the following assumptions. Assumption (Boundedness and Smoothness). For any s E and any 0' E RRN,
[o(s)) S C.: Vo(s)l < D.,
[10o(s) S Co. Vo2s(s) V V2 (v)))))) (s) < Lv 0'11.
where Co, Co. Do and Ly are some positive constants.
follows that for any 0,0' RV Vo(s) Vor(s) S Calle 8'1, and (())(s) &er (s)ll D..110 - 8 We note that these assumptions are equivalent to the assumptions adopted the original non-linear TDC asymptotic convergence analysis [Batnagar et al. 22099.
From Assumption
and can be easily satisfied by appropriately choosing the function class {Vo- 0 E } For example, neural networks, these assumptions can be satisfied if the activation function Lipschitz and
smooth Du et al. 2019 Neyshabur 2017
Miyato et al. 2018
5

---

Assumption 2 singuuagul,,, For any A E RN,, XL (Aa) X > O, where (A) denotes the minimal eigenvalue of the matrix A and X, is positive constant.
Assumption 3 (Bounded Importance Sampling Ratio). For any (8, E x A, p(s,a) Pmaxsfor some positive constant Pmax-
m(als) [b(a]s]
S
The following assumption only needed for the analysis under the Markovian setting, and is widely used for analyzing the Markovian noise, c.g., [Wang and Zou 2020 Kaledin et al. 2020 Xu and Liang
202T Zou et al., 2019 Srikant and Ying [
Bhandan et al. 2018
Assumption (Geometric uniform ergodicityy) There exist some constants m > and E (0, 1) such that supses drv (P(s, = 180 = 8, ,²" S m any t > 0, where drv denotes the total-variation distance between the probability measures.
We then present the bounds on the convergence the TDC algorithm with general smooth function approximation in the following theorem.
Theorem 1. Consider the following step-sizes:
0 7 and B = (7t) where 1 S S 1 2
and O < b S a. Then, (I) under the i.i.d. setting,
[VJ((W) 1 0
(Tr- + -iiz) ; and (2)
under the Markovian setting, J[W( )l? ) = Ti-a + T
log T
log T
T
Here we only assume the order of the step-sizes in terms of T for simplicity, their exact assumptions on them can be found in Section B.3 and Section C.3 Similarly, we only provide the order of the bounds here, and the explicit bounds can be found (86) and (133) in the appendix. can be seen that the rate under the Markovian setting is slower than the one under the i.i.d. setting by a factor of
log which is essentially the mixing time introduced by the dependence of samples.
Theorem characterizes the dependence between convergence rate and the step-sizes a and B. We also optimize over the step-sizes in the following corollary.
Corollary 1. Let a = b= 3.4 i.e., 3 = O(L/VT), then (1) under the i.i.d. setting, [V]()) O(1/VT); and (2) under the Markovian setting, [[v )|2 Ollo T/VT).
Remark 1. Our result matches with the sample complexity for the batch-based algorithm in [u and Liang 2021]. But their work requires a large batch size of O(e-1) to control the bias and variance, while ours only needs convergence rate. We note that by setting the batch size being one in [Xu and Liang) 2021] their desired sample complexity cannot be obtained, and their error bound will be constant. To obtain our non-asymptotic bound and sample complexity for the non-linear TDC algorithm, we develop a novel and more refined analysis on the tracking error, which will be discussed in the next section. Moreover, our result matches with the convergence rate of solving general non-convex optimization problems using stochastic gradient descent in [Ghadimi and Lan 2013]. Compared to their work, our analysis is more challenging due to the two time-scale structure and the gradient bias from the Markovian noise and the tracking error.
sample in each step to update 0 and and can still obtain the same
Remark 2. Some analyses on two time-scale stochastic approximation bound the tracking error in resulting in a convergence
terms of g. and require g - 0 in order to drive the tracking
rate of O (3+ (3+ [Borkar 2009 In this paper, we develop a much tighter bound on the tracking error in terms of the slow scale parameter (.)).. Therefore, the tracking error in our analysis is driven zero by (.(@)) > 0 not - 0. Similar results that do not need a 0 can also be found, e.g., in [Konda et al. 2004| Kaledin et al. 2020). We would like to point out that the techniques in [Konda et al. 2004 Kaledin et al. [020] cannot be applied in our analysis due to the non-linear two time-scale updates this paper.
4 Proof Sketch
In this section, we provide outline of the proof of Theorem 1 under the Markovian setting, and highlight our major technical contributions. For the complete proof of Theorem T we refer the readers to Appendices B.2 and C.2

---

Let Or = (st, dg, ft, s(+1) be the sample observed at time t. Denote the tracking error by 2 Wi - -w(O),, which characterizes the eтror between the fast time-scale update and its limit if the slow time-scale update 0, is kept fixed and only the fast time-scale is being updated. Denote by G++1 w) - (0):(0)
( (s)( " We - (4,0ww) Denote by the mixing time of the MDP, i.c., T f min {t mx' 8}.
Step In this step, we decompose the enror of gradient norm into two parts: the stochastic bias and the tracking error. We first show in Appendix that J(0) is -mooohh: for any 01, 02 E R
[V:) (.2(2)) - L, 1 02l1.
We note that the smoothness of J()) is also used in Xu and Liang 2021], which, however, is assumed instead of being proved as in this paper. then follows that
| - -(0,))))))))))))) - NI
Get1
G. Go,1(O,,
(0)
+a VJ())). V((O.)
LJ 2 + G.+ G++1(0,,((O))) + +2 a (111+++
(10)
This implies that the error bound on the gradient norm controlled by the tracking error (a) which is introduced by the two time-scale update rule, and the stochastic bias (b) which is due to the time- varyeign projection and the Markovian sampling.
Step 2. We first bound the tracking error Re-write the update of wi in terms of 2t 2++1 2, + 3 (- (o,, (st) + (0.)) + w(+)) w(0+11), where Ag, (st) do, (s)) (s,) and b,(0,) (8t). From the Lipschitz continuity of ((), it follows that
- -A (O)) +
|| | Il S (1 + ( + B(bmax + L7 Cg),
z1| S 8C | 3(bmax + Cg),
(11)
which further implies
E [|| 21 |
=|
222 (ze+1 + BAg z1) +0 (B"B[1=z|1 + BPP) + BB [2zr (- Ao,
(12)
(c)
where the last term in (12 can be further upper bounded by -,
One challenging part in our analysis is to bound term (c). Equivalently, decompose the following term into three parts:
(-
1 (2t+1 - -
E
Zt
Ao
w(O,) ((1+1)
E
Ao, + Ao, (80))2c)
-E2,, (e.))
E
2,
(13)
B
(d)
(F)
Consider term (d) in 13 Unlike the case with linear function approximation, where the character function (V) = ((s) is independent with 0, here the character function de(s) depends on 0. We use the geometric uniform ergodicity property of the MDP and the Lipschitz continuity of Ag and (s(s) to decouple the dependence. More specifically, for any fixed 8, [{))(s:)] converges to Ag as t increases. Let TB. then have that
E
27g (-Aa, + An.p 1)²9)
E 120 (-As,, + Ao, (Srg )20)} E 20 T
( (-Ao-g + Ao ($rg) Ao,, Aa, (Srg Ao, 1))
(ZrH 20) (- + Ao (STO)) 20)] + 2F (Erg 20)T (- (-Aor, + Aor, ))0
E
(14)
7

---

which can be further bounded using the mixing time 7B and the Lipschitz property of As and As(srg)
We note that from the update of 2t, we can bound 12 - =o and ||= by || |l hence the bound in (14) can be bounded in terms of || Il-
Similarly, note that [6,, (0) converges to 0 as co, then we can also bound term (e) in 13
E 2 D (0+,)) )] = [( - z0) bra (0r, )] + Eizg Dra (f6) + Elzd (6,, (6r,) - D (fo))] (15)
which can be similarly bounded in terms of |270 ll-
The challenge of bounding the third term (f) in 13) lies in bounding the difference between ((t)) and (((+1). One simple approach is to use the Lipschitz continuity w and bound ||0, out1 by constant of order ((a), but this will lead to a loose bound because the update G++1 (6,, wi) is
actually an estimator of the gradient, which will also converge to zero. The key idea in our analysis is to bound term (f) in terms of the gradient of the objective function VJ((O). Specifically, we first rewrite term (2e; ((,) w((++1)) -(2,, (w((0)(B Oe)) [Va(V
where 0, c0, + (1 c)0++1 for some e [0, 1]. It can be shown that
w(OT)) 11 =
-
a
Vu (G WTo) - ((0.,
Tp
B
a
T Frg
(w((rp)
(rp+ VJ(0+,)
+
E
T 773
vw(
VJ((OT.)
3
2
2
(16)
The first term in (16) can be bounded in terms of || Erg 2| using the Lipschitz property of G (0. w)
in w. The second term can be bounded using the uniform ergodicity of the MDP and the Lipschitz
property of =J (w) (Go (0)) (J in 0. The third term can be bounded in terms of
|| 1 and J 1 Combining all bounds together, we have the bound term (f) in (3
((rg) w(O
E
TTB
0
a
E
|| [1]] + O [ || +0 +0
E
VJ
V
||3]
(17)
3
83
We combine all the bounds terms (d), (e) and (f) and hence get the error bound on
13
E
bt
-- 2t
0(8rs) + o 1 I(am - 21) < <ol (3 E 21 0
{ E [
(18)
Plugging the above bound in 12) we have the following recursive bound on the tracking error:
|| < 01 8) [|==|]]] + O(a)E [I [[())) + TB)9T)).
(19)
Then by recursively applying the incquality in and summing up w.r.t. t from to 1, we obtain the bound on the tracking error Et-
1//:
ET' T
El 21 <
1 T3
E V +Br3)
T
Step 3. In this step bound the stochastic bias term E (VJ(()), =ejee + (0,, Similarly, we add and subtract (06) and Grg+ (00, (00)). and obtain that
(
VJ((..))
((((T))
+ G Gro+1 ((r.))())..077))))
2
= -(VJ((b), (J((o)
2 + Gr,42(0b, ((0))) + ((TJ(Om))
VJ(O-))
+ (00t1(0,,
2
8

---

V((()), VJ((b)) 2
(0++1(...(00))))
(20)
which again can be bounded using the geometry uniform ergodicity of the MDP and the Lipschitz continuity of (O)) (J(0) + (Q,))((0,000))
Step 4. Plugging in the bounds the tracking and the stochastic bias and rearranging the
terms, then it follows that Σre ETn' [(
I UV Eiso ( + V, where and V are
some constants depending on the step sizes, and the explicit definitions can found in (132 By (e.)li) we obtaín that
solving the inequality > 7
V T
1 (T8 + T3
1 Ta
0O
+ aTg +
5 Conclusion
In this paper, we extend the on-policy non-linear TDC algorithm to the off-policy setting, and characterize its non-asymptotic error bounds under both the i.i.d. and the Markovian settings. We show that the non-linear TDC algorithm converges as fast O(1vvT) (up factor of log T'). The techniques and tools developed in this paper can be used to analyze a wide range of value-based RL algorithms with general smooth function approximation.
Limitations: is not clear yet whether the stationary points that the TDC converges to are second- order stationary potentially saddle points.
Negative social impacts: This work theoretical investigation of some fundamental RI. algorithms, and therefore, the authors do not foresee any negative societal impact.
6
Acknowledgment
The work of Yue Wang and Shaofeng Zou was supported in part by the National Science Foundation under Grants CCF-2106560 and CCF-2007783. Yi Zhou's 's work was supported in part by U.S. National Science Foundation under the Grant CCF-2106216.

---

References
TW Archibald, KIM McKinnon, and LC Thomas. On the generation of Markov decision processes. Journal of the Operational Research Society, 46(3):354-361, 1995.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings, pages 30-37. Elsevier, 1995.
Dimitri P Bertsekas. Dynamic programming and optimal control 3rd edition, volume Belmont, MA: Athena Scientific, 2011.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Proc. Annual Conference Learning Theory (CoLT), pages 1691-1692. PMLR, 2018.
Shalabh Bhatnagar, Doina Precup, David Silver, Richard S Sutton, Hamid Maei, and Csaba Szepesvári. Convergent temporal-different learning with arbitrary smooth function approximation. In Proc. Advances in Neural Information Processing Systems (NIPS), volume 22, pages 1204-1212, 2009.
Vivek S Borkar. Stochastic approximation: dynamical systems viewpoint, volume 48. Springer, 2009.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-difference learning con- verges to global optima. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 11312-11322, 2019.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analysis of two-ttoomme tro-timescale stochastic approximation with applications reinforcement learning. Proceedings of Machine Learning Research, 75:1-35, 2018.
Gal Dalal, Balazs Szorenyi, and Gugan Thoppe. tale two-timescale reinforcement learning with the tightest finite-time bound. In Proc. AAAI Conference on Artificial Intelligence (AAAI), pages 3701-3708, 2020.
Thinh T Doan. Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance. In Learning for Dynamics and Control, pages 47-47. PMLR, 2021.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima deep neural networks. In Proc. International Conference on Machine Learning (ICML), pages 1675-1685. PMLR, 2019.
Saced Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):3341-2368, 2013.
Harsh Gupta, R Srikant, and Lei Ying. Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning. In Proc. Advances Neural Information Processing Systems (NeurIPS), pages 17700-4715.1 2019.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05170. 2020.
Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with Markovian noise. In Proc. Annual Conference on Learning Theory (CoLT), pages 2144-2203. PMLR, 2020.
Prasenjit Karmakar and Shalabh Bhatnagar. Two time-scale stochastic approximation with controlled Markov noise and off-policy cemporal-differene learning. Mathematics of Operations Research. 43(1):130-151, 2018.
Vijay R Konda, John Tsitsiklis, et al. Convergence rate of linear two-time-scale stochastic approximation. The Annals of Applied Probability, 14(2):79--819) 2004.
10

---

Chandrashekar Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In Proc. International Conference on Artificial Intelligence and Statistics, pages 1347-1355, 2018.
Bo Liu, Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient TD algorithms. In Proc. International Conference Uncertainty in Artificial Intelligence (UAI), pages 504-513. Citeseer, 2015.
Shaocong Ma, Yi Zhou, and Shaofeng Zou. Variance-reduced off-policy TDC learning: Non- asymptotic convergence analysis. In Proc. Advances Neural Information Processing Systems (NeurIPS), volume 33, pages 14796-14806, 2020.
Shaocong Ma. Yi Zhou, and Shaofeng Zou. Greedy-GQ with variance reduction: Finite-time analysis and improved complexity. In Proc. International Conference on Learning Representations (ICLR), 2021.
Hamid Reza Maei. Gradient temporal-differeee, learning algorithms. Thesis, University of Alberta, 2011.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S Sutton. Toward off off-policy learning control with function approximation. In Proc. International Conference on Machine Learning (ICML), pages 719-726, 2010.
Francisco S Melo, Sean P Meyn, and Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proc. International Conference Machine Learning (ICML), pages 664-671. ACM, 2008.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In Proc. International Conference on Learning Representations (ICLR), 2018.
Abdelkader Mokkadem, Mariane Pelletier, et al. Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms. The Annals of Applied Probability, 16(3): 1671-1702, 2006.
Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint arXiv:1709.000 2017.
Theodore J Perkins and Doina Precup. A convergent form of approximate policy iteration. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 1627-1634, 2003.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Proc, Annual Conference on Learning Theory (CoLT), pages 2803-2830. PMLR, 2019.
Jun Sun, Gang Wang, Georgios B Giannakis, Qinmin Yang, and Zaiyue Yang. Finite-sample analysis of decentralized temporal-difiie difference learning with linear function approximation. In Proeedings of the International Workshop on Artificial Intelligence and Statistics, 2020.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction, Second Edition. The MIT Press, Cambridge, Massachusetts, 2018
Richard S Sutton, Hamid R Maei, and Csaba Szepesvári. A convergent (n)) temporal-difference algorithm for off- -ooicy learning with linear function approximation. Proc. Advances Neural Information Processing Systems (NIPS), pages 1609-1616, 2009a.
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar. David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for remporal-differene learn- ing with linear function approximation, In Proc. International Conference on Machine Learning (ICMI), pages 993-1000, 2009b.
John Tsitsiklis and Benjamin Van Roy. analysis of defforal- learning with function approximation. IEEE transactions automatic control, 42(5):677-660, 1997.
11

---

Yue Wang and Shaofeng Zou. saitle analysis of greedy-GQ with linear function approxi- mation under Markovian noise. In Proc. International Conference on Uncertainty Artificial Intelligence (UAI), pages 11 11-20. PMLR, 2020.
Yue Wang. Wei Chen, Yuting Liu, Zhi-Ming Ma, and Tie-Yan Liu. Finite sample analysis of the GTD policy evaluation algorithms in Markov setting. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 5504-5513, 2017.
Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite time analysis of two time-scale actor critic methods. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Pan Xu and Quanquan Gu. A finite-time analysis of Q-learning with neural network function approximation. In Proc. International Conference on Machine Learning (ICML), pages 10555- 10565. PMLR, 2020.
Tengyu Xu and Yingbin Liang. Sample complexity bounds for two timescale value-based reinforce- ment learning algorithms. Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 811-819. PMLR, 2021.
Tengyu Xu. Shaofeng Zou, and Yingbin Liang. Two time-scale off off-policy TD learning: Non- asymptotic analysis over Markovian samples. Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 10633-10643) 2019.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for SARSA with linear function approximation. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 8665-8675, 2019.
12


Reviews:
[{"review_id": "mHcYmpTl623", "reviewer": "Reviewer_SQEZ", "summary": "This paper analyses the convergence of two time-scale TDC with general smooth function approximation. Previous analysis mainly focuses the linear approximation, but the nonlinear approximation is more powerful and its convergence analysis is more challenging; thus, this work is theoretically solid. The analysis covers both i.i.d. settings and Markov settings. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper analyses the convergence of two time-scale TDC with general smooth function approximation. Previous analysis mainly focuses the linear approximation, but the nonlinear approximation is more powerful and its convergence analysis is more challenging; thus, this work is theoretically solid. The analysis covers both i.i.d. settings and Markov settings. \n\nNo empirical study is carried out. If some reinforcement learning tasks are conducted to verify the theory, the results can be more convincing. \n\n1.\tIt is mentioned that the projection step in Line 6 of algorithm 1 is for the convenience of the analysis. So, does removing the projection destroy the convergence or yield a worse convergence rate? \nTypo: Line 103, Page 3, resent.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "lhbdXikiSHi", "reviewer": "Reviewer_zbSi", "summary": "This paper develops the non-asymptotic error bound for an important RL algorithm TDC with general non-linear function approximation. The TDC algorithm is a commonly used one for off-policy policy evaluation in practice. Existing studies on non-asymptotic error bound mostly focus on the case with linear function approximation. This work extends the study to the case with non-linear function approximation. Several new challenges are addressed in this paper, the nonconvexity of the objective function, non-linear two time-scale update rule, time-varying projection and a tight tracking error analysis. Both the iid and Markovian settings are investigated. The convergence rate provided is $\\mathcal O(1/\\sqrt(T))$.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Pros:\n1. The proof generalizes the analysis for nonconvex optimization in [Ghadimi & Lan 2013] to the  TDC algorithm with a two time-scale structure, where the tracking error due to the two time-scale updates needs to be bounded, which is also their major technical novelty in the analysis. They bound the tracking error using the gradient norm $E[\\|\\nabla J(\\theta_t)\\|^2]$, which should also converge to zero. Other analysis of two time-scale algorithms either use a constant bound (resulting in a loose bound in the end) or using a mini-batch method (resulting in a large batch size ($1/\\epsilon$). Their idea of bounding the tracking error using $E[\\|\\nabla J(\\theta_t)\\|^2]$, which is the quantity that is being bounded, is novel and interesting. This technique could be useful for developing non-asymptotic error bound of other two time-scale algorithms with a non-convex objective function. \n\n2. Another novelty lies in the way they handle dependency between the projection tangent plane and the sample trajectory. For most existing studies with linear function approximation, the projection is fixed, and there does not exist such an issue. They first characterized the geometry of those functions, and then decoupled the dependency by exploiting the smoothness of the function approximator.\n\nCons:\nThere is no significant difference between the iid setting and the Markovian setting. The approach of handling the Markovian noise using a mixing argument is kind of standard in the current RL literature.\n\nQuality: The complexity of $\\mathcal O(1/\\sqrt(T))$ looks natural. This result matches with the complexity of optimizing a general smooth non-convex function in [Ghadimi & Lan 2013]. The proof looks correct. \n\nClarity: This paper is well-written. I enjoyed reading this paper. The proof of sketch part is clear and informative, where the major steps and technical novelty are highlighted. The table of contents in the appendix is helpful to navigate in the appendix. \n\nSignificance: As discussed above, the idea of bounding the tracking error using the gradient norm is novel, and is useful for analyzing other two time-scale algorithms with non-convex objectives.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some comments/questions are also listed below.\n\n1. The experiments could be moved to the main body of the paper as there is still room. \n\n2. In remark 2, it is discussed that the ratio $\\alpha/\\beta$ does not necessarily need to go to zero (in this paper alpha and beta are chosen to be constant at the order of $O(1/\\sqrt(T)$). This is kind of counterintuitive. Some more elaboration on this issue could help.\nIn assumption 4, it is assumed that the MDP is uniformly ergodic. It is kind of a standard assumption in RL analysis when there is Markovian noise. It would be helpful to discuss what kind of MDPs satisfy this assumption.\n\n3. Figs 4 and 5 in the appendix shall be aligned. \n\n4. Page 25, it is assumed that the step size $\\beta$ satisfies some condition $\\beta\\tau_\\beta C_\\phi^2\\leq 1/4$, which should also be stated in the theorem. ", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "8ATsRnJGxfe", "reviewer": "Reviewer_bpa2", "summary": "This paper provides finite-sample analysis on the two time-scale TDC algorithm with non-linear function approximation, proposed by [5] Bhatnagar et al. Both the i.i.d. setting and the Markovian setting are considered. The convergence rate is near-optimal given the target MSPBE function is generally non-convex.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is clearly written and easy to understand.  \n\nBased on the asymptotic results given in [5] Bhatnagar et al., it is natural to consider the finite-sample analysis and the non-asymptotic rate $1 / \\sqrt{T}$ achieved here is a bit surprisingly good. The downside though is that the whole analysis falls under the framework where the outside loop (the slower component $\\theta$) is to optimize a general non-convex function with stochastic gradients, while the inner loop (the faster component $\\omega$) is a linear stochastic approximation task (which is effectively strongly convex). Therefore the analysis can always be decomposed to first bounding the tracking error of the faster component $\\omega$ to the optimal solution $\\omega(\\theta)$ while the slower component only suffers a small loss from the tracking error aside from the classical non-convex SGD analysis. The Markovian setting is great but also suffers from a similar novelty issue since there has been plenty of previous works dealing with the Markov noise under the uniform ergodicity assumption. \n\nOne suggestion is that the arguments in Line 539 and Line 594 that requires $\\alpha$ to be much smaller than $\\beta$ need to be stated more clearly, because there are too many constants involved there and it is better to write down an assumption on the ratio $\\alpha / \\beta$.  \n\nIt would help highlight the technical contribution if the author can also compare the two time-scale techniques used here with those in some previous works:\n1. (this presents the non-convex outer loop + convex inner loop framework) A Finite-Time Analysis of Two Time-Scale Actor-Critic Methods. NIPS'20 \n2. (a more general formulation) A Two-Timescale Stochastic Algorithm Framework for BilevelOptimization:  Complexity Analysis and Application to Actor-Critic. Arxiv 2007.05170\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors pointed out the limitation that the target function is generally non-convex and therefore this paper can only guarantee convergence toward a saddle point rather than a global minimum. There are no specific concerns with respect to its social impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides non-asymptotic analysis for TDC algorithm with general smooth function approximation, which is technically sound and novel. The authors’ responses have well addressed the reviewers’ concerns. All the reviewers have reached a consensus on the acceptance of this work. We suggest that the authors further polish their paper to prepare a camera-ready version based on the reviewers’ comments.
Decision: Accept (Poster)