Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes new nonlinear bandit and reinforcement learning algorithms whose sample complexity toward local maxima are bounded by the sequential Rademacher complexity of particular loss functions (and do not depend on the action dimension). An interesting insight obtained in this paper is that when dealing with nonlinear models and dynamics (in settings where the action dimension may be very large), maximizing the virtual return suggested by a strong online learner (with carefully augmented loss) may lead to good convergence guarantees to local maxima.
main_review: The paper is well-written. The theoretical results are sound and the proofs are correct. The problem studied in this paper is well-motivated and very interesting. The main algorithmic idea of augmenting the loss function of the online learner is quite clever. I recommend  acceptance.

On the downside, I would like to say that the algorithms and results in this paper are more like "proofs of concept", and some places of the paper are still clunky. I discuss several limitations and provide some suggestions below.

1. The paper seems to mainly focus on the "pure exploration" or PAC setting of bandits and RL. While there is some discussion on the "local regret" in Appendix D.5, it is just a slightly different analysis of the same algorithm (without additional efforts tailored for the regret setting). Do the authors have any ideas on whether one can get substantially better regret bounds by incorporating additional considerations for the regret setting? By the way, an interesting thing that I find in this paper is that the current algorithm already tries to avoid "over exploration", even in a "pure exploration" setting --- is it because of the fact that the paper only asks for convergence to local maxima? Do the authors have any ideas on whether the notion of "local regret" would encourage certain behavior of learning algorithms?

2. The assumptions on deterministic reward and deterministic dynamics are restrictive. While the authors provide some impossibility results on the noisy reward setting, a framework that can only deal with deterministic reward and dynamics are far from being practical. I would encourage the authors to improve their framework and try to understand this issue better in future work.

3. The theoretical bounds proved in this paper have a much worse dependence on $\epsilon$ compared with existing dimension-dependent bounds. This may make the statistical guarantees undesirable compared with dimension-dependent or specialized algorithms in many cases.

4. Since the algorithms need to *augment the loss functions to be non-standard ones* (see equation (5)), the tasks of bounding the sequential Rademacher complexity and designing computationally efficient online learners both become more challenging. 

I notice that the authors actually have some very related discussions in Appendix B. It would be good if some key points of the discussions can also be mentioned in the main text.

Minor comments: 
1. In lines 145-146, the notation $[T]$ appears without any definition (I understand what $[T]$ means but it is good to write everything clearly).
2. I find the following two references also relevant.
[1] Xu, Y., & Zeevi, A. (2020). Upper counterfactual confidence bounds: a new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07876.
[2] Foster, D. J., Gentile, C., Mohri, M., & Zimmert, J. (2020). Adapting to misspecification in contextual bandits. NeurIPS. 
Both [1] and [2] consider model-based nonlinear (contextual) bandits with infinite actions and obtain regret bounds that depend on the action dimension.

======update after rebuttal======

Thank you for the feedback. I keep my positive rating and vote for accepting the paper.
limitations_and_societal_impact: The authors have discussed the potential negative societal impact in their Appendix A.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies model-based nonlinear bandit and reinforcement learning and proposes the ViOlin algorithm (Virtual Ascent with Online Model Learner). The main contributions are as follows.

1) For bandit problems, with deterministic reward functions satisfying Assumption 2.1 (Lipschitz over continuous actions, smooth over actions, and the third order derivative over action is bounded), and with sublinear sequential Rademacher complexity, they show that the ViOlin algorithm achieves an $\epsilon$ approximate local maximum using $\tilde{O}(\epsilon^{-8})$ iterations, which does not depend on the dimension of action space.

Some instantiations are shown, including linear bandit with finite model class, with sparse or structured model vectors, and two-layer neural nets, which is the first result of non-linear bandit with neural network parameterization.

The main idea is to fit the estimation of gradient and Hessian, and show that the current greedy action can be improved until the parameter is close enough to an approximate local maximum.

2) For RL, with deterministic transition, and Assumptions 4.1 and 4.2 (regularity of value function and policy), they show that the similar ViOlin (Algorithm 2) achieves an $\epsilon$ approximate local maximum using also sublinear iterations.

