Smooth Imitation Learning for Online Sequence Prediction

Hoang M. Le

HMLE

CALTECH

EDU

Andrew Kang

AKANG

CALTECH

EDU

Yisong Yue

YYUE

CALTECH

EDU

California Institute of Technology, Pasadena, CA, USA

Peter Carr

PETER

CARR

DISNEYRESEARCH

COM

Disney Research, Pittsburgh, PA, USA

Abstract

We study the problem of smooth imitation learn-

ing for online sequence prediction, where the

goal is to train a policy that can smoothly imitate

demonstrated behavior in a dynamic and con-

tinuous environment in response to online, se-

quential context input. Since the mapping from

context to behavior is often complex, we take

a learning reduction approach to reduce smooth

imitation learning to a regression problem us-

ing complex function classes that are regular-

ized to ensure smoothness. We present a learn-

ing meta-algorithm that achieves fast and stable

convergence to a good policy. Our approach en-

joys several attractive properties, including be-

ing fully deterministic, employing an adaptive

learning rate that can provably yield larger policy

improvements compared to previous approaches,

and the ability to ensure stable convergence. Our

empirical results demonstrate significant perfor-

mance gains over previous approaches.

1. Introduction

In many complex planning and control tasks, it can be very

challenging to explicitly specify a good policy. For such

tasks, the use of machine learning to automatically learn

a good policy from observed expert behavior, also known

as imitation learning or learning from demonstrations, has

proven tremendously useful (Abbeel & Ng, 2004; Ratliff

et al., 2009; Argall et al., 2009; Ross & Bagnell, 2010; Ross

et al., 2011; Jain et al., 2013).

In this paper, we study the problem of imitation learning for

smooth online sequence prediction in a continuous regime.

Proceedings of the

33

International Conference on Machine

Learning

, New York, NY, USA, 2016. JMLR: W&CP volume

Online sequence prediction is the problem of making on-

line decisions in response to exogenous input from the en-

vironment, and is a special case of reinforcement learning

(see Section 2). We are further interested in policies that

make smooth predictions in a continuous action space.

Our motivating example is the problem of learning smooth

policies for automated camera planning (Chen et al., 2016):

determining where a camera should look given environ-

ment information (e.g., noisy person detections) and cor-

responding demonstrations from a human expert.

It is

widely accepted that a smoothly moving camera is essen-

tial for generating aesthetic video (Gaddam et al., 2015).

From a problem formulation standpoint, one key difference

between smooth imitation learning and conventional imita-

tion learning is the use of a “smooth” policy class (which

we formalize in Section 2), and the goal now is to mimic

expert demonstrations by choosing the best smooth policy.

The conventional supervised learning approach to imitation

learning is to train a classifier or regressor to predict the ex-

pert’s behavior given training data comprising input/output

pairs of contexts and actions taken by the expert. How-

ever, the learned policy’s prediction affects (the distribu-

tion of) future states during the policy’s actual execution,

and so violates the crucial i.i.d. assumption made by most

statistical learning approaches. To address this issue, nu-

merous learning reduction approaches have been proposed

(Daum

e III et al., 2009; Ross & Bagnell, 2010; Ross et al.,

2011), which iteratively modify the training distribution in

various ways such that any supervised learning guarantees

provably lift to the sequential imitation setting (potentially

at the cost of statistical or computational efficiency).

We present a learning reduction approach to smooth im-

itation learning for online sequence prediction, which we

call SIMILE (

mooth

IMI

tation

arning).

Building

Access data at

http://www.disneyresearch.com/

publication/smooth-imitation-learning/

and

code at

http://github.com/hoangminhle/SIMILE

arXiv:1606.00968v1 [cs.LG] 3 Jun 2016

Smooth Imitation Learning for Online Sequence Prediction

upon learning reductions that employ policy aggregation

(Daum

e III et al., 2009), we provably lift supervised learn-

ing guarantees to the smooth imitation setting and show

much faster convergence behavior compared to previous

work. Our contributions can be summarized as:

•

We formalize the problem of smooth imitation learn-

ing for online sequence prediction, and introduce a

family of smooth policy classes that is amenable to

supervised learning reductions.

•

We present a principled learning reduction approach,

which we call SIMILE. Our approach enjoys sev-

eral attractive practical properties, including learning

a fully deterministic stationary policy (as opposed to

SEARN (Daum

e III et al., 2009)), and not requiring

data aggregation (as opposed to DAgger (Ross et al.,

2011)) which can lead to super-linear training time.

•

We provide performance guarantees that lift the

the underlying supervised learning guarantees to the

smooth imitation setting.

Our guarantees hold in

the agnostic setting, i.e., when the supervised learner

might not achieve perfect prediction.

•

We show how to exploit a stability property of our

smooth policy class to enable adaptive learning rates

that yield provably much faster convergence com-

pared to SEARN (Daum

e III et al., 2009).

•

We empirically evaluate using the setting of smooth

camera planning (Chen et al., 2016), and demonstrate

the performance gains of our approach.

2. Problem Formulation

Let

“ t

,...,x

u Ă

denote a context sequence

from the environment

, and

“ t

,...,a

u Ă

de-

note an action sequence from some action space

. Con-

text sequence is exogenous, meaning

does not influ-

ence future context

for

. Let

denote a

policy class, where each

generates an action se-

quence

in response to a context sequence

. Assume

are continuous and infinite, with

