Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper combines a widely used variance reduction technique SVRG with the greedy-GQ. It provides a finite-time analysis of the proposed algorithm  in the off-policy and Markovian sampling setting (convergence to the stationary point) and improves the sample complexity from the order $\epsilon^{-3}$ to $\epsilon^{-2}$ comparing with the vanilla greedy GQ. Interestingly, the analysis shows that the biase error caused by the Markovian sampling and the variance error of the stochastic gradient are reduced by the $M$, where M is the batch size of the batch gradient in SVRG. At last, it verifies the theoretical claim by two toy examples.

pros:
1. It combines the variance reduction trick in optimization community with the two time scale analysis in RL.
2. The analysis is on the off-policy control setting, which in general is much harder than the off-policy evaluation setting.
3. The objective function of MSPBE in control setting is non-convex, which increases the difficulty of the proof.


cons:
1. The main contribution of this paper is its theoretical analysis. However the techniques in the proof have already existed in many literatures. It seems that the author just combines them together. For instance, there are many literatures on the convergence analysis of the SVRG in the non-convex setting.  The author claims that the 'fine-tuned' Lyapunov function is novel. However such tools in the non-convex SVRG are widely used. It may be true that we need to chose the c_t carefully to cancel some error term but  the main framework of the proof is the same.

2. I am not sure whether the variance reduction technique is useful in practice. There are some evidences that SVRG does not work well in the training of deep learning problem.  Would faster convergence to the stationary points lead to the better performance (e.g. higher reward )? I do not see anything related to that in the experiment. 

3. The author just tests their algorithm on two toy examples. I hope to see more complicated experiments. Maybe the author can try the neural network in the function approximation beyond the linear function approximation.  I know the analysis is just on the linear case, but this experiment would demonstrate the potential applicability of the algorithm.


################after rebuttal

After reading the responds from the author, I keep my score at 5.

review_title: Review

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: EDIT: After reading the other reviews, responses, and thinking more about the issues raised and resolved, I'm increasing my score to an 8.

---

### Summary:
The paper introduces a variance-reduced version of the Greedy-GQ algorithm for off-policy control, based on SVRG. The paper then analyzes the finite-time convergence rate of the proposed method (VR-Greedy-GQ) under the assumption of Markovian noise and finds an improvement on the order of 1/epsilon to achieve an epsilon-stationary point. The theoretical findings are supported by some experiments.

### Pros:
- Proposed improvement to existing method
- Theoretical support for proposed improvement
- Markovian noise assumption
- Some new techniques in the theoretical analysis
- Well written

### Cons:
- SVRG setup involving inner and outer loop conflicts with the original motivation for Greedy-GQ (online and incremental latent learning)

#### Clarity/Quality:
The paper is well written and not too difficult to follow despite the complicated topics. Sections 4 (Finite-time analysis of VR-Greedy-GQ) and 5 (sketch of the technical proof) were especially well-written and helpful, and the experiments seemed reasonable.

#### Originality:
The paper seems fairly incremental in terms of the proposed method, applying an existing method for variance reduction to an existing algorithm. However, some of the technical tools used in the analysis of the resulting VR-Greedy-GQ algorithm are original to the best of my knowledge.

### Decision:
Despite some concerns listed below, I recommend accepting the paper for publication.

Why use SVRG to reduce variance? The nested loop structure seems at odds with the single Markovian path of experience, and conflicts with the original motivation for Greedy-GQ ("Online, incremental, with memory and per-time-step computation costs that are linear in the number of features" ). If we're giving up online and incremental algorithms, why not use an LSTD-based method like LSPI (Lagoudakis & Parr, 2003) instead?

Why require smooth policies when the original Greedy-GQ paper doesn’t? Is it just for convenience? Would the analysis still apply for a non-smooth policy like the greedy policy?

### Suggestions for improvement:
- In the related work section, it could be helpful to explicitly write how the related work is different from the current work.

### Miscellaneous comments:
- Spelling error in third paragraph of section 1.1: “new tecnical developments”
- In section 2.2 the paper states that “[Greedy-GQ] aims to minimize the Bellman error”, but my understanding is that Greedy-GQ was designed explicitly for the function approximation setting where minimizing MSBE and MSPBE are different. It would be better to write “and in the tabular setting it aims to minimize the Bellman error”.
- Corollary 4.2 sets $\eta_\theta$ twice. Is the second $\eta_\theta$ supposed to be $\eta_\omega$?

