Curriculum Design for Teaching via Demonstrations: Theory and Applications
Year: 2022

Abstract:
We consider the problem of teaching via demonstrations in sequential decisionmaking settings. In particular, we study how to design a personalized curriculum over demonstrations to speed up the learner’s convergence. We provide a unified curriculum strategy for two popular learner models: Maximum Causal Entropy Inverse Reinforcement Learning (MaxEnt-IRL) and Cross-Entropy Behavioral Cloning (CrossEnt-BC). Our unified strategy induces a ranking over demonstrations based on a notion of difficulty scores computed w.r.t. the teacher’s optimal policy and the learner’s current policy. Compared to the state of the art, our strategy doesn’t require access to the learner’s internal dynamics and still enjoys similar convergence guarantees under mild technical conditions. Furthermore, we adapt our curriculum strategy to the setting where no teacher agent is present using task-specific difficulty scores. Experiments on a synthetic car driving environment and navigation-based environments demonstrate the effectiveness of our curriculum strategy.

heading: 1 Introduction
text: Imitation learning is a paradigm in which a learner acquires a new set of skills by imitating a teacher’s behavior. The importance of imitation learning is realized in real-world applications where the desired behavior cannot be explicitly defined but can be demonstrated easily. These applications include the settings involving both human-to-machine interaction [1–4], and human-to-human interaction [5, 6]. The two most popular approaches to imitation learning are Behavioral Cloning (BC) [7] and Inverse Reinforcement Learning (IRL) [8]. BC algorithms aim to directly match the behavior of the teacher using supervised learning methods. IRL algorithms operate in a two-step approach: first, a reward function explaining the teacher’s behavior is inferred; then, the learner adopts a policy corresponding to the inferred reward.
In the literature, imitation learning has been extensively studied from the learner’s point of view to design efficient learning algorithms [9–15]. However, much less work is done from the teacher’s point of view to reduce the number of demonstrations required to achieve the learning objective. In this paper, we focus on the problem of Teaching via Demonstrations (TvD), where a helpful teacher assists the imitation learner in converging quickly by designing a personalized curriculum [16–20]. Despite a substantial amount of work on curriculum design for reinforcement learning agents [21– 27], curriculum design for imitation learning agents is much less investigated.
Prior work on curriculum design for IRL learners has focused on two concrete settings: noninteractive and interactive. In the non-interactive setting [17, 18], the teacher provides a near-optimal set of demonstrations as a single batch. These curriculum strategies do not incorporate
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
any feedback from the learner, hence unable to adapt the teaching to the learner’s progress. In the interactive setting [28], the teacher can leverage the learner’s progress to adaptively choose the next demonstrations to accelerate the learning process. However, the existing state-of-the-art work [28] has proposed interactive curriculum algorithms that are based on learning dynamics of a specific IRL learner model (i.e., the learner’s gradient update rule); see further discussion in Section 1.1. In contrast, we focus on designing an interactive curriculum algorithm with theoretical guarantees that is agnostic to the learner’s dynamics. This will enable the algorithm to be applicable for a broad range of learner models, and in practical settings where the learner’s internal model is unknown (such as tutoring systems with human learners). A detailed comparison between our curriculum algorithm and the prior state-of-the-art algorithms from [18, 28] is presented in Section 1.1.
Our approach is motivated by works on curriculum design for supervised learning and reinforcement learning algorithms that use a ranking over the training examples using a difficulty score [29–35]. In particular, our work is inspired by theoretical results on curriculum learning for linear regression models [32]. We define difficulty scores for any demonstration based on the teacher’s optimal policy and the learner’s current policy. We then study the differential effect of the difficulty scores on the learning progress for two popular imitation learners: Maximum Causal Entropy Inverse Reinforcement Learning (MaxEnt-IRL) [10] and Cross-Entropy loss-based Behavioral Cloning (CrossEntBC) [36]. Our main contributions are as follows:1
1. Our analysis for both MaxEnt-IRL and CrossEnt-BC learners leads to a unified curriculum strategy, i.e., a preference ranking over demonstrations. This ranking is obtained based on the ratio between the demonstration’s likelihood under the teacher’s optimal policy and the learner’s current policy. Experiments on a synthetic car driving environment validate our curriculum strategy.
2. For the MaxEnt-IRL learner, we prove that our curriculum strategy achieves a linear convergence rate (under certain mild technical conditions), notably without requiring access to the learner’s dynamics.
3. We adapt our curriculum strategy to the learner-centric setting where a teacher agent is not present through the use of task-specific difficulty scores. As a proof of concept, we show that our strategy accelerates the learning process in synthetic navigation-based environments.

