Interaction-limited Inverse Reinforcement Learning

This paper proposes an inverse reinforcement learning (IRL) framework to accelerate learning when the learner-teacher \textit{interaction} is \textit{limited} during training. Our setting is motivated by the realistic scenarios where a helpful teacher is not available or when the teacher cannot access the learning dynamics of the student. We present two different training strategies: Curriculum Inverse Reinforcement Learning (CIRL) covering the teacher's perspective, and Self-Paced Inverse Reinforcement Learning (SPIRL) focusing on the learner's perspective. Using experiments in simulations and experiments with a real robot learning a task from a human demonstrator, we show that our training strategies can allow a faster training than a random teacher for CIRL and than a batch learner for SPIRL.


Introduction
Learning from Demonstrations (LfD) is an active research area that addresses the problem of learning how to perform a task by observing the demonstrations provided by an expert. This approach plays an important role in many real-life learning settings, including human-to-robot interaction [1,2,3,4,5].
The two popular approaches for LfD include (i) behavioral cloning, which directly mimics the expert behavior, without understanding the objective [6], and (ii) inverse reinforcement learning (IRL), which infers the reward function (i.e., the objective of the task) explaining the expert behavior [7].
In this work, we focus on the IRL approach to LfD. Typically, the IRL learner assumes that the demonstrated expert behavior is optimal with respect to some reward function, even if the reward function cannot be specified explicitly as in typical reinforcement learning (RL). IRL algorithms operate by first recovering this reward function from demonstrations, and then obtaining a policy corresponding to the inferred reward [7,8]. IRL has been extensively studied in the context of designing efficient learning algorithms for a given set of demonstrations [8,9,10,11].
In this paper, we consider a sequential variant of the popular IRL algorithm, namely Maximum Entropy IRL algorithm [10,12], where at each time step, the learner receives only a minibatch of demonstrations from the teacher. Recent works in this field have shown that the interaction between the learner and the teacher can considerably improve the speed of the learning process.
From the learner's point of view, [13,14] have proposed active learning algorithms for IRL that focus on reducing the number of demonstrations that needs to be requested from a teacher. From the viewpoint of a teacher, [15] have designed active teaching algorithms for IRL, where the teacher actively chooses the appropriate next demonstration for the learner based on the learner's current progress and the target knowledge.
However, to our knowledge, no prior work considers the problem of speeding up the learning process of an online IRL learner when the teacher-learner interaction during the learning process is not possible. To solve this problem, we extend some of the techniques that were initially developed to accelerate the training process in the supervised learning problem, to the problem of online IRL with the goal of minimizing the number of demonstrations required to learn/teach a task.
To understand the key contributions, consider the example of a teacher who wants to write a mathematics book consisting of some concepts related to a particular topic. The teacher could present the contents (definitions and theorems etc.) in a random order, hoping that the readers would find their path, or the teacher could organize the materials in a manner that is beneficial to an "average" reader, usually from more straightforward concepts to complex ones.
This cognitive/learning process of humans is the intuition behind Curriculum Learning [16] whose method consists in ordering the input data such that the ordering can improve the robustness and speed of the learning process of an online learner. Now, consider a reader who receives this book to learn some concepts. She does not need to follow the path given by the author exactly; for example, she might skip some parts, go back on others, etc. This insight is the basis for self-paced learning [17], a learning algorithm in which the learner actively chooses the examples that she will process at each time step, i.e., the learner is designing her own curriculum.  Curriculum learning and self-paced learning have been applied effectively to the supervised and semisupervised learning problems [16,18,19,20,21,22]. More recently, these techniques have been integrated with reinforcement learning algorithms as well [23,24,25]. Recent work [26] combines curriculum learning and self-paced learning to extract the benefits of both a careful teacher through the curriculum and a conscientious learner through selfpaced learning. The different learning/teaching modalities presented in this section, and their similarities, are summarized in Figure 1.
In this paper, we introduce Curriculum Inverse Reinforcement Learning (CIRL), a teaching strategy, and Self-Paced Inverse Reinforcement Learning (SPIRL), a learning strategy, which improve the learning speed of an agent that iteratively learns a task from demonstrations. To test our proposed algorithms, experimental results demonstrate the superiority of the proposed strategies in gridworld environments and with a real robot as compared to uninformative training strategies.

