Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper presents a model-based reinforcement learning algorithms based on the optimism in the face of uncertainty. First of all, the algorithm CBOO is constructed based on Bayesian credible region. However, CBOO is difficult to use in practice and therefore, the authors apply Lagrangian relaxation and posterior sampling to construct practical algorithm. Then, the authors provide regret analysis and conditions for various model setting. Finally, the authors discuss the optimization of the BOO.
strengths_and_weaknesses: **Strengths**:

The proposed algorithm is a general algorithm for various model classes. In addition, the authors provide regret analysis to support the proposed algorithm.

**Weakness**:

1. Related work.

There are many model-based RL algorithms in finite MDPs. However, this paper presents only a very brief introduction to the related work. Because BOO can be reduced to finite MDPs, comparisons with previous works would be very helpful for understanding (e.g. connections between Theorem 5.1 in this paper and regret analysis in previous work)

2. Clarity

In this paper, notations are very confused. For example, $M$ is used to express MDP and to define covering number. Also, there is no definition of $\mathcal{X}$ in the paper. Finally, what is the definition of model – only transition, or only policy, or both? It is very confusing because there are no connection between $\mathcal{X}$, $\mathcal{F}$ and notations in MDP.

3. Implementation

It is not clear how to implement practical algorithm. It would be good if the authors could suggest at least the algorithms for models in Table 1. (how to compute & update posterior, how to sample MDPs from posterior, how to compute $\arg\max_\pi$, etc.)

questions: 1. This paper seems to deal with frequentist RL problem. But the authors introduce the definition of Bayesian regret in preliminaries. This confuses me if I'm understanding correctly. Would you clarify this part?

2. Many previous frequentist model-based RL algorithms also uses similar concept with Bayesian credible region. For example, in [1], UCRL2 also introduces ‘plausible MDPs’ $\mathcal{M}_k$, where true MDP $M$ is in $\mathcal{M}_k$ with high probability $1-\delta$. Then, UCRL2 choose optimistic MDP $\tilde{M}_k$ among these plausible MDPs. I would like to know the main difference between BOO and previous model-based RL algorithms in finite MDP setting. It will be very helpful for understanding this paper.

3. How can we construct Algorithm 4 in practice? In my opinion, Algorithm 2 is nothing new and already well-known part. However, as the authors mentioned in Section 4.1, obtaining optimistic MDP (from credible region), is not trivial. Previous model-based RL algorithms have focused on how to make it possible in practice. Then, how can we construct a practical OFU algorithm based on Algorithm 4?

4. In conclusion section, the authors claimed BOO enjoys sublinear regret. Where can we know that the regret is sublinear? In Theorem 5.1, (7) is the regret bound for the best $v$. But, the order of $K$ is $1+\text{(some positive)}\ge 1$: as the number of episode increases, the regret bounds exponentially increases. It looks too weird to me. Would you please correct my misunderstanding?

[1] Auer, Peter, Thomas Jaksch, and Ronald Ortner. "Near-optimal regret bounds for reinforcement learning." NIPS 2008.

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new model-based RL that exploits the principle of optimism in the face of uncertainty (OFU). The proposed algorithm, Bayesian optimistic optimization (BOO) is shown to be sample-efficient and less computationally expensive than previous Bayes-adaptive MDP methods. The paper also provide theoretical analysis to show that the algorithm has a sublinear regret for many model classes. 
strengths_and_weaknesses: Strength:
- Principled method to integrate OFU into MBRL. 
- Theoretical analysis showing a sublinear regret
- An optimization based on the natural gradient and entropy
regularization

Weakness:
- No empirical results
- Lacking discussions on related work of OFU on Batesian BMRL.
questions: See below
limitations: 
The paper proposes an interesting idea to combine OFU into MBRL. Constructing an uncertainty constraint is not new in MBRL. The step-by-step derivation from start to the final algorithm CBOO is very clear and easy to follow. The use of Lagrangian Relaxation of CBOO is sensible to exploit uncertainty in making decisions. I was wondering how this is different from adding UCB, ie. probably the closest work is [1]. Does it lead to a totally different behavior for optimization/online planning? Can the authors also comment or discuss about your approach in comparisons to previous work that already introduced uncertainty bonus to Bayes-Adaptive MDP?

The theoretical result reported in Theorem 4.1 is interesting. Can the authors provide a bit of insights about it, i.e. on why the variance is at least m/2 is good thing for RL?

It is also very interesting to see the authors provided practical optimization aspects for the proposed algorithm. It would be very interesting if this can be realized with empirical results.

[1] Arthur Guez, Nicolas Heess, David Silver, Peter Dayan:
Bayes-Adaptive Simulation-based Search with Value Function Approximation. NIPS 2014: 451-459
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers the exploration-exploitation tradeoff in reinforcement learning and develops a new algorithm rooted in the "optimisim in the face of uncertainty" principle. The paper starts from a Bayesian perspective where the policy is selected optimistically w.r.t. a credible, high-probability region of the model posterior. It then develops a lagrangian relaxation (BOO) and provides a regret bound that is sublinear depending on a schedule for the Lagrange multiplier and novel upper-bounds for the distributional eluder dimension. The paper also shows that BOO can be approximated by optimizing over samples from the posterior and, based on that, developes a practical algorithm for parametric models based on the reinforce trick applied to the model's stochasticity. It also extends this methods with the natural policy gradient. The main paper does not provide any experimental evaluation, though a small-scale study is included in the appendix.
strengths_and_weaknesses: The paper investigates the relevant topic of efficient exploration in reinforcement learning. It provides novel regret bounds. As far as I can tell the theoretical analysis is rigorous and presents an interesting perspective on how to side-step defining explicit confidence regions for the model. The main limitation, which is also discussed in the paper, is that this comes at the cost of having to manually specify a Lagrange multiplier to trade-off model-likelihood v.s. gained value. While the paper provides regret bounds for fixed schedules that depend on the model-class, without an adaptive selection this severely limits the usefullness of the approach.

The paper tries to cover both the theoretical contribution and the practical question of how to optimize it. While this is commendable in general, in this case experiments are banished to the appendix. In it's current form, imho anything beyond Theorem 6.1 does not add significant value, since empirical concerns like entropy-regularization would also require empirical evaluation. The current experiments in the appendix lack significant details, but are limited to toy systems and do not seem to cover any results from Sec. 6.
questions: Could you summarize what you view as the main technical novelties in the derivations of the regret bound?

It seems to me that the policy gradient in (8) would, like standard reinforce, yield high-variance results for close-to-detministic models as the gradient of the log-probability becomes very steep. Usually that is "resolved" by adding an entropy bonus for the policy, but this seems unreasonable for the model. How do you deal with this in practice? 

The Related work section is currently a bit sparse and should be expanded. Below are some recent papers on OFU that come to mind, it would probably be good to discuss them in relation to the current paper.
- Chowdhury et. al, "Online Learning in Kernelized Markov Decision Processes", AISTATS, 2019
- Kakade et. al, "Information theoretic regret bounds for online nonlinear control", NeurIPS 2020
- Curi et. al., Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning, NeurIPS 2020
limitations: For the theoretical part are discussed throughout the paper, but not for Sec. 6
review_title: null

Meta-review: metareview: The paper presents a new model-based approach based on optimism in the face of uncertainty.
After reading each other's reviews and the authors' feedback, most of the reviewers' concerns were solved and the reviewers agree that this paper deserves publication.
However, while preparing the final version of their paper, the authors have to consider the reviewers' suggestions and in particular, they are expected to extend the related work discussion and move some of the experimental results from the appendix to the main paper.
confidence: Less certain
Decision: Accept