The difference with bandit design is that the loss function is using one-step model prediction errors rather than gradient and Hessian.

3) The authors show some lower bound results. In particular, (i) using ReLU activations in one-layer neural network bandits, finding global optimal action takes exponentially large iterations. (ii) the failure of Eluder dimension: one-layer neural networks has its Eluder dimensions exponentially large. (iii) the failure of UCB: with linear reward function, and two-layer neural network as the hypothesis function class, UCB would take exponential sample complexity to find the optimal action.
main_review: Overall, this is a good paper, making good contributions to RL theory community. The presentation of the main paper is clear and easy to follow. The intuition is very well explained. There are following questions I would ask the authors to clarify.

1) In lower bound results, it is mentioned (at least for one layer NNs) ReLU is needed. Does the "Two-layer neural nets" instantiation also apply to NNs with ReLU activations? It seems from "link function with bounded derivatives up to the third order", it does not apply to ReLU.

Then is it possible that for the link functions with "bounded derivatives up to the third order", finding a global optimal solution is also possibly efficient?

2) Is Hessian used for eliminating saddle points? What kind of results can be obtained if just using gradient?

3) The deterministic reward and deterministic transition assumption makes the algorithm kind of restrictive. Any idea how to remove those assumptions?

Minors:

4) What is the meaning of $\mathcal{R}$ in Algorithm 1 (line 3)?

5) What is the definition of $\mathfrak{A}$ in line 887? Does this mean the approximate local minima set?

======update after rebuttal======

Thank you for the feedback. I would keep my current rating and vote for accepting the paper.

limitations_and_societal_impact: The paper is mainly theoretical and the algorithm is not implemented. There is no specific potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers learning in deterministic bandit and reinforcement learning problems with function approximation. They quantify the complexity of the function class using the sequential Rademacher complexity of a related loss function (although in some settings, it is not super clear how this relates to the complexity of the reward/value function). In the bandit setting, they provide a general regret bound and instantiate this for various different assumptions on the model, including two layer neural networks, which is a nice result. To extend their results to reinforcement learning some assumptions are made so that the value function can be written as a non-linear function of the policy parameters and optimized accordingly. They then provide a slightly simpler loss function and show that the sample complexity can be bounded in terms of the sequential Rademacher complexity of this. Finally, the authors provide some interesting lower bounds showing that finding a global maximum is exponentially hard, and motivating them to study the sample complexity to find an approximate local maximum.
main_review: The discussion of the pros/cons of the UCB algorithm in lines 198-208 is nice as is the non-technical motivation of the algorithm in lines 219-228. However, I have very little intuition about why the loss function and definition of y_t used are the most appropriate/natural. It is nice to see a general result bounding the sample complexity in terms of the sequential Rademacher complexity in Theorem 1. In the examples following Theorem 3.1, it always seems that zeta_h^4 epsilon^{-8}> zeta^2_{3rd} epsilon^{-6}. Are there any realistic cases where the converse is true? Does their result ever lead to epsilon^{-6} rather than epsilon^{-8} complexity? The epsilon^{-8} dependence seems sub-optimal, I imagine it should be epsilon^{-2}  but do the authors have any intuition/lower bound to indicate what the optimal dependence on epsilon is in this setting? In the discussion about the application of their results for linear bandit in Section 3.1, it would be helpful to also include the dependence on epsilon of some of the other algorithms. It is difficult to compare fairly when the authors only highlight the terms that their algorithm improves on. In some cases it may be that d<1/epsilon so a worse dependence on d would be preferred to a worse dependence on epsilon in such a case. I am also curious about the results for sparse linear bandits when Theta is infinite? In such a case I imagine we may replace |Theta| with the covering number, which would then lead to linear dependence on d, do other approaches have worse dependence on d in that case too?