non-negative and bounded such that

~

~

Predicting actions

may depend on recent contexts

,...,x

and actions

,...,a

. Without loss of

generality, we define a state space

“ r

Policies

can thus be viewed as mapping states

“

to actions

. A roll-out of

given context sequence

“

,...,x

is the action sequence

“ t

,...,a

“

q “

“ r

s @

P r

,...,T

Note that unlike the general reinforcement learning prob-

lem, we consider the setting where the state space splits

into external and internal components (by definition,

in-

fluences subsequent states

, but not

). The use

We can always concatenate consecutive contexts and actions.

of exogenous contexts

models settings where a policy

needs to take online, sequential actions based on external

environmental inputs, e.g. smooth self-driving vehicles for

obstacle avoidance, helicopter aerobatics in the presence of

turbulence, or smart grid management for external energy

demand. The technical motivation of this dichotomy is that

we will enforce smoothness only on the internal state.

Consider the example of autonomous camera planning for

broadcasting a sport event (Chen et al., 2016).

can cor-

respond to game information such as the locations of the

players, the ball, etc., and

can correspond to the pan-

tilt-zoom configuration of the broadcast camera. Manually

specifying a good camera policy can be very challenging

due to sheer complexity involved with mapping

It is much more natural to train

to mimic observed

expert demonstrations. For instance,

can be the space of

neural networks or tree-based ensembles (or both).

Following the basic setup from (Ross et al., 2011), for any

policy

, let

denote the distribution of states at time

is executed for the first

time steps. Furthermore,

let

“

be the average distribution of states if

we follow

for all

steps. The goal of imitation learning

is to find a policy

which minimizes the imitation loss

under its own induced distribution of states:

“

argmin

q “

argmin

„

qqs

(1)

where the (convex) imitation loss

captures how

well

imitates expert demonstrations for state

. One com-

mon

is squared loss between the policy’s decision and the

expert demonstration:

qq “ }

q ́

for some

norm

}

. Note that computing

typically requires hav-

ing access to a training set of expert demonstrations

some set of context sequences. We also assume an agnos-

tic setting, where the minimizer of (1) does not necessarily

achieve 0 loss (i.e. it cannot perfectly imitate the expert).

2.1. Smooth Imitation Learning & Smooth Policy Class

In addition to accuracy, a key requirement of many con-

tinuous control and planning problems is smoothness (e.g.,

smooth camera trajectories). Generally, “smoothness” may

reflect domain knowledge about stability properties or ap-

proximate equilibria of a dynamical system. We thus for-

malize the problem of

smooth imitation learning

as mini-

mizing (1) over a smooth policy class

Most previous work on learning smooth policies focused on

simple policy classes such as linear models (Abbeel & Ng,

2004), which can be overly restrictive. We instead define a

much more general smooth policy class

as a regularized

space of complex models.

Definition 2.1

(Smooth policy class

)

Given a com-

plex model class

and a class of smooth regularizers

, we define smooth policy class

as satisfying:

Smooth Imitation Learning for Online Sequence Prediction

“ p

f,h

is close to

both

x,a

and

induced state

“ r

x,a

s P

where closeness is controlled by regularization.

For instance,

can be the space of neural networks or de-

cision trees and

be the space of smooth analytic func-

tions.

can thus be viewed as policies that predict close to

some

but are regularized to be close to some

For sufficiently expressive

, we often have that

Thus optimizing over

can be viewed as constrained op-

timization over

(by

), which can be challenging. Our

SIMILE approach integrates alternating optimization (be-

tween

and

) into the learning reduction. We provide

two concrete examples of

below.

Example 2.1

(

)

Let

be any complex supervised

model class, and define the simplest possible

q “

. Given

, the prediction of a policy

can be viewed

as regularized optimization over the action space to ensure

closeness of

to both

and

x,a

q “

argmin

1

›

x,a

q ́

›

q ́

›

“

x,a

λh

“

x,a

λa

(2)

where regularization parameter

trades-off closeness to

and to previous action. For large

x,a

is encouraged

make predictions that stays close to previous action

Example 2.2

(Linear auto-regressor smooth regularizers)

Let

be any complex supervised model class, and define

using linear auto-regressors,

q “

, which

model actions as a linear dynamical system (Wold, 1939).

We can define

analogously to (2).

In general, SIMILE requires that

satisfies a smooth prop-

erty stated below. This property, which is exploited in our

theoretical analysis (see Section 5), is motivated by the

observation that given a (near) constant stream of context

sequence, a stable behavior policy should exhibit a corre-

sponding action sequence with low curvature. The two ex-

amples above satisfy this property for sufficiently large

Definition 2.2

(

-state-smooth imitation policy)

For

small constant

, a policy

x,a

state-smooth if it is

-smooth w.r.t.

, i.e. for fixed

a,a

›

∇

x,a

sq ́

∇

x,a

›

}

where

indicates the

component of

vector-valued function

q “

“

,...,π

‰

and

}

and

}

are some norm and dual norm respectively.

For twice differentiable policy

, this is equivalent to hav-

ing the bound on the Hessian

∇

x,a

This emphasizes the possibility that

is a vector-valued func-

tion of

. The gradient and Hessian are viewed as arrays of

gra-

dient vectors and Hessian matrices of 1-d case, since we simply

treat action in

as an array of

standard functions.

3. Related Work

The most popular traditional approaches for learning from

