On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL
Authors: Jinglin Chen
Aditya Modi
Akshay Krishnamurthy
Nan Jiang
Alekh Agarwal
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement learning
reward-free exploration
sample complexity analysis
general non-linear function approximation

Abstract: We study reward-free reinforcement learning (RL) under general non-linear function approximation, and establish sample efficiency and hardness results under various standard structural assumptions. On the positive side, we propose the RFOLIVE (Reward-Free OLIVE) algorithm for sample-efficient reward-free exploration under minimal structural assumptions, which 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). Our analyses indicate that the explorability or reachability assumptions, previously made for the latter two settings, are not necessary statistically for reward-free exploration. On the negative side, we provide a statistical hardness result for both reward-free and reward-aware exploration under linear completeness assumptions when the underlying features are unknown, showing an exponential separation between low-rank and linear completeness settings.

On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL
Jinglin Chen *
Aditya Modi Microsoft admodi @umi ch,
Department of Computer Science
University of Illinois Ahhana-Chaamaigh
Langlin@eilinee edu
Akshay Krishnamurthy
Nan Jiang
Microsoft Research
Department of Computer Science
akshaykromicromm wtwp://frrrrrrooooooooooooooo... com
University of Illinois Urbana- Urbana-Champaign Champaign
edu
Alekh Agarwal Google Research al Llethagarva1@@goglee.coo
Abstract
We study reward-free reinforcement learning (RL) under general non-linear func- tion approximation, and establish sample efficiency and hardness results under various standard structural assumptions. On the positive side, we propose the RFO- LIVE (Reward-Free OLIVE) algorithm for sample-efficient reward-free exploration under minimal structural assumptions, which 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 al., 2021). Our analyses indicate that the explorability or reachability assumptions, previously made for the latter two settings, are not necessary statistically for reward-free ffre-ffee exploration. On the negative side, we provide a statistical hardness result for both reward-fre and reward-awan exploration under linear completeness assumptions when the underlying features are unknown, showing an exponential separation between low-rank and linear completeness settings.
Introduction
Designing a reward function which faithfully captures the task of interest remains central practical hurdle reinforcement learning (RL) upplications. address this, a series recent works (Jin et al., 2020a; Zhang et al., 2020b; Wang et al., 2020a; Zanette et al., 2020b; Qiu et al., 2021) investigate the problem of reward-free exploration, where the agent initially interacts with its environment to collect experience ("online phase"), that enables it to perform offline learning of near optimal policies for any reward function from potentially pre-specified class ("offline phase"). Reward free exploration also provides basic form of multitask RL, enabling zero-shot generalization, across diverse rewards, and provides a useful primitive in tasks such as representation learning (Agarwal al., 2020; Modi al., 2021). So far, most of the study of reward-free RL has focused on tabular and linear function approximation settings, in sharp contrast with the literature on reward-aware RI,
Equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Setting
Reference
Linear MDP
Wang et al. (2020a)
2
Linear completeness + explorability
Zanette et al. (2020b)
3
Completeness + Q-type B-E dimension
Theorem
4
Completeness +, V-type B-E dimension + small |A|
Theorem 3
5
Low-rank MDP (o* ② small |A| + reachability
Modi et al. (2021)
Linear completeness (ø* E +) + small |A| reward-aware
6
Theorem (intractable)
+ explorability reachability + generative model
Table 1: Summary of results and comparisons most closely related works in reward-free exploration. Blue arrows represent implication (A - B means B is a consequence of and hence weaker condition than A), and the red assumptions are what prior works need that are avoided by us. For linear settings, the true feature o is assumed known unless otherwise specified (e.g., in Rows 5 & o² is unknown but belongs (Jin et al., 2021). Row 6 has many assumptions, which make it strong since it is negative result. The detailed comparisons of existing sample complexity rates and our corollaries can be found in Appendix A.
feature class 4). "B-E" stands for (low) Bellman Eluder dimension
where abstract structural conditions identify when general function approximation can used in a provably sample-efficient manner (Jiang et al., 2017: Jin et al., 2021; Du et al., 2021).
In this paper, we seek bridge this gap and undertake systematic study of reward-free RL in model-free setting with general function approximation. We devise an algorithm, RFOLIVE, which is non-trivially adapted from reward-aware counterpart (Jiang et al., 2017), and provide polynomial sample complexity guarantees under general conditions that significantly relax the assumptions needed by prior reward-free RL works. Our results produce both algorithmic contributions and important insights about the tractability of reward- free RL, as we summarize below (see also Table 1).
Algorithmic contribution: beyond linearity A unique challenge in reward-free RL is that the agent must exhaustively explore the environment during the online phase, since it does not know which states will be rewarding in the offline phase. A natural idea tackle this challenge is to deploy reward-aware RL. "base algorithm" with the O reward function, since this algorithm must explore to certify that there is indeed no reward. Prior works adopt this idea with optimistic value-iteration (VI) approaches, which use proxy reward functions to drive the agent to new states. However these optimistic methods rely heavily on linearity assumptions to construct the proxy reward, and it is difficult to extend them to general function approximation. Instead of using optimistic VI, our basic building block is the OLIVE² algorithm of Jiang et al. (2017). constraint- constraint-gathering and elimination algorithm that is a central workhorse for reward-aware RL with general function approximation In the online phase of RFOLIVE, we run this algorithm with the reward function, and we save the set of constraints gathered (in the form of separate datasets) for use in the offline phase.
Algorithmic contribution: novel offfine module Prior works for reward-free RL typically use regression approaches (Ernst et al., 2005; Chen and Jiang, 2019; Jin et al., 2020b) in the offline phase, c.g., FQI (Modi et al., 2021: Zanette et al.. 2020b), or optimistic variants (Zhang et al., 2020b; Wang et al., 2020a). In the offline phase of RFOLIVE, rather than relying on regression, we enforce the constraints gathered in the online phase, which amounts eliminating functions that have large average Bellman errors on state- naate-distributions visited in the online phase. This generic elimination scheme does not rely on tabular or linear structures and allows us move beyond these assumptions to obtain reward-free frree guarantees in much more general settings.
positive results The major assumptions that enable sample complexity guarantees are Bellmman-completness (A (Assumption 2) and low Bellman Eluder dimension (Definition 5 and Definition 7); see Rows 3 and 4 in Table These conditions significantly relax prior assumptions in the more restricted settings. Furthermore, prior works in the linear completeness and low-rank MDP settings require explorabiltyyrraccabllt assumptions (Zanette al., 2020b; Modi et al., 2021),
Implications:
We use the Q-type and V-type versions of OLIVE from Jin et al. (2021) as their structural assumption of low Bellman Eluder dimension subsumes the low Bellman rank assumption in Jiang et al. (2017) (see Proposition 3).

---

which, roughly speaking, assert that every direction in the state-action feature space can be visited with sufficient probability. These assumptions are often not needed in reward-aware RL but suspected to be necessary for model-free reward-free settings. Our results do not depend on such assumptions, showing that they are not necessary for sample-efficient reward-free exploration either.
negative results We develop lower bounds, showing that some of the structural assumptions made here are not easily relaxed further. While the settings of linear completeness with known features (Row 3), and low-rank MDPs with unknown features (Row 4) are both independently tractable, we show hardness result against learning under linear completeness when the features are unknown, even under few additional assumptions (Row 6).
Implications:
Taken together, our results take significant step in bridging the sizeable gap in our understanding of reward-aware and reward-free settings and bring the two closer to an equal footing.
Related work In recent years, we have seen a wide range of results for reward-aware RL under general function approximation (Jiang et al., 2017; Dann et al., 2018; Sun et al., 2019; Wang et al., 2020c; Jin et al., 2021; Du et al., 2021). These works develop statistically efficient algorithms using structural assumptions the function class. Despite their generality, trivial extension to the reward-free setting incurs an undesirable linear dependence on the size of the reward class.
There also exists a line of research on reward-free ffee RL in various settings: tabular MDPs (Jin et al., 2020a; Zhang et al., 2020b; Kaufmann et al., 2021; Ménard et al., 2021; Yin and Wang. 2021; Wu et al. 2022), MDPs with the linear structure (Wang et al., 2020a; Zhang et al., 2021: Zanette et al., 2020b; Huang et al., 2021; Wagenmaker et al., 2022), kernel MDPs (Qiu et al., 2021), block/low-rank MDPs (Misra et al., 2020; Agarwal et al., 2020; Modi et al., 2021), and multi-agent settings (Bai and Jin, 2020; Liu et al., 2021). Many of these settings can be subsumed by our more general setup.
Our offline module uses average Bellman error constraints, which is related to a line of work in offline RL (Xie and Jiang, 2020; Jiang and Huang. 2020; Chen and Jiang, 2022: Zanette and Wainwright, 2022). However, there is only one dataset in the standard offline RL setting, and these works form multiple average Bellman error constraints using an additional helper class for reweighting, and need to impose additional realizabilityy or even completeness- type assumptions on such class. In contrast, we naturally collect multiple datasets in the online phase, so we do not require a parametric class for reweighting during offline learning.
2 Preliminaries
Markov Decision Processes (MDPs) We consider a finite-horizon episodic Markov decision process (MDP) defined as M = A, where X' is the state space, A is the action space, P = Pn-1) with Pa : X x A A(X) is the transition dynamics, and H is the number of timesteps in each episode. If the number of actions is finite, we denote the cardinality |A] by K. In each episode, an agent generates trajectory T (xo, Gp, -1,--. HH 0,,,,, by taking a sequence of actions ap...., 4H-1, where 2n is a fixed starting state and -h-1 ~ Pa Th, an). For simplicity, we will use auy denote ai, aj and use the notation [M] to refer to 10 H - 1}. We use the notation क to denote a collection of H (deterministic) policy functions
(To...., -I- 1), where Th X - A. For any h E [H] with h > h, we use the notation JAA to denote the policies (Т), Th+1 ..... T.). For any policy π and reward function' R -Ro....Rp-1. with R2 X x A- + (0, 1]. we define the policy-specifie action-value (or
Q-) function as (2, = Ex H-1 R(* aN) | F = x, an = a) and state-valke value function as (x) = F2 1= (I. an) In = x, ag ~ T). We also use o = (T)) to denote the expected return of policy и. For any fixed reward function R, there exists a policy क such that " (x (x: sup, V7, (2:) for all X and i E [HT], where v7 denotes the optimal expected return under R. We use Th to denote the reward-dependent Bellman operator: VSK+1 E AAA, (T fn+1)xz,)) a) == (I, a) + E [max,'eA fx+1 (a', .a) | x' ~ P= 2, a)] and similarly define Th for the operator with zero reward. The optimal action-value function (under reward R) Qi satisfies the Bellman optimality equation QRA = T, QRRKII Vh E [M]
We consider deterministic reward and initial state for simplicity. Our results easily extend to stochastic versions.
3