It is nice that there is an extension to reinforcement learning. The assumptions made in the extension to model-based reinforcement learning seem to reformulate the problem as a contextual bandit problem, thus making the extension simpler. However they seem quite strong, even though the authors give a simple example where they are satisfied. The loss function for the reinforcement learning setting seems slightly more natural than that in the bandit case. I would appreciate more discussion of how this is calculated within the algorithm though (e.g. in round t, do we need to play according to both policies pi_t and pi_{t-1}?) The loss function depends mainly on the transition, and so the sample complexity depends on the difficulty of learning some function of the transition function. However, the introduction to section 4 is written as if we can make an assumption on the value function only, but this may not necessarily lead to having a transition function st the Rademacher complexity of the loss is small. Instead it seems that the idea is that we assume the dynamics are members of some function class and then show that this leads to a value function of the desired form as in example 4.3. It would be helpful to clarify this.

The lower bounds in Section 5 are nice. In particular, the result in Theorem 5.1 showing that the sample complexity can be exponential in d when comparing to global maximum for one-layer neural networks is nice, and well motivates comparing to local maxima as is done in this paper. Similarly the result in theorem 5.2 is also nice (although it is proved concurrently in another paper). In theorem 5.3, is the sample complexity exponential when compared to the local maximum or global maximum? And is the only reason for the exponential sample complexity the fact that the action set is chosen to be exponentially large?

Lots of content seems to be deferred to the appendix making the main paper hard to follow at times.

Minor comments:
- It would be good to have a more thorough discussion of [54]. Saying the conditions can ‘likely’ not be satisfied is not rigorous enough.
- the discussion in lines 136-138 is incomplete and needs expanding upon. I thought the remark was to motivate the need to consider deterministic rewards, but Appendix C.1 seems to be about the difficulty of finding a global maximum. It is not clear to me how this relates to considering local maxima in a noisy setting.
- I don’t follow the discussion of why the number of random projections in line 234 does not depend on the dimension, can more details be given?
- I’m not sure what the ‘local regret’ means in line 21 is nor where it is defined.
- the definition of the loss function in (5) is quite involved. I therefore have no intuition for how difficult this will be to learn as a function of the original parameters of the problem and why this is an appropriate loss definition. Also what is kappa here?
- A couple of times in Section 3.1, the authors ‘claim’ that the sample complexity is bounded by XXX. Is this just a claim or is it proven?
- I don’t follow why it is beneficial to consider stochastic policies in Section 4, could more details be provided on this?


=========
After response:
Thank you to the authors for answering most of my questions. I hope that for the final version of the paper the authors clarify some of the discussions and add further details about the dependence on epsilon and the construction of the exponential lower bound.

limitations_and_societal_impact: Some limitations discussed but not in huge detail. There is no discussion of societal impact but since this is a theoretical paper, that is probably OK.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work investigates model-based bandit and RL under non-linear function approximations. In particular, it focuses on convergence to approximate local maxima under deterministic reward (and deterministic dynamics for RL). Several technical results are derived showing that the presented model-based algorithm can have a favorable sample complexity that only depends on the sequential Rademacher complexity of the model class. The paper also contains some hardness results to better contextualize the contribution of this work.
main_review: The paper is technically dense but the authors manage to provide enough intuition and explanation for the results. There are generally enough context for one to understand the corresponding results. I didn't go into the technical details, but the contributions seem solid, and the results and technical novelty could be interesting for the theoretical community.

One question I have is that to what extend, the results depend on the deterministic assumptions (deterministic dynamics and reward). The technical novelty as claimed by the authors is to explore with model-based curvature estimates. To achieve this, it seems from page 6 that the algorithm leverages the deterministic property to estimate the projections. The authors also mention some motivation for considering deterministic rewards (lines 136 -138). Overall, I would appreciate a concrete remark on both the deterministic dynamics and reward, explaining the potential difficulties/extensions of the current framework. 

========after response======
I thank the authors for the response. I'm happy to keep my positive evaluation and hope that the authors could also include few sentences in the final version to clarity the assumptions.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper takes a new approach to the theory of exploration in reinforcement learning with function approximation, with the main insight being to aim for local optimality rather than global optimality. The reviewers agree that the paper is well-motivated, technically interesting, 
 and fairly creative result that will likely inspire further research along this direction in RL. While there are many directions in which the technical results themselves can likely be improved (e.g., moving beyond deterministic dynamics), it seems appropriate to leave this for future work.

The authors are encouraged to incorporate the clarifications suggested by the reviewers.
Decision: Accept (Poster)