Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the exploration problem for MDPs with transition kernel captured by general function classes with bounded covering number. The transition dynamics is assumed to be a low-rank Gaussian RBF kernel with unknown features of states and actions, which captures both linear MDPs and a number of neural nets as special cases. It proposes an exploration algorithm named ELNF that has provable sublinear sample complexity to find a near-optimal policy. The sample complexity is guaranteed to depend only on the covering number instead of the Eluder dimension, which is shown to be exponentially large even for two-layer neural nets.

strength_and_weaknesses: I found this paper very well motivated with inspiring results. The major observation made in the paper is that the kernelized nonlinear regulator, linear MDPs, and neural-nets parameterized MDPs can be summarized by the so-called MDPs with neural dynamics models. The neural dynamics models assume the transition dynamics is proportional to the Gaussian RBF kernel in the low-rank embedding space of the states and actions. To find the optimal policies, the proposed algorithm ELNF adapts estimation and planning techniques based on MLE estimation scheme in low-rank MDPs and kernelized LSVI algorithm proposed by Yang et al. (2020). However, it requires much effort to adapt these techniques in the neural dynamics model, which I believe is another key novelty. 

Nevertheless, I do have some concerns about the results of the paper. 

1. The first question is about the number of actions appearing in the sample complexity. For general MDPs with neural dynamics, the number of actions should also be large. Examples include continuous control tasks, combinatorial optimization tasks, etc. The famous AlphaTensor algorithm has exponential number of actions. I think it is better to discuss how to perform "discretization" or establish some Lipschitz assumptions on the action space to reduce the cost of uniform sampling.
2. Intuitively the log-covering number of neural nets should have polynomial dependency on the number of parameters. It seems that the sample efficient neural dynamics model does not include the well-known over parameterized neural nets whose number of parameters are very large.
3. The authors claim that the ELNF algorithm is computational-efficient if the optimization oracle (4.3) and (4.4) can be implemented efficiently. How does this oracle implemented when the dynamics is parameterized by neural nets?
4. I think there should be more discussions on the decay rate $\gamma$ of the covering number. How large is this decay rate for common neural nets? Could you provide some intuitions on why $\gamma$ affects the sample complexity in the exponents?
5. Why do you need step -1 and step 0, and how do you assure $s_1$ is exactly the initial state?

A minor question: 
Page 9 (comparison with Done et al.(2021)): $\epsilon=0$ should be $\gamma=0$
clarity,_quality,_novelty_and_reproducibility: The statements in the paper is very clear, and the organization is pretty good. See above for the discussion on the novelties.
summary_of_the_review: This is a good paper studying the neural dynamics models in RL, though I do have some problems about the results. I recommend for accepting the paper, and may raise my score if my concerns are addressed properly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyses a method for learning transition and reward dynamics in MDPs.  They show that a more generally parameterised MDP can be solved efficiently.  No empirical results are presented, but extensive theoretical analyses are.  

strength_and_weaknesses: This is an **intensely** theoretical paper, in a domain that I am not overly familiar with.  While I have an understanding of the high-level findings, I did not and cannot faithfully review the derivations in the supplement (which is over 40 pages long).  

This paper is really in two parts: there is the high-level algorithm and result (that an MDP with NN link functions can be handled efficiently), and a long sequence of incredibly low-level results proving out the theory that underpins this algorithm.  I think there is merit in this paper for both audiences at ICLR:  a high-level audience which will benefit from the formalism, discussion of MDPs and the final result, and a low-level audience that will enjoy the theoretical analysis.  

## Strengths
1.  The paper does an excellent job of defining the core RL terms and formalism.
2.  The core idea is appealing, and provides a good generalisation of existing ideas.
3.  The authors appear to have done an incredibly thorough job of theoretically analysing the topic.  
4.  Although a bit too theoretically and technically heavy for my liking, the material that is there is presented exceptionally well, with basically no typos, typographical errors or grammatical errors.

## Weaknesses

### Challenging presentation.
The intensity of theoretical analysis is also a weakness.  While the core claims seem reasonable, I don’t believe many, if any, readers (or reviewers!) will review the supplementary material.  While the authors are to be commended for the depth of their theoretical analysis, they must do a better job in breaking down the analysis and making it more accessible for the average reader.  Sketch proofs are the main way of doing this.  

Some of the theoretical material and nuanced comparison could be dropped to the supplement and replaced with higher-level summaries to expand the target audience of the paper.  

### Methodological Comments
I understand that assuming oracles is common in RL analysis (because the alternative is realistically intractable to analyse), but I would like to see some comment on what the impact of not being able to use an oracle in practice is.  

Building on this, I would like the authors to confirm that my evaluation of their method is correct:  You essentially rollout under the current policy, and then take two steps from a uniform policy.  This uniform sampling increases the diversity, but degrades the sampling efficiency.  I am struggling to see the relevance of exactly two steps under a uniform policy, after rolling out for P steps.  Is there not a more principled way of doing this?  Eg. rolling out under a policy with an entropy increase (adding uniform at each timestep, increasing the variance)?  Why is exactly two additional steps the best option?

