Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper examines statistical guarantees of imitation learning under various regimes -- interactive setting, non-interactive setting, and non-interactive setting with known dynamics. It further looks at the linear setting and derives bounds for non-interactive settings with/without known dynamics. The main contributions are:
1. Interactive: To show that “reduction-based” online algorithms (DAGGER / AGGREVATE, DAEQUIL) have matching upper and lower bounds
2. Non-interactive: All such algorithms have O(H^2) bounds
3. Non-interactive + Linear + Parameter sharing: Recover O(H) bound
4. Non-interactive + Known dynamics + Linear: Introduces a new algorithm, confidence set linear classification, that achieves O(H^3/2) 

main_review: The paper addresses an important, yet under examined, problem -- what is the best one can expect from any imitation learning algorithm under various settings? The contributions in examining the linear setting are particularly important, one hopes functional analysis (RKHS) soon follows. 

I very much enjoyed reading the paper. It made central ideas accessible to the reader. I much appreciated the effort put in the introduction to give the reader a broad view of the key results. 

The two main strengths of the paper are:
1. Technically sound [4/5]: While some of the proofs get a bit hairy, there is adequate hand-holding and it is clear that the authors wield technical theorems in an adept manner
2. Significance of claims (if true) [4/5]: In particular, the linear analysis potentially paves the way for a full RKHS analysis and that would be truly consequential. 

However, there are two main shortcomings that keep the paper from being a strong addition to the body of imitation learning knowledge: 
1. Contented contributions [2/5]: There appears to be contributions that are either incorrect or misinterpreted, and others that are previously established and refined here. Clarifying / removing these would sharpen the contributions this paper has to offer.
2. Clarity of exposition [3/5]: For practitioners in IL (which is still a large majority), this paper is hard to read and glean insights from. Insights are often lost in the paper and a concern is that the consequences of the theory presented in this paper may be lost on its readers. \

I will now expand on the two shortcomings

## Contented contributions
Before going into individual contributions, I would like to flag that there is a recent paper that appear to make a subset of the claims presented here that the authors do not cite:

Swamy et al. “Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap” (ICML 2021) https://arxiv.org/abs/2103.03236 

For instance, Swamy et al. also have a notion of \mu-recoverability (Def 3) and express bounds as a function of \mu. Hence, for overlapping claims (some of which I will attempt to call out), it would be useful to clarify the differences between them. I will henceforth refer to this paper as Swamy et al.

1. Interactive setting (matching upper and lower bounds) [Informal Theorem 1, Formal theorem 2,3]: 
The upper bound is similar in form to Swamy et al. (as well as Dagger), i.e. \mu H \epsilon, where \epsilon is the per-step loss (I would imagine that would be of the order of |S| / N). The lower bound appears to be sharper than Swamy et al. (H \epsilon), and perhaps this is worth calling out.

The devices used in the upper bound proof also follow from reduction of imitation learning to online learning (learner provides a policy, receives a loss). Hence, it is unclear what this theorem adds to what is already established.

