Title: REANALYSIS OF VARIANCE REDUCED TEMPORAL DIF-FERENCE LEARNING

Abstract: Temporal difference (TD) learning is a popular algorithm for policy evaluation in reinforcement learning, but the vanilla TD can substantially suffer from the inherent optimization variance. A variance reduced TD (VRTD) algorithm was proposed by Korda and La (2015) , which applies the variance reduction technique directly to the online TD learning with Markovian samples. In this work, we first point out the technical errors in the analysis of VRTD in Korda and La (2015) , and then provide a mathematically solid analysis of the non-asymptotic convergence of VRTD and its variance reduction performance. We show that VRTD is guaranteed to converge to a neighborhood of the fixed-point solution of TD at a linear convergence rate. Furthermore, the variance error (for both i.i.d. and Markovian sampling) and the bias error (for Markovian sampling) of VRTD are significantly reduced by the batch size of variance reduction in comparison to those of vanilla TD. As a result, the overall computational complexity of VRTD to attain a given accurate solution outperforms that of TD under Markov sampling and outperforms that of TD under i.i.d. sampling for a sufficiently small conditional number.

1. INTRODUCTION:

In reinforcement learning (RL), policy evaluation aims to obtain the expected long-term reward of a given policy and plays an important role in identifying the optimal policy that achieves the maximal cumulative reward over time Bertsekas and Tsitsiklis (1995) ; Dayan and Watkins (1992) ; Rummery and Niranjan (1994) . The temporal difference (TD) learning algorithm, originally proposed by Sutton (1988) , is one of the most widely used policy evaluation methods, which uses the Bellman equation to iteratively bootstrap the estimation process and continually update the value function in an incremental way. In practice, if the state space is large or infinite, function approximation is often used to find an approximate value function efficiently. Theoretically, TD with linear function approximation has been shown to converge to the fixed point solution with i.i.d. samples and Markovian samples in Sutton (1988) ; Tsitsiklis and Van Roy (1997) . The finite sample analysis of TD has also been studied in Bhandari et al. (2018) ; Dalal et al. (2018a) ; Cai et al. (2019) ; Srikant and Ying (2019) .

Since each iteration of TD uses one or a mini-batch of samples to estimate the mean of the pseudogradient1 , TD learning usually suffers from the inherent variance, which substantially degrades the convergence accuracy. Although a diminishing stepsize or very small constant stepsize can reduce the variance Bhandari et al. (2018) ; Srikant and Ying (2019) , they also slow down the convergence significantly.

Two approaches have been proposed to reduce the variance. The first approach is the so-called batch TD, which takes a fixed sample set and transforms the empirical mean square projected Bellman error (MSPBE) into an equivalent convex-concave saddle-point problem Du et al. (2017) . Due to the finite-sample nature of such a problem, stochastic variance reduction techniques for conventional optimization can be directly applied here to reduce the variance. In particular, Du et al. (2017) showed that SVRG Johnson and Zhang (2013) and SAGA Defazio et al. (2014) can be applied to improve the performance of batch TD algorithms, and Peng et al. (2019) proposed two variants of SVRG to further save the computation cost. However, the analysis of batch TD does not take into account the statistical nature of the training samples, which are generated by a MDP. Hence, there is no guarantee of such obtained solutions to be close to the fixed point of TD learning.

The second approach is the so-called TD with centering (CTD) algorithm proposed in Korda and La (2015) , which introduces the variance reduction idea to the original TD learning algorithm. For the sake of better reflecting its major feature, we refer to CTD as Variance Reduced TD (VRTD) throughout this paper. Similarly to the SVRG in Johnson and Zhang (2013) , VRTD has outer and inner loops. The beginning of each inner-loop (i.e. each epoch) computes a batch of sample pseudogradients so that each subsequent inner loop iteration modifies only one sample pseudo-gradient in the batch pseudo-gradients to reduce the variance. The main difference between VRTD and batch TD is that VRTD applies the variance reduction directly to TD learning rather than to a transformed optimization problem in batch TD. Though Korda and La (2015) empirically verified that VRTD has better convergence accuracy than vanilla TD learning, some technical errors in the analysis in Korda and La (2015) have been pointed out in follow up studies Dalal et al. (2018a) ; Narayanan and Szepesvári (2017) . Furthermore, as we discuss in Section 3, the technical proof in Korda and La (2015) regarding the convergence of VRTD also has technical errors so that their results do not correctly characterize the impact of variance reduction on TD learning. Given the recent surge of interest in the finite time analysis of the vanilla TD Dalal et al. (2018a) ; Bhandari et al. (2018) ; Dalal et al. (2018b) ; Srikant and Ying (2019) , it becomes imperative to reanalyze the VRTD and accurately understand whether and how variance reduction can help to improve the convergence accuracy over vanilla TD. Towards this end, this paper specifically addresses the following central questions.

• For i.i.d. sampling, it has been shown in Dalal et al. (2018a) ; Bhandari et al. (2018) that vanilla TD converges only to a neighborhood of the fixed point for a constant stepsize and suffers from a constant error term caused by the variance of the stochastic pseudo-gradient at each iteration.

For VRTD, does the variance reduction help to reduce such an error and improve the accuracy of convergence? How does the error depend on the variance reduction parameter, i.e., the batch size for variance reduction? • For Markovian sampling, it has been shown in Bhandari et al. (2018) that the convergence of vanilla TD further suffers from a bias error due to the correlation among samples in addition to the variance error as in i.i.d. sampling. Does VRTD, which was designed to have reduced variance, also enjoy reduced bias error? If so, how does the bias error depend on the batch size for variance reduction? • For both i.i.d. and Markovian sampling, to attain an -accurate solution, what is the overall computational complexity (the total number of computations of pseudo-gradients) of VRTD, and does VRTD have a reduced overall computational complexity compared to TD?

1.1 OUR CONTRIBUTIONS Our main contributions are summarized in Table 1 and are described as follows.

For i.i.d. sampling, we show that a slightly modified version of VRTD (for avoiding bias error) converges linearly to a neighborhood of the fixed point solution for a constant stepsize α, with the variance error at the order of O(α/M ), where M is the batch size for variance reduction. To attain an -accurate solution, the overall computational complexity (i.e., the total number of pseudo-gradient computations) of VRTD outperforms the vanilla TD algorithm Bhandari et al. (2018) if the condition number is small.

For Markovian sampling, we show that VRTD has the same linear convergence and the same variance error reduction over the vanilla TD Dalal et al. (2018a) ; Bhandari et al. (2018) as i.i.d. sampling. More importantly, the variance reduction in VRTD also attains a substantially reduced bias error at the order of O(1/M ) over the vanilla TD Bhandari et al. (2018) , where the bias error is at the order of O(α). As a result, VRTD outperforms vanilla TD in terms of the total computational complexity by a factor of log 1 .

At the technical level, our analysis of bias error for Markovian sampling takes a different path from how the existing analysis of TD handles Markovian samples in Bhandari et al. (2018) ; Wang et al. (2017) ; Srikant and Ying (2019) . Due to the batch average of stochastic pseudo-gradients adopted by VRTD to reduce the variance, the correlation among samples in different epochs is eliminated. Such an analysis explicitly explains why the variance reduction step helps to further reduce the bias error. 

EQUATION