Related Work
Interaction between teacher and learner plays an essential role in accelerating the learning process of an IRL learner. [27] extends the principles of active learning to inverse reinforcement learning by allowing the agent to query the demonstrator for samples at specific states instead of receiving demonstrations at random. In a recent work [13], the learner has to navigate actively into a sequence of tasks demonstrated by a teacher, to minimize the number of queries made to the teacher. [15] takes the viewpoint of a teacher in how to best assist the learning agent by providing an optimal sequence of demonstrations, using the learner's knowledge about the task. [28] have studied the interaction between the teacher and the learner as a cooperative game and have produced behaviors similar to active learning and active teaching. However, contrary to our approach, all these works suppose that teacher-learner interaction is possible during the whole learning process.
In [29], authors have studied the problem of improving the learning process of an IRL agent [30] in the batch setting by selecting the most informative set of demonstrations at once. In recent work, [31] have shown that the problem of finding the optimal set of demonstrations can be formulated as a set cover problem, and proposed machine teaching algorithms [32,33,34] for the batch IRL learner.
Similar to our approach, there is no teacher-learner interaction during the learning process in these approaches as well, and the agents have to deal with the absence of feedback related to the learner's current knowledge. However, our approach focuses on the ways a fixed batch of demonstrations can be ordered by the teacher (in CIRL) or by the learner (in SPIRL), whereas machine teaching focuses on how this batch of demonstrations can be built.

Background
This section provides the necessary background on Inverse Reinforcement Learning, and learning modalities.
We denote a policy π : S × A → [0, 1] as a mapping from a state to a probability distribution over actions. For any policy π, the value (total expected reward) of π in the MDP M is defined as follows: where µ π = E ∞ t=0 γ t φ(s t , a t ) s 0 ∼ P 0 , π is the feature expectation vector of the policy π. Similarly, for any trajectory ξ = {(s t , a t )} t=0,1,... , representing a sequence of state-action pairs, we define the empirical feature expectation vector as µ ξ := ∞ t=0 γ t φ(s t , a t ). Then for a set of trajectories Ξ, we have µ Ξ = 1 |Ξ| ξ∈Ξ µ ξ . For a fully specified MDP M (with reward function R w * where w * 1 ≤ 1), an optimal policy π * is given by π * = arg max π V π . We refer π * as the expert policy that we want to teach to the learner. In IRL, the learner does not know the reward function R w * , and must infer it from the set of trajectories Ξ given by the expert. Each trajectory is obtained by executing the policy π * in the MDP M. The performance of a learned policy π (w.r.t. π * ) in M is evaluated via the feature expectation mismatch given by µ π − µ π * 2 [8].

Maximum Entropy IRL (MaxEnt IRL)
In the MaxEnt IRL [10,35] formulation, the learner seeks to maximize the log-likelihood where π w is the policy obtained by Soft Value Iteration [35, Algorithm. 9.1] with parameter w (see Appendix A). Note that the function L is concave, and its gradient is given by Given a batch of expert demonstrations Ξ, the optimal reward weights vector w * can be obtained by gradient ascent on L. In this work, we consider a natural online variant (cf. [12]) of the batch MaxEnt IRL. In this setting, at each time step t, the learner receives a mini-batch of demonstrations Ξ t and perform a gradient ascent step. Here, the gradient will be g = µ Ξt − µ πw t , the difference between the feature expectation vector of Ξ t and the learner's current feature expectation vector. Algorithm 1 presents the online MaxEnt IRL learner.

