Provably Efficient Imitation Learningfrom Observations Alone
Wen Sun
CMU —> MSR NYC[wensun@cs.cmu.edu]
Joint work with Anuridh Vemula, Byron Boots, and Drew Bagnell

1Motivation[Williams et.al, 17][Ross et al. 13][Mnih et al. 15]

Less data,
reward less clear[Sliver et al. 17]

Huge data

Leverage expert’s demonstrations to learn efficiently,
even w/ unknown reward/coste.g., Apprenticeship Learning [Abbeel & Ng 05, Syed & Schapire 08]
Inverse Optimal Control [Ziebart & Bagnell, 10]Interactive Imitation Learning [Ross& Bangell, 11, 14]Generative Adversarial Imitation Learning [Ho & Ermon 16]2

Theoretical Motivation:
Scale Provably Efficient RL to Large Scale MDPs
Sample Eﬃciency

f 2F
Sample Complexity:
To achieve ✏ near-optimal policy,
we need at mostpoly(# of states, # of actions, Horizon, 1/✏)

6=

Bridgee.g. VC-dim

many interactions[e.g., Kearns & Singh, 02, Dann & Brunskill, 15, Azar et.al, 17]3

Previous Works that Can Achieve:poly(Horizon, # of actions, 1/✏, complexity of function classes)

1. Reactive POMDP (small # of hidden state)(Krishnamurthy et al., NeurIPS 16, Dann et al, NeurIPS 18, Du et al, ICML 19)

2. Decision Process w/ Low Bellman Rank
(Jiang et al., ICML 17)

3. Markov Decision Process w/ Low Witness Rank
(Sun et al., COLT 19)…and a lot of works on Contextual Bandits (horizon=1)(e.g., Agarwal et al., ICML 14)

4

Imitation Learning from Observations[e.g., Torabi et.al 18, Edwards et.al, 18, Liu et.al, 17, Peng et.al,18]

Trajectories ofObservations
Learning From
Observations
No interactive expert, no expert action, no reset, no cost signals.
Finite Horizon (T-step) Episodic MDP
Ground-Truth cost function cT (x) 2 [0, 1] .

Different from RL:
Unknown cost, but
we have state-only demonstrations from expert
5⇡?

Model-Free Algorithm:
Forward Adversarial Imitation Learning (FAIL):⇡1 , ⇡2 , ⇡3 , . . . , ⇡T
Two-player game
Reduce Sequential Problem into
H many min-max games61

Min-Max Games: Minimizing
Integral Probability Metrics (IPM)
Distinguish 2 distributions:max (Ex⇠P [f (x)]Set ofdiscriminators

f 2FEx⇠Q [f (x)])

Total-variation
Wasserstein Distance
Max Mean Discrepancy…

Learning the first policy:?
⇠ µ1⇠ P (·|x0 , ⇡0 (x0 ))⇡0 and Dynamics:

Expert distribution

Generator

min max f⇡0 2⇧ f 2F

f

—
7IPM

Learning the Second Policy
Now we have already learned ⇡0Roll in?
⇠ µ2⇠ P (·|x1 , ⇡1 (x1 ))⇡1 and Dynamics:

Expert distributionf⇡ 2⇧ f 2F

Generatorf

min max—18

Keep Forward Training….

⇡0⇡2

⇡1

⇠ P (·|x2 , ⇡2 (x2 ))Rolling in…

min max⇡2 2⇧ f 2F?
⇠ µ3ff—9

Capacity of Discriminators

min max⇡22 2⇧ f 2F

ff

—Strong Discriminator => Overfitting (need a lot of samples)
Weak Discriminator => Unable to distinguish

BEInherent Bellman Error(?

f )(x) , Ea⇠⇡? (x),x0 ⇠Px,a f (x )0BE = minmax
kf
0
ff0?

⇤ff k1
10F

Analysis of FAIL
Realizability Assumption:?

?

⇡ 2 ⇧, V 2 F( ⇡ ? , V ? : expert’s policy & value function)

To learn a near-optimal policy:?
2J(⇡)

J(⇡ )  T (BE + ✏)we need samples:poly(T, A, 1/✏, SC(⇧), SC(F))
Statistical Complexity ofPolicy & Discriminator classes
Discriminators ⇡ expert’s value functions
Approximate Policy Improvement over expert
11

Is Inherent Bellman Error Avoidable
in the IL from Observation Setting?
Yes in model-based setting…
Start with a realizable model class P & discriminator class F?

P 2 P, V 2 F

There exists an algorithm that takes {P, F} as input,outputs an optimal policy, with # of samples:✏Poly (H, A, 1/✏, SC(P), SC(F))(Note such result is not possible in RL setting [1])but, model-free IL from Observation setting?
[1] Model-based RL in CDPs: PAC bounds and Exponential Improvements over Model-free Approaches,
W Sun, N Jiang, A Krishnamurthy, A Agarwal, J Langford, COLT 1912

A Simpler Baseline…
Minimizing some divergence between avg state distributions(e.g., Generative Adversarial Imitation Learning (GAIL))[Ho & Ermon 16]d⇡ average state distribution over horizon of ⇡min max E⇡2⇧

f 2Fx⇠d⇡ [f (x)]Ex⇠d⇡? [f (x)]new RL objective function,13

Success rate

Simulation Results# of expert trajectories
14

FAIL code: https://github.com/wensun/Imitation-Learning-from-Observation
GAIL (without actions) is adopted from existing code in OpenAI baselines

Take Away Messages
With Observations alone from experts, we canlearn near optimal policies:
Near-Optimal Guarantee• Supervised Learning type sample complexity• Out-of-box performance is pretty good•

Future Work
Get rid of inherent Bellman error in model-free IL setting?
• A computationally efficient model-based algorithm?
•Thanks!
wensun@cs.cmu.edu
https://github.com/wensun/Imitation-Learning-from-Observation