A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation
Authors: Philip Amortila
Nan Jiang
Dhruv Madeka
Dean Foster
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement learning
imitation learning
function approximation
sample efficiency
linear realizability

Abstract: The current paper studies sample-efficient Reinforcement Learning (RL) in settings where only the optimal value function is assumed to be linearly-realizable. It has recently been understood that, even under this seemingly strong assumption and access to a generative model, worst-case sample complexities can be prohibitively (i.e., exponentially) large. We investigate the setting where the learner additionally has access to interactive demonstrations from an expert policy, and we present a statistically and computationally efficient algorithm (Delphi) for blending exploration with expert queries. In particular, Delphi requires $\tilde O(d)$ expert queries and a $\texttt{poly}(d,H,|A|,1/\varepsilon)$ amount of exploratory samples to provably recover an $\varepsilon$-suboptimal policy. Compared to pure RL approaches, this corresponds to an exponential improvement in sample complexity with surprisingly-little expert input. Compared to prior imitation learning (IL) approaches, our required number of expert demonstrations is independent of $H$ and logarithmic in $1/\varepsilon$, whereas all prior work required at least linear factors of both in addition to the same dependence on $d$. Towards establishing the minimal amount of expert queries needed, we show that, in the same setting, any learner whose exploration budget is \textit{polynomially-bounded} (in terms of $d,H,$ and $|A|$) will require \textit{at least} $\tilde\Omega(\sqrt{d})$ oracle calls to recover a policy competing with the expert's value function. Under the weaker assumption that the expert's policy is linear, we show that the lower bound increases to $\tilde\Omega(d)$.

A Few Expert Queries Suffices for Sample-Eficcient RL with Resets and Linear Value Approximation
Philip A
Nan Jiang"
Dhruv Madeka
Dean P. Foster
"University of Illinois, Urbana- Urbana-Champaige Champaign
AAmazon, NYC
Abstract
The current paper studies sample-efficient Reinforcement Learning (RL) in settings where only the optimal value function is assumed be linearly-realizable. It has recently been understood that, even under this seemingly strong assumption and access to a generative model, worst-case sample complexities can be prohibitively (i.e., exponentially) large. We investigate the setting where the learner additionally has access to interactive demonstrations from an expert policy, and we present statistically and computationally efficient algorithm (DELPHI) for blending ex- ploration with expert queries. In particular, DELPHI requires (dd) expert queries and a poly(d, H, |A,, 1/E) amount of exploratory samples to provably recover an e-suboptimal policy. Compared pure RL approaches, this corresponds exponential improvement in sample complexity with surprisingly- little expert input. Compared prior imitation learning (IL) approaches, pert demonstrations is independent of H and logarithmic in 1/8, whereas all prior work required least linear factors of both in addition to the same dependence d. Towards establishing the minimal amount of expert queries needed, we show that, in the same setting, any learner whose exploration budget
required number of ex-
momommally-boundder (in terms of II, and (Al) will require least }2( dd) oracle calls recover a policy competing with the expert's value function. Under the weaker assumption that the expert's policy is linear (rather than their value function), we show that the lower bound increases to ((d).
Introduction
Many potential applications of reinforcement learning (RL) have intractably-large state spaces. Thus, we seek provably-corres methods which have statistical and computational requirements that are independent of the size of the state space. This requires some modelling assumptions. One dominating approach has been to introduce function approximation, and posit that the MDP or its value functions are well-represented by the function approximation scheme which is employed. basic starting point which still lacks comprehensive understanding is the case of linear value function approximation, which models value functions lying in the span of known d-dimensional feature mapping and asks for methods which have sample complexities that are polynomial only in d, Ht and possibly [A] (Hf and A are the horizon and action sets of the MDP, respectively). This desideratum was recently understood to be impossible for the "minimal" case where only the optimal value function (or optimal action-value function) is assumed to be linear - i.e. there exist MDPs satisfying this assumption where the statistical complexity of any algorithm will be exponentially large, either in d or in H [WAS2I] WSG21 WWK21 FKQR21). Furthermore, this also holds in the case where the leamner is equipped with a generative model (or simulator), allowing them sample transitions from any state-action pair of the MDP. In recent years much has been said about linear value approximation under stronger assumptions, for example under determinism
"philipa40illinoiss
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

