Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation

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 O(1/ √ T ) (up to a factor of O(log T )). Our approach can be applied to a wide range of value-based reinforcement learning algorithms with general smooth function approximation.

text: √ T ) (up to a factor of O(log T )). Our approach can be applied to a
wide range of value-based reinforcement learning algorithms with general smooth function approximation.

heading: 1 Introduction
text: In reinforcement learning (RL), an agent interacts with a stochastic environment in order to maximize the total reward [Sutton and Barto, 2018]. Towards this goal, it is often needed to evaluate how good a policy performs, and more specifically, to 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, 1995, Tsitsiklis and Van Roy, 1997]. To address this issue, a family of gradient-based TD (GTD) algorithms, e.g., GTD, GTD2, temporal-difference learning with gradient correction (TDC) and Greedy-GQ, were developed for the case with linear function approximation [Maei, 2011, Sutton et al., 2009b, Maei et al., 2010, Sutton et al., 2009a,b]. These algorithms were later extended to the case with general smooth function approximation in [Bhatnagar et al., 2009], 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 (NeurIPS 2021).
recently have the non-asymptotic error bounds for these algorithms been investigated, e.g., [Dalal et 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-linear TDC) for both i.i.d. and Markovian samples. Technically, the analysis in this paper is not a 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 is 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 a timevarying 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.

heading: 1.1 Challenges and Contributions
text: 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 on two time-scale stochastic approximation, e.g., [Konda et al., 2004, Gupta et al., 2019, Kaledin et al., 2020] and the studies of linear GTD algorithms in [Xu et al., 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-linear 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 value-based 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 a general smooth class of functions usually does not have a closed-form 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 a 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., 2004], where a linear transformation can asymptotically decouple the dependence between the fast and slow time-scale updates, it is non-trivial to construct such a transformation for non-linear updates. To develop a tight bound on the tracking error, we develop a novel technique that bounds the tracking error as a function of the gradient of the MSPBE. This leads to a 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]. Although we do not decouple the fast and slow time-scale updates, we still obtain a desired convergence rate of O(1/ √ T ) (up to a factor of log T ), which matches with the complexity of stochastic gradient descent for non-convex problems [Ghadimi and Lan, 2013].

heading: 1.2 Related Work
text: TD, Q-learning and SARSA. The asymptotic convergence of TD with linear function approximation was shown in [Tsitsiklis and Van Roy, 1997], and the non-asymptotic analysis of TD was developed in [Srikant and Ying, 2019, Lakshminarayanan and Szepesvari, 2018, Bhandari et al., 2018, Dalal et al., 2018, Sun et al., 2020]. Moreover, [Cai et al., 2019] 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 in [Melo et al., 2008, Perkins and Precup, 2003]. Their non-asymptotic error bounds were also studied in [Zou et al., 2019]. The non-asymptotic 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 a two time-scale algorithm.
GTD methods with linear function approximation. A class of GTD algorithms were proposed to address the divergence issue for off-policy training [Baird, 1995] and arbitrary smooth function approximation [Tsitsiklis and Van Roy, 1997], e.g., GTD, GTD2 and TDC [Maei, 2011, Sutton et al., 2009b, Maei et al., 2010, Sutton et al., 2009a,b]. Recent studies established their non-asymptotic 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 al., 2020, Kaledin et al., 2020, Ma et al., 2020, 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-linear, the objective is non-convex, and the projection is time-varying, and thus new techniques are required to develop the non-asymptotic analysis.
Non-linear two time-scale stochastic approximation. There are also studies on asymptotic convergence 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 on 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-linear TDC in [Xu and Liang, 2021], where at each update, a batch of samples is used. To achieve a sample complexity of O( −2), a batch size of O( −1) is required in [Xu and Liang, 2021] to control the bias and variance. We note that by setting the batch size being one in [Xu and Liang, 2021], 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 an 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 O( −1) while still achieving the same sample complexity.

heading: 2 Preliminaries

