Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proves that the adaptive temporal-difference (TD) learning with ReLU neural network approximation converges when the width of the network is sufficiently large. Moreover, this paper proves that adaptive TD is faster than TD with the ReLU neural network approximation.
strengths_and_weaknesses: Strengths:

- To the best of my knowledge, Theorem 1, the main result of this paper, is significant and highly non-trivial. In particular, this paper has extended the analysis of adaptive TD with linear function approximation to multiple layers neural network approximation.

Weakness:

- The analysis is limited to ReLU networks.

- It is not clear if the bound in Theorem 1 is tight. The authors might consider running some experiments to illustrate this.

- The writing of this paper can be further improved. In particular, the current version of Section 2.4 is a little bit hard to follow. This paper also has a complicated notation system; however, some notations are used without first defining them. Examples include $\hat{f}$ in Definition 1 and $\mathbf{B}$ in Lemma 1.


questions: - Might the authors briefly explain why the analysis is limited to ReLU networks?

- Might the authors briefly explain the tightness of the bound in Theorem 1?

limitations: The authors have adequately addressed the limitations and potential negative societal impact of this paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the adaptive TD method in the nonlinear function approximator setting, specifically MLPs with ReLU activations. It essentially bridges two prior works, one of which establishes the convergence of TD under MSPBE to the global optimum, while the other proves accelerates rates of convergence for adaptive TD in the linear setting. The current submission combines these the two and proves accelerated rates of convergence to the minimizer of MSPBE for adaptive TD in the nonlinear setting.
strengths_and_weaknesses: The paper provides a natural next step for a recent body of work that have analyzed finite-time convergence rate for (projected) TD methods in the non-linear setting. In terms of originality and significance, the main result itself, if somewhat incremental, is novel and useful. Beyond the result itself, the authors introduce a new proof technique that may prove useful beyond the scope of this paper. The paper is technically polished with a clear exposition of the results and its derivations (I did look at the proofs, but not in great detail). Overall, the paper is well written with a clear motivation and contribution.  

My main issue with this paper is that it does not delineate the difference between MSBE (which is not analyzed) and MSPBE (for which the results hold). This is extremely important because the proof technique that this paper uses (introduced in prior work) relies on an implicit linearization. The approximation error induced by linearization grows with diameter of the projection set. This is the main limitation of this type of analysis, because tight convergence rates requires the projection set to be small, and hence the minimiser to which it converges is often very different from the minimizer of MSBE. Consequently, these result are really only relevant for MSPBE. While understanding MSPBE is in itself useful, it important to delineate the contribution made to not con that the paper fails to make. With that said, this can be resolved by adding a paragraph or two. 
questions: - The bounds obtain depends quadratically (in fact, cubically) on the diameter of the set V. The authors avoid this issue by carefully setting a whole host of magic constants to have them magically vanish, yielding the final bound. However, it is unlikely that any practical application can actually make these choices. Do the authors see an avenue forward for this line of research that avoids such strong depends on the diameter of the projection set?

- The authors mention a novel proof technique, do you believe this technique can be useful in other cases as well? 

- Do the authors have an intuition of how hard it would be to extend these result to also include policy improvement iteration?
limitations: See above. Overall, the authors are very clear about assumptions under which their results hold.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Disclaimer: I do not have enough background to check the technical details and hence basically make a guess. There may be another reviewer (sorry for my late notice) for this paper. I will go through other reviews carefully and adjust my score accordingly.

The paper is purely theoretical. It provides the finite-time analysis for the adaptive TD with multi-layer ReLU networks. 

strengths_and_weaknesses: Strength: 

This should be the first work in analyzing the convergence of adaptive TD with multi-layer ReLu NNs.

Weaknesses: 

My main concern is the work is likely to be incremental, in the sense that the proof framework and the method of proving technical assumptions, and lemmas are quite similar to those existing papers as cited by the authors, especially [7,18,48]. I expect an explicit discussion about the differences in the techniques used for proofs.  

The main theoretical result is not informative; it is known that usually adaptive learning rate strategies can improve the convergence rate by choosing appropriate hyper-parameters (as the non-adaptive/plain version is simply a special case). But the result does not provide any additional insight into what designs/hyper-parameter choices in the adaptive method can help improve convergence.
questions: NA. 
limitations: NA
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper establishes the finite-time analysis for the adaptive TD with
9 multi-layer ReLU networks approximation whose samples are generated from
10 a Markov decision process. Overall, the paper includes interesting results. However, it needs modifications to improve its quality.

strengths_and_weaknesses: Strengths: New analysis of TD learning with neural network. The established theory shows that if the width of
the deep neural network is large enough, the adaptive TD using neural network 12 approximation can find the (optimal) value function with high probabilities under he same iteration complexity as TD in general cases. 

Weaknesses: 
It includes the projection step, which is in general hard to perform. 
The overall presentation is sloppy.
questions: 1) \phi is not defined in the definition of the neural approximated Q in line 124. How can we understand the  feature vector in the nueral approximation? Please clarify it in the paper.
2) Why do you use boldface for value function while the normal font for Q-function?
3) Why do we have sqaure root of m in the definition of f? Please clarify it in the paper.
4) The norm || ||_F in eq (5) is not defined. 
5) The set B in Lemma 1 is not defined. 
6) It is in general hard to understand the intuitive meaning of Theorem 1. For example, what is the meaning of the objective function being small? How can we interprete the solution theta^*? Moreover, it is not easy to conclude that the bound is small in practice. More dicussions are needed to clarify the above points.  
7) Overall the overall presentation is sloppy. There are many math expressens whose definitions are lacking. 
8) There is notational explosion. It is recommended to simplify the notations.
limitations: It seems that it is hard to conclude meaningful results in practice from the analysis in this paper.
review_title: null

Meta-review: metareview: The reviewers agree that the theoretical results presented in the paper are solid and advance our understanding of the behavior of temporal difference (TD) methods, which are at the core of most reinforcement learning algorithms. The contributions of the paper can be summarized in two main results:

- Adaptive TD combined with a ReLU neural network converges when the width of the network is sufficiently large; 

- Adaptive TD combined with a ReLU neural network converges faster than its non-adaptive counterpart.

Both results are important and novel.

One consistent complaint among the reviewers was the paper presentation, which was considered slightly sloppy and not very accessible. We strongly encourage the authors to perform a thorough revision of the paper, paying special attention to the definition and consistency of the notation adopted. We also suggest the authors add intuitive explanations wherever possible to make the paper accessible to a wider audience.

confidence: Certain
Decision: Accept