expert demonstration focused on using approximate policy

iteration techniques in the MDP setting (Kakade & Lang-

ford, 2002; Bagnell et al., 2003). Most prior approaches

operate in discrete and finite action space (He et al., 2012;

Ratliff et al., 2009; Abbeel & Ng, 2004; Argall et al.,

2009). Some focus on continuous state space (Abbeel &

Ng, 2005), but requires a linear model for the system dy-

namics. In contrast, we focus on learning complex smooth

functions within continuous action and state spaces.

One natural approach to tackle the more general setting

is to reduce imitation learning to a standard supervised

learning problem (Syed & Schapire, 2010; Langford &

Zadrozny, 2005; Lagoudakis & Parr, 2003). However, stan-

dard supervised methods assume i.i.d. training and test ex-

amples, thus ignoring the distribution mismatch between

training and rolled-out trajectories directly applied to se-

quential learning problems (Kakade & Langford, 2002).

Thus a naive supervised learning approach normally leads

to unsatisfactory results (Ross & Bagnell, 2010).

Iterative Learning Reductions.

State-of-the-art learning

reductions for imitation learning typically take an iterative

approach, where each training round uses standard super-

vised learning to learn a policy (Daum

e III et al., 2009;

Ross et al., 2011). In each round

, the following happens:

•

Given initial state

drawn from the starting distribu-

tion of states, the learner executes current policy

resulting in a sequence of states

,...,s

•

For each

, a label

(e.g., expert feedback) is col-

lected indicating what the expert would do given

resulting in a new dataset

“ tp

•

The learner integrates

to learn a policy

. The

learner updates the current policy to

based on

and

The main challenge is controlling for the cascading errors

caused by the changing dynamics of the system, i.e., the

distribution of states in each

„

. A policy trained

using

induces a different distribution of states than

and so is no longer being evaluated on the same distribution

as during training. A principled reduction should (approx-

imately) preserve the i.i.d. relationship between training

and test examples. Furthermore the state distribution

should converge to a stationary distribution.

The arguably most notable learning reduction approaches

for imitation learning are SEARN (Daum

e III et al., 2009)

and DAgger (Ross et al., 2011). At each round, SEARN

learns a new policy

and returns a distribution (or mix-

ture) over previously learned policies:

“

for

P p

. For appropriately small choices of

, this stochastic mixing limits the “distribution drift” be-

tween

and

and can provably guarantee that the

Smooth Imitation Learning for Online Sequence Prediction

performance of

does not degrage significantly rela-

tive to the expert demonstrations.

DAgger, on the other hand, achieves stability by aggre-

gating a new dataset at each round to learn a new policy

from the combined data set

. This aggre-

gation, however, significantly increases the computational

complexity and thus is not practical for large problems that

require many iterations of learning (since the training time

grows super-linearly w.r.t. the number of iterations).

Both SEARN and DAgger showed that only a polynomial

number of training rounds is required for convergence to a

good policy, but with a dependence on the length of hori-

zon

. In particular, to non-trivially bound the total vari-

ation distance

}

new

old

}

of the state distributions

between old and new policies, a learning rate

required to hold (Lemma 1 of Daum

e III, Langford, and

Marcu (2009) and Theorem 4.1 of Ross, Gordon, and Bag-

nell (2011)). As such, systems with very large time hori-

zons might suffer from very slow convergence.

Our Contributions.

Within the context of previous work,

our SIMILE approach can be viewed as extending SEARN

to smooth policy classes with the following improvements:

•

We provide a policy improvement bound that does not

depend on the time horizon

, and can thus converge

much faster. In addition, SIMILE has adaptive learn-

ing rate, which can further improve convergence.

•

For the smooth policy class described in Section 2, we

show how to generate simulated or “virtual” expert

feedback in order to guarantee stable learning. This

alleviates the need to have continuous access to a dy-

namic oracle / expert that shows the learner what to do

when it is off-track. In this regard, the way SIMILE

integrates expert feedback subsumes the set-up from

SEARN and DAgger.

•

Unlike SEARN, SIMILE returns fully deterministic

policies. Under the continuous setting, deterministic

policies are strictly better than stochastic policies as

(i) smoothness is critical and (ii) policy sampling re-

quires holding more data during training, which may

not be practical for infinite state and action spaces.

•

Our theoretical analysis reveals a new sequential pre-

diction setting that yields provably fast convergence,

in particular for smooth policy classes on finite-

horizon problems. Existing settings that enjoy such

results are limited to Markovian dynamics with dis-

counted future rewards or linear model classes.

4. Smooth Imitation Learning Algorithm

Our learning algorithm, called SIMILE (

mooth

IMI

tation

arning), is described in Algorithm 1. At a high level, the

process can be described as:

A similar approach was adopted in Conservative Policy Iter-

ation for the MDP setting (Kakade & Langford, 2002).

Algorithm 1

SIMILE (

mooth

IMI

tation

arning)

Input:

features

“ t

, human trajectory

“ t

base routine

Train

, smooth regularizers

Initialize

Ð t

“

‰

“

argmin

“

›

Initial policy

“

Train

for

“

,...,N

“ t

u Ð

sequential roll-out

Ð t

“

‰

“ r

“ t

u @

collect smooth feedback

“

argmin

“

›

new regularizer

Train

train policy

adaptively set

10:

“

update policy

11:

end for

output

Last policy

1. Start with some initial policy

(Line 2).

