Venue: NeurIPS 2022 Conference

Reviews:

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: This paper studies the problem of classification-based online imitation learning, and shows a negative result that any proper learning fails to achieve sublinear regret.
The main contributions include:
  - Theoretical guarantee for drawbacks of proper online learning
  - An improper online learning algorithmic framework
  - Efficient algorithms to deal with computational hardness

strengths_and_weaknesses: - Strengths
  - The paper proves that proper learning fails to achieve sublinear regret in COIL setting.
  - The paper proposes a clear convex combination to construct mixed policy class so that online regret minimization in IL becomes an online linear optimization problem.
  - The paper proposes Theorem 13 to show that all problems in PPAD are solvable in randomized polynomial time under some specific circumstances in COIL setting.

- Weaknesses
  - [12] already gives a general online convex optimization formulation for online IL, so it seems that linear optimization is covered.


questions: N/A
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors provide (1) an impossibility result for obtaining sublinear regret in general online learning settings, (2) present an online linear optimization algorithm (LOGGER) which uses policy mixtures to improve sample / complexity interaction guarantees over behavioral cloning algorithms, and (3) they show that achieving sublinear dynamic regret is still impossible in the LOGGER framework.




strengths_and_weaknesses: ## Strengths
1. The authors combined analysis which composes sample complexity and interaction round complexity is extremely interesting, and to my knowledge novel in the area of online imitation learning.
2. The list of assumptions required in proving the results given by the authors is clear and precise. 
3. The use of "separator sets" by the authors seemingly opens up a couple fun algorithmic questions that can take advantage of existing research from support vector machines and active sets. 
4. Proposition 2 creates an interesting link between exploration in online imitation learning and recent results in over-parameterization in online convex optimization~[1,2].

## Weaknesses 
2. Proposition 6 seems like a restatement of one of the theorems in [1], or perhaps a special case. 
3. The assumption regarding mu recoverability seems to implicitly impose some constraints on the space of MDPs that are not likely to be realistic in practice. 
5. All analysis are completed in a a discrete finite state-action Markov decision process, making the utility of such analysis unlikely to be directly applicable to practical applications and studies.
6. No experimentation or code is included with the work, making it difficult to determine if the algorithms proposed are actually possible to implement.

questions: ## Abstract 
1. Please fix the spacing in the abstract. 

## Background
1. The assumption about labeling of the expert examples seems unrealistic. In most settings checking if something is an expert action requires the same effort as just providing the binary value provided in your framework (unless you are using human in the loop RL for language tasks possibly). It makes sense why this is a much more difficult form of feedback to optimize with, but making the distinction between this and more common assumptions should be included. 
2. Theorem 4 seems similar to impossibility results from the reinforcement learning theory literature. This impossibility result is also somewhat confusing considering your previous result which uses effectively they same type of feedback, with what amounts to less information (e.g. binary feedback telling you if you were wrong, versus feedback telling you if you explicitly how much worse you were then the expert). Can you clarify intuitively why your result makes sense. 
5. Can you clarify the statement made in line 206 "equivalent to drawing a freshly new policy ...", are you sampling without replacement from the set B? If so does this not enforce additional requirements on the policy class not included in your list of assumptions?
6. Proposition 6 seems strictly worse then the results presented in [1]
7. Does the assumption regarding mu recoverability implicitly impose constraints on the space of MDPs that are not likely to be realistic in practice.
 
## Efficient algorithms with static regret guarantees
1. Text error on line 261 
 
## Potentially relevant citations
[1] https://arxiv.org/abs/2007.02520

[2] https://arxiv.org/abs/1809.02864

[3] https://arxiv.org/abs/2006.06835
limitations: The most important limitation of this work, is that it proposes a framework which creates a trade off between sample efficiency and oracle query efficiency, but provides no experimentation of such an algorithm. If the multiple variants of LOGGER are not possible to implement in practice, this should be stated explicitly. If they are, a simple toy experiment would be useful to illistrate to the reader how such an algorithm function, and whether or not there are any hidden constants in the bound or the algorithm definition which make it intractable in practice.
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: This paper studies the fundamental problems of classification-based online imitation learning. A framework called COIL is developed, and several contributions are achieved. First, like Cover's impossibility result, this paper shows there exists a hard instance, such that any proper online learning algorithm must suffer a sublinear regret. Second, an algorithmic framework called COIL is developed, which reduces COIL to online linear optimization. Third, two algorithms, LOGGER-M and LOGGER-ME, are proposed with provably efficient sample and interaction round complexities. This paper argues that these algorithms can be better than BC. Finally, this paper discusses why efficient dynamic regret minimization is inapplicable in the LOGGER framework.


====

After discussion, the authors have addressed my concerns. I am glad to see that this paper makes a remarkable step in the non-realizable cases. I believe such results could help us better apply imitation learning algorithms in practice. Accordingly, I raise my score from 5 to 7.
strengths_and_weaknesses: **Strengths**

