Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper investigates approaches to curriculum design for teaching via demonstrations, unifying two models in the literature. Some theoretical results are proven and experiments show the effectiveness of the approach. 
main_review: The paper presents a unified approach to curriculum design for MaxEnt-IRL and CrossEnt behavioral cloning. The primary contributions appear to be a teaching approach that does not require direct access to the learner's internal parameters, theoretical results regarding convergence rate, and modest sized empirical demonstrations of effectiveness. 

Positive aspects: 
- The problem of curriculum design is interesting and important, and compelling theoretical results are relatively limited at this time. 
- The proposed approach based on difficulty scores is interesting. 
- The empirical results are nice, if a bit modest in scope. 

Weaknesses: 
- The review of literature was somewhat limited. In particular, there are several papers by Mark Ho and Michael Littman and colleagues that seem relevant. 
- The motivation for difficulty scores was weak. In particular, it seems connected to the broader class of approaches that trade off effort of the teacher and effect for the learner that appear in probabilistic formulations. 
- The paper is rather niche. The theoretical results appear to be limited to the two approaches considered, and not general to curriculum learning. The empirical demonstrations are on small scale gridworld style problems. The exposition does not flow particularly well in that there are terms used without introduction, motivations for choices early in the paper are explained later, etc. 
- Although the paper is billed as being about curriculum learning theory and applications, it is not general enough to live up to these promises. 

Detailed comments: 
- "much less work is done from the teacher’s point of view to reduce the number of demonstrations required to achieve the learning objective" There is a literature on Teaching dimension that is relevant. Also see Optimal Cooperative Inference. 
- There is relevant work by Mark Ho, Michael Littman and others that does not appear to be reviewed. 
- "We define difficulty scores for any demonstration" Please define terms such as "difficulty scores" when they are introduced. 
- "We then study the differential effect of the difficulty scores" What does this mean? 
- "We adapt our curriculum strategy to utilize domain knowledge, in the form of task-specific difficulty scores, when the teacher’s optimal policy is unknown." What does this mean? What constitutes domain knowledge? What are difficulty scores? Teacher's policy unknown to whom? 
- ", the teacher could approximately infer the policy πLt by probing the learner and using Monte Carlo methods" Probing the learner? 
- "Leads to CUR teaching algorithm" How does it lead to it? 
- Self-curriculum is not defined. 
- I had trouble understanding the feasible set introduced on lines 142-143. The difficulty values are the same or different from difficulty scores? What type are they? 
- "In our experiments we relax the simplification" What does this mean? 
- Rather than using the phrase "differential effect" it would be clearer to just say what the effect is. Differential effect is not that helpful for the reader to whom the details have not been explained. 
- " The result is analogous to that obtained for linear regression" Analogous how?  
- I do not support the choice to put the technical details on nu_t in the appendix. One could at least give the reader a flavor. 
- "Theorem 1 motivates our curriculum strategy in Eq." How? Also, the ordering of the exposition is not ideal, given that Eq 1 appears much earlier. 
- In theorem 3, what does it mean for the convergence rate to be "roughly" something? 
- The use of a scheduling mechanism is fine in principle. But it is important to assess all algorithms on the same footing, so we can differentiate between what is due to the algorithm and what is due to the training approach. It is not ideal to put details relevant to understanding performance in the appendix. 
- " This clearly shows the effectiveness of our proposed ranking strategy that combines the two difficulty scores" This does not seem quite accurate. The result shows that both difficulty scores matter. I do not believe we can tell what it says about the particular manner of combining them. 
- "Our work provides theoretical underpinnings of curriculum design for teaching via demonstrations, which can be beneficial for education applications and faster training of IRL/BC learners across application domains." This is a huge overstatement. 
limitations_and_societal_impact: No limitations were discussed. Societal impact was not discussed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of providing experts demonstrations
to a learner, modeled as a Maximum Entropy IRL or a Cross Entropy
Behavioral Cloning algorithm, in order for them to achieve a target
performance on some task. The key contribution of the paper is to
provide a demonstration ranking strategy which can be greedily
utilized to define a curriculum. This strategy resulting in
convergence for both types of learners. Importantly, and in contrast
to prior work, this approach can be done in a manner that does not
explicitly see the learner's internal dynamics.  Moreover, in the case
of the maximum entropy IRL (with deterministic dynamics), the prove
that the convergence is logarithmic. Finally, they show the efficacy
of this approach in various domains.


main_review: The considered problem of efficiently teaching common learning from
demonstration algorithms is certainty interesting and has a number
of theoretical and practical applications. For example, there is a 
large body of literature of treating humans as maxEnt IRL learners
and optimizing the informativeness of demonstrations, particularly
in the context of human robot collaboration.