Note: The results on the performance of TD are due to Bhandari et al. (2018) and the results on the performance of VRTD (which are highlighted by the red color) are characterized by this work.

1.2. RELATED WORK:

On-policy TD learning and variance reduction. On-policy TD learning aims to minimize the Mean Squared Bellman Error (MSBE) Sutton (1988) when samples are drawn independently from the stationary distribution of the corresponding MDP. The non-asymptotic convergence under i.i.d. sampling has been established in Dalal et al. (2018a) for TD with linear function approximation and for TD with overparameterized neural network approximation Cai et al. (2019) . The convergence of averaged linear SA with constant stepsize has been studied in Lakshminarayanan and Szepesvari (2018) . In the Markovian setting, the non-asymptotic convergence has been studied for on-policy TD in Bhandari et al. (2018) ; Karmakar and Bhatnagar (2016) ; Wang et al. (2019) ; Srikant and Ying (2019) . Korda and La (2015) proposed a variance reduced CTD algorithm (called VRTD in this paper), which directly applies variance reduction technique to the TD algorithm. The analysis of VRTD provided in Korda and La (2015) has technical errors. The aim of this paper is to provide a technically solid analysis for VRTD to characterize the advantage of variance reduction.

Variance reduced batch TD learning. Batch TD Lange et al. (2012) algorithms are generally designed for policy evaluation by solving an optimization problem on a fixed dataset. In Du et al. (2017) , the empirical MSPBE is first transformed into a quadratic convex-concave saddle-point optimization problem and variance reduction methods of SVRG Johnson and Zhang (2013) and SAGA Defazio et al. (2014) were then incorporated into a primal-dual batch gradient method. Furthermore, Peng et al. (2019) applied two variants of variance reduction methods to solve the same saddle point problems, and showed that those two methods can save pseudo-gradient computation cost.

We note that due to the extensive research in TD learning, we include here only studies that are highly related to our work, and cannot cover many other interesting topics on TD learning such as asymptotic convergence of TD learning Tadić (2001) ; Hu and Syed (2019) , off-policy TD learning Sutton et al. (2008; 2009) ; Liu et al. (2015) ; Wang et al. (2017) ; Karmakar and Bhatnagar (2017) , two time-scale TD algorithms Xu et al. (2019) ; Dalal et al. (2018b) ; Yu (2017) , fitted TD algorithms Lee and He (2019) , SARSA Zou et al. (2019) etc. The idea of the variance reduction algorithm proposed in Korda and La (2015) as well as the analysis techniques that we develop in this paper can potentially be useful for these algorithms. It is known that v π (s) is the unique fixed point of the Bellman operator T π , i.e., v π (s) = T π v π (s).

2. PROBLEM FORMULATION AND PRELIMINARIES:

In practice, since the MDP is unknown, the value function v π (s) cannot be directly obtained. The goal of policy evaluation is to find the value function v π (s) via sampling the MDP.

2.2. TD LEARNING WITH LINEAR FUNCTION APPROXIMATION:

In order to find the value function efficiently particularly for large or infinite state space S, we take the standard linear function approximation v(s, θ) = φ(s) θ of the value function, where 

φ(s) = [φ 1 (s), • • • , φ d (s)] with φ i (s) for i = 1, 2

(θ) = Aθ + b where A = E µπ [φ(s)(γφ(s )-φ(s)) ] and b = E µπ [r(s)φ(s)].

We call g(θ) as pseudo-gradient for convenience due to its analogous role as in the gradient descent algorithm. It has been shown that the iteration in eq. ( 1) converges to the fix point θ * = -A -1 b at a sublinear rate O(1/t) with diminishing stepsize α t = O(1/t) using both Markovian and i.i.d. samples Bhandari et al. (2018) ; Dalal et al. (2018a) .

Throughout the paper, we make the following standard assumptions Wang et al. (2017) ; Korda and La (2015) ; Tsitsiklis and Van Roy (1997) ; Bhandari et al. (2018) .

Assumption 1 (Problem solvability). The matrix A is non-singular.

Assumption 2 (Bounded feature). φ(s) 2 ≤ 1 for all s ∈ S. Assumption 3 (Geometric ergodicity). The considered MDP is irreducible and aperiodic, and there exist constants κ > 0 and ρ ∈ (0, 1) such that

sup s∈S d T V (P(s t ∈ •|s 0 = s), µ π (s)) ≤ κρ t , ∀t ≥ 0,

where d T V (P, Q) denotes the total-variation distance between the probability measures P and Q.

Assumption 1 requires the matrix A to be non-singular so that the optimal parameter θ * = -A -1 b is well defined. Assumption 2 can be ensured by normalizing the basis functions {φ i } d i=1 . Assumption 3 holds for any time-homogeneous Markov chain with finite state-space and any uniformly ergodic Markov chains with general state space.

3. THE VARIANCE REDUCED TD ALGORITHM:

In this section, we first introduce the variance-reduced TD (VRTD) algorithm proposed in Korda and La (2015) for Markovian sampling and then discuss the technical errors in the analysis of VRTD in Korda and La (2015) .

3.1. VRTD ALGORITHM KORDA AND LA (2015):

Since the standard TD learning takes only one sample in each update as can be seen in eq. (1), it typically suffers from a large variance. This motivates the development of the VRTD algorithm in Korda and La (2015) (named as CTD in Korda and La (2015) ). VRTD is formally presented in Algorithm 2, and we briefly introduce the idea below. The algorithm runs in a nested fashion with each inner-loop (i.e., each epoch) consists of M updates. At the beginning of the m-th epoch, a batch of M samples are acquired and a batch pseudo-gradient g m ( θm-1 ) is computed based on these samples as an estimator of the mean pseudo-gradient. Then, each inner-loop update randomly takes Algorithm 1 Variance Reduced TD with iid samples Input: batch size M , learning rate α and initialization θ0 1: for m = 1, 2, ..., S do 2: θm,0 = θm-1 3: Sample a set Bm with M samples indepedently from the distribution µπ 4: gm( θm-1) = 1 M x i ∈Bm gx i ( θm-1) 5: for t = 0, 1, ..., M -1 do 6:

Sample xj m,t indepedently from the distribution µπ 7:

θm,t+1 = θm,t + α gx j m,t (θm,t)

8::

-gx j m,t ( θm-1) + gm( θm-1) 9: end for 10: set θm = θm,t for randomly chosen t ∈ {1, 2, ..., M } 11: end for Output: θS Algorithm 2 Variance Reduced TD with Markovian samples Korda and La (2015) Input: batch size M , learning rate α and initialization θ0 1: for m = 1, 2, ..., S do 2: θm,0 = θm-1

3: gm( θm-1) = 1 M mM -1 i=(m-1)M gx i ( θm-1) 4: for t = 0, 1, ..., M -1 do 5:

Sample jm,t uniformly at random in {(m -1)M, ..., mM -1} from trajetory 6:

θm,t+1 = ΠR θ θm,t + α gx j m,t (θm,t)

7::

-gx j m,t ( θm-1) + gm( θm-1) 8: end for 9: set θm = θm,t for randomly chosen t ∈ {1, 2, ..., M } 10: end for Output: θS one sample from the batch, and updates the corresponding component in g m ( θm-1 ). Here, Π R θ in Algorithm 2 denotes the projection operator onto a norm ball with the radius R θ . The idea is similar to the SVRG algorithm proposed in Johnson and Zhang (2013) for conventional optimization. Since a batch pseudo-gradient is used at each inner-loop update, the variance of the pseudo-gradient is expected to be reduced.

