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: The authors consider reward-free reinforcement learning under general class of function approximation. They propose the RFO-LIVE algorithm, a reward-free version of the OLIVE algorithm by Jiang et al., 2017, for reward-free under minimal structural assumptions. In particular, the considered set of assumptions covers the previously studied settings of linear MDPs (Jin et al., 2020b), linear completeness (Zanette et al., 2020b), and low-rank MDPs with unknown representation (Modi et al., 2021). In particular, they show that previous assumptions made for the latter two settings are unnecessary for reward-free RL. Finally, they provide a lower bound showing that reward-free (and even reward-aware) exploration under linear completeness assumptions when the underlying features are unknown is intractable.
strengths_and_weaknesses: Contributions:
-Algorithm RFOlive an adaptation for reward-free exploration of the Olive algorithm by Jiang et al. (2017). Novelty: low; relevance: medium.
-Exploitability assumptions for linear completeness setting and reachability for low-rank MDPs are not necessary for reward-free exploration. Novelty: low;  relevance: high.
-Reward-free (and reward-aware) exploration with linear completeness assumptions and when the
underlying features are unknown is intractable. Novelty: medium, relevance: medium.

The paper is well-written. The proofs seem correct from what I read. Note that most of the technical argument used in the proofs of Theorem 1 and 2 seem to be adapted from Jin et al. 2021, see specific comments. I think characterizing the sample complexity of reward-free exploration for general function approximation is a valuable contribution, especially knowing which assumption is necessary or not. The improvements in terms of sample complexity over the previous work seem a bit incremental. But my main concern is that the proposed algorithms are computationally intractable. Indeed, usually, the interest of such computationally inefficient algorithm is to characterize the optimal rate for the sample complexity which seems not to be the case here.
questions: General comments:
-It would be interesting to compare clearly the obtained sample complexity for the proposed algorithms with the ones of previous work. Additionally, it could also be interesting to provide lower bounds for the different settings (particularly those of Corollary 2 and 4) and compare them to the obtained rates.
-

Specific comments: 
-L45: At this point it is not clear what is the set of constraints.
-L127: Do you have simple concrete examples of MPD and associated classes \cR and \cF which verify these two assumptions? 
-L160, Algorithm 1: It may be clearer to specify in the algorithm what you keep in memory from the online phase for the offline phase, i.e. (\pi^t,h^t,\cD^t).
-L186,(3): h_t instead of h.
-L200: Do you have an example where this assumption is verified?
-L235: Is there any lower bound for this setting to compare with? And how the obtained rate compare to the one in Zanette et al.(2020b).
-L267:  Can you discuss the differences between Q-type and V-type RFOlive, in partícular in terms of theoretical guarantees.
-L290: Can you provide a table with the different rates given the algorithm and the setting to ease the comparison with the previous baselines?
-L296:Can you explain why it 'significantly improves' over the previous bounds.
-L551:By realizability you mean that assumption 5 is verified?
-L558: At this point, it is difficult to follow the proof without reading one of Theorem 18 by Jin et al. 2021. And I think you should include this argument in your proof. 
-L581: A hat is missing.
-L597 Maybe you should precise the events.
limitations: Yes.
review_title: null

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 work studies different settings of reward free reinforcement learning under general function approximation, including linear MDPs, linear completeness, and low-rank MDPs. The main contributions are the release of exploitability or reachability assumptions in previous works. Moreover, it shows the intrinsic hardness of the RL problems under linear completeness assumptions with comparisons to low-rank ones.
strengths_and_weaknesses: Strengths:
1. The organization of this paper is clear and easy to read.
2. This work proposed provable algorithms for different settings without reachability/explorability assumptions that are necessary for previous works, which is a big improvement.

Weakness:
1. The results in Table.1 only show the difference in the settings/assumptions of different works, while lacking the comparisons of the sample complexity or other main results. Adding the comparisons of the main results may be more clear.
2. Although the main results show provable algorithms without reachability/explorability assumptions that are necessary for previous works,  the sample complexity bound is also worse in H as claimed in Line 238. It is confusing that if this is a tradeoff that releasing assumptions will lead to worse sample complexity or due to technical tools?


questions: 1. In Line 217, it mentioned that adapting Golf may lead to a sharper result. So why not directly adapt that state-of-art method?
2. Since I'm not so familiar with the literature on reward-free, why do we need two types of algorithms (Q and V)? what is the difference between them? Or, what are the advantages of them respectively. The motivation to have them is not introduced clearly.
limitations: This work already mentioned the limitations such as the computation cost of the proposed algorithms are still expensive.
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 studies reward-free RL with non-linear function approximation. They propose an extension to the OLIVE algorithm of Jiang et al. (called RFOlive) for which they establish polynomial sample complexity in relevant problem variables (using Bellman-eluder-dimension-based arguments).  As a positive side result, they show that the explorability or reachability assumptions used in prior works are actually not necessary for achieving polynomial sample complexity. As a negative result, they show that polynomial sample complexity in all relevant variables is impossible in the setting where linear completeness holds for unknown features (despite realizability). 
strengths_and_weaknesses: Strengths:
- The paper studies a relevant problem (RF RL with general function approximation) which was previously unaddressed
- The results are significant and they do not rely on strong assumptions
- The hardness result of Section 4 is significant and of independent interest
- The paper is well-written and easy to follow. All results are clearly stated (though they can be fully understood only by looking at the appendix)

