Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a novel algorithm, based on LSVI to perform best-policy identification uniformly across the state space. The method is based on a RHKS assumption on the reward and value functions and performs targeted 'exploration' based on the performance gaps defined as the difference between upper and lower bounds of the action value function. The authors study theoretically the performance of the algorithm in function of $\Gamma_k$, a property of the specific kernels used and give specific bounds for some families of frequently used kernels. Moreover, the authors perform an empirical evaluation on several domains, comparing AE-LSVI with algorithms from SOTA, explicitly showing the conditions under which this method outperforms the baselines.
strength_and_weaknesses: Strengths:
 - The authors study the interesting problem of best policy identification in episodic reinforcement learning
 - The authors propose a fairly simple algorithm, easy to implement and with performance guarantees
 - The sample complexity bound does not scale with the state and action space sizes
 - The authors perform a thorough empirical evaluation explicitly identifying the limitations of the algorithms and the settings in which it performs better than the baselines

Weaknesses:
- The central point of the algorithm is choosing states to sample from he generative model based on the perfomance gap, i.e. the difference between the upper and lower bounds on the V-function of the state. The authors should  cite other works that performs selection on similar metrics based on this uncertainty. For example, there is a large body of work in the best-arm identification literature that uses the difference between upper and lower bounds to select which arm to choose, [1], [2] etc.
- The paper does use a fairly common assumption from the literature, but nonetheless it should be more self contained. I would have expected to see a discussion on how restrictive is the RHKS assumption as well as a comparison of the guarantees provided non only with methods taking the same assumption but also with other method that make less or more limiting assumptions. For example, a comparison with methods that assume linearity of the reward and value functions would improve the clarity of the paper. 
- A bit more discussion on why the bound presented loses the dependency on the state and action space sizes might also improve the paper.  Especially when comparing with the algorithm presented in Cher et. al. 2019 at the end of Section 4 which also makes the RHKS assumption, has a dependency on $\Gamma_k$ but also on the state and action spaces.
- The algorithms adds an additional parameter $\beta_t$, fairly important since it is used to define the upper and lower bound on Q-values, central for the "exploration" method used in AE-LSVI. Unfortunately, no discussion on the selection of this hyperparameter is provided. The authors present all the results with the value 0.5 (why 0.5). Instead, an empirical evaluation of the effect off the value of $\beta_t$ is warranted.
- While I am mostly positive on the experimental section, I am surprised with the choice of DDQN as a baseline. DDQN was chosen as a SOTA method for online RL, but there are more advanced methods right now for online RL, especially it would have been beneficial to see other online RL methods that use uncertainty estimates just like AE-LSVI like [3] [4] or [5]. Any of them would make a better baseline then DDQN but especially [3] since it makes decisions also based on upper and lower bounds on Q.

[1] Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric, Sébastien Bubeck, Multi-Bandit Best Arm Identification, NeurIPS 2022

[2] Marta Soare, Alessandro Lazaric, Rémi Munos, Best-Arm Identification in Linear Bandits, NeurIPS 2014

[3] Ted Moskovitz, Jack Parker-Holder, Aldo Pacchiano, Michael Arbel, Michael I. Jordan, Tactical Optimism and Pessimism for Deep Reinforcement Learning

[4] Ian Osband, Charles Blundell, Alexander Pritzel, Benjamin Van Roy, Deep Exploration via Bootstrapped DQN

[5] Alberto Maria Metelli, Amarildo Likmeta, Marcello Restelli, Propagating Uncertainty in Reinforcement Learning via Wasserstein Barycenters

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and easy to follow. I would suggest to rewrite the title to contain "Best policy identification" instead of just "policy identification" as the former might be confused with "policy space identification" another branch of RL concerned with identifying the minimal space of policies containing the optimal (near-optimal) ones.

The related works is solid, it's almost exhaustive and clearly positions the paper in the literature. The only comments around it would be to include some previous work on best-arm identification (not only classical bandits) as it is fairly close to the setting considered in this paper (see also previous section of the review). Moreover I would suggest to the authors to consider moving this section after the preliminaries or even after the section 4, as the related works also compare AE-LSVI with other algorithms from the literature, and without reading section 2, 3 and 4 it might be hard for the reader to appreciate the differences.

The paper is fairly novel, it uses standard assumptions from the literature (RHKS) and similar ideas from the other research areas to define and analyze a novel algorithm.


