Model-based RL in Contextual
Decision Processes:
PAC Bounds and Exponential Improvements
over Model-free Approaches
Wen Sun
CMU -> MSR NYC
Joint work with Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford

Reinforcement Learning
Markov Decision Process
AgentEnvironment⇡(x) ! a

Policy: determine action based on state2

Reinforcement Learning
Markov Decision Process
Agent

Environment⇡(x) ! a

Policy: determine action based on state

Send reward and next state from aMarkovian transition dynamics
0r(x, a),x ⇠ P (·|x, a)2

Reinforcement LearningMarkov Decision Process
AgentEnvironment⇡(x) ! a

Policy: determine action based on state

H Steps

Send reward and next state from a
Markovian transition dynamics
0r(x, a),x ⇠ P (·|x, a)2

Reinforcement Learning
Markov Decision Process
AgentEnvironment⇡(x) ! a

Policy: determine action based on state

H Steps

Send reward and next state from a
Markovian transition dynamics
0r(x, a),x ⇠ P (·|x, a)Maximize expected total reward:J(⇡) = E[r1 + r2 + · · · + rH |⇡]2

Progress of RL in Theory
Sample Eﬃciency
in Small Discrete MDPs

3

Progress of RL in Theory
Sample Eﬃciency
in Small Discrete MDPs