Weaknesses:
- Novelty: it seems to me that the proposed algorithm is essentially a direct application of Olive (or its Q-type variant by Jin et al.) with the zero reward function. The authors mention in the introduction the RFOlive is "nontrivially adapted from its reward-aware counterpart", though it is not clear what are the novel algorithmic components here. Moreover, while Section 3.3 specifies what are some novel aspects in the analysis, it would be good to elaborate a little more on how much of the analysis is actually novel and how much is taken from prior works
- The proposed algorithm is computationally intractable as it explicitly maintains version spaces. Even worse, the V-type variant of RFOlive maintains explicitly a finite cover of the function class (which is of exponential size in the dimension). Therefore, there is no real practical impact
- No numerical result is presented (though, as a consequence of the previous point, it is not possible to do much beyond very toy problems)
questions: Overall, while there are some limitations, I think that the paper presents interesting and significant results. I am thus more inclined towards acceptance. Here a few comments/questions:

1. As stated above, I am quite puzzled about the novelty of this work (specifically of the algorithm and its analysis). I am not claiming that the paper is not novel, but rather that it was unclear whether it is sufficiently novel after reading it. This would be an important point to clarify in the rebuttal and in an updated version of the paper.

2. V-type RFOlive seems to be more complicated as an algorithm (eg it must build the cover of F explicitly) and has worse sample complexity (eg depending on K). What is its advantage over the Q-type variant?

3. The result for low-rank MDPs with unknown features (Corollary 4) is stated only for V-type RFOlive. Is it possible to have it also for the Q-type variant?

4. Theorem 5 is a little informal and not very clear. Does the fact that a polynomial sample complexity in all stated variables is impossible mean that, for any algorithm, there exists at least one instance where the sample complexity is exponential in at least one of those variables ? In that case, it should be clarified

Other minor comments:
- When first introducing the function class at line 107, it is not clear what it should model (and footnote 3 is confusing), though everything becomes clear later on. I would anticipate a comment on that.
- Line 147: the rightmost x_h should be a_h
- Line 252: "dateset"
limitations: Limitations have been properly discussed
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Reward-free RL is a well-studied RL setting where the agent must explore an unknown environment without access to the rewards, and then given an arbitrary number of reward functions, must propose a near-optimal policy for each of them. This work builds on results on reward-free RL in the linear function approximation setting and shows that reward-free RL is possible for general function classes (with bounded Bellman-Eluder dimension). 

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

Update: After reading the author's reply and other reviews, I would like to maintain my score of 7.
strengths_and_weaknesses: Strengths:
Both reward-free RL and RL with general function approximation are problems of much interest in the RL community. This work is the first to study the reward-free problem in the general function approximation setting. The results obtained (while not optimal) are likely close to the optimal rates. Several corollaries are given in various specific settings of interest specializing the results to these settings, and a lower bound is also given showing that in some settings (the linear completeness and unknown features setting) reward-free RL is not in general efficient. 

The algorithm is a modification of an existing algorithm (OLIVE) yet it is not a priori obvious how to extend OLIVE to the reward-free setting, and I believe the extension proposed in this work is technically interesting.  

Overall, I believe this work makes a fundamental contribution to the theory of RL and will be of much interest to the RL theory community. Furthermore, it is well-written and appears to be technically sound. 

I did not see any major weaknesses but had several minor questions and corrections:
- It is stated that “prior works require explorability/reachability assumptions, which, roughly speaking, assert that every direction in the feature space can be visited with sufficient probability. These assumptions are often not needed in reward-aware RL but suspected to be necessary for reward-free settings.” It is true that works like [Zanette et al., 2020] do require such assumptions, but other works on reward-free RL with linear function approximation (e.g. [Wang et al., 2020], [Wagenmaker et al., 2022]) do not require such assumptions. The statement above seems to imply the opposite—I believe this should be clarified. 
- Some more discussion on Q-type vs V-type would be helpful. It’s not entirely clear why we need to consider two separate settings unless the reader has seen them before. 
- In Section 3.1, perhaps reference Definition 6 or otherwise remind the reader what $\phi^{lc}$ corresponds to.
questions: It was not clear to me why the algorithm uses the difference function class (i.e. $\mathcal{F}^{on}$). Could the authors explain this? 
limitations: Limitations are discussed. No discussion is given on societal impact. While the work is primarily theoretical and may not have obvious immediate societal impact, it is contributing to the larger field of RL which does have practical impact. Given this, I would encourage the authors to consider what such impacts might be, and how negative impacts might be mitigated.
review_title: null

Meta-review: metareview: Despite a few concerns about the novelty of the paper (mostly from an algorithmic perspective), I think the investigation of the minimal structural assumptions for reward-free RL is interesting for the community. This work provides a first step in the direction of obtaining a better understanding about reward-free RL outside the tabular setting.
confidence: Certain
Decision: Accept