Pessimistic Model-based Oﬄine Reinforcement
Learning under Partial Coverage
10/25, 2021 @RL Theory Seminar

Masatoshi Uehara, Wen Sun• 1: Overview• 2: Preliminary• 3: Pessimistic Model-based Oﬄine RL• 4: Examples with Refined Concentrability Coeﬃcients

Offline RL
Online RL

Oﬄine RL

Big logged data

• We only have access to logged data.
• We want to learn high-quality polices fromthe logged data.

Question• Unfortunately, the oﬄine data is often not exploratory.
• Q. Can we still learn good policies when the oﬄine data is
not fully exploratory? (with realizability of the model)

Oﬄine data: ρ(s, a) .

Distribution induced by a policy π, d π(s, a)Global vs. Partial Coverage• Most of oﬄine RL worksπassume globalπ(P ⋆)− V π̂ = Small .
*V( π(P ⋆) is the optimal
policy. V π is the policy
value of π. )d (s, a)coverage. Under max< ∞ ∀π ,s,a ρ(s, a)they show the learned policy π ̂ can competewith the global optimal policy [MS, 2008].

• In this work, we want to show results underpartial coverage. We want to show theoutput policy can compete with any policesd π(s, a)π s . t . max< ∞.
s,a ρ(s, a)*V π − V π ̂ = Small forany π covered by oﬄine
data.

Global vs. Partial Coverage• Global coverage is not satisfied in the following. (π′ is notcovered by oﬄine data)• But, under partial coverage, we can still compete with apolicy π.

dπ(s, a)dπ′(s, a)Oﬄine data: ρ(s, a)What We Know So Far💭
• There are many works under global coverage [MS, 2008].
• In particular (linear) models, there exists a model-basedalgorithm under partial coverage [CUSKS21]. But not forany models!

• Several papers under partial coverage in the model-freesetting [RZMIR21, JYW21, ZCZS21,XCJMA21,ZWB21],
which assume completeness as well as realizability.

What We Show

• We propose a model-based oﬄine RL algorithm CPPO.
We show the PAC guarantee under partial coverageassuming the realizability of the model.

• This works for any MDPs 😄.
• When we have more structures, the density-ratio based
partial coverage concept is refined.

• Examples: linear mixture MDPs, KNRs, low-rank MDPs
(models with unknown features), factored MDPs.

• 1: Overview• 2: Preliminary• 3: Pessimistic Model-based Oﬄine RL• 4: Examples with Refined Concentrability Coeﬃcients

Notation• MDP: ⟨𝒮, 𝒜, r, P, γ, d0⟩. Discount factor γ ∈ [0,1), 𝒮: State space,
𝒜: Action space.

Transition Dynamics

P : 𝒮 × 𝒜 → Δ(𝒮)

Reward functionr : 𝒮 × 𝒜 → [0,1]Initial distribution

d0 ∈ Δ(𝒮)(i) (i) ′(i) nWehave
anoﬄinedataset:𝒟={s, a , s }i=1following•(s, a) ∼ ρ, s′ ∼ P ⋆(s, a). (P ⋆ is the true unknown transition density)•dπ∞t π= (1 − γ)γ dt is a state action discounted occupancy∑
t=0⋆

distribution under π and P .

πV• P is an expected cumulative reward of π under P:

E[∞∑
h=0

γ hrh ∣ s0 ∼ d0, a0 ∼ π(s0), s1 ∼ P(s0, a0), ⋯].Function Classes We Use• We need two function classes:• Model class M ( ⊂ {𝒮 × 𝒜 → Δ(𝒮)} ) to learn thetrue transition P ⋆ .

