PaperlayerView exact revision on arXiv

Source-linked AI summary

Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage

Masatoshi Uehara, Wen Sun

arXiv:2107.06226v4cs.LGcs.AIstat.ML

TL;DR

Offline model-based reinforcement learning often relies on strong full-coverage or function-class assumptions. This paper introduces CPPO, showing that realizability and partial coverage suffice for competing with covered policies, while extending the framework to structured MDPs.

  • Problem

    Full coverage and Bellman completeness are strong assumptions, motivating offline reinforcement learning under partial coverage with general model classes.

  • Method

    CPPO encodes pessimism through a constraint over a realizable model class, with related incremental policy optimization and posterior-sampling algorithms for computational purposes.

  • Results

    Under realizability and partial coverage, CPPO learns a policy comparable to any covered policy, including history-dependent policies, and refines partial-coverage conditions for structured MDPs.

  • Takeaways & Limitations

    Model-based offline reinforcement learning can compete with covered policies without full coverage or Bellman completeness, while structural assumptions yield more specialized partial-coverage conditions.

  • Takeaways & Limitations

    For nonparametric linear MDPs, the PAC bound incurs ln(|Π|), requiring a restricted policy class and potentially being worse than model-free results.

Abstract

from arXiv · show

We study model-based offline Reinforcement Learning with general function approximation without a full coverage assumption on the offline data distribution. We present an algorithm named Constrained Pessimistic Policy Optimization (CPPO)which leverages a general function class and uses a constraint over the model class to encode pessimism. Under the assumption that the ground truth model belongs to our function class (i.e., realizability in the function class), CPPO has a PAC guarantee with offline data only providing partial coverage, i.e., it can learn a policy that competes against any policy that is covered by the offline data. We then demonstrate that this algorithmic framework can be applied to many specialized Markov Decision Processes where additional structural assumptions can further refine the concept of partial coverage. Two notable examples are: (1) low-rank MDP with representation learning where the partial coverage condition is defined using a relative condition number measured by the unknown ground truth feature representation; (2) factored MDP where the partial coverage condition is defined using density ratio based concentrability coefficients associated with individual factors.

1 Introduction

The paper asks whether model-based offline RL can learn under partial coverage with only realizability, and answers affirmatively through CPPO. It extends partial-coverage guarantees to structured MDPs and offers Bayesian alternatives with different guarantees.

  • Motivation: Offline RL seeks learning from static transition data, but common guarantees require full coverage and strong function-class assumptions such as Bellman completeness.Full coverage requires the offline data to cover policies broadly, while Bellman completeness requires Bellman updates to remain in the function class.
  • Research question: Given realizability and partial coverage, the paper asks whether a policy can compete with any comparator policy covered by the offline distribution.The comparator need not be optimal and may be history-dependent.
  • Main result: CPPO uses a realizable model class and constrained pessimistic policy optimization to learn a policy as good as any covered comparator, including history-dependent policies.This result holds for any MDP with a realizable model class.
  • Structured settings: For structured MDPs, the framework refines density-ratio concentrability into problem-specific coverage quantities.The paper treats low-rank, factored, linear, linear-mixture, and KNR settings.
  • Structured settings: In low-rank MDPs, coverage becomes a relative condition number under the unknown true representation, while factored MDPs use density ratios associated with individual factors.These refinements target tighter quantities than a potentially vacuous global density ratio in large-scale MDPs.
  • Bayesian alternatives: Bayesian incremental policy optimization and posterior sampling avoid explicitly designing pessimism but replace worst-case guarantees with Bayesian suboptimality-gap guarantees.This is presented as a computational alternative under Bayesian assumptions.
  • Scope: The model-based theory relies on realizability, which is usually considered stronger than realizability in model-free offline RL.The paper presents this assumption as an important scope boundary when contrasting the two settings.

2 Related work

