Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies reinforcement learning with a 1-hidden layer neural network and low-rank polynomial function approximation schemes. 

Under mostly standard assumptions about realizability, completness etc, they provide algorithms mainly focusing on sample complexity in cases when there is access to a perfect generative model of the transitions and in the fully online setting, where planning is not possible in episodic reinforcement learning.

They improve upon the sample complexity with respect to existing baselines for the respective function approximation schemes.
main_review: My main questions and concerns are as follows:

1)The baseline considered in Du et al 2020c, considers a weaker form of realizability assumption, where they can find the best function approximation for $Q^*$ in the given class upto a error $\delta > 0$. Now, since the class here are 1-layer neural networks or low-rank polynomials, there exists simple deterministic transitions that have complex Q functions (i.e, when using shallow networks this requires exponential width), (see Dong et al. 2020). Is it possible to comment on the tradeoff due to expressivity errors?

2) Could the authors clarify on the dependence on H, more explicitly if possible?

3) Theorem 5.2 states that there is a unique solution to the system of equations. Is there an efficient algorithm for it? Since it is used in Algorithms 4 and 5.

4) A large portion of the results in the neural network recovery is from Zhong et al. 2017, as a clarification is assumption A11 satisfied by ReLu activation?

Additional Reference:
Dong, Kefan, et al. "On the expressivity of neural networks for deep reinforcement learning." International Conference on Machine Learning. PMLR, 2020.

After Rebuttal:

 I raise my score after the authors made the necessary clarifications.
limitations_and_societal_impact: See above for limitations.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This paper focuses on analyzing sampling efficiency of nonlinear reinforcement learning with neural network approximations of the $Q$ function. It reduces the sampling complexity from $O(d^{\text{poly}(1/\epsilon)})$ to $O(\text{poly}(d) \exp(k))$ where $k$ is the width of the hidden layer of a two-layer fully connected neural network. The idea is described accurately and the paper is overall well written. 
main_review: The paper considers both neural network and polynomial approximations of the $Q$ function. Since polynomial approximation does not scale well with the dimensionality, the analysis on the sampling complexity of neural network-based $Q$ function approximation is more interesting. In the neural network setting, the RL algorithms, i.e., Algorithm 1, 2 and 3 are quite standard RL algorithms, so the novelty does not lie in algorithm development. In my opinion, the main contributions of this paper should be the proof of Theorem 4.4, 4.5 and 4.6. However, the main idea of the proofs are not included in the main paper. 

When digging into Appendix, it becomes apparent that the key improvement of the sampling complexity are based on the results in 

Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one-hidden-layer neural networks. Proceedings of the Thirty-fourth International Conference on Machine Learning (ICML), 70, 2017.

For example, the proof of Theorem 4.4 is given in Appendix as Theorem A.1. In the proof of Theorem A.1, the key step is the use of Theorem A.14. When looking at Theorem A.14, the proof is provided in Appendix A.4.2 from Line 715 to Line 725. The main ingredient of the ten-line proof is the used of Lemma D.3, Lemma D.11 and Lemma D.16 in [Zhong et al. 2017]. Similar strategy is used to prove Theorem 4.5 and 4.6. Therefore, I think Theorem 4.4 - 4.6 are just simple extension of the results in [Zhong et al. 2017] to the RL setting, so the theoretical contribution of this paper is not significant.

On the other hand, I strongly disagree with the way the theoretical results are presented, because I don't think the importance of [Zhong et al. 2017] is explicitly and sufficiently acknowledged in the main text. In fact, the paper [Zhong et al. 2017] is only cited twice in the main text. Even though it is mentioned in Line 49 that [Zhong et al. 2017] is one of the main technique used in this paper, but it is not completely not clear that the complexity of NN-based approximation in Table 1 comes from the neural network recovery result in [Zhong et al. 2017]. 

Additionally, there is a lack of justification of the appropriateness of Assumption 3.1 and 3.2. It looks like the assumptions were made on purpose so that the results in [Zhong et al. 2017] can be used. It would be helpful if the authors can provide some RL examples that satisfy the assumptions.  


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers RL with neural function approximation, extending significantly previous works that only focuses on linear feature approximation. In particular, the authors propose (1) an efficient algorithm using two-layer NNs in a generative model assuming completeness, and (2) an efficient algorithm with two-layer NNs but only assuming realizability.