heading: 1.1 Comparison to Existing Approaches on Curriculum Design for Imitation Learning
text: In the non-interactive setting, [18] have proposed a batch teaching algorithm (SCOT) by showing that the teaching problem can be formulated as a set cover problem. In contrast, our algorithm is interactive in nature and hence, can leverage the learner’s progress (see experimental results in Section 5).
In the interactive setting, [28] have proposed the Omniscient algorithm (OMN) based on the iterative machine teaching (IMT) framework [37]. Their algorithm obtains strong convergence guarantees for the MaxEnt-IRL learner model; however, requires exact knowledge of the learner’s dynamics (i.e, the learner’s update rule). Our algorithm on the other hand is agnostic to the learner’s dynamics and is applicable to a broader family of learner models (see Sections 4 and 5).
Also for the interactive setting, [28] have proposed the Blackbox algorithm (BBOX) as a heuristic to apply the OMN algorithm when the learner’s dynamics are unknown—this makes the BBOX algorithm more widely applicable than OMN. However, this heuristic algorithm is still based on the gradient functional form of the linear MaxEnt-IRL learner model (see Footnote 2), and does not provide any convergence guarantees. In contrast, our algorithm is derived independent of any specific learner model and we provide a theoretical analysis of our algorithm for different learner models (see Theorems 1, 2, and 3). Another crucial difference is that the BBOX algorithm requires access to the true reward function of the environment, which precludes it from being applied to learnercentric settings where no teacher agent is present. In comparison, our algorithm is applicable to learner-centric settings (see experimental results in Section 6).

heading: 1.2 Additional Related Work on Curriculum Design and Teaching
text: Curriculum design. Curriculum design for supervised learning settings has been extensively studied in the literature. Early works present the idea of designing a curriculum comprising of tasks with increasing difficulty to train a machine learning model [29–31]. However, these approaches require
1Github repo: https://github.com/adishs/neurips2021_curriculum-teaching-demonstrations_code.
task-specific knowledge for designing heuristic difficulty measures. Recent works have tackled the problem of automating curriculum design [38, 39]. There is also an increasing interest in theoretically analyzing the impact of a curriculum (ordering) of training tasks on the convergence of supervised learner models [32, 40, 41]. In particular, our work builds on the idea of difficulty scores of the training examples studied in [32].
The existing results on curriculum design for sequential decision-making settings are mostly empirical in nature. Similar to the supervised learning settings, the focus on curriculum design for reinforcement learning settings has been shifted from hand-crafted approaches [34, 35] to automatic methods [21–23, 25]. We refer the reader to a recent survey [42] on curriculum design for reinforcement learning. The curriculum learning paradigm has also been studied in psychology literature [43–47]. One key aspect in these works has been to design algorithms that account for the pedagogical intentions of a teacher, which often aims to explicitly demonstrate specific skills rather than just provide an optimal demonstration for a task. We see our work as complementary to these.
Machine teaching. The algorithmic teaching problem considers the interaction between a teacher and a learner where the teacher’s objective is to find an optimal training sequence to steer the learner towards a desired goal [37, 48–50]. Most of the work in machine teaching for supervised learning settings is on batch teaching where the teacher provides a batch of teaching examples at once without any adaptation. The question of how a teacher should adaptively select teaching examples for a learner has been addressed recently in supervised learning settings [51–56].
Furthermore, [16–18, 28, 57, 58] have studied algorithmic teaching for sequential decision-making tasks. In particular, [17, 18] have proposed batch teaching algorithms for an IRL agent, where the teacher decides the entire set of demonstrations to provide to the learner before any interaction. These teaching algorithms do not leverage any feedback from the learner. In contrast, as discussed in Section 1.1, [28] have proposed interactive teaching algorithms (namely OMN and BBOX) for an IRL agent, where the teacher takes into account how the learner progresses. The works of [57, 58] are complementary to ours and study algorithmic teaching when the learner has a differet worldview than the teacher or has its own specific preferences.