The related work spans offline RL and representation learning in RL. The paper distinguishes its offline partial-coverage PAC guarantees from prior representation-learning and dimensionality-reduction studies.

  • Offline RL: Prior offline RL work addresses insufficient dataset coverage through both model-free and model-based methods.The cited literature treats limited coverage as a central challenge caused by the lack of online exploration.
  • Representation learning: Representation learning for low-rank MDPs has been studied in online learning from both model-based and model-free perspectives.Other online studies consider representation learning under different model assumptions.
  • Representation learning: The paper states that its offline setting requires algorithms and analyses different from those used in related online representation-learning work.The distinction is tied to the offline nature of the data and guarantees.
  • Offline representation learning: Prior offline studies considered dimensionality reduction in predefined kernel spaces and feature selection in sparse linear MDPs, rather than PAC guarantees under partial coverage.The paper also notes that one cited kernel-based study did not analyze policy-optimization errors after learning features.

3 Preliminaries

The paper formalizes an MDP with transition dynamics, rewards, discounting, and initial-state distribution, then defines offline data sampled from an offline state-action distribution. Its focus is partial rather than global coverage.

  • MDP setting: The MDP is defined by state and action spaces, transition kernel P, discount factor γ, reward function r, and initial distribution d0.Rewards are assumed known, with unknown-reward extensions described as straightforward.
  • Policy evaluation: A policy maps states or histories to action distributions, and V^π_P denotes its expected cumulative reward under model P, initial distribution d0, and reward r.The notation also includes Q-functions, advantage functions, and state-action occupancy distributions.
  • Offline data: The offline dataset samples state-action pairs from ρ, observes the known reward r(s,a), and samples next states from the true transition P⋆.The goal is to learn from this dataset without further environment interaction.
  • Objective: The formal objective is to construct an offline algorithm whose output minimizes the suboptimality gap relative to covered comparator policies, potentially from an unrestricted policy class.The policy class may include non-Markovian policies.
  • Coverage: Global coverage requires bounded occupancy-to-data density ratios for all policies or a full-rank offline feature covariance matrix.Under global coverage, guarantees can target the globally optimal policy.
  • Coverage: Partial coverage requires only that a comparator policy’s occupancy distribution be covered by the offline data, making it weaker than global coverage.The comparator is characterized by d^π⋆_P(s,a)/ρ(s,a) ≤ C.

4 Pessimistic Model-based Offline RL

CPPO uses constrained pessimistic optimization over a realizable model class to obtain PAC guarantees under partial coverage. Its guarantees extend to unrestricted policy classes, while likelihood-ratio constraints and structural model assumptions support broader function classes and refined coverage measures.

  • General CPPO framework: CPPO takes a realizable model class and constructs a pessimistic policy-evaluation or optimization procedure using constraints around an estimated model.The framework includes total-variation and likelihood-ratio constrained variants.
  • General CPPO framework: Pessimism makes the estimated value a lower bound on the true value for every policy, leaving the final error dependent on the comparator policy’s concentrability coefficient.The resulting analysis evaluates the comparator rather than requiring coverage of every policy.
  • Coverage measures: The model-based concentrability coefficient adaptively measures mismatch between offline data and comparator occupancy through the model class and can be bounded by density-ratio concentrability.For specific settings, the coefficient can become a relative condition number or other structural quantity.
  • Guarantees under partial coverage: Under realizability and finite concentrability, CPPO provides PAC guarantees against any feasible comparator policy, including policies from an unrestricted class and history-dependent policies.The result is presented as the first PAC guarantee for general MDPs under partial coverage with only a realizable hypothesis class.
  • General CPPO framework: The version space is built around the maximum-likelihood estimator so that the true model belongs to it with high probability.Pessimistic evaluation minimizes policy value over models in this version space.
  • Likelihood-ratio constraints and infinite classes: CPPO-LR retains the statistical guarantee of CPPO-TV, and its infinite-class analysis uses bracketing numbers to quantify model-class complexity.The likelihood-ratio formulation can require only bracketing-number calculations for models.
  • Comparison with model-free approaches: A model-free comparison incurs ln |Π| in the suboptimality conversion, restricting the policy class, whereas CPPO can use unrestricted policies under its model-based guarantee.This distinction is central when the offline data covers a strong history-dependent policy but not the optimal policy.

5 Examples with Refined Concentrability Coefficients