3.2. TECHNICAL ERRORS IN KORDA AND LA (2015):

In this subsection, we point out the technical errors in the analysis of VRTD in Korda and La (2015) , which thus fails to provide the correct variance reduction performance for VRTD.

At the high level, the batch pseudo-gradient g m ( θm-1 ) computed at the beginning of each epoch m should necessarily introduce a non-vanishing variance error for a fixed stepsize, because it cannot exactly equal the mean (i.e. population) pseudo-gradient g( θm-1 ). Furthermore, due to the correlation among samples, the pseudo-gradient estimator in expectation (with regard to the randomness of the sample trajectory) does not equal to the mean pseudo-gradient, which should further cause a non-vanishing bias error in the convergence bound. Unfortunately, the convergence bound in Korda and La (2015) indicates an exact convergence to the fixed point, which contradicts the aforementioned general understanding. More specifically, if the batch size M = 1 (with properly chosen λ A defined as λ A := 2|λ max (A + A )|), VRTD reduces to the vanilla TD. However, the exact convergence result in Theorem 3 in Korda and La (2015) does not agree with that of vanilla TD characterized in the recent studies Bhandari et al. (2018) , which has variance and bias errors.

In Appendix B, we further provide a counter-example to show that one major technical step for characterizing the convergence bound in Korda and La (2015) does not hold. The goal of this paper is to provide a rigorous analysis of VRTD to characterize its variance reduction performance.

4. MAIN RESULTS:

As aforementioned, the convergence of VRTD consists of two types of errors: the variance error due to inexact estimation of the mean pseudo-gradient and the bias error due to Markovian sampling. In this section, we first focus on the first type of error and study the convergence of VRTD under i.i.d. sampling. We then study the Markovian case to further analyze the bias. In both cases, we compare the performance of VRTD to that of the vanilla TD described in eq. ( 1) to demonstrate its advantage.

4.1. CONVERGENCE ANALYSIS OF VRTD WITH I.I.D. SAMPLES:

For i.i.d. samples, it is expected that the bias error due to the time correlation among samples does not exist. However, if we directly apply VRTD (Algorithm 2) originally designed for Markovian samples, there would be a bias term due to the correlation between the batch pseudo-gradient estimate and every inner-loop updates. Thus, we slightly modify Algorithm 2 to Algorithm 1 to avoid the bias error in the convergence analysis with i.i.d. samples. Namely, at each inner-loop iteration, we draw a new sample from the stationary distribution µ π for the update rather than randomly selecting one from the batch of samples drawn at the beginning of the epoch as in Algorithm 2. In this way, the new independent samples avoid the correlation with the batch pseudo-gradient evaluated at the beginning of the epoch. Hence, Algorithm 1 does not suffer from an extra bias error.

To understand the convergence of Algorithm 1 at the high level, we first note that the sample batch pseudo-gradient cannot estimate the mean pseudo-gradient g( θm-1 ) exactly due to its population nature. Then, we define e m ( θm ) = g m ( θm-1 ) -g( θm-1 ) as such a pseudo-gradient estimation error, our analysis (see Appendix D) shows that after each epoch update, we have

EQUATION

where F m,0 denotes the σ-field that includes all the randomness in sampling and updates before the m-th epoch. The first term in the right-hand side of eq. ( 2) captures the contraction property of Algorithm 1 and the second term corresponds to the variance of the pseudo-gradient estimation error.

It can be seen that due to such an error term, Algorithm 1 is expected to have guaranteed convergence only to a neighborhood of θ * , when applying eq. ( 2) iteratively. Our further analysis shows that such an error term can still be well controlled (to be small) by choosing an appropriate value for the batch size M , which captures the advantage of the variance reduction. The following theorem precisely characterizes the non-asymptotic convergence of Algorithm 1. Theorem 1. Consider the VRTD algorithm in Algorithm 1. Suppose Assumptions 1-3 hold. Set a constant stepsize α < λ A 8(1+γ) 2 and the batch size

EQUATION

where 1+γ) 2 (with C 1 < 1 due to the choices of α and M ), and