2. At iteration

, use

to build a new state distribu-

tion

and dataset

“ tp

(Lines 4-6).

3. Train

“

argmin

„

qqs

, where

is the imitation loss (Lines 7-8). Note that

needs

not be the original

, but simply needs to converge to

it.

4. Interpolate

and

to generate a new determin-

istic policy

(Lines 9-10). Repeat from Step 2 with

until some termination condition is met.

Supervised Learning Reduction.

The actual reduction is

in Lines 7-8, where we follow a two-step procedure of first

updating the smooth regularize

, and then training

via

supervised learning. In other words,

Train

finds the best

possible for a fixed

. We discuss how to set the

training targets

below.

Policy Update.

The new policy

is a deterministic inter-

polation between the previous

and the newly learned

(Line 10). In contrast, for SEARN,

is a stochastic in-

terploation (Daum

e III et al., 2009). Lemma 5.2 and Corol-

lary 5.3 show that deterministic interpolation converges at

least as fast as stochastic for smooth policy classes.

This interpolation step plays two key roles. First, it is

a form of myopic or greedy online learning. Intuitively,

rolling out

leads to incidental exploration on the mis-

takes of

, and so each round of training is focused on

refining

. Second, the interpolation in Line 10 ensures

a slow drift in the distribution of states from round to

round, which preserves an approximate i.i.d. property for

the supervised regression subroutine and guarantees con-

vergence.

However this model interpolation creates an inherent ten-

sion between maintaining approximate i.i.d. for valid su-

Smooth Imitation Learning for Online Sequence Prediction

pervised learning and more aggressive exploration (and

thus faster convergence). For example, SEARN’s guaran-

tees only apply for small

{

. SIMILE circumvents

much of this tension via a policy improvement bound that

allows

to adaptively increase depending on the quality of

(see Theorem 5.6), which thus guarantees a valid learn-

ing reduction while substantially speeding up convergence.

Feedback Generation.

We can generate training targets

using “virtual” feedback from simulating expert demon-

strations, which has two benefits. First, we need not query

the expert

at every iteration (as done in DAgger (Ross

et al., 2011)). Continuously acquiring expert demonstra-

tions at every round can be seen as a special case and a

more expensive strategy. Second, virtual feedback ensures

stable learning, i.e., every

is a feasible smooth policy.

000

001

002

003

004

005

006

007

008

009

010

011

012

013

014

015

016

017

018

019

020

021

022

023

024

025

026

027

028

029

030

031

032

033

034

035

036

037

038

039

040

041

042

043

044

045

046

047

048

049

050

051

052

053

054

055

056

057

058

059

060

061

062

063

064

065

066

067

068

069

070

071

072

073

074

075

076

077

078

079

080

081

082

083

084

085

086

087

088

089

090

091

092

093

094

095

096

097

098

099

100

101

102

103

104

105

106

107

CVPR

#307

CVPR

#307

CVPR 2015 Submission #307. CONFIDENTIAL REVIEW COPY. DO NOT DISTRIBUTE.

Learning Online Smooth Predictors for Realtime Camera Planning

Anonymous CVPR submission

Paper ID 307

Abstract

Data-driven prediction methods are extremely useful in

many computer vision applications. However, the estima-

tors are normally learned within a time independent con-

text. When used for online prediction, the results are jittery.

Although smoothing can be added after the fact (such as

a Kalman filter), the approach is not ideal. Instead, tem-

poral smoothness should be incorporated into the learning

process. In this paper, we show how the ‘search and learn’

algorithm (which has been used previously for tagging parts

of speech) can be adapted to efficiently learn regressors for

temporal signals. We apply our data-driven learning tech-

nique to a camera planning problem: given noisy basketball

player detection data, we learn where the camera should

look based on examples from a human operator. Our exper-

imental results show how a learning algorithm which takes

into account temporal consistency of sequential predictions

has significantly better performance than time independent

estimators.

1. Introduction

In this work, we investigate the problem of determining

where a camera should look when broadcasting a basketball

game (see Fig.

). Realtime camera planning shares many

similarities with online object tracking: in both cases, the

algorithms must constantly revise an estimated target posi-

tion as new evidence is acquired. Noise and other ambi-

guities cause non-ideal jittery trajectories: they are are not

good representations of how objects actually move, and in

camera planning, lead to unaesthetic results. In practice,

temporal regularization is employed to minimize jitter. The

amount of regularization is a design parameter, and controls

a trade-off between precision and smoothness. In contrast to

object tracking, smoothness is of paramount importance in

camera control: fluid movements which maintain adequate

framing are preferable to erratic motions which pursue per-

fect composition.

Model-free estimation methods, such as random forests,

are very popular because they can be learned directly from

Figure 1:

Camera Planning

The objective is to predict

an appropriate pan angle for a broadcast camera based

on noisy player detection data. Consider two planning al-

gorithms (shown as blue and red curves in the schematic)

which both make the same mistake at time

but recover to a

good framing by

(the ideal camera trajectory is shown in

black). The blue solution quickly corrects by time

using

a jerky motion, whereas the red curve conducts a gradual

correction. Although the red curve has a larger discrepancy

with the ideal motion curve, its velocity characteristics are

most similar to the ideal motion path.

data. Often, the estimator is learned within a time indepen-

dent paradigm, and temporal regularization is integrated as

a post-processing stage (such as a Kalman filter). However,

this two stage approach is not ideal because the data-driven

estimator is prevented from learning any temporal patterns.

In this paper, we condition the data-driven estimator on pre-

vious predictions, which allows it to learn temporal patterns

within the data (in addition to any direct feature-based re-

lationships). However, this recursive formulation (similar

to reinforcement learning) makes the problem much more

difficult to solve. We employ a variant of the ‘search and

learn’ (SEARN) algorithm to keep training efficient. Its

strategy is to decouple the recursive relationships using an

auxiliary reference signal. This allows the predictor to be

learned efficiently using supervised techniques, and our ex-

periments demonstrate significant improvements when us-

ing this holistic approach.

Problem Definition

In the case of camera planning, we

assume there is an underlying function

:

7!

which

describes the ideal camera work that should occur at the

Figure 1.

Consider Figure 1, where our pol-

icy

(blue/red) made a mistake

at location A, and where we have

only a single expert demonstra-

tion from

(black). Depending

on the smoothness requirements of

the policy class, we can simulate

virtual expert feedback as via ei-

ther the red line (more smooth) or blue (less smooth) as

a tradeoff between squared imitation loss and smoothness.

When the roll-out of

(i.e.

) differs substantially

from

, especially during early iterations, using smoother

feedback (red instead of blue) can result in more stable

learning. We formalize this notion for

in Proposi-

tion 5.8. Intuitively, whenever

makes a mistake, re-

sulting in a “bad” state

, the feedback should recom-

mend a smooth correction

w.r.t.

to make training

“easier” for the learner.

The virtual feedback

should

converge to the expert’s action

. In practice, we use

“

σa

with

increases (which

satisfies Proposition 5.8).

5. Theoretical Results

All proofs are deferred to the supplementary material.

5.1. Stability Conditions

One natural smoothness condition is that

x,a

should

be stable w.r.t.

is fixed. Consider the camera planning

setting: the expert policy

should have very small curva-

ture, since constant inputs should correspond to constant

actions. This motivates Definition

, which requires that

has low curvature given fixed context. We also show that

smooth policies per Definition 2.2 lead to stable actions,

in the sense that “nearby” states are mapped to “nearby”

actions. The following helper lemma is useful:

A similar idea was proposed (He et al., 2012) for DAgger-

type algorithm, albeit only for linear model classes.

Lemma 5.1.

For a fixed

, define

x,a

. If

non-negative and

-smooth w.r.t.

., then:

a,a

q ́

›

Writing

x,a

“

x,a

,...,π

x,a

‰

with each

x,a

-smooth, Lemma 5.1 implies

x,a

sq ́

x,a

sqq} ď

}