heading: 2.1 Markov Decision Process
text: A Markov decision process (MDP) is a tuple (S,A,P, r, γ), where S and A are the state and action spaces, P = P(s′|s, a) is the transition kernel, r : S×A× S→ R+ is the reward function bounded by rmax, and γ ∈ [0, 1] is the discount factor. A stationary policy π maps a state s ∈ S to a probability distribution π(·|s) over the action space A. At each time-step t, suppose the process is at some state st ∈ S, and an action at ∈ A is taken. Then the system transits to the next state st+1 following the transition kernel P(·|st, at), and the agent receives a reward r(st, at, st+1). For a given policy π and any initial state s ∈ S, we define its value function as V π (s) = E [ ∑∞ t=0 γ
tr(St, At, St+1)|S0 = s, π]. The goal of policy evaluation is to use the samples generated from the MDP to estimate the value function. The value function satisfies the Bellman equation: V π(s) = TπV π(s) for any s ∈ S, where the Bellman operator Tπ is defined as
TπV (s) = ∑
s′∈S,a∈A
P(s′|s, a)π(a|s)r(s, a, s′) + γ ∑
s′∈S,a∈A
P(s′|s, a)π(a|s)V (s′). (1)
Hence the value function V π is the fixed point of the Bellman operator Tπ [Bertsekas, 2011].

heading: 2.2 Function Approximation
text: In practice, the state space S usually contains a large number of states or is even continuous, which will induce a heavy computational overhead. A popular approach is to approximate the value function using a parameterized class of functions. Consider a parameterized family of functions{ Vθ : S→ R|θ ∈ RN } , e.g., neural networks. The goal is to find a Vθ with a compact representation in θ to approximate the value function V π. In this paper, we focus on a general family of smooth functions, which may not be linear in θ.