The key contribution of this paper, the ranking function, is fairly
simple to compute both directly given the learner's internal state
as well as empirically using monte carlo methods. As such, this
work opens up several possible applications compared to prior work.

An interesting feature, although whether it is a positive or negative
feature is another question, is that the convergence guarantees are
agnostic to the particular MDP being considered. One would naturally
expect that some MDPs are "easier" than others, but this is not
reflected in the bounds. An MDP sensitive analysis while more
difficult, may give a much sharper characterization of the learning
curves observed in practice.

My primary concern with the paper was the simple setting of
deterministic dynamics for maxEnt considered (although weakened in the
experiments). While the convergence guarantees are fairly strong, its
unclear to me if this should be expected to hold in more general
dynamics or is a special feature of the deterministic setting.

That said, the empirical evaluation seems to suggest that the
curriculum really does make a difference compared to an agnostic
teacher which is un-aware of the trace level difficultly.

## Minor points
Unless I'm misunderstanding, t, seems to be used in multiple ways,
both as the demonstration index and the time within an episode. 

Should the footnote on the bottom of page 3 point to section 4?

The technical details of eta would really be nice in the main draft.
limitations_and_societal_impact: This approach extends the theoretical understanding of teaching to existing algorithms and potentially enable new forms of human robot interaction. None of these are particularly concerning and I would argue this work is a net positive impact.

Regarding the limitations, the primary limitation (acknowledged in the conclusion) is the sharpness of the convergence bounds for cross entropy and extending to more general dynamics. That said, I feel that it is perfectly reasonable to leave these as future work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors introduce a new method for imitation learning, and more specifically, for selecting an expert demonstration that is maximally useful for the learner.
main_review: **Originality:** 

The method that is introduced here is not inherently bad but it only appears to work on small isolated grid world problems in which all states and actions can be enumerated. I believe that with automatic curriculum methods like DAGGER [1] and AGGREVATE [2] (which work in continuous state/action spaces), and astounding results such as "Learning to drive in a day" [3], the relevancy of this contribution is questionable at best. I guess the only way to convince me otherwise would be to include experiments in continuous state/action space but I don't think this can be part of the discussion period.

The authors also omitted a related literature section and instead list a few related works in the introduction, which does not help separate this work clearly from its predecessors.

I also feel like Behavior Cloning is treated as state of the art for imitation learning and from my best understanding that is the most naive possible approach. Some more contemporary baselines are DAC [4], TCN [5], and VIRL [6] that learn trajectory embeddings of the expert which could be used for comparison, rather than the product of single-state differences, which is one of the proposed metrics in this work.

**Quality:** 

1. In the car environment, the learned curriculum is visualized (Fig.3 and 4, b & d) and there are artifacts that need to be explained: (a) why does the learner with initial knowledge of T0 go back to learning T0 after T=150, why does it ignore T1 instead? (b) what is the "time" axis? Is that supposed to be environment interactions? (c) Why does the agent with knowledge of T0-T3 gradually resume these tasks? (d) ...and why does it initially ignore T4 and T5? (e) How many seeds were used to train the agents in Fig. 3/4?
2. All that the experiments in the 6x6 grid world show is that the agent learns to maximize equation 4, i.e. create more goals and fewer bombs/mud and therefore create easier and easier environments, which is backed up by Figure 5c. What are these experiments supposed to show? The agent has not acquired any resilience to bombs and mud but rather found a way to remove them from the environment altogether.

**Clarity:** 