### References:
- Wang, Y., & Zou, S. (2020). Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise. arXiv preprint arXiv:2005.10175.
- Maei, H. R., Szepesvári, C., Bhatnagar, S., & Sutton, R. S. (2010, January). Toward off-policy learning control with function approximation. In ICML.
- Lagoudakis, M. G., & Parr, R. (2003). Least-squares policy iteration. Journal of machine learning research, 4(Dec), 1107-1149.
review_title: Interesting paper that addresses variance issues with Greedy-GQ

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a variance reduced Greedy-GQ algorithm and proves that it enjoys a lower convergence rate compared with vanilla Greedy-GQ. The paper is well written and clearly presented. The sample complexity of the proposed algorithm is lower than Greedy-GD by a factor of 1/eps, which could be a great improvement when the target precision eps is small. 

In the related work part, the nonasymptotic convergence of Q-learning with function approximation has also been extended to neural network function approximation (A finite-time analysis of q-learning with neural network function approximation. In ICML 2020).

In the algorithm, what specific policy improvement is used? Does the choice affect the proof of the convergence?

One drawback of the result in Theorem 4.5 is that the convergence is only guaranteed for the minimal gradient norm over the whole trajectory. However, in Algorithm 1, the output is defined as the last iterate. In other words, the convergence rate in Theorem 4.5 is not for the proposed algorithm. In this sense, the convergence results may not be as useful as other algorithms that can guarantee the convergence of the last iterate of the average iterate.

In terms of the experiments, it would be nice if the cumulative reward versus running time can be shown, which demonstrates the performance in a clearer way. It would also be interesting to see whether the proposed variance reduced Greedy-GQ method can match the performance of off-policy policy gradient (or actor-critic) methods and variance reduced policy gradient methods in controlling problems.

#########Edits after the rebuttal#########

I have read the response and other reviewers' review/discussion. I will keep a score as 6.
review_title: A novel algorithm with convergence analysis.

final_score: rating: 3: Clear rejection
review_content: 

Greedy-GQ is an RL algorithm for a control problem that extends on GTD, which is a prediction algorithm. While Greedy-GQ asymptotically converges to a stationary point, it does so with high sample complexity. The authors reduce the variance of Greedy-GQ by incorporating SVRG variance reduction scheme to both the time-scale update of the algorithm. The main contribution of the paper is in showing that the variance reduced Greedy-GQ algorithm achieves a sample complexity that is an order of magnitude less than the vanilla Greedy-GQ. 

Major concerns:

1.	My major concern is that the paper uses SVRG for variance reduction, which is not the state-of-the-art method. Since the two seminal methods (SVRG and SAGA) have been proposed, there have been substantial achievements during the past few years along this direction, such as SARAH, SPIDER, and STORM. It is very important they author identify with enough analysis that those three competing methods as mentioned above reach the same time and space complexity (aka, w.r.t the mini-batch size). The reviewer strongly suggests the author to do so.
2.	Assumption 4 (geometric ergodicity) seems too restrictive. The author should give some more detailed justification to justify if it is widely applicable or not.
3.	For the experiments, it would have been nice to include the plots based on the objective function and not just its norms.
4.	Wordings of the experiments in 6.2 is a bit confusing to me. After the target policy is generated via the uniform distribution, is it getting improved as the off-policy control algorithm should, or is it only evaluated against the behavior policy?
5.	in section 1.2 the paper concluded Q-learning and SARSA with function approximation as related work. However, the proposed algorithm doesn’t seem to be related to it.
6.  I noticed that there is a recently published NeurIPS paper (Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis), which further reduces the merit of the paper on the perspective of adapting SVR techniques to nonstandard stochastic optimization algorithms such as TDC/Greedy-GQ. 