C 1 := 4α(1 + γ) 2 + 4(1+γ) 2 α 2 +1 αM 1 λ A -4α(

D 2 = 4((1 + γ) 2 R 2 θ + r 2 max ).

We note that the convergence rate in eq. ( 3) can be written in a simpler form as

E[|| θm -θ * || 2 ] ≤ C m 1 || θ0 -θ * || 2 + O(α/M ).

Theorem 1 shows that Algorithm 1 converges linearly (under a properly chosen constant stepsize) to a neighborhood of the fixed point solution, and the size of the neighborhood (i.e., the error term) has the order of O( α M ), which can be made as small as possible by properly increasing the batch size M . This is in contrast to the convergence result of the vanilla TD, which suffers from the constant error term with order O(α) Bhandari et al. (2018) for a fixed stepsize. Thus, a small stepsize α is required in vanilla TD to reduce the variance error, which, however, slows down the practical convergence significantly. In contrast, this is not a problem for VRTD, which can attain a high accuracy solution while still maintaining fast convergence at a desirable stepsize.

We further note that if we have access to the mean pseudo-gradient g( θm-1 ) in each epoch m, then the error term ||θ m -θ * || 2 2 becomes zero, and Algorithm 1 converges linearly to the exact fixed point solution, as the iteration number m goes to infinity with respect to the conditional number C 1 , which is a positive constant and less than 1. This is similar to the conventional convergence of SVRG for strongly convex optimization Johnson and Zhang (2013) . However, the proof here is very different. In Johnson and Zhang (2013) , the convergence proof relies on the relationship between the gradient and the value of the objective function, but there is not such an objective function in the TD learning problem. Thus, the convergence of the parameter θ needs to be developed by exploiting the structure of the Bellman operator.

Based on the convergence rate of VRTD characterized in Theorem 1 under i.i.d. sampling, we obtain the following bound on the overall computational complexity.

Corollary 1. Suppose Assumptions 1-3 hold. Let α = λ A 16(1+γ) 2 , M = max{ D2 3(1-C1) 1 , 33(1+γ) 2 λ 2 A } .

Then, for any > 0, an -accuracy solution (i.e., E|| θm -θ * || 2 ≤ ) can be attained with at most m = log 2 θ0-θ * 2 2 / log 1 C1 iterations. Correspondingly, the total number of pseudo-gradient computations required by VRTD (i.e., Algorithm 1) under i.i.d. sampling to attain such an -accuracy solution is at most

O max 1 , 1 λ 2 A log 1 .

Proof. Given the values of α and M in the theorem, it can be easily checked that

E|| θm -θ * || 2 ≤ for m = log 2 θ0-θ * 2 2 / log 1 C1 .

Then the total number of pseudo-gradient computations is given by 2mM that yields the desired order given in the theorem.

As a comparison, consider the vanilla TD algorithm studied in Bhandari et al. (2018) with the constant stepsize α = O( ). If the samples are i.i.d. generated, it can be shown (see Appendix F.1) that the vanilla TD requires O 1 λ 2 A log 1 pseudo-gradient computations in total to obtain an -accuracy solution. Clearly, VRTD has lower computational complexity than vanilla TD if λ A is small. Such a comparison is similar in nature to the comparison between SVRG Johnson and Zhang (2013) and SGD in traditional optimization, where SVRG achieves better computational complexity than SGD for strongly convex objectives if the conditional number of the loss is small.

4.2. CONVERGENCE ANALYSIS OF VRTD WITH MAKOVIAN SAMPLES:

In this section, we study the VRTD algorithm (i.e., Algorithm 2) with Markovian samples, in which samples are generated from one single MDP path. In such a case, we expect that the convergence of VRTD to have both the variance error due to the pseudo-gradient estimation (similar to the case with i.i.d. samples) and the bias error due to the correlation among samples. To understand this at the high level, we define the bias at each iteration as ξ m (θ) = (θ -θ * ) (g m (θ) -g(θ)). Then our analysis (see Appendix E) shows that after the update of each epoch, we have

EQUATION

The first term on the right-hand side of eq. ( 4) captures the epochwise contraction property of Algorithm 2. The second term is due to the variance of the pseudo-gradient estimation, which captures how well the batch pseudo-gradient g m (θ * ) approximates the mean pseudo-gradient g(θ * ) (note that g(θ * ) = 0). Such a variance term can be shown to decay to zero as the batch size gets large similarly to the i.i.d. case. The third term captures the bias introduced by the correlation among samples in the m-th epoch. To quantitatively understand this error term, we provide the following lemma that characterizes how the bias error is controlled by the batch size M .

Lemma 1. For any m > 0 and any θ ∈ B θ , which is a ball with the radius R θ , we have

E[ξ m (θ)] ≤ λ A 4 E[ θ -θ * 2 2 |F n,0 ] + 8[1 + (κ -1)ρ] λ A (1 -ρ)M [R 2 θ (1 + γ) 2 + r 2 max ],

where the expectation is over the random trajectory, θ is treated as a fixed variable, and 0 < C 0 < ∞ is a constant depending only on the MDP.

Lemma 1 shows that the bias error diminishes as the batch size M increases and the algorithm approaches to the fixed point θ * . To explain why this happens, the definition of ξ m (θ) immediately yields the following bound:

ξ m (θ) ≤ 1 λ A g n (θ) -g(θ) 2 2 + λ A 4 θ -θ * 2 2 .

(5)

The first term on the right-hand-side of eq. ( 5) can be bounded by the concentration property for the ergodic process as

g m (θ) = 1 M mM -1 i=(m-1)M g xi (θ)

a.s.

→ g(θ). As M increases, the randomness due to the pseudo-gradient estimation is essentially averaged out due to the variance reduction step in VRTD, which implicitly eliminates its correlation from samples in the previous epochs.

As a comparison, the bias error in vanilla TD has been shown to be bounded by Bhandari et al. (2018) . In order to reduce the bias and achieve a high convergence accuracy, the stepsize α is required to be small, which causes the algorithm to run very slowly. The advantage of VRTD is that the bias can be reduced by choosing a sufficiently large batch size M so that the stepsize can still be kept at a desirable constant to guarantee fast convergence. Theorem 2. Consider the VRTD algorithm in Algorithm 2. Suppose Assumptions 1-3 hold. Set the constant stepsize α < λ A 12(1+γ) 2 and the batch size M > 1 0.5αλ A -6α 2 (1+γ) 2 . Then, we have

E[ξ n (θ)] = O(α log(1/α))

EQUATION

where

C 1 = 1/M +3α 2 (1+γ) 2 0.5αλ A -3α 2 (1+γ) 2 (with C 1 < 1 due to the choices for α and M ), C 2 = 16[1+(κ-1)ρ][R 2 θ (1+γ) 2 +r 2 max ] 1-ρ and C 4 = [(1 + γ)R θ + r max ] 2 + 2ρκG[(1+γ)R θ +rmax] 1-ρ .

We note that the convergence rate in eq. ( 6) can be written in a simpler form as

E[|| θm -θ * || 2 ] ≤ C m 1 || θ0 -θ * || 2 + O(1/M ).

Theorem 2 shows that VRTD (i.e., Algorithm 2) with Markovian samples converges to a neighborhood of θ * at a linear rate, and the size of the neighborhood (i.e., the convergence error) decays sublinearly with the batch size M . More specifically, the first term in the right-hand side of eq. ( 6) captures the linear convergence of the algorithm, the second term corresponds to the sum of the cumulative pseudogradient estimation error and the cumulative bias error. For the fixed stepsize, the total convergence error is dominated by the sum of those two error terms with the order O(1/M ). Therefore, the variance reduction in Algorithm 2 reduces both the variance and the bias of the pseudo-gradient estimator.

Based on the convergence rate of VRTD characterized in Theorem 2 under Markovian sampling, we obtain the following bound on the corresponding computational complexity.

Corollary 2. Suppose Assumptions 1-3 hold. Let α = λ A 24(1+γ) 2 and M = ( 32C2+4C4 3(1-C1) + 100(1 + γ) 2 ) max{ 1 , 1 λ 2 A } .

Then, for any > 0, an -accuracy solution (i.e., E|| θm -θ * || 2 ≤ ) can be attained with at most m = log 2 θ0-θ * 2 2 / log 1 C1 iterations. Correspondingly, the total number of pseudo-gradient computations required by VRTD (i.e., Algorithm 2) under Markovian sampling to attain such an -accuracy solution is at most

O max 1 , 1 λ 2 A log 1 .

Proof. Given the values of α and M in the theorem, it can be easily checked that

E|| θm -θ * || 2 ≤ for m = log 2 θ0-θ * 2 2 / log 1 C1 .

Then the total number of pseudo-gradient computations is given by 2mM that yields the desired order given in the theorem.

As a comparison, consider the vanilla TD algorithm studied in Bhandari et al. (2018) with the constant stepsize α = O( / log(1/ )). Under Markovian sampling, it can be shown (see Appendix F.2) that vanilla TD requires O 1 λ 2 A log 2 1 pseudo-gradient computations in total to obtain an -accuracy solution. Hence, in the Markovian setting, VRTD outperforms vanilla TD in terms of the total computational complexity by a factor of log 1 . To intuitively explain, we first note that the correlation among data samples in the Markovian case also causes a bias error in addition to the variance error. For VRTD, due to the variance reduction scheme, the bias and variance errors are kept at the same level (with respect to the batch size) so that the bias error does not cause order-level increase in the computational complexity for VRTD. However, for vanilla TD, the bias error dominates the variance error, which turns out to require more iterations to attain an -accurate solution, and yields an additional log 1 factor in the total complexity compared to VRTD.

5. EXPERIMENTS:

In this section, we provide numerical results to verify our theoretical results. Note that in Appendix A, we provide further experiments on two problems in OpenAI Gym Brockman et al. (2016) and one experiment to demonstrate that VRTD is more sample-efficient than vanilla TD.

We consider an MDP with γ = 0.95 and |S| = 50. Each transition probability are randomly sampled from [0,1] and the transitions were normalized to one. The expected reward for each transition is also generated randomly in [0,1] and the reward on each transition was sampled without noise. Each component of the feature matrix Φ ∈ R 50×4 is randomly and uniformly sampled between 0 and 1. The baseline for comparison is the vanilla TD algorithm, which corresponds to the case with M = 1 in our figure. We conduct two experiments to investigate how the batch size M for variance reduction affects the performance of VRTD with i.i.d. and Markovian samples. In the Markovian setting, we sample the data from a MDP trajectory. In the i.i.d. setting, we sample the data independently from the corresponding stationary distribution. In both experiments, we set the constant stepsize to be α = 0.1 and we run the experiments for five different batch sizes: M = 1, 50, 500, 1000, 2000. Our results are reported in Figure 1 and 2. All the plots report the square error over 1000 independent runs. In each case, the left figure illustrates the convergence process over the number of pseudo-gradient computations and the right figure shows the convergence errors averaged over the last 10000 iterations for different batch size values. It can be seen that in both i.i.d. and Markovian settings, the averaged error decreases as the batch size increases, which corroborates both Theorem 1 and Theorem 2. We also observe that increased batch size substantially reduces the error without much slowing down the convergence, demonstrating the desired advantage of variance reduction. Moreover, we observe that the error of VRTD with i.i.d samples is smaller than that of VRTD with Markovian samples under all batch size settings, which indicates that the correlation among Markovian samples introduces additional errors. 

6. CONCLUSION:

In this paper, we provided the convergence analysis for VRTD with both i.i.d. and Markovian samples. We developed a novel technique to bound the bias of the VRTD pseudo-gradient estimator. Our result demonstrate the advantage of VRTD over vanilla TD on the reduced variance and bias errors by the batch size. We anticipate that such a variance reduction technique and our analysis tools can be further applied to other RL algorithms. In this subsection, we provide an additional experiment to compare the performance of VRTD given in Algorithm 2 (under constant stepsize) with the TD algorithm (under a changing stepsize as suggested by the reviewer). We adopt the same setting of Frozen Lake as in Appendix A.1. Let VRTD take a batch size M = 5000 and stepsize α = 0.1. For a fair comparison, we start TD with the same constant stepsize α = 0.1 and then reduce the stepsize by half whenever the error stops decrease. The comparison is reported in Figure 5 , where both curves are averaged over 1000 independent runs. The two algorithms are compared in terms of the squared error versus the total number of pseudo-gradient computations (equivalently, the total number of samples being used). It can be seen that VRTD reaches the required accuracy much faster than TD. In this section, we use a counter-example to show that one major technical step for characterizing the convergence bound in Korda and La (2015) does not hold. Consider Step 4 in the proof of Theorem 3 in Korda and La (2015) . For the following defined (θ)

EQUATION

where Ψ denotes the stationary distribution of the corresponding Markov chain, Korda and La (2015) claimed that the following inequality holds

EQUATION

)