The writing is mostly clear.
1. A dedicated "Related Literature" section would be good
2. line 80 $\Theta$ is not defined
3. line 82 should be an equation and not line-broken
4. Algorithm 1 can be cut because it's trivial or can be explained in 2 sentences.
5. The entirety of sections 4(.0) and 4.1 is pointless in my eyes because it assumes comparability of the agent parameters $\theta$ to the expert parameters $\theta^*$ and that is not a realistic or even plausible assumption, given that an expert can be of a completely different structure (e.g. a human demonstrating to a neural network)
6. Fig. 1 and 2 are missing an explanation of what "HOV" is. (I'm a native English speaker and I had to google that.)
7. Fig. 6 could use a legend of what the different symbols mean. It's clear from the text but Fig. 6a would be easier to parse with one.

**Significance:** 

As outlined above, I do not believe this method is pushing the state-of-the-art.

**Nitpicks and Questions:**

1. The authors keep repeating the phrase "under minor technical conditions" 3 times in the paper and I have no idea what this is supposed to mean.

**References:**

- [1] Ross, Stéphane, Geoffrey Gordon, and Drew Bagnell. "A reduction of imitation learning and structured prediction to no-regret online learning." Proceedings of the fourteenth international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, 2011.
- [2] Ross, Stephane, and J. Andrew Bagnell. "Reinforcement and imitation learning via interactive no-regret learning." arXiv preprint arXiv:1406.5979 (2014).
- [3] Kendall, Alex, et al. "Learning to drive in a day." 2019 International Conference on Robotics and Automation (ICRA). IEEE, 2019.
- [4] Kostrikov, Ilya, et al. "Discriminator-actor-critic: Addressing sample inefficiency and reward bias in adversarial imitation learning." arXiv preprint arXiv:1809.02925 (2018).
- [5] Sermanet, Pierre, et al. "Time-contrastive networks: Self-supervised learning from video." 2018 IEEE international conference on robotics and automation (ICRA). IEEE, 2018.
- [6] Berseth, Glen, and Christopher J. Pal. "Visual Imitation Learning with Recurrent Siamese Networks." arXiv preprint arXiv:1901.07186 (2019).
limitations_and_societal_impact: The authors did not properly explain the limitations of this work and neither the societal impact. Both were only mentioned off-hand in the conclusion.
Here are some suggestions:
- Instead of "our approach could be beneficial for education applications", you could write something more concrete like "We believe that this method can be employed by MOOC platforms to gauge which order of courses would be most beneficial for the students..."
- As for limitations, I would recommend to put the contribution of this work into perspective to other contemporary works and add a few sentences a la "we only experimented in a limited grid world setting, we only experimented with a low number of random seeds, we assume that we have unlimited access to a teacher,  etc"
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of designing a curriculum of trajectories to teach an imitation learning agent. The authors propose to sequentially give trajectories that are both difficult (low probability) for the current learner and easy (high probability) for the demonstrator. Some theoretical justification is provided for why this approach works as well as some empirical results on simple domains. In general this paper seems novel, but there are many areas that deserve more clarification and it is unclear how far this idea can be taken given the strong assumptions.
main_review: Overall, I like this paper. The problem setting is interesting and the theoretical analysis is nice and some of the empirical results are compelling. However, there are three main weaknesses that I see that should be addressed:.

(1) The authors claim that batch curriculum approaches are not as good as interactive settings. However, the approach is not compared with batch curriculum approaches. The authors need to compare with a batch setting to justify why to select the trajectories sequentially. For example, the SCOT algorithm (citation [18]) uses a set cover approximation to design the entire curriculum offline. While this method was not originally designed for training BC agents, it can be used as a baseline in the MaxEnt IRL agent setting. It is unclear whether the proposed methods are that much better as they require access to the learner's policy at each iteration. It seems that an offline curriculum algorithm will be much more efficient as it only requires access to the MDP and the teacher's policy and does not require repeatedly probing the learner. However, I agree that there is a potential for the sequential approach to be better as it can adapt to the learning progress. This hypothesis needs to be rigorously tested by comparing the proposed approach with the prior work on batch teaching for LfD.

(2) Probing the learner's policy seems very difficult. The authors mention monte-carlo techniques but this would require repeatedly querying for actions at every state, if I understand correctly. Is there a possibility of devising a curriculum that doesn't require this many queries? See some ideas below. Also, it's unclear how much of an advantage it is to have access to the policy but not the internal parameters as in prior work [28]. What is the benefit of also having access to the internal parameters as done in prior work? I don't think this point needs to be solved, but more discussion of this limitation would strengthen the paper.

(3) Figure 5 shows that you don't need the hand-crafted difficulty score since you can just use the learner's difficulty. This seems to make the entire section 6 unnecessary. I'm not convinced that equation (4) is a good surrogate for teacher difficulty. In particular it seems that having more goals makes it easier not harder since there are more ways to solve the task near optimally. 
Also the interpretation of the curriculum in Figure 6 seems iffy. The number of goals is included in the surrogate difficulty score f^E so it seems like that is the main reason later stages have more goals, not that this is actually a more difficult concept. I would recommend that the authors compare qualitatively with CUR-L to see if you get the same or different curricula if you don't use f^E.

I like the car driving example for visualizing and testing curriculum learning. 

Clarity:
The authors often say that their method doesn't require access to the "learner's internal dynamics". This is incorrect and the wording should be changed. The internal dynamics are the way that the learner updates its model. This is assumed to be known. The unknown thing is the learner's parameters, not their internal dynamics. Just saying "internal parameters" would be much better and clearer.


Questions:
What happens with deterministic policies? How do you define/deal with 0/0 when selecting trajectories.

It would be good to relate this approach to prior work by Brown et al. on "Value Alignment Verification"? There they also seek an epsilon-approximate value difference. But look at a testing problem rather than a teaching problem. This enables them to verify the student policy is within epsilon of the teacher without requiring access to the entire policy of the learner as assumed in this work. Can something similar be done here?

Along similar lines, could ideas from Jacq et al. "Learning from a learner" allow curriculum design for a MaxEnt agent without needing to query for the entire policy?

Does the proposed approach work for continuous action spaces? What would be needed to extend to this setting?

Why have two separate theorems (1 and 3)? They say basically the same thing. If the proof techniques are different enough to justify different theorems it would be nice to give a proof sketch for how they are different. Or just merge them into one theorem.

Also, why is there no analogy to Thm 2 for BC? I think this is fine to leave for future work, but it would be beneifical to add a brief description of why this setting is so much more challenging than that for Thrm 2.

In figure 3b and d, why teach what is known initially later in training? Is this implicitly accounting and correcting for catastrophic forgetting?

The reward function still appears to be linear since there is an indicator for the conjunction, right?

The Ominicient teacher is not really ever explained in section 3.

How would this work for educational applications? There I'd assume that you know the teaching policy but can never really know the learner policy. This seems to make the proposed approach ill-suited since the experiments show that you can get around not knowing the teacher's policy, but need access to the full policy of the student.

---
Thank you for your extensive response. The authors have answered my questions and based on the response, I think the paper quality will improve. 

---
Update: After a fruitful discussion with the other reviewers and the authors I am satisfied with the claims of novelty in the paper. I think these claims are nuanced and deserve better attention and I would like to see a more careful discussion of the differences between the submission and the blackbox approach proposed by Kamalaruban et al.. I think these points are easy to fix and will strengthen the paper. I would recommend that the paper be accepted.

limitations_and_societal_impact: yes
review_title: null

Meta-review: The paper is interested in defining an interactive curriculum for learning from demonstrations. Like in Weinshall et al., 2018, the idea is that the most useful demonstrations are the easiest ones for the teacher/oracle and the most difficult ones for the current learner (where the difficulty of a demonstration w.r.t. a policy is computed as its probability w.r.t. this policy). 
The lesson is backed by a theoretical analysis in the linear case, considering MaxEnt-IRL and CrossEnt-BC algorithms. 

Three approaches are experimentally compared: CUR (selecting the demonstration less difficult wrt the expert and most difficult wrt the current learner), CUR-L (where the difficulty wrt the expert is replaced with a heuristic measure) and CUR-T (that mostly considers the difficulty wrt the expert). The results suggest that the most important is to take into account the difficulty w.r.t. the current learner. 

The area chair did not take into account the most negative review (nb: this reviewer was eventually convinced by the good and thorough job done by the authors w.r.t. all reviewers, to explain the issues and to promise to revise their paper w.r.t. all points and suggestions raised by the reviewers). 

However, the area chair considered that the novelty of the paper w.r.t.  Kamalaruban et al.'s paper  (IJCAI 2019, cited) needed to be discussed:

* a main difference lies in  considering MaxEnt-IRL and CrossEnt-BC whereas Kamalaruban et al. considered MCE-IRL; 

* the structure of the proof (section 4.3 in Kamalaruban et al; Appendix C in the submitted paper) is similar ;

* the experimental setting (the car driving problem) is the same;

* this paper argues that it improves on Kamalaruban et al as it does not require the knowledge of the optimal policy, as it replaces the difficulty w.r.t. the expert policy with a heuristic function. The quality of this heuristic function however does not seem to be very important (point 3 in Response to Reviewer RaMd); unless I missed it, the authors did not comment further on it and did not consider any lesion of this, to study its impact.  

The significance of the contributions in the submitted paper w.r.t. Kamalaruban et al's (K, in the following) has been extensively discussed, concluding that 
* K presents an omniscient algorithm, aimed to yield the optimal $\theta^*$ policy parameter using the gradient $g_t$
* K also presents an approximation thereof, based on an estimation of $\theta_t$, though with no guarantees and specifically based on the MaxEnt-IRL / MCE-IRL freamework.


Overall, the paper is considering a hot topic and presenting interesting results; the many additional complements (explanations, discussion and results) in the answers to the reviews let us hope that the revised version will be way better than the submitted one. 
It is mandatory that in the final version, the authors clarify the novelty issue, and  compare their results with the Blackbox teaching baseline (section 5 in K).

Decision: Accept (Poster)