Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 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.

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.
- 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.
- The insight of how to use the expert queries is interesting and seems to be new.

Weaknesses
- The algorithm requires a resetting assumption (this is weaker than a full generative model but stronger than the standard episodic RL setup)
- There is a gap between the sqrt{d} lower bound and d upper bound.

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?
- 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? 
- 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.


limitations: The limitations are adequately addressed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: 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.
strengths_and_weaknesses: The authors exaggerate their results due to misunderstanding others' conclusions.
Specifically, the exponential lower bounds (w.r.t. $H$, $d$) in [WAS21] and [WWK21] are constructed based on exponentially large action spaces.
As far as I know, the prior arts only establish the $\mathrm{poly}(d, H, A, 1/\varepsilon)$ lower bound.
The authors should correct their claim throughout the paper, if they cannot provide the exponential lower bounds (w.r.t. $H$, $d$, $A$).

In addition, it seems a better result is given in [AJKS19] for the infinite horizon MDP, which I see in Section 5. 
If this is right, the authors should discuss the difficulties of this extension.

The writing should be improved due to many typos.
questions: The authors exaggerate their results due to misunderstanding others' conclusions.
limitations: The authors exaggerate their results due to misunderstanding others' conclusions.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: 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.
strengths_and_weaknesses: Strengths:
- 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). 

Weaknesses:
- 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. 
- 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. 
- 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. 
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 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. 
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. 

The 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.  

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. 

I 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?

In 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.  

limitations: These are adequately adressed.
review_title: null

Meta-review: metareview: We thank the authors for their submission.

The paper studies finite-horizon MDPs in which *only* the optimal value function is realized by a linear function. The learner has access to the MDP via a generative model and has to minimize its sample complexity for finding a policy with approximately optimal value function. This was shown by prior work to require a number of samples exponential in the problem parameters.
Contributions: First, an algorithm that guarantees polynomial sample complexity if the learner has additional access to $O(d)$ expert demonstrations. Second, a lower bound of $\Omega(\sqrt{d})$ on the required number of expert queries. 
The work adds to our understanding of when MDPs with linear function approximation are solvable, showing that a hard RL problem becomes easy with a small amount of additional information. It is very well-written.
confidence: Certain
Decision: Accept