The results significantly extends prior research on linear methods, or methods with bounded eluder dimension.
main_review: - Originality: the paper is one of the few papers that consider reinforcement learning in (the more general) neural network approximation regime. Related works are clearly cited and ~the work has made significant contributions different from existing research~. Please see the updated comment. I realized I neglected the result's reliance on [1] and have adjusted my score accordingly.

- Quality: the theorems and results in the paper are well justified. 

- Clarity: proofs are clear and well-written.

- Significance: being one of the first papers studying neural network approximation, the paper could pave way for future research in this area. ~The results are technically sound and significant.~ See updated comment.

[1] Zhong, Kai, et al. "Recovery guarantees for one-hidden-layer neural networks." International conference on machine learning. PMLR, 2017
limitations_and_societal_impact: Limitations and scopes of the theoretical results are clearly stated. The strong assumptions required are reemphasized in the conclusion and directions for future research are proposed.

No apparent negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies sample efficient RL with two-layer neural network function approximation with a generative model. In particular, they prove that they can learn an optimal policy with poly samples with only realizability in deterministic MDP, and that the sample complexity for learning a near-optimal policy in stochastic MDPs is in an order of $\epsilon^{-2}$ in two cases: policy completeness assumption and Bellman completeness assumption. The algorithms they use are based on simple (non-optimistic) value regression. 
main_review: **Strong points**:
- Sample efficient RL with deep neural network function approximation is an important and timely topic 
- The sample complexity with neural network function approximation does not suffer from the curse of dimensionality  (i.e., sample efficiency is possible in RL with neural network function approximation)

**Weak points**: 
- The main guarantees are direct results of the lemmas of the exact network recovery from noisy/noiseless data [Zhong et al, 2017]. What is a technical innovation in this paper?  
- I think learning with a simulator (a generative model) is rather not a practical setting as in practice, data is sequentially obtained from the beginning of an episode. Can the result with neural network function approximation here be extended to such online setting? Currently, the paper has the result in an online setting with polynomial realizability. 
- The paper claims that “this is the first paper that shows sample efficient RL is possible with neural net function approximation”. It does not seem so. For example, Yang et al., 2020 “On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces” already obtains a sample efficient RL in online setting with neural function approximation using optimism. Without optimism, Pan Xu and Quanquan Gu “A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation” obtains sample efficiency of Q-learning with neural network function approximation in online setting with Markovian data.  

**Minor comments**
- The abstract only mentions neural network function approximation but in the main paper, it also considers polynomial function. 
- Line 139: typo, \kappa = s_{\max} / s_{\min}
- Line 93: Missing literature, I think you should consider adding Jin et al, 2021, “Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms”, as you discuss sample efficient RL with function approximation. 

**Questions for authors**:
- What is a rationale for the sample efficiency of simple value regression without optimism in your proposed algorithms Alg 1,2,3? What is the key to such a simple algorithm that can lead to the obtained sample efficiency? Probably due to the generative model that we can obtain good coverage of the state-action space that does not require intricate exploration such as optimism, but I would like to hear the authors discuss more on this. 
- More discussion on how mild are the policy-complete and Bellman-complete assumptions. 

------------------ POST-REBUTTAL----------------------

Thank you the authors for providing a detailed response to my concerns. After reading the authors' responses and other reviews, I am happy to raise my initial score to 6 for the following reasons: the paper has made a solid contribution in showing the feasibility of sample efficient RL with non-linear neural network function approximation in the generative setting. Technically, though the paper relies heaviely on the parameter recovery theorem in non-linear neural networks and an extension to RL setting in the generative model is quite natural and straightforward, the result in the paper does complement the literature of RL with non-linear function approximation and can be helpful to the community. My initial score was due to mainly two issues: the technical contribution of the paper and the result's significance. Though there is no significant technical contribution as in my initial review, I misinterpreted the paper result when comparing it with the literature RL with overparameterized neural networks. I encourage the authors to take the discussion into the revision.   


limitations_and_societal_impact: The authors have partly addressed the limitations of their work and fully addressed the societal impact of their work.
review_title: null

Meta-review: This paper has received a lot of discussion.
In the end, the reviewers agree that the paper contributes to the literature and should be accepted.
There are a number of useful comments that the authors should take into account when preparing the camera ready version of the paper.
Decision: Accept (Poster)