Then, the “method” is using an oracle to “solve” for the transition and reward functions from a very expressive variational family using these extra two steps.  Why do you use just the extra two steps?  Isn’t it more sample efficient to use the whole trajectory?  Does using just the final two steps bias the function estimator to be biased towards the regions of state space with a high occupancy at the *end* of the trajectory? 

Then the remaining analysis is showing that the approximation error is bounded with a tractable complexity?  One thing that I don’t understand is the “exploration bonus”.  This exploration bonus modifies the policy that is currently held, and so does this bonus go to zero during optimization, so that the final policy is “purely exploit”?  The policy learning is also done exactly through using the planning algorithm in the appendix?  Does this algorithm impose any further constraints on the space?  Does inaccuracies in the planning algorithm lead to pathological failures in the algorithm?  


### Empirical Validation
I acknowledge that ICLR has a strong purely theoretical remit.  However, for an algorithm as practically motivated and generally applicable as this, I would have liked to have seen at least a toy example.  This is partly to “validate” the theory, but also to help the reader understand the different facets of the algorithm.  While this is not a requirement for my response, I implore the authors to at least explore applying this to an LQR, an in-built MuJoCo example, even something like mountain cart.  This would help the reader a lot, and would further increase the reach and impact of the paper.  


## Minor Weaknesses / Typographical Comments

(a)  Advanced concepts such as covering number and Eluder number are completely undefined (although maybe there is little in this paper for anyone that doesn’t already understand those terms).  

(b)  The bold-facing of fonts is unnecessary.  

(c)  Are the terms in the norm in (3.4) reversed compared to the preceding and next equation?  It would probably be clearer if they were the same way around in each expression.  

clarity,_quality,_novelty_and_reproducibility: Modulo my comments above, the works seem to be of a high quality, original, and a good contribution.  

summary_of_the_review: Since I cannot faithfully comment on the full theoretical extent of the work, but the content that I have analysed is good, I will rate this paper as a weak accept.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper aims at building "novel algorithm that designs exploration incentives via learnable representations of the dynamics model by embedding the neural dynamics into a kernel space induced by the system noise."
strength_and_weaknesses: Strength:
The aim of the paper seems ambitious and interesting

Weaknesses:
The paper is not clear
clarity,_quality,_novelty_and_reproducibility: Many elements in the paper do not seem well supported/nor correct or they are at least not written in a way that makes the paper understandable. Here is a subset of these elements:

- Beginning of page 5, it is written that "Thus, (3.4) can be equivalently written as (...)". It is however very unclear how the authors manage that. Where is the exponential for instance?
- The following paragraph is strange 

"To simplify the presentation of the algorithm in our work, we introduce an extended MDP, where we assign meanings to steps h = −1, 0, H + 1, and H + 2. In particular, the interaction of an agent with the extended MDP starts with a dummy initial state s−1. During the interaction, all the dummy state and action sequences {s−1, a−1, s0, a0} lead to the same initial state sinit. Moreover, the agent is allowed to interact with the environment for two steps after observing the final state sH+1 of an episode. Nevertheless, the agent only collects the reward rh(sh, ah) at steps h ∈ [H], which leads to thesamelearningobjectiveastheoriginalMDP.Inaddition,wedenoteby[H]+ =[−1,0,...,H+2] the set of steps in the extended MDP. In the sequel, we do not distinguish between an MDP and an extended MDP for the simplicity of presentation."

It basically introduce an extended MDP that is not actually different in a meaningful way than the original MDP. All that to say at the end of the paragraph that both will be considered identical. What is the the point?
- Almost the whole page 6 is a very long explanation for the basic operation of collecting a tuple $(s,a,r,s')$ and adding it to the dataset. Why is such a long explanation needed here? What does the $\tau$ superscript mean? The same symbols are used with different subscripts/superscripts which makes the paper not clear because there is no definition of what adding these subscripts/superscripts mean.
- Equations 4.3 to 4.5 are introduced without any explanation on how it relates to the earlier introduced theory (Equations 3.2 to 3.4)

Minor comments:
- Below Equation 3.4, it is written "$(h,s,a) \in \Phi \times \mathcal S \times \mathcal A$". Why is $h \in \phi$ possible as $\phi$ seems to be defined three lines earlier as a function space?
summary_of_the_review: The paper is not clear
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper contains several novel, albeit highly theoretical results. It formalises a class of MDPs with nonlinear transitions that can be learned by neural networks; proposes an oracle-efficient algorithm to find the optimal policy, and shows that the convergence rate of this method does not depend on the (potentially exponentially large) eluder dimension, but only on the log-covering number.

The reviewers broadly agree that this paper makes a technically sound, substantial contribution. The also all worry that the presentation could be improved, and that the impact of this paper may suffer from this dense, highly technical presentation. 

The revision uploaded by the authors seems to have improved the presentation a bit, though, so that this paper can now be accepted.
justification_for_why_not_higher_score: See above.
justification_for_why_not_lower_score: See above.
Decision: Accept: poster