Minor concerns:
1.	Page 6, Corollary 4.6: Shouldn’t one of the \eta_\theta be \eta_\omega?
2.	in section 1.1 paragraph 2 line 7, it is better to use “order of O(M^-1) and O(\eta_\theta M^-1) respectively” instead of “…O(M^-1), O(\eta_\theta M^-1),…”
3.	in section 5 equation (6), it is better to use “… 1/M)” instead of “…M^-1” to keep consistency. 
4.	In section 5 step 3, it is better to say lemma D.7 and D.9 is in the Appenix.
5.	The paper mentioned “SPIDER (a.k.a SARAH)”. These two algorithms are very similar, but they are not identical, as pointed out by several papers. For example, referring to the last few paragraphs of pp.3 of the paper “Finite-Sum Smooth Optimization with SARAH” (https://arxiv.org/pdf/1901.07648.pdf).



review_title: The VR method is not SOTA, please justify

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This submission deals with the classical value-based Greedy-GQ algorithm for off-policy optimal control, and develops a two-timescale variance reduction scheme to reduce the stochastic variance of Greedy-GQ thus improving its sample complexity. 

Specifically, a variance reduced (VR)-Greedy-GQ variant that applies the SVRG-type variance reduction technique to the two-timescale updates of Greedy-GQ. Assuming linear function approximation and Markovian data samples, it is shown that the VR-Greedy-GQ achieves a sample complexity of O(\epsilon^{-2}), which is order-wise lower than the sample complexity O(\epsilon^{-3}) of the original Greedy-GQ. Convincing experiments are also provided to demonstrate the effectiveness of the proposed variance reduction algorithm.

Overall evaluation: This paper is reasonably well written and presents interesting technical results. The Greedy-GQ algorithm is an important and efficient value-based approach for off-policy control. 

Detailed comments: In the existing study, variance reduction techniques have been successfully applied to value-based TD learning algorithms for policy evaluation (e.g., VRTD, VRTDC), but they have not been explored by value-based algorithms for control, especially in the off-policy setting with Markovian samples. This paper fills this important gap. Below please find several related technical comments.

i) The main contribution is to show that VR-Greedy-GQ achieves an improved sample complexity over that of Greedy-GQ. In particular, the authors showed that (as commented in the contribution section), VR-Greedy-GQ induces a small bias error caused by the Markovian sampling and a small variance error of the stochastic updates, both errors are inverse proportional to M — the batch size of the SVRG reference batch update. Hence, a larger M should gives smaller error terms, and this is also suggested by the bounds in Theorem 4.5. However, it is not clear why Corollary 4.6 chooses the special M=\epsilon^{-1} to achieve the desired sample complexity, can the author clarify the trade-off in choosing these hyper-parameters?

ii) A key technique in the finite-time analysis is the introduction of the fine-tuned Lyapunov function R_t^m. In particular, the coefficient c_t is specially chosen so that the quadratic term on theta can be totally absorbed into the Lyapunov function for telescoping. Although this technical development is very interesting, how is it different from the traditional analysis of nonconvex SVRG? For example, see the paper Stochastic Variance Reduction for Nonconvex Optimization by Sashank J. Reddi et.al. 

iii) More recent results on finite-time analysis of TD/Q-learning algorithms dealing with Markovian samples should be discussed, as well as how the current analysis differentiates/improves from existing e.g., drift analysis in [Srikant et al, COLT'2019] and multistep Lyapunov analysis in [Wang et al, AISTATS'2020] in terms of accommodating the bias and correlations introduced by the Markovian data samples. 
review_title: A variance-reduced Greedy GQ variant along with its sample complexity analysis in the Markov setting

Meta-review: **Overview** This paper provides a way to combine SVRG and greedy-GQ to improve the algorithm performance. In particular, the finite iteration complexity is improved from $\epsilon^{-3}$ to $\epsilon^{-2}$.

**Pros** The paper is well-written. Reviewers believe this is a solid theoretical work on advancing value-based algorithms for off-policy optimal control. It has sufficient theoretical advancement and experiments demonstrations of the methods. 

**Cons** Some reviewers are concerned that SVRG is not SOTA. SVRG is not used in practice. The techniques appear to be similar to some existing works. 

**Recommendation** The meta-reviewer believes that the paper has solid theoretical contributions. SVRG is a component in the new algorithm to improve the complexity. It does not need to be "useful" or "SOTA". The paper is also well-written. Hence the recommendation is accept.
Decision: Accept (Poster)