Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
Nan Jiang1,3, Akshay Krishnamurthy2, Alekh Agarwal3, John Langford3, Robert E. Schapire3
1
University of Michigan, Ann Arbor 2University of Massachusetts, Amherst 3Microsoft Research, NYC

Long-term Planning
Approximate DP

PAC-MDP Theory

Our Answer:● A new measure – Bellman rank

Problem

Generalization

Exploration○ Polynomial sample
complexity guarantee

Simplified Algorithm● Generate trajectories using πf’ .

● A new algorithm – OLIVE
Contextual Bandits

Proof Sketch

Bound

Full matrix view

(assuming no statistical errors)○ Captures a wide range oftractable RL problems?

OLIVE (Optimism-Led Iterative Value-function Elimination)

RL problems with low Bellman rank

Introduction: 3 challenges of RL

Tabular MDP(context = state)● Eliminate all f with non-zero
Bellman error.

Bellman rank≤
# states

PAC Learning:
known (e.g., [2])State distribution
induced by πf’

Bellman error of fon each state● Choose a new πf’ optimistically:
f’ is the maximizer ofamong the surviving functions.

Value-based RL in CDPs
Contextual Decision Processes (CDPs): episodic RL with rich observations● Action space A, horizon H.
● Context space X. A context is ...
○ any function of history that expresses a good policy & value function○ e.g., last 4 frames of images in Atari games○ e.g., (state, time-step) for finite-horizon tabular MDPs

● An episode: x1, a1, r1, x2, …, xH, aH, rH● Policy π : X → A. Want to maximize

hiddenstate

POMDP with rich obs.
and reactive value function(context = current obs.)

Bellman rank≤# hidden statesrichobs.

Factored matrix viewAnalysis of iteration complexity● Suffices to find a row that contains
non-zero entry in surviving columns.
● Optimism finds the row with a
non-zero diagonal entry (for some h).

.

In general, |X| is very large ⇒ Requires generalization!
Large MDP with
low-rank transition(context = state)

Bellman rank≤
rank of transition
matrixhiddenfactorBellman rank≤poly(# abstractstates, # actions)abstract
statestate

Analysis that considers statistical errors

Geometric view
(Bellman rank = 2)

NewLarge MDP with
Q*-irrelevant abstraction(context = abstract state)

Need additional condition, otherwise
exponential lower bound applies. [1].

● If dark blue vectors are linearly indep.,#iterations (for h) ≤ Bellman rank.

Extends [1]Value-based PAC-RL in CDPs
● Input: a function space F which contains Q*● Output: π such that, w.p. ≥ 1- , Vπ* - Vπ ≤ εafter acquiring poly(|A|, H, log|F|, 1/ε, 1/ ) trajectories.

● Repeat until

Average Bellman error

state

Known [3]Bellman rank
Rank of average Bellman error matrices(maximum over h=1, …, H)PSRs with rich obs.
and reactive value function(context = current obs.)

candidate value function● Sample-efficient toevaluate a row at a time:
generate trajectories using πf’until h, then random action+ importance weighting[Todd’82]:
Expressing Bellman error matrix using a submatrix of the
System Dynamics Matrix (naturally low-rank for PSRs).
(histories = all (h-1)-long seq., tests = length 2 seq.)

,

|⟨

⟩|

=> Significant reduction in ellipsoid volumeSample complexity:

M: Bellman rankNew● Size |F| × |F|● Q* has 0 Bellman error on all
roll-in policies (col of 0’s)roll-in policy

Bellman rank≤poly(system dim,# actions)Linear QuadraticRegulators(context = state)

Bellman rank≤poly(state space dim,action space dim)●●●

Need policy class + state-value function classrepresentation (see Extensions).
Crucially depends on the choice of function classes:
linear policies + quadratic value functions.
Algorithm does not apply as-is due to continuous
action space.

Known [4]References[1] Krishnamurthy, Agarwal, and Langford. PAC reinforcement learning with rich observations. NIPS 2016.
[2] Kearns and Singh. Near-Optimal Reinforcement Learning in Polynomial Time. ML 2000.
[3] Lihong Li. A unifying framework for computational reinforcement learning theory. PhD thesis, 2000.
[4] Osband and Van Roy. Model-based reinforcement learning and the eluder dimension. NIPS 2014.

Extensions● Can use doubling trick to guess unknown Bellman rank.
● Can compete with functions that have small non-zero Bellman errors.
● Can work with policy class + V-value function class (as opposed to Q).
○ Compete with the best (policy, V-value function) pair that respects
Bellman equation for policy evaluation.
● Can accommodate infinite classes with bounded statistical complexity.
● Can handle approximately low-rank Bellman error matrices.