for

up-

per bounding

. Bounded action space means that a suffi-

ciently small

leads to the following stability conditions:

Condition 1

(Stability Condition 1)

satisfies the Sta-

bility Condition 1 if for a fixed input feature

, the ac-

tions of

in states

“ r

x,a

and

“ r

x,a

satisfy

}

q ́

q} ď }

}

for all

a,a

Condition 2

(Stability Condition 2)

satisfies Stability

Condition 2 if each

-Lipschitz continuous in the ac-

tion component

with

. That is, for a fixed

the

actions of

in states

“ r

x,a

and

“ r

x,a

satisfy

}

q ́

q} ď

}

for all

a,a

These two conditions directly follow from Lemma 5.1 and

assuming sufficiently small

Condition 2 is mildly

stronger than Condition 1, and enables proving much

stronger policy improvement compared to previous work.

5.2. Deterministic versus Stochastic

Given two policies

and

, and interpolation parameter

P p

, consider two ways to combine policies:

stochastic

sto

q “

with probability

, and

sto

q “

with probability

deterministic

det

q “

q`p

Previous learning reduction approaches only use stochastic

interpolation (Daum

e III et al., 2009; Ross et al., 2011),

whereas SIMILE uses deterministic. The following result

shows that deterministic and stochastic interpolation yield

the same expected behavior for smooth policy classes.

Lemma 5.2.

Given any starting state

, sequentially ex-

ecute

det

and

sto

to obtain two separate trajectories

“ t

“

and

“ t

“

such that

“

det

and

“

sto

, where

“ r

and

“ r

Assuming the policies are stable as per Condition 1, we

have

s “

“

,...,T

, where the expectation is

taken over all random roll-outs of

sto

Lemma 5.2 shows that deterministic policy combination

(SIMILE) yields unbiased trajectory roll-outs of stochas-

tic policy combination (as done in SEARN & CPI). This

represents a major advantage of SIMILE, since the num-

ber of stochastic roll-outs of

sto

to average to the deter-

ministic trajectory of

det

is polynomial in the time hori-

zon

, leading to much higher computational complexity.

Furthermore, for convex imitation loss

, Lemma 5.2

and Jensen’s inequality yield the following corollary, which

states that under convex loss, deterministic policy performs

at least no worse than stochastic policy in expectation:

Smooth Imitation Learning for Online Sequence Prediction

Corollary 5.3

(Deterministic Policies Perform Better)

For

deterministic

det

and stochastic

sto

interpolations of two

policies

and

, and convex loss

, we have:

det

q “

sto

where the expectation is over all roll-outs of

sto

Remark.

We construct a simple example to show that Con-

dition 1 may be necessary for iterative learning reductions

to converge. Consider the case where contexts

are either constant or vary neglibly. Expert demonstrations

should be constant

sq “

for all

. Consider

an unstable policy

such that

q “

x,a

sq “

for fixed

. The rolled-out trajectory of

diverges

at an exponential rate. Assume optimistically that

learns the correct expert behavior, which is simply

q “

x,a

sq “

. For any

P p

, the updated policy

“

becomes

x,a

sq “

βa

Thus the sequential roll-out of the new policy

will also

yield an exponential gap from the correct policy. By induc-

tion, the same will be true in all future iterations.

5.3. Policy Improvement

Our policy improvement guarantee builds upon the analysis

from SEARN (Daum

e III et al., 2009), which we extend to

using adaptive learning rates

. We first restate the main

policy improvement result from Daum

e III et al. (2009).

Lemma 5.4

(SEARN’s policy nondegradation - Lemma 1

from Daum

e III et al. (2009))

Let

max

“

sup

π,s

is defined as

sto

in lemma 5.2. Then for

P p

{

1

q ́

q ď

βT

„

qqs`