heading: 3 TDC with Non-Linear Function Approximation
text: 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 non-asymptotic error bounds.
Consider the the following mean-square projected Bellman error (MSPBE): J(θ) = Eµπ [ ‖Vθ(s)−ΠθTπVθ(s)‖2 ] , (2)
where µπ is the stationary distribution induced by the policy π, and Πθ is the orthogonal projection onto the tangent plane of Vθ at θ: { V̂ζ(s)|ζ ∈ RN and V̂ζ(s) = φθ(s)>ζ } and φθ(s) = ∇Vθ(s).
Note that the projection is onto the tangent plane instead of { Vθ : θ ∈ RN } since the projection onto the latter one may not be computationally tractable if Vθ is non-linear.
In [Bhatnagar et al., 2009], the authors proposed a two time-scale TDC algorithm to minimize the MSPBE J(θ). Specifically, a stochastic gradient descent approach is used with the weight doubling trick (for the double sampling problem) [Sutton et al., 2009a], which yield a two time-scale update rule. We note that the algorithm developed in [Bhatnagar et al., 2009] was for the on-policy setting with i.i.d. samples from the stationary distribution, and the asymptotic convergence of the algorithm to stationary points was established.
In the off-policy setting, the goal is to estimate the value function V π of the target policy π using the samples from a different behavior policy πb. In this case, the MSPBE can be written as
J(θ) = Eµπb [‖Vθ(s)−ΠθTπVθ(s)‖2], (3) and we use the approach of importance sampling. Following steps similar to those in [Maei, 2011], J(θ) can be further written as
J(θ) = Eµπb [ρ(S,A)δS,A,S′(θ)φθ(S)]>A−1θ Eµπb [ρ(S,A)δS,A,S′(θ)φθ(S)], (4)
where δs,a,s′(θ) = r(s, a, s′) + γVθ(s′) − Vθ(s) is the TD error, φθ(s) = ∇Vθ(s) is the character vector, ρ(s, a) = π(a|s)πb(a|s) is the importance sampling ratio for a given sample O = (s, a, r, s
′) and Aθ = Eµπb [φθ(S)φθ(S)>]. To compute ∇J(θ), we consider its i-th entry, i.e., the partial derivative w.r.t. the i-th entry of θ:
− 1 2 ∂J(θ) ∂θi
= −Eµπb [ ∂
∂θi (ρδφ) ]> A−1θ Eµπb [ρδφ]︸ ︷︷ ︸
(a)
+ 1
2 (A−1θ Eµπb [ρδφ])
>Eµπb [ ∂
∂θi (φφ>) ] (A−1θ Eµπb [ρδφ])︸ ︷︷ ︸
(b)
,
(5)
where to simplify notations, we omit the dependence on θ, 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 we employ the weight doubling trick [Sutton et al., 2009a]. Define ω(θ) = A−1θ Eµπb [ρ(S,A)δS,A,S′(θ)φθ(S)] , then term (a) can be written as follows:
− Eµπb [ ∂
∂θi (ρδφ)
]> A−1θ Eµπb [ρδφ]
= −Eµπb [ρ(γ(φθ(S′))i − (φθ(S))i)φθ(S)] > ω(θ)− Eµπb [ ρδ(∇2V )i ]> ω(θ); (6)
and term (b) can be written as follows:
(A−1θ Eµπb [ρδφ]) >Eµπb
[ ∂
∂θi (φφ>)
] (A−1θ Eµπb [ρδφ]) = 2Eµπb [ φ>ω(θ)( ∂
∂θi φ>)ω(θ)
] . (7)
Hence the gradient can be re-written as
−∇J(θ) 2
= Eµπb [ρ(S,A)δS,A,S′(θ)φθ(S)]− h(θ, ω(θ))− γEµπb [ ρ(S,A)φθ(S ′)φθ(S) >]ω(θ),
(8) where h(θ, ω) = Eµπb [ ( ρ(S,A)δS,A,S′(θ)− φθ(S)>ω ) ∇2Vθ(S)ω]. Thus with this weight doubling trick [Sutton et al., 2009a], a two time-scale stochastic gradient descent algorithm can be constructed. In Algorithm 1, 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 in Appendix B.
Algorithm 1 Non-Linear Off-Policy TDC under the Markovian Setting Input: T , α, β, π, πb, { Vθ|θ ∈ RN } Initialization: θ0,w0
1: Choose W ∼ Uniform(0, 1, ..., T − 1) 2: for t = 0, 1, ...,W − 1 do 3: Sample Ot = (st, at, rt, st+1) following πb 4: δt(θt) = r(st, at, st+1) + γVθt(st+1)− Vθt(st) 5: ρt =
π(at|st) πb(at|st) 6: ht(θt, ωt) = ( ρtδt(θt)− φθt(st)>ωt ) ∇2Vθt(st)ωt
7: ωt+1 = ΠRω ( ωt + β ( − φθt(st)φθt(st)>ωt + ρtδt(θt)φθt(st) )) 8: θt+1 = θt + α ( ρtδt(θt)φθt(st)− γρtφθt(st+1)φθt(st)>ωt − ht(θt, ωt)
) 9: end for
Output: θW
In Algorithm 1, ΠRω (v) = argmin‖w‖≤Rω ‖v − w‖ denotes the projection operator, where Rω = ρmaxCφ λv
(rmax + (1 + γ)Cv) (the constants are defined in Section 3.1). As we will show in (44) in the appendix that for any θ ∈ RN , ω(θ) is always upper bounded by Rω, i.e., ‖ω(θ)‖ ≤ Rω. The projection step in 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 a uniform distribution over {0, 1, ..., T − 1}. We then run the non-linear TDC algorithm for W steps and output θW .