Curriculum and Self-Paced Learning
The field of curriculum learning attempts to rank the training examples from the "easy" to "hard" ones based on a "difficulty score". Specifically, we find an ordering γ : such that an online learner (for example a learner using Stochastic Gradient Descent) is exposed to the training data in this particular order. There are many ways to define a curriculum, often depending on the problem of interest.
In [16], the authors rank images of geometrical shapes according to their variability (for example circles are ranked before ellipsoids). In [36], the authors suggest to use the loss of the optimal hypothesis as a difficulty score and prove speedup in convergence for linear regression and binary classification (with hinge loss as the error measure).
Even though designing a generic curriculum for different types of learners can be intuitively good, this approach is limited by the fact that the teacher is not taking into account the current progress of the learner. Self-paced learning [17] addresses this limitation by allowing the curriculum to be designed by the learner. In particular, given a loss function L(y i , f w (x i )) between the ground truth data y i and the estimated output f w (x i ), the learner seeks to minimize where v ∈ [0, 1] n is a weight vector specifying the importance given to each training example.
This objective function is biconvex and can be optimized by alternating minimization of L with respect to w and v. With the fixed w, we This means that at each iteration of the learning process, the learner will select only training examples whose loss is below the threshold λ. Intuitively, the parameter λ should increase over time to be able to select more and more difficult examples with time (a basic rule is for example to increase λ when the set of training examples considered is not growing). The overall procedure is described in Algorithm 2.

Interaction-limited IRL
In this section, we derive two strategies, one for teaching and the other for learning, that seek to improve the training process of an online IRL learner when the learner can not interact with the teacher during the learning process.
Theoretical Insights We define the loss function of a trajectory ξ under the reward weight vector w as (ξ, w) = − log P(ξ|w).
Consider a learner using the Online MaxEnt IRL, as presented in Algorithm 1. At a fixed time t of the learning process, using the update rule w t+1 = w t + η t (µ Ξt − µ πw t ), we have The objective of a greedy teacher would be to provide a batch of demonstrations Ξ t such that Teacher: If the teacher has to choose the next batch, without knowing the current knowledge of the learner (i.e., she only has access to w * ), this teacher could seek to find arg min Ξ − w * , µ Ξ , which corresponds to the demonstrations with high reward with respect to w * . This observation matches with that of [36] regarding curriculum learning in the context of supervised learning problem.
Learner: Conversely, if the learner has to choose the next batch, without the possibility of asking to a teacher (i.e., she only has access to w t ), this learner would like to find min This objective can be interpreted as follows: • In the beginning of the learning process, η t is large, thus the learner will give more attention to minimize µ Ξt − µ πw t 2 , which means she will select a demonstration whose features expectation vector is close to µ πw t , which also means that she will choose demonstrations with high reward with respect to w t .
• After a sufficient number of iterations, η t is close to 0, the learner will minimize w t , µ Ξt , which means the demonstrations with low reward with respect to w t , which can be viewed as "outliers." This observation matches with the intuition behind Self-Paced Learning.

Curriculum Inverse Reinforcement Learning
In this section, we extend the principles of curriculum learning to Inverse Reinforcement Learning. Following the insights proposed in [36], we rank the demonstrations of Ξ according to their loss with respect to the true reward weight vector w * , i.e., (ξ, w * ). There are two possible interpretations of this objective function: • Reward-based curriculum (R-CIRL): Using the fact that, in the MaxEnt IRL framework, a first curriculum consists of ordering the trajectories of Ξ according to their reward (under the true reward weight vector w * ).
• Probability-based curriculum (P-CIRL): Another way of ranking the demonstrations would be to directly compute, for a trajectory ξ of finite length H, P(ξ|w * ) based on the state-action probability

Self-Paced Inverse Reinforcement Learning
In this section, we use (ξ, w) as a loss function to extend the principles of self-paced learning to IRL. The resulting procedure, presented in Algorithm 3, is a special case of the online MaxEnt IRL algorithm presented in Algorithm 1.
if λ is too small then increase λ 7: return w T

Experiments
In this section, we demonstrate the performance of our algorithms in gridworld environments. In Appendix C, we provide results for experiments with a real robot.

Experimental Setup
Preliminaries The error metric used in our experiments is the distance between the learner's and the teacher's features expectation vectors. Because we want to study the effect of the demonstrations' ordering on the learning process, when a demonstration is provided, it is discarded from the pool.
Baselines CIRL focuses on the ordering of a demonstrations' set from the teacher point of view for an online learner, thus we compare CIRL to a teacher giving demonstrations at random (i.e. a teacher with no particular strategy) and a teacher doing the opposite of what the curriculum suggests (anticurriculum). SPIRL focuses on how to process actively, from the learner's point of view, a fixed batch of demonstrations (the learner has access to the whole batch at any time), we compare it to a learner computing his gradient with the full batch of demonstrations at each time step.

Learner Model
The learner is an online learner, as described in Algorithm 1, using gradient ascent with learning rate η t = 1 t .
Learner Initialization Since the quality of the sequence of demonstrations provided highly depends on the initial w of the learner, we will repeat the process several times (around 200 times for each environment and each learning/teaching modality) with a different initialization of the learner's reward weights w 0 , sampled uniformly in [−1, 1] d .  Gridworlds We will first test our approach on three different 20 × 20 gridworlds with different reward maps, as it can be seen in Figure 2. The pool of demonstrations in these gridworlds consists of 100 expert demonstrations which result from the expert policy starting from 100 different states in the grid. The curriculums used for these environments can be viewed in Appendix B. Hanoi Towers To study the robustness of our approach with respect to domains with sparse rewards, we consider the puzzle of Hanoi Towers, whose goal is to move some rings (here 4) lying around different rods (here 3) to a final configuration (see Figure 3). In this puzzle, each move consists in taking the disk which is at the top of a stack, with the rule that large disks always have to be under smaller disks. We consider a batch of expert demonstrations, corresponding to the demonstration of an optimal teacher solving the puzzle for each of the possible starting states (which makes 3 4 = 81 demonstrations).  Figure 4, we show the evolution of the features expectation matching error. Table 1 reports the error at the end of the training process (when every expert demonstration has been given once).

Results (SPIRL)
In Figure 5, we show the evolution of the features expectation matching error. Table 2 reports the error at the end of the training process (when every expert demonstration has been given once). The different curves correspond to different update steps λ in the SPIRL algorithm.

Additional Experiments
We also study the robustness of our approach in different contexts. To do this, we will only run our experiments on the last gridworld (the right one in Figure 2).

Suboptimal Demonstrations
We study the influence of suboptimal demonstrations on the learner's performance. The teacher provides demonstrations following the optimal policy, but with a fixed proportion of random actions, respectively 0 % (results from Tables 3 and 4), 10 % and 30 %. Results are presented in Tables 5 and 6. The error is the difference fetween the learner's policy and the teacher's optimal policy (i.e with no random actions).

Conclusions
In this paper, we presented CIRL and SPIRL, two approaches guided by theoretical insights of the MaxEnt IRL theory, which deal with the absence of teacher-learner interaction in Inverse Reinforcement Learning. Using experiments in simulated environments and with a real robotic task, we show that our algorithms allow an improvement in the learning speed compared to a teacher providing demonstrations at random (for CIRL) and to a learner processing a whole batch of demonstrations (for CIRL). Our experimental results show that CIRL will provide first, in the gridworlds, demonstrations which are close to a goal state, without specifying any obstacles or dangerous zones. Future work could focus on designing curriculums for IRL with hard constraints such as the fact that obstacles should be learned as fast as possible in the learning process.

A Maximum Entropy Inverse Reinforcement Learning
In the Maximum Causal Entropy framework, we assume a probability distribution over the trajectories based on the exponential of the reward of these trajectories. We have To satisfy this condition, the action probability π w is given by Q w (s, a)) .
Let us define the soft optimal Bellman operator B w : R |S| → R |S| such that ∀s ∈ S, We can prove that B w is a contraction and use the fact that V w is a fixed point of B w to compute V w . This procedure called "Soft Value Iteration" is described in Algorithm 4.

Algorithm 4 Soft Value Iteration
Require: Weights vector w 1: Initialize V ∈ R |S| 2: while not converged do 3: for (s, a) ∈ S × A do

B Visualization of the Curriculums
Since there is a one-to-one mapping between the expert demonstrations and the cells of the gridworld, we can vizualize the order of the demonstrations in the curriculums in the map. Based on the considerations made in Section 4.1, the curriculums which are chosen for each environment are shown in Figure 8.
The bright areas correspond to the starting state of the demonstrations with high reward for P-CIRL or high probability for P-CIRL (i.e. demonstrations which will be given early in the learning process).

C Robotics Experiment
Experimental Setup In this section, we present an application of CIRL and SPIRL for the learning of a robotic task. The task consists of moving a ball held with a spoon and dropping the ball in a cup, while avoiding obstacles. The robot used for this experiment is a Franka Emika Panda robot. The experimental setup can be seen in Figure 9. The state space of the robot is of 7 dimensions, corresponding to its joint angles. We use a Gaussian Mixture Model to split the continuous state The expert reward will be computed using a distance between the different states of the GMM. We record by kinesthetic teaching 33 different demonstrations of the task, with different initial states. The movements required to reach the cup while keep the spoon horizontal are varied, notably due to the robot's joint angle limits and the obstacle.
To apply the framework of discrete Markov Decision Processes to this continuous environment, in a first phase, we record with the robotic arm many different states in which the robot can be (without trying to record this task). Once these states are recorded, we augment them with the 33 demonstrations recorded for the task.
Then, we use a Gaussian Mixture Model to segment all the states recorded during the two first phases into 40 clusters. This discretization of the state space allows a more compact representation than discretizing each coordinate. The modeling of the state space with multivariate normal distributions provides a convenient way to move from a state to another using classical robotics techniques such as linear quadratic regulator (LQR).
Note that since we have the constraint that the spoon should be kept approximately horizontal so that the ball does not fall, the dimensionality of the allowed joints configurations is reduced.
To make it more realistic, we restrict actions such that we can only move from a state to adjacent states. To compute the distance between two states, we compute the integral of the product of the probability density functions of the states (seen as multivariate normal distributions). The historical lowest value of this integral (computed over the data recorded in the two first phases) will serve as a threshold to determine which states are adjacent and which are not, even if they were not visited during the recording phase.
Instead of setting hand-engineered reward weights for the teacher, we compute the reward based on the integral of the product of the probability density functions of the states.

Results
In this experiment, we study CIRL with the reward-based curriculum. In addition to the error in features expectations between the set of expert demonstrations and the learner's policy, we look at the expected reward of a trajectory (using the distance between the states of the GMM).
Results of this experiment are presented in Figure 10.
Comments on the Video In the video attached to this paper, we present the experimental setup and show examples of learned policies in the robotics experiment.
The first sequence of the video presents a human demonstrator showing the robot how to do the task.
The three following sequences show three expert demonstrations: the first and the last demonstration of the reward-based curriculum and another demonstration. We replay these demonstrations without the expert for a better visualization. The two last sequences of the video present two examples of trajectories produced by policies learned with MaxEnt IRL. The first one comes from a policy learned after one step of learning with the curriculum teacher, the second one after one step of learning with the anticurriculum teacher. We see that the first trajectories goes directly to the goal whereas the second one seems to explore a lot of states before reaching the goal.

C.1 Discussion
Based on the results presented in this section, CIRL outperforms the random teacher in most of the environments. The two curriculums designed have comparable performance. SPIRL also outperforms the batch learner, with its performance depending on the update step λ.
SPIRL and CIRL show robustness with respect to stochastic transitions and inexact computation of the features expectations, which is a first step towards adapting these strategies to continuous control tasks. In [37], the authors propose a gradient update rule for continuous Inverse Optimal Control (based on an approximation of the soft Bellman policy using a second-order Taylor expansion of the reward). Future work could focus on extending our analysis for this new update rule and devise new teaching strategies Also, our algorithms do not outperform the baselines when the learner is using an adaptive optimization strategy. Future work will investigate whether update rules better suited for online learning could aleviate this issue, e.g. reusing the previously used demonstrations to avoid forgetting.
In the robotics experiment, even if CIRL outperforms the random teacher using the different metrics, the difference with the random teacher is not as significant as in the other environments. This might be due to the modeling of the environment into an MDP and to the fact that the human demonstrator is not optimizing a reward function in a Markov Decision Process but rather doing the task on intuition, which might lead to sub-optimal demonstrations in the batch.