heading: 2 Formal Problem Setup
text: Here, we formalize our problem setting which is based on prior work on sequential teaching [28, 37].
Environment. We consider an environment defined as a Markov Decision Process (MDP)M :=( S,A, T , γ, P0, RE ) , where the state and action spaces are denoted by S and A, respectively. T : S × S × A → [0, 1] is the transition dynamics, γ is the discounting factor, and P0 : S → [0, 1] is an initial distribution over states S. A policy π : S × A → [0, 1] is a mapping from a state to a probability distribution over actions. The underlying reward function is given by RE : S ×A → R.
Teacher-learner interaction. We consider a setting with two agents: a teacher and a sequential learner. The teacher has access to the full MDPM and has a target policy πE (e.g., a near-optimal policy w.r.t. RE). The learner knows the MDPM but not the reward function RE , i.e., has only access to M \ RE . The teacher’s goal is to provide an informative sequence of demonstrations to teach the policy πE to the learner. Here, a teacher’s demonstration ξ = {( sξτ , a ξ τ )} τ=0,1,... is obtained by first choosing an initial state sξ0 ∈ S (where P0(sξ0) > 0) and then choosing a trajectory, sequence of state-action pairs, obtained by executing the policy πE in the MDPM. The interaction between the teacher and the learner is formally described in Algorithm 1. For simplicity, we assume that the teacher directly observes the learner’s policy πLt at any time t. In practice, the teacher could approximately infer the policy πLt by probing the learner and using Monte Carlo methods.
Generic learner model. Here, we describe a generic learner update rule for Algorithm 1. Let Θ ⊆ Rd be a parameter space. The learner searches for a policy in the following parameterized policy space: ΠΘ := {πθ : S ×A → [0, 1] , where θ ∈ Θ}. For the policy search, the learner sequentially minimizes a loss function ` that depends on the policy parameter θ and the demonstration ξ = {( sξτ , a ξ τ )} τ
provided by the teacher. More concretely, we consider ` (ξ, θ) := − logP (ξ|θ), where P (ξ|θ) = P0(sξ0) · ∏ τ πθ ( aξτ |sξτ ) · T ( sξτ+1|sξτ , aξτ ) is the likelihood (probability) of the demon-
Algorithm 1 Teacher-Learner Interaction
1: Initialization: Initial knowledge of learner πL1 . 2: for t = 1, 2, . . . do 3: Teacher observes the learner’s current policy πLt . 4: Teacher provides demonstration ξt to the learner. 5: Learner updates its policy to πLt+1 using ξt.
stration ξ under policy πθ in the MDP M. At time t, upon receiving a demonstration ξt provided by the teacher, the learner performs the following online projected gradient descent update: θt+1 ← ProjΘ [θt − ηtgt], where ηt is the learning rate, and gt = [∇θ` (ξt, θ)]θ=θt . Note that the parameter θ1 reflects the initial knowledge of the learner. Given the learner’s current parameter θt at time t, the learner’s policy is defined as πLt := πθt .
Teaching objective. For any policy π, the value (total expected reward) of π in the MDPM is defined as V π := ∑ s,a ∑∞ τ=0 γ
τ ·P {Sτ = s | π,M}·π (a | s)·RE (s, a) ,where P {Sτ = s | π,M} denotes the probability of visiting the state s after τ steps by following the policy π. Let πL denote the learner’s final policy at the end of teaching. The performance of the policy πL (w.r.t. πE) inM can be evaluated via
∣∣∣V πE − V πL∣∣∣ [9, 59]. The teaching objective is to ensure that the learner’s final policy -approximates the teacher’s policy, i.e.,
∣∣∣V πE − V πL ∣∣∣ ≤ . The teacher aims to provide an optimized sequence of demonstrations {ξt}t=1,2,... to the learner to achieve the teaching objective. The teacher’s performance is then measured by the number of demonstrations required to achieve this objective. Based on existing work [28, 37], we assume that ∃ θ∗ ∈ Θ such that πE = πθ∗ (we refer to θ∗ as the target teaching parameter). Similar to [28], we assume that a smoothness condition holds in the policy parameter space: |V πθ − V πθ′ | ≤ O (f (‖θ − θ′‖))∀θ, θ′ ∈ Θ. Then, the teaching objective in terms of V π convergence can be reduced to the convergence in the parameter space, i.e., we can focus on the quantity ‖θ∗ − θt‖.

heading: 3 Curriculum Design using Difficulty Scores
text: In this section, we introduce our curriculum strategy which is based on the concept of difficulty scores and is agnostic to the dynamics of the learner.
Difficulty scores. We begin by assigning a difficulty score Ψθ (ξ) for any demonstration ξ w.r.t. a parameterized policy πθ in the MDP M. Inspired by difficulty scores for supervised learning algorithms [32], we consider a difficulty score which is directly proportional to the loss function `, i.e., Ψθ (ξ) ∝ g (` (ξ, θ)), for a monotonically increasing function g. Setting g(·) = exp(·) leads to Ψθ (ξ) =
1∏ τ πθ(a ξ τ |sξτ )
for MDPs with deterministic transition dynamics. Based on this insight, we define the following difficulty score which we use throughout our work. Definition 1. The difficulty score of a demonstration ξ w.r.t. the policy πθ in the MDPM is given by Ψθ (ξ) := 1∏
τ πθ(a ξ τ |sξτ )
.
Intuitively, the difficulty score of a demonstration ξ w.r.t. an agent’s policy is inversely proportional to the preference of the agent to follow the demonstration. Demonstrations with a higher likelihood under the agent’s policy (higher preference) have a lower difficulty score and vice versa. With the above definition, the difficulty scores for any demonstration ξ w.r.t. the teacher’s and learner’s policies (at any time t) are respectively given by ΨE (ξ) := Ψθ∗ (ξ) and ΨLt (ξ) := Ψθt (ξ).
General curriculum strategy. Our curriculum strategy picks the next demonstration ξt to provide to the learner based on a preference ranking induced by the teacher’s and learner’s difficulty scores. The difficulty score of a demonstration ξ w.r.t. the teacher and learner (at any time t) is denoted by ΨE and ΨLt respectively. Specifically, our curriculum strategy is given by:
ξt ← arg max ξ
ΨLt (ξ) ΨE (ξ) . (1)
Teacher-centric and learner-centric settings. In the teacher-centric setting formalized in Section 2, our curriculum strategy utilizes the difficulty scores induced by the learner’s current policy πLt and the teacher’s policy πE . From Eq. (1) and Definition 1, we obtain the following teacher-centric curriculum strategy: ξt ← arg maxξ ∏ τ πE(aξτ |s ξ τ )
πLt (a ξ τ |sξτ )
.
Additionally, we also consider the learner-centric setting where a teacher agent is not present and the target policy πE is unknown. Here, the learner can benefit from designing a self-curriculum (i.e., automatically ordering demonstrations) based on its current policy πLt . We adapt our curriculum strategy to this setting by utilizing task-specific domain knowledge to define the teacher’s difficulty score ΨE(ξ) for any demonstration ξ. From Eq. (1), given the learner’s current policy πLt and the teacher’s difficulty score ΨE(ξ), the learner-centric curriculum strategy is given as follows: ξt ← arg maxξ 1ΨE(ξ)∏τ πLt (aξτ |sξτ ) . Note that our curriculum strategy only requires access to the learner’s and teacher’s policies (πLt and πE) and does not depend on the learner’s internal dynamics (i.e, its update rule as mentioned in Section 2). This makes our approach more widely applicable to practical applications where it is often possible to infer an agent’s policy, but the internal update rule is unknown.

heading: 4 Theoretical Analysis of Our Curriculum Strategy
text: In this section, we present the theoretical analysis of our curriculum strategy for two popular learner models, namely, MaxEnt-IRL and CrossEnt-BC. For our analysis, we consider the teacher-centric setting as introduced in Section 2. Our curriculum strategy obtains a preference ranking over the demonstrations to provide to the learner based on the difficulty scores (see Definition 1). To this end, we analyze the relationship between the difficulty scores (w.r.t. the teacher and the learner) of the provided demonstration and the teaching objective (convergence towards the target teaching parameter θ∗) during each sequential update step of the learner.
Given two difficulty values ψE , ψL ∈ R, we define the feasible set of demonstrations at time t as Dt ( ψE , ψL ) := { ξ : ΨE (ξ) = ψE and ΨLt (ξ) = ψ L }
. This set contains all demonstrations ξ for which the teacher’s difficulty score ΨE(ξ) is equal to the value ψE , and the learner’s difficulty score ΨL(ξ) is equal to the value ψL. Let ∆t ( ψE , ψL ) denote the expected convergence rate of the teaching objective at time t, given difficulty values ψE and ψL:
∆t ( ψE , ψL ) := Eξt|ψE ,ψL[‖θ∗ − θt‖ 2 − ‖θ∗ − θt+1(ξt)‖2], (2)
where the expectation is w.r.t. the uniform distribution over the setDt ( ψE , ψL ) . Below, we analyse
the differential effect of ψE and ψL on ∆t ( ψE , ψL ) , i.e., the effect of picking demonstrations with higher or lower difficulty scores on the learning progress.

heading: 4.1 Analysis for MaxEnt-IRL Learner
text: Here, we consider the popular MaxEnt-IRL learner model [10, 59, 60] in an MDPM with deterministic transition dynamics, i.e., T : S × S ×A → {0, 1}. The MaxEnt-IRL learner model uses a parametric reward function Rθ : S ×A → R where θ ∈ Rd is a parameter. The reward function Rθ also depends on a feature mapping φ : S ×A → Rd′ which encodes each state-action pair (s, a) by a feature vector φ (s, a) ∈ Rd′ . For our theoretical analysis, we consider Rθ with a linear form, i.e., Rθ (s, a) := 〈θ, φ (s, a)〉 and d = d′. In our experiments, we go beyond these simplifications and consider environments with stochastic transition dynamics and non-linear reward functions.
Under the MaxEnt-IRL learner model, the parametric policy takes the following soft-Bellman form: πθ(a|s) = exp (Qθ(s, a)− Vθ(s)), where Vθ(s) = log ∑ a expQθ(s, a) and Qθ(s, a) = Rθ(s, a) +
γ ∑ s′ T (s
′|s, a) · Vθ(s′). For any given θ, the corresponding policy πθ can be efficiently computed via the Soft-Value-Iteration procedure with reward Rθ (see [59, Algorithm. 9.1]). For the above setting and a given parameter θ, the probability distribution P (ξ|θ) over the demonstration ξ takes the closed-form P (ξ|θ) = exp(〈θ,µ
ξ〉) Z(θ) , where µ ξ := ∑∞ τ=0 γ τφ(sξτ , a ξ τ ) andZ (θ) is a normalization
factor. Then, at time t, the gradient of the MaxEnt-IRL learner is given by gt = µπθt − µξt , where
µπ := ∑ s,a ∑∞ τ=0 γ
τ ·P {Sτ = s | π,M} · π (a | s) ·φ (s, a) is the feature expectation vector of policy π. We note that our curriculum strategy in Eq. (1) is not using knowledge of gt.
For the MaxEnt-IRL learner, we obtain the following theorem, which shows the differential effect of the difficulty scores (w.r.t. the teacher and the learner) on the expected rate of convergence of the teaching objective ∆t ( ψE , ψL ) . We note that [32] obtained similar results for linear regression learner models in the supervised learning setting.
Theorem 1. Assume that ηt is sufficiently small for all t s.t. ηt ‖gt‖2 2 |〈θ∗ − θt, gt〉|, where gt is the gradient of the MaxEnt-IRL learner. Then, for the MaxEnt-IRL learner, the expected convergence rate of the teaching objective ∆t ( ψE , ψL ) is:
• monotonically decreasing with value ψE , i.e., ∂∆t ∂ψE < 0, and
• monotonically increasing with value ψL, i.e., ∂∆t ∂ψL > 0.
Theorem 1 suggests that choosing demonstrations with lower difficulty score w.r.t. the teacher’s policy and higher difficulty score w.r.t. the learner’s policy would lead to faster convergence. Our curriculum strategy in Eq. (1) induces a preference ranking over demonstrations that aligns with these insights of Theorem 1. Furthermore, the following theorem states that the particular form of combining the two difficulty scores used in curriculum strategy, Eq. (1), achieves linear convergence to the teaching objective. This is similar to the state-of-the-art OMN algorithm based on the IMT framework for sequential learners [28, 37]. Importantly, unlike the OMN algorithm, our curriculum strategy does not rely on specifics of the learner model when selecting demonstrations. Theorem 2. Consider Algorithm 1 with the MaxEnt-IRL learner and our curriculum strategy in Eq. (1). Then, the teaching objective ‖θ∗ − θt‖ ≤ is achieved in t = O(log 1 ) iterations. In the above theorem, the constant terms suppressed by the O(·) notation depend on the learning rate of the learner (ηt), the distance between the learner’s initial parameter/knowledge and the target teaching parameter (‖θ∗ − θ1‖), and the richness of the set of demonstrations obtained by executing the policy πE in the MDPM. The richness notion is formally discussed in the Appendix.

heading: 4.2 Analysis for CrossEnt-BC Learner
text: Next, we consider the CrossEnt-BC learner model [15, 36]. In this case, the learner’s parametric policy takes the following softmax form: πθ(a|s) = exp(Hθ(s,a))∑
a′ exp(Hθ(s,a ′)) , where Hθ : S × A → R
is a parametric scoring function that depends on the parameter θ ∈ Rd and a feature mapping φ : S × A → Rd′ . For our theoretical analysis, we consider a linear scoring function Hθ of the form Hθ (s, a) := 〈θ, φ (s, a)〉 (with d = d′). Then, at time step t, the gradient gt of the CrossEntBC learner is given by: gt = ∑∞ τ=0 ( E a∼πθt(·|s ξt τ ) [ φ(sξtτ , a) ] − φ(sξtτ , aξtτ ) ) . In the experiments, we also consider non-linear scoring functions parameterized by neural networks.
Similar to Theorem 1, we obtain the following theorem for the CrossEnt-BC learner, which also justifies our curriculum strategy in Eq. (1).
Theorem 3. Assume that ηt is sufficiently small for all t s.t. ηt ‖gt‖2 2 |〈θ∗ − θt, gt〉|, where gt is the gradient of the CrossEnt-BC learner. Then, for the CrossEnt-BC learner, the expected convergence rate of the teaching objective ∆t ( ψE , ψL ) , after first-order approximation, is:
• monotonically decreasing with ψE , i.e., ∂∆t ∂ψE < 0, and
• monotonically increasing with ψL, i.e., ∂∆t ∂ψL > 0. We note that the proof of Theorem 3 relies on the first-order Taylor approximation of the term∑ τ log ∑ a′ exp ( Hθ ( sξtτ , a
′)) around θt (detailed in the Appendix). Due to this approximation, it is more challenging to obtain a convergence result analogous to Theorem 2.

heading: 5 Experimental Evaluation: Teacher-Centric Setting
text: Inspired by the works of [28, 61, 62], we evaluate the performance of our curriculum strategy, Eq. (1), in a synthetic car driving environment on MaxEnt-IRL and CrossEnt-BC learners. In particular, we consider the environment of [28] and the teacher-centric setting of Section 2.
Car driving setup. Fig. 1 illustrates a synthetic car driving environment consisting of 8 different types of tasks, denoted as T0, T1, . . ., T7. Each type is associated with different driving skills. For instance, T0 corresponds to a basic setup representing a traffic-free highway. T1 represents a crowded highway. T2 has stones on the right lane, whereas T3 has a mix of both cars and stones. Similarly, T4 has grass on the right lane, and T5 has a mix of both grass and cars. T6 and T7 introduce more complex features such as pedestrians, police, and HOV (high occupancy vehicles). The agent starts navigating from an initial state at the bottom of the left lane of each task, and the goal is to reach the top of a lane while avoiding cars, stones, and other obstacles. The agent’s action space is given by A = {left, straight, right}. Action left steers the agent to the left of the current lane. If the agent is already in the leftmost lane when taking action left, then the lane is randomly chosen with uniform probability. We define similar stochastic dynamics for taking action right; action straight means no change in the lane. Irrespective of the action taken, the agent always moves forward.
Environment MDP. Based on the above setup, we define the environment MDP,Mcar, consisting of 8 types of tasks, namely T0–T7, and 5 tasks of each type. Every location in the environment is associated with a state. Each task is of length 10 and width 2, leading to a state space of size 5 × 8 × 20. We consider an action-independent reward function REcar that is dependent on an underlying feature vector φE (see Fig. 2). The feature vector of a state s, denoted by φE(s), is a binary vector encoding the presence or absence of an object at the state. In this work we have two types of features: features indicating the type of the current cell as stone, grass, car, ped, police, and HOV, as well as features providing some look-ahead information such as whether there is a car or pedestrian in the immediate front cell (denoted as car-front and ped-front). Now we explain the reward functionREcar . For states in tasks of type T0-T6, the reward is given by〈 w, φE(s) 〉 (see Fig. 2). Essentially there are different penalties (i.e., negative rewards) for colliding with specific obstacles such as stone and car. For states in tasks of type T7, there is a reward of value +1 for driving on HOV; however, if police is present while driving on HOV, a reward value of −5 is obtained. Overall, this results in the reward function REcar being nonlinear.

heading: 5.1 Teaching Algorithms
text: Here, we introduce the teaching algorithms considered in our experiments. The teacher’s nearoptimal policy πE is obtained via policy iteration [63]. The teacher selects demonstrations to provide to the learner using its teaching algorithm. We compare the performance of our proposed CUR teacher, which implements our strategy in Eq. (1), with the following baselines:
• CUR-T: A variant of our CUR teacher that samples demonstrations based on the difficulty score ΨE alone, and sets ΨLt to constant. • CUR-L: A similar variant of our CUR teacher that samples demonstrations based on the difficulty score ΨLt alone, and sets Ψ
E to constant. • AGN: an agnostic teacher that picks demonstrations based on random ordering [28, 32]. • OMN: The omniscient teacher is a state-of-the-art algorithm [28, 37], which is applicable only
to MaxEnt-IRL learners. OMN requires complete knowledge of the parameter θ∗, the learner’s current parameter θt, and the learner’s gradients ηtgt. Based on this knowledge, the teacher picks demonstrations to directly steer the learner towards θ∗, i.e., by minimizing ‖θ∗ − (θt − ηtgt)‖.
• BBOX: The blackbox teacher [28] is designed based on the functional form of gradients for the linear MaxEnt-IRL learner model.2 Specifically, the teacher picks a demonstration ξ which maximizes |∑s′,a′{ρπLt (s′, a′) − ρξ(s′, a′)}RE(s′, a′)|, where ρ denotes state visitation frequency vectors. The BBOX teacher does not require access to θ∗ or the learner’s current parameter θt; however, it requires access to the true reward function RE . • SCOT: The SCOT teacher [18] aims to find the smallest set of demonstrations required to teach an optimal reward function to the MaxEnt-IRLlearner. The teacher uses a set cover algorithm to precompute the entire curriculum as a batch, prior to training. In our implementation, after having provided the entire batch, the teacher continues providing demonstrations selected at random.

heading: 5.2 Learner Models
text: Next, we describe the MaxEnt-IRL and CrossEnt-BC learner models. For the MaxEnt-IRL learner, we evaluate all the above-mentioned teaching algorithms that include state-of-the-art baselines; for the CrossEnt-BC learner, we evaluate CUR, CUR-T, CUR-L, and AGN algorithms.
MaxEnt-IRL learner. For alignment with the prior state-of-the-art work on teaching sequential MaxEnt-IRL learners [28], we perform teaching over states in our experiments. More concretely, at time t the teacher picks a state st (where P0(st) > 0) and provides all demonstrations starting from st to the learner given by Ξst = { ξ = {( sξτ , a ξ τ )} τ s.t. sξ0 = st } . The gradient gt of the MaxEnt-
IRL learner is then given by gt = µπθt ,st − µΞst , where (i) µΞst := 1|Ξst | ∑ ξ∈Ξst µξ, and (ii) µπ,st is the feature expectation vector of policy π with starting state set to st (see Section 4.1). Based on [28], we consider the learner’s feature mapping as φ(s, a) = φE(s) and the learner uses a nonlinear parametric reward functionRLθ (s, a) = 〈θ1:d′ , φ (s, a)〉+〈θd′+1:2d′ , φ (s, a)〉 2 where d′ is the
2The BBOX teacher’s objective is derived under the assumptions that the reward function can be linearly parameterized as 〈 w∗, φE(s) 〉 and gradients gt are based on the linear MaxEnt-IRL learner model. Under these assumptions, the teacher’s objective can be equivalently written as | 〈w∗, gt〉 |.
dimension of φ(s, a). As explained in [28], a linear reward representation cannot capture the optimal behaviour forMcar. We consider learners with varying levels of initial knowledge, i.e., the learner is trained on a subset of tasks before the teaching process starts. In this setting, for our curriculum strategy in Eq. (1) the difficulty score of a set of demonstrations associated with a starting state Ξs is computed as the mean difficulty score of individual demonstrations in the set. CrossEnt-BC learner. We consider the CrossEnt-BC learner model of Section 4.2 as our second learner model. The learner’s feature mapping is given by φ (s, a) = Es′∼T (·|s,a)[φE(s′)]. A quadratic parametric form is selected for the scoring function, i.e., Hθ (s, a) = 〈θ1:d′ , φ (s, a)〉 + 〈θd′+1:2d′ , φ (s, a)〉2, where d′ is the dimension of φ(s, a). We consider learners with varying initial knowledge and perform teaching over states similar to the MaxEnt-IRL learner.

heading: 5.3 Experimental results
text: Figs. 3a, 3c and 4a, 4c show the convergence of the total expected reward for the MaxEnt-IRL and CrossEnt-BC learners respectively, averaged over 10 runs. The CUR teacher outperforms OMN despite not requiring information about the learner’s dynamics. For non-linear parametric reward functions, the MaxEnt-IRL learner no longer solves a convex optimization problem. As a result, forcing the learner to converge to a fixed parameter doesn’t necessarily perform well, as seen by the poor performance of the OMN teacher in Fig. 3c. The CUR teacher is competitive with the BBOX teacher. Unlike our CUR teacher, the BBOX teacher does require exact access to the true reward function, RE . The CUR teacher consistently outperforms the AGN and SCOT teachers, as well as both the CUR-T and CUR-L variants.
Figs. 3b, 3d and 4b, 4d visualize the curriculum generated by the CUR teacher for the MaxEntIRL and CrossEnt-BC learners respectively. Here, the curriculum refers to the type of task, T0–T7, associated with the demonstrations provided by the teacher to the learner at time step t. For both types of learners we see that at the beginning of training, the teacher focuses on tasks which teach skills the learner is yet to master. For example, in Fig. 4d, the teacher picks tasks T4, T6, and T7, which teaches the learner to avoid grass, pedestrians, and to navigate through police and HOV. We also notice that the CUR teacher can identify degradation in performance on previously mastered tasks, e.g., task T1 in Fig. 3d, and corrects for this by picking them again later during training.
Additional results under limited observability. In the above experiments, we consider the learner’s policy to be fully observable by the teacher at every time step. Here, we study the performance of our CUR teacher under the limited observability setting, similar to [28], where the learner’s policy needs to be estimated by probing the learner. The probing process is formally characterized by two parameters, (B, k), where the learner’s policy is probed after every B time steps and each probing step corresponds to querying the learner’s policy πLt a total of k times from each state s ∈ S in the MDP. The learner’s policy, πLt (a|s) ∀a, s, is then approximated based on the fraction of the k queries in which the learner performed action a from state s. In between every B time steps that the learner is probed, the CUR teacher does not update its estimate of the learner’s policy. We
note that the (B = 1, k →∞) setting corresponds to full observability of the learner. Fig. 5 depicts the performance of the CUR teacher for different values of (B, k). Even under limited observability, the CUR teacher’s performance is competitive with the full observability setting. The performance of (B = 40, k → ∞) is even slightly better at certain time steps during later stages of training compared to (B = 1, k →∞), which is possibly due to the strategy of greedily picking demonstrations not being necessarily optimal. Also, for the limited observability setting it can be interesting to explore approaches that alleviate the need to query the full policy of the learner [64, 65].

heading: 6 Experimental Evaluation: Learner-Centric Setting
text: In this section, we evaluate our curriculum strategy in a learner-centric setting, i.e., no teacher agent is present, and the teacher’s difficulty ΨE(ξ) is expressed by a task-specific difficulty score (see Section 3). We evaluate our approach for training a multi-task neural policy to solve discrete optimization problems. Here, we provide an overview of the results with additional details in the Appendix.
(a) (b)
Figure 6: Illustration of a shortest path navigation task (left) and convergence curves (right). (a) (b)
Figure 7: Illustration of a travelling salesman navigation task (left) and convergence curves (right).
Experiment setup. We begin by describing the synthetic navigation-based environments considered in our experiments. Our first navigation environment comprises of tasks based on the shortest path problem [66]. We represent each task with a grid-world (see Fig. 6a) containing goal cells (depicted by stars), and cells with muds and bombs (shown in brown and red respectively). The agent aims to navigate to the closest goal cell while avoiding muds and bombs. Our second navigation environment comprises of tasks inspired by the travelling salesman problem (TSP) [67, 68] (see Fig. 7a). Again we represent each task with a grid-world, where the agent’s goal is to find the shortest tour which visits all goals and returns to its initial location (see Fig. 7a). Orange arrows in Figs. 6a and 7a depict the optimal path for the agent. In our experimental setup, we begin by creating a pool of tasks and split them into training and test sets. The curriculum algorithms order the training tasks during the training phase based on their strategy to speed up the learner’s progress. The aim of the learner is to learn a multi-task neural policy that can generalize to new unseen tasks in the test set.
Curriculum algorithms. We compare the performance of four different curriculum algorithms: (i) the CUR algorithm picks tasks from the training set using Eq. (1) where the numerator is ΨLt and the denominator ΨE is defined by a task-specific difficulty score (detailed in the Appendix); (ii) the CUR-L algorithm picks tasks from the training set using Eq. (1) where the numerator is ΨLt and the denominator is set to 1; (iii) the CUR-T algorithm picks tasks from the training set using Eq. (1) where the numerator is set to 1 and the denominator is set to ΨE ; (iv) the AGN algorithm picks tasks with a uniform distribution over the training set.
Learner model. We consider a neural CrossEnt-BC learner (see Section 4.2). The learner’s scoring function Hθ is parameterized by a 6-layer Convolutional Neural Network (CNN). The CNN takes as input a feature mapping of the agent’s current position in a task, and outputs a score for each action. The learner minimizes the cross-entropy loss between its predictions and the demonstrations.
Results. Figs. 6b and 7b, show the reward convergence curves on the test set for the different curriculum algorithms averaged over 5 runs. The CUR algorithm leads to faster reward convergence compared to the AGN algorithm, which is the common approach for training a neural policy. CURL is competitive with CUR in this setting which highlights the importance of the learner’s difficulty.

heading: 7 Discussion and Conclusions
text: We presented a unified curriculum strategy, with theoretical guarantees, for the sequential MaxEntIRL and CrossEnt-BC learner models, based on the concept of difficulty scores. Our proposed strategy is independent of the learner’s internal dynamics and is applicable in both teacher-centric and learner-centric settings. Experiments on a synthetic car driving environment and on navigationbased environments demonstrated the effectiveness of our curriculum strategy.
Our work provides theoretical underpinnings of curriculum design for teaching via demonstrations, which can be beneficial in educational applications such as tutoring systems and also for selfcurriculum design for imitation learners. As such we do not see any negative societal impact of our work. Some of the interesting directions for future work include: obtaining convergence bounds for CrossEnt-BC and other learner models, designing curriculum algorithms for reinforcement learning agents based on the concept of difficulty scores, and designing approaches to efficiently approximate the learner’s policy using less queries.

Review summaries:
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.

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.