2. Non-interactive setting (Informal Theorem 1, Formal Theorem 2) The O(H^2) is a well known result and the proof uses an MDP very similar to the one used in “Efficient Reductions for Imitaiton Learning”  (http://proceedings.mlr.press/v9/ross10a/ross10aSupple.pdf), notably Figure 1. 

3.  L.105, the authors mention “this is the first result to establish a clear separation in statistical minimax rate of suboptimality..”. This claim is not substantiated, and at the very least requires a clear comparison to Swamy et al. which does not make such a claim but conveys results of the same kind. 

4. Non-interactive setting + Linear + Parameter sharing (Informal Theorem 4, Formal Theorem 5): The claim that parameter sharing results in a reduction from O(H^2) to O(H) appears to be incorrect. Notably in Lemma 1, \gamma can be very high which would make the bound in Lemma 1 H\gamma ~= H, i.e. trivial. 
 
Taking a step back, it’s totally common to share parameters in behavior cloning (i.e. have the same weights for all timestep). The update in (4) would add up the errors over timestep and be exactly the supervised learning loss. \gamma can be high, and in fact be masking a H term, i.e. gamma = H \epsilon. 

5. Non-interactive + Linear + Known dynamics (Informal Theorem 5, Formal Theorem 6) 

Swamy et al. show that in this setting it is possible to get O(H \epsilon) though one needs a “planner” (ala MaxEnt IRL Ziebart et al.) to search over the sequence of actions. I was surprised to see no such discussion in this theorem although Mimic-MD clearly requires such a planner in step 6. Moreover, while O(H^3/2) seems to be a clear improvement over BC, O(H), it’s still not the same order as the bound O(H). Clarifying the significance of this result w.r.t to Swamy et al. would be useful. 

6. Informal theorem 6 (formal theorem 7): This indeed appears to be the novel contribution. I struggled to follow the proof entirely but trust that the authors got it correct. 


## Clarity of exposition
I’ll go over the paper chronologically and identify areas where the writing was unclear / there were typos.

Section 1: Introduction

* Should have been at most 2 pages. There was no need to have so many definitions up front. Certainly no need to even talk about linear results. Instead, I would have structured it to talk about the 3 regimes of IL, talk about the key results in each regime and have forward pointers to theorem in the paper. There is no need to state things twice. 
* I would massively compress Def 4 onwards till the end. The only thing interesting there is the O(H) from parameter sharing and O(H^3/2) for known dynamics. 
* I would keep the parts that  convey insight (L.59-66, L.73-79,L.155-165).
* L86. - 90: Unclear why reduction based approach fails to distinguish between power of learners. The authors claim they circumvent reduction based guarantees, but they don’t in their proofs (reduce it to FTRL). 
* L.131: Classic supervised learning in IL does indeed use multi-class classification algorithm (for discrete actions > 2). 

Section 2/3

* Move the definition here
* Theorem 1: Explicitly mention realizability assumption here. 
* Theorem 3: Probably want the figure from appendix to be moved up here. 
* L307: should be \theta^* without the _t subscript
* L310-313: Unclear what is meant by separable and Markovian here. The point is unclear as well. 
* L316: The reader is still left trying to understand why, by mere rephrasing of the problem, the bound goes from O(H^2) to O(H). It feels like a smoke and mirror trick. The intuition is that to get such a reduction, surely we are paying elsewhere for added complexity (reasoning in the space of trajectories). That needs to be made clearer.

Section 4


L333: OPT: \tilde(J)_r(\pi^*)
Also one needs to explain how to solve OPT in practice and that it is hard.

Also, what if the reward function is only a function of state and not state action. Does this entire section fall apart? (Presumably no, but unclear)

Eq (5) explain E^c. 
L340: Simple empirical estimate -- unclear from what distribution. Please explain mathematically

Alg 1, Line 6. \tilde(J)_r(\pi^*)

Appendix:
L565 tr_i should be \pi_i

L604: Wrong theorem (state the active setting)

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary:  The authors study statistical guarantees for the Imitation Learning problem, for many settings: considering or not the possibility of interacting with the environment, using the \mu-recoverability assumption, and assuming linear function approximation. Furthermore, they introduce a new setting, called confidence set linear classification.
main_review: ## Originality: 
The main novelty consists in the analysis proposed by the authors, which allows to determine theoretical properties, improving some pre-existent results. Moreover, they introduce and study a new setting.

## Quality:
The applied methodology seems to be sound, and the work is complete, analysing a spectrum of interesting cases.

## Clarity: 
While the paper is clearly well written, the structure of the whole work can be improved. The authors tried to summarize in the introduction the main results provided, by means of informal theorems and definitions. I would suggest to keep a more traditional informal introduction, in which formulas and statement are few, and the main ideas are explained by words. Consequently, I would suggest to add a preliminaries section, where both the notation part and the definition could fit more.

## Significance:
The work offers important statistical guarantees for different settings, advancing the state of the art. The obtained results are likely to be useful for other researchers to build on them.
limitations_and_societal_impact: No potential negative impact is present.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: They study imitation learning in several variations, in particular with interaction (i.e., the expert can be queried during training) and without. And under some interesting additional assumptions, such as mu-recoverability (i.e., if the imitator visits suboptimal states, this has small impact of the overall value, by being able to go back to optimal easily).

They provide several theoretical results, 
- negative ones -- i.e., lower bounds on the suboptimality that can be achieved in terms of difference of imitator versus optimal expert value incurred -- as well as 
- positive ones -- algorithms that achieve linear instead of quadratic suboptimality, in particular their main contribution thm4. This works by reduction to supervised learning paradigm sample bounds.

As a means to this, they also have a little taxonomy on versions of IL.

One thing that's hard to judge for me is novelty. I feel this is novel, but I'm not sure how much overlap there is with DAgger and all the subsequent work in this direction, not an expert on this.
main_review: Overall this is an interesting paper, addressing common IL settings, providing non-trivial theoretical contributions. 

The reduction-based approach to thm4 looks powerful (though reduction, I guess, are not new for this but originate from DAgger etc.). 

The little IL taxonomy (Def1, 2, ...) is interesting in itself.

Some of the proofs look non-trivial.

Quality-wise, I have not checked details, but the theorems and proofs seem to be stated with care.

Style of writing is OK-good.
limitations_and_societal_impact: Small limitations include:
- I'm surprised that one of the most common settings -- no interaction, but being able to sample from the dynamics -- is not discussed. However, I guess Def6 is a close enough approximation to this for the sake of this paper.
- How limiting is the linear expert setting? Linear would be pretty limiting, but I guess it's only linear in the features which would be quite general again.
- There are no experiments but that's OK given there is enough conceptual and theoretical contribution.
- I have not read the full paper. Some writing may be premature -- e.g. l98 "regard. idea is crucial" -- but this seems neglectable.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates statistical guarantees for imitiation learning (IL) under the $\mu$-recoverability assumption of [27]. The authors prove  bounds on the sub-optimality of any algorithm which does not interact with the MDP and uses an offline dataset. Under linear function approximation, the authors prove bounds on the suboptimality of behaviour cloning.
main_review: Overall I found this paper to be quite good, for which I am recommending an accept.

I really appreciated the informal theorems presented before the real theorems, as they help in the clarity of the paper.

I think the proofs in the Appendix could be clarified and extended to make it easier for more readers to follow, as currently it seems to be written for an audience that is already quite familiar with that type of theoretical work.

More details below.

## Questions / Comments
1.  What exactly does "0-1 loss" mean in line 84?
1. In line 92, why does $\hat{\pi}$ denote the learner, if the policy is continuously changing? Relatedly, in line 93 does $J(\hat{\pi})$ represent the policy at convergence? Same question on line 103. The phrasing used in informal theorem 3 seems better for this.
1. Does the negative result of informal theorem 2 not hold for $\mu < 1$? Why not?
1.  The term "statistical minimax rate" is used quite a lot in the paper but never explicitly defined. It would be good to define for clarity.
1.   In line 149, "it is known from [22] that...", is this also under the assumption of deterministic transitions, like in the current paper?
1.  In line 168, if $h^{*}$ is defined as an $\arg\max$, shouldn't you use "$=$" instead of "$\sim$"?
1.  Please define $\mathbb{S}^{d-1}$ in line 188.
1.  In line 193, the term $d^{3/2} / N$ seems to suggest that there is a tradeoff between expressivity (large $d$) and vacuosity of bound (small $d$), since $d \ll |\mathcal{S}|$ likely incurs larger $\mathfrak{R}$. Is this the case?
1.  In line 230, shouldn't it be $\hat{\pi}^1,\cdots,\hat{\pi}^T$?
1.  In line 237, isn't the second term of the _empirical online-learning regret_ just zero?
1.  The statement in line 245: "By scaling each reward..." seems a little strange. Presumably $\mu$ has relevance under the assumption that the rewards are in $[0, 1]$ (as stated in the introduction). But just scaling the rewards, while not changing optimal policies, _does_ change the meaning and tightness of suboptimality bounds (e.g. I can make the bounds arbitrarily small by scaling the rewards). I guess this is for the lower bound, so it's ok? On this note, is $\mu$-recoverability necessary just so you satisfy the the existing theorem's requirements (from [22])?
1.  In Theorem 3, it seems the lower bound would be of more use if it depended on $|\mathcal{A}|$ instead of $H$.
1.  In line 322, I think you need to add "with probability $1-\delta$" to the end of the sentence.
1. In Section 4 you should specify from the beginning that you are considering the case when $P$ is known (this is only revealed once you reach the Algorithm).
1.  In Algorithm 1, it would help clarify things if you highlight with a different color what is different from the original MIMIC-MD.
1. In equation (8), what is $-\mathcal{K}$?
1.  In line 564 of the Appendix, it says "samples the policy $tr_i$", do you mean policy or trajectory?
1.  In line 565 it says "rolling out $tr_i$, should this be $\pi_i$?
1.  In line 568, what does it mean to be rolled out and conditioned on $\hat{\pi}^i$?


## Minor comments
1.  What do you mean by "nicely" in line 29?
1.  What do you mean by "game AI" in line 37?
1.  Throughout the paper the authors use numbered citations as nouns (e.g. "[25] study BC from a theoretical..."). You should use something like "Ross & Bagnell [25] study BC from a theoretical...". This is especially problematic when you start sentences/paragraphs like this, as you do in line 320.
1.  In line 81, in the expectation subscript, use $a'$ (instead of $a$) to avoid confusion, as $a$ already has a different meaning.
1.  Line 87, the sentence "the size of expert dataset / number of MDP interactions, N in the no-interaction / active settings." reads weirdly, consider rephrasing.
1.  Line 89, should be "propose **a** policy".
1.  In line 98 a sentence starts improperly ("idea is crucial...")
1.  In line 130 please state what ERM stands for.
1.  Line 146, should read "provied **a** dataset $D$".
1.  Line 164, should be "output" instead of "otput".
1.  Section 1.1 (Related work) seems out of place where it is, as it interrupts the narrative flow. Consider putting at the end of the paper.
1. Line 235, should be "a measurable function **of** the first".
1.  Line 282 should be "upper bound" (singular, not plural).
1.  Line 311, what do you mean by "By contradiction"?
1.  In the paper use \restatable so that the theorem statements are reprinted in the Appendix.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This is a good paper that studies the statistical properties of imitation learning under various regimes, e.g., interactive, and several non-interactive settings. The reviewers found the paper technically sound and the results significant.

The shortcomings of the papers are:
- Not citing and comparing with a recent paper by Swamy et al., ICML, 2021. Some of the results of these two papers are comparable.
I believe this omission in the initial submission is acceptable, given the recency of the paper and that its arXiv version was uploaded on 4 March 2021, relatively close to the NeurIPS deadline. That being said, I encourage the authors to provide a detailed comparison with that work.
- The exposition can be improved, for example, how the Introduction is presented.
Please consult the reviews for concrete suggestions.

Overall, I believe this paper should be accepted.
Decision: Accept (Poster)