• Policy class Π ( ⊂ {𝒮 → Δ(𝒜}). Throughout thispresentation, this is the unrestricted policy class.

Model-based RL̂= argmaxP∈M
Step 1: MLE. PMLEn∑

log P(s ′(i) ∣ s (i), a (i)).

i=1

Step 2: Policy Optimization. π ̂ = argmaxπ∈ΠV π ̂PMLE.

d π(s, a)≤ C, ∀π ) , the output canUnder global coverage 😓 ( max•s,a ρ(s, a)compete with the global optimal policy π(P ⋆) with 1 − δ:π(P ⋆)VP⋆ − VPπ̂⋆ = O((1 − γ)−2 C ln( | M | /δ)/n) .

• 1: Overview• 2: Preliminary• 3: Pessimistic Model-based Oﬄine RL• 4: Examples with Refined Concentrability Coeﬃcients

Algorithm
CPPO: Constrained Pessimistic Policy Optimizationn̂
= argmaxP∈Mlog P(s ′(i) ∣ s (i), a (i)).
Step 1: MLE. PMLE∑
i=1

Step 2: Solve constrained Optimization.
π ̂ = argmaxπ∈Π min VPπ whereP∈M𝒟1 n̂ ( ⋅ ∣ s (i), a (i)) − P( ⋅ ∣ s (i), a (i))∥2 ≤ ξ .
M𝒟 = P ∣ P ∈ M,∥PMLE1n∑{}i=1* ξ is a hyperparamter

πSearchfortheleast
favorablemodelintermsofV•P that isfeasible w.r.t the constraint.

• Why? Pessimistic principle (being conservative on
uncovered regions) is employed.

Model-based Concentrability
Coefficient[Definition] Model-based concentrability coefficient:!Cπ† = supE(s,a)∼dπ[∥P′( ⋅ ∣ s, a) − P( ⋅ ∣ s, a)∥21].
2]
E[∥(P′(⋅∣s,a)−P(⋅∣s,a)∥P′∈M (s,a)∼ρ
1•

Smaller than the density ratio: Cπ† ≤ max d π(s, a)/ρ(s, a) .

•†Adaptive to model classes. If the model class is small, Cπ iss,asmall either.

Guarantee of CPPO
[PAC Bound for CPPO] Suppose P! ⋆ ∈ M. (by choosing ξ! properly)With probability 1! − δ,! ∀π*; VPπ*⋆ − VPπ ̂ ⋆ = O†(1 − γ)−2 Cπ*ln( | M | /δ)/n .
()• The output can simultaneously compete with any comparator
polices satisfying partial coverage C † < ∞.
π*⋆†π*π(P)CEvenifistheoptimal
policy,•π(P ⋆)< ∞ is still weaker

than the global coverage (max d π(s, a)/ρ(s, a) < ∞, ∀π) .
s,a•When | ℳ | is infinite, we can still use localized Rademacher
complexities.

Derivation

πππ̂̂Define V = min V . then, π ̂ = argmaxπV .

P
•
P∈MD
⋆
• We can show P ∈ MD in high probability.
ππ̂We
have(Pessimism).
V
≤
V,∀π∈
Π
⋆
•
P

•

VPπ*⋆ − VPπ̂⋆ = VPπ*⋆ − V̂ π* + V̂ π* − VPπ̂⋆ ≤ VPπ*⋆ − V̂ π* + V̂ π̂ − VPπ̂⋆ ≤ VPπ*⋆ − V̂ π* .
Pessimism.
Definition of π ̂ .

• Finally, use performance diﬀerence lemma. Done 👍Model free vs. Model-based• The error in CPPO does not include | Π | . As a result, thepolicy class Π can be unrestricted. More strongly, we cancompete with any history dependent policies.

• [XCJMA21] shows the PAC guarantee under partial

coverage, realizability and Bellman completeness of Qfunction class for any policy in Π, i.e. , 𝒯πQ ⊂ Q .

* 𝒯π is the Bellman operator for a policy π.

• Thus, Π needs to be generally restricted .

• It cannot compete with history dependent policies.

Comparison to Existing Pessimistic
Algorithms• CPPO use the MLE guarantee:̂ ( ⋅ ∣ s, a) − P ⋆( ⋅ ∣ s, a)∥2] ≲E(s,a)∼ρ[∥PMLE
1ln | M | /δ)/n .

• For linear models, [CUSKS21, JYW21] (existing oﬄine RL papers
using negative bonus terms) use

Distance(P(̂ ⋅ ∣ s, a), P ⋆( ⋅ ∣ s, a))2 ≲ Poly(1/n, ln(1/δ), ⋯), ∀(s, a) .

• Average error (over oﬄine data) guarantees are weaker thanpointwise error guarantees 😩

• But average error guarantees are enough for the pessimism
and obtained for any nonlinear models 😆

• 1: Overview• 2: Preliminary• 3: Pessimistic Model-based Oﬄine RL• 4: Examples with Refined Concentrability Coeﬃcients

Next Questions•†
Cπ* is very abstract. Can we replace it with moreinterpretable quantities? (and tighter than the density ratio.)• To see them, we analyze on four models:• Linear mixture MDPs (including linear MDPs),• KNRs (generalization of LQRs),• Low-rank MDPs (with unknown features),• Factored MDPs.

1:Linear MDPs
Definition: Linear MDPs [YW20]
The true P! ⋆ is μ! ⊤(s′)M ⋆ϕ(s, a) ( Unknown !M ⋆ ∈ ℝd1×d2 ) given
d2d1a) : 𝒮 × 𝒜 → ℝ , μ(s):𝒮→ℝ .
feature vectors ϕ(s,!
!

!P ⋆|S| ×|S||A|=!μ|S| ×d1×!M ⋆d1 × d2×!ϕd2 × | S | | A |1:Linear MDPs
Definition: Linear MDPs [YW20]
The true P! ⋆ is μ! ⊤(s′)M ⋆ϕ(s, a) ( Unknown !M ⋆ ∈ ℝd1×d2 ) givend2d1a) : 𝒮 × 𝒜 → ℝ , μ(s):𝒮→ℝ .
feature vectors ϕ(s,!
!
[Concentrability Coefficient for Linear MDPs]! π* = supC̄dx∈ℝ•x ⊤E(s,a)∼dπ⋆[ϕ(s, a)ϕ(s, a)⊤]xx ⊤E(s,a)∼ρ[ϕ(s, a)ϕ(s, a)⊤]x.

Smaller than the density ratio, i.e., C̄π* ≤ max d π*(s, a)/ρ(s, a).
s,a• If C̄π* is small, this implies the oﬄine data suﬃciently covers thesubspace that the comparator policy π* visits measured by ϕ(s, a).

•In tabular MDPs, C̄π* = max d π*(s, a)/ρ(s, a).
s,a1:Linear MDPs
[PAC Bound for CPPO] Suppose !P ⋆ ∈ M. With probability 1! − δ,! ∀π*; VPπ*⋆ − VPπ ̂ ⋆ = Õ((1 − γ)−2C̄π*d 2 ln(1/δ)/n) .

• Partial coverage is refined as C̄π* < ∞ .
⊤• E(s,a)∼ρ[ϕ(s, a)ϕ(s, a) ] can be singular. (Previous works assume
the non-singularity. )1: Linear Mixture MDPs
Definition: Linear Mixture MDPs [AJSWY20,MJTS 20]⋆⋆⊤
The true !P is !θ ψ(s, a, s′) given a feature vectord!
ψ(s,a, s′) : 𝒮 × 𝒜 × 𝒮 → ℝ .

• Linear MDPs belong to linear mixture MDPs.
∫ψV (s, a) = ψ(s, a, s′)V(s′)d(s′)
Definepseudo
featurevectors:•[Concentrability Coefficient for Linear Mixture MDPs]!C̄π*,mix = sup supdP∈ZP⋆ x∈ℝx ⊤E(s,a)∼dπ⋆[ψVPπ*(s, a)ψVPπ*(s, a)⊤]xx ⊤E(s,a)∼ρ[ψVPπ*(s, a)ψVPπ*(s, a)⊤]xwhere !ZP⋆ = {P : E(s,a)∼ρ[TV(P( ⋅ ∣ s, a), P ⋆( ⋅ ∣ s, a)2] ≤ ξ}.

• C̄π*,mix is defined for varying feature vectors ψVPπ*.
• In linear MDPs, C̄π*,mix reduces to C̄π*.

,1: Linear Mixture MDPs
[PAC Bound for CPPO] Suppose !P ⋆ ∈ M. With probability 1! − δ,! ∀π*; VPπ*⋆ − VPπ ̂ ⋆ = Õ((1 − γ)−2C̄π*,mixd 2 ln(1/δ)/n) .

• Partial coverage concept is refined as C̄π*,mix < ∞ .

2 KNRs
Definition: Kerneliazed nonlinear regulators. The true P ⋆ is a⋆⋆dS×d
Gaussian distribution 𝒩(W ϕ(s, a), I) (W ∈ ℝ) givenda feature vector ϕ : 𝒮 × 𝒜 → ℝ . (dS is a dimension of S)• Include LQRs.
• Include RKHS models (GPs) .
[Concentrability Coefficient for KNRs]! π* = supC̄

dx∈ℝ

x ⊤E(s,a)∼dπ⋆[ϕ(s, a)ϕ(s, a)⊤]xx ⊤E(s,a)∼ρ[ϕ(s, a)ϕ(s, a)⊤]x.

• This is exactly the same as the one in linear MDPs.

2 KNRs[PAC Bound for CPPO]
Let Σ! ρ = E(s,a)∼ρ[ϕ(s, a)ϕ(s, a)⊤]. Suppose P! ⋆ ∈ M. With 1! − δ,! ∀π*; VPπ*⋆ − VPπ ̂ ⋆ = Õ

(1 − γ)−2rank(Σρ)3 dSC̄π* ln(1/δ)/n .
()• Partial coverage concept is refined as C̄π* < ∞ .
• Σρ can be singular!! The error depends on rank[Σρ] but not d.
• d can be infinite. Formally, extended to the infinite-dimensionalsetting, P ⋆ = 𝒩(g ⋆(s, a), I) where g ⋆is an element of RKHS.

3: Low-rank MDPs
Definition: Low-rank MDPs [JKALS17, AKKS20]. The true⋆⋆⊤ ⋆⋆⋆
P is μ (s′) ϕ (s, a). Both μ ( ⋅ ), ϕ ( ⋅ ) are unknown⋆d⋆dfeatures. ( μ : 𝒮 → ℝ , ϕ : 𝒮 × 𝒜 → ℝ )!P ⋆|S| ×|S||A|μ! ⋆=×!ϕ ⋆d× |S||A||S| ×d• Features are unknown 😩. We set the function classes⋆⋆μ ∈ Ψ, ϕ ∈ Φ .

• Low-rank MDPs include latent variable models, block
MDPs and linear MDPs.

3: Low-rank MDPs
Definition: Low-rank MDPs [JKALS17,AKKS20]. The true P ⋆⋆⊤ ⋆⋆⋆is μ (s′) ϕ (s, a). Both μ ( ⋅ ), ϕ ( ⋅ ) are unknown
features. ( μ ⋆ : 𝒮 → ℝd, ϕ ⋆ : 𝒮 × 𝒜 → ℝd)[Concentrability Coefficient for Low-rank MDPs]!C̄π*,ϕ* = supdx∈ℝ

x ⊤E(s,a)∼dπ⋆[ϕ ⋆(s, a)ϕ ⋆(s, a)⊤]xx ⊤E(s,a)∼ρ[ϕ ⋆(s, a)ϕ ⋆(s, a)⊤]x†Lookssimilartotheoneinlinear
MDPs
andKNRs🤔
C•π*,ϕ ⋆depends on the only true feature ϕ ⋆ but not on other features.

3: Low-rank MDPs
[PAC Bound for CPPO] Let Σ! ρ,ϕ ⋆ = E(s,a)∼ρ[ϕ ⋆(s, a)ϕ ⋆(s, a)⊤].
Suppose P! ⋆ ∈ M. with 1! − δ,! ∀π*; VPπ*⋆ − VPπ ̂ ⋆ = Õ((1 − γ)−2C̄π*,ϕ⋆rank(Σρ,ϕ⋆)ln( | M | /δ)/n).

• Partial coverage concept is refined as C̄π*,ϕ⋆ < ∞ .
• Error depends on rank(Σρ,ϕ⋆) instead of d.
• Previous related work on sparse linear MDPs ([HDLSW20])
assumes the non-singularity of Σρ,ϕ for any ϕ ∈ Φ .

4. Factored MDPs
Definition: Factored (tabular) MDPs.

P ⋆(s′ ∣ s, a) =d∏
i=1

𝒮 = 𝒪dP ⋆(s′[i] ∣ s[Pai], a) . Denote 𝒮i = 𝒪|Pai| .

Pa1 = [2,4]

S’[1]

S[1]

Pa2 = [1,d]

S’[2]

S[2]

Pa3 = [4]

S’[3]

…..
S[d]

S[3]
S[4]…..
S[d]Factored MDPs are governed by O( ∑ | 𝒪 ||Pai| ) parameters.

•id• Non-factored MDPs are governed by O( | 𝒪 | ) parameters.
• When | Pai | < < d, the diﬀerence is huge.
• Our goal is leveraging this factored structure.

4. Factored MDPs
Definition: Factored (tabular) MDPs.
⋆P (s′ ∣ s, a) =d

∏
i=1

•

Introduce C̄[ j]π*,∞=𝒮=𝒪d|Pai|⋆P (s′[i] ∣ s[Pai], a) . Denote 𝒮i = 𝒪maxd π(sj, a)sj∈𝒮j,a∈𝒜 ρ(sj, a), ν(sj, a) =∑ν(s, a)

s:∈𝒮,s[Paj]=sj[ j]C̄• π*,∞ is the marginal density ratio over each component.

ExamplePa1 = [2,4]

S’[1]

S[1]

Pa2 = [1,d]

S’[2]

S[2]

Pa3 = [4]S’[3]πd (s1, a)[1]C̄π*,∞ =max.
s1∈{s[2],s[4]},a ρ(s1, a)

…..
S[d]

S[3]
S[4]

…..
S[d].

4. Factored MDPs
[Concentrability Coefficient for Factored MDPs]
j! π*,∞ = max C̄C̄j∈[1,⋯,d]π*,∞πd(s, a)[ j]C̄π*,∞ is smaller than the global density ratio max•s∈𝒮,a∈𝒜 ρ(s, a)
for any j ∈ [1,⋯, d].

d π(s, a)Thus, C̄π*,∞ is smaller than the global density ratio max.
•s∈𝒮,a∈𝒜 ρ(s, a)4. Factored MDPs
[PAC Bound for CPPO] Suppose !P ⋆ ∈ M. With probability 1! − δ,! ∀π*; VPπ*⋆ − VPπ ̂ ⋆ = Õ((1 − γ)−2dC̄π*,∞∑| 𝒪 |Pai ln(1/δ)/n).

i• Partial coverage concept is refined as C̄π*,∞ < ∞ .
• This formally demonstrates the benefit of the factoredstructure in terms of the coverage condition.

Disclaimer• We claim CPPO works for any MDPs. What does it mean?
• Any MDPs where the MLE has valid statistical guarantees.
• CPPO does not work on (diﬀerent) linear MDPs [JYWJ20]
and linear Bellman complete MDPs 😩.

• But, by taking a model-based perspective on them andmodifying CPPO, we can still ensure the PAC guarantee
under partial coverage.

Conclusion• CPPO has the PAC guarantee under partial coverageassuming the realizability of the model. This works for anyMDPs.

• Partial coverage concept is tailored to each model:• KNRs, linear mixture MDPs: relative condition numbers.
• Low-rank MDPs: relative condition numbers defined on
the true unknown features.

• Factored MDPs: density ratios considering the factoredstructures.

Future Directions• Computationally eﬃcient algorithm which has
PAC guarantee under partial coverage.

• Lower bound results.
• Bayesian algorithms.

References• [CUSKS21] Mitigating covariate shift in imitation learning via offline data without great coverage. 202• [MS 08] Finite-time bounds for fitted value iteration. ´ Journal of Machine Learning Research, 9(May):815–857,2008.
• [XCJMA21] Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint arXiv:2106.06926,2021.
• [ZWB 21] Provable benefits of actor-critic methods for offline reinforcement learning. arXiv preprint arXiv:
2108.08812, 2021.
• [RZMJR21] Bridging offline reinforcement learning and imitation learning: A tale of pessimism. arXiv preprint
arXiv:2103.12021, 2021.
• [JYW21] Is pessimism provably efficient for offline rl? arXiv preprint arXiv:2012.15085, 2021.
• [ZCZS21] Corruption-robust offline reinforcement learning. arXiv preprint arXiv:2106.06630, 2021.
• [YW20] Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In Proceedings of the 37th
International Conference on Machine Learning, pages 10746–10756, 2020.
• [AJSWY20] Model-based reinforcement learning with value-targeted regression. In International Conference onMachine Learning, pages 463–474. PMLR, 2020.
• [AKKS20] Flambe: Structural complexity and representation learning of low rank mdps. In Advances in NeuralInformation Processing Systems, volume 33, pages 20095–20107, 2020.
• [HDLSW20] Sparse feature selection makes batch reinforcement learning more sample efficient. In InternationalConference on Machine Learning, pages4063–4073. PMLR, 2021.