This is not correct. Consider the following counter-example. Let the batch size M = 3 and the dimension of the feature vector be one, i.e., Φ ∈ R |S|×1 . Hence, all variables in eq. ( 8) and eq. ( 7) are scalars. Since the steps for proving eq. ( 8) in Korda and La (2015) do not have specific requirements for the transition kernel, eq. ( 8) should hold for any distribution of v. Thus, suppose v follows the uniform distribution over [-3, 3] . Further assume that in the n-th epoch, the samples of v are given by {1, 2, -3}. Recall that E(•|F n ) is the average over the batch samples in the n-th epoch. We have:

E Ψ,θn (v) = 0, E Ψ,θn (v 2 ) = 3, E(v|F n ) = 0, E(v 2 |F n ) = 14 3 .

Substituting the above values into eq. ( 8) yields

EQUATION

which obviously does not hold in general when θ = θ * . Consequently the second statement in Theorem 3 of Korda and La (2015) , which is critically based on the above erroneous steps, does not hold. Hence, the first statement in the same theorem whose proof is based on the second statement cannot hold either.

C USEFUL LEMMAS:

In the rest of the paper, for any matrix W ∈ R d×d , we denote W 2 as the spectral norm of W and W F as the Frobenius norm of W . Lemma 2. For any

x i = (s i , r i , s i ) (i.i.d. sample) or x i = (s i , r i , s i+1 ) (Markovian sample), we have A xi 2 ≤ 1 + γ and b xi 2 ≤ r max .

Proof. First consider the case when samples are i.i.d. Due to the definition of A xi , we have

A xi 2 = φ(s i )(γφ(s i ) -φ(s i )) 2 ≤ φ(s i )(γφ(s i ) -φ(s i )) F ≤ γ φ(s i )φ(s i ) F + φ(s i )φ(s i ) F ≤ 1 + γ. Then, consider b xi : b xi 2 = r xi φ(s i ) 2 ≤ r max φ(s i ) 2 ≤ r max .

Following similar steps, we can obtain the same upper bounds for the case with Markovian samples.

Lemma 3. Let G = (1 + γ)R θ + r max . Consider Algorithm 2. For any m > 0 and 0 ≤ t ≤ M -1, we have g xj m ,t (θ m,t ) 2 , g xj m ,t ( θm-1 ) 2 , g m ( θm-1 ) 2 ≤ G.

Proof. First, we bound g xj m ,t (θ m,t ) 2 as follows.

g xj m ,t (θ m,t ) 2 = A xj m,t θ m,t + b θm,t 2 ≤ A xj m,t 2 θ m,t 2 + b θm,t 2 ≤ (1 + γ)R θ + r max .

Following the steps similar to the above, we have g xj m ,t ( θm-1 ) 2 ≤ G. Finally for g xj m ,t ( θm-1 )

2:

, we have

EQUATION

where eq. ( 10) follows from the last fact g xj m ,t ( θm-1 )

2 ≤ G. Lemma 4. Define D 1 = 2(1 + γ) 2 and D 2 = 4((1 + γ) 2 R 2 θ + r 2 max ). For any θ ∈ R d , we have g xi (θ) 2 2 ≤ D 1 θ -θ * 2 2 + D 2 .

Proof. Recalling the definition of g xi , and applying Lemma 2, we have

g xi (θ) 2 2 = A xi θ + b xi 2 2 = A xi (θ -θ * ) + (A xi θ * + b xi ) 2 2 ≤ 2 A xi (θ -θ * ) 2 2 + 2 A xi θ * + b xi 2 2 ≤ 2 A xi 2 2 θ -θ * 2 2 + 4( A xi 2 2 θ * 2 2 + b xi 2 2 ) ≤ 2(1 + γ) 2 θ -θ * 2 2 + 4((1 + γ) 2 R 2 θ + r 2 max ) = D 1 θ -θ * 2 2 + D 2 .

Lemma 5. Considering Algorithm 2 with Markovian samples. We have

E[A j |P i ] -A F ≤ (1 + γ)κρ j-i and E[b j |P i ] -b 2 ≤ r max κρ j-i for 0 < i < j.

Proof. We first derive

E[A j |P i ] -A F = A xi dP (x i |P j ) -A xi dµ π F ≤ A xi dP (x i |P j ) -A xi dµ π F ≤ A xi F |dP (x i |P j ) -dµ π | ≤ (1 + γ) P (x i |P j ), µ π T V ≤ (1 + γ)κρ j-i .

Following the steps similar to the above, we can derive

E[b j |P i ] -b 2 ≤ 2r max κρ j-i .

D PROOF OF THEOREM 1: CONVERGENCE OF VRTD WITH I.I.D. SAMPLES:

