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 , 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 , 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. 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;;. The temporal difference (TD) learning algorithm, originally proposed by , 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;. The finite sample analysis of TD has also been studied in;; Dalal et al. (2018a);. Since each iteration of TD uses one or a mini-batch of samples to estimate the mean of the gradient 1, 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;; Dalal et al. (2018a), 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. 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, showed that and can be applied to improve the performance of batch TD algorithms, and 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 , 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 , VRTD has outer and inner loops. The beginning of each inner-loop (i.e. each epoch) computes a batch of sample gradients so that each subsequent inner loop iteration modifies only one sample gradient in the batch gradient 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. empirically verified that VRTD has better convergence accuracy than vanilla TD learning, some technical errors in the analysis in have been pointed out in follow up studies Dalal et al. (2018a); Narayanan and Szepesvári. Furthermore, as we discuss in Section 3, the technical proof in regarding the convergence of VRTD also has technical errors so that their 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;; Dalal et al. (2018a), 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 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 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; 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? 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. This clearly reduces the corresponding variance error O(α) of vanilla TD in. For Markovian sampling, we show that VRTD has the same linear convergence and the same variance error reduction over the vanilla; 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; , where the bias error is at the order of O(α). Therefore, vanilla TD typically needs to decrease the stepsize α in order to reduce the variance and bias errors, which however slows down the convergence. In contrast, VRTD can increase the batch size to reduce both errors while still keeping the stepsize at a desired constant level to maintain fast convergence, as can be observed in our experiments. At the technical level, our analysis of bias error for Markovian sampling takes a different path from the techniques used in;;. Due to the batch average of stochastic gradients adopted by VRTD to reduce the variance, we apply a concentration bound established in Dedecker and Gouëzel for Markovian samples. This shows that the correlation among samples in different epochs is eliminated due to the concentration to a deterministic average, and the correlation among samples within each epoch is implicitly captured by the parameters in the concentration inequality. Such an analysis also explicitly explains why the variance reduction step can also reduce the bias error. On-policy TD learning and variance reduction. On-policy TD learning aims to minimize the Mean Squared Bellman Error (MSBE) 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. The convergence of averaged linear SA with constant stepsize has been studied in. In the Markovian setting, the non-asymptotic convergence has been studied for on-policy TD in;;;. 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 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. algorithms are generally designed for policy evaluation by solving an optimization problem on a fixed dataset. , the empirical MSPBE is first transformed into a quadratic convex-concave saddle-point optimization problem and variance reduction methods of and were then incorporated into a primal-dual batch gradient method. applied two variants of variance reduction methods to solve the same saddle point problems, and showed that those two methods can save 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ć; , off-policy TD learning Sutton et al. (2008; 2009);;; , two time-scale TD algorithms Dalal et al. (2018b); , fitted TD algorithms , etc. The idea of the variance reduction algorithm proposed in as well as the analysis techniques that we develop in this paper can potentially be useful for these algorithms. We describe the problem of value function evaluation over a Markov decision process (MDP) (S, A, P, r, γ), where each component is explained in the sequel. Suppose S ⊂ R d is a compact state space, and A is a finite action set. Consider a stationary policy π, which maps a state s ∈ S to the actions in A via a probability distribution π(·|s). 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 with φ i (s) for i = 1, 2, · · · 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 asv(θ) = Φθ. Our goal is to find the fixed-point parameter θ The TD learning algorithm performs the following fixed-point iterative update to find such θ *. 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), and A 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 gradient g(θ) = Aθ + b where We call g(θ) as gradient for convenience due to its analogous role as in the gradient descent algorithm. It has been shown that the iteration in eq. 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; Dalal et al. (2018a);. Throughout the paper, we make the following standard assumptions;;;;. Assumption 1 (Problem solvability). The matrix A is non-singular. Assumption 3 (Geometric ergodicity). The considered MDP is irreducible and aperiodic, and there exist constants κ > 0 and ρ ∈ such that 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. Assumption 3 holds for any time-homogeneous Markov chain with finite state-space and any uniformly ergodic Markov chains with general state space. In this section, we first introduce the variance-reduced TD (VRTD) algorithm proposed in for Markovian sampling and then discuss the technical errors in the analysis of VRTD in. 3.1 Since the standard TD learning takes only one sample in each update as can be seen in eq., it typically suffers from a large variance. This motivates the development of the VRTD algorithm in (named as CTD in). 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 gradient g m (θ m−1) is computed based on these samples as an estimator of the mean gradient. Then, each inner-loop update randomly takes 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 for conventional optimization. Since a batch gradient is used at each inner-loop update, the variance of the gradient is expected to be reduced. Input: batch size M, learning rate α and initializatioñ θ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: Sample xj m,t indepedently from the distribution µπ 7: θm,t+1 = θm,t + α gx j m,t (θm,t) −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 Input: batch size M, learning rate α and initializatioñ θ0 1: for m = 1, 2,..., S do 2: θm,0 =θm−1 3: 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) −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 3.2 In this subsection, we point out the technical errors in the analysis of VRTD in , which thus fails to provide the correct variance reduction performance for VRTD. At the high level, the batch 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) gradient g(θ m−1). Furthermore, due to the correlation among samples, the gradient estimator in expectation (with regard to the randomness of the sample trajectory) does not equal to the mean gradient, which should further cause a non-vanishing bias error in the convergence bound. Unfortunately, the convergence bound in 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 in Theorem 3 in does not agree with that of vanilla TD characterized in the recent studies; , which has variance and bias errors. In Appendix A, we further provide a counter-example to show that one major technical step for characterizing the convergence bound in does not hold. The goal of this paper is to provide a rigorous analysis of VRTD to characterize its variance reduction performance. As aforementioned, the convergence of VRTD consists of two types of errors: the variance error due to inexact estimation of the mean 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. to demonstrate its advantage. 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 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 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 gradient cannot estimate the mean 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 gradient estimation error, our analysis (see Appendix C) shows that after each epoch update, we have 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. captures the contraction property of Algorithm 1 and the second term corresponds to the variance of the 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. 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 M > where (1+γ) 2 (with C 1 < 1 due to the choices of α and M), and We note that the convergence rate in eq. can be written in a simpler form as 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 of the vanilla TD, which suffers from the constant error term with order O(α) 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 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. However, the proof here is very different. , 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. 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 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 ). Then our analysis (see Appendix D) shows that after each epoch update, we have The first term on the right-hand side of eq. captures the epochwise contraction property of Algorithm 2. The second term is due to the variance of the gradient estimation, which captures how well the batch gradient g m (θ *) approximates the mean 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 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. In Lemma 1, the constant C 0 depends proportionally on the coupling time and the returning time of the underlying Markov chain. Specifically, the coupling time indicates how fast the Markov chain converges to the stationary distribution, and the returning time, which depends on the nature of the stationary distribution, captures the expected time that the Markov chain returns to the same state. Although it is in general difficult to obtain an explicit form for C 0, the value of C 0 is typically small if the Markov chain has a small mixing time and the stationary distribution is less degenerate. 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: The first term on the right-hand-side of eq. can be bounded by the concentration property for the ergodic process as g m (θ) = → g(θ). As M increases, the randomness due to the 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 E[ξ n (θ)] = O(α log(1/α));. 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 where 0.5αλ A −3α 2 (1+γ) 2 (with C 1 < 1 due to the choices for α and M),. We note that the convergence rate in eq. can be written in a simpler form as 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. captures the linear convergence of the algorithm, the second term corresponds to the sum of the cumulative gradient 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 gradient estimator. In this section, we provide numerical to verify our theoretical . We consider an MDP with γ = 0.95 and |S| = 50. Each transition probability are randomly sampled from and the transitions were normalized to one. The expected reward for each transition is also generated randomly in 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 are reported in Figure 1. 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 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. 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 gradient estimator. Our 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. Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W.. OpenAI Gym. In this section, we use a counter-example to show that one major technical step for characterizing the convergence bound in does not hold. Consider Step 4 in the proof of Theorem 3 in. For the following defined (θ) where Ψ denotes the stationary distribution of the corresponding Markov chain, claimed that the following inequality holds 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. and eq. are scalars. Since the steps for proving eq. in do not have specific requirements for the transition kernel, eq. 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: Substituting the above values into eq. yields which obviously does not hold in general when θ = θ *. Consequently the second statement in Theorem 3 of , 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. 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 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, Proof. First, we bound g xj m,t (θ m,t) 2 as follows. Following the steps similar to the above, we have g xj m,t (θ m−1) 2 ≤ G. Finally for where eq. follows from the last fact g xj m,t (θ m−1) 2 ≤ G. Proof. Recalling the definition of g xi, and applying Lemma 2, we have Lemma 5. Considering Algorithm 2 with Markovian samples. We have Proof. We first derive Following the steps similar to the above, we can derive 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. 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. First, consider the third term in the right-hand side of eq., we have Then, by taking the expectation conditioned on F m,M −1 on both sides of eq., we have where (i) follows from the fact that and (ii) follows from the inequality E[(X − EX) 2 ] ≤ EX 2 and Lemma 2. Then, taking the For all 1 ≤ i ≤ M, we have Then, arranging terms in eq. and using the above fact yield Finally, dividing eq. by [αλ A − 4α 2 (1 + γ) 2 ]M on both sides yields Step 2: Bounding the variance error where eq. follows from Lemma 4. Step 3: Iteration over m epoches First, we substitute eq. into eq. to obtain where we define Taking the expectation of eq. 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 Then, by following the above steps for (m − 1) times, we have which yields the desirable . We define σ(S) to be the σ-field of all sample trajectories {x 1, x 2, ...} 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: We first prove Lemma 1, which is useful for step 4 in the main proof in Theorem 2 provided in Section D.2. Proof. Recall the definition of the bias term: where and To bound eq. and eq., we apply the concentration inequality over Markov chains developed in Dedecker and Gouëzel. We first introduce such a concentration bound as follows. Theorem 3 (Dedecker and Gouëzel, Theorem 2). Let {X n} be an irreducible aperiodic Markov chain which is geometrically ergodic on a space S. Let π be its stationary distribution. There exists a constant C 0 depending on the Markov chain (see the detailed definition of C 0 in Dedecker and Gouëzel) with the following property. Let n ∈ N. Let K(x 0, · · ·, x n−1) be a function of n variables on S n. Then for all t > 0, where µ is the stationary distribution of the Markov chain and 0 ≤ L i < +∞ is a constant that satisfies: Since the MDP in Algorithm 2 satisfies Assumption 3, it satisfies the assumptions in Theorem 3. Then applying Theorem 3 to each W n,(i,j) and V n,i, we have and where 0 < C 0 < ∞ is a constant depending on the MDP parameters. Then, substituting eq. into eq. and eq. into eq. yield and Then we derive the following two bounds: and Finally, substituting eq. and eq. into eq. yields D.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. First, consider the third term in the right-hand side of eq.. Then, by taking the expectation conditioned on F m,(M −1) on both sides of eq., we have where (i) follows from the fact that, and (iii) follows from Lemma 2. We further consider the last term in eq.: Then, taking the expectation conditioned on F m,M −1 on both sides of eq. yields where (i) follows by plugging eq. into its preceding step and from the fact that for θ ∈ R d. Then, by applying eq. iteratively, we have Arranging the terms in eq. yields Then, substituting eq. into eq., we obtain Subtracting 0.5λ 2 |F m,0 ] on both sides of eq. yields Then, dividing eq. by [0.5αλ A − 3α 2 (1 + γ) 2 ]M on both sides, we obtain For simplicity, let 0.5λ A −3α(1+γ) 2. Then we rewrite eq.: Step 2 by following similar steps in the previous steps, we obtained By following the above steps for (m − 1) times, we have Then taking the expectation of σ(S) (which contains the randomness of the entire sample trajectory) on both sides of eq. yields where the second term in the right hand side of eq. corresponds to the bias error and the third term corresponds to the variance error. Without loss of generality, we consider the case when j > i as follows: computations required by VRTD (i.e., Algorithm 1) under i.i.d. sampling to attain such an -accuracy solution is at most Proof. Given the values of α and M in the theorem, it can be easily checked that E||θ m − θ * || 2 ≤ for m = log. Then the total number of 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 Proof. Given the values of α and M in the theorem, it can be easily checked that E||θ m − θ * || 2 ≤ for m = log. Then the total number of 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 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. The finite-time convergence rate of vanilla TD under i.i.d. and Markovian sampling has been characterized in;. However, these studies did not provide the overall computational complexity, i.e., the total number of gradient computations to achieve an -accuracy solution. This section provides such an analysis based on their convergence for completeness. only when it reaches the goal and 0 otherwise. Each transition probability is randomly sampled from and normalized to one, and each component of the feature matrix Φ ∈ R 16×4 is also randomly sampled from. Given the feature matrix and the transition probability, the ground truth value of θ * can be calculated, which is used to evaluate the error in the experiments. We set the stepsize to be α = 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 2 shows the convergence process over the number of gradient computations and the right plot in Figure 2 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. Mountain Car is a game in OpenAI Gym, which is driven by an MDP with an infinite state space and a finite action space. At each time step, an agent randomly chooses an action ∈ {push left, push right, no push}. In this problem, the ground truth value of θ * is not known. In order to quantify the performance of VRTD, we apply the error metric known as the norm of the expected TD update given by NEU= E[δφ] 2 2, where δ is the temporal difference;. The state sample is transformed into a 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 = 0. At t = 0, the agent starts from the lowest point, receives a reward of −1 at each time step, and returns to the starting point every time it 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 gradient computations, learning is paused and the NEU is computed by averaging over 1000 test samples. We conduct 1000 independent runs and the are reported by averaging over these runs. Figure 3 shows the convergence process of the NEU versus the number of gradient computations. It can been seen that VRTD achieves smaller NEU than vanilla TD. Upon the request of one reviewer, 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 G.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 4, 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 gradient computations (equivalently, the total number of samples being used). It can be seen that VRTD reaches the required accuracy much faster than TD.
This paper provides a rigorous study of the variance reduced TD learning and characterizes its advantage over vanilla TD learning