- Several new theoretical contributions to the online imitation learning field. Like Cover's impossibility result, Theorem 4 shows that without reachability or randomization, it is impossible to achieve a sublinear regret.
- By considering mixed policy classes, new algorithms LOGGER-M and LOGGER-ME are developed. 

**Weakness** 

- Motivation is weak. This paper claims that the prior frameworks like DAgger have two issues: 1) applying rule-based policies is hard; 2) optimization of such policies is tricky (because of the convex realization). These issues depend on specific applications. It seems that they are not fundamental issues.
- The BC's guarantee is weaker, and the improvements over BC are questionable. The direct reduction of BC to supervised learning yields a loose bound, as shown in [1]. The expert annotation complexity of BC should be \widetilde{O}(H^2/\epsilon) rather than \widetilde{O}(H^4/\epsilon^2). 

---

[1] Rajaraman, Nived, et al. "Toward the fundamental limits of imitation learning." *Advances in Neural Information Processing Systems* 33 (2020): 2914-2924.
questions: - Can the authors help explain the computation benefits of LOGGER-M and LOGGER-ME?

In Section 3.2, this paper argues that regret-minimization algorithms like Hedge has a computation issue, i.e., O(B) complexity. I believe this is not a big issue. Furthermore, I do not find the discussion about the computation efficiency of LOGGER-M and LOGGER-ME in Section 4. I hope the authors can help explain this point. 

- What are new messages compared with the prior work [2]?

I find this paper lacks a discussion with the prior work [2], in which it is shown that (with realizability assumption), an online IL algorithm can solve the COIL studied in this paper. Furthermore, a separation between the online and offline settings is established to help the readers understand the fundamental limit. I wonder whether there are new messages in this paper. 

- Is the theoretical guarantee for BC tight?

[1] proved that the expert annotation complexity for BC should be $\widetilde{O}(H^2 S/\epsilon^2)$, if there is no approximation error. I believe this result is true even though there is an approximation error. The analysis in the appendix may be loose. For the approximation error of BC, due to the $\mu$-recoverability assumption, I guess the tight dependence should be $\mu H$ rather than $H^2$.  

--- 


[2] Rajaraman, Nived, et al. "On the Value of Interaction and Function Approximation in Imitation Learning." *Advances in Neural Information Processing Systems* 34 (2021): 1325-1336.
limitations: This paper studies classification-based online imitation learning (COIL). By the powerful techniques from the online optimization literature, new theoretical results are obtained in the context of imitation learning. Some theoretical results can corroborate some discussions in [3]. Though this paper has fruitful results, I am worried about the implications of these results. 

What are new messages? (compared with the old paper like DAGGER and the new paper [2]) How can the theoretical results of this paper guide practice? This question is related to the remark in the conclusion part. What kind of experiments do you want to conduct to empirically evaluate algorithms?

This paper is well written. A minor issue is a claim in the introduction (Line 30 and 31). In general, interactive IL can not be better than its offline counterpart; see [1]. Only under suitable assumptions, interactive IL can have superior performance; see [2]. A side message is that for tasks similar to the lower bound in [1], online algorithms cannot help. This message is important for practitioners. Please consider clarifying this misleading claim.

I am willing to recommend accepting this paper if the above concerns can be well-addressed. 

---

[3] Spencer, Jonathan, et al. "Feedback in imitation learning: The three regimes of covariate shift." *arXiv preprint arXiv:2102.02872* (2021).
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: This paper investigates the fundamental feasibility and statistical limits of designing oracle-efficient regret minimization algorithms in the setting of classification-based online imitation learning. Specifically, the paper shows that any proper algorithm is unlikely to achieve a sublinear regret (similar to the Cover's impossibility theory). Inspired by this observation, the paper propose an improper online learning framework that is equivalent to online linear optimization with the help of a mixed policy class. This framework allows us to design oracle0efficient algorithms with different sample/interaction round complexities.
strengths_and_weaknesses: Strengths
- The paper is a solid theoretical work that studies the fundamental limitations of classification-based online imitation learning and propose a new algorithmic framework to bypass the fundamental challenges.
- Good presentation quality with nice discussions about the connection and differences to previous works.

Weaknesses
- I do not find any technical issues. It would be very helpful if there are some experimental results (at least on some toy settings) to demonstrate the practical value as well as to make the key insights easier to understand.
questions: I note that theorem 4 is based on the assumption that the expert's feedback is of the form $\zeta_E(s,a) = A^E(s,a)$. How does this choice affect the results and can we use other choices like direct expert annotation (zero-one loss, which seems more practical or easier to obtain in practice)?
limitations: Limitations and potential negative societal impact of their work have been properly discussed.
review_title: null

Meta-review: metareview: This paper studied imitation learning in the classification setting. The paper shows that using proper online learning algorithms is not sufficient to obtain sublinear regret, and devises an improper learning framework that relies on online linear optimization resulting in provably efficient algorithms. 

All the reviewers appreciated the theoretical novelty and are unanimous in their decision to accept the paper. Please incorporate the reviewers' feedback and the resulting discussion. Adding in some basic experimental results (outlined in the "Experimental plan" comment) would strengthen the paper. 
confidence: Certain
Decision: Accept