Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a new notion of coverability, and shows its sufficiency for efficient online reinforcement learning. This new notion is compared with existing concepts from both offline and online RL. For offline RL, the authors show other weaker notions of coverage are not sufficient for efficient exploration. For online RL, they show their notion are independent from existing complexity measures, including Bellman rank and Bellman-Eluder dimension, and provide a new complexity measure that unifies these notions. 
strength_and_weaknesses: Strength: 

1. The topic is important and the idea is novel. Both offline RL and online RL are important topics for the community and the paper serves as a bridge of the two formulations. In particular, the idea that the notion in offline RL can facilitate online exploration is novel and may serve as an inspiring point for future researches. 

2. The story is complete. The authors compare their notion with existing notations for both online and offline RL, which addresses the necessity and novelty of their findings. The example of block MDP is also a good point, which shows how the authors' findings can actually result in a sharper sample complexity, compared with previous works. 

Weakness:

1. Part of the technical contribution is limited, since the algorithm and some of the analysis are directly copied from existing works. However, it shouldn't be considered as a big problem since the paper itself is mainly focused on the analysis instead of the algorithm design, and the paper does show its own novelty in the regret analysis. 

clarity,_quality,_novelty_and_reproducibility: The overall writing is clear, easy to follow. I didn't read the entire appendix in detail and only checked the proofs of some main results, which is easy to understand and seems to be correct. 

A very small number of typos appear in the text, e.g., "ands" in page 1, "offline and offline", "can achieved" in page 2. There might be more in the later sections but overall the impact is minimal and doesn't affect the understanding of the paper. 
summary_of_the_review: The work is novel and provides impressive results, based on simple but inspiring observations. I would suggest it be accepted.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers a setting of RL where the learner has access to ofﬂine data, yet also has the ability to online interact with the environment. The main contribution of the paper is to show that under a data distribution with good coverage, we can enable sample-efficient online RL. The paper introduces a new notation, called coverability which is weaker than the concentrability coefficient in offline RL and shows that it is enough for sample-efficient online RL. In addition, the paper also shows (1) several weaker notions of coverage which are sufficient for ofﬂine RL, but insufficient for online RL; (2) existing complexity measures for online RL such as Bellman rank and Bellman-Eluder dimension are insufficient for sample-efficient online RL. 


strength_and_weaknesses: Strengths:
- The paper addresses an important setting of RL: online RL with access to ofﬂine data
- The paper is generally well written

Weaknesses:
- However, I have some concerns about the novelty of the main contribution of the paper.  A very recent result under review of ICLR 2023 [1] shows that under the Concentrability assumption as Definition 1 (similar to the coverability assumption as the paper proposed), it is enough to achieve an "optimal" offline RL, without any interaction with the environment. These results seem correct to me. Then, 
 - If we can access offline data and assume that offline data has good coverage as stated in Definition 2 (lower bound of Concentrability assumption), so do we really need the online RL?
 - If we really still need the online RL, then it seems that the coverability condition on offline data that the paper proposed is not enough weak to keep a sample-efficient online RL.    

[1] https://openreview.net/forum?id=ZsvWb6mJnMv&referrer=%5BReviewer%20Console%5D(%2Fgroup%3Fid%3DICLR.cc%2F2023%2FConference%2FReviewers%23assigned-papers)
clarity,_quality,_novelty_and_reproducibility: The paper is well written and the problem the paper considers is important and novel. 
summary_of_the_review: Due to my concerns about the main contributions of this paper, I am toward rejecting it.  If the authors can address my concern, I am willing to increase my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors have introduced the concept of coverability, and related it to the sample efficiency in the online reinforcement learning. This idea is very interesting and the paper is well written with detailed description of everything. 
strength_and_weaknesses: *Strengths*
- The paper is well written. 
- The authors have addressed a crucial challenge of sample efficiency in reinforcement learning and the paper is quite relevant to the community. 
- The authors have introduced the concept of coverability with taking motivation from the idea of concentrability from offline RL which is quite interesting. 

*Questions to Authors*

- It would have been nice to show the effect of coverability coefficient via empirical studies. 

- Is it possible to have coverability coefficient =0 ? 

- How difficult is it to construct the confidence sets in practice? Is the approach feasible? 

- Is it possible to extend this framework to continuous state-action spaces? 

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. Please refer to weakness section for specific questions. 
summary_of_the_review: N/A
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper established a new complexity measure for online RL with nonlinear function approximations based on the coverage conditions commonly studied in offline RL. Conceptually, this paper draws an interesting connection between online and offline RL. It also shows that the coverage condition is not captured by existing complexity notions such as the Bellman-Eluder dimension and therefore contributes new territories of provably solvable RL instances. I vote for acceptance of this paper.
justification_for_why_not_higher_score: N/A.
justification_for_why_not_lower_score: I believe this paper and the ideas it presents are of broad interest to the RL community at large.
Decision: Accept: notable-top-5%