Recall that B m is the sample batch drawn at the beginning of each m-th epoch and x i,j denotes the sample picked at the j-th iteration in the i-th epoch in Algorithm 1. We denote σ( θ0 ) as a trivial σ-field when θ0 is a deterministic vector. Let σ(A ∪ B) indicate the smallest σ-field that contains both A and B. Then, we construct a set of σ-fields in the following incremental way.

F 1,0 = σ( θ0 ), F 1,1 = σ(F 1,0 ∪ σ(B 1 ) ∪ σ(x 1,1 )), ..., F 1,M = σ(F 1,(M -1) ∪ σ(x 1,M )), F 2,0 = σ(F 1,M ∪ σ( θ1 )), F 21 = σ(F 2,0 ∪ σ(B 2 ) ∪ σ(x 2,1 )), ..., F 2,m = σ(F 2,(M -1) ∪ σ(x 2,M )), . . . F m,0 = σ(F (m-1),M ∪ σ( θm-1 )), F m1 = σ(F m,0 ∪ σ(B m ) ∪ σ(x m,1 )), ..., F m,M = σ(F m,(M -1) ∪ σ(x m,M )).

The proof of Theorem 1 proceeds along the following steps.

Step 1: Iteration within the m-th epoch

For the m-th epoch, we consider the last update (i.e., the M -th iteration in the epoch), and decompose its error into the following form.

EQUATION

First, consider the third term in the right-hand side of eq. ( 11), we have

EQUATION

Then, by taking the expectation conditioned on F m,M -1 on both sides of eq. ( 12), we have

E g xj m,M (θ m,M -1 ) -g xj m,M ( θm-1 ) + g m ( θm-1 ) 2 2 F m,M -1 (i) ≤ 4E g xj m,M (θ m,M -1 ) -g xj m,M (θ * ) 2 2 F m,M -1 + 4E g xj m,M ( θm-1 ) -g xj m,M (θ * ) -E g xj m,M ( θm-1 ) -g xj m,M (θ * ) F m,M -1 ] 2 2 F m,M -1 + 2E g m ( θm-1 ) -g( θm-1 ) 2 2 F m,M -1 (ii) ≤ 4(1 + γ) 2 E θ m,M -1 -θ * 2 2 |F m,M -1 + 4(1 + γ) 2 E θm-1 -θ * 2 2 |F m,M -1 + 2E g m ( θm-1 ) -g( θm-1 ) 2 2 F m,M -1 where (i) follows from the fact that E[ g xj m,M ( θm-1 ) -g xj m,M (θ * ) |F m,M -1 ] = g( θm-1 ) -g(θ * ),

and (ii) follows from the inequality E[(X -EX) 2 ] ≤ EX 2 and Lemma 2. Then, taking the expectation conditioned on F m,M -1 on both sides of eq. ( 11) yields

EQUATION

where (i) follows from the fact that E g xj m,M ( θm-1 ) F m,M -1 = g( θm-1 ). In (ii) we define λ A as the absolute value of the largest eigenvalue of matrix (A T + A), which is negative definite according to Tsitsiklis and Van Roy (1997) .

In (iii) we define ξ m (θ) = (θ -θ * ) (g m (θ) -g(θ)) for θ ∈ R d .

Then, by applying eq. ( 13) iteratively, we have

EQUATION

For all 1 ≤ i ≤ M , we have

E ξ m ( θm-1 ) F m,0 = E g m ( θm-1 ) F m,0 -g( θm-1 ) = 1 M i∈Bm E[A xi θm + b xi |F m,0 ] -(A θm + b) = 1 M i∈Bm E[A xi |F m,0 ] -A θm + 1 M i∈Bm E[b xi |F m,0 ] -b = 0.

Then, arranging terms in eq. ( 14) and using the above fact yield

EQUATION

Finally, dividing eq. ( 15) by

EQUATION

Step 2: Bounding the variance error

EQUATION

EQUATION

where eq. ( 18) follows from Lemma 4.

Step 3: Iteration over m epoches

First, we substitute eq. ( 18) into eq. ( 16) to obtain

EQUATION

where we define

C 1 = 4α(1 + γ) 2 + 2D1α 2 +1 αM 1 λ A -4α(1+γ) 2 .

Taking the expectation of eq. ( 19) conditioned on F m-1,0 and following the steps similar to those in step 1 to upper bound E θm-1 -θ * 2 2 F m-1,0 , we obtain

E θm -θ * 2 2 F m-1,0 ≤ C 1 E θm-1 -θ * 2 2 F m-1,0 + 2D 2 α (λ A -4α(1 + γ) 2 )M ≤ C 2 1 θm-2 -θ * 2 2 + 2D 2 α (λ A -4α(1 + γ) 2 )M 1 k=0 C k 1 .

Then, by following the above steps for (m -1) times, we have

E θm -θ * 2 2 ≤ C m 1 θ0 -θ * 2 2 + 2D 2 α (λ A -4α(1 + γ) 2 )M m-1 k=0 C k 1 ≤ C m 1 θ0 -θ * 2 2 + 2D 2 α (1 -C 1 )(λ A -4α(1 + γ) 2 )M ,

which yields the desirable result.

E PROOF OF THEOREM 2: CONVERGENCE OF VRTD WITH MARKOVIAN SAMPLES We define σ(S i ) to be the σ-field of all samples up to the i-th epoch and recall that j m,t is the index of the sample picked at the t-th iteration in the m-th epoch in Algorithm 2. Then we define a set of σ-fields in the following incremental way:

F 1,0 = σ(S 0 ), F 1,1 = σ(F 1,0 ∪ σ(j 1,1 )), ..., F 1,M = σ(F 1,(M -1) ∪ σ(j 1,M )), F 2,0 = σ(σ(S 1 ) ∪ F 1,M ∪ σ( θ1 )), F 21 = σ(F 2,0 ∪ σ(j 2,1 )), ..., F 2,m = σ(F 2,(M -1) ∪ σ(j 2,M )), . . . F m,0 = σ(σ(S m-1 ) ∪ F (m-1),M ∪ σ( θm-1 )), F m,1 = σ(F m,0 ∪ σ(j m,1 )), ..., F m,M = σ(F m,(M -1) ∪ σ(j m,M )).

E.1 PROOF OF LEMMA 1:

We first prove Lemma 1, which is useful for step 4 in the main proof in Theorem 2 provided in Section E.2.

Proof. Recall the definition of the bias term: ξ n (θ) = (θ -θ * ) (g n (θ) -g(θ)). We have

EQUATION

where (i) follows from the fact that W 2 ≤ W F for all matrices W ∈ R d×d . We define the interproduct between two matices W, V ∈ R d×d as W, V = ij ij W ij V ij . Consider the second term in eq. ( 20):

EQUATION

Now consider upper bound the term E[ A xi -A, A xj -A |F n,0 ] in eq. ( 21). Without loss of generality, we consider the case when i > j as follows:

E[ A xi -A, A xj -A |F n,0 ] = E E A xi -A, A xj -A |x j F n,0 = E E A xi |x j -A, A xj -A F n,0 ≤ E E A xi |x j -A F A xj -A F F n,0 ≤ E E A xi |x j -A F A xj F + A F F n,0 ≤ 2(1 + γ)E E A xi |x j -A F F n,0 ≤ 2κ(1 + γ) 2 ρ i-j .