The paper specializes CPPO across tabular, linear mixture, low-rank, and factored MDPs, refining partial-coverage measures using each setting’s structure. These refinements yield PAC guarantees whose complexity can depend on feature geometry or factorization rather than unrestricted state-space coverage.

  • 5.1 Tabular MDPs: In tabular MDPs, the model-based concentrability coefficient equals the density-ratio coefficient Cπ∗,∞.This is identified as the appropriate quantity for small tabular MDPs.
  • 5.2 Linear Mixture MDPs: Linear mixture MDPs admit a newly introduced concentrability coefficient measured on integrated feature vectors, yielding a PAC guarantee under partial coverage.For parametric linear MDPs, the coefficient can be replaced by a relative condition number based on the feature representation.
  • 5.2 Linear Mixture MDPs: The linear-mixture relative condition numbers are tighter than density-ratio concentrability coefficients and can remain finite even when the density ratio is infinite.For one-hot features, they reduce to the density-ratio coefficient.
  • 5.3 Low-rank MDPs with Representation Learning: For low-rank MDPs with unknown representations, CPPO refines partial coverage to a relative condition number defined by the unknown true representation φ∗.The guarantee applies when C̄π∗,φ⋆ is finite and is distribution-dependent through rank(Σρ).
  • 5.4 Factored MDPs: For factored MDPs, the refined coefficient uses density ratios associated with individual factors, and the resulting sub-optimality gap scales polynomially with the factored complexity L rather than |S|.The factorized coefficient C̈π∗ is expected to be much smaller than the unfactored Cπ∗.

6 Constrained Pessimistic Model-Based Policy Optimization for KNRs

The KNR instantiation of CPPO yields tighter partial-coverage guarantees, including distribution-dependent bounds for finite- and infinite-dimensional feature representations. The RKHS extension uses regularized kernel estimation and an offline-distribution-dependent effective dimension.

  • KNR guarantees: CPPO is applied to KNRs to obtain tight guarantees under partial coverage.The framework is presented as broadly applicable to kernelized nonlinear regulators.
  • Finite-dimensional KNRs: Regularized MLE estimates the KNR transition parameter before constrained policy optimization.The estimator uses a Frobenius-norm regularization formulation.
  • Finite-dimensional KNRs: The KNR guarantee can depend on rank[Σρ] rather than feature dimension d, remaining valid when offline data concentrates on a low-dimensional subspace.The condition does not require Σρ to be full-rank.
  • RKHS KNRs: For RKHS KNRs, kernel ridge regression learns the transition function and CPPO retains a valid PAC guarantee under partial coverage.The RKHS construction uses a regularized MLE and an effective-dimension analysis.
  • RKHS KNRs: The RKHS effective dimension extends rank[Σρ] to infinite-dimensional models and is defined by the offline distribution.Its eigenvalues and eigenfunctions are determined using the offline distribution ρ.

7 Constrained Pessimistic Model-based Policy Optimization for (nonparametric) linear MDPs

The paper modifies CPPO to handle nonparametric linear MDPs, where standard MLE is unavailable because the transition measure is nonparametric. The resulting model-based method retains PAC guarantees under stated assumptions, but its bound depends on the policy-class size.

  • Motivation: Standard CPPO cannot directly handle the nonparametric linear MDP formulation because MLE is no longer applicable.The paper addresses this limitation with a modification based on alternative model-learning objectives.
  • Model estimation: The modified approach uses witness functions and regularized least squares to estimate transition expectations.The estimator targets integrals of the transition measure against witness functions rather than directly estimating the measure.
  • Model estimation: The witness-function class is chosen to include state-value functions induced by models in the model class.The resulting estimator need not itself belong to the model class.
  • Guarantee: The modified CPPO algorithm provides a PAC bound for nonparametric linear MDPs under norm and boundedness assumptions.The theorem applies uniformly over comparator policies in the specified policy class.
  • Limitation: Theorem 6 incurs ln(|Π|), requiring a restricted policy class and potentially yielding weaker bounds than model-free alternatives in this setting.The paper contrasts this dependence with models where CPPO does not incur ln(|Π|).

8 Bayesian Offline RL: Policy Optimization via Posterior Sampling

