Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a unified framework which encompasses both model-based and model-free MDP algorithms. The framework, Admissible Bellman Characterization, covers a wide range of MDPs. The key idea is to use decomposable estimation function which has decomposable sturctural properties for optimization-based exploration (which is also their algorithm). To measure the complexity of model class, they use the functional eluder dimension. 
strength_and_weaknesses: Strength:
1. The authors proposed a unified framework which covers a large section of MDPs, both model-free and model-based
2. The framework maintains the best-known sample complexity results for special instances.
3. They also propose a novel algorithm, OPtimization-based ExploRation with Approximation (OPERA), which maximizes the value function constrained in a small confidence region around the model minimizing the estimation function.

Weakness:
Although this framework improves the sample bounds, it is as generic as the existing framework, meaning the algorithms which were not covered in previous framework (such as those with state-action aggregation) are also not covered here.
clarity,_quality,_novelty_and_reproducibility: Good
summary_of_the_review: It is good paper, written quite well. It improves on the existing frameworks which could not preserve the sample complexity bounds.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a unified perspective and analysis for almost all of the existing sample efficient RL algorithms.
This notion is based on Admissible Bellman Characterisation, and provides an a bound in terms of the functional eluder dimension.
Together with this analysis, the authors present an algorithm OPERA, which really is a general form of optimism in the face of uncertainty.
While this algorithm is not necessarily practical (it may not be computable) it provides some general flavour of the types of results that might be possible.
strength_and_weaknesses: There are several things to like about the paper:
- The writing and paper structure are good, and give a good overview of the many lines of research in this area.
- The general analysis and flavour of the results are clear and concise. Take, for example, Theorem 12 as an example. This clearly highlights the main dependencies in the regret bound.
- The ABC class supersedes the many different notions of complexity, as outlined well in Figure 1.

There may be a few places where the paper falls down in terms of top-level impact:
- First, it feels like this work is really mostly consolidating/summarising threads of research that have been going on for a while in the eluder-dimension++ pieces of RL with generalization. This is valuable, but feels more "cleaning up" than forging new course.
- The OPERA algorithm is really more of a high-level principle than a practical algorithm. Thinking about how we can make scalable/practical algorithms is probably not just an "unnecessary complication" but I agree it is OK to leave this to future work in this conference paper.
- There is a *lot* of material to go through in reviewing this paper... so many theorems and definitions. This is great for clarity, since it allows a motivated reader to go through piece by piece, but there is a slight concern with *so many* pieces that it takes away from the "main thing".
clarity,_quality,_novelty_and_reproducibility: Overall, I think the paper scores very highly in clarity.
The quality, and reproducibility also appear to be solid... although I have not checked all steps in detail.

In terms of *novelty* I think the main contribution is the calm and coherent way of combining lots of existing perspectives, and rationalizing this treatment in one place.
This is definitely valuable, but I would not rate *novelty* as one of the main strengths.
summary_of_the_review: This paper collates many existing results in the OFU-RL literature with function approximation.
By revisiting the functional eluder dimension under the ABC condition, they show that OPERA algorithm provides a more unified perspective on statistically efficient reinforcement learning.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a general framework which unifies problem complexity measures with function approximation in the model-based and model-free lens for reinforcement learning.  In particular, the authors propose Admissible Bellman Characterization (ABC) class that subsumes many prior models for problem complexity in the prior literature.  The authors also provide a new algorithm, OPERA, achieving regret bounds that match or improve over the prior literature.

