Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:

The paper claims to study the sample efficiency in policy optimization with general function approximation. Specifically, the authors propose an algorithm with transition model approximation and analyze the regret when adopting RKHS or function classes with bounded Eluder dimension. The results also apply to neural networks in the NTK regime.

-----------------------------------------------------------------------------------------

Reasons for score:

The theoretical understanding of RL with function approximation is an important issue. It is nice to see that the paper provides a wide-ranging discussion under this topic. My major concerns are about the novelty and clarity. The paper investigates many interesting scenarios, but disappointingly, none of them is satisfyingly addressed.

-----------------------------------------------------------------------------------------

Pros:
* The paper goes beyond tabular MDP and finite-dimensional linear function setting. The use of RKHS and Eluder dimension makes the results more general.
* The paper connects reinforcement learning with neural network and attempts to provide a unified theoretical explanation for the empirical successes in deep RL.

-----------------------------------------------------------------------------------------

Cons:
* In introduction, the authors claim to study a policy-based approach but their algorithm turns out to be a model-based one.
* The paper seems only a combination of Cai et al. (2019) and Ayoub et at. (2020) using RKHS and Eluder dimension techniques. Admittedly, the extension needs some work, however, the results do not provide much more insights compared with Cai et al. (2019).
* Assumption 4.2 is too restrictive. It assumes the eigenvalues of kernel to decay exponentially fast. A discussion of power law spectral decay would definitely improve the quality of the paper. In Assumption 4.6, it is also unclear why exponential spectral decay is a reasonable assumption on NTK.
The authors refer to Srinivas et al. (2019) and Yang & Salman (2019) to justify their assumptions. However, it seems to the reviewer that Srinivas et al. (2019) considers all finite spectrum, exponential spectral decay and power law spectral decay. Also, Theorem 3.1 in Yang & Salman (2019) shows a power law for NTK and does not support Assumption 4.6.
review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Summary:**

This paper proves a regret bound for an optimistic variant of a policy optimization algorithm in an advsersarial reward setting. The paper extends prior work in this setting by considering function classes with bounded Eluder dimension instead of linear functions. This yields guarantees for a kernel-based variant of the algorithm (which also apply to neural kernels like the NTK).

--------------------------------------------------------------------

**Strengths:**

1. More general than prior work. The main strength of this paper is to extend the work of Cai et al. (2019) beyond the Linear MDP setting to one with a kernelized transition matrix. This essentially requires introducing some results based on the Eluder dimension from Russo and Van Roy (2014). The paper helps to fill out this line of research by showing that the algorithm from Cai et al. (2019) does indeed work when the linear MDP is replaced by a kernelized one.
2. The proofs seem to be correct.

--------------------------------------------------------------------

**Weaknesses:**

1. Setting seems unrealistic. The paper assumes that the *entire reward function* is revealed after each episode rather than only seeing the rewards at the visited states. This is integral to the algorithm since this reward function is then queried at new state, action pairs. I understand that this allows for adversarial reward functions and is the same assumption from Cai et al. (2019), but it seems unrealistic and unmotivated. I cannot think of a problem where the *entire reward function* would be revealed at the end of each episode, and without this assumption the entire algorithm and argument seem to break down.
2. Calling this algorithm policy optimization seems misleading. The algorithm requires using the kernel-based approximator to learn not just a model, but an entire confidence set over models. In the usual RL nomenclature this would seem to be a model-based algorithm. While the policy is not simply attained by planning in the learned model, having to learn these models seems to make the algorithm indeed model-based. This would not be so important except a major motivation for the paper in the abstract and intro is to provide guarantees for model-free policy optimization algorithms like the policy gradient algorithms that are often used in practice. This motivation does not align with the algorithm the paper is actually analyzing.
3. The main assumption is not clearly explained. The main assumption in the paper is that the transition kernel is in some RKHS, but the paper never explains what this assumption means and which sorts of MDPs it may apply to. It is more general than the Linear MDP, but how much more general? Moreover, the introduction makes it sound like the function approximation assumption is merely for the policy class, but in fact the approximator must be able to represent the entire transition kernel, which is potentially much more complicated. 
4. Novelty. To me the paper is only an incremental improvement over the results of Cai et al. (2019). Specifically, extending results from a linear setting to a kernel setting provides a technical challenge, but it is not clear how much insight is gained. The main result follows quickly from combining the results on Eluder dimension from Russo and Van Roy (2014) with thos of Cai et al. (2019). 
5. Algorithm seems computationally infeasible. The algorithm requires maximizing an integral over the entire state space against over a set of measures defined by a confidence set over models in the RKHS at every step. The paper argues that the algorithm can be implemented with supervised learning oracles, but having to solve several supervised learning problems at each step of training over all historical data seems quite inefficient. In short, this is not an algorithm that a practitioner would attempt to implement.

--------------------------------------------------------------------

**Recommendation:**

I recommend to reject this paper, and gave it a score of 4. While the paper is a logical extension of some prior work, I am not convinced of the usefulness of the setting or algorithm proposed.

If the authors can provide better motivation for the setting, novelty, and practical value of the contribution, I would consider raising my score.
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper propose a novel policy optimization algorithm that allows general function approximation (i.e., kernel function approximation, neural function approximation) that go beyond linear approximation, the algorithm achieves exploration by absorbing optimism into policy evaluation. An \sqrt{T} regret bound of the proposed algorithm is obtained.

Overall, this paper is very well-written, the problem is well-motivated, and the claims and proofs looks solid.
review_title: Recommendation to Accept

final_score: rating: 7: Good paper, accept
review_content: The paper proposes an optimistic policy optimization algorithm. It is theoretically shown that the algorithm has sublinear regret for multiple model classes such as kernel function and NTK. The policy update rule also allows the algorithm to have sublinear regret for  adversarial reward function. The technique for analyzing nonparametric model classes can potentially be extended to other reinforcement learning algorithms based on optimism.

While the algorithm itself is neat and clean, the paragraph describing its implementation is not very rigorous. In particular, how is Line 13 computed? Note that for general value function approximation, the state space is usually large (or even infinite).  If I understand correctly, there is no assumption about the structure of Q-function in this paper. How is the Q-function even stored, or parameterized? 

A similar question is that, the last few sentences before Sec 4 says "it suffices to solve a least-square regression problem". Does it mean that $Q_h^k(\cdot\mid\cdot)$ is computed by doing a regression problem where the target is r+clamp...? If this is the case, can the Q-function be solved exactly? Can the algorithm work for the case where the regression error is small but not zero?

It seems to me that the analysis for general function class is different to those for kernel function and NTK, so I'm wondering that are there any upper/lower bounds for the Eluder dimension of the two non-parametric classes described in this paper? Besides that, the regret upper bound given by Theorem 4.3 and 4.7 depends on parameter $\gamma$. In what scenario the parameter $\gamma$ is lower bounded by some constant?

Minor issue:
- In Eq. (3.1), Page 3: should the policy be $\pi_h^k(a\mid s)=\frac{\exp(E_h^k(s,a))}{\sum \exp(E_h^k(s,a))}$?

Overall, the results are solid and interesting. Therefore I would recommend a acceptance.
review_title: Solid theoretical results on policy optimization with function approximation

Meta-review: While the reviewers appreciated the aim of the work, they found the technical contribution to be too incremental to be of sufficient interest and the exploration of the problem and its significance to be incomplete in the paper's current state.
Decision: Reject