Reanalysis of Variance Reduced Temporal Difference Learning
Authors: Tengyu Xu
Zhe Wang
Yi Zhou
Yingbin Liang
Venue:  (2020)
Keywords: Reinforcement Learning
TD learning
Markovian sample
Variance Reduction

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 \cite{korda2015td}, 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 \cite{korda2015td}, 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.

Published as a conference paper at ICLR 2020
REANALYSIS OF VARIANCE REDUCED TEMPORAL DIF- FERENCE LEARNING
Tengyu Xu¹, Zhe Wang', Yi Zhou?, Yingbin Liang
i Department of ECE, The Ohio State University ,Columbus, OH 43210, USA $ Department of ECE, The University of Utah, Salt Lake City, UT 84112, USA 32 Cosu. edu, wang. 10 19882 edu, zhouutth. edu, 1iang. 8898888. edu
ABSTRACT
Temporal difference (TD) learning is 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 earning with Markovian samples. this work, we first point out the technical errors in the analysis of VRTD in Korda and La (013). 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 result, the overall computational complexity of VRTD to attain given accurate solution outperforms that of TD under Markov sampling and outperforms that of TT under i.i.d. sampling for sufficiently small conditional number.
INTRODUCTION
In reinforcement learning (RL), policy evaluation aims to obtain the expected long-term reward of a given policy and plays important role in identifying the optimal policy that achieves the maximal cumulative reward over time Bertsekas and Tsitsiklis (1995), Dayan and Watkins ( (992)): 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 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 (997). The finite sample analysis of TD has also been studied in Bhandari et al. (2018); Dalal et al. 20188); Cai et al. (2019); Srikant and Ying 2019).
Since each iteration of TD uses one or mini-batch of samples to estimate the mean of the pseudo- gradient TD learning usually suffers from the inherent variance, which substantially degrades the convergence accuracy. Although 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-poin 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 reduce the variance. In particular, Duu et al. (2017) showed that SVRG Johnson and Zhang (2013) and SAGA Defazio et al. (201)) can be applied to improve
We call the increment in each iteration of TD as "pseudo-gradient" because such quantity is not gradient of any objective function, but the role that serves in the TD algorithm is analogous to the role of the gradient in the gradient descent algorithm.

---

