1. Policy Evaluation(Online Bellman Residual)[Sun & Bagnell, 15, UAI (Best Student Paper)]Function Approximation

2. RL via Imitation(Imitation Learning)[Sun et.al 17, ICML; 18, ICLR]

Function Approximation &Imitation

RL

3. RL via Indirect
Imitation(Dual Policy Iteration)[Sun et.al, 18, submitted to ICML]

Function Approximation
Optimal Control

4. Proposed Work:
Temporal Diﬀerence Learning &Apprenticeship Learning
20

Imitation Learning
MachineLearning
Algorithm

Expert Feedback•••••••

SVM
Gaussian Process
Kernel Estimator
Deep NetworksRandom Forests
LWR…

PolicyMaps statesto actions

21

Eﬃcient RL via Imitation
Human

Extra Assumptions:e⇡expert
policyattraining;
Planner & Controller
cost(reward)signal(e.g., Optimal Planner, MPC )(robotics)[Choudhury, et.al, ICRA, RSS, 17, Pan et.al,17]

Ground Truth
Labels + Utility(NLP)

Search Algorithm(e.g. A*) as expert
22

Why bother imitating when
you have cost/reward signals?

23

Formalizing Advantages
ADVANTAGE #1
Less sensitive to local optimality
DAgger (Data Aggregation) [Ross et.al, 11, AISTATS]
AggreVaTe (Aggregate with Values) [Ross&Bagnell14, arxiv]

ADVANTAGE #2
More Sample Eﬃcient (i.e., Learns faster)
There exist problems, s.t. with access to optimal expert, i.e., ⇡ e = ⇡ ⇤IL learns exponentially faster than RL[Sun et.al, 17,ICML]
24

Consider a simple, tree like MDP⇤e⇤let us assume ⇡ = ⇡ , and we can query Q (s, a)

s0 Go-Right

Go-Left
Optimal Paths1

s3
c3

s2
s4<c4s5<c5s6<c6Q⇡ (s, a) : the total cost of taking action a at s then following policy ⇡25And an expert who tells us which action is better⇤e⇤

let us assume ⇡ = ⇡ , and we can query Q (s, a)

s0
s1
s3
c3

s2
s4

<c4s5
<c5s6
<c6

Halving: Eliminate half of the nodes at every iteration
26

In time logarithmic in #states,
we know an optimal policy

s0
s1
s3
c3
N
X
i=1

s2
s4

<(J(⇡i )c4s5<⇤c5s6<c6J(⇡ ))  O(log(S))
27[Sun et.al, 17,ICML]In time logarithmic in #states,
we know an optimal policy[Sun et.al, 17,ICML]

Now if we can only query unbiased but noisys0s1s3c3N
Xi=1(J(⇡i )s2s4<c4s5<⇤J(⇡ ))  O ln(S)(28c5ps6<c6ln(S)N +pln(2/ )N )Poly-Log wrt S

[Sun et.al, 17,ICML]

But For Pure RL

s0s1s3c3s2s4<ANY RL ALGORITHM:c4NX

s5c5<(J(⇡i )s6<c6J(⇡ ⇤ ))p⌦( SN )i=1

Proof uses a reduction from Multi-Armed Bandit29

[Ross & Bagnell, 14, arXiv]

Ex: AggreVaTe
Roll in Learned Policy,
Stop at a randomly picked
time steps a3a1 a2Q⇤ (s, a2 ) = 3⇤

Q (s, a2 ) = 0Roll out Expert’s PolicyQ⇤ (s, a1 ) = 100

23⇤Q(s, a1 ) on⇤4Q(s, a2 )5s,N⇤
Q (s, a3 )Cost-Sensitive classification dataset30

Ex: AggreVaTe

⇡ns

⇡

2

[Ross & Bagnell, 14, arXiv]

3⇤
Q(s, a1 ) on
5...
s, 4N
⇤
Q (s, aA )⇤⇡n+12AggregateDataset3⇤
Q(s, a1 ) on
5...
D + s, 4
Cost-Sensitive ClassifierN⇤
Q (s, aA )XX
⇡n+1 = arg min⇡(a|s)Q⇤ (s, a)⇡s2D aSimple incremental update?

31

Towards Diﬀerentiable AggreVaTe(AggreVaTeD)[Sun et.al, 17, ICML]

Stochastic parameterized policy:⇡✓ = ⇡(·|s; ✓)⇡(·|s) 2sSoftmax Layer
Non-Linear Layer

32

(A)

[Sun et.al, 17, ICML]

Diﬀerentiable AggreVaTe (AggreVaTeD)⇡✓ ns⇡2⇤⇡✓n+1`n (✓) =r✓ `n (✓)|✓n⇤
Q(s, a1 ) on5...
s, 4N⇤
Q (s, aA )XXsµr✓ `n (✓)|✓=✓nAggreVaTeD-NG (Natural Gradient):✓n+1 = ✓n⌘n I(✓n )1r✓n `n (✓n )⇤⇡(a|s; ✓)Q (s, a)aCost-Sensitive loss on
the new batch (noaggregation)

AggreVaTeD-GD (Gradient Descent):✓n+1 = ✓n333

[Sun et.al, 17, ICML]

Diﬀerentiable AggreVaTe (AggreVaTeD)
Discrete MDP, Tabular Policy:
AggreVaTe with
Online Gradient Descent

AggreVaTeD-GD[Zinkevich, 03]AggreVaTe with
Weighted Majority

AggreVaTeD-NG[Littlestone & Warmuth, 03]

Practical Algorithms• AggreVaTe’s theory as Guidance• GD ensures Convergence•Strong Theoretical GuaranteeeJ(ˆ⇡ )  J(⇡ )34

Dependency Parsing
Dependency Parsing on Handwritten Algebra Data

35

Dependency Parsing
Dependency Parsing <=> Sequential Decision Making[Chang et.al 15, Duyck & Gordon 15]

Partial constructed parse tree + Action (Arc) => New partial parse treest+at=>

a1a2

h…

…

o136

st+1o2

Unlabelled Attachment Score

The Higher the Better

Performance of AggreVaTeD, RL, and DAgger
100

92.4
75

83.2

82.6

50

53
38.6

250

AggreVaTeD (LSTM) RL(LSTM)

AggreVaTeD (NN)37

RL(NN)

DAgger

RL: Natural Policy Gradient [Kakade02, Bagnell 04]
DAgger result from Duyck & Gordon, 15

“Surprisingly”
It Can Outperform Expert

The Higher the Better

CartPole and Acrobot

R (y-axis): total reward
Experts
38