The Bayesian extension replaces explicit pessimism with posterior sampling combined with incremental policy optimization. Fresh model samples make persistent exploitation of errors in a single fitted model difficult, while the analysis gives Bayesian suboptimality guarantees under partial coverage.

  • Algorithm: PS-PO updates the policy incrementally using a fresh model sampled from the posterior at every iteration.The policy update is an exponentiated-advantage update with learning rate η.
  • Algorithm: Posterior sampling prevents policy optimization from consistently exploiting errors in one model outside the data-covered region.Sampled models agree in well-covered regions but may disagree where offline data are sparse.
  • Analysis: Partial coverage is characterized through density-ratio and relative-condition quantities averaged over the prior distribution.The relevant quantities are required to be bounded by constants.
  • Analysis: The Bayesian analysis decomposes suboptimality using a data-dependent lower-confidence function L(π; D).The function is bounded below by policy value with high probability under the sampled ground-truth model.
  • Guarantees: Theorem 7 establishes Bayesian sumoptimality under partial coverage, and PS-PO analysis bounds per-iteration regret using the same framework.The analysis identifies a dominant partial-coverage term after sufficiently many iterations.
  • Guarantees: The framework yields specialized posterior-sampling corollaries for general function classes, tabular, linear-mixture, KNR, and low-rank MDPs.These corollaries instantiate the Bayesian partial-coverage guarantee across several model families.

9 Conclusion

The paper concludes that realizability and partial coverage suffice for model-based offline RL to compete with covered policies, including history-dependent ones. It also identifies computational tractability and policy-class dependence as important scope boundaries.

  • Main conclusion: Realizability plus partial coverage suffices for model-based offline RL to compete with covered policies, including history-dependent policies.This contrasts with model-free approaches that often require Bellman completeness and restrict comparator policies.
  • Computational scope: The CPPO minimax objective fits robust-MDP planning, enabling approximate solution methods beyond the tabular setting.The paper connects the optimization to robust Bellman, value-iteration, and policy-iteration methods.

A Comparison to Xie et al. (2021)

The comparison shows that directly applying Xie et al. (2021) incurs dependence on the policy class and cannot match the unrestricted-policy guarantee established here. The authors also identify why another stochastic-policy result is inapplicable except under stronger structural conditions.

  • Comparison with Xie et al. (2021): The comparison theorem assumes realizability of the policy-induced Q-functions in the chosen function class and provides a PAC guarantee for any comparator policy in Π.The theorem is obtained by extending the model-free result and converting it to a model-based result under partial coverage.
  • Comparison with Xie et al. (2021): The direct application of Xie et al. (2021) yields a bound whose complexity includes |Π| and competes only with policies restricted to Π.The reduction constructs Q-function and discriminator classes with |F| = |Π||M| and |G| = |Π|2|M|2.
  • Comparison with Xie et al. (2021): The presented algorithm instead works for the unrestricted policy class Π, including potentially history-dependent policies.The paper contrasts this with the restricted comparator class in the direct application.
  • Comparison with Xie et al. (2021): The NPG results of Xie et al. (2021) are not applicable because their comparator policy must satisfy a Bellman-completeness condition that fails after the model-to-Q-function conversion.The paper notes a linear Bellman-complete MDP as an exception where stochastic policies satisfy the required condition.
  • Proof strategy: The proof constructs a constrained model version space and controls model error through MLE generalization bounds, concentration, and distribution-shift analysis.The argument first establishes inclusion of P⋆ in the constrained set, then bounds transition error for every constrained model before applying a simulation argument.

B.2 Proofs for general function approximation for CPPO-LR with infinite hypothesis class (Proof of Theorem 3)