max

SEARN guarantees that the new policy

does not degrade

from the expert

by much only if

{

. Analy-

ses of SEARN and other previous iterative reduction meth-

ods (Ross et al., 2011; Kakade & Langford, 2002; Bagnell

et al., 2003; Syed & Schapire, 2010) rely on bounding the

variation distance between

and

1

. Three drawbacks of

this approach are: (i) non-trivial variation distance bound

typically requires

to be inversely proportional to time

horizon

, causing slow convergence; (ii) not easily appli-

cable to the continuous regime; and (iii) except under MDP

framework with discounted infinite horizon, previous vari-

ation distance bounds do not guarantee monotonic policy

improvements (i.e.

1

q ă

We provide two levels of guarantees taking advantage of

Stability Conditions 1 and 2 to circumvent these draw-

backs. Assuming the Condition 1 and convexity of

, our

first result yields a guarantee comparable with SEARN.

Theorem 5.5

(T-dependent Improvement)

Assume

convex and

-Lipschitz, and Condition 1 holds. Let

“

max

„

}

q ́

. Then:

1

q ́

q ď

βLT

q ́

(3)

In particular, choosing

P p

{

yields:

1

q ́

q ď

q ́

(4)

Similar to SEARN, Theorem 5.5 also requires

P p

{

to ensure the RHS of (4) stays small. However, note that the

reduction term

q ́

allows the bound to be

strictly negative if the policy

trained on

significantly

improves on

(i.e., guaranteed policy improvement).

We observe empirically that this often happens, especially

in early iterations of training.

Under the mildly stronger Condition 2, we remove the de-

pendency on the time horizon

, which represents a much

stronger guarantee compared to previous work.

Theorem 5.6

(Policy Improvement)

Assume

is convex

and

-Lipschitz-continuous, and Condition 2 holds. Let

“

max

„

}

q ́

. Then for

P p

1

q ́

q ď

βγL

q ́

(5)

Corollary 5.7

(Monotonic Improvement)

Following the

notation from Theorem 5.6, let

∆

“

q ́

and

“

γL

. Then choosing step size

“

∆

2∆

, we have:

1

q ́

q ď ́

∆

(6)

The terms

and

q ́

on the RHS of (4) and (5)

come from the learning reduction, as they measure the “dis-

tance” between

and

on the state distribution induced

(which forms the dataset to train

). In practice, both

terms can be empirically estimated from the training round,

thus allowing an estimate of

to minimize the bound.

Theorem 5.6 justifies using an adaptive and more aggres-

sive interpolation parameter

to update policies. In the

worst case, setting

close to

will ensure the bound from

(5) to be close to

, which is consistent with SEARN’s

result. More generally, monotonic policy improvement

can be guaranteed for appropriate choice of

, as seen

from Corollary 5.7. This strict policy improvement was

not possible under previous iterative learning reduction ap-

proaches such as SEARN and DAgger, and is enabled in

our setting due to exploiting the smoothness conditions.

5.4. Smooth Feedback Analysis

Smooth Feedback Does Not Hurt:

Recall from Section

4 that one way to simulate “virtual” feedback for training

a new

is to set the target

“

σa

` p

for

P p

, where smooth feedback corresponds to

To see that simulating smooth “virtual” feedback target

does not hurt the training progress, we alternatively view

SIMILE as performing gradient descent in a smooth func-

tion space (Mason et al., 1999). Define the cost functional

: Π

over policy space to be the average imitation

loss over

q “

}

q ́

. The gra-

Smooth Imitation Learning for Online Sequence Prediction

dient (G

ateaux derivative) of

w.r.t.

is:

∇

q “

αδ

“

q ́

where

is Dirac delta function centered at s. By first order

approximation

q “

qq «

∇

. Like traditional gradient

descent, we want to choose

such that the update moves

the functional along the direction of negative gradient. In

other words, we want to learn

such that

∇

y !

. We can evaluate this inner product along the states

induced by

. We thus have the estimate:

∇

y «

“

q ́

qqp

q ́

“

sq ́

Since we want

∇

y ă

, this motivates the

construction of new data set

with states

“

and labels

“

to train a new policy

, where we want

q ă

. A sufficient solution is to set target

“

σa

` p

(Section 4), as this will point the

gradient in negative direction, allowing the learner to make

progress.

Smooth Feedback is Sometimes Necessary:

When the

current policy performs poorly, smooth virtual feedback

may be required to ensure stable learning, i.e. producing

a feasible smooth policy at each training round. We for-

malize this notion of feasibility by considering the smooth

policy class

in Example 2.1. Recall that smooth reg-

ularization of

via

encourages the next action to be

close to the previous action. Thus a natural way to mea-

sure smoothness of

is via the average first order

difference of consecutive actions

“

}

. In

particular, we want to explicitly constrain this difference

relative to the expert trajectory

“

}

} ď