heading: 3.1 Non-asymptotic Error Bounds
text: In this section, we present our main results of the non-asymptotic error bounds on the convergence of the off-policy non-linear TDC algorithm. Our results will be based on the following assumptions. Assumption 1 (Boundedness and Smoothness). For any s ∈ S and any θ, θ′ ∈ RN ,
|Vθ(s)| ≤ Cv, ‖φθ(s)‖ ≤ Cφ, ‖∇2Vθ(s)‖ ≤ Dv, ‖∇2Vθ(s)−∇2Vθ′(s)‖ ≤ LV ‖θ − θ′‖,
where Cφ, Cv , Dv and LV are some positive constants.
From Assumption 1, it follows that for any θ, θ′ ∈ RN , |Vθ(s) − Vθ′(s)| ≤ Cφ‖θ − θ′‖, and ‖φθ(s)− φθ′(s)‖ ≤ Dv‖θ − θ′‖. We note that these assumptions are equivalent to the assumptions adopted in the original non-linear TDC asymptotic convergence analysis in [Bhatnagar et al., 2009], and can be easily satisfied by appropriately choosing the function class { Vθ : θ ∈ RN } . For example, in neural networks, these assumptions can be satisfied if the activation function is Lipschitz and smooth [Du et al., 2019, Neyshabur, 2017, Miyato et al., 2018].
Assumption 2 (Non-singularity). For any θ ∈ RN , λL (Aθ) ≥ λv > 0, where λL(A) denotes the minimal eigenvalue of the matrix A and λv is a positive constant.
Assumption 3 (Bounded Importance Sampling Ratio). For any (s, a) ∈ S×A, ρ(s, a) = π(a|s)πb(a|s) ≤ ρmax, for some positive constant ρmax.
The following assumption is only needed for the analysis under the Markovian setting, and is widely used for analyzing the Markovian noise, e.g., [Wang and Zou, 2020, Kaledin et al., 2020, Xu and Liang, 2021, Zou et al., 2019, Srikant and Ying, 2019, Bhandari et al., 2018].
Assumption 4 (Geometric uniform ergodicity). There exist some constants m > 0 and κ ∈ (0, 1) such that sups∈S dTV (P(st = ·|s0 = s, π), µπ) ≤ mκt, for any t > 0, where dTV denotes the total-variation distance between the probability measures.
We then present the bounds on the convergence of the TDC algorithm with general smooth function approximation in the following theorem.
Theorem 1. Consider the following step-sizes: α = O (
1 Ta
) , and β = O ( 1 T b ) , where 12 ≤ a ≤ 1
and 0 < b ≤ a. Then, (1) under the i.i.d. setting, ‖∇J(θW )‖2 = O ( 1 T 1−a + 1 T b + 1 T 1−b ) ; and (2)
under the Markovian setting, ‖∇J(θW )‖2 = O ( log T T 1−a + 1 T 1−b + log T T b ) .
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 in (86) and (133) in the appendix. It 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 T , which is essentially the mixing time introduced by the dependence of samples.
Theorem 1 characterizes the dependence between convergence rate and the step-sizes α and β. We also optimize over the step-sizes in the following corollary. Corollary 1. Let a = b = 12 , i.e., α, β = O(1/ √ T ), then (1) under the i.i.d. setting, ‖∇J(θW )‖2 =
O(1/ √ T ); and (2) under the Markovian setting, ‖∇J(θW )‖2 = O(log T/ √ T ).
Remark 1. Our result matches with the sample complexity for the batch-based algorithm in [Xu and Liang, 2021]. But their work requires a large batch size of O( −1) to control the bias and variance, while ours only needs one sample in each step to update θ and ω and can still obtain the same 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 a 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.
Remark 2. Some analyses on two time-scale stochastic approximation bound the tracking error in terms of αβ , and require α β → 0 in order to drive the tracking error to zero resulting in a convergence
rate of O ( β + αβ ) [Borkar, 2009]. In this paper, we develop a much tighter bound on the tracking error in terms of the slow time-scale parameter∇J(θ). Therefore, the tracking error in our analysis is driven to zero by∇J(θ)→ 0 not αβ → 0. Similar results that do not need α β → 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., 2020] cannot be applied in our analysis due to the non-linear two time-scale updates in this paper.

