Temporal difference (TD) learning is a popular algorithm for policy evaluation in reinforcement learning, but the vanilla TD can substantially suffer from the inherent optimization variance. A variance reduced TD (VRTD) algorithm was proposed by Korda and La (2015), which applies the variance reduction technique directly to the online TD learning with Markovian samples. In this work, we first point out the technical errors in the analysis of VRTD in Korda and La (2015), and then provide a mathematically solid analysis of the non-asymptotic convergence of VRTD and its variance reduction performance. We show that VRTD is guaranteed to converge to a neighborhood of the fixed-point solution of TD at a linear convergence rate. Furthermore, the variance error (for both i.i.d. and Markovian sampling) and the bias error (for Markovian sampling) of VRTD are significantly reduced by the batch size of variance reduction in comparison to those of vanilla TD.
This paper presents a non-asymptotic analysis of Variance Reduced TD (VRTD), proposed by Korda and La (2015), to apply variance reduction ideas to temporal difference learning, specifically TD(0) with linear function approximation. The algorithm closely follows ideas of stochastic variance reduction (SVRG) which is widely used for large scale empirical risk minimization.
Specifically, the authors show VRTD converges (in expectation) to a neighborhood of the limit point using a constant step-size. Interestingly, this neighborhood can be made small using a large batch size M in both the IID and Markovian sampling regimes. From a technical standpoint, the work seems novel with interesting results although I am not sure if VRTD offers practical performance gains.
Main points:
1) I am a bit confused by the presence of a constant variance error term in the results. Intuitively, with variance reduction, I was expecting convergence in expectation; not just to a neighborhood with constant error. In other words, the variance error term decaying with $m$ (and not M). This would imply a stronger result than what authors have currently. 
Note that vanilla SGD for strongly convex objectives also suffers from a constant variance error term (see for example Chapter 4 in Bottou et al., 2018). However, analysis of SVRG (Johnson and Zhang 2013) shows linear convergence for strongly convex objectives and claims sublinear convergence for convex objectives. While I appreciate the technical challenge in analyzing a \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?
Also, the authors might find it useful to look at (Lakshminarayanan and Szepesvari, 2018) which does in fact show convergence with a constant (problem instance independent) step-size for the IID case. I think that result only applies with iterate averaging but it might still be useful (certainly as a citation suggestion).
2) As a practical proposal, I wonder if VRTD has a potential benefit over vanilla TD(0). Essentially, the rates showed in this paper require $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).
Minor points:
- The counter example in Section 3.2 seems out of place. While it is important to point out the errors in previous analysis, I suggest the authors to flesh out the details in an Appendix section. 
- $R_{\theta}$ and $r_{max}$ seem undefined in the main body of the paper. 
- The constants in Theorem 1 and 2 seem complicated. Is there a way to simplify these for presentation purposes?
Response to author comments.
I thank the authors for their comments and changes to the draft.
1) The explanation makes a lot of sense. Since we cannot exactly estimate the population gradient, the variance error seems unavoidable with constant stepsize. I like the clarifications in Section 3.2
2) Thanks for clarifying that all the comparisons are done in terms of a fixed number of total gradient computations. Please add this clearly in the paper as well. I think the additional experiments and comparison with the new scheme I suggested above does a good job of convincing the readers of the practical usefulness of variance reduction. 
Although I am not sure how likely practitioners are to use this (both $\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.
Some minor comments and suggestions:
1) 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. 
2) Page 6 should have $e(\tilde{theta}_m-1)$ instead of $e(\tilde{theta}_m)$.
3) Before stating the main results in Section 4, please restate the definition of $\lambda_A$ for better readability. 
4) 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.
5) Theorem 2 has a dependence on $d$. Maybe the authors should explicitly mention and discuss that. 
6) The result for Markovian case requires the bias term to not dominate. This seems novel to me and would benefit from emphasis in the main body of the paper. 
7) Equation 5 should have ’m’ instead of ’n’.
8) I always find large figures and clear (and) large axis labels very useful. Can the ‘iteration process’ graphs in Figure 1 be made more reader friendly? I’d  like to see the behavior of vanilla TD more clearly. 
9) Section A in the Appendix might benefit from more background. For example, what is $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).