each iteration, where

“

›

When

performs poorly, i.e. the ”average gap” between

current trajectory

and

is large, the training target

for

should be lowered to ensure learning a smooth policy

is feasible, as inferred from the following proposition. In

practice, we typically employ smooth virtual feedback in

early iterations when policies tend to perform worse.

Proposition 5.8.

Let

be the average supervised train-

ing error from

, i.e.

“

min

„

sq ́

Let the rolled-out trajectory of current policy

If the average gap between

and

is such that

„

Uniform

}s ě

, then us-

ing

as feedback will cause the trained policy

to be

non-smooth, i.e.:

„

Uniform

}s ě

η,

(7)

for

the rolled-out trajectory of

Figure 2.

Expert (blue) and predicted (red) camera pan angles.

Left: SIMILE with

10 iterations. Right: non-smooth policy.

Figure 3.

Adaptive versus fixed interpolation parameter

6. Experiments

Automated Camera Planning.

We evaluate SIMILE in a

case study of automated camera planning for sport broad-

casting (Chen & Carr, 2015; Chen et al., 2016). Given

noisy tracking of players as raw input data

“

, and

demonstrated pan camera angles from professional human

operator as

“

, the goal is to learn a policy

that pro-

duces trajectory

“

that is both smooth and accurate

relative to

“

. Smoothness is critical in camera con-

trol: fluid movements which maintain adequate framing are

preferable to jittery motions which constantly pursue per-

fect tracking (Gaddam et al., 2015). In this setting, time

horizon

is the duration of the event multiplied by rate of

sampling. Thus

tends to be very large.

Smooth Policy Class.

We use a smooth policy class fol-

lowing Example 2.2: regression tree ensembles

regular-

ized by a class of linear autoregressor functions

(Chen

et al., 2016). See Appendix B for more details.

Summary of Results.

•

Using our smooth policy class leads to dramatically

smoother trajectories than not regularizing using

•

Using our adaptive learning rate leads to much faster

convergence compared to conservative learning rates

from SEARN (Daum

e III et al., 2009).

•

Using smooth feedback ensures stable learning of

smooth policies at each iteration.

•

Deterministic policy interpolation performs better

than stochastic interpolation used in SEARN.

Smooth versus Non-Smooth Policy Classes.

Figure 2

shows a comparison of using a smooth policy class ver-

sus a non-smooth one (e.g., not using

). We see that our

Smooth Imitation Learning for Online Sequence Prediction

Figure 4.

Comparing different values of

approach can reliably learn to predict trajectories that are

both smooth and accurate.

Adaptive vs. Fixed

One can, in principle, train using

SEARN, which requires a very conservative

in order to

guarantee convergence. In contrast, SIMILE adaptively se-

lects

based on relative empirical loss of

and

(Line 9

of Algorithm 1). Let

error

and

error

denote the

mean-squared errors of rolled-out trajectories

respectively, w.r.t. ground truth

. We can set

as:

“

error

error

error

(8)

which encourages the learner to disregard bad policies

when interpolating, thus allowing fast convergence to a

good policy (see Theorem 5.6). Figure 3 compares the

convergence rate of SIMILE using adaptive

versus con-

servative fixed values of

commonly used in SEARN

(Daum

e III et al., 2009). We see that adaptively choosing

enjoys substantially faster convergence. Note that very

large fixed

may overshoot and worsen the combined pol-

icy after a few initial improvements.

Smooth Feedback Generation:

We set the target labels

“

σa