heading: 4 Proof Sketch
text: In this section, we provide an outline of the proof of Theorem 1 under the Markovian setting, and highlight our major technical contributions. For the complete proof of Theorem 1, we refer the readers to Appendices B.2 and C.2.
Let Ot = (st, at, rt, st+1) be the sample observed at time t. Denote the tracking error by zt = ωt − ω(θt), which characterizes the error between the fast time-scale update and its limit if the slow time-scale update θt is kept fixed and only the fast time-scale is being updated. Denote by Gt+1(θ, ω) , ρtδt(θ)φθ(st)− γρtφθ(st+1)φθ(st)>ωt− ht(θ, ω). Denote by τβ the mixing time of the MDP, i.e., τβ , min {t : mκt ≤ β}. Step 1. In this step, we decompose the error of gradient norm into two parts: the stochastic bias and the tracking error. We first show in Appendix A that J(θ) is LJ -smooth: for any θ1, θ2 ∈ RN ,
‖∇J(θ1)−∇J(θ2)‖ ≤ LJ‖θ1 − θ2‖. (9) 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. It then follows that
α 2 ‖∇J(θt)‖2≤J(θt)− J(θt+1) + α〈∇J(θt),−Gt+1(θt, ω(θt)) +Gt+1(θt, ωt)〉︸ ︷︷ ︸
(a)
+ α 〈 ∇J(θt),
∇J(θt) 2 +Gt+1(θt, ω(θt)) 〉 ︸ ︷︷ ︸
(b)
+ LJ 2 α2‖Gt+1(θt, ωt)‖2. (10)
This implies that the error bound on the gradient norm is 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-varying projection and the Markovian sampling.
Step 2. We first bound the tracking error. Re-write the update of ωt in terms of zt: zt+1 = zt + β (−Aθt(st)zt + bt(θt)) + ω(θt)− ω(θt+1), where Aθt(st) = φθt(st)φθt(st)> and bt(θt) = −Aθt(st)ω(θt) + ρtδt(θt)φθt(st). From the Lipschitz continuity of ω(θ), it follows that
‖zt+1‖ ≤ (1 + βC2φ)‖zt‖+ β(bmax + LωCg), ‖zt+1 − zt‖ ≤ βC2φ‖zt‖+ β(bmax + LωCg), (11)
which further implies E [ ‖zt+1‖2 − ‖zt‖2 ] ≤ E[2z>t (zt+1 − zt + βAθtzt)]︸ ︷︷ ︸
(c)
+O ( β2E[‖zt‖2] + β2 ) + βE [ 2z>t (−Aθt)zt ] , (12)
where the last term in (12) can be further upper bounded by −2βλvE[‖zt‖2]. One challenging part in our analysis is to bound term (c). Equivalently, we decompose the following term into three parts:
E [ z>t ( −Aθtzt − 1
β (zt+1 − zt) )] = E[z>t (−Aθt +Aθt(st))zt]︸ ︷︷ ︸
(d)
−E[z>t bt(θt)]︸ ︷︷ ︸ (e)
−E [ z>t
ω(θt)− ω(θt+1) β ] ︸ ︷︷ ︸
(f)
. (13)
Consider term (d) in (13). Unlike the case with linear function approximation, where the character function∇Vθ(s) = φ(s) is independent with θ, here the character function φθ(s) depends on θ. We use the geometric uniform ergodicity property of the MDP and the Lipschitz continuity of Aθ and Aθ(s) to decouple the dependence. More specifically, for any fixed θ, E[Aθ(st)] converges to Aθ as t increases. Let t = τβ , then we have that
E [ z>τβ (−Aθτβ +Aθτβ (sτβ ))zτβ ] = E [ z>0 (−Aθ0 +Aθ0(sτβ ))z0 ] + E [ z>0 (−Aθτβ +Aθτβ (sτβ ) +Aθ0 −Aθ0(sτβ )))z0
] + E [ (zτβ − z0)>(−Aθτβ +Aθτβ (sτβ ))(zτβ − z0) ] + 2E [ (zτβ − z0)>(−Aθτβ +Aθτβ (sτβ ))z0 ] ,
(14)
which can be further bounded using the mixing time τβ and the Lipschitz property of Aθ and Aθ(sτβ ). We note that from the update of zt, we can bound ‖zτβ − z0‖ and ‖z0‖ by ‖zτβ‖, hence the bound in (14) can be bounded in terms of ‖zτβ‖.
Similarly, note that E[bt(θ)] converges to 0 as t→∞, then we can also bound term (e) in (13):
E[z>τβbτβ (θτβ )] = E[(zτβ − z0) >bτβ (θτβ )] + E[z>0 bτβ (θ0)] + E[z>0 (bτβ (θτβ )− bτβ (θ0))], (15)
which can be similarly bounded in terms of ‖zτβ‖.
The challenge of bounding the third term (f) in (13) lies in bounding the difference between ω(θt) and ω(θt+1). One simple approach is to use the Lipschitz continuity of ω(θ) and bound ‖θt − θt+1‖ by a constant of order O(α), but this will lead to a loose bound because the update Gt+1(θt, ωt) 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 ∇J(θ). Specifically, we first rewrite term 〈zt, ω(θt)− ω(θt+1)〉 = −〈zt,∇ω(θ̂t)(θt+1 − θt)〉 = −α〈∇ω(θ̂t)Gt+1(θt, ωt)〉, where θ̂t = cθt + (1− c)θt+1 for some c ∈ [0, 1]. It can be shown that
E [ z>τβ ω(θτβ )− ω(θτβ+1) β ] = −α β E[z>τβ∇ω(θ̂τβ )(Gτβ+1(θτβ , ωτβ )−Gτβ+1(θτβ , ω(θτβ )))]
− α β E [ z>τβ∇ω(θ̂τβ ) ( Gτβ+1(θτβ , ω(θτβ )) + ∇J(θτβ ) 2 )] + α β E [ z>τβ∇ω(θ̂τβ ) (∇J(θτβ ) 2 )] .
(16)
The first term in (16) can be bounded in terms of ‖zτβ‖2 using the Lipschitz property of Gτβ+1(θ, ω) in ω. The second term can be bounded using the uniform ergodicity of the MDP and the Lipschitz property of z>0 ∇ω(θ) ( Gτβ+1(θ, ω(θ)) + ∇J(θ) 2 ) in θ. The third term can be bounded in terms of ‖zτβ‖2 and ‖∇J(θτβ )‖2. Combining all bounds together, we have the bound on term (f) in (13):∣∣∣∣E [z>τβ ω(θτβ )− ω(θτβ+1)β ]∣∣∣∣
≤ O ( α
β ) E [∥∥zτβ∥∥2]+ O (ατβ)E [∥∥zτβ∥∥]+ O (ατβ) + O( α8β ) E [∥∥∇J(θτβ )∥∥2] . (17)
We combine all the bounds on terms (d), (e) and (f) and hence get the error bound on (13): E [ z>t ( −Aθtzt − 1
β (zt+1 − zt)
)] ≤ O ( α
β
) E[‖zt‖2] + O(βτβ) + O ( α
β
) E[‖∇J(θt)‖2].
(18)
Plugging the above bound in (12), we have the following recursive bound on the tracking error: E [ ‖zt+1‖2 ] ≤ O(1− β)E [ ‖zt‖2 ] + O(α)E [ ‖∇J(θt)‖2 ] + O(β2τβ). (19)
Then by recursively applying the inequality in (19) and summing up w.r.t. t from 0 to T − 1, we obtain the bound on the tracking error ∑T−1 t=0 E[‖zt‖2]/T :∑T−1
t=0 E[‖zt‖2] T ≤ O
( 1
Tβ + α β
∑T−1 t=0 E[‖∇J(θt)‖2]
T + βτβ
) .
Step 3. In this step we bound the stochastic bias term E [〈 ∇J(θt), ∇J(θt)2 +Gt+1(θt, ω(θt)) 〉] . Similarly, we add and subtract∇J(θ0) and Gτβ+1(θ0, ω(θ0)), and obtain that〈 ∇J(θτβ ),
∇J(θτβ ) 2 +Gτβ+1(θτβ , ω(θτβ )) 〉 = 〈 ∇J(θ0),
∇J(θ0) 2 +Gτβ+1(θ0, ω(θ0))
〉 + (〈 ∇J(θτβ ),
∇J(θτβ ) 2 +Gτβ+1(θτβ , ω(θτβ ))
〉
− 〈 ∇J(θ0),
∇J(θ0) 2 +Gτβ+1(θ0, ω(θ0))
〉) , (20)
which again can be bounded using the geometry uniform ergodicity of the MDP and the Lipschitz continuity of 〈 ∇J(θ), ∇J(θ)2 +Gτβ+1(θ, ω(θ)) 〉 .
Step 4. Plugging in the bounds on the tracking error and the stochastic bias and rearranging the terms, then it follows that ∑T−1 t=0 E[‖∇J(θt)‖
2] T ≤ U
√∑T−1 t=0 E[‖∇J(θt)‖2]
T + V, where U and V are some constants depending on the step sizes, and the explicit definitions can be found in (132). By
solving the inequality of ∑T−1 t=0 E[‖∇J(θt)‖
2] T , we obtain that∑T−1
t=0 E[‖∇J(θt)‖2] T
≤ O ( βτβ + 1
Tβ + ατβ +
1
Tα
) .

heading: 5 Conclusion
text: 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 as O(1/ √ T ) (up to a 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: It is not clear yet whether the stationary points that the TDC converges to are secondorder stationary or potentially saddle points.
Negative social impacts: This work is a theoretical investigation of some fundamental RL algorithms, and therefore, the authors do not foresee any negative societal impact.

heading: 6 Acknowledgment
text: 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 work was supported in part by U.S. National Science Foundation under the Grant CCF-2106216.

Review summaries:
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.

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.   

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))$.