summary_of_the_review: Overall I am positive about the paper. The issues I describe all all fairly minor and solvable. I would increase my score if my concerns are adequately addressed. (See previous sections for details)
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a policy search algorithm that combines kernelized LSTD with the "optimism in the face of uncertainty" approach, which is a well-known method in bandit algorithms. The paper analyzes the theoretical properties of the resulting algorithm and reports results on a number of simulated control environments.
strength_and_weaknesses: Strengths:
   - Despite being a combination of multi-decade-old ideas, the eventual algorithm is simple, solid, and novel.
   - The theoretical results are thorough and sufficiently informative, while being a corollary of existing work.
   - The experiments are comprehensive enough and the reported results support the central claim of the paper.

Weaknesses:
   - The baselines chosen for comparison are rather arbitrary and not state-of-the-art.
clarity,_quality,_novelty_and_reproducibility: The paper is written in a very clear language. This is a very high quality work with prominent novelty. The reported results are reproducible.
summary_of_the_review: Overall very solid work, which neatly combines the theory and practice of online policy search.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper is concerned with near-optimal policy identification in the generative model setting. The contributions of this paper includes:

(1) The development of the AE-LSVI algorithm for $\epsilon$-optimal identification;
(2) A concrete proposal of the algorithm based on the RKHS model;
(3) Establishment of the theoretical findings to justify the proposed algorithm;
(4) Empirical verification of the proposed algorithm. 
strength_and_weaknesses: The contributions and strengths of paper are listed above. Below, I list some points to discuss: 

1. Page 3. It was mentioned that the goal in this setting is to identify an $\epsilon$-optimal policy while minimizing the number of necessary episodes $T$. This differs from the standard setting on cumulative regret minimization. The paper would benefit from adding more motivations to justify such an objective. Is this objective commonly used in the generative model setting?

2. Under the generative model setting, the agent has access to a simulator that can be used for adaptive data generation. The optimal policy that maximizes the cumulative reward in simulators is not necessarily maximizing that in real applications, due to potential difference from simulator and real-world environments. Would it be better to consider the more realistic setting with sim-to-real gap?

3. Instead of obtaining $s_h^t$ according to Equation (12), we can alternatively define some uncertainty measure for the value and directly selects $s_h^t$ that minimizes the uncertainty. Would this procedure work?

4. While kernel methods enjoy nice theoretical properties, their empirical implementation requires tuning of the kernel bandwidth. What kernel functions did you choose in the numerical experiments? Are the results sensitive to the choice of the bandwidth? How would you suggest practioners to select this hyper-parameter? 

5. In continuous action setting, the author(s) proposed to first discretize the action space and then apply the proposed method. Can your methodology be extended to the continuous action setting? Alternatively, can we adaptively discretize the action space to improve the performance (see e.g., http://proceedings.mlr.press/v80/lee18b/lee18b.pdf; https://arxiv.org/pdf/2007.00717.pdf; https://openreview.net/pdf?id=rvKD3iqtBdk)? 

6. The current methodology and theory are developed under the episodic MDP setting with time-varying dynamics. Can these results be extended to time-homogeneous MDP models?
clarity,_quality,_novelty_and_reproducibility: The paper is clear and is of good quality. The proposed algorithms and the associated theoretical analysis are novel, to our knowledge. The implementation details are provided in the Appendix. Code is also provided in the supplementary materials. 
summary_of_the_review: The paper is well-written and studies an interesting research question. The proposed algorithm and the theoretical analysis are novel. I have some comments regarding the practical usage of the proposed method and the model setup. I hope the author(s) can address my concerns.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a novel active reinforcement learning algorithm based on a kernelized version of LSVI, which provably finds a near-optimal policy uniformly over the entire state space.
After reading each other's reviews and the authors' feedback, the reviewers agree that the paper studies an interesting problem and proposes a sound solution, which is analyzed both theoretically and empirically. The main weak point raised by the reviewers is the lack of competitive baselines in the experiments, which has been partly addressed by the authors through the addition of Bootstrapped DWN.
Overall, the paper has solid contributions and deserves to be published.
justification_for_why_not_lower_score: While the paper could also be accepted as a spotlight, I would not go below that level given the relevance of the contributions.
Decision: Accept: notable-top-5%