We can further obtain

EQUATION

Then substituting eq. ( 22) into eq. ( 21) yields

E    1 M nM -1 i=(n-1)M A xi -A 2 F F n,0    ≤ 1 M 4(1 + γ) 2 + 4(1 + γ) 2 κρ 1 -ρ .

Then consider the third term in eq. ( 20):

E 1 M nM -1 i=(n-1)M b xi -b 2 2

F n,0 , similarly we have 

EQUATION

EQUATION

)

Combing all of the above pieces together yields the following final bound

EQUATION

E.2 PROOF OF THEOREM 2

Step 1: Iteration within the m-th inner loop

For the m-th inner loop, we consider the last update (i.e., the M -th iteration in the epoch), and decompose its error into the following form.

EQUATION

First, consider the third term in the right-hand side of eq. ( 26).

EQUATION

Then, by taking the expectation conditioned on F m,(M -1) on both sides of eq. ( 27), we have

EQUATION

where (i) follows by plugging eq. ( 28) into its preceding step and from the fact that

E g xj m,M ( θm-1 ) -g m ( θm-1 ) F m,M -1 = 0. In (ii) we define ξ m (θ) = (θ -θ * ) (g m (θ) -g(θ)) for θ ∈ R d .

Then, by applying eq. ( 29) iteratively, we have

EQUATION

Arranging the terms in eq. ( 30) yields

EQUATION

Then, substituting eq. ( 25) into eq. ( 31), we obtain

EQUATION

) Subtracting 0.5λ A α M -1 i=0 E[ θ m,i -θ * 2 2 |F m,0

] on both sides of eq. ( 32) yields

EQUATION

Then, dividing eq. ( 31) by [0.5αλ A -3α 2 (1 + γ) 2 ]M on both sides, we obtain

EQUATION

For simplicity, let 3α(1+γ) 2 . Then we rewrite eq. ( 34):

C 1 = 1/M +3α 2 (1+γ) 2 0.5αλ A -3α 2 (1+γ) 2 , C 2 = 16[1+(κ-1)ρ][R 2 θ (1+γ) 2 +r 2 max ] 1-ρ and C 3 = 3α 0.5λ A -

EQUATION

Step 2: Iteration over m epochs Taking the expectation of eq. ( 35) conditioned on F m-1,0 and upper-bounding E θm-1 -θ * 2 2 by following similar steps in the previous steps, we obtained

E θm -θ * 2 2 F m-1,0 ≤ C 1 θm-1 -θ * 2 2 + C 2 [0.5λ A -3α(1 + γ) 2 ]λ A M + C 3 E g m (θ * ) 2 2 F 1,0 ≤ C 2 1 θm-2 -θ * 2 2 + C 2 [0.5λ A -3α(1 + γ) 2 ]λ A M 1 k=0 C k 1 + C 3 1 k=0 C k 1 E g m-k (θ * ) 2 2 F 1,0 .

By following the above steps for (m -1) times, we have

EQUATION

Then taking the expectation of σ(S) (which contains the randomness of the entire sample trajectory) on both sides of eq. ( 36) yields

EQUATION

)

where the second term in the right hand side of eq. ( 37) corresponds to the bias error and the third term corresponds to the variance error.

Step 3: Bounding the variance error

For any 0 ≤ k ≤ m -1, we have 

EQUATION

where (i) follows from Lemma 3. Consider the expectation of the second term in eq. ( 38), which is given by 1

EQUATION

Without loss of generality, we consider the case when j > i as follows:

EQUATION

)

Substituting eq. ( 40) into eq. ( 39), we obtain 1

EQUATION

Then substituting eq. ( 41) into eq. ( 38) yields

EQUATION

where

C 4 = G 2 + 2ρκG[(1+γ)R θ +rmax]

(1-ρ)

. Finally, substituting eq. ( 42) into the accumulated residual variance term in eq. ( 37), we have

EQUATION

)

Step 4: Combining all error terms Finally, substituting eq. ( 43) and substituting the values of C 2 and C 3 into eq. ( 37), we have

E θm -θ * 2 2 ≤ C m 1 θ0 -θ * 2 2 + 3C 4 α + C 2 /λ A (1 -C 1 )[0.5λ A -3α(1 + γ) 2 ]M ,

which yields the desired result.

F SAMPLE COMPLEXITY OF TD:

The finite-time convergence rate of vanilla TD under i.i.d. and Markovian sampling has been characterized in Bhandari et al. (2018) ; Srikant and Ying (2019) . However, these studies did not provide the overall computational complexity, i.e., the total number of pseudo-gradient computations to achieve an -accuracy solution. This section provides such an analysis based on their convergence results for completeness.

F.1 TD WITH I.I.D. SAMPLES Consider the vanilla TD update in Bhandari et al. (2018) . Following the steps similar to those in Bhandari et al. (2018) for proving Theorem 2, and letting the constant stepsize α ≤ min{ λ A 4(1+γ) 2 , 2 λ A }, we have

E θ t -θ * 2 2 ≤ (1 - 1 2 λ A α) t θ 0 -θ * 2 2 + 2C 5 α λ A ≤ e -1 2 λ A αt θ 0 -θ * 2 2 + 2C 5 α λ A ,

where 0 < C 5 < ∞ is a constant. Let α = min{ λ A 4(1+γ) 2 , 2 λ A , λ A 4C5 }. It can be checked easily that with the total number of iterations at most

EQUATION

an -accurate solution can be attained, i.e., E θ t -θ * 2 2 ≤ . Since each iteration requires one pseudo-gradient computation, the total number of pseudo-gradient computations is also given by eq. ( 44).

F.2 TD WITH MARKOVIAN SAMPLES:

Consider the vanilla TD update in Bhandari et al. (2018) . Following the steps similar to those in Bhandari et al. (2018) for proving Theorem 3, and letting the constant stepsize α ≤ 1 λ A , we have

E θ t -θ * 2 2 ≤ (1 -λ A α) t θ 0 -θ * 2 2 + C 6 α λ A + C 7 α log( 1 α ) λ A ≤ e -λ A αt θ 0 -θ * 2 2 + C 6 α λ A + C 7 α log( 1 α ) λ A

where 0 < C 6 < ∞ and 0 < C 7 < ∞ are constants. Now let α = min{ C8 log(1/C8 ) , 1 λ A } where C 8 = λ A min{ 1 C6 , 1 6C7 }, it can be checked easily that with the total number of iterations at most

EQUATION

an -accurate solution can be attained, i.e., E θ t -θ * 2 2 ≤ . Since each iteration requires one pseudo-gradient computation, the total number of pseudo-gradient computations is also given by eq. ( 45).

:

We call the increment in each iteration of TD as "pseudo-gradient" because such a quantity is not a gradient of any objective function, but the role that it serves in the TD algorithm is analogous to the role of the gradient in the gradient descent algorithm.

Figures and Tables:

Figure 1: Error decay of VRTD with i.i.d. sample

Figure 2: Error decay of VRTD with Markovian sample

Figure 5: Comparison of error decay of VRTD and TD with changing stepsize in Frozen Lake problem

Now to upper-bound the term E[(b xi -b) (b xj -b)|F n,0 ], without loss of generality, we assume