Published as a conference paper at ICLR 2020
the performance of batch TD algorithms, and Peng al. (2019) 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.
proposed two variants of SVRG to
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 (213)), VRTD has outer and inner loops. The beginning of each inner-loop (i.e. each epoch) computes a batch of sample pseudo- gradients so that each subsequent inner loop iteration modifies only one sample pseudo-gradient in the batch meeuo-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 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 discuss in Section 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); 8); Dalal
al. (2018b); (rikant 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. (201 8a); Bhandari et al. (2018) that vanilla TD converges only to neighborhood of the fixed point for constant stepsize and suffers from a constant error term caused by the variance of the stochastic pseudo -raddiet 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 al. (2018) that the convergence of vanilla TD further suffers from bias error due to the correlation among samples in addition to the variance error 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.dd. and Markovian sampling, to attain an e-accurate solution, what is the overall computational complexity (the total number of computations of pseudo-gradients of VRTD, and does VRTD have reduced overall computational complexity compared to TD?
1.1 OUR CONTRIBUTIONS
Our main contributions are summarized in Table[[and are described as follows.
For i..dd sampling, we show that a slightly modified version of VRTD (for avoiding bias error) converges linearly neighborhood of the fixed point solution for constant stepsize a, with the variance егтоr at the order of O(aMM), where M is the batch size for variance reduction. To attain an e-accurate solution, the overall computational complexity (i.e., the total number of pscudo- pseudo-gradient 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 (2018)); Bhandari 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 O1/MM) over the vanilla TD Bhandari et al. (2018). , where the bias error is at the order of O(a). As result, VRTD outperforms vanilla TD in terms of the total computational complexity by a factor of log?
At the technical level, our analysis of bias error for Markovian sampling takes different path from how the existing analysis of TD handles Markovian samples in Bhandari et al. (2018;; Wang et al. adopted by
(2017); Srikant and Ying (2019). Due to the batch average of stochastic sveudo-gradiens VRTD to reduce the variacce, the correlation among samples in different epochs is eliminated. Such an analysis explicitly explains why the variance reduction step helps further reduce the bias error.
2

---

Published as a conference paper at ICLR 2020
Table Comparison of performance of TD and VRTD algorithms.
Algorithm
Variance Error
Bias Error
Overall Complexity
TD
O(a)
NA
log
i...d. sample
VRTD
O(a/M)
NA
max
log (1)
A
TD
O(a)
O(a)
log"
(t)
Markovian sample
VRTD
O(a/M)
(L/MM)
max
log
(2)
Note: The results on the performance of 'TD are due to Blandari et al. 2018 and the reaults on the performance of VRID (which are highlighted by the color) are characterized by this work.
1.2 RELATED WORK
On-policy TD learning and variance reduction. On-policy TD learning aims minimize the Mean Squared Bellman Error (MSBE) |Sutonn (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 al. (2019). The convergence of averaged linear SA with constant stepsize has been studied in Lakshminarayanaa and Szepesvari (2018). the Markovian setting, the con-asymptotic convergence has been studied for on 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 redueed batch TD learning. Batch TD Lange et al. 2011)) algorithms are generally designed for policy evaluation by solving optimization problem
fixed dataset. In Du et al. (017)) 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 primal-dual batch gradient method. Furthermore, |eng 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- off-policy TD learning Sutton et al. (2008 2009); Liu et al. (2015); Wang al. (2017)) Karmakar and Bhatnagar (017)), two time-scale TD alg goritthmm Xu et al.
2 Dalal et al. (0188) (201)), fitted TD algorithms Lee and He (2019), SARSA Zou et al. (019) etc. The idea of the variance reduction algorithm proposed in Korda and La 2015)) as well the analysis techniques that we develop in this paper can potentially be useful for these algorithms.
PROBLEM FORMULATION AND PRELIMINARIES
2.1 ON-POLICY VALUE FUNCTION EVALUATION
We describe the problem of value function evaluation over a Markov decision process (MDP) AS P, 7), where each component is explained in the sequel. Suppose S Rd is compact state space, and A is finite action set. Consider a stationary policy ग, which maps a state a E S to the actions in A via probability distribution (-1s). At time-step I,, suppose the process is in some state E S, and an action E AA is taken based on the policy π (-]st). Then the transition kernel P( 9t, a;) determines the probability of being at state st+1
in the next time-step. and the reward r2 r(8t, az2 St+1) is received, which is assumed to be bounded by Tmax- We denote the associated Markov chain by p(s'ls) = En P(s'ls, (a)(s)s). and assume that it ergodic. Let lrn be the induced stationary distribution, i.e.. E, (( (s) (s'). We define the value function for a policy as TTTh (s) E 7'1(s1, 04, S2+1) 880 8, m). where 7 E (0, 1) is the discount
3

---

Published as a conference paper at ICLR 2020
factor. Define the Bellman operator 7 for any function ((s) as (()) == rr)ss) + >5
where r" (s) Pars"ler(ss a, s') is the expected reward of the Markov chain induced by the policy It is known that e"(ss is the unique fixed point of the Bellman operator I i.e. e=(ss) u (s).
In practice, since the MDP unknown, the value function vx (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 0(s, 8) Φ(s) of the value function, where o(s) = [d1 (s),-
@s(s)] with (s) for = 1, 2. .. dd denoting the fixed basis feature functions of state 8, and 0 E Rd is a parameter vector. Let & be the |S| cl feature matrix (with rows indexed by the state and columns corresponding to components of 0). The linear function approximation can be written in the vector form i(0) 40. Our goal is find the fixed-point parameter 0* IRd that satisfies Ep, 0(s, 8*) = E,,, T (s. 0*). The TD learning algorithm performs the following fixed-point iterative update to find such 0-.
Bi+1 = 0g + argr, (0s) = 0, (1,,, bm.),
(1)
where a > the stepsize. and Az, and by, are specified below. For i..d. samples generated
from the distribution Nr., we denote the sample as I₁ = (s,,r,, and Ap, = d(s:)(r0(s))
((+))) and by2 = r(s)))(st). For Markovian samples generated sequentially from a trajectory, we denote the sample as = (st, Ft. 1)+1); and in this case Ar, and bn, = =st)) We further define the mean pseudo-gradient g(0) = AO + where Ex, [)(s)())(s))) o(s)) and b E,,,, (r())(())))))))))))))))))))))()) We call (0) pscudo- 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 0" A-1 'b at a sublinear rate (11 with diminishing stepsize
((x)))
ag = O(/tt) using both Markovian and i.i.d. samples Bhandari et al. 2018);; Dalal et al. (2018s) 8a).
Throughout the paper, we make the following standard assumptions Wang al. (2017 7 Korda and
.a (2013): Tsitsiklis and Van Roy (997); Bhandari et al. (2018).
Assumption (Problem solvability). The matrix A is non-singular. Assumption 2 (Bounded feature). ||ø(s)]l2 I for all S.
Assumption 3 (Geometric ergodicity). The considered MDP is irreducible and aperiodic, and there exist constants x > 0 and p E (0, 1) such that
supdrv (P E -|so = s), S kp'. Vt 2
sES
where drv (P, Q) denotes the total-variation distance between the probability measures P and Q.
Assumption 1 requires the matrix A to non-singular so that the optimal parameter d* - A is
well defined. Assumption can be ensured by normalizing the basis functions { Assumption 3 hollds 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-reducee 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 (015
Since the standard TD learning takes only one sample in each update as can seen in eq. T.. typically suffers from 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 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 samples as estimator of the mean aeeudo-gradien Then, each inner-loop update randomly takes
9m (0m-1) is computed based on these
4

---

Published as a conference paper at ICLR 2020
Algorithm 1 Variance Reduced TD with iid sam-
Algorithm Variance Reduced TD with Marko- vian samples Korda and La (2015)
ples
Input:
batch size M, learning rate and initialization lg
Input:
batch size M, learning rate and initialization
1: for m = 1 1...... do
1: for 1, ..... do
2:
0m.0 = 0m
2: 0m. mm-1
3: Sample set Bm with samples indepedently
3: gon go. (mm-mm M -i= 92, (8m-1)
from the distribution
4: for 0, 0,,,..., ...,M..
4: Im (0)
E...B.. In; (0m-1)
5: Sample Jm, uniformly random in {(m
5: for 1 0,
do
1)M, m.M - 1} from trajetory
6:
Sample Kim, indepedently from the distribu-
6: 0m.r+1 1l, (0m. + a a(f35m. (0m,t)
tion per
7:
Om.i+1 = 0m.t + agg (0m.t) -musm, (8m-1) + Im (0m-))
7:
-9njm, (6m-1) + 9o. (0 (0m=
8:
8: end for
9:
end for set Om Om,e for randomly chosen L
9: set Pm = Om. for randomly chosen t E
10:
(1.2.....A M}
[1,2,... ...,, M}
10: end for
11: end for
Output: 0g
Output: 0g
one sample from the batch, and updates the corresponding component in 9m (0...)) Here, II in Algorithm 2eantthmm@eenteee denotes the projection operator onto a norm ball with the radius Rg. The idea is similar to the SVRG algorithm proposed in JJhnsson 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 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-gradiee gm gm. (0m-1) computed the beginning of each epoch m should necessarily introduce non-vane non-vanishing variance error for a fixed stepsize, because it cannot exactly equal the mean (i.e. population) ascudo-gradien g(0m-1). Furthermore, due to the correlation estimator in expectation (with regard the randomness of
among samples, the the sample trajectory) does not equal to the mean pseudo- -oraidi-rrriett,, 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 (with properly chosen A defined as AA = 2lAmax(AA +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.
we further provide a coumter-example to show that one major technical step for characterizing the convergence bound in Korda and La (2055) does not hold. The goal of this paper to provide a rigorous analysis of VRTD to characterize its variance reduction performance.
In Appendix B
4 MAIN RESULTS
As aforementioned, the convergence of VRTD consists of two types of errors: the variance error due inexact estimation of the mean pseudo-gradient and the bias error due Markovian sampling. In this section, we first focus on the first type of eтror and study the convergence of VRTD under i.i.d. sampling. We then study the Markovian case further analyze the bias. In both cases, we compare the performance of VRTD to that of the vanilla TD described in eq. (I) to demonstrate its advantage.
5

---

Published as a conference paper at ICLR 2020
4.1 CONVERGENCE ANALYSIS OF VRTD WITH I.I.D. SAMPLES
For i..dd samples, is expected that the bias error due the time correlation among samples does not exist. However, if we directly apply VRTD (Algorithm 2 originally designed for Markovian samples, there would be bias term due to the correlation between the batch every inner-loop updates. Thus, we slightly modify Algorithm 2 Algorithm 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
estimate and
In this way, the new independent samples avoid the correlation with the batch pseudo-grading evaluated at the beginning of the epoch. Hence, Algorithm T does not suffer from an extra bias error.
To understand the convergence of Algorithm at at the high level, we first note that the sample batch pscudo- pscudo-gradient cannot estimate the mean pseudo g(0m-1) exactly due to its population nature. Then, we define 6.n (f.)) Inn (6 g00m-1) such aseudo-gradient estimation error, our analysis (see Appendix D shows that after each epoch update, we have
1
E
8m 0-)
Fm.
1/M + 4a² 7)2
0 m0-
8-
2a
E
em (8m (0n- Fm.0
(2)
ad - 4a 7)²
Aa 40 + 7)²
where Fm,o denotes the o-field that includes all the randomness in sampling and updates before the mnth epoch. The first term in the right-hand side eq. (2) captures the contraction property of Algorithm [and the second term corresponds to the variance of the pseudo-gradien estimation error. can be seen that due to such an error term, Algorithm Dis expected to have guaranteed convergence only to a neighborhood of 6", 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]] I
Theorem 1. Consider the VRTD algorithm in Algorithm 7 Suppose Assumptions D3 hold. Set
AA and the batch size M constant stepsize a < 8(1+g)²
> aAA 80(1+))
Then, for all m E N,
0m - -o-10 001[]] - <C cCml|06
1 -001 (1 (1- - 4a(1 7)2
2D20
E
(3)
where C1 : [aa11 + 7)² + 4(2 4(2+1)3a2+1
As 2a(140) (with C1 due to the choices of a and
add
M), and D2 4((1 + 7)2 R3 + r m.
We note that the convergence rate in eq. (3) can be written in a simpler form as Ell@mm - 0- S 1T - 111 + (aaM))
Theorem shows that Algorithm [ 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 ( which can be made 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 ((a) Bhandari al. (0118) for a fixed stepsize. Thus, a small stepsize a is required in vanilla TD to reduce the variance error, which, however, slows down the practical convergence significantly. In contrast, this is not problem for VRTD, which can attain a high accuracy solution while still maintaining fast convergence at desirable stepsize.
We further note that if we have access to the mean -grddiit g( in each epoch m, then the error term ||0m 1'1 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 C1 which 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 (0013). 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.

---

Published as a conference paper at ICLR 2020
Based the convergence rate of VRTD characterized in Theorem under i..d. sampling, obtain the following bound on the overall computational complexity.
Corollary 1. Suppose Assumptions hold. Let a 16(1+5].. M = [max 31--
D3
33(1+)) F.
X
Then, for any > O, e-accuracy solution (i.e., Bl|0m. - 0-1 < e) can be attained with at most
m = llog 2 -100-00'12 log C, iterations. Correspondingly, the total number of -rradiet
computations required by VRTD (i.e. Algorithm [ under i..dd sampling to attain such an c-accuracy solution is at most
1
log (
O max (e X
Proof. Given the values and M in the theorem, it can be easily checked that El 1-1 S
for [log 21100-00112 / log J Then the total number of gpeudo-gradient computations is given by M 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 = (c)). If the samples are i.i.d. generated, it can be shown (see Appendix F.1 that the vanilla TD requires O EX log (1) gocudo-gradien computations in total to obtain an e-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 case, we expect that the convergence of VRTD to have both the variance error due to the pseudo granddet estimation (similar to the case with i..d. samples) and the bias error due the correlation among samples. To understand this at the high level, we define the bias at each iteration &m (0) (0 0*) (gm (0) g(0).. Then our analysis (see Appendix Eb shows that after the update of each epoch, we have
0- 2=
E
0m
F Pm.
1/M + 30 + 7
0m- 0- 00122
3o AA
E
[1sm (0')11 |mmo]
ads- 3a (1 + +7)²
-3a(1 + 7)2
M
2
Σ
IE (0m.)) [moo]
A - 30(1 7)
The first term on the right-hand side of eq. (4) captures the epochwise contraction property of Algorithm 2 The second term is due the variance of the pseudo-gradient estimation, which captures how well the batch pseudo-gradient 9m (0*) approximates the mean pseudo-gradient g0*)) (note that g(0*) 0). Such a variance 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 eтror term, we provide the following lemma that characterizes how the bias error is controlled by the batch size M.
can be shown decay zero as the batch size gets
Lemma 1. For any m >> 0 and any 0 E Ba, which is ball with the radius Ra, we have
X1 E| 11 Fr.o)
8[1 + (x 1)p)
[[Em(())
[R] + 7)² + + m
Xa - p)M
where the expectation is over the random trajectory, is treated as a fixed variable. and 0 < Co < 00 constant depending only on the MDP.
7

---

Published as a conference paper at ICLR 2020
Lemma 1 shows that the bias enror diminishes as the batch size M increases and the algorithm approaches to the fixed point 0* To explain why this happens, the definition &m (m(() immediately yields the following bound:
(1)n(0)- 9(0) XA 11--6-12
5m S Aa
1-
(5)
The first term on the right-hand hand-side of eq. (5) can be bounded by the concentration property for the ergodic process as gm (0) = x 2im (m- 1)M Ir; (0) 3 g()) As M increases, the randomness due to the pseudo-gradient estimation essentially averaged out due 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 E[s, (0)] = (a (og(()))) Bhandari et al. (0118) In order to reduce the bias and achieve a high convergence accuracy, the stepsize a 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 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 D3 hold. Set the
constant stepsize a
Aa and the batch size M 12(1+>}²
Then, we have
0.bada Go (1+7)²
2 CTT
0 0- 00 (1 (1- (1)0.))0.5.+ 30(1 + 7)
3Csa C2/dA
E
0m
0"
S
(6)
2
133+3n 2
where Ci
0.5 - 3ex (I+y) (with C₁ < due to the choices for a and M), C2 =
(x 1)0(( -
and C4 [(1 + Ro + Tima]2 3pxG((1+-)Rottmmee I-p
We note that the convergence rate in eq. (6) can be written in a simpler form as E1]i0m 0 0-1 CT'1100 - 0-1 + O(1/M).
Theorem Zishows that VRTD (i.e., A with Markovian samples converges to neighborhood of 6* at Tinear rate, and the size 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 pseudo- gradient estimation eиror 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 (1/M)). Therefore, the
variance reduction in Algorithm 2 reduces both the variance and the bias of the pseudo-gradient estimator.
Based the convergence rate of VRTD characterized in Theorem 2 Junder Markovian sampling, obtain the following bound on the corresponding computational complexity.
Aa Corollary 2. Suppose Assumptions hold. Let a 21(1+7)² and M = [[ 32C2++4CC + 100(1 + 3(1-C:)
1 7) maxf? :: <x3, }1. Then, for any > O. e-accuracy solution (i.e., 0 0- 2 < c) can be
2 211ōp-00 0" log 2,1 iterations. Correspondingly, the total number of c
attained with at most m = [log
pseudo-gradie gradient computations required by VRTD (i.e., Algorithm 2 under Markovian sampling to attain such an e-accuracy solution is at most
O max
{ EX
124 1og !
Proof. Given the values of a and M in the theorem, it can be easily checked that Eli0... 0-11² <
for m = [log 2010--0-112 log 2 1. Then the total number of useudo-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. (218)) with the constant stepsize O(e/ log(lo)))) [/c)).. Under Markovian sampling, it can be shown (see Appendix F.2) that vanilla TD requires O log" (t)) pseudo-gradient computations in total to obtain an e-accuracy
8

---

Published as a conference paper at ICLR 2020
solution. Hence, in the Markovian setting, VRTD outperforms vanilla TD in terms of the total computational complexity by a factor of log To intuitively explain, we first note that the correlation among data samples in the Markovian case also causes a bias error in addition the variance enror. 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) 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 attain an e-accurate solution, and yields an additional log factor in the total complexity compared to VRTD.
EXPERIMENTS
In this section, we provide numerical results to verify our theoretical results. Note that in Appendix A we provide further experiments two problems in OpenAl Gym Brookmman al. (2016) and one experiment to demonstrate that VRTD is more sample-efficient than vanilla TD.
We consider MDP with 7 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 & E R50x4 is randomly and uniformly sampled between 0 and 1. The baseline for comparison the vanilla TD algorithm, which corresponds to the case with M = 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. the Markovian setting, we sample the data from a MDP trajectory. In the i.i.d. setting, sample the data independently from 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 [nd 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- soaddgg 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 I and Theorem [] We also observe that increased batch size substantially reduces the error without much slowing down the convergence, demonstrating the desired ad advantage of variance reduction. Moreover, we observe that the error of VRTD with i.i.d samples smaller than that of VRTD with Markovian samples under all batch size settings, which indicates that the correlation among Markovian samples introduces additional errors.
the corresponding stationary distribution.
15
3.5
TD: M-1
VRTD: VRTD:M-60 M=50
VRTD: M-600
VRTD: M-1000
VRTD: M-2000
10:01p
Convergecca
2.5
1.5
pasudo- gradient computations
Ratch (M)
(a) left: iteration process; right: averaged convergence error
Figure 1: Error decay of VRTD with i.i.d. sample
6 CONCLUSION
In this paper, we provided the convergence analysis for VRTD with both i.i.d. and Markovian samples. We developed novel technique to bound the bias of the VRTD demonstrate the advantage of VRTD over vanilla TD the reduced variance and bias errors by the batch size. We anticipate that such variance reduction technique and our analysis tools can be further applied other RI algorithms.
estimator. Our result

---

Published as a conference paper at ICLR 2020
15
3.5
TD:
VRTD: M-50
VRII: M--00
3-
VRTID M- 1000
10
VRTD: M--000
Gonvegence
1.5
0.5
2.5
of paeudo-gradient computations
(a) left: iteration process; right: averaged convergence crror
Figure 2: Error decay of VRTD with Markovian sample
ACKNOWLEDGMENTS
The work was supported in part by US National Science Foundation under the grants CCF-1801855, ECCS- ECCS-1818904 1818904, and CCF-190929) The authors would like thank Bowen Weng at the Ohio State University for the helpful discussions on the experiments. The authors would also like to thank few anonymous reviewers for their suggestions on the analysis of the overall computational complexity as well as additional experiments, which significantly help to improve the quality of the paper.
REFERENCES
Bertsekas, D. P. and Tsitsiklis, J. N. (1995). Neuro-dynamic programming: An overview. In Proceedings of 34th IEEE Conference on Decision and Control, volume 1, pages 560-564.
Bhandari, J., Russo, D., and Singal, R. (2018). A finite time analysis of temporal difference learning with linear function approximation. In Proc. Conference on Learning Theory (COLT), pages 1691-1692.
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016). OpenAl Gym.
Cai, Q., Yang, Z., Lee, J. D., and Wang. Z. (2019). Neural temporal-differee learning converges to global optima. arXiv preprint 1905: 10027.
Dalal, G., Szörényi, B., Thoppe, G., and Mannor, S. (2018a). Finite sample analyses for TD (0) with function approximation. In Proc. AAAI Conference on Artificial Intelligence (AAAI).
Dalal, G., Szorenyi, B., Thoppe, G., and Mannor, S. (2018b). Finite sample analysis of two-timescale stochastic approximation with applications reinforcement learning. In Proc. Conference Learning Theory (COLT).
Dayan, P. and Watkins, C. (1992). Q-learning. Machine Learning, 63)):7992292.
Dedecker, J. and Gouëzel, S. (2015). Subgaussian concentration inequalities for geometrically ergodic Markov chains. Electronic Communications in Probability, 20.
Defazio, A., Bach, F., and Lacoste-Julien, S. (2014). SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems (NIPS), pages 1646-1654.
Du. S., Chen, J., Li. L., Xiao, L., and Zhou, D. (2017). Stochastic variance reduction methods for policy evaluation. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1049-1058.
Hu, B. and Syed, U. A. (2019). Characterizing the exact behaviors of temporal difference learning algorithms using Markov jump linear system theory. arXiv preprint arXiv:
10

---

Published as a conference paper at ICLR 2020
Johnson, R. and Zhang, T. (2013). Accelerating stochastic gradient descent using predictive variance reduction. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 313-323.
Karmakar, P. and Bhatnagar, S. (2016). Dynamics of stochastic approximation with Markov iterate- dependent noise with the stability of the iterates not ensured. arXiv preprint 160i 0.2.1222
Karmakar, P. and Bhatnagar, S. (2017). Two time-scale stochastic approximation with controlled Markov noise and off- off-po ceamoral--dffeeeeee learning. Mathematics of Operations Research, 1301):130-151.
Korda, N. and La, P. (2015). On TD (0) with function approximation: Concentration bounds and centered variant with exponential convergence. In Proc. International Conference on Machine Learning (ICML), pages 226-634.
Lakshminarayanan, C. and Szepesvari, C. (2018). Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International Conference on Artificial Intelligence and Statistics, pages 1347-1355.
Lange, S., Gabel, T., and Riedmiller, M. (2012). Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer.
Lee, D. and He, N. (2019). Target-based temporal difference learning. In International Conference on Machine Learning (ICML).
Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., and Petrik, M. (2015), Finite-sample analysis of proximal gradient td algorithms. Proc. Uncertainty Artificial Intelligence (UAI), pages 504-513, AUAI Press.
Maei, H. R. (2011). Gradient temporal-difference learning algorithms. PhD thesis, University of Alberta.
Narayanan, C. and Szepesvári, C. (2017). Finite time bounds for temporal difference learning with function approximation: Problems with some "state-of-the-art results. Technical report.
Peng, Z., Touati, A., Vincent, P., and Precup, D. (2019). SVRG for policy evaluation with fewer gradient evaluations. arXiv preprint 1rXiv:1906.03704.
Rummery, G. A. and Niranjan, M. (1994). On-line Q-learning Using Connectionist Systems, vol- ume 37, University of Cambridge, Department of Engineering Cambridge, England.
Srikant, R. and Ying, L. (2019). Finite-time error bounds for linear stochastic approximation and TD learning, Proc. Conference Learning Theory (COLT).
Sutton, R. S. (1988). Learning to predict by the methods temporal differences. Machine Learning. 3(1):9-44.
Sutton, S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D.,, Szepesvári, C., and Wiewiora, E. (2009). Fast gradient-descent methods for temporal-difiie difference learning with linear function approximation. Proc. International Conference on Machine Learning (ICML) pages 993-1000.
Sutton, R. S., Szepesvári, C., and Maei, H. R. (2008). A convergent o(n) algorithm for off- temporal-difference learning with linear function approximation. Advances Neural Information Processing Systems (NIPS), 21611):1699-661.
Tadić, V. (2001). On the convergence of temporal-difference learning with linear function approxima- tion. Machine Learning, 42(3):241-267.
Tsitsiklis, J. N. and Van Roy, B. (1997). Analysis of temporal-diffference learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 1075-1081.
Wang, G., Li, B., and Giannakis, G. B. (2019). A multistep Lyapumov approach for finite-time analysis of biased stochastic approximation. arXiv preprint arXiv: 19X.:29909.04299
11

---

Published as a conference paper at ICLR 2020
Wang, Y., Chen, W., Liu, Y. Ma, Z.-M., and Liu, T.-Y. (2017). Finite sample analysis of the GTD policy evaluation algorithms in Markov setting. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 5504-5513.
Xu, T., Zou, S., and Liang. Y. (2019). Two time-scale off-policy td learning: Non-asymptotic analysis over markovian samples. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 10633-10643.
Yu, H. (2017). On convergence of some gradient- grasient-based temporal-differencee algorithms for off- aff-policy learning, arXiv preprint arXiv: 1712.096...
Zou, S., Xu, T., and Liang, Y. (2019). Finite-sample analysis for sarsa with linear function approxi-
mation. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 8665-8675.
12

---

Published as a conference paper at ICLR 2020
Supplementary Materials
A ADDITIONAL EXPERIMENTS
In this section, we assess the practical performance of VRTD (Algorithm 2 on two problems in OpenAl Gym Brockman et al. (2016), which are Frozen Lake (4 x 4) and Mountain Car. We also provide an additional experiment to demonstrate that VRTD is more sample-efficiet than vanilla TD.
A.1 FROZEN LAKE
Frozen Lake is a game in OpenAI Gym, which is designed by an MDP with finite state and action space. An agent starts from the starting point It returns to the start-point every time it reaches "hole" or the "goal". The agent receives a reward 1 only when reaches the goal and otherwise. Each transition probability is randomly sampled from [0, 1] and normalized to one, and each component of the feature matrix & E R is also randomly sampled from (0, 1]. Given the feature matrix and the transition probability, the ground truth value of 0" can be calculated, which is used to evaluate the error in the experiments. We set the stepsize to be a = 0.1 and run vanilla TD (M = 1) and VRTD with the batch sizes M = 50, 500, 1000, 2000. Note that .M 1 corresponds to the base line vanilla TD. We compute the squared error over 1000 independent runs. The left plot in Figure 3 shows the convergence process over the number of pseudo-ge gradient computations and the right plot in 3 shows the convergence error averaged over the last 10000 iterations. It can be observed that VRTD achieves much smaller error than TD, and increasing the batch size for VRTD substantially reduces the error without much slowing down the convergence.
and can only transport the neighbor blocks.
x10
0.04
Mm11
VRTD: Ma50
VRTD: M-00C
0.03
M=1000
VRTD: M=2000
Converpence Enor
e
0.02
0.01
0.5
1.5
2.5
2000
of peeudo-gradient computations x
Batch Size (M)
(a) left: iteration process; right: averaged convergence error
Figure Error decay of VRTD in Frozen Lake problem
A.2 MOUNTAIN CAR
Mountain Car is a game in OpenAl Gym, which driven by an MDP with an infinite state space and finite action space. At each time step, agent randomly chooses an action E {push left, push right, no push). In this problem, the ground truth value of 0* is not known. In order to quantify the performance of VRTD, we apply the enror metric known as the norm of the expected TD update given by NEU= | [| where is the temporal difference Sutton et al. (2009); Maei 1) The state sample is transformed into feature vector with the dimension 20 using an approximation of a RBF kernel. The agent follows a random policy in our experiment and we initialize 0, O. At f 0, the agent starts from the lowest point, receives reward of -1 at each time step, and returns to the starting point every time reaches the goal. We set the stepsize to be 0.2 and run vanilla TD (M 1) and VRTD with batch size M 1000. After every 10000 aseudo-gradient computations, learning is paused and the NEU is computed by averaging over 1000 test samples. We conduct 1000 independent runs and the results are reported by averaging these
13

---

Published as a conference paper at ICLR 2020
runs. Figure shows the convergence process of the NEU versus the number of sreudo-gradien computations. can been seen that VRTD achieves smaller NEU than vanilla TD.
VATD: M-1000
-2
log(NEU)
-4
-6
-8
2
3
4
7
8
9
10
paeedo-gradiee computations
x10"
Figure 4: NEU decay of VRTD in Mountain Car problem
A.3 COMPARISON BETWEEN VRTD AND TD WITH A CHANGING STEPSIZE
In this subsection, we provide an additional experiment 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 AA. 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.
0.05
VRTD: M=50Co
0.04
0.03
0.02
0.01
3
peeudo-gradient computations x10=
Figure 5: Comparison of error decay of VRTD and TD with changing stepsize in Frozen Lake problem
B A COUNTER EXAMPLE
In this section, we use a counter-example 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 in Korda and La (201)). For the following defined E(0)
(0) (0 0T*TT [E(x TolTel u(F.)) Ev.o. (v [T)]((( 8*),
14

---

Published as a conference paper at ICLR 2020
where y denotes the stationary distribution of the corresponding Markov chain, claimed that the following inequality holds
Korda and La (0155)
[e((0)l2 s 2H [[[(]]Fa) (u))1,
This not correct. Consider the following counter-example. Let the batch size M and dimension of the feature vector be one, i..., E || Hence, all variables in eq. (8 and eq. 7 are scalars. Since the steps for proving eq. (8) in Korda and La (2013) do not have specific requirements for the transition kernel, eq. should hold for any distribution of Thus, suppose e follows the uniform distribution over 3, 3 Further assume that in the n-th epoch, the samples of v are given
by {1, -3). Recall that B(-1F,)) the average over the batch samples the n-th epoch. We have:
[(u(Fn)) =0, B(o - 14
Ev.o,, (v) O, Ex, (v²) 3,
Substituting the above values into eq. (8) yields
||(0)]12 14
3) (0 ~ 2H 0
which obviously does not hold in general when 0 + lr. Consequently the second statement in Theorem 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 E Rdddd we denote [W]], as the spectral norm of W and ||W|| as the Frobenius norm of W.
Lemma 2. For any v; (8i, Ti, 8)) (i.i.d. sample) or n; = (8s, r'; 8141) (Markovian sample), we have Ar. < 1 + 7 and lbbr, ll2 S Tmax-
Proof. First consider the case when samples are i.idd Due to the definition of Az,, we have
|| Az, 112 [1(())))))(s) (1
< (((())(7008)) (ss)))
S (0(s))(($)) T + [(((s:)o(s;)
< 11+%.
Then, consider bry
|| = |lr,, ((s)) S Tmax [1@(s:)l12 Tmax-
Following similar steps, we can obtain the same upper bounds for the case with Markovian samples.
Lemma 3. Let G = (1 + Ro + Tmax Consider Algorithml 2 For any >> 0 and 0 S 5 M - 1,
we have [192)mm (fm.))ll2 Desm: (8m (0m-1) 2' 9m (0m-z))
< G.
Proof. First, bound || 9 (0m,e) 1| as follows.
| / (0 (0m,e)lls
|Anmm Om,t bom.lll ll2
$ A elle 110m.t 1b9m.
$ (1 + Ro -max.
Following the steps similar to the above, we have
5 G. Finally for
| (8m-1) have
mi-
gesm. (0m (8m-1)
Σ
9z. 10 (0m-1)
=
M
im (m
1)M
15

---

Published as a conference paper at ICLR 2020
m.M
Σ
Dz. (mm-
M
i= 1)M
S G,
(10)
where eq. (10) follows from the last fact [ (0m (0m-1) SG.
Lemma 4. Define D = 2(1 + 7) and D2 4((1+ (((1+))2BB) 7)2 R2 + max)). For any O E R2, we have 11 (0)12 < Dj ||0 0- D2-
Proof. Recalling the definition of Jays and applying Lemma we have
l19,, (0) ||A,, 0 + ba, 112
||A,, (0 8*) (A,, 0* + )12
- 2 21, 0 + 2 ||, 0r + bz, l12
s 2 2| 11 0/1 4(1 :ed::1: 112 |10 1|b 112)
- 2(1 + 7)² 100 11 + 4(1 + R2 + max)
D1 0 1 D2-
Lemma Considering Algorithm
with Markovian samples. We have |[[[A]|P]] All S
(1+ 7)pp' and [b PP] bl]2 S Tmaxtssp -4 for <i<j.
Proof. We first derive
/ Ag, dP(si
/ Ar. du
[B[A A =
$ / |P, As, dualle
dua
$ (1 1(Pe $ (1 + ))pp"
Following the steps similar the above, can derive ||b P.l bll2 2m
D PROOF OF THEOREM I CONVERGENCE OF VRTD WITH L.L.. SAMPLES
Recall that Bn, is the sample batch drawn at the beginning of each m-th epoch and æi,5 denotes the sample picked at the j-th iteration in the i-th epoch in Algorithm| 1 o-field when 0g is deterministic vector. Let (A U B) indicate the smallest a-field that contains both A and B. Then, we construct of o-fields the following incremental way.
We denote a (0)) as a trivial
Fi.o = (00), Fi,1 oFFi. (o( uo(r)))) FL,M = (Fi,(M)))) Ua(Zi F2.0 oFF (o()) Fai (F20 Uo (B2) (o(2z))), Fz.m a (F2 Ua(D2M)),
Fm.o = ( 1).M Col.uoo(OA (o(ōm-1)), Fm1 = oFFm, (a(Bm) U (Z( FM.M = (FF,(MM)-)) Ua(am.)))
The proof of Theorem proceeds along the following steps.
Step 1: Iteration within the m-th epoch
16

---

Published as a conference paper at ICLR 2020
For the m-th epoch, consider the last update (i.e., the M-th iteration in the epoch), and decompose its error into the following form.
- 97sm, (0m-1) + gm (0m- 0" 1
1l0m.M 0-1
0m. + at 9 (0m,M-1) +00005mmmmm
110m,M-1 - 0-11 2a(0m. -00) A0im. (0m,
Io (0m-1) + Im (0((m-1)
9 (0m,M-1) masm, (0m-1) + Im (0m 1
(11)
First, consider the third term in the right-hand side of eq. we have
323mm (0m, Dusm, (0m-1) 1) + Im (0m-1)
Irsm..e (0m, Ixsm. (0m-2) + ((0mm=1) 1) 11( +2 gm 100-11)9(0mm)))
gommae (9m,N-1) - 3m (0)) (9 (0m-1) - Ju (0*)) (g(0m-1) - g(0
9m (0m-1) - g(0mm ((0m--))
Or I [8r) (0 (mm-1) 3 (8*)) (g(0m-1) 9(07))
1mmm M (0m,As-)
+ 2 gm 9m (0m-1) g(0m
(12)
Then, by taking the expectation conditioned on Fm,M-1 on both sides of eq.
12 we have
E
9oim, as (0m,ar-1) I1 (0m-1) 1) + 9m (0
Mm,M-1
(3)
Arsm. (0m,As-1) Irsm.n (0r) 1// F Fm,M-1
41E
4E
(9ssmma (8m-1) - Ix (8*) EE [f[9 (8m-1) m (8*)
Pm.M-1
9m (0m-1) -9(0))) 990mm-)) Fm
2E
(18)
1mmmmmmmmmmmm + 4(1 + ") 110m--100 1 1m
< 4(1 +
Im (0m-1) - ((0m- 100m-i))1 Fm
+ 2E
where (i) follows from the fact that El (0m-1) I2sm.s (8*)) Fm. g(0m=1) g(0))
and (ii) follows from the inequality B[(X EX)2] TX and Lemma 2 expectation conditioned on Fm.M-1 on both sides of eq.
Then, taking the
(II) yields
[10m, 0-112 Pm.
110mm..------ 112 22(20, - - T
g (0m, (
gesm, (0m-1) + Im (mm Fm
azZE | (mm,M-1) Iosmmar (0m-1) + Im (0m 111?
5 110m,M-1 0-112 +
- 00) g(0m,,--))
+ +2a(0m -0)) (B 9m (0m-1) Fm Fm,
g(0m-1)
4a (1) (0)]|10,,MM-111 - 0-113 4c² 7) 10m-1
17

---

Published as a conference paper at ICLR 2020
+ 2 |m |1 (00mm0)) 900m= 1)1 Fm.M--1
(1))
100m 00-12 ads 110m.11- - -0- 2al {m (m(mm-1) Mm
+ 2 (1 + x)² 11 0-112 + 4a + 7)² 00 00-m - 0
+ 2 || | (mm(0m1)) =((mm=)) ->11= P'm Fm,M-11
(161)
110, - -00 - [add -4a² + 7) -0 4a + 7)² | 0m 0-
+2alE Em ()0--))(Fmmaa Fm. 20 [|mm(mmm1))) - g(( -g(0m-1) F Fm.M-1
(13)
where (1) follows from the fact that E (9rmm (0m-1) Fm,M- g(0m-1). In (ti) define
A the absolute value of the largest eigenvalue of matrix (A" A), which is negative definite according to Tsitsiklis and Van Roy (1997). In (dit) we define &m (0) - (0 - 0*) (gm(0) - (0))
for 8 Rd. Then, by applying eq. (13) iteratively, we have
110m 0r Fm.o]
M-1
< 110,0 10
jadd 40² + 7
Σ
R 110m. -0112 Fm.o] + 4Mo + + 0 - 00-12
1=
2aME
Em (0m-1) + 22
- Fm.0
|1
(14)
For all sis M, we have
E
Sm (0m- Fm Fm.0 =
9m (0m- Fmo] g(0m-1)
B[Ar, Om ber [Fm,o] (A0m + b)
M
ie
E[Ac,|Pm.ol) - -AJōm + [[
1
Σ
Elbe, (m b)
M
BEB...
Then, arranging terms in eq.
14 and using the above fact yield
M
lads - 442
E
110m. - 0011 Fm.o]
0 0m-1- - 0- 001 2M |m (0m-1) (00m-1) 1 Pmo
$ + 4Ma + 2]
(15)
Finally, dividing eq.
15) by Jads 4a² + M both sides yields
0m 0r 1 Fm.D
1/M + 2a² 7)
0m-1
+ Xa 4c(11 + 7)2
2a
E 9m (0m-1) - -9(0mm Fm.
ada 21 + 7)
(16)
Step 2: Bounding the variance error
For any 0 0 k < m 1, we have
9m (0m-1) - g(0m-1) 1 Fm.
(17)
18

---

Published as a conference paper at ICLR 2020
E
Σ Bm
In; (0m-1) g(0mm-1)
Fm.
Σ
yr, (0m-1) - g(0m=
Pm.
M
iEBm
(E mm
g2, (0m--) g(0 -g(0m-1))
((0m-i))(E
E
Io, (0m-1) g( g(0m-1) Fmm
M
jeBm
E
Σ
E
-mm00m - -9(mm-)mmmmm))))m Io,, (mm-1)
9(8m-1)) Fm.o)
M
R JeBm
E
ger (0m-1) - 9(0mm1) Fm..0
M
Nw: (0 (0m-)) - 1B[2 [o (0m-1) Fm.oo ||2 Fmoo]
E
M
gw: (0 1111 Fmm.
1 M
Di ( - 00112 +Dz)) D2)
E
(18)
M
where eq.
(18 follows from Lemma
Step 3: Iteration over m epoches First, we substitute eq.
(18) into eq. 16 to obtain
E
pm -
Fm.
- Ci || 0
0m-1
001
8+
2D2a
(19)
(AA
1o1-4a(1+20 +a(1+7)))M
where we define C₁ = (4a + 7)² + 2D.a7 aM
Taking the expectation of eq.
199
conditioned on Fm and following the steps similar those in
step to upper bound E
0 0m-1
0r
F Fm-1,0 1,0
obtain
2
| | 001 Fm-1.0 + (A1
2Dza
E m
0-
F 1,0
4a(1 +
77))
- cC 0m 8- 11 (AA - 4a(1 + 7
2D2a
Σ c
Then, by following the above steps for (m
1) times, we have
E 0m - 0013]
0 0" |?
2D20
< c
ct
2
(AA 4a + 7)2)
k=0
2Dza
< CT
0 0"
(1-C))(>
4c111 7)
which yields the desirable result.
E PROOF OF THEOREM 2 CONVERGENCE OF VRTD WITH MARKOVIAN SAMPLES
We define a (S,) to be the o-field of all samples up to the i-th epoch and recall that Jm, is the index of the sample picked at the t-th iteration in the m-th epoch in Algorithm 2 Then we define set of o-fields the following incremental way:
Fi.0 (So), Fi,1 (F (o(.))) ... FL. oFFi (H.,))
F2.0 = (o(()) U FI Uo(O))), Fn = (F2. (o(i)))),.. Fzm = o(F U (o(j2,))
Fn.D (( 1 F(m-1).M (m((mm))); Fm, (Fmm (J)mm)))) m. Fm.M ((Fm,(M-1) U (im,),
19

---

Published as a conference paper at ICLR 2020
E.1 PROOF OF LEMMA 1
We first prove Lemma Section E.2
1
which is useful for step 4 in the main proof in Theorem 2
provided in
Proof. Recall the definition of the bias term: (n (0 -00) (g,) 200). We have
[0)] Fn,u]
= E (00 8*) T (g.(()) ((0))
nM- -1
nd-
E (0 0*)
Σ
Az. - A)
1
Σ
bz - b)] Fr. Fm.
M
i= (n-1)M
i= 1)M
nM-1 Σ
aM
$
A ABBlIO 11 Fm.o) +
E
As. A) 0 +
Σ
bas - b)
Fno
4
Aa
M
M
i= (22 1)M
i= (n- 1)M
nM -1 Σ
A4
El100
11 Fn,o]]
+
E
Aa, A)
Fn.o
4
Aa
M
1= (12 (
1 n.M
2
bas
Fn.0
A
M
(R-
1)M
AA
1- Fr,o]] +
2R2
E
1
aM-1
Σ
Az. A
Fn,
4
AA
M
(TL
1)M
1
2
E
1
Σ
basa
Fn.0
AA
M
(1
1)M
(
AA
2122 E
nM 1
Bill0 - 1F122Fmn. + Aa
Aa; A
Fn.
M
im (1 13 JM
2 + Aa
nーー1
Das
Fn.o
(20)
M
(=(n-)aa 1)ad
where (i) follows from the fact that || 122 S
|| F for all matrices W Radxd We define the interproduct between two matices W, V R.xdd as (W, V) Eij Eng WiyVi. Consider the second
term in eq. 20 E
- 1)M 1)M Ar. - A
Fu,0 we have
M
T -
E
Ag A
Fn.D
M
i=(n-
1)M
nM-1
Σ
Σ
B((Ar, A, Aa, - A))Fnno)
M
t=
M (=(n- 1)M
1
Σ
E
A1
A12 [F Σ
EE((Ar; A, Ar, A)
M
(*)
20

---

Published as a conference paper at ICLR 2020
11 + ( - EB(AA. - -,,A, F))
M
4(1 M
Σ igj
IB(AA A,A An.l
(21)
M
Now consider upper bound the term B[[AAr; - A, Az,
A) in eq.
21
Without loss of
generality, consider the when > j as follows:
EKA m; A, Az; [
E
B[ - A, Ar₃ - [ Fr.00
E
(B[A2, |z,]
A, A) Frno]]
E
E An [zy]
All || - -Al1 [r,o0]
E
|| A... [mg]
All (1) |1 + -1AAll ) [Fno]
2(1 + 7B
A All [Fno]]
$ 2x(1 + 7
We can further obtain
M-1
Σ (
B[(A.. A. A., AWF s 2xx(++0)
Σ p-llsll 2xx(1+ 72²
Σp p
k=
2p
M-1
4(1 + Mkp
S 2x(1 + 7)
(1 (1-
(22)
p
1 1-p
Then substituting eq.
22
into eq. 21 yields
1
nM-1
4(1 + 7)2 + 4(1 11++7 +1)+ppppp
An
A
Fn.
S M
M
1-p
1-M
F
Then consider the third term in eq.
(20):
E.
1
Σ
M-M
bz. - 1113 Fn,0
similarly we have
M
(n- 1)M
2
MM-
E
1
Σ
bzs
Fn,00
M
Am (n- 1)M
ndd -1
nM-1
Σ
Σ
[[(b,, b)T (br, - Fn.
M
i=
1)M j= (n- 1)A8
Blllbr, 6112 Fn.o] + Σ
El(bbr -b) (bbs bn)]Fnnol
M
$
B((lIbe.ll2
Fu,u] + El(be. - b)" (be, Fn.o
M
(
4r
maxe M +
Σ
El(br. - b)T (bz, - b) Fn
(23)
M
Now to upper-bound the term (b(,,, b)T (bz, Fn,o, without loss of generality, we assume
i > j
Bi(b,, b) [(bbx bn)o
21

---

Published as a conference paper at ICLR 2020
E (bx. b) (bx, - b)[xا]] Fn.
(R Dax [zy] b) (ba, b)) Fr.00
S
| R. [r 8/12 lIbe, 8|12 Fn.o]
be. [
-b112 (11b2, 112 - 1b|12/ ) Fn.o
2r maxl
E [bx |ay]]
6112 Fn.o)
2x 2
maxp"
Thus, we have
M-1 &
Σ 1
Bl(be. - b)" (b2g b)] S 2nr max
Σ
k= 1=1 الااا
< 2nT
max
itj
2p
M
4 max Mxp
$
2kT max
Σ (1-
(1-pp)
(24)
1-p
P
Combing all of the above pieces together yields the following final bound
X1 E|l0 0r 1/ [Fnool+
8(1 + (x 1)pl
E [()(()))Fn.o)
Aa(1- - p)M [R] 7)) + mmax
(25)
E.2 PROOF OF THEOREM
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.
||0m.M 1-11
[RRo (0m.M-1 a (9 (6m,M-1) - 95 (8m-1) + Im (8m-1))) 0r
allgosmm... (0m, M--1) Irim. (0m-1) + Im (mm(0m-1)) 0" |
00..--1
110m,M11 - 101 20000 - TT)T (0uim.e (0m,Ms-)
-rssm. (0m-1) + 9m (0m-1))
a² A0smm.r (mm, 92sm. ar (0m-1) 1) + Im (0m- 1
(26)
First, consider the third term in the right-hand side of eq. 26
92 (0m, 92sm. (0m-1) 1)= + Im (0m (0m-1)
Mesmma (0m,M-1) 92sm. (0") - (gagmer (0m-1) 3m.m.a (0*)) (gm (0m-1) Im (0²)) + Im (00)
$ 9erm (0m,M-1) - Ixsm, i (0r) + +3 (8m-1) - -9 (0*)) (gm (6m-1)
9m (8*)) 1.2
Im
3 I1gm (0')
(27)
Then, by taking the expectation conditioned on F'M(M-1) on both sides of eq. 227 we have
Irsm, (9m,As-1) 9r M (0m-1) + 9m (0 113 Fm.M-1 --1
(1)
M (1 Insm.n (03]13 [ali///m,e Fm,M-1
< 3E
[[ (0m-1)- - Iuimass (0*) [ [[ggssma (6m-1) - Iwim.s (0)) Fm. F Fm.M--
+
3E
22

---

Published as a conference paper at ICLR 2020
l1gm (0')112 Fm.
+ 3E
9 (0m.M-1) - gesmi (00) Fm + 3E |1 0 (0m-1)
g (0r)
$ 3E
F F
(1))
Am ll2 |mm 8- 112
- 3E
|| Am 12110mmns-1- 0- F Pm,M--) + 3E
F Fm.M-
3B
[10m (00m(00)) (0*) [1.0]
(i61)
$ 3(1 7) 110 10. -0 3(1 + 7)2 00-1--000
-00 + 3E 11 (0')12 Fi,0
(28)
where (3) follows from the fact that El(gesm.. (0m-1) 9zsm as (0*)) F M- 9m (0m-
Im (0*), ), (ti) follows from the inequality E EX)
S EX² and (iii) follows from Lemma
We further consider the last term eq. (28)
(
mM-1
m.
E [1mm (0") 1 Fi.0
Σ
A.)00
Σ
M
i= 1)M
1)M
Then, taking the expectation conditioned on F on both sides of eq. (26) yields
E
[10m,ss 1/ Fm..M-1]
110m,M-1- 0-/ + 2ax 20000m -0) [ goim (0m, Iuim, (0m-1) + Im (0m- FmM--)
| (0m,M-1) Dusm, (0m-1) )) + Im 1|² (fmmr-i)
a2E
(
- 110m,ar1 0¹112 [ 22(0m..M1 - TT) 92 (0m. F Mm.M-1) + +3a + 7)² 110 -
3a (1 + +22 |6m-1 - 10122 1ltt0?2 3a²F [11mm [19mm (8") Fi.u]
(1))
10 0-113 + 22x(0m, - -00) g(0mm + 2xF
Sm (9 (0m, 100-))Pmmtt Pm.M-1]
+ +3a + 77) 110m,.1---1111 0-112 + + 30 + 7) ||0 |0m-1 -
0 0r
2
+ 3a
[11mm(0
Fi.0
$ |10m,M-1 - 11 fada - 3a² (1 + 7) 8 m 1- 30 (1 + x)² 10m-1~ -
+ 2aE Sm (0m.M-1) Fm. Mm ] + 3 I1mm (0 (0*) 112 Fi.0
(29)
where
(i) follows by plugging eq.
28 into its preceding step and from the fact that
E ge, (0m-1) (im-1))-m(mmme. (0m-mm)) Fm.M-1 0. In (ii) we define (m)()) = (0 0-) (Igm (0) g
for A IR. Then, by applying eq.
(2 iteratively, we have
E 100, -0 00 [m..]]
M-1
110m,0 0-112 [add 30 7
Σ
E [10m. - 0-112 Fm. 3Maa (1+)) |0m-1 - 0"
1=
M-1
2a
Sm (0m..)
Pmo]]
+3Ma 21 [11mm (1am)(00)11) (00))
(30)
1=0
Arranging the terms in eq.
30) yields
M
lads 31 + 21
E |10m, - 8011/ Fmo
1=0
23

---

Published as a conference paper at ICLR 2020
M
$ [1 + 3M02 +
0m
0r
| + 2x
Em (0m.)) Fm.o] + +3Ma22
|19m (8 )12
F1.0
(31)
Then, substituting eq.
(25) into eq.
31
we obtain
M
- 3a2 7
110m,s - 0-112 Fm.o)
1=0
0m- 0r 2 +
Aa
M-
$ [1 31+ + 7
3Maa
E
[10m. - -00112 |Fm.a]
2
1=
16 + (Ks 1)pla
+
[R] (1 + 7)2 + +r m
+
3Ma
[I (0) F1.0]
(32)
AA(1 p)
Subtracting 0. En1o B[ m. 8 Fm, both sides of eq. (32) yields
0..0AA-33 -3a² +
Σ
E
[10mm
0'11 Fim.0]
1=0
$ [1 + 31 + + |
|0m-1
0+ 001 + 16[1 + (K 1)pla
[n 7)² + r
Aa(1 -ppp))
3MaaE
I1 (0*) F1.0]
(33)
Then, dividing eq.
31 by 10.5aA1-000 - 3a + 7 on both sides, we obtain
@m. 8-
1
2
Fm.0
1/M
(1 7)2
16 + (n (1-)p|1))) R) + 7)
+ r
00-- - 8-
0.5aAs 3a²(1 + 7)2
A - 00.5aa - 3a² + 7
3a
E
[19mm (10)12 Fi.0].
(34)
0.5AA 3a(1 + 7)2
(144)
16 1)01
For simplicity, let C
C2
and C33 =
0.5aA- 1
-30
(++7)3
1-0
0.5A 1324-30(1-3)) Then we rewrite eq.
(34:
E
0m 001 Pm..) [mmo) < Ci
0r
C2
C3B [19m (0') Fi.0
0.5AA
3a
7)2 AM
(35)
Step 2: Iteration over epochs
Taking the expectation of eq. (35) conditioned on Fm-1,0 and upper-bounding E ||lm-- 10133]
by following similar steps in the previous steps, obtained
0m
8-
1 F
Fm-1.0
s C1
10m11
0r
C2
+ CBB
9l (00) Fi.
10.5AA
3a(1 + 2
C2
1
< C²
00-22 - 0r
Σ 0=
C3 Σ
c Il
(0+)
Fi.
10.5AA - -3((1 + 7)
k=0
By following the above steps for (m 1) times, have
@m - 0- 1-1 F1.0
E
24

---

Published as a conference paper at ICLR 2020
8 -8011
00112
+ 1..5A - 3a(1 AM
C2
m-1
E
ct
m C2
B
F1.0]
A=
k=
(36)
Then taking the expectation of (S) (which contains the randomness of the entire sample trajectory) on both sides of eq. (36) yields
l1 0-1 |
2
$ CT
06 - 0122-
+
C₂ 10.5AA 3a(1 + M
m-11
Σ
c
+ C3
m-1
Σ k=0
C
(0
(37)
where the second term in the right hand side of eq. term corresponds to the variance error.
eq.
37
corresponds to the bias error and the third
Step 3: Bounding the variance error For any 0 S k < 1, we have
2
(m k. M -1
11. x00))
1
Σ
9z. (0*)
=
M
im (m k- 1)M
(m--k)M-1
(m-k)-M-
Σ
Ix. (00)
Σ
Fo, (0r)
M
(m
1)M
j=(m-k-1)M
(m-
RYM-1
(m- (o-k))--
1
Σ
Σ
In. (0" (0))), (0*)
M2
1)M
1m--k-1 1)ar
19
(0")
In. (8") (0')),, (0*)
M
M bf
G2
M
1
92, (0 (00)), (0))
(38)
M
M
where (i) follows from Lemma given by
3
Consider the expectation of the second term in eq.
38 which is
ElgJ, (0")g., (0)))-
(39)
M i
Without loss of generality, we consider the case when j > as follows:
Big.T, (0" )9r, (0*) [[E[g,, (0)) 9x. (0*)
< [[ [P:] l1 (0*)lla)
(0')
GE(|E[[AA, P
S ([][II|AA/PP]0+++,],,
(E[A)]] A))0 [E]b b)
CB[[[[[[[A|3]]- 1 ||b, P.] b11]]
< CB[[IB[AA|P]] - AAl1 10 + [|B b11
xG((1 + Ro |mmax]
(40)
Substituting eq.
40
into eq.
39
obtain
E lg )0)g (0)) sG((1 + Ro + Tinxx]
M
M²
(
25

---

Published as a conference paper at ICLR 2020
14
KGI(L + R) + Tmax
(2M
pl)
M
2pxC|(1 + R. Rg + Tmax
(41)
(1- p)M
Then substituting eq.
41 into eq.
38 yields
( 2pxG[(1 + R) + Tmax
C4
E (1l9mmx((0"11)) (0))
(42)
(1 1 -p)
M
where Cs = G² + 2px Re Finally, substituting eq. 42) p)
into the accumulated residual
variance term in eq.
37 have
C3C4
1h
C2Cs
C3
C 110m x (00)) S
Σ C
(43)
M
C.)M
0=
k=0
Step 4: Combining all error terms
Finally, substituting eq.
(43 and substituting the values of C2 and C3 into eq. 37 we have
E
0m 0r [ CTT
0
0+ 1 + (1-C))0.5d4 3a(1 M
3Caa C2/AA
which yields the desired result.
F SAMPLE COMPLEXITY OF TD
The finite-time convergence rate of vanilla under i.i.d. and Markovian sampling has been characterized in Bhandari al. 2018); Srikant and Ying (2019). However, these studies did not provide the overall computational complexity, i.c., the total number of pscudo-gradient computations achieve e-accuracy solution. This section provides such analysis based their convergence results for completeness.
F.1 TD WITH I.I.D. SAMPLES
Consider the vanilla TD update Bhandari et 2018). Following the steps similar those in Bhan- dari al. (2018) for proving Theorem and letting the constant stepsize min x1+T)= Xa
we have
2CBa
E
00
0r
Aaax) 1100 00 +
2
Aa
2Csa
Se Auatt
1100 -8-11
Aa
where 0 < C < 0o is constant. Let = min with the total number of iterations at most
4[1+g]2
d1
Ne ic,
2
}. It can be checked easily that
2 t = AAa
2
1'1 = [2 max f
4(1 + 7)2
4C
log( 2 1|66
0" 1113
log(
1,
x2
ex3
=o
log
(44)
e-accurate solution can be attained, i.e., E 100 8- 11 < secudo-gradiem computation, the total number of
Since each iteration requires one computations is also given by
eq. (44)
26

---

Coa CTa Published as a conference paper at ICLR 2020
F.2 TD WITH MARKOVIAN SAMPLES
Consider the vanilla TD update in Bhandari et al. (2018). Following the steps similar to those in have
Bhandari et al. (2018) for proving Theorem and letting the constant stepsize
0| 0- (1 AAa)² 100 100-0-1 +
A
AA
Assat 110b 1 Coa Cra
AA
A
where 0 Co < oo and < C oo are constants. Now let a = min Tog(1/Cse]]
Cae
x where
Cs AA Aimin aट, J. can be checked easily that with the total number iterations
log( 3 110 10
1
100
1
|max
2 log
log
min
{ Ch oC, Mage
CBe
o log" (
(45)
an c-acourate solution can be attained, i.e., 1|0 8- S c. Since each iteration requires one geeuo-graddent computation, the total number of pseudo -raddien computations is also given by
eq. (45)
27


Reviews:
[{"review_id": "ryl2mm7I9r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is on temporal difference learning, specifically variance reduction of it. As per the claims of the paper, a previous method from (Korda and La, 2015) had technical errors, which the paper corrects and provides a better analysis of variance reduction. In the end, the paper focuses on the variance of the gradient estimator in temporal difference learning, and on analysis of the bias error. The final method is validated on two experiments with iid and Markovian sampling.\n\nStrengths:\n\n+ The paper seems to conduct some serious analysis of the variance in temporal difference learning. The discussed analysis is substantial and the derivations seem to check out.\n\nWeaknesses:\n\n+ I believe the paper could improve its clarity for someone who is not an expert on reinforcement learning. In the current version I find it a bit hard to understand the direction the paper takes.\n\n+ The experiments are quite thin and also vague. It is unclear what exactly is the experimental setup, how were the data generated and what are fair baselines. In fact, not even competitor methods or the method of (Korda and La, 2015) are included in the comparisons. As such, it is not possible to understand whether the proposed method is really contributing something or not. What would be the results in standard RL environments, like from the OpenAI gym or the MuJoCo environments?\n\nI apologize for my rather short review. Unfortunately, I find it hard to write something more without going very deep on the derivations, which I could not give shortage of time. I believe the paper is of value and I am willing to upgrade my score upon a more persuasive experimentation.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rke_FDh39r", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes a TD algorithm with batch estimation of the TD step with the purpose of variance reduction in both the iid and Markov noise setups. This work is brought as reanalysis of the centered TD algorithm from Korda and La (2015), which is known to contain several errors in its analysis and statements.\n\nThe contributions are in the form of two respective finite-time bounds for the iid and Markov noise, that exhibit improvement over vanilla TD by a factor of O(1/M) for the variance and O(1/\\sqrt{M}) for the bias, at the expense of M inner iterations instead of 1. Even though it is usually challenging to convey this type of analysis in a short manuscript, this work makes it accessible and is well written. The counterexample to existing errors in previous proofs is compelling, and the preceding discussion regarding the proofs prior to each theorem make it easy to immediately catch the gist of the proofs without having to go through the appendix.\n\nDespite the advantages above, I am disturbed by the lack of comparison of the computational burden introduced by the M inner loops to vanilla TD. It is not clear from the results whether a practitioner would prefer paying those extra computations to reduce the bias and variance by the M-dependent factors in the convergence rate. Second, the novelty of this work is not highly significant. It indeed corrects a bound for an existing algorithm, but not more than that. Namely, it only analyzes the so-called VRTD with a specific stepsize O(1/n), which also contains a system-dependent parameter that is not known to the user -- the smallest eigenvalue of the driving matrix. \n\nWhile I don't believe the authors can do much to mitigate the second of the two qualms above, I am open to upgrade my score if they can provide a compelling answer to the first, and answer the questions bellow.\n\nThe following comments/questions are in order:\n1. In several locations the TD update is referred to as a gradient. Despite the explanation as of why in Footnote 1, this is misleading. Since it is known that the TD update is *not* a true gradient step, it would be wiser not to refer to it as one.\n2. Can't Algorithm 1 be easily improved to be more efficient? In step 7 you perform M updates but end up throwing away M-t of them, where t is drawn randomly (step 10). Instead, you can simply draw t at the beginning and compute step 7 only up to that t. Is that correct?\n3. Theorem 1: mention what exactly is the M you refer to -- that might expose more interesting relations.\n4. Paragraph above 4.2: \"... then the error term becomes zero, and Algorithm 1 converges linearly to the fixed point solution ...\". Which error rate becomes zero? be more specific please. Also, you never pointed out with respect to which parameter the rate is linear. Is it always \\alpha?\n5.  Paragraph above 4.2, last two sentences: the text seems to be messed up there, please fix.\n6. Lemma 1: can you specify what exactly is C_0 or how can we estimate/bound it given some MDP? It is a caveat in your main and final result.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJghCzooFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nIn this paper, the authors study the variance reduced TD (VRTD) algorithm, by Korda and Prashanth (2015)  (KP15), for policy evaluation in RL. They first highlight technical errors in the analysis of KP15, and then provide new convergence analysis for this algorithm. The new analysis is based on a new technique to bound the bias of the VRTD gradient estimator, and shows the advantage of VRTD over vanilla TD (the analyses by Bhandari et al. 2018 and Srikant and Ying 2019), both in terms of variance and bias, that are reduced by increasing the batch size. The authors show that while the variance and bias of vanilla TD are both of O(\\alpha) (where \\alpha is the step-size), they are of O(\\alpha/M) and O(1/\\sqrt{M}) (where M is the batch size) in VRTD. This shows that a good convergence is possible for VRTD without reducing the step-size \\alpha, that causes slow convergence, by increasing the batch size M. In the middle of their analysis, the authors propose a slight modification of VRTD for the case that the samples are obtained iid from the stationary distribution of the evaluating policy, and provide its analysis. Finally, the authors provide simple experiments to support their theoretical findings.  \n\nComments: \n- More discussion on the parameter C_0, a constant between 0 and \\infty that depends on the MDP, is necessary in the paper. The authors provide no discussion about this constant and only in the appendix, refer the readers to Dedecker and Gouezel (2015). This constant is important because if it is large, then the batch size M should be very big in order for the bias error to go to zero. It would be good to see that which MDP properties affect the value of C_0. \n- As we increase M, the final performance gets better, but the (sample) cost of each gradient update increases. It would be good to have a comparison between different M values, in terms of performance vs. number of samples. What I mean is to have figures similar to 1(a) and 1(b) in which the performance is on the y-axis and the number of samples on the x-axis. \n- I was wondering if we can get the same improvement in terms of performance by having a decreasing schedule for \\alpha. What I mean is instead of increasing M, we keep M constant and then define a decreasing schedule for \\alpha and prove similar bounds that go to zero as \\alpha goes to zero. \n\nMinor Comments:\n- The projection \\Pi_{R_\\theta} in Algorithm 2 has not been explained. This is important as R_\\theta appears in some of the theoretical results later in the paper. \n- \\lambda_A  has been used on Page 5 without definition. The authors define this quantity later on Page 6. \n- What is \\Psi in the discussions at the bottom of Page 5 (Eqs. 2, 3, and 4). Is it \\Phi? Overall, I think this discussion would be more meaningful if the authors first introduce the terms used in Eqs. 2 and 3.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "r1xTu9l6cB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nSpecifically, 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.\n\nMain points:\n\n1) 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 $m$ (and not M). This would imply a stronger result than what authors have currently. \n\nNote 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 \\textit{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 \\textit{get rid} of the constant variance error term when analyzing TD(0) with constant step-sizes. Can the authors clarify?\n\nAlso, 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).\n\n2) As a practical proposal, I wonder if VRTD has a potential benefit over vanilla TD(0). Essentially, the rates showed in this paper require $O(mM)$ samples. I wonder how vanilla TD would perform with $O(mM)$ 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).\n\nMinor points:\n- 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. \n- $R_{\\theta}$ and $r_{max}$ seem undefined in the main body of the paper. \n- The constants in Theorem 1 and 2 seem complicated. Is there a way to simplify these for presentation purposes?\n\nResponse to author comments.\n\nI thank the authors for their comments and changes to the draft.\n\n1) 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\n\n2) 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. \n\nAlthough I am not sure how likely practitioners are to use this (both $\\alpha$ 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.\n\nSome minor comments and suggestions:\n\n1) In Theorem 1, constant D_2 depends on $R_{\\theta}$ but there Algorithm 1 has no projection step. I think the authors assume that $\\norm{\\theta^*} \\leq R_{\\theta}$. If so, please state that somewhere. If not, maybe I missed something and would like a clarification. \n\n2) Page 6 should have $e(\\tilde{theta}_m-1)$ instead of $e(\\tilde{theta}_m)$.\n\n3) Before stating the main results in Section 4, please restate the definition of $\\lambda_A$ for better readability. \n\n4) Constant G seems to be undefined for Theorem 2. In fact, it seems that $C_4 = G^2 [1 + \\frac{2\\rho \\kappa}{1-\\rho}]$. This is what I meant by simplifying constants. Ensuring that these constants are optimized for presentation helps.\n\n5) Theorem 2 has a dependence on $d$. Maybe the authors should explicitly mention and discuss that. \n\n6) 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. \n\n7) Equation 5 should have ’m’ instead of ’n’.\n\n8) 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. \n\n9) Section A in the Appendix might benefit from more background. For example, what is $v$. 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).\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklAWLvF9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides theoretical guarantees for variance reduced temporal difference algorithms. It points out an analysis error in a previous paper and gives the correct proof. The analyses are based on two sampling schemes, i.i.d. and Markovian.  Convergence guarantees and convergence rates are provided for both sampling schemes. \n\nThe paper is well written. The main theoretical results are presented clearly. The convergence rates are reasonable to me. Considering the importance of TD, I think this analysis will provide some insights for future directions of TD. \n\nI have several questions and concerns. \n1. The data is simulated. I am wondering how VRTD works in practice comparing to naive TD. \n2. The number of gradient evaluations is used in x-axis in the experimental results. What if it's replaced by wall-clock time?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the variance reduced TD algorithm by Konda and Prashanth (2015). The original paper provided a convergence analysis that had some technical issues. This paper provides a new convergence analysis, and shows the advantage of VRTD to vanilla TD in terms of reducing the bias and variance. Several of the five reviewers are expert in this area and all of them are positive about it. Therefore, I recommend acceptance of this work.
Decision: Accept (Poster)