The proof establishes CPPO-LR’s guarantee for infinite model classes by combining bracketing arguments with likelihood-ratio control and a simulation-based treatment of distribution shift.

  • Model error: For every constrained model, the expected squared total-variation error is bounded by an empirical likelihood-ratio term plus a bracketing-complexity term.The bound includes 2ED[log(P⋆(s′ | s, a)/P(s′ | s, a))] and a term proportional to n^-1 log(c1N[](ϵ, M, ∥· ∥∞/δ).
  • Bracketing and concentration: The proof uses an ϵ-bracket of the model class and Cramer-Chernoff bounds to control likelihood ratios uniformly over models.The bracket width is set to ϵ = 1/(nι(S)), followed by Markov and union-bound arguments.
  • Pessimism: P⋆ belongs to the pessimistic constrained set with high probability, providing the first step of the proof.This inclusion follows from the bracketing-based likelihood-ratio bound.
  • Distribution shift: The final guarantee follows by combining the constrained-model error bound with a simulation lemma that accounts for distribution shift.The proof separates the pessimism, model-error, and distribution-shift steps before combining them for any comparator policy.

C.1 Proofs for Tabular MDPs (Proof of Corollary 1)

The tabular proof constructs finite approximations of transition models, transfers empirical control to the offline state-action distribution, and then bounds policy-value error under distribution shift.

  • Finite approximation: The proof constructs an ϵ-net over transition simplices and forms a finite model class covering every possible transition model.With ϵ = 1/n, the covering number is bounded using simplex covering results.
  • Finite approximation: The set M′ contains models in the pessimistic class that are within ϵ of some model in the constrained set MD.Figure 1 illustrates MD, M′, and the surrounding approximation set ¯M.
  • Pessimism and model error: The proof shows that the true model belongs to the constrained set and that every model in it has controlled transition error under the offline distribution.These are the first two steps before handling distribution shift.
  • Distribution shift: The final step uses feature covariance and a one-step-back inequality to translate offline-distribution control into control under the comparator policy.The argument introduces Σ = nE(s,a)∼ρ[φ⋆(s, a)φ⋆⊤(s, a)] + λI and applies a simulation lemma.
  • Factored extension: For factored models, the proof applies analogous concentration and total-variation arguments factor by factor before combining them into the final bound.The construction uses individual factor transition terms and a union bound over factors.

D.1 Proofs for Finite-Dimensional KNRs (Proof of Corollary 3)

The finite-dimensional KNR proof bounds pessimistic parameter error through covariance-based concentration and converts that error into transition and policy-performance guarantees.

  • Pessimistic parameter set: The proof first establishes that the true parameter belongs to the pessimistic parameter set with high probability.This is followed by a uniform bound for every parameter in that set.
  • Parameter error: For every parameter in the constrained set, the proof controls estimation error in the empirical covariance norm.The argument combines concentration results with bounds from Chang et al. (2021).
  • Transition error: Squared total variation between transition models is related to the feature-weight error, allowing covariance control to yield transition-error control.The proof uses TV(P(W)(· | s, a), P(W⋆)(· | s, a))2 = Θ(∥(W −W⋆)φ(s, a)∥2 2).
  • Final guarantee: The final result combines the covariance, concentration, and transition-error bounds to complete the KNR corollary.The proof concludes after applying the corresponding results for the auxiliary quantities g and W.

E Missing Proofs in Section 7

The section collects omitted proofs built around three steps: pessimism, algorithmic construction, and distribution shift. It also states simulation, estimation, structural, and concentration lemmas used to establish the bounds.

  • Main proof structure: The main proof proceeds through pessimism, an algorithm-construction step, and a distribution-shift step before concluding the bound.The proof conditions on high-probability events and invokes results from prior work in the pessimism step.
  • Posterior analysis: The proof tracks posterior distributions over the true model and sampled models conditional on the dataset.It identifies the posterior of the true model given the dataset with β′ and uses the same posterior for the sampled model.
  • Simulation and distribution shift: The analysis uses a simulation lemma to relate transition-model discrepancies to policy evaluation quantities.The lemma considers two transition models and an arbitrary policy, with total variation appearing in the resulting bounds.
  • Model-estimation lemmas: Supporting lemmas provide MLE guarantees for general, tabular, and KNR model classes, alongside a Gaussian-distance bound.These results control transition estimation error, while the Gaussian lemma is derived using Pinsker’s inequality and closed-form KL divergence.
  • Structural model lemmas: For linear mixture and linear MDPs, parameter differences control transition probabilities, total variation, and value-function discrepancies.The stated bounds rely on bounded feature representations and specialize the mixture representation through a Kronecker product.
  • Concentration and shift control: The appendix also invokes a distribution-shift lemma and functional Bernstein inequalities to complete high-probability generalization arguments.Several conclusions are obtained by conditioning on events with probability at least 1 −δ and then taking δ = 1/n.
Loading 2107.06226v4…