---

Reward-free RL with function approximation We study reward-free free RL with value function approximation. wherein, the agent is given a function class F x .... Fu-1 where Fn : & x A- 1- H H-h-11, 1],
vh [H]* Without loss of generality, we assume 0 E Fr. Vh E [H] and fn 0, vf F. For any f E F, we use Vr,1 to denote its induced state-value function, i.e., (I,A(a) max, Jn (ar, a) and ạf (2) as its greedy policy, i.e., (z)) = argmax, (n a). When
these functions take 24 as input and there is no confusion, we may drop the subscript and use (I(TT) and (x()))
In reward-free RL, the agent is given access reward class R. but the specific reward function is only selected after the agent finishes interacting with the environment. Specifically, the agent operates in two phases: an online phase where explores the given MDP M to collect dataset of trajectories D without the reward information, and an offline phase, where it uses the collected dataset D to optimize for any revealed reward function R R.
Our goal is to investigate the statistical efficiency of reward-free RL. with general non-linear function approximation: how many trajectories does the agent need collect in the online phase such that in the offline phase, with probability at least 1 - 6, for any R E R, it can compute a near-optimal policy R satisfying " 2 R s? We measure the statistical efficiency in terms of the structural complexity of function class F, reward class R. horizon H, accuracy e and failure probability d.
As for expressivity assumptions, we assume the function class F is realizable and complete. Realiz- ability requires that the optimal function Q3 belongs to the seward-appended class F + R, which is natural in the reward-free setting where the agent uses F to capture reward-independent information. Completeness requires that the Bellman backups of and Fu+1 + Ru+1 belong to Fr. and additionally that the Bellman backup of Fu+1 Fn+1 belongs Fr, Fi-
Assumption 1 (Realizability of the function class). We assume VR E R. h E [M], Qi, E Fn. + Ra. where Fi. + RA = {fr + RA fn E FrJ.
Assumption 2 (Completeness), We assume Yh E [H]. FR41, (F RA+1) S Fn and Th (F Fr+11 Fr - Fhi where Fr - Fr = (fh Sh fIr EF).
Next we define the covering number, which measures the statistical capacities of function classes. Definition (E-covering number, e.g., Wainwright (2019)). We use NNx()) to denote the E-covering number of a set F Fu Fo.... x FH-1 under metric o(f.f") = max Il. f% oo for f. f F. We define it as ~x(E)) min Fowerl such that Foover S F fnr any f F, there exists f E Feover that satisfies of f') S e. For the reward class R, (R(s) is defined in the same way.
Finally,
guarantees depend Bellman Eluder (BE) dimensions-
are structural proper- we will need the following definitions (see
ties of the MDP that enable sample-efficient exploration- -ee Russo and Van Roy, 2013; Jin et al., 2021) which the later definitions of BE dimensions will build on. Definition 2 (e-independence between distributions). Let J be a function class defined on some space X', and p,,...,,M, be probability measures over X'. We say v is E-independent of { Vi=ı W.r.l. F' ff F' such that v (E (fT)2 Ss, s, but [/ > Definition 3 (Distributional Eluder (DE) dimension). Let J be a functioon class defined on some space X', and I" be a family of probability measures over X". The DE dimension dao(F', ,I',)) is the length of the longest sequence {pr)- I s.t. Ee' 2 E where Pt is E' e'-independent of (p:};=1,vt vi=ii. 1,....... n.
We also introduce the notation D,= = (DeH)) where Dy,, denotes the collection of all possible roll-in distributions at the h-th step generated by x for some f E F. Formally, Dy == (T) Her where d (z, a) = xx, [ax, = an = a) is the state-action occupancy measure.
3 RFOLIVE algorithm and results
In this section, we describe our main algorithm RFOLIVE, reward-free variant of OLIVE (Jiang et al., 2017; Jin et al., 2021). The algorithmic template for RFOLIVE is shown in the pseudocode
*Since is natural to use F to capture the reward wewrrdiiddeeedeent component (Assumption 1) in our reward-free free setting, we assume Fi, is upper bounded by H - h 1. We include the negative range to simplify the discussions for various instantiations. Our main results also hold if we assume Fa : X A + [0, H h - 1].

---

(Algorithm 1) and it can be instantiated with both Q-type and V-type versions of OLIVE from Jin al. (2021). the pseudocode, we use O placeholder for the respective Q/V-type definitions. For clarity, we will describe the Q-type R FOLIVE algorithm and its results in Section 3.1 and then state the differences for the V-type version and corresponding results in Section 3.2.
Before introducing our algorithm, we define the following average Bellman error:
Definition (Average Bellman error). We denote en as the average Bellman error under reward R:
E (F, h) E (Fn an) Rí (2h, an. Vj (z+++1) 00:h-1 n, a, x
As shorthand, we use (S, h, E (f. to represent the Q-type average Bellman error and (f. h)) (f. म. f. h) represent the V-rype average Bellman error (Jin et al., 2021). We use 8 represent the average Bellman errors under 0 reward.
Algorithm RFOLIVE (FE,0) Reward-Free OLIVE
Online phase, no reward information.
1: Set Eactv; Eelim, a Relim according to Q-type/V-type and construct Fon = =F
2: Initialize j < Fon (Q-type) J + Zon. where Zon is an (εelim/ (ecim/64)-covee of Fon (V-type).
3: for /. 0, 1, .... do
4: Choose policy n² ft, where f argmax (2(2)))
5: Collect Platv trajectories {(10) (f) (1)
ag ..... 1- 10-1,aH--1 1-1) mer by following x' for all h E [M]
(2) (1)
and form estimates (J', x x², h) for each [#]] via Eq. (1),
6:
if Σ (f'', ,', h) I HEW then Set and exit the loop.
7:
8:
end if
9:
Pick any ht E [H] for which (ft,, n², n², hh) > Eacty-
10:
Set Tea = x² (Q-type) or = Unif( A), i.e., draw actions uniformly at random (V-type).
Collect netim samples Dt {( ag 1 D)
(4) (i) Padi where ap:h--1 n² and ag Test-
12: For all E F compute estimate (f, n² h²) via Eq. (2) (Q-type) Eq. (4) (V-type).
Update F {f E F. (8A n², h2)l Eetm)
14:
end for
15:
Save the collected tuples {(h', x'; D') for the offline phase. Offline phase, the reward function R = (Ro..... .... RH-1) 1) is revealed.
16: Fort
= F + R, set II = {a'} (Q-type) or II = Io = {Ty : f E Zoal (i.e.. the greedy policies induced by Zoa) (V-type).
17: For each t E [T]. g (R), and E IT compute estimate (R( nt, n,, h²) via Eq. (3)
(Q-type) or Eq. (5) (V-type).
18: Set Fsur Rt) = {g E For (R) VI E [7]. VT E IT [ T', ,,,,,,,,, nT,) S 6elim/2).
19: Return policy मे Tg. where ğ argmax gE (R) (z())
3.1 Q-type RFOLIVE
Our algorithm, reward-free OLIVE (RFOLIVE) described in Algorithm 1, takes the function class F, the accuracy parameter E, and the failure probability 6 as input. As we are in the reward-free setting, it operates in two phases; an online exploration phase where it collects a dataset without an explicit reward signal, and an offline phase where it computes a near-optimal policy after the reward function R is revealed. Below, we describe the two phases and the intuition behind the algorithm design.
Online exploration phase During the online phase, we first set elimination thresholds Eactv, Eelim and sample sizes Nactv, Nelim and construct the following function class Fon used in the online phase:
=F (Wo for /H-1 fH-1) Sn. S E Fr. Vh E [M]
'The Q/V-type algorithms differ in whether to use uniform actions during exploration, and the distinction is needed handle different settings of interest (see Appendix B as well Table 1).
5

---

The detailed specification of these parameters are deferred to Theorem and Theorem 3. Subsequently, we simulate Q-type OLIVE with the function class Fmn using the zero reward function = 0 and the specified parameters. Similar to OLIVE, we initialize F Fon and maintain a version space F C _ C Fan of surviving functions after each iteration. each iteration, we first find the optimistic function I E F (line 4) and set x² = st. In line 5, we collect Paetv trajectories to estimate the Q-type average Bellman error EQ (0', n hb (0 ,², x , under zero reward:
E TT' x ,', Flcctv
S M
( (00 Vy (
If the low average Bellman error condition in line is satisfied, then we terminate the online phase and otherwise, we pick a step h where the estimate E n", m J²²) > Eacty (line 9). Then collect netim trajectories using 0D:!* ~ IT and set D' as the transition tuples at step h². Using D', we construct the Q-type average Bellman error estimates (8, xx, h²) for all f E J in line 12:
1
Theins
frr
(2 2 -V
(1 (1)+1)
(2)
Thelim
Finally, in line 13, we eliminate all the f TEFt Jt whose average Bellman error estimate &g (')))
Eelim-
The online phase returns tuples {(h', n², TT where T is the total number of iterations and each dataset D' consists of netim transition tuples.
Offiine elimination phase In the offline phase, the reward function R revealed, and we first con- struct the reward-appended function class Fot R)) F+ R == {(fo+ [ofo-Ro..... ... -
fn E
FR, Yh [ Using the class II { from line 16 and the collected tuples {(h², x², Dt) p))}"- T-11
1==
we estimate the reward-dependent average Bellman error (Definition 4) for all iterations E [T] of
the online phase:
(" xt tt +h)))
gh
I
RE
Vg
(3)
Teelin
RFOLIVE eliminates all E For whose average Bellman error estimates are large (line 18) and returns the optimistic function 9 from the surviving set (line 19).
Remark Similar to its counterparts in reward-aware general function approximation setting (Jiang et al., 2017; Dann et al., 2018; Jin al., 2021; Du al., 2021). RFOLIVE is in general not computationally efficient. We leave addressing computational tractability as a future direction.
3.1.1 Main results for Q-type RFOLIVE
In this part, we present the theoretical guarantee of Q-type RFOLIVE. We start with introducing the Q-type Bellman Eluder (BE) dimension (Jin al., 2021).
Definition 5 (Q-tye BE dimension). Let (I - T ==
= (/n -Ti'Jtti= I F} be the set of h=0 where Tn is a set of distributions over X x A.
Bellman differences of F at step h, and T = (T ]==0
H-1
The e-BE dimension of w.r.f. is defined as dimm (F,T,e)
R
maxne[H] da ((ITHR)) E)
We can now state our sample complexity result for Q-type RFOLIVE. To simplify presentation, we state the result here assuming parametric growth of the covering numbers, that is log(N>((E) < di log(1/e) and log(NR(()) S dR. log(1/z).
Theorem 1 (Q-type RFOLIVE, parametric case). Fix ò E (0, 1). Given a reward class R and function class F that satisfies Assumption I and Assumption 2, with probability least 1 6, for any R E R, Q-type RFOLIVE (Algorithm) 1) outputs policy ā that satisfies u 2 uR E. The required
number of episodes 5
((H dy + H dR) deo log( log(1/8)/67)
where dabe = dimgbo (F- CAFFFFFDDDA F,Dr-s,e/44R)
'The Ö(-) notation suppresses lola-togaii factors in its argument.

---

The more general statement along with the specific values of Eacte, Eelim, Navv, Relim are deferred to Appendix C.2. where we also present the proof. We remark that we only need the covering number of R. to set these parameters and do not use any other information about the reward class.
We pause to compare Theorem 1 to the reward-aware case. First, our BE dimension involves the "difference" function class J - F under zero reward as opposed to the original class with the given reward, and our completeness assumption is also related such a "difference" function class. As we will see, these differences are inconsequential for our examples of interest. Second, our sample complexity has an additional H dependence because (a) we consider a different reward normalization from Jiang et al. (2017); Jin et al. (2021) and (b) we use smaller threshold in the online phase to ensure sufficient exploration. Similar gaps in H factors between reward- free and reward-awe aware learning also appear in Wagenmaker et al. (2022). We also pay for the complexity of R in lower order term, which is standard in reward- that a similar adaptation of GOLF (Jin et al., 2021) for the reward-free setting may provide sharper result with improved dependence on H and dabe: analogously to the reward-aware setting.
RI (Zhang et al., 2020a; Modi et al., 2021). We believe
3.1.2 Q-type RFOLIVE for known representation linear completeness setting
Here, we instantiate the general guarantee of Q-type RFOLIVE to the linear completeness setting.? ?
Definition 6 (Linear completeness setting (Zanette et al., 2020b)). We call feature øle
(ob...., 2 with o) X x + Rd ())l2 I 1, 1, E [H] a linearly complete feature, for any B > 0,h h E [H - 1] and V ff++ E Qx+1(10') B) we have: min meellll J.B) ll.r Th futtll 00 = 0, where Qn ), B) = {ook 0n) :100112 S Bydce.
When the linearly complete features (Definition 6) dle are known, we can construct the function class F((o)))) = Fo H- -1 x... x FH J)),, where Fn((d Bn) = { (T un) = (on, on). 0n): : |10,112 S Bayda. (.), 0n) E [--B,, BA]} consists of appropriately bounded linear functions of d²c, Here superscript and subscript le imply that the notations are related to the linear completeness setting. It is easy to verify that F((o")) }}) satisfies the assumptions in Theorem 1.
This gives us the following corollary (see the full statement and the proof in Appendix C.4):
Corollary 2 (Informal). Fix 8 E (0, 1). Consider an MDP M that satisfies linear completeness (Definition 6) with known feature @lc, and the linear reward class R = R2 x... x Rv, where RA {ol mm): ||ma ll2 I vdie, (-)) ma) [0, 1]}. With probability least 1 - 5, for any R R. Q-rype RFOLIVE (Algorithm 1) with a vn E. The required number of samples is Ô (H log(1/8)/e²).
F((d"()) outputs a policy ă that satisfies
The reward normalization above, called explicit regularity in Zanette et al. (2020b), is standard. Compared to that work, our result implics that explorability is not necessary, which significantly relaxes the existing assumptions for this setting. Our result can also be easily extended to handle approximately linearly complete features (i.e., low inherent Bellman error). On the other hand, our algorithm is not computationally efficient owing our general function approximation setting. Although our sample complexity bound appears to be worse in H factors compared with their upper bound of Ô (df HH log(L/o)/="). it is indeed incomparable because their bound only holds when E S (((min// Virie) (Mmin is their explorability factor). Thus, there is an implicit dependence on 1/ V/min in their result, which could make the bound arbitrarily worse than ours. More discussions are deferred to Appendix A and Appendix C.4.
3.2 V-type RFOLIVE
In this section, we describe the instantiation of RFOLIVE with V-type definitions. For V-type RFOLIVE, we also assume that the action space is finite with size K.
Online exploration phase Instead of using Fon. we use its (elim/64)-coer Zon and maintain version space Ft across iterations. Since the on-policy version of Q-type and V-type Bellman
"Zanette et al. (2020b) only detine linear completeness B It can easily verified that it is equivalent for any choice of B. More discussion can be found Appendix C.4. Following Jin et al. (2021), we run V-type OLIVE with the discretized class Zon for the ease of presentation.
7

---

enrors are the same, the termination check in line 5 and line 6 are unchanged. If the algorithm does not terminate in line 6, we again identify a deviation step h' such that (f , = ((' h²) > Eacte. Instead of using n' to collect trajectories, we use du:kt-1 x¹ and choose age uniformly at random to collect the dataset of nelim transition tuples at step h². Compared to Q-type RFOLIVE, we estimate EQ for all f E F in line 12 using importance sampling (IS):
Rein 1 1
(6) (1)))
(9))
E n h²)
Sna
a - V, x6 (=
(4)
Thelim
1/K
Finally, in line 13, we eliminate all / E Ft whose V-rype average Bellman error estimates are large.
Offline elimination phase In the offline phase, we consider the same reward-appended function class Fult (.) when reward R E R revealed. For V-type RFOLIVE, in line 16, we define the policy class I1 = -Ion which consists of greedy policies with respect to all f E Zon. Using dataset D we estimate (g, ,',,,,,,,, ((') for all g E (I), n' E Ilo, [T] from its empirical version:
1
Batin 1aah
(1 (Sh( ( Rs (8) Oi
(00)
(2 (5)
Thelim
1/K
and eliminate invalid functions in line 18. Finally, we return the optimistic policy मे from the surviving set. Apart from estimating different average Bellman errors, the noticeable difference between Q-type and V-type RFOLIVE is that the latter uses IS to correct the uniformly drawn action to some policy r' E Lon to witness the average Bellman error (Jiang et al., 2017).
3.2.1 Main results for V-type RFOLIVE
Here we present the theoretical guarantee of V-type RFOLIVE. Firstly, we introduce the V-type Bellman Eluder (BE) dimension (Jin et al., 2021). Definition 7 (V-type BE dimension). Let (I TR S (X R) be the state-wise Bellman difference class of F step h defined as (I TR f== for (Sh The (nt n (x)) _H-1 where I'p is a set of distributions over X. The V-rype s-BE dimension of F F}. Let = {T=)k=o with respect to D is defined as dim R (F,T,e) = maxXe[H] (V,
We now state the guarantee for V-type REOLIVE, assuming polynomial covering number growth.
Theorem 3 (V-type RFOLIVE, parametric case). Fix å 1). Given reward class R. function class F. that satisfies Assumption I, Assumption 2, with probability at least 1 - 6, for any R E R. V-type RFOLIVE outputs policy î that satisfies v 2 on E. The required number of episodes is
Ō Õ(H dy HHddx) & K log log(1/6)/E8)
where dobe = di FF..
The detailed proof and the specific values of Easw; Celim: actv nelim deferred to Appendix D.2. Our rate is again loose in H factors when compared with the reward-aware version. Compared with the Q-type version, here also incur dependence on K |A), analogous to the reward-aware case.
3.2.2 V-type RFOLIVE for unknown representation low-rank MDPs
As special case, we instantiate our V-rype RFOLIVE result to low-rank MDPs (Modi et al., 2021) Definition 8 (Low-rank factorization). transition operator P,, X A + A(Y) admits low- rank decomposition of dimension die if there exists dir : X' A + Rd and p X + Rdv s.I. 'x, X.a a A Pa x. (d) (xr, a), u1 (x))), and additionally ((()) S and vP' ; 1-1, we have || (x))))
S dir. We say M is low-rank with embedding dimension dr. if each (H), the transition operator Pn admits rank-dy, decomposition.
Here superscript and subscript Ir imply that the notations are related to low-rank MDPs. As in Modi al. (2021), we consider low-rank MDPs in a representation learning setting, where we are given realizable feature class dlr rather than the feature dlr .....
(ob...... dlr -1) directly:
8

---

Assumption 3 (Realizability of low-rank feature class), We assume that finite feature class D - satisfies df 1 vh H). In addition, wh E [H] On E b//
dbr 0 x ...
(+1l -
Similar to the linear completeness setting (Section 3.1.2), we construct F(Bl))= Fo( H 1)x -F 0), where Fi, BB) = (T as) = (Øn(IN, as)) ),,, 0n) on E t 1 S B₁ TH (oh (-), 0n) E [- BB,, B-]]- In Proposition 4, we show that the V-type Bellman Eluder dimension of F( F( in this case is Ô (dz)) which leads to the following corollary:
Corollary 4 (Informal, parametric case). Fix d E (0, 1). Consider a low-rank MDP M of embedding dimension die with a realizable feature class & (Assumption 3) and a reward class R. With probability at least 1 - 6, for any R E R, V-type RFOLIVE (Algorithm 1) with F(D")) outputs policy ā that satisfies u 2 UR -E. The required number of episodes is
Ô ((H di log([ + 11 dR) K log log(1/8)/=²).
We defer the full statement and detailed proof of the corollary to Appendix D.3. In the low-rank MDP setting, Modi et al. (2021) propose more computationally viable algorithm, but additionally require reachability assumption. Our result shows that reachability is not necessary for statistically efficiency, which opens an interesting avenue for designing an algorithm that is both computationally and statistically efficient without reachability. Moreover, our result significantly improves upon their sample complexity bound. The detailed comparisons are deferred to Appendix A and Appendix D.3. Notice that here K shows up in our bound. As another corollary, in the linear MDP (Definition plus d'r is known), Q-type RFOLIVE yields a K independent bound. The details can be found in Appendix C.5.
3.3 Intuition and proof sketch for RFOLIVE
We first provide the intuition. Since the online phase of RFOLIVE is equivalent to running OLIVE with 0 reward function, any policy y attains zero value (i.e., Vo.6 (1o) = 0, Vf E Fou). By the policy loss decomposition lemma (Jiang et al., 2017), the value error for the greedy policy, V)())) Volú (aro). small when the algorithm stops (line 6). Therefore, all f E Fon which predict large values Vy (mn) must have been eliminated before OLIVE terminates. This implies that, in the online phase, we gather a diverse set of constraints (roll-in distributions π') that can witness the average Bellman error of functions in Fon- In this sense, algorithm focuses function space elimination and does not try to reach all latent states or directions (Modi et al., 2021; Zanette et al., 2020b), which is the key conceptual difference that enables to avoid reachability and explorability assumptions.
On the technical side, note that the way we use OLIVE in the offline setting is novel to our knowledge and is crucial to getting a good sample complexity under our assumptions, as opposed to more standard FQI style approaches. Because we have to coordinate between the online and offline phases, the analysis bears significant novelty beyond the original analysis of OLIVE (and its reward-aware follow-up works), and this one of our key contributions. The most crucial part to show that any bad g Fon (R) whose average Bellman eπror is large under the true reward R will be eliminated in the offline phase. To prove this, we construct f E Fou that has the same average Bellman error as g and predicts a large positive value Vy(Zu), which implies that it will be eliminated during the online phase. Finally, by our construction, the constraint used to eliminate f directly witnesses the average Bellman enror of g, thus ruling out g in the offline phase. We discuss it in more detail in Appendix C.3.
Hardness result for unknown representation linear completeness setting
In Section 3.1.2, we showed that Q-type RFOLIVE requires polynomial sample for reward-free RL in the known feature linear completeness setting. For low-rank MDPs, when given a realizable feature class, we showed V-type RFOLIVE is statistically efficient in Section 3.2.2. A natural next step is to relax the low-rank assumption on the MDP and show a sample efficiency result for the more general linear completeness and unknown feature case. However, below we state hardness result which shows that polynomial dependence on the feature class ( ($tee) or an exponential dependence on H is unavoidable. We first introduce the realizability of a linearly complete feature class.

---

Assumption 4 (Realizability of the linearly complete feature class). We assume that there exists finite candidate feature class & D x
1 H such that Vh [H], we have df E.y. In addition, vh E [H), 0h E k V(x, a) E X x A. we have (-))())l 12 S 1.
Now we state of hardness result for learning in the linear completeness setting with a realizable feature class (Assumption 4). A complete proof and more discussions are provided in Appendix E.
Theorem 5. There exists family of MDPs M. a reward class R and feature set Φ such that VM E M, the (M, "0 pair satisfies Assumption 4. yet information theoretically impossible for algorithm oblain a poly (thes H, log( [b/1)) log( [R]), 1/e, log(1/6) sample complexity for reward-free exploration with the given reward class R.
The hardness result in Theorem 5 is also applicable to easier settings: (i) learning with a generative model (or using a local access protocol, Hao et al. (2022)), (ii) reward-free learning with explorability (Zanette et al., 2020b) and reachability (Modi et al., 10 assumptions and (iii) reward-aware learning as R is known singleton class. Thus, the result highlights an exponential separation between the low-rank MDP and linear completeness assumptions by showing that linearly complete true feature 6e Φ is not sufficient for polynomial sample efficiency and additional assumptions are required to account for the unknown representation.
5 Conclusion and discussion
In this paper, we investigated the statistical efficiency of reward-free RL under general function approximation. The proposed algorithm, RFOLIVE, is the first algorithm to address reward-free exploration under general function approximation. Contrary to prior works which either try to reach all states or all directions the feature space, RFOLIVE follows a value function climination template and ensures that the collected exploration data can be used to identify and eliminate non- optimal value functions for downstream planning. This significantly sets us apart from the existing reward-free free exploration works. Our positive results significantly relax the existing assumptions in the reward-frre --reee exploration framework. Our negative result shows the first sharp separation between low-rank MDP and the linear completeness settings with unknown representations. In addition, provide an algorithm-specifee counterexample in Appendix F that shows RFOLIVE can fail when the completeness assumption is violated. As realizability alone is sufficient for reward-aware RL (Jiang et al., 2017; Jin et al., 2021; Du et al., 2021), our results also elicit the further question:
Are maliizabliity-type assumptions sufficient for statistically efficient reward-free RL.
We conjecture that the answer is no, and we believe that the hardness between reward-aware and reward-free RL has deep connection to the sharp separation between realizability and completeness (Chen and Jiang, 2019; Wang al., 2020b, 2021; Xie and Jiang, 2021; Weisz al., 2021a,b, a, 2022; Foster et al., 2021).
Acknowledgements
JC would like to thank Tengyang Xie for helpful discussions. Part of this work was done while AM was at University of Michigan and was supported in part by a grant from the Open Philanthropy Project to the Center for Human- Compa--Coe AI, and in part by NSF grant CAREER IIS- (SS-142099. NJ acknowledges funding support from ARL Cooperative Agreement W91 1991NF-177 17-2--99- NSF 114-21 NSF CAREER IIS-2141781, and Adobe Data Science Research Award.
References
Alekh Agarwal and Tong Zhang. Non-linear reinforcement learning in large action spaces: Structural conditions and sample-effiiiency of posterior sampling. arXiv preprini arXiv:2203.08244 2022.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in Neural Information Processing Systems, 2020.
10

---

Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, 2020.
Jinglin Chen and Nan Jiang. Information-theorrtiic considerations in batch reinforcement learning. In International Conference Machine Learning, 2019.
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density- rrttoo realizability: The power of gaps. In Conference on Uncertainty in Artificial Intelligence, 2022.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. On oracle-efficient PAC RL with rich observations. In Advances in Neural Information Processing Systems, 2018.
Simon Du Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. International Conference on Machine Learning, 2019.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. In International Conference on Machine Learning, 2021.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 2005.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. arXiv:2111.10911 2021.
Botao Hao, Nevena Lazic, Dong Yin, Yasin Abbasi- Yadkor,, and Csaba Szepesvari. Confident least square value iteration with local access to simulator. In International Conference Artificial Intelligence and Statistics, 2022.
Jiawei Huang, Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie- Yan Liu. Towards deployment- efficient reinforcement learning: Lower bound and optimality. International Conference on Learning Representations, 2021.
Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, 2018.
Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low Bellman rank are PAC-leamable. In International Conference on Machine Learning, 2017.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward free exploration for reinforcement learning. In International Conference Machine Learning, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. In Advances in Neural Information Processing Systems, 2021.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. Algorithmic Learning Theory, 2021.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 2016.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. sharp analysis of modellbased reinforcement learning with self-play. In International Conference on Machine Learning, 2021.

---

Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration reinforcement learning. In Interna- lional Conference on Machine Learning, 2021.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning, 2020.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal, Model-free representation learning and exploration in low-rank mdps. arXiv:2102.07035, 2021.
Shuang Qiu, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. On reward-free RL with kernel and neural function approximations: Single-agent MDP and markov game. In International Conference on Machine Learning, 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 2013.
Wen Sun, Nan Jiang, Akshay Krishnamurthh, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, 2019.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. In International Conference on Learning Representations, 2021.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. Reward- free RL is no harder than reward-aware RL linear markov decision processes. arXiv:2201. 11206, 2022.
Martin J Wainwright. High-dimenssonal statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019.
Ruosong Wang, Simon Du, F. Lin Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation. In Advances in Neural Information Processing Systems, 2020a.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? In International Conference on Learning Representations, 2020b.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. In Advances in Neural Information Processing Systems, 2020c.
Yuanhao Wang, Ruosong Wang, and Sham Kakade, An exponential lower bound for linearly realizable MDP with constant suboptimality gap. Advances in Neural Information Processing Systems, 2021.
Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkorii Nan Jiang, and Csaba Szepesvári. On query- planning in MDPs under linear realizability of the optimal state- value function. In Conference on Learning Theory, 2021a.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in MDPs with linearly- optimal action-valus functions. In Algorithmic Learning Theory, 2021b.
Gellért Weisz, Csaba Szepesvári, and András György. Tensorplan and the few actions lower bound for planning in MDPs under linear realizability of optimal value functions. In International Conference on Algorithmic Learning Theory, 2022.
Jingfeng Wu, Vladimir Braverman, and Lin Yang. Gap-dependent unsupervised exploration for reinforcement learning. In International Conference Artificial Intelligence and Statistics, 2022.
12

---

Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforeement learning: A theoretical comparison. In Conference on Uncertainty Artificial Intelligence. 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference Machine Learning, 2021.
Ming Yin and Yu-Xiang Wang. Optimal uniform OPE and model-based offline reinforcement learning in time-homogeneous, reward-free and task-agnostic settings. Advances in neural information processing systems, 2021.
Andrea Zanette and Martin J Wainwright. Bellman residual orthogonalization for offline reinforce- ment learning. arXiv:2203. 12786, 2022.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference Machine Learning. 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill. Provably effi- cient reward-agnostic navigation with linear value iteration, In Advances in Neural Information Processing Systems, 2020b.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. In International Conference on Learning Representations, 2020a.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 2021.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 2020b.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Table 1, Theorem 1, Theorem 3, Theorem 5,
Corollary 2, Corollary 4, Corollary
(b) Did you describe the limitations of your work? [Yes] Our results hold for assumed structural properties and the R RFOLiVE algorithm is not computationally efficient as our focus statistical efficiency.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results?[ See Theorem Theorem 3, Theorem 5, Corollary 2, Corollary 4, Corollary 6.
(b) Did you include complete proofs of all theoretical resul We include all the proofs in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "tWx3_HmHpKc", "reviewer": "Reviewer_A559", "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). \n\n----------------\n\nUpdate: After reading the author's reply and other reviews, I would like to maintain my score of 7.", "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.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nBoth 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. \n\nThe 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.  \n\nOverall, 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. \n\nI did not see any major weaknesses but had several minor questions and corrections:\n- 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. \n- 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. \n- In Section 3.1, perhaps reference Definition 6 or otherwise remind the reader what $\\phi^{lc}$ corresponds to.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "sdnO5EzMWXY", "reviewer": "Reviewer_Xxv4", "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). ", "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:\n\n1. 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.\n\n2. 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?\n\n3. 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?\n\n4. 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\n\nOther minor comments:\n- 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.\n- Line 147: the rightmost x_h should be a_h\n- Line 252: \"dateset\"", "limitations": "Limitations have been properly discussed", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper studies a relevant problem (RF RL with general function approximation) which was previously unaddressed\n- The results are significant and they do not rely on strong assumptions\n- The hardness result of Section 4 is significant and of independent interest\n- 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)\n\nWeaknesses:\n- 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\n- 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\n- No numerical result is presented (though, as a consequence of the previous point, it is not possible to do much beyond very toy problems)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "h0oS0ljRwJc", "reviewer": "Reviewer_GjCj", "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.", "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?\n2. 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.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The organization of this paper is clear and easy to read.\n2. This work proposed provable algorithms for different settings without reachability/explorability assumptions that are necessary for previous works, which is a big improvement.\n\nWeakness:\n1. 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.\n2. 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?\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "T9KTLWrIMd", "reviewer": "Reviewer_zknp", "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.", "questions": "General comments:\n-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.\n-\n\nSpecific comments: \n-L45: At this point it is not clear what is the set of constraints.\n-L127: Do you have simple concrete examples of MPD and associated classes \\cR and \\cF which verify these two assumptions? \n-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).\n-L186,(3): h_t instead of h.\n-L200: Do you have an example where this assumption is verified?\n-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).\n-L267:  Can you discuss the differences between Q-type and V-type RFOlive, in partícular in terms of theoretical guarantees.\n-L290: Can you provide a table with the different rates given the algorithm and the setting to ease the comparison with the previous baselines?\n-L296:Can you explain why it 'significantly improves' over the previous bounds.\n-L551:By realizability you mean that assumption 5 is verified?\n-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. \n-L581: A hat is missing.\n-L597 Maybe you should precise the events.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Contributions:\n-Algorithm RFOlive an adaptation for reward-free exploration of the Olive algorithm by Jiang et al. (2017). Novelty: low; relevance: medium.\n-Exploitability assumptions for linear completeness setting and reachability for low-rank MDPs are not necessary for reward-free exploration. Novelty: low;  relevance: high.\n-Reward-free (and reward-aware) exploration with linear completeness assumptions and when the\nunderlying features are unknown is intractable. Novelty: medium, relevance: medium.\n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept