On-Policy Imitation Learning from an Improving Supervisor

Ashwin Balakrishna * 1 Brijen Thananjeyan * 1 Jonathan Lee 1 Arsh Zahed 1 Felix Li 1
Joseph E. Gonzalez 1 Ken Goldberg 1

Abstract
Most on-policy imitation algorithms, such as
DAgger, are designed for learning with a fixed
supervisor. However, there are many settings
in which the supervisor improves during policy
learning, such as when the supervisor is a humanperforming a novel task or an improving algorithmic controller. We consider learning from an“improving supervisor” and derive a bound on thestatic-regret of online gradient descent when aconverging supervisor policy is used. We present
an on-policy imitation learning algorithm, Follow the Improving Teacher (FIT), which uses a
deep model-based reinforcement learning (deep
MBRL) algorithm to provide the sample complexity benefits of model-based methods but enable
faster training and evaluation via distillation intoa reactive controller. We evaluate FIT with experiments on the Reacher and Pusher MuJoCodomains using the deep MBRL algorithm, PETS,
as the improving supervisor. To the best of ourknowledge, this work is the first to formally consider the setting of an improving supervisor in
on-policy imitation learning.

1. Introduction
In on-policy imitation learning, a policy is iteratively trained
to match the behavior of a supervisor on a particular task
on the distribution of the learned policy. In algorithms suchas DAgger (Ross et al., 2011a), the supervisor serves as alabeler, providing feedback on the appropriate controls forstates visited by the learner. Ross et al. (2011a) show that
DAgger can be interpreted as a no-regret algorithm in the
online-learning setting, and provides vanishing regret guarantees when the policy update step via Follow The Leader*

Equal contribution 1 Department of EECS, University of California, Berkeley. Correspondence to: Ashwin Balakrishna <ashwin balakrishna@eecs.berkeley.edu>, Brijen Thananjeyan <brijen@eecs.berkeley.edu>.
Real-World Sequential Decision Making Workshop at ICML 2019,
Copyright 2019 by the author(s).

(FTL) has vanishing regret (Ross et al., 2011a; Kakade &Tewari, 2009).
Prior work focuses on imitation learning algorithms with afixed supervisor (Ross et al., 2011a; Sun et al., 2017; Leeet al., 2019; Cheng & Boots, 2018). However, in this work,
we consider a convergent sequence of supervisors. This
context is motivated by practical scenarios in which thesupervisor may improve its task performance substantiallyas time progresses, e.g., as a human supervisor learns how
to play a game they have never played or teleoperate a robot
with unfamiliar controls.
We investigate how initially suboptimal labeling feedback
affects the incurred static regret of the learned policy. Thisis particularly relevant to long time horizon tasks, in whicha large-scale system is designed to improve over time on adifficult task using human experience as feedback. In thiswork, we show that results are not significantly affected
when the supervisor is initially suboptimal, as long as it
converges to the desired policy.
Learning from improving supervisors also has applications
to deep model-based reinforcement learning, which has
attracted interest due to the improved sample-efficiency
compared to model-free methods (Chua et al., 2018). Recent model-based RL algorithms for continuous-control domains represent system dynamics with a deep neural network, which is updated on-policy, and use model-predictive
control (MPC) to generate controls (Chua et al., 2018; Nagabandi et al., 2018). However, generating controls for dynamics models represented by deep neural networks often
involves significant online computation, making it infeasible
to collect high-frequency policy rollouts from the modelbased controller. This significantly slows down both training, which requires policy rollouts for policy evaluation, andevaluation at test-time, making direct application of thesetechniques difficult in many robotic tasks. We focus on thissetting in this work.
Motivated by the idea of learning from an improving supervisor, we present an on-policy imitation learning algorithm
to train a model-based deep reinforcement learning agent
using off-policy data from a model-free learner policy. The
model-based supervisor is used to generate labels, which arethen used to update the learner. This enables fast policy eval-On-Policy Imitation Learning from an Improving Supervisor

uation since rollouts are collected from a model-free policy,
so the deep model-based controller can relabel visited statesin a rollout in parallel at the end of a rollout rather thanserially. This combines the sample complexity advantagesof deep model-based methods with the fast policy evaluationof model-free RL.
The contributions of this work are:
1. New setting for on-policy imitation learning and sublinear regret guarantees if online gradient descent (OGD)
is used to learn from an improving supervisor.
2. A new algorithm, FIT, which involves training a modelfree policy to track an improving deep model-based
RL algorithmic supervisor.
3. Experimental data suggesting that FIT can achieve
final return within 16 % of the method proposed in(Chua et al., 2018) on both the Reacher and Pusher
MuJoCo domains while utilizing fully off-policy datafrom a model-free policy, suggesting the potential forsignificant speedups in learning and policy evaluation.

2. Related Work
Imitation learning is an effective method for learning complex behaviors efficiently from the demonstration data ofa supervisor. In this section, we review related work in
online policy learning via imitation and deep model-based
reinforcement learning. We also briefly discuss past workin supervised and active learning involving learning fromstochastic and multiple supervisors.
2.1. Learning from Stochastic Supervisors
Past work in supervised learning involving learning fromnoisy labels (Natarajan et al., 2013; Khetan et al., 2018) typically has focused mainly on classification. Common settings
are cases where labels either are noise-injected versions oforacle labels (Natarajan et al., 2013) or labels come from avariety of different supervisors (Khetan et al., 2018). There
has also been interest in intelligently aggregating the resultsof multiple labelers for each instance in a dataset (Raykar
et al., 2009; Richardson & Domingos, 2003; Laskey et al.,2016a). Finally, there has also been work in active learning
to determine which of a set of supervisors, of varying quality, to query for labels (Zhang & Chaudhuri, 2015; Yan et al.,2012). Distinct from these works, we focus specifically on
the imitation learning setting and provide analysis when asupervisor is improving over time.
2.2. On-Policy Imitation Learning
Online imitation learning algorithms that directly learn reactive policies from a supervisor were recently popularizedwith DAgger in (Ross et al., 2011b). DAgger is an iterative
approach that improves by deploying the learner’s current

policy and receiving supervisor feedback. It was shownthat this approach achieves significant performance gains
in both theory and practice over analogous offline methods, e.g. (Bagnell, 2015; Pomerleau, 1989). Since DAgger,a number of practical extensions have been proposed to,for example, ensure safety (Menda et al., 2017), smooth
controllers (Le et al., 2016), and relieve burden on humansupervisors (Laskey et al., 2016b). Furthermore, online
methods have been applied with both human (Laskey et al.,2017) and algorithmic supervisors (Pan et al., 2018) such
as MPC. These works typically assume that a single, fixed
supervisor is the guiding policy. We propose a setting inwhich the supervisor improves over time, which is common
when learning from human demonstrators or when distillingan expensive, iteratively improving controller into a policythat can be efficiently executed in practice.
Since the introduction of DAgger, theoretical analyses of theonline imitation learning algorithms (Ross et al., 2011b; Sunet al., 2017) have often been embedded in the online learning
framework (Zinkevich, 2003). Recently, convergence results
and stronger guarantees on regret metrics such as dynamic
regret have been shown for a fixed supervisor (Cheng &Boots, 2018; Lee et al., 2019). We present an analysis of
on-policy imitation learning from a convergent sequence ofsupervisors. Specifically, we show that OGD can achieve
comparable guarantees in the improving supervisor setting.
2.3. Deep Model-Based Reinforcement Learning
Deep model-based reinforcement learning has seen significant interest due to the improvement in sample complexity
when compared to model-free methods (Deisenroth & Rasmussen, 2011; Levine et al., 2015; Nagabandi et al., 2018;
Chua et al., 2018). Recently, Nagabandi et al. (2018) and
Chua et al. (2018) showed that using neural network dynamics models to perform MPC gives comparable asymptotic performance to model-free reinforcement learning
methods while maintaining the sample complexity gains
of model-based methods. However, solving the MPC objective over neural network dynamics models often requires
expensive, derivative-free, sampling-based approaches suchas the Cross-Entropy Method (CEM), significantly slowing
down policy evaluation. In this work, we investigate how
distilling MPC into a model-free policy by treating it as
an improving supervisor can be used to accelerate policy
evaluation and thus potentially speed up both training andevaluation of these methods. The closest related work in thisregard is (Kahn et al., 2017). Here, an MPC policy is trainedwith true state information, but constrained to be close toa model-free policy which only has access to observations.
However, Kahn et al. (2017) assume known dynamics, andthus the MPC supervisor does not improve with time.

On-Policy Imitation Learning from an Improving Supervisor

3. Improving Supervisor Framework andAnalysis
On-policy imitation learning involves executing a policyin the environment, and then soliciting feedback from asupervisor on the visited states. This is in contrast to offpolicy imitation learning methods, such as behavior cloning,in which policy learning is performed entirely on statesfrom the supervisor’s state distribution rather than that of thelearner. Here we outline a theoretical framework in whichto study on-policy imitation learning with an improving
supervisor and provide an analysis of the static regret of
OGD in this setting.
3.1. Definitions
1. Supervisor: Consider a sequence of N supervisors (labelers), (ψi )Ni=1 , where ψi is any function on
RS → RA , S and A are the sets of allowed states andactions, and S and A are the dimensionality of thesesets respectively. Supervisor ψi provides labels forimitation learning policy updates at iteration i.
2. Learner: The learner is represented at iteration i bya parameterized policy πθi on RS → RA where πθi
is differentiable in the policy parameter θi ∈ K. ΠK
denotes the Euclidean projection operator onto K.
3. Loss: We specifically consider losses of the formli (πθi , ψ) = Es∈{Si } kπθi (s) − ψ(s)k2

3.2. Assumptions
In our regret analysis we adopt the following standard assumptions.
1. Strongly convex losses: lθi (πθi , ψ) is strongly convex
with respect to θ with parameter α ∈ R+ . Precisely,
we assume thatli (πθ2 , ψ) ≥ li (πθ1 , ψ) + ∇θ li (πθ1 , ψ)T (θ2 − θ1 )+αkθ2 − θ1 k22 ∀ θ1 , θ2 ∈ K
2
2. Bounded parameter space diameter: kθi − θj k ≤D ∀ θi , θj ∈ K where D ∈ R+ .
3. Bounded action space: The diameter of the action
space A of the policy is bounded, specifically thatka1 − a2 k2 ≤ δ∀ a1 , a2 ∈ A

where δ ∈ R+ .
4. Bounded operator norm of policy Jacobian:k∇θ πθi (s)k ≤ G for all s ∈ S where G ∈ R+ and||·|| is a subadditive operator norm. Note that this also
implies that the loss function gradients are boundedsincek∇θ li (πθ , ψ)k =kEs∈{Si } 2(∇θ πθ (s))T (πθ (s) − ψ(s)) k ≤Es∈{Si } k2(∇θ πθ (s))T (πθ (s) − ψ(s))kby convexity of norms k·k and Jensen’s inequality.

where k·k is the 2-norm and {Si } is the set of states in
the minibatch processed at iteration i. {Si } is sampledfrom the distribution of trajectories p(τ |θi ) generatedby πθi . All gradients of li are taken with respect to θin the first argument and not the θi parameterizing the
trajectory distribution. Specifically, ∇θ li (πθi , ψ) :=∇θ li (πθ , ψ)|θ=θi .
4. Regret: We analyze the regret of FIT with respect tothe best policy in hindsight that has labels from the final
supervisor ψN for the whole dataset. Note, however,that during learning, labels are provided not by ψN ,but by supervisor ψi at iteration i. This results in amore difficult regret metric than is typically consideredin static regret analysis for on-policy imitation learningsince labels are provided by the improving supervisor
but regret is evaluated with respect to the best policy
given labels from the final supervisor.

RegretN =N
Xli (πθi , ψN ) −i=1

where θ? = arg min
θ∈K

N
X

li (πθ? , ψN )

i=1
N
X
i=1

li (πθ , ψN )Then, we have thatk(∇θ πθ (s))T (πθ (s) − ψ(s))k ≤k∇θ πθ (s)kkπθ (s) − ψ(s)k ≤ Gδdue to Assumption 3 and subadditivity. Thus, we havethat ∀θ, θi ∈ K, ∀ψk∇θ li (πθ , ψ)k ≤ 2Gδ.
The assumptions in this section and the loss formulation are
consistent with those in Hazan et al. (2016) and Osa et al.
(2018) for analysis of online projected gradient descent andimitation learning algorithms.
3.3. Regret Analysis
To motivate FIT and the idea of learning from an improving
supervisor, we show that given that the learner is represented
by a strongly convex policy and satisfies other standard conditions, OGD has sublinear static regret with respect to thebest policy in hindsight with labels from the final supervisor
policy. Hazan et al. (2016) derive sublinear regret guarantees
for OGD under similar assumptions with a static supervisor; we extend this analysis by showing that the additional

On-Policy Imitation Learning from an Improving Supervisor

asymptotic regret depends only on the convergence rate of
the supervisor. Note that this is different from the type ofregret analysis in (Ross et al., 2011a) and other on-policy
imitation learning algorithms since in this setting, labels
come not from a fixed supervisor, but from an improving
supervisor during learning.
Theorem 1. For loss function li (πθi , ψ) satisfying theabove assumptions, the expected static regret of OGD withlabels from (ψi )N
i=1 can be bounded above as follows:
RegretN ≤
+ 2GD

N
X


2G2 δ 2 
1 + log N
α
Es∈{Si } kψN (s) − ψi (s)kwhich itself is updated using data from the model-free rollouts. Note that if the algorithmic supervisor has slow policy
evaluation, such a procedure can speed up policy learningsince the supervisor can label each state in a given rollout
in parallel after the rollout has completed rather than serially at each timestep of every policy rollout. If using deep
MPC algorithms such as those presented in (Chua et al.,2018; Nagabandi et al., 2018) as the algorithmic supervisor,
the supervisor is updated by updating the dynamics model
used for MPC with transitions collected from the learnerrollouts. In general, any off-policy algorithmic supervisor
can be used. There are also many possible choices for the
on-policy imitation learning algorithm, such as OGD or
DAgger. This is illustrated in Algorithm 1 below.

i=1

Proof of Theorem 1 can be found in the appendix.
Theorem 2. If Es∈{Si } kψi (s) − ψN (s)k ≤ fi w.p. 1∀N > i for some sequence (fi )N
i=1 where limi→∞ fi = 0,
the expected static regret of OGD is sublinear:
N
X

Es∈{Si } k(ψN (s) − ψi (s)k = O(N )i=1

Algorithm 1 Follow the Improving Teacher (FIT)
Require: Randomly initialized off-policy algorithmic
supervisor, ψ0 , model-free policy πθ0for i ∈ {1, . . . , N } doSample T step trajectory from πθiGet dataset Di = {(s, ψi (s))}
Update πθi+1 and ψi+1 using Di
end forreturn πθN

Proof of Theorem 2 can be found in the appendix.
Given Theorem 1, if we choose fi = Ci for C ∈ R+ , wepay no extra asymptotic penalty in regret, achieving a regretbound of
 2 2


2G δ
+ 2GDC
1 + log N(1)α
We also note that any faster rate than fi = Ci also avoids
additional asymptotic regret.
This motivates further exploration of on-policy imitation
learning algorithms in the improving supervisor setting. See
appendix for experimental studies on empirical regret andthe effect of label quantity and quality on learning results.

4. Follow the Improving Teacher (FIT)
Motivated by the analysis in Section 3, we present Follow
the Improving Teacher (FIT), which enables accelerated policy evaluation for deep model-based reinforcement learning.
Instead of collecting policy rollouts using an an algorithmic supervisor that is expensive to query online, FIT usesa model-free policy to collect rollouts on each iteration,
but labels for each state in the rollout are provided by thesupervisor to refit the policy. FIT can be thought of as ameta-algorithm, which updates the model-free policy andalgorithmic supervisor at each iteration using updates given
by an on-policy imitation learning algorithm trained via labels from an off-policy reinforcement learning algorithm,

5. Experiments
In all experiments, we run FIT using the model-based deep
reinforcement learning algorithm, PETS (Chua et al., 2018),
as the improving supervisor, DAgger as the on-policy imitation learning algorithm, and squared loss between learnerand supervisor as the imitation learning loss function. We
consider the PR2 Reacher and Pusher MuJoCo domains
from (Chua et al., 2018). See the appendix for further details on the parameters used for PETS.
For experiments, task return is reported for FIT, the supervisor, and PETS. Returns for FIT and the supervisor arecomputed by rolling out the model-free learner policy andmodel-based controller after each training iteration and computing the task return respectively. Note that the supervisor
here is trained on off-policy data from the learner, so thedifference between the learner and supervisor performancemeasures how effectively the learner is able to track thesupervisor performance. Furthermore, we also report task
return for the original PETS algorithm, which is trainedon data from its own policy. Thus, the difference in performance between the supervisor and PETS measures how
important on-policy data is for supervisor performance.
In Figure 1, we show the empirical regret and return for FIT,
where the learner is represented with a linear policy trained
via ridge-regression with regularization parameter α = 1.

On-Policy Imitation Learning from an Improving Supervisor
Empirical Regret: Reacher

2000

Empirical Regret: Pusher
80

1750
1500

40

750

30

500

20

250

10
0

20

40
60
Training Iterations

80

0

100

(a) Empirical Regret of FIT on
PR2 Reacher Task

ReturnRegretRegret

50

1000

0

200

60

1250

0

20

40
60
Training Iterations

80(b) Empirical Regret of FIT on
PR2 Pusher Task

40
60
Training Iterations

80

40
60
Training Iterations

ReturnReturn

100

0

20

40
60
Training Iterations

80

100

(b) Pusher Returns

learnersupervisor
PETS
20

80

learnersupervisor
PETS

100

Return: Pusher

0

40
60
Training Iterations

Return: Pusher

50
100
150
200
250

(c) Reacher Returns
50
100
150
200
250

20

(a) Reacher Returns

Return20

learnersupervisor
PETS
0

100

learnersupervisor
PETS
0

400
600

Return: Reacher
50
100
150
200
250

Return: Reacher

0

70

80

100

(d) Pusher Returns
Figure 1. FIT with a linear learner policy: We first show theempirical regret of FIT for (a) Reacher and (b) Pusher, which show
clearly sublinear growth as expected. We also show training curves
for the learner, supervisor and PETS on (c) Reacher and (d) Pusher.
FIT is not only able to successfully track the supervisor on both
domains, but also performs well compared to PETS. However,
performance is slightly better on Reacher.

We observe that the empirical regret shows a sub-linear
growth pattern for both Reacher and Pusher as shown in Figures 1a and 1b. We also see in Figures 1c and 1d that for bothtasks, that not only is the learner able to successfully track
the supervisor, but also that the supervisor performance is
not significantly harmed by training on off-policy data inthese settings. However, we notice that for the Pusher task,
both the learner and supervisor converge to a slightly worse
final return than PETS.
Finally, to determine whether FIT can effectively scale tomore complex learner policy representations and to determine whether a more expressive learner could close thegap between FIT and PETS on the Pusher task, we repeat
the above experiments with the learner represented by aneural network with 2 hidden layers with 20 hidden units
each, ReLU activations, and trained using the Adam optimizer. Results are shown in Figure 2. The learner is able
to match the supervisor and PETS closely for both tasks,
demonstrating the efficacy of FIT in these settings.
This result is promising because if the model-free learnerpolicy is able to achieve similar performance when tracking
a model-based reinforcement learning supervisor compared

Figure 2. FIT with a neural network learner policy: Training
curves for the learner, supervisor and PETS on (a) Reacher and (b)Pusher. We see that FIT is not only able to successfully track thesupervisor on both domains, but also performs well compared to
PETS for both tasks.

to the supervisor on its own distribution, we achieve thesample complexity benefits of model-based reinforcement
learning while achieving the low online computation timeof model-free methods. This has potential to accelerate bothtraining and testing times for model-based reinforcement
learning algorithms by simply labeling states visited by amodel-free policy in parallel after each rollout. We hope
to explore this further in future work. As an initial checkto determine the potential speedup that FIT could provide,
we measure the average rollout time of the model-based
controller PETS and the model-free learner policy over 50
rollouts for the Reacher task on a desktop running Ubuntu
16.04 with a 3.60 GHz Intel Core i7-6850K, 12 core CPU
and an NVIDIA GeForce GTX 1080. On the Reacher task,
we find that PETS has an average rollout time of 25.25 seconds while the model-free policy has an average rollout timeof 0.324 seconds, demonstrating that a significant speedup
is possible with a fully parallel implementation.

6. Conclusion
We introduce a new setting for on-policy imitation learning in which the expert policy is not fixed, but improving
over time. We show that if the learner policy is strongly
convex, and has bounded parameter space diameter, action
space, and Jacobian operator norm, OGD with labels froman improving supervisor yields sublinear regret with respect
to the best policy in hindsight trained with labels from thefinal supervisor. We use this to motivate a new algorithm,
FIT, which provides the sample complexity benefits of deep
MBRL while enabling the fast policy evaluation time ofmodel-free methods. In future work, we hope to provide
regret analysis for stochastic supervisors with specific noise

On-Policy Imitation Learning from an Improving Supervisor

profiles and consider a more general class of surrogate loss
functions. We are also interested in implementing FIT in aparallelized manner to show that learning from an improving supervisor allows substantial speedup in wall-clock time
without significantly affecting task performance.

7. Acknowledgments
This research was performed at the AUTOLAB at UC Berkeley inaffiliation with the Berkeley AI Research (BAIR) Lab, Berkeley
Deep Drive (BDD), the Real-Time Intelligent Secure Execution(RISE) Lab, and the CITRIS ”People and Robots” (CPAR) Initiative. This research was supported in part by the Scalable Collaborative Human-Robot Learning (SCHooL) Project, NSF National
Robotics Initiative Award 1734633. Authors were also supported
in part by donations from Siemens, Google, Toyota Research Institute, Autodesk, Knapp, Honda, Intel, Comcast, Hewlett-Packard
and by equipment grants from PhotoNeo, NVidia, and Intuitive
Surgical. We thank our colleagues who provided helpful feedback,in particular Ajay Tanwani, Marius Wiggert, and Jeff Ichnowski.

On-Policy Imitation Learning from an Improving Supervisor

References
Bagnell, J. Andrew (Drew). An invitation to imitation. Technical Report CMU-RI-TR-15-08, Carnegie Mellon University,
Pittsburgh, PA, March 2015.
Cheng, Ching-An and Boots, Byron. Convergence of value aggregation for imitation learning. International Conference on Artificial Intelligence and Statistics, abs/1801.07292, 2018. URL
http://arxiv.org/abs/1801.07292.
Chua, Kurtland, Calandra, Roberto, McAllister, Rowan, andLevine, Sergey. Deep reinforcement learning in a handful of trials using probabilistic dynamics models. NeurIPS,
abs/1805.12114, 2018. URL http://arxiv.org/abs/
1805.12114.
Deisenroth, MP. and Rasmussen, CE. Pilco: A model-based anddata-efficient approach to policy search. In Proceedings of the
28th International Conference on Machine Learning, ICML
2011, pp. 465–472. Omnipress, 2011.
Hazan, Elad et al. Introduction to online convex optimization.
Foundations and Trends R in Optimization, 2(3-4):157–325,
2016.

Lee, Jonathan, Laskey, Michael, Tanwani, Ajay Kumar, Aswani,
Anil, and Goldberg, Kenneth Y. A dynamic regret analysis andadaptive regularization algorithm for on-policy robot imitation
learning. WAFR, 2019.
Levine, Sergey, Wagener, Nolan, and Abbeel, Pieter. Learning contact-rich manipulation skills with guided policy search.
CoRR, abs/1501.05611, 2015. URL http://arxiv.org/
abs/1501.05611.
Menda, Kunal, Driggs-Campbell, Katherine, and Kochenderfer,
Mykel J. Dropoutdagger: A bayesian approach to safe imitation
learning. arXiv preprint arXiv:1709.06166, 2017.
Nagabandi, Anusha, Kahn, Gregory, Fearing, Ronald S., andLevine, Sergey. Neural network dynamics for model-based
deep reinforcement learning with model-free fine-tuning. ICRA,
2018.
Natarajan, Nagarajan, Dhillon, Inderjit S, Ravikumar, Pradeep K,
and Tewari, Ambuj. Learning with noisy labels. In Burges,
C. J. C., Bottou, L., Welling, M., Ghahramani, Z., andWeinberger, K. Q. (eds.), Advances in Neural Information
Processing Systems 26, pp. 1196–1204. Curran Associates,
Inc., 2013. URL http://papers.nips.cc/paper/
5073-learning-with-noisy-labels.pdf.

Kahn, Gregory, Zhang, Tianhao, Levine, Sergey, and Abbeel,
Pieter. Plato: Policy learning using adaptive trajectory optimization. 2017 IEEE International Conference on Robotics andAutomation (ICRA), pp. 3342–3349, 2017.

Osa, Takayuki, Pajarinen, Joni, Neumann, Gerhard, Bagnell, J. Andrew, Abbeel, Pieter, and Peters, Jan. An algorithmic perspective on imitation learning. Foundations and Trends in Robotics,
2018. URL http://arxiv.org/abs/1811.06711.

Kakade, Sham M and Tewari, Ambuj. On the generalization
ability of online strongly convex programming algorithms. In
Koller, D., Schuurmans, D., Bengio, Y., and Bottou, L. (eds.),
Advances in Neural Information Processing Systems 21, pp.
801–808. Curran Associates, Inc., 2009.

Pan, Yunpeng, Cheng, Ching-An, Saigol, Kamil, Lee, Keuntak,
Yan, Xinyan, Theodorou, Evangelos, and Boots, Byron. Agile
autonomous driving via end-to-end deep imitation learning. In
Proceedings of Robotics: Science and Systems (RSS), 2018.

Khetan, Ashish, Lipton, Zachary C., and Anandkumar, Anima.
Learning from noisy singly-labeled data. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=H1sUHgb0Z.
Laskey, Michael, Lee, Jonathan, Chuck, Caleb, Gealy, David,
Hsieh, Wesley, Pokorny, Florian T, Dragan, Anca D, and Goldberg, Ken. Robot grasping in clutter: Using a hierarchy ofsupervisors for learning from demonstrations. Automation Science and Engineering (CASE), 2016 IEEE, pp. 827–834, 2016a.
Laskey, Michael, Staszak, Sam, Hsieh, Wesley Yu-Shu, Mahler,
Jeffrey, Pokorny, Florian T, Dragan, Anca D, and Goldberg,
Ken. Shiv: Reducing supervisor burden in dagger using support
vectors for efficient learning from demonstrations in high dimensional state spaces. In 2016 IEEE International Conference on
Robotics and Automation (ICRA), pp. 462–469. IEEE, 2016b.
Laskey, Michael, Chuck, Caleb, Lee, Jonathan, Mahler, Jeffrey, Krishnan, Sanjay, Jamieson, Kevin, Dragan, Anca, and Goldberg,
Ken. Comparing human-centric and robot-centric sampling
for robot deep learning from demonstrations. In 2017 IEEE
International Conference on Robotics and Automation (ICRA),
pp. 358–365. IEEE, 2017.
Le, Hoang M, Kang, Andrew, Yue, Yisong, and Carr, Peter.
Smooth imitation learning for online sequence prediction. arXiv
preprint arXiv:1606.00968, 2016.

Pomerleau, Dean A. Alvinn: An autonomous land vehicle in aneural network. In Advances in neural information processing
systems, pp. 305–313, 1989.
Raykar, Vikas C., Yu, Shipeng, Zhao, Linda H., Jerebko, Anna,
Florin, Charles, Valadez, Gerardo Hermosillo, Bogoni, Luca,and Moy, Linda. Supervised learning from multiple experts: Whom to trust when everyone lies a bit. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, pp. 889–896, New York, NY,
USA, 2009. ACM. ISBN 978-1-60558-516-1. doi: 10.
1145/1553374.1553488. URL http://doi.acm.org/10.
1145/1553374.1553488.
Richardson, Matthew and Domingos, Pedro. learning-withknowledge-from-multiple-experts. In Proceedings of theTwentieth International Conference on Machine Learning, pp. 624–631. AAAI Press, January 2003.
URL
https://www.microsoft.com/en-us/research/
publication/learning-with-knowledge-from\-multiple-experts/.
Ross, Stéphane, Gordon, Geoffrey J., and Bagnell, J. Andrew.
A reduction of imitation learning and structured prediction to
no-regret online learning. In AISTATS, 2011a.
Ross, Stéphane, Gordon, Geoffrey J, and Bagnell, J Andrew. A
reduction of imitation learning and structured prediction to noregret online learning. International Conference on Artificial
Intelligence and Statistics, 2011b.

On-Policy Imitation Learning from an Improving Supervisor
Sun, Wen, Venkatraman, Arun, Gordon, Geoffrey J., Boots, Byron,and Bagnell, J. Andrew. Deeply AggreVaTeD: Differentiable
imitation learning for sequential prediction. In Precup, Doina
and Teh, Yee Whye (eds.), Proceedings of the 34th International
Conference on Machine Learning, volume 70 of Proceedingsof Machine Learning Research, pp. 3309–3318, International
Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.
Yan, Yan, Rosales, Romer, Fung, Glenn, Farooq, Faisal, Rao,
Bharat, and Dy, Jennifer. Active learning from multiple knowledge sources. In Lawrence, Neil D. and Girolami, Mark(eds.), Proceedings of the Fifteenth International Conferenceon Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pp. 1350–1357, La
Palma, Canary Islands, 21–23 Apr 2012. PMLR. URL http://proceedings.mlr.press/v22/yan12.html.
Zhang, Chicheng and Chaudhuri, Kamalika. Active learning from weak and strong labelers.
In Cortes, C.,
Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 28, pp. 703–711. Curran Associates, Inc.,2015.
URL http://papers.nips.cc/paper/
5988-active-learning-from-weak-and-\strong-labelers.pdf.
Zinkevich, Martin. Online convex programming and generalized
infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp.
928–936, 2003.

On-Policy Imitation Learning from an Improving Supervisor

8. Appendix

We can rearrange the above to:

8.1. Proof of Theorem 12(∇θ li (πθi , ψN ))T (θi − θ? ) ≤We proceed similarly to Hazan et al. (2016). The parameter update
via online projected gradient descent is given by:kθi − θ? k2 − kθi+1 − θ? k2+ 4ηi G2 δ 2 +ηihiT
Es∈{Si } 4(∇θ πθi (s))T (ψN (s) − ψi (s)) (θ? − θi )kθi+1 − θ? k2 =kΠK (θi − ηi ∇θ li (πθi , ψi )) − θ? k2 ≤

(2)

? 2

kθi − ηi ∇θ li (πθi , ψi ) − θ kApplying Cauchy–Schwarz and subadditivity gives:

Expanding the above gives:h
iT
Es∈{Si } 4(∇θ πθi (s))T (ψN (s) − ψi (s)) (θ? − θi ) ≤? 2

kθi+1 − θ k ≤kθi − θ? k2 + ηi2 k∇θ li (πθi , ψi )k2 −(10)

Es∈{Si } 4k∇θ πθi (s))kkψN (s) − ψi (s)kkθ? − θi k
(11)

(3)

2ηi (∇θ li (πθi , ψi ))T (θi − θ? )where k∇θ πθi (s))k is the operator norm of ∇θ πθi (s).

Rearranging this gives:

Using Assumption 2 and Assumption 4, we have that2(∇θ li (πθi , ψi ))T (θi − θ? ) ≤kθi − θ? k2 − kθi+1 − θ? k2+ 4ηi G2 δ 2
ηi(4)

where k∇θ li (πθi , ψi )k ≤ 2Gδ by Assumption 4.
Given that the loss is of form:

Es∈{Si } 4k∇θ πθi (s)kkψN (s) − ψi (s)kkθ? − θi k ≤4DEs∈{Si } k∇θ πθi (s))kkψN (s) − ψi (s)k ≤4GDEs∈{Si } kψN (s) − ψi (s)kThus, we can rewrite equation 10 as follows:li (πθi , ψi ) = Es∈{Si } kπθi (s) − ψi (s)k2∇θ li (πθi , ψN )T (θi − θ? ) ≤we can relate the gradients of the loss with labels from the final
supervisor ψN and from the labeler at iteration i (ψi ) as follows:∇θ li (πθi , ψi ) =ihEs∈{Si } 2(∇θ πθi (s))T (πθi (s) − ψi (s))∇θ li (πθi , ψN ) =hi
Es∈{Si } 2(∇θ πθi (s))T (πθi (s) − ψN (s))

kθi − θ? k2 − kθi+1 − θ? k2+ 2ηi G2 δ 2
2ηi+ 2GDEs∈{Si } k(ψN (s) − ψi (s))k

(5)

(6)
∇θ li (πθi , ψN )T (θi − θ? ) −

(7)

(8)

Thus, by substituting the right-hand side of equation 8 into theleft-hand side of equation 4, we obtain:
2 ∇θ li (πθi , ψN )i Th+ Es∈{Si } 2(∇θ πθi (s))T (ψN (s) − ψi (s))(θi − θ? ) ≤? 2

αkθi − θ∗ k22 ≥2(14)

li (πθi , ψN ) − li (πθ? , ψN )Now using strong convexity and equation 13 gives:li (πθi , ψN ) − li (πθ? , ψN ) ≤so∇θ li (πθi , ψi ) = ∇θ li (πθi , ψN ) +hi
Es∈{Si } 2(∇θ πθi (s))T (ψN (s) − ψi (s))(13)

Now, we can use the strong convexity of the loss function (Assumption 1) to obtain the following bound for α > 0:

We can compute the difference of the loss gradients as follows:∇θ li (πθi , ψi ) − ∇θ li (πθi , ψN ) =hi
Es∈{Si } 2(∇θ πθi (s))T (ψN (s) − ψi (s))

(12)

? 2

kθi − θ k − kθi+1 − θ k+ 4ηi G2 δ 2ηikθi − θ? k2 − kθi+1 − θ? k2+ 2ηi G2 δ 2 +2ηiα2GDEs∈{Si } kψN (s) − ψi (s)k − kθi − θ∗ k22
2
Now, summing each side over the iterations gives:NX[li (πθi , ψN ) − li (πθ? , ψN )] ≤

i=1
N 
X
kθi − θ? k2 − kθi+1 − θ? k2
i=1

(9)

(15)

2ηi

(16)

+ 2ηi G2 δ 2+ 2GDEs∈{Si } kψN (s) − ψi (s)k −αkθi − θ∗ k222

On-Policy Imitation Learning from an Improving Supervisor
Now, we can explicitly represent this in terms of a telescoping sum
as follows:N Xkθi − θ? k2 − kθi+1 − θ? k2+ 2ηi G2 δ 2
2η
i
i=1

α
+ 2GDEs∈{Si } kψN (s) − ψi (s)k − kθi − θ∗ k22 ≤
2
(17)


N 
? 2
X
kθi − θ k1
1
2 2−
− α + 2ηi G δ
2
ηi
ηi−1
i=1

+ 2GDEs∈{Si } kψN (s) − ψi (s)k1
for i > 0 and η10 = 0, we see that
Using ηi = αiN Xkθi − θ? k2 1
2

i=1

ηi

−

1
ηi−1


−α

=0

Thus, we have:NX[li (πθi , ψN ) − li (πθ? , ψN )] ≤

i=1
2 2

2G δ

N
X

ηi + 2GD

i=1

N
X

(18)
Es∈{Si } kψN (s) − ψi (s)ki=1

so
RegretN =N
X[li (πθi , ψN ) − li (πθ? , ψN )] ≤i=1


2G2 δ 2 
1 + log N
αNX
Es∈{Si } kψN (s) − ψi (s)k
+ 2GD

(19)

i=1