Comparison of performance of TD and VRTD algorithms.

Table content: <table><tr><td/><td>Algorithm Variance Error Bias Error</td><td>Overall Complexity</td></tr><tr><td>i.i.d. sample</td><td>TD</td></tr></table>

At time-step t, suppose the process is in some state s t ∈ S, and an action a t ∈ A is taken based on the policy π(•|s t ). Then the transition kernel P = P(s t+1 |s t , a t ) determines the probability of being at state s t+1 ∈ S in the next time-step, and the reward r t = r(s t , a t , s t+1 ) is received, which is assumed to be bounded by r max . We denote the associated Markov chain by p(s |s) = a∈A p(s |s, a)π(a|s), and assume that it is ergodic. Let µ π be the induced stationary distribution, i.e., s p(s |s)µ π (s) = µ π (s ). We define the value function for a policy π as v π (s) = E[ ∞ t=0 γ t r(s t , a t , s t+1 )|s 0 = s, π], where γ ∈ (0, 1) is the discount factor. Define the Bellman operator T π for any function ξ(s) as T π ξ(s) := r π (s) + γE s |s ξ(s ), where r π (s) = E a,s |s r(s, a, s ) is the expected reward of the Markov chain induced by the policy π.

Table content: <table><tr><td>2.1 ON-POLICY VALUE FUNCTION EVALUATION</td></tr><tr><td>We describe the problem of value function evaluation over a Markov decision process (MDP)</td></tr><tr><td>(S, A, P, r, γ), where each component is explained in the sequel. Suppose S ⊂ R d is a compact</td></tr><tr><td>state space, and A is a finite action set. Consider a stationary policy π, which maps a state s ∈ S to</td></tr><tr><td>the actions in A via a probability distribution π(•|s).</td></tr></table>

, • • • d denoting the fixed basis feature functions of state s, and θ ∈ R d is a parameter vector. Let Φ be the |S| × d feature matrix (with rows indexed by the state and columns corresponding to components of θ). The linear function approximation can be written in the vector form as v(θ) = Φθ. Our goal is to find the fixed-point parameterθ * ∈ R d that satisfies E µπ v(s, θ * ) = E µπ T π v(s, θ * ).The TD learning algorithm performs the following fixed-point iterative update to find such θ * .θ t+1 = θ t + α t g xt (θ t ) = θ t + α t (A xt θ t + b xt ),(1)where α t > 0 is the stepsize, and A xt and b xt are specified below. For i.i.d. samples generated from the distribution µ π , we denote the sample as x t = (s t , r t , s t ), andA xt = φ(s t )(γφ(s t )φ(s t )) and b xt = r(s t )φ(s t ). For Markovian samples generated sequentially from a trajectory, we denote the sample as x t = (s t , r t , s t+1 ), and in this case A xt = φ(s t )(γφ(s t+1 ) -φ(s t )) and b xt = r(s t )φ(s t ). We further define the mean pseudo-gradient g

Table content: <table/>

Peer review (iclr2020):
This paper presents a non-asymptotic analysis of Variance Reduced TD (VRTD), proposed by Korda and La (2015), to apply variance reduction ideas to temporal difference learning, specifically TD(0) with linear function approximation. The algorithm closely follows ideas of stochastic variance reduction (SVRG) which is widely used for large scale empirical risk minimization. Specifically, the authors show VRTD converges (in expectation) to a neighborhood of the limit point using a constant step-size. Interestingly, this neighborhood can be made small using a large batch size M in both the IID and Markovian sampling regimes. From a technical standpoint, the work seems novel with interesting results although I am not sure if VRTD offers practical performance gains. Main points: 1) I am a bit confused by the presence of a constant variance error term in the results. Intuitively, with variance reduction, I was expecting convergence in expectation; not just to a neighborhood with constant error. In other words, the variance error term decaying with (and not M). This would imply a stronger result than what authors have currently. Note that vanilla SGD for strongly convex objectives also suffers from a constant variance error term (see for example Chapter 4 in Bottou et al., 2018). However, analysis of SVRG (Johnson and Zhang 2013) shows linear convergence for strongly convex objectives and claims sublinear convergence for convex objectives. While I appreciate the technical challenge in analyzing a 	extit{semi-gradient} method like TD vis-a-vis analyzing gradient descent for convex objectives, my understanding is that (Bhandari et al., 2018) showed a connection between the two. This connection makes me think if variance reduction can also help 	extit{get rid} of the constant variance error term when analyzing TD(0) with constant step-sizes. Can the authors clarify? Also, the authors might find it useful to look at (Lakshminarayanan and Szepesvari, 2018) which does in fact show convergence with a constant (problem instance independent) step-size for the IID case. I think that result only applies with iterate averaging but it might still be useful (certainly as a citation suggestion). 2) As a practical proposal, I wonder if VRTD has a potential benefit over vanilla TD(0). Essentially, the rates showed in this paper require samples. I wonder how vanilla TD would perform with samples coupled with a simple strategy of reducing the step-size by half when the value-function estimates stop changing. See Chapter 4 in (Bottou et al., 2018) for details. That would probably be a fairer comparison to help convince audience of VRTD as a practical alternative to TD(0). Minor points: - The counter example in Section 3.2 seems out of place. While it is important to point out the errors in previous analysis, I suggest the authors to flesh out the details in an Appendix section. - and seem undefined in the main body of the paper. - The constants in Theorem 1 and 2 seem complicated. Is there a way to simplify these for presentation purposes? Response to author comments. I thank the authors for their comments and changes to the draft. 1) The explanation makes a lot of sense. Since we cannot exactly estimate the population gradient, the variance error seems unavoidable with constant stepsize. I like the clarifications in Section 3.2 2) Thanks for clarifying that all the comparisons are done in terms of a fixed number of total gradient computations. Please add this clearly in the paper as well. I think the additional experiments and comparison with the new scheme I suggested above does a good job of convincing the readers of the practical usefulness of variance reduction. Although I am not sure how likely practitioners are to use this (both and M are problem dependent), in my opinion the paper presents a novel analysis of an important idea of variance reduction applied to Online TD. The experiments seem reasonable to suggest benefits. I’ll be happy to see this paper accepted. I have also updated my score. Some minor comments and suggestions: 1) In Theorem 1, constant D_2 depends on but there Algorithm 1 has no projection step. I think the authors assume that . If so, please state that somewhere. If not, maybe I missed something and would like a clarification. 2) Page 6 should have instead of . 3) Before stating the main results in Section 4, please restate the definition of for better readability. 4) Constant G seems to be undefined for Theorem 2. In fact, it seems that . This is what I meant by simplifying constants. Ensuring that these constants are optimized for presentation helps. 5) Theorem 2 has a dependence on . Maybe the authors should explicitly mention and discuss that. 6) The result for Markovian case requires the bias term to not dominate. This seems novel to me and would benefit from emphasis in the main body of the paper. 7) Equation 5 should have ’m’ instead of ’n’. 8) I always find large figures and clear (and) large axis labels very useful. Can the ‘iteration process’ graphs in Figure 1 be made more reader friendly? I’d like to see the behavior of vanilla TD more clearly. 9) Section A in the Appendix might benefit from more background. For example, what is . I am thinking this section to be more self contained with the readers not being compelled to read the proof in Korda and La (2015).