More concretely, the authors consider an MDP $(S,A,r,P,H)$ where $S$ is state space, $A$ the action space, $r$ the reward function and $P$ the global transition distribution, and $H$ the horizon.  Given access to a function class (representing either the transition kernel in model-based or the $Q$ function for model-free) typical algorithms come up with complexity measures of the function class and design algorithms with sublinear regret with respect to that complexity measure.  The main point of this paper is to present a unified complexity measure framework that includes all model-free and model-based RL classes, while simultaneously allowing a simple algorithm with sample efficiency guarantees.  To this lens, the authors make two several frameworks:
1. The authors propose a new framework called ABC that covers structural assumptions previously studied in model-free and model-based RL.  To some extent, the framework can be thought of as extending the Eluder Dimension to include (a) arbitrary coupling functions for measuring the error, (b) a discriminator function which characterizes the interaction between different hypotheses
2. Under the ABC framework the authors design an algorithm OPERA based on maximizing value function in a confidence region around model estimation - showing that the framework has sublinear regret guarantees.

## Questions
- What is the role of $\pi_{est}$ on page 8?

## Minor Comments
- FLAMBE is used to refer to both the model and the algorithm
- Value terms are swapped in regret definition on page 3
- Definition of $\pi_f(s)$ on bottom of page 3 has typo in it
strength_and_weaknesses: ## Strengths

1. The authors provide a novel problem complexity measure which subsumes several others which are studied in the literature.
2. The authors provide a simple algorithmic framework based on optimistic principle over uncertainty sets which achieves strong regret performance.

## Weaknesses

1. The authors include no discussion on the computational complexity of the algorithm.
2. There are no theoretical matching lower bounds (or discussion along this point)
3. The authors provide no empirical results of their algorithm's performance
4. The theoretical contributions and algorithm design seems like a straightforward extension of prior mechanisms with general function approximation techniques.  The novel algorithmic contributions could be highlighted more in the writing.

clarity,_quality,_novelty_and_reproducibility: ## Clarity

The paper is extremely well written and easy to follow, although a bit on the technical side. I listed some small comments on writing earlier up in the review. The two most useful clarifications which I think could help:
- Clarify the roll of $\pi_{est}$ on page 8
- Simplify section 3.2 (delaying some examples which readers could be familiar with in the literature) to allow for more discussion around ABC in Section 3.2

## Quality + Novelty

The paper provides novel theoretical contributions for developing an encompassing framework to understand the complexity of model-free and model-based reinforcement learning with function approximation.  The theoretical results then highlight the fact that the definition encompasses many well-studied notions of complexity in the literature.  They complement the new measure with a simple algorithm based on confidence sets which achieve strong regret guarantees (although no matching lower bounds are included).  
summary_of_the_review: The paper provides strong theoretical contributions for developing a framework which unifies model-based and model-free RL via their Admissible Bellman Characterization formulation - which subsumes most models in the literature for tractable RL with function approximation.  The paper is extremely well written, although very technical, but highlights the main differences and contributions between the paper and the related work. However, the paper offers no empirical results (or discussion on computational tractability of their proposed algorithm), although standard in the RL with function approximation literature.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers the problem of sample efficient RL with large state space that requires function approximation. It defines a new class of Admissible Bellman Characterization (ABC) that includes existing structural characterization, such as Bellman Eluder and Bilinear Classes, as special cases. The paper also introduces OPERA, an optimistic under certain constraint set algorithm, for efficient exploration. It provides a regret bound that is proportional to $\sqrt{T dim_{FE} }$, where $dim_{FE}$ is the introduced functional Eluder dimension.

While reading this paper, I was wondering whether there is any interesting class of MDPs that is within ABC but is not already captured with one of the existing characterizations? The paper might have already answered it and I just missed it. But if not, it would be good to discuss it.

Overall, all reviewers agree that this is a good paper. The ABC class encompasses many other previous results. The paper provides an algorithm with a good regret guarantee and is written clearly. I recommend the acceptance of this paper.
justification_for_why_not_higher_score: The results are quite technical, and are mostly of interest to a subset of RL theory researchers. Moreover, it does not seem that the results are breaking new grounds that everyone in the community should be immediately aware of. They are important, but as far as I can say, are mostly technical refinements of existing concepts.
justification_for_why_not_lower_score: This is a solid paper with three 8s.
Decision: Accept: notable-top-25%