8.2. Proof of Theorem 2
If
Es∈{Si } kψi (s) − ψN (s)k ≤ fi
w.p. 1 ∀N > i for some sequence (fi )N
i=1 where limi→∞ fi = 0,then this implies that
N
X

Es∈{Si } k(ψN (s) − ψi (s)k ≤

i=1

N
X

fi

i=1

The Additive Cesàro’s Theorem states that if the sequence (an )∞n
has a limit, thena1 + a2 . . . an
= limn→∞ annThus, we see thatPif limi→∞ fi = 0, then it must be the caseN
N
that limN →∞ N1
i=1 fi = 0. This shows that for any (fi )i=1
converging to 0, it must be the case thatlimn→∞N
X
i=1

Es∈{Si } kψN (s) − ψi (s)k ≤NX

fi = O(N )i=1Thus, based on the regret bound in Theorem 1, we can achieve
sublinear regret for any sequence (fi )N
i=1 which converges to 0.

8.3. PETS Details
PETS learns an ensemble of neural network dynamics models
using sampled transitions and updates them on-policy to betterreflect the dynamics local to the learned policy’s state distribution.
MPC is run over the learned dynamics to select actions for the
next iteration. For both the Reacher and Pusher environments, anensemble of 5 neural networks with 3 hidden layers, each with 500
hidden units are used to represent the dynamics model. We use an
MPC planning horizon of length 25 for both environments. Chuaet al. (2018) contains further details on training PETS.

8.4. Experimental Study of OGD on Cartpole with
iLQR Expert
Here, we study the performance of FIT on a Cartpole task withknown dynamics. We use a linear policy trained via ridgeregression with regularization parameter α = 1 to represent thelearner and an iLQR controller for the supervisor. Since the iLQR
controller has good global performance in this domain, we study
the effect of a specific supervisor convergence rate by explicitly
adding progressively smaller action bias to the iLQR controller tosimulate a supervisor improving at a specific rate. OGD is used forpolicy updates, so this experiment exactly satisfies the assumptionsof the theoretical analysis. For these experiments, we simulate aCsupervisor improvement rate corresponding to fi = √, whichi√gives expected regret on the order of O( N ).
We show the empirical regret with an improving iLQR controller
on Cartpole in Figure 3a. As expected, the regret shows a clear
sublinear pattern. Furthermore, to study the effect of poor quality
initial labels on learner performance, we show the average squared
difference between the learner and supervisor actions for a setof learners that are each initialized at progressively later OGD
iterations. The idea here is that learners which are initialized later
will have access to less data, but this data will be from a higher
quality supervisor. Thus, we expect to see a tradeoff between
data quality and quantity, where sufficient amounts of low quality
data may actually mislead the learner even if there is enoughtotal data, while a very small amount of high quality data may beinsufficient to successfully match supervisor performance. Results
are shown in Figure 3b. Learners that are initialized earlier takelonger to converge and still exhibit relatively noisy performance
while those initialized later on appear to converge relatively quickly
despite having fewer supervisor labels. It is possible that on amore difficult domain, fewer supervisor labels would have a more
adverse effect on learner performance. We hope to investigate
this tradeoff between data quality and quantity, specifically withregards to how a learner can best determine which supervisor labels
to use when the supervisor is time-varying, in future work.

On-Policy Imitation Learning from an Improving Supervisor
Cartpole Empirical Regret
Regret

1250
1000
750
500
0

20

40
60
Training Iterations

80

100

(a) Cartpole Empirical Regret
Effect of Delay on Policy Performance
0
20
40
60
80
90

0.175

Loss vs. Expert

0.150
0.125
0.100

Table 1. Learner, Supervisor, and PETS final training rewards: We report (learner final reward, supervisor final reward,
PETS final reward) for the Reacher and Pusher tasks after 100
training iterations with a linear policy and neural network policy.
Although there is no significant difference in the policy representations for Reacher, for Pusher the increased expressiveness ofthe neural network policy does improve the learner’s performance.
For both environments, the learner is able to achieve a final return
within 16 % of PETS, even with completely off-policy data.

0.075
0.050
0.025
0.000
0

20

40

Iteration

60

80

100

(b) Learner performancewith varying quality data
Figure 3. Performance of OGD on Cartpole with known dynamics: (a) Empirical Regret of OGD on Cartpole with known
dynamics and an iLQR teacher with action bias chosen to matchCsupervisor convergence rate given by fi = √. Here, we seeithat the regret shows a clear sublinear pattern as expected; (b)Average squared difference between actions chosen by the learnerand supervisor for a set of learners that are each initialized at
progressively later OGD iterations. As expected, learners thatare initialized earlier on take longer to converge and exhibit more
noisy performance due to the low quality initial supervisor labels,
while learners that are initialized later converge more quickly.

TASK

R EACHERP USHERL INEAR P OLICYN EURAL N ET P OLICY(-34.70, -45.20, -44.08)(-31.67, -49.21, -44.08)(-77.33, -98.63, -59.41)(-70.48, -61.72, -59.41)

8.5. FIT Experimental Results on Reacher/Pusher
The final return achieved by FIT, the supervisor, and PETS corresponding to Figures 1 and 2 is shown in Table 1. Since FITis
able to match the performance PETS relatively closely even whentrained with completely off-policy data, this indicates that there issignificant potential for accelerating learning and policy evaluation
without significantly affecting task performance.