[WR13]. linear/low-rank MDPs JYW120 AJSWY20J, Bellman--cosedness [LSW20 ZLKB20,, or
the existence of "core set" [SS20] ZLKB These stronger assumptions can recover polynomial
statistical complexities (thought not always computational ones), but are restrictive and oftentimes unrealistic.
In this work, we consider an alternative possibility for recovering polynomial complexities which does not further restrict the class of MDPs under consideration. We do this by assisting the learner with some additional side information about the problem. Specifically, we assume that there is a deterministic expert policy (which need not be the optimal policy) that the learner can query at any state, whereupon they will be informed of the expert's action at that state. Indeed, such information can often be made readily available if we have some form of prior knowledge (or human input) about the problem. Leveraging such expert demonstrations has been studied in interactive imitation learning (II.), with common applications in simulated domains [RGBT]] Rost3| RB14 14 SVGBB17]. As we will see, however, the amount of expert queries required by a pure II. approach is significantly higher than what we need. Since interaction with a (human) expert might be costly, we wish to minimize the burden of the expert by having the learner explore mostly on their own, and only query the expert in judicious manner. The question asked by this work, then, is:
Under linearity of the optimal value function, what is the minimal amount of expert data required for campleccomuuationallyyyye
learning?
Our main result is the DELPHI algorithm for exploring with an interactive expert. DELPHI assumes that the expert's 's value function is linear, and that the agent has access to RESET function which lets them return to the state most recently seen. Under these conditions, our method uses surprisingly-fe expert queries combined with some modest (polynomial) amount of exploration to recover the expert policy. Formally, DELPHI recovers a policy that is E o-optimal (with respect to the expert policy) with (od())(B/))) oracle calls and Ö (
exploratory samples, where B is bound on the lz no-morm of the unknown linear parameter Thus, our results show that merely (d) expert queries enable exponential improvement in sample complexity when compared to RL without expert advice. Furthermore, the number of oracle calls is completely independent of the horizon of the problem and is logarithmic in 1/c, whereas prior work in IL leveraging expert advice requires (at best) linear factors of both in addition to scaling with d. We also show that DELPIII is computationally efficient, that it is robust to optimization and misspecification errors, and that it can be extended to the case where the action-value function of the expert is linear when the MDP dynamics are deterministic.
Towards establishing the optimality of our algorithm, we study the capabilities of expert-augmentee learners which have fixed exploration budgets. More specifically, we ask: what is the minimal number of expert queries required by any algorithm which is constrained to a polynomially-bounder exploration budget? We show that any polynomially- require least Ω( oracle calls recover policy competing with the expert's 's value function. In the weaker setting where only the expert's 's policy is linear, we show that this lower bound increases to (d). matching our upper bound up to logarithmic factors.
learner (in terms of d, H, and (.A)) will
The rest of the paper is structured as follows: in Section ww review background and present the problem setting. S describes our algorithm, its guarantee, sketch of the proof, and discusses some extensions. Section 4 gives the lower bound on the number of expert queries needed. We conclude with an overview of related work and some discussion in Sections Jand
2 Background & Problem Setting
Notation We write Dists(X') for the set of probability measures on some set X. We write [M] = The direct product @ corresponds to "concatenating" two vectors, i.. for any two vectors u E R and v E IR"", we have u @ == (u1,..., Un, 01, 01...., Um) T E Rn+mm We write @ for the tensor (or outer) product of two vectors, defined by u 8 = uo E Raxm and b(u @ v) E p for the flattening (or vectorization) of said tensor product.
N). [1....,N]
"The Ô notation ignores logarithmic factors.
2

---

MDPs, Policies, and Value Functions The typical environment in RL is modelled as an MDP
4ut14; Sze [BB8]. We consider here finitehhorizon MDPs, which are specified by tuple M S,A, R.P, H, fo). where S is a state space, A = [A] is a finite action set, R. S A - Dists [0, I)) a (bounded) reward distribution function with expectation r(s, a), P S X - Dists(S) the transition distribution function with probability vectors P(s, a) = [P(s']ss, a))rrss E R $i H E N is the horizon, and μf E DS) is the starting distribution. Note that we have assumed that the action space is finite, although the state space may be infinite. Without loss of generality we assume that S is a disjoint union of per-horizon state spaces, i.e. S Sh.
A (non (non-stationary) policy π = (TT1 ... TH) prescribes a sequence of actions Th : Sh - Dists(A), and its value function is v*))s) = The action-value function 9" (8, a) is defined similarly, save that the first action taken a and the
r(sw, aw)) 8h 8, dh TA (sw( )] where E Sp.
proceeding actions follow π. Value functions satisfy the recursive relationship:
( = r(s, T) + (P(s, 00 ()) = T<
(1)
where we have the shorthands r(s, TT (awn(s) (r(s, a,),)] P(s, .T - Ba (P(s, a)}. and the Bellman operator (+) := r(s, TT + (P(s, (-)). The Bellman operator has n" as its unique fixed point. The optimal policy is written as n,, and its value function is denoted as y = u=". The
objective is to find a π maximizing en (1o) == Exo [v (su)).
Function Approximation With an Interactive Expert must be explored. As stated in the introduction, we seek sample complexities which are independent of the number of states. This is evidently not possible without further assumptions. To assist the learner, we assume that the agent has further access to an oracle, which, upon being queried, returns the action of an expert policy TO for the state. The expert policy need not be the optimal policy. We will assume that л² is deterministic, which is satisfied for example when T = TT" or when x² is the greedy policy of some value function.
In the RL setting, the MDP is unknown and
Assumption 2.1 (Interactive expert). There is an oracle which can be queried at the current state which returns the action TO (s). Syntactically, the oracle is queried via the ORACLE(S) function.
We note that the oracle can only be queried at the state the learner is currently visiting. The objective of the learner is to recover a policy which competes with the expert policy, namely a á such that:
a (mo) 2 v (Ha) - with probability 2 1 - 8,
(2)
where U u is the value function of the expert. In the sequel we refer to a policy satisfying Equation as s-optimal.
Our next assumption concerns the interplay of the expert policy with linear value approximation. Namely, assume that the expert policy has value function which is linear in set of known features.
Assumption 2.2 (V- -linearit, with bounded features). The value function d of the expert is linear with known features yp E Rd, i.e.
8 (0(s) = (v((), 0º), Vs
(3)
for some unknown 0 E Rd. We further assume that [|:(())122 I 1 V' and that |0012 S B for some known B E Rd.
This assumption can be extended to the case of (slight) misspecification, as will be shown in Subsection 3.2 Our last assumption is that the agent has the ability to "reset" to the state most recently seen.
Assumption 2.3 (Resets). After experiencing a transition (s,a, s') in the MDP, the agent can return the state s. Syntactically, this is done via the RESET() function.
Our RESET assumption is weaker than the full generative model access KMN022 or the "local" simulator setting [WAJAYJS2]] LCCGW2T HLYAYS22] which has appeared prior works. As noted in the introduction, existing exponential lower bounds entail that Assumptions 2.2 and 2.3 together are not enough to enable sample-efficient learning. Thus, any efficient learner which is provided with the above assumptions (2.1 2.2 and 2.3 must necessarily make use of the expert.
3

---

3 The DELPHI algorithm
We are ready to describe our approach and give the main result. We begin by supposing that the starting distribution is deterministic (we will see later that this comes at no loss of generality).
Theorem 3.1. Suppose Assumptions 2.7 2.3 and hold. Then the DELPHI algorithu will recover a policy ât such that v² (so) 2 v (so) - with probability 2 1 - 6, using (((EE)))) oracle calls
and Ö 14
AB*) gd
interactions with the MDP. Furthermore this algorithm is computationally efficient.
The pseudo-code for DELPHI is given in Algorithm [ which uses Algorithm 2 (measureTD) sub-routine to measure expectations. DELPHI will solve for a parameter 0 such that induced policy T (defined via Eq. { will compete with the expert's value function. We note that deploying the policy Ty also requires the RESET functionalityy, since expectations must be estimated from a small number of samples at each state encountered. This is a consequence of our assumption that v² is linear (rather than, e.g., q" or the MDP itself), since selecting actions based on state-value functions will always require one-step look-aheads.
Intuition for DELPHI Recall that the expert policy π" satisfics ve = =T vo, and that this fixed point is unique. We say that a candidate value function is consistent at a state if v(s) = 7 v(s). Note that we need consistency to hold globally (i.e. at all states) in order to ensure that v = o= Our methodology is based ensuring that consistency on small number of well-chosen states will guarantee global consistency.
DELPHI is inspired by recent algorithm of [WAJAYJS2] called TensorPlan. As in TensorPlan, DELPHI proceeds via a "guess and check" procedure: at every iteration, we pick the optimistic linear parameter which is consistent on the past expert data that we have seen. We then check whether this choice of parameter is globally consistent, by playing Arollout rollouts of length H with a policy derived from the parameter. More specifically, for any 0 the policy Ta takes the form
To = argmin (f(s,a) R..a(vo(('') - vo((s)
where vo(+) = (v()), 0), and f(s, a) and B,r-P(s.a) are estimated via the RESET function.
After a certain number of rollouts, one of two things happen: either this policy encounters a state where there is no consistent action (i.e. the above minimum has a strictly positive value), or we only encounter states that are consistent In the first case, we query the oracle for its expert action and use the transition for that action to update the parameter set. In the second case, we derive (cf. Lemma 3.7) that if no inconsistencies are observed for several rollouts, then our "virtual value" Vg is close to the true value under me (i.e., =*"), Using that was optimistic (i.e. (00) 2 Uge (80)), this implies that we optimal.
The only thing left to argue is that the number of iterations (i.e. the number of times that we can continue finding new parameters which are not globally consistent) is small. Using linearity of v", it turns out roughly d inconsistencies are sufficient for this. To see this, note that we can re-write the Bellman equation for any v-(-) (sp(-), 0) as:
v0(s) T v0(s) - r(s, n (s)) + (Ex- | - ((s)
(A (a): 1 + 0),
(5)
(ps)) and used linearity of expectation, linearity of inner products, the definition of Ug. and the definition of the direct product. We call the vector A..a the temporal difference (TD) vector for (s, a). Equation (5) is precisely an orthogonality constraint in d + 1 dimensions. Since the parameter 6, which is chosen at time t was consistent on past data, it orthogonal from interactions with the oracle. If we happen to find a state which has no consistent action, then the TD vector corresponding to the expert action at that state must not be in the span of the previous expert TD vectors (otherwise it would be consistent). It follows that the iteration complexity is at most + 1, since there are at most + 1 linearly independent vectors in Rd+1, We use the Eluder dimension [VRR33 to generalize this argument to the case where the expectations are estimated.
where we have introduced the notation A..a r(s, a) @ -
the previous
1 TD vectors which have been generated
The next section solidifies the above intuition and sketches the proof more formally.
In reality, due sampling errors, tolerate some error during the consistency checks.

---

Algorithm DELPHI
1: Inputs: So, 9, sub-optimality Starget, confidence 6, parameter bound B
2: Og f Ball;,(B)
D + current consistent parameters
3: Initialize Ed, Reval- and Etol via Equations 9
13
4: for t = to Ed + do
5: Pick 0, E arginaggee.. (ve(so) 0" (0(()))))))))))))))))))))
Optimistic choice over O
6: consistent <- true
7: for m
Arollout do
Prollout number of rollouts with 0g-induced policy > Initialize rollout
8:
St.m. = 80 for 1 do
9:
10:
for a E [A] do
P For each action
11:
Ås m.m f- measureTD((S Sh. a, Navai)
Measure TD vector at (s, a)
end for mina (As.m.... o 0,)
13:
> Etol then
No consistent action
14:
consistent c- false
aj f- ORACIE((S.....
Query oracle for T (St.m.))
16:
m f measureTD(S Gi, 4eva
Refined data
17:
O - (0 ( 0)1 I Etol New admissible parameters
18:
Exit current iteration, t + 1, Goto Line end if
19:
20:
A 5 argmin ( mm + 0.)
Else consistent, keep playing
21:
Play At,,h get Re,,, St. MDP
Roll forward
end for 23: end for
if consistent true then
25: return O
No inconsistency for rollouts
success
end
27:
end for
28: return DEs+1
Algorithm 2 measureTD
1: Inputs: s, a, sp(-), n, RESET()
2: for i = 1 to do
3: Play action a at 8, receive sample R2 and S from MDP
4: A, < R₁ + ((p())) pp())
5: RESET()
6: end for
7: return ÂS = Eig(n) A;
3.1 Proof sketch
The full proof comes in parts. The proofs for all Lemmas and the precise values of all hyperparame- ters are given in Appendix(A
1. Lemmas 3.2 and 3.3 gives concentration bounds which establish that, with high probability, the
measurements (Line and Á (Line 16) concentrate to the average As.a = ER( @
(RP((..))(s'')>00) -ss)).
Lemma 3.4 establishes that, with high probability, the true optimal parameter 8 is not eliminated from O for any parameter set that is encountered. It follows (Lemma 3.5) by optimism that
Up, (5o) 2 0 (so) with high probability, where 0, the parameter chosen time L.
3. Lemma 3.6 establishes iteration bound: the algorithm will terminate after at most / = Ea iterations of the outermost loop (and thus after most F, oracle queries). The quantity F.a happens to be the Eluder dimension of our linear function class.
5

---

4. Lastly, Lemma 3.7 establishes that if Arollous number of rollouts oceur without observing consistency break, then the virtual value (Uol (5a)) must be roughly equal the true value under the executed policy (u (sa)). Theorem 3.1 combines all the ingredients to conclude the proof.
Part 1: Concentration bounds Recall that 4s,a == r(s (Elp(s') (p(s) is the true TD
vector, Å is the estimated TD vectors obtained with Nevrl samples (in Line 11 and is the "refined data" obtained with 4 Eeveval samples (in Line The following lemmas establish concentration of Á and Á to the TD vector.
Lemma 3.2 (Concentration of Á,,a (Line
For any 8, a E S x A that is observed throughout we have that with probability 2 5,
the execution DELPHI, with Nevat samples es in Line 77
A A,,0
S Eevat and thus that (1 + 0, As,a -aaa) S Eeval.
Lemma 3.3 (Âs.a concentrates even more (Line 16 we have || Assa
Similarly, for all 8, where we call the oracle,
with probability
S eevat/ (2at/(2//a)) and thus, 40 Balli, (B),
[11 ① 0, As.a As,a)l I Eeaar (ovaz/(2//E)) (2vEa).
Part 2: Optimism This part shows that (with high probability) the true optimal parameter is not eliminated from the version space, and thus by optimism that the predicted value is upper bounds vf.
Lemma 3.4 (0 not eliminated). With probability 2 11-6, 5, 0 E for all iterations E [Fa + 1].
Lemma 3.5 (Optimism). Under the event of Lemmal 3.4 we have ve(su) 2 v (s(). Vt E [Eu].
Part Iteration bound To bound the iteration complexity of our algorithm, Eluder dimension [RVR13]. Loosely, the Eluder dimension with respect to some target function is the longest sequence of points (x;) such that there exists functions differing from the target function on I; but which correctly fit it on 21...., -i- Eij-.. A formal definition is provided in Appendix A We will use the result that the Eluder dimension of linear functions is O ln(B/=)) (RVRI3] LKFS21)
use the notion of
Lemma 3.6 (Iteration Complexity). With probability 2 28, the iteration complexity of the algorithm is at most the Eluder dimension at scale Evvat, i.e. Ea = OndIn(B eva.)).
Part 4: Consistency, and putting everything together The last thing to show is that if consistent at all states for several rollouts then the virtual value Ug will be close to the value of the TT
Lemma 3.7 (Consistency
accurate prediction). If rollouts have occured without any inconsistencies (i.e., the if statement of Line 13 never gets triggered), then ( > U0(8))
5HE eval Croli with probability 2 35.
We are now ready to put everything together.
Proof (of Theorem 3.7). Assume all events introduced so far (i.e. the events in Lemma 3.2 Lemma
3.3 and Lemma 3.7 Together these happen with probability 2 1 36, so we can re-define å + 8/3
such that the events happen together with probability 2 (this only increases factors inside
logarithms by 3). By Lemma 3.7
we have:
To (3o) 2 (0())) - 5/Eava 6roll
10 (8)) Starget
T (so) Starget:
(6)
where the second step follows from plugging in the definitions of neval (Eq. 12 Prollout (Fq.
10
Eeral, (Eq. (13) and Eroil (Eq. (16), and the final step follows by optimism (Lemma The total sample complexity of our algorithm is: E, ((d) oracle calls, and Nneeval
3.5
H exploration cost. The last claim to verify is that of computational efficiency. We note that the only computationally intensive step from iteration is Line i.e. the optimization problem corresponding to the optimistic choice over the parameter set maxece.., 0 (ss)). This is readily seen to be convex program, since the objective is linear
EEa

---

function and the constraint set is convex set in R (it is initialized at Ou Ball,, (B) and every update intersects with half-spaces [7)) Besides the zorn constraint, all other constraints can be represented with línear program, since each absolute value constraint can be split into two inequalities. By Lemma the number of constraints will be at most 2 = (d) (and these can easily be converted to standard form). Thus, there are a plethora of polynomial-timg methods for solving this convex program [BBV04 Bub+15
3.2 Extensions
In this section, we show that DELPHT can be extended to work with optimization errors, under stochastic starting distributions, with misspecification, and with linear q" whenever dynamies are deterministic.
Optimization errors and stochastic start state If the optimistic program can only be solved
upto accuracy Sapt S CEvarget (for E [0. 1)) at each iteration, then Lemma 3.5 becomes Ug (8p) 2 e" (su) FEpp and this only appears in Eq. O We then need 5H t E I (I=c)Etarget: which is achieved by increasing Trollout and Reval by a factor of 1/(1-c)2. This increases the final exploration cost by 1/(1- For stochastic starting states, we simply work with uy (po) = Eesryu [vg (su)) (resp.
v" (Po)) wherever (so) (resp. v (so)) previously appeared. The "starting feature" E Esa (p())) must be estimated from samples, which is then used for the optimistic program in Line 5 with (psp)
replaced by this expectation. The error easily bounded as before by Hoeffding's inequality, and will simply propagate additively through the proof.
Misspecified value functions and innacurate simulators DELPHI inherits some robustness prop- erties from TensorPlan. Namely, with a constant increase in exploration cost, DELPHI continues to work under errors in the modelling assumptions. The first case is where the expert value function is not linear but rather is approximately linear up some uniform error. Formally, we say that the MDP 1y-misppecified for the expert policy л and the feature map yp if there exists 0 such that sup, (s) (f(s), | S. 7j. The second case is where the simulator itself is flawed. Formally, we say that the simulator is X-innacurate a transition (r, from any state-action pair (s, a) of the MDP is instead observed (II(r + )e,a), s'), where 11 is the projection onto [0, 1] and Ae. is constant uniformly bounded by X. The following result (proved in Appendix AA.5) states that DELPHI tolerate misspecification simulator inaccuracies of order roughly
O ((aa)-
Theorem 3.8 (DELPHI with misspecification). Redefine n' n'avat 4n eval (Eq.
12 and all subsequent
hyperparameters which depend on v' Then we have that, for all MDPs that are at most
Eavot
SvT.
misspecified or for all simulators that are at most East -innaccurate, the conclusions of Theorem 3.1 AvFE continue to hold when rumning DELPHI with the new hyperparameters.
dº -ineeriiy in deterministic dynamics Rather than working with the Bellman equation 09(s) T (s) we work with qo(s, a) T go(8, a), which can be linearized similarly to Eq. (5) Namely:
( ())
(r(s, a) @ (Bly(s', x (+)) a)), $ 0)
This derivation holds generally, although to be able to speak of consistency at (s, a) with respect to next action a', we now assume deterministic dynamics, so that the above becomes
0 (r(s.a) @ (p(s', a²) ppss, a)) A).
where s' is the unique successor of (s, a) and a' is the action that we are checking consistency for. The algorithm proceeds as before, except rather than checking all actions at given state (Line we check all proceeding actions a' against the current (s, a), and play the one with the smallest TD error (analogously to Line 20 of Algorithm IT.
'In fact, replacing On with an l.x. constraint will only incur d factor to the exploration cost and log factors the oracle cost (since think of B + VdB), but Line 5 will then be fully linear program.
7

---

4 How many oracle calls are necessary?
Is DELPHI optimal in terms of its number of oracle calls? To answer this question, we must argue that no algorithm can find an e e-optimal solution with less than ()() expert queries. As stated, we are competing with agents which can (for example) exhaustively search the state-space and do not refer to the expert at all. Thus, an exploration budger must be imposed (formally, a maximal amount of allowed interaction with the MDP, excluding oracle calls). To make matters more interesting, we set this cap to be any polynomial amount, resulting in the following question:
2.2 and 2.3 what is the minimal amount of expert queries needed for any algorithm with poly(d, H. A, () exploration budget to find an E-optimal solution?
Under Assumptions 2.7
We firsly note that, measured in the worst-case, this minimal amount of expert queries is strictly positive since there exists MDPs satisfying v* u"-linearity for which no algorithm can return a sound solution with poly(d, H, A. 4) queries [WAS21| WSG21]. Secondly, while it was possible to restrict ourselves simply to learners which have the same exploration requirements as DELPHI, , we opted to study algorithms with arbitrary polynomial exploration budgets, since it is a more fundamental question about the limits of exploration and the benefits of expert advice.
Note that any solution to this question must, a priori, have an exponential sample complexity for pure RL (otherwise the agent does not need to resort the expert). Interestingly, most constructions which exhibit exponential lower bounds for linearly-realizable RL can be solved with a single query from the oracle (e.g.. [WAS2I] [WK2T)) These constructions rely on having an exponentially large action set with single correct action that effectively solves the MDP. Our main lower bound comes from extending the recent lower bound of (WSG2I). which is also the only known construction for an exponential lower bound which has polynomial action set (rather than exponential). Our result is that at least $2( dd) oracle calls are necessary:
Theorem 4.1. There exists a family of MDPs satisfying 2.1 2.2 and 2.3 such that any algorithm with poly(d, dd H, A) exploration budget will need at least ([Vd) oracle calls to recover a policy such that a² (80) 2 v (so) - 0.01.
Our second lower bound considers an alternative assumption, which instead posits that the expert policy is linear. Formally, this assumption says:
Assumption 4.2 (T -linearity, with bounded features), The policy x² of the expert is linear with known features up : x A + Rd, i.e.
(s)s) argmax, (fps, 0?), Vs S,
(8)
for some unknown 8 E Rd \ {o} We further assume that [|x(())]22 S 1 Vs and that 110 < B for some known B E Rd.
When ~² π², is easy to see that this assumption is implied by the assumption that q" is linearly- realizable. In general however, qº -inneatry does not imply that T² is linear (see Appendix C for an example), although does imply that the greedy policy derived from qº is linear. We give lower bound for this case which matches the upper bound of DELPHI up to logarithmic factors.
Theorem 4.3. There exists a family of MDPs satisfying assumptions 2.1 4.2, and and 2uchh that any
algorithum with poly(d, H, A) exploration budget will need least Q oracle calls to recover policy such that of (so) 2 e (so) 0.01.
Intuition for the lower bound Theorems and use the same MDP construction but with different features. We give some intuition for the MDP construction which is used, but due to its intricacy a full description (and the information -theorretttthteeeeeeeoo proof) are deferred to Appendix B Loosely, the learner has to find a hidden hypercube vector s* E (+1) Jr. The action space is A = [p]. and each action corresponds to flipping one of the bits of the current vector. The MDP has K "phases" which each correspond to bit flips (thus H z Kp). A linear reward is given only if a sufficiently small neighborhood of 8* is reached, and the reward (thus the value) will decay geometrically in each subsequent phase that the neighborhood is not reached. Intuitively, the oracle needs to be used
We exclude 0 since otherwise this would simply be the class of all policies.
8

---

= p times, since each oracle calls only reveals one action, and thus one bit of the optimal vector s*. The reason that this results in S2(V lower bound (rather than (id)) is that the value function will experience scale transition when going from states where s* is reachable given the remaining steps in the current phase to states where s* is no longer reachable. As just described, the value (and thus the features) will be one order of magnitude smaller in this latter portion of the state space, As this would betray the location of the secret parameter, the value function is instead augmented to be quadratic in p (roughly, the product of the distance achieved at the end of this phase and that of the next phase), which requires that p x vd in order to observe linearity. On the other hand, the lower bound for 7 -linearity (Theorem 4.3 can remain linear in d, since the definition (Eq. 8 is scale-insensitive.
Closing the gap between our upper bound of ((d) and our lower bound of $2(Vd) remains a challenging but interesting question. In finite horizons, with access to a generative model or RESET method, we suspect that the only mechanism for creating hard MDP is by geometrically decaying the maximum possible value for each stage, such that at the final stage of the MDP the (random) reward becomes exponentially small in H (that is the approach taken here and in WAS21 WSG21) [ If the geometric decaying happens in "phases" then this implies that (1) of the value is located in the first "phase". The tension, then, is to have such construction while hiding this large value, and forcing the learner to rely on several oracle calls to find it. Prior constructions [WAS2I] WWK21 have hid the large initial value by choosing exponentially large action set, although as discussed above these examples are solved with a single query of the expert oracle. Extending the "needle in haystack" to occur over multiple decisions (cf. the "phases" used above) leads to increased oracle requirements, although due to the scale transition phenomenon observed above it is far from clear how to do this with phases of length Ri d. The question thus boils down to: is geometric value reduction necessary for exponential lower bounds in this setting, and if so can we avoid the scale transition problem? The situation is likely to be different in the online RI. setting. For example, the construction of [WWK2T] extends [WAS2T] to the online setting, and does not need to decay rewards but instead adds an 12(1) probability of death at every transition. This mechanism evidently does not work when the agent has resets, and since it is not known whether DELPHI can be extended to the online setting we opted to keep the settings consistent between our upper bound and our lower bound.
5 Related works
The closest body of work to our setting is the field of interactive IL. As in our setting, interactive IL considers the case where the learner has access to expert oracle that can be queried adaptively. differs from our setting, however, since traditionally in IL the learner does not observe reward information. We further differ from the IL setting since we consider value function approximation rather than general policy classes, and since we assume access to a RESET function. Despite that many demonstrations of interactive IL occur in simulated domains [RGB11] Ros13 RB14), the benefits of this feature have not previously been studied. Our assumption of v" linearity entails that many IL methods are not directly applicable. Indeed, the policy 'O itself does not need to be linear (despite that v is), so it is unclear which policy class to use for those algorithms. Assuming for the sake of comparison that linear policies can be used, IL methods would still obtain worse oracle rates. Indeed, using results from (AJKS19]. Behaviour Cloning (for the passive case) or
Aggre VaTe RB144 SVGBBI7 (for the interactive case) have worst-case errors O (111911 dln(1/8) for discounted MDPs, which roughly translates to an oracle complexity of N = (d /E²) when using the standard reduction H - (1 -1)-1. This is in sharp contrast to our ((d) oracle calls, which in independent of и/ and logarithmic in 1/e. and demonstrates the improvement due exploration with the help of value-function approximation. Beyond these approaches, another intuitive method would be to perform regression by doing a Monte Carlo estimation for the value of o (s(s for each s along a certain "good" set of features. This would require collecting rollouts from those states, which will again introduce factor of H in the number of oracle queries. Our algorithm instead finds a set of state-action pairs where the Temporal difference (TD) errors (which we represent as vectors) span orthogonal directions. These can be estimated with single transition, and this "local fitting" approach is novel to the II. literature and avoids the factors of H and 1/c from previous works.
'In particular, an exponentially small gap is necessary, since backwards induction -tppe methods are possible and have sample complexities scaling with the inverse gap (DKWY19 DLMW20
when 9" is
9

---

In terms of other linear structure in IL, the works of (AN04, SS07] assume a known transition function and unknown linear rewards, and derive expert complexities of O ddH² /e) and O H log(d) e²
E²
respectively, but the algorithms involve (tabular) planning in MDPs and thus are not computationally efficient. Most relevant is the recent work of [RHYLIR2I] which, in the reward- -ree case, assumes that the expert policy is linear (i.e., our Assumption 4.2 A sample complexity of (sdH/s) is shown for Behaviour Cloning in this case, though no lower bound is given.
On the technical side, the DELPHI algorithm is inspired by recent algorithm called TensorPlan [WAJAY]S2T]. TensorPlan works for pure RL under Assumptions 2.2 and 2.3 but has sample
complexity scaling poly( (H A -B) and is computationally intractable. Our extension of Tensor- Plan naturally incorporates the expert demonstrations, while simultaneously (1) having low oracle requirements, (2) addressing the exponential sample complexity of TensorPlan, and (3) rendering the algorithm computationally efficient. Our approach is based only on finding value functions which satisfy the Bellman equation. Bellman error minimization approaches have appeared in other works (c.g. [JLM2I] ZLKB20; (JT9)). but have always required a restrictive "Bellman closedness" assumption. As discussed, our lower bound construction is extension of the recent remarkable lower bound of [WSG21]. although several aspects of the construction have been modified to ob- tain better rates. In particular,
modified the reward/valus functions, the feature mappings, and introduced an expert policy which differs from the optimal policy. For the proof, our setting is more complex as the learner has adaptive access second information source (the oracle). and more sophisticated information-theoretie argument was needed to show that the oracle does not leak too much information.
6 Conclusion
We presented the DELPHI algorithm for RL with an interactive expert. We saw that, with ((d) oracle calls, exponential improvements in sample complexity are possible for RL with finearl--realizabee optimal value functions. Compared to prior works on learning with an interactive expert, we also saw that DELPHI'S 's oracle requirements were smaller, and in fact are independent of the horizon of the MDP. It would be interesting and fruitful to resolve the gap between the oracle complexity required by DELPHI and the one obtained from our lower bound (either answer would be surprising the authors). It would also be fruitful to study the case of linearly-realizable action-value functions in stochastic MDPs, which would potentially enable our method to be extended to the online setting.
Acknowledgments and Disclosure of Funding
PA gratefully acknowledges funding from the Natural Sciences and Engineering Research Council of Canada (NSERC). Work done in part while PA was an intern at Amazon.
References
[AJKS19]
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. "Reinforcement learn- ing: Theory and algorithms". In: CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep (2019).
[AJSWY20]
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. "Model- based reinforeement learning with value-targeted regression". In: International Conference on Machine Learning. PMLR. 2020, pp. 463-4744
[AN04]
Pieter Abbeel and Andrew Y Ng. "Apprenticeship learning via inverse reinforcement learning". In: Proceedings of the twenty-firs international conference on Machine learning. 2004, p. 1.
[BBV04]
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[Bub+15]
Sébastien Bubeck et al. "Convex optimization: Algorithms and complexity". In: Foundations and Trends in Machine Learning 8.3-4 (2015), pp. 231-357.
[CJ19]
Jinglin Chen and Nan Jiang. "Information-theoree considerations in batch rein- forcement learning". In: International Conference on Machine Learning. PMLR. 2019, pp. 1042-1051.
10

---

[DKWY19] Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. "Is good repre- sentation sufficient for sample efficient reinforcement learning?" In: arXiv preprint arXiv: 19 10.03016 (2019).
[DLMW20]
Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. "Agnostic Q- learning with function approximation in deterministic systems: Tight bounds on approximation error and sample complexity". In: arXiv preprint arXiv:2002.07125 (2020).
[FKQR21]
Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. "The Statistical Complexity of Interactive Decision Making". In: arXiv preprint arXiv:2 12. 13487 (2021).
[HLYAYS22]
Botao Hao, Nevena Lazic, Dong Yin, Yasin Abbasi Yadkori, and Csaba Szepesvari. "Confident Least Square Value Iteration with Local Access to a Simulator". In: International Conference Artificial Intelligence and Statistics. PMLR. 2022, pp. 2420-2425
[JLM21]
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. "Bellman eluder dimension: New rich classes of rl problems. and sample-efficient algorithms". In: Advances in Neural Information Processing Systems 34 (2021).
[JYWJ20]
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael I Jordan. "Provably efficient reinforcement learning with linear function approximation". In: Conference on Learning Theory. 2020, pp. 2137-2143.
[KMN02]
Michael Kearns, Yishay Mansour, and Andrew Y Ng. "A sparse sampling algorithm for near-optimal planning in large Markov decision processes". In: Machine learning 49.2 (2002), pp. 193-208.
[LCCGW21]
Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, and Yuting Wei. "Sample-efficient re- inforcement learning is feasible for linearly realizable MDPs with limited revisiting".
In: Advances Neural Information Processing Systems 34 (2021).
[LKFS21]
Gene Li, Pritish Kamath, Dylan J Foster, and Nathan Srebro. "Eluder dimension and generalized rank". In: arXiv preprini (0fi::20040067000 (2021).
[LSW20]
Tor Lattimore, Csaba Szepesvári, and Gellért Weisz. "Learning with Good Feature Representations in Bandits and in RL with Generative Model".. In: ICML. 2020, pp. 9464 94722.
[Put14]
Martin L Puterman. Markov decision processes: discrete stochastic dynamic pro- gramming. John Wiley & Sons, 2014.
[RB14]
Stephane Ross and Andrew Bagnell. "Reinforcement and imitation learning via interactive no-regret learning". In: arXiv preprini 1406. (2014). Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. "A reduction of imitation learning and structured prediction to no-regret online learning". In: Proceedings of the fourteenth international conference artificial intelligence and statistics. JMLR Workshop and Conference Proceedings. 2011, pp. 627-635.
[RGB11]
[RHYIJR21]
Nived Rajaraman, Yanjun Han, Lin Yang, Jingho Liu, Jiantao Jiao, and Kannan Ram- chandran. "On the Value of Interaction and Function Approximation in Imitation Learning". In: Advances in Neural Information Processing Systems 34 (2021). Stephane Ross. "Interactive learning for sequential decisions and predictions". PhD thesis. Carnegie Mellon University, 2013.
[Ros13]
[RVR13]
Daniel Russo and Benjamin Van Roy. "Eluder Dimension and the Sample Complex- ity of Optimistic Exploration." In: Citeseer. 2013.
[SB18]
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2018.
[SS07]
Umar Syed and Robert E Schapire. "A game-theoretic approach to apprenticeship learning". In: Advances in neural information processing systems 20 (2007). Roshan Shariff and Csaba Szepesvári. "Efficient planning in large MDPs with weak linear function approximation". In: Advances in Neural Information Processing Systems 33 (2020). 19163-19174.
[SS20]
[SVGBB17]
Wen Sun, Arun Venkatraman, Geoffrey J Gordon, Byron Boots, and J Andrew Bag- nell. "Deeply aggrevated: Differentiable imitation learning for sequential prediction" In: International Conference on Machine Learning. PMLR. 2017, pp. 3309-3318
11

---

[Sze10]
Csaba Szepesvári. "Algorithms for reinforcement learning". In: Synthesis lectures on artificial intelligence and machine learning 4.1 (2010), pp. 1-103.
[WAJAY]S21]
Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi- MadsiiYadkori, Nan Jiang, and Csaba Szepesvári. "On Query-efficient Planning in MDPs under Linear Realiz- ability of the Optimal State-value Function". In: arXiv preprint arXiv:2102.02049 (2021).
[WAS21]
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. "Exponential lower bounds for planning in mdps with lincarly-realizable optimal action-value functions". In: Algorithmic Learning Theory. PMLR. 2021, pp. 1237-1264.
[WR13]
Zheng Wen and Benjamin Van Roy. "Efficient Exploration and Value Function Generalization in Deterministic Systems". In: Advances in Neural Information Processing Systems. 2013, pp. 3021-3029.
[WSG21]
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: arXiv preprint arXiv:2110.0211 (2021).
[WWK21]
Yuanhao Wang, Ruosong Wang, and Sham Kakade. "An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap". In: Advances in Neural Information Processing Systems 34 (2021).
[ZLKB19]
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. "Limiting extrapolation in linear approximate value iteration". In: Advances in Neural Information Processing Systems 32 (2019).
[ZLKB20]
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. "Learning near optimal policies with low inherent bellman error". In: International Conference on Machine Learning. PMLR. 2020, pp. 10978-10989.
12


Reviews:
[{"review_id": "gyyaywi4x_", "reviewer": "Reviewer_v8cV", "summary": "Recent work has shown that linear realizability of the optimal value function is not a sufficient condition for sample-efficient RL (i.e. you need exponentially many samples to find a near optimal policy). This work shows that it is possible to learn a near-optimal policy using only polynomially many samples if the learner is also given access to an oracle it can query and which will return a “good” action at a given state. In particular, they show that if the value function of this oracle can be parameterized by a $d$-dimensional feature vector, then with $O(d)$ calls to the oracle, it is possible to learn a near-optimal policy using only polynomially many samples. In addition, a lower bound is given which shows that at least $\\Omega(\\sqrt{d})$ oracle queries are necessary for sample-efficient learning.", "questions": "None.", "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": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Understanding when sample-efficient learning in RL is possible is an important question that has been of much interest in recent years. This work makes a non-trivial contribution to developing our understanding of this. I believe it is interesting and not obvious that by making limited oracle queries a previously intractable problem becomes tractable, though I have some concerns on the rate (see below). \n\nWeaknesses:\n- I believe the primary weakness of this work is the gap between the $O(d)$ upper bound on the oracle queries, and the $\\Omega(\\sqrt{d})$ lower bound. It is easy to construct settings where $O(d)$ calls to an oracle trivially solves the problem. For example, if we consider a tabular MDP with $S$ states and $A$ actions, the typical mapping from tabular to a linearly parameterized MDP has dimension $d = SA$. In this setting, if we query an oracle $SA$ times, that will simply give us the oracle policy, and the problem is solved. A similar conclusion can be reached in linear MDPs. Even in the more difficult setting considered in this work, the proposed algorithm seems to be doing something similar: since it assumes the oracle policy has a linearly realizable value function, it essentially just queries it in a spanning set of directions, which allows the value function to be approximately recovered. It does not seem too surprising this is possible, but doing this in $O(\\sqrt{d})$ oracle calls seems much less trivial, as in that case the learner would have to do a significant amount of learning without relying on the oracle. Thus, I think closing this gap between $O(d)$ and $\\Omega(\\sqrt{d})$ is essential for this to be a convincing result, but I don’t think the style of algorithm proposed here is able to do this. \n- One suggestion for improving this would be to restrict the learner so it can only access the oracle in the state it is currently visiting. The proposed algorithm only requires this type of access, and it would make it at least somewhat less trivial to solve easier problems with an oracle, as some exploration would still be required. \n- Is the assumption that the oracle policy is linear in the features necessary? It seems essential to the algorithm. I don’t think this is a critical issue since, if we take the oracle policy to simply be the optimal policy, this will be satisfied by our linear realizability assumption, but relaxing this assumption would still strengthen the results. ", "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": "_R9gSLnosI", "reviewer": "Reviewer_TmTo", "summary": "Assuming that only the optimal value function is linearly-realizable for the homogeneous finite horizon MDP, this paper proposes a sample-efficient algorithm with access to interactive demonstrations from an expert policy.", "questions": "The authors exaggerate their results due to misunderstanding others' conclusions.", "limitations": "The authors exaggerate their results due to misunderstanding others' conclusions.", "rating": 5, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors exaggerate their results due to misunderstanding others' conclusions.\nSpecifically, the exponential lower bounds (w.r.t. $H$, $d$) in [WAS21] and [WWK21] are constructed based on exponentially large action spaces.\nAs far as I know, the prior arts only establish the $\\mathrm{poly}(d, H, A, 1/\\varepsilon)$ lower bound.\nThe authors should correct their claim throughout the paper, if they cannot provide the exponential lower bounds (w.r.t. $H$, $d$, $A$).\n\nIn addition, it seems a better result is given in [AJKS19] for the infinite horizon MDP, which I see in Section 5. \nIf this is right, the authors should discuss the difficulties of this extension.\n\nThe writing should be improved due to many typos.", "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": "9MgNM1IUYU", "reviewer": "Reviewer_oG41", "summary": "The paper studies the RL problem of approximating the behavior of an expert demonstrator in a setting where the learner is allowed to both interactively query the environment and query the expert. Under the assumption that the value function of the expert is linearly realizable in a known feature mapping, the authors prove that the Delphi algorithm finds an eps optimal policy using O(d) samples and polynomially many samples in the other problem parameters. ", "questions": "In L:124, the authors claim that assumption 2.1 is necessary. This isn’t supported by the theoretical results. The assumption is definitinitely sufficient, but it isn’t strictly necessary? There could be other assumptions (distinct from 2.1) that could enable sample efficient learning. \n\nI can see that the expert policy is consistent if it corresponds to the optimal policy, but why should we expect this to hold generically for non-optimal policies?\n\nIn Theorem 3.1, the authors claim that the algorithm is computationally efficient. What is the precise, formal statement here? There is no formal runtime bound that is provided.  \n", "limitations": "These are adequately adressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper makes significant progress towards understanding the possibilities (and limitations) of learning a good policy in MDPs under linear function approximation. They introduce a new (and sensible) sufficient condition for the problem to be statistically tractable. \n\nThe paper is very clearly written. It nicely communicates the intuition behind the algorithm and why we might expect it to work. The lower bounds on the number of expert queries that are necessary nicely complement the analysis of the Delphi algorithm and add to the picture of learning with expert demonstrations. The robustness results regarding mispecified dynamics and value functions are also interesting.  \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": "-CF_4Aq7IDe", "reviewer": "Reviewer_T4Ki", "summary": "This paper studies the problem of reinforcement learning of reinforcement learning with a linearly realizable optimal value function. While this problem is infeasible in general (as shown by recent lower bounds), this paper shows that two additional assumptions are sufficient for sample efficiency in this setting: O(d) queries to an expert and the ability to resample arbitrarily many times from the most recent state visited. A new algorithm is proposed that achieves poly sample complexity under these assumptions. Lower bounds are shown justifying at least O(\\sqrt{d}) queries from the expert.\n", "questions": "- While the paper’s theoretical contributions are already very strong, I am curious why there were no experiments, especially considering the algorithm is advertised as being computationally efficient? How do you think this algorithm will compare to IL algorithms like BC, Dagger, and Aggrevate? How would it compare to RL algorithms?\n- I’m also curious about how necessary Assumption 2.3 (resets) is. It is clear that it plays an important role in the proposed algorithm to identify states for which there is consistency. What seems to be the technical challenges needed to remove this? \n- Can you also comment on to what extent using Assumption 2.3 might be helping with the linear realizability assumption? For example, in some offline RL papers, one sometimes sees that double-sampling enables sample-efficient guarantees even with few assumptions on the function class (like completeness), so I am curious if something similar is happening under the hood here. Clearly resetting is not enough by itself given the existing lower bounds, but I am curious to know how much it helps / if it's necessary.\n\n", "limitations": "The limitations are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- In my view, the results constitute contributions to both reinforcement learning (specifically to the study of weaker forms of realizability) and imitation learning. On the RL side, we learn that a notoriously harder problem is solvable with a limited amount of side information in the form of expert actions. On the IL side, we get a clearer picture of how much interactive expert information is actually necessary to learn in a sample efficient manner.\n- The paper is very well written and easy to understand. It does a good job of placing itself in the literature and making clear what is and is not possible with existing results.\n- The insight of how to use the expert queries is interesting and seems to be new.\n\nWeaknesses\n- The algorithm requires a resetting assumption (this is weaker than a full generative model but stronger than the standard episodic RL setup)\n- There is a gap between the sqrt{d} lower bound and d upper bound.\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": {}}]

Author rebuttal:

Decision: Accept