Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyses the convergence of two time-scale TDC with general smooth function approximation. Previous analysis mainly focuses the linear approximation, but the nonlinear approximation is more powerful and its convergence analysis is more challenging; thus, this work is theoretically solid. The analysis covers both i.i.d. settings and Markov settings. 


main_review: This paper analyses the convergence of two time-scale TDC with general smooth function approximation. Previous analysis mainly focuses the linear approximation, but the nonlinear approximation is more powerful and its convergence analysis is more challenging; thus, this work is theoretically solid. The analysis covers both i.i.d. settings and Markov settings. 

No empirical study is carried out. If some reinforcement learning tasks are conducted to verify the theory, the results can be more convincing. 

1.	It is mentioned that the projection step in Line 6 of algorithm 1 is for the convenience of the analysis. So, does removing the projection destroy the convergence or yield a worse convergence rate? 
Typo: Line 103, Page 3, resent.

limitations_and_societal_impact: No negative societal impact
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper develops the non-asymptotic error bound for an important RL algorithm TDC with general non-linear function approximation. The TDC algorithm is a commonly used one for off-policy policy evaluation in practice. Existing studies on non-asymptotic error bound mostly focus on the case with linear function approximation. This work extends the study to the case with non-linear function approximation. Several new challenges are addressed in this paper, the nonconvexity of the objective function, non-linear two time-scale update rule, time-varying projection and a tight tracking error analysis. Both the iid and Markovian settings are investigated. The convergence rate provided is $\mathcal O(1/\sqrt(T))$.

main_review: Pros:
1. The proof generalizes the analysis for nonconvex optimization in [Ghadimi & Lan 2013] to the  TDC algorithm with a two time-scale structure, where the tracking error due to the two time-scale updates needs to be bounded, which is also their major technical novelty in the analysis. They bound the tracking error using the gradient norm $E[\|\nabla J(\theta_t)\|^2]$, which should also converge to zero. Other analysis of two time-scale algorithms either use a constant bound (resulting in a loose bound in the end) or using a mini-batch method (resulting in a large batch size ($1/\epsilon$). Their idea of bounding the tracking error using $E[\|\nabla J(\theta_t)\|^2]$, which is the quantity that is being bounded, is novel and interesting. This technique could be useful for developing non-asymptotic error bound of other two time-scale algorithms with a non-convex objective function. 

2. Another novelty lies in the way they handle dependency between the projection tangent plane and the sample trajectory. For most existing studies with linear function approximation, the projection is fixed, and there does not exist such an issue. They first characterized the geometry of those functions, and then decoupled the dependency by exploiting the smoothness of the function approximator.

Cons:
There is no significant difference between the iid setting and the Markovian setting. The approach of handling the Markovian noise using a mixing argument is kind of standard in the current RL literature.

Quality: The complexity of $\mathcal O(1/\sqrt(T))$ looks natural. This result matches with the complexity of optimizing a general smooth non-convex function in [Ghadimi & Lan 2013]. The proof looks correct. 

Clarity: This paper is well-written. I enjoyed reading this paper. The proof of sketch part is clear and informative, where the major steps and technical novelty are highlighted. The table of contents in the appendix is helpful to navigate in the appendix. 

Significance: As discussed above, the idea of bounding the tracking error using the gradient norm is novel, and is useful for analyzing other two time-scale algorithms with non-convex objectives.




limitations_and_societal_impact: Some comments/questions are also listed below.

1. The experiments could be moved to the main body of the paper as there is still room. 

2. In remark 2, it is discussed that the ratio $\alpha/\beta$ does not necessarily need to go to zero (in this paper alpha and beta are chosen to be constant at the order of $O(1/\sqrt(T)$). This is kind of counterintuitive. Some more elaboration on this issue could help.
In assumption 4, it is assumed that the MDP is uniformly ergodic. It is kind of a standard assumption in RL analysis when there is Markovian noise. It would be helpful to discuss what kind of MDPs satisfy this assumption.

3. Figs 4 and 5 in the appendix shall be aligned. 

4. Page 25, it is assumed that the step size $\beta$ satisfies some condition $\beta\tau_\beta C_\phi^2\leq 1/4$, which should also be stated in the theorem.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides finite-sample analysis on the two time-scale TDC algorithm with non-linear function approximation, proposed by [5] Bhatnagar et al. Both the i.i.d. setting and the Markovian setting are considered. The convergence rate is near-optimal given the target MSPBE function is generally non-convex.
main_review: The paper is clearly written and easy to understand.  

Based on the asymptotic results given in [5] Bhatnagar et al., it is natural to consider the finite-sample analysis and the non-asymptotic rate $1 / \sqrt{T}$ achieved here is a bit surprisingly good. The downside though is that the whole analysis falls under the framework where the outside loop (the slower component $\theta$) is to optimize a general non-convex function with stochastic gradients, while the inner loop (the faster component $\omega$) is a linear stochastic approximation task (which is effectively strongly convex). Therefore the analysis can always be decomposed to first bounding the tracking error of the faster component $\omega$ to the optimal solution $\omega(\theta)$ while the slower component only suffers a small loss from the tracking error aside from the classical non-convex SGD analysis. The Markovian setting is great but also suffers from a similar novelty issue since there has been plenty of previous works dealing with the Markov noise under the uniform ergodicity assumption. 

One suggestion is that the arguments in Line 539 and Line 594 that requires $\alpha$ to be much smaller than $\beta$ need to be stated more clearly, because there are too many constants involved there and it is better to write down an assumption on the ratio $\alpha / \beta$.  

It would help highlight the technical contribution if the author can also compare the two time-scale techniques used here with those in some previous works:
1. (this presents the non-convex outer loop + convex inner loop framework) A Finite-Time Analysis of Two Time-Scale Actor-Critic Methods. NIPS'20 
2. (a more general formulation) A Two-Timescale Stochastic Algorithm Framework for BilevelOptimization:  Complexity Analysis and Application to Actor-Critic. Arxiv 2007.05170


limitations_and_societal_impact: The authors pointed out the limitation that the target function is generally non-convex and therefore this paper can only guarantee convergence toward a saddle point rather than a global minimum. There are no specific concerns with respect to its social impact.
review_title: null

Meta-review: This paper provides non-asymptotic analysis for TDC algorithm with general smooth function approximation, which is technically sound and novel. The authors’ responses have well addressed the reviewers’ concerns. All the reviewers have reached a consensus on the acceptance of this work. We suggest that the authors further polish their paper to prepare a camera-ready version based on the reviewers’ comments.
Decision: Accept (Poster)