Sample Complexity:
To achieve ✏ near-optimal policy,
need at mostpoly(# of states, # of actions, Horizon, 1/✏)many interactions[e.g., Kearns & Singh, 02, Dann & Brunskill, 15, Azar et.al, 17]3

Progress of RL in Theory
Sample Eﬃciency
in Small Discrete MDPs

Sample Complexity:
To achieve ✏ near-optimal policy,
need at mostpoly(# of states, # of actions, Horizon, 1/✏)many interactions[e.g., Kearns & Singh, 02, Dann & Brunskill, 15, Azar et.al, 17]3

Progress of RL in Theory
Large-Scale Decision Making Problems
Sample Eﬃciency
in Small Discrete MDPs

6=
Sample Complexity:
To achieve ✏ near-optimal policy,
need at mostpoly(# of states, # of actions, Horizon, 1/✏)many interactions[e.g., Kearns & Singh, 02, Dann & Brunskill, 15, Azar et.al, 17]3

Progress of RL in Theory
Large-Scale Decision Making Problems
Sample Eﬃciency
in Small Discrete MDPs

f 2F

BridgeSample Complexity:
To achieve ✏ near-optimal policy,
need at mostpoly(# of states, # of actions, Horizon, 1/✏)many interactions[e.g., Kearns & Singh, 02, Dann & Brunskill, 15, Azar et.al, 17]4

Progress of RL in Theory
Large-Scale Decision Making Problems
Sample Eﬃciency
in Small Discrete MDPs

f 2F

BridgeSample Complexity:
To achieve ✏ near-optimal policy,
need at mostpoly(# of states, # of actions, Horizon, 1/✏)many interactions[e.g., Kearns & Singh, 02, Dann & Brunskill, 15, Azar et.al, 17]

VC-dim4

Previous Works on PAC RL
w/ General Function Approximation

5

Previous Works on PAC RL
w/ General Function Approximation
Contextual Bandits (horizon=1)(e.g., Auer et al., 02, Langford & Zhang, 07)

5

Previous Works on PAC RL
w/ General Function Approximation
Contextual Bandits (horizon=1)(e.g., Auer et al., 02, Langford & Zhang, 07)Contextual Decision Process(Krishnamurthy et al.,16, Jiang et al., 17, Dann et al, 18)

5

Previous Works on PAC RL
w/ General Function Approximation
Contextual Bandits (horizon=1)(e.g., Auer et al., 02, Langford & Zhang, 07)Contextual Decision Process(Krishnamurthy et al.,16, Jiang et al., 17, Dann et al, 18)

Model-based vs Model-free5

Previous Works on PAC RL
w/ General Function Approximation
Contextual Bandits (horizon=1)(e.g., Auer et al., 02, Langford & Zhang, 07)Contextual Decision Process(Krishnamurthy et al.,16, Jiang et al., 17, Dann et al, 18)

Model-based vs Model-free
A PAC model-based Algorithm
5Setup of Model-Based RL

6

Setup of Model-Based RL

0?

x ⇠ P (·|x, a)6

Setup of Model-Based RL
Function Approximators(x, a)

P (·|x, a)

P = {P : X ⇥ A !

0(X )}?

x ⇠ P (·|x, a)6

Setup of Model-Based RL
Function Approximators(x, a)

P (·|x, a)

P = {P : X ⇥ A !
1. Realizability: P0?

(X )}

2P?

x ⇠ P (·|x, a)6

Setup of Model-Based RL
Function Approximators(x, a)

P (·|x, a)

P = {P : X ⇥ A !
1. Realizability: P0?

2. Access to
Optimal Planner (OP)(X )}OP (P, r) ) ⇡P

2P?

x ⇠ P (·|x, a)6

Definition of Model-free RL
Input: Q , {Q : X ⇥ A ! R}7

Definition of Model-free RL
Input: Q , {Q : X ⇥ A ! R}
Policy: determine action based on state

H Steps

Env: reveal next statex

7Definition of Model-free RL
Input: Q , {Q : X ⇥ A ! R}
Policy: determine action based on state

H Steps

Q-profile:[Q(x, a)]Q2Q,a2A
all possible Q values evaluated at statex

7Definition of Model-free RL
Input: Q , {Q : X ⇥ A ! R}
Policy: determine action based on state

H Steps

Q-profile:[Q(x, a)]Q2Q,a2A
all possible Q values evaluated at stateEﬃcient Q-learning (Jin et.al, 18)
Fitted Q-Iteration (Ernst et.al., 05)
OLIVE (Jiang et.al, 17)
Policy Gradient (Williams 92)

x7

An Exponential Improvement
over Model-free RL

8

An Exponential Improvement
over Model-free RL

There exists MDPs (e.g., Factored MDPs), s.t., to learn near optimal policy,
Model-Based RL:
Polynomial Sample
Complexity

VS8

ANY Model-Free RL:⌦(exp(H))

We have been studying model-based RL,
BUT…

xx0a0LD(x, x )aLipschitz MDPs
[Kearn, Langford, Kakade, 03]

Small Tabular MDP
Factored MDPs

[Kearn & Singh, 02][Guestrin et.al, 03; Osband & Van Roy,13 ]Linear Quadratic Regulator (LQR)[Dean et.al, 18]

9We have been studying model-based RL,
BUT…

xx0

a0

LD(x, x )a

Lipschitz MDPs
[Kearn, Langford, Kakade, 03]

A Unified
Algorithm?
Small Tabular MDP
Factored MDPs

[Kearn & Singh, 02][Guestrin et.al, 03; Osband & Van Roy,13 ]Linear Quadratic Regulator (LQR)[Dean et.al, 18]

9

A Unified Measure—Witness Rank
Misfit Matrix:2R10|P|⇥|P|

A Unified Measure—Witness Rank
Misfit Matrix:

Pr2RPc10|P|⇥|P|

A Unified Measure—Witness Rank
Misfit Matrix:

PrW (Pr , Pc ; F)

Pc

102R|P|⇥|P|

A Unified Measure—Witness Rank
Misfit Matrix:
ProvidesConditional
State-action
Distribution

PrW (Pr , Pc ; F)

Pc
Ex⇠⇡Pr ,a⇠U

102R|P|⇥|P|

A Unified Measure—Witness Rank
Misfit Matrix:
ProvidesConditional
State-action
DistributionPr

W (Pr , Pc ; F)

Pc

2RCandidate

Ex⇠⇡Pr ,a⇠U [EEx0 ⇠Pc f (x, a, x0 )Imaginary

10|P|⇥|P|

Ex0 ⇠P ? f (x, a, x0 )]RealA Unified Measure—Witness Rank
Misfit Matrix:
ProvidesConditional
State-action
DistributionPr

W (Pr , Pc ; F)

Pc

2RCandidate

W (Pr , Pc ; F) = max Ex⇠⇡Pr ,a⇠U [E
Ex0 ⇠Pc f (x, a, x0 )f 2F
Witness functions(aka discriminators)

Imaginary

10|P|⇥|P|

Ex0 ⇠P ? f (x, a, x0 )]RealA Unified Measure—Witness Rank
Misfit Matrix:
ProvidesConditional
State-action
Distribution

PrW (Pr , Pc ; F)

Pc

2RCandidate

W (Pr , Pc ; F) = max Ex⇠⇡Pr ,a⇠U [EEx0 ⇠Pc f (x, a, x0 )f 2F
Witness functions(aka discriminators)

ImaginaryEx0 ⇠P ? f (x, a, x0 )]Witness Rank , rank of this misfit matrix
10|P|⇥|P|

RealCapture Complexities of Existing RL problems

xx0aaLD(x, x0 )Lipschitz Continuous MDPs
[Kearn, Langford, Kakade, 03]

Rank <= Covering numberof state space

Small Discrete MDP

Factored MDPs

Rank <= # of state

11[Guestrin et.al, 03; Osband & Van Roy,13 ]Rank <= exp(in-degree)

LQR
Rank <= O(d^2)

Capture Complexities of Existing RL problems

xx0aaLD(x, x0 )Lipschitz Continuous MDPs
[Kearn, Langford, Kakade, 03]

Rank <= Covering numberof state space

Small Discrete MDP

A Unified
Algorithm!

Rank <= # of state

11

Factored MDPs

[Guestrin et.al, 03; Osband & Van Roy,13 ]Rank <= exp(in-degree)

LQR
Rank <= O(d^2)

Sample Complexity
To achieve ✏ near-optimal policy (w/ high probability)

12

Sample Complexity
To achieve ✏ near-optimal policy (w/ high probability)Õ⇣ H 3 R2 |A|
✏2log

12

⇣ |F||P| ⌘⌘Sample Complexity
To achieve ✏ near-optimal policy (w/ high probability)
Witness RankÕ

⇣ H 3 R2 |A|
✏2log

12

⇣ |F||P| ⌘⌘Sample Complexity
To achieve ✏ near-optimal policy (w/ high probability)
Witness RankÕ

⇣ H 3 R2 |A|✏2log⇣ |F||P| ⌘⌘Complexities ofmodel class & discriminator class
Poly Dependency on # of states

12Take-home Messages

Take-home Messages
Model-based RL could be exponentially more
sample eﬃcient than model-free ones

Take-home Messages
Model-based RL could be exponentially more
sample eﬃcient than model-free ones
Sample eﬃciency is possible when Witness
Rank is small