` p

for

(Line 6 of

Algorithm 1). Larger

corresponds to smoother (

closer to

) but less accurate target (further from

as seen in Figure 4. Figure 5 shows the trade-off between

Figure 5.

smoothness loss (blue

line, measured by first

order

difference

Proposition 5.8) and

imitation loss (red line,

measured

mean

squared distance) for

varying

. We navigate

this trade-off by setting

closer to 1 in early iterations, and have

increases. This “gradual increase” produces more stable

policies, especially during early iterations where the

learning policy tends to perform poorly (as formalized

in Proposition 5.8). In Figure 4, when the initial policy

(green trajectory) has poor performance, setting smooth

Figure 6.

Performance after different number of iterations.

targets (Figure 4b) allows learning a smooth policy in

the subsequent round, in contrast to more accurate but

less stable performance of “difficult” targets with low

(Figure 4c-d). Figure 6 visualizes the behavior of the the

intermediate policies learned by SIMILE, where we can

see that each intermediate policy is a smooth policy.

Deterministic vs. Stochastic Interpolation:

Finally, we

evaluate the benefits of using deterministic policy averag-

ing intead of stochastically combine different policies, as

done in SEARN. To control for other factors, we set

a fixed value of

, and keep the new training dataset

the same for each iteration

. The average imitation loss of

stochastic policy sampling are evaluated after 50 stochastic

roll-outs at each iterations. This average stochastic policy

error tends to be higher compared to the empirical error

of the deterministic trajectory, as seen from Figure 7, and

confirms our finding from Corollary 5.3.

Figure 7.

Deterministic policy error vs. average stochastic policy

error for

“

0

5

and 50 roll-outs of the stochastic policies.

7. Conclusion

We formalized the problem of smooth imitation learning

for online sequence prediction, which is a variant of imita-

tion learning that uses a notion of a smooth policy class. We

proposed SIMILE (

mooth

IMI

tation

arning), which is

an iterative learning reduction approach to learning smooth

policies from expert demonstrations in a continuous and

dynamic environment. SIMILE utilizes an adaptive learn-

ing rate that provably allows much faster convergence com-

pared to previous learning reduction approaches, and also

enjoys better sample complexity than previous work by be-

ing fully deterministic and allowing for virtual simulation

of training labels. We validated the efficiency and practical-

ity of our approach on a setting of online camera planning.

Smooth Imitation Learning for Online Sequence Prediction

References

Abbeel, Pieter and Ng, Andrew Y. Apprenticeship learn-

ing via inverse reinforcement learning. In

International

Conference on Machine Learning (ICML)

, 2004.

Abbeel, Pieter and Ng, Andrew Y. Exploration and appren-

ticeship learning in reinforcement learning. In

Interna-

tional Conference on Machine Learning (ICML)

, 2005.

Argall, Brenna D, Chernova, Sonia, Veloso, Manuela, and

Browning, Brett.

A survey of robot learning from

demonstration.

Robotics and autonomous systems

, 57

(5):469–483, 2009.

Bagnell, J Andrew, Kakade, Sham M, Schneider, Jeff G,

and Ng, Andrew Y. Policy search by dynamic program-

ming. In

Neural Information Processing Systems (NIPS)

2003.

Caruana, Rich and Niculescu-Mizil, Alexandru. An em-

pirical comparison of supervised learning algorithms. In

International Conference on Machine Learning (ICML)

2006.

Chen, Jianhui and Carr, Peter. Mimicking human camera

operators. In

IEEE Winter Conference Applications of

Computer Vision (WACV)

, 2015.

Chen, Jianhui, Le, Hoang M., Carr, Peter, Yue, Yisong,

and Little, James J. Learning online smooth predictors

for real-time camera planning using recurrent decision

trees. In

IEEE Conference on Computer Vision and Pat-

tern Recognition (CVPR)

, 2016.

Criminisi, Antonio, Shotton, Jamie, and Konukoglu, En-

der. Decision forests: A unified framework for classifi-

cation, regression, density estimation, manifold learning

and semi-supervised learning.

Foundations and Trends

in Computer Graphics and Vision

, 7(2–3):81–227, 2012.

Daum

e III, Hal, Langford, John, and Marcu, Daniel.

Search-based structured prediction.

Machine learning

75(3):297–325, 2009.

Gaddam, Vamsidhar Reddy, Eg, Ragnhild, Langseth, Rag-

nar, Griwodz, Carsten, and Halvorsen, P

al. The camera-

man operating my virtual camera is artificial: Can the

machine be as good as a human&quest.

ACM Transac-

tions on Multimedia Computing, Communications, and

Applications (TOMM)

, 11(4):56, 2015.

He, He, Eisner, Jason, and Daume, Hal. Imitation learning

by coaching. In

Neural Information Processing Systems

(NIPS)

, 2012.

Jain, Ashesh, Wojcik, Brian, Joachims, Thorsten, and Sax-

ena, Ashutosh. Learning trajectory preferences for ma-

nipulators via iterative improvement. In

Neural Informa-

tion Processing Systems (NIPS)

, 2013.

Kakade, Sham and Langford, John. Approximately op-

timal approximate reinforcement learning. In

Interna-

tional Conference on Machine Learning (ICML)

, 2002.

Lagoudakis, Michail and Parr, Ronald.

Reinforcement

learning as classification: Leveraging modern classi-

fiers. In

International Conference on Machine Learning

(ICML)

, 2003.

Langford, John and Zadrozny, Bianca.

Relating rein-

forcement learning performance to classification perfor-

mance. In

International Conference on Machine Learn-

ing (ICML)

, 2005.

Mason, Llew, Baxter, Jonathan, Bartlett, Peter L, and

Frean, Marcus. Functional gradient techniques for com-

bining hypotheses. In

Neural Information Processing

Systems (NIPS)

, 1999.

Ratliff, Nathan, Silver, David, and Bagnell, J. Andrew.

Learning to search: Functional gradient techniques for

imitation learning.

Autonomous Robots

, 27(1):25–53,

2009.

Ross, St

ephane and Bagnell, Drew. Efficient reductions for

imitation learning. In

Conference on Artificial Intelli-

gence and Statistics (AISTATS)

, 2010.

Ross, Stephane, Gordon, Geoff, and Bagnell, J. Andrew. A

reduction of imitation learning and structured prediction

to no-regret online learning. In

Conference on Artificial

Intelligence and Statistics (AISTATS)

, 2011.

Srebro, Nathan, Sridharan, Karthik, and Tewari, Ambuj.

Smoothness, low noise and fast rates. In

Neural Infor-

mation Processing Systems (NIPS)

, 2010.

Syed, Umar and Schapire, Robert E. A reduction from ap-

prenticeship learning to classification. In

Neural Infor-

mation Processing Systems (NIPS)

, 2010.

Wold, Herman. A study in the analysis of stationary time

series, 1939.