Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
Authors: Masatoshi Uehara
Wen Sun
Venue: ICLR 2022 Poster (2022)
Keywords: Reinforcement learning Theory
Offline reinforcement learning
PAC Bounds

Abstract: 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 models 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 covered by the offline data. We then demonstrate that this algorithmic framework can be applied to many specialized Markov Decision Processes where the 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.

Published as a conference paper at ICLR 2022
PESSIMISTIC MODEL-BASED OFFLINE REINFORCE- MENT LEARNING UNDER PARTIAL COVERAGE
Masatoshi Uehara, Wen Sun Department of Computer Science Cornell University, Ithaca, NY 14850, USA (mu223, ws455) cornell edu
ABSTRACT
We study model-based offline Reinforcement Learning with general function ap- proximation without full coverage assumption on the offline data distribution. We present an algorithm named Constrained Pessimistic Policy Optimization (CPPO) which leverages 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 the flexibility of CPPO: it can be seamlessly applied to many specialized Markov Decision Processes where additional structural assumptions 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 ratios associated with individual factors.
INTRODUCTION
Offline Reinforcement Learning (RL) is one of the important areas RL where the learner is pre- sented with static dataset consisting of transition-related information (state, action, reward, and next state) collected by some behavior policy, and needs to learn purely from the offline data without any future online interaction with the environment. Offline RL is used in number of applications where online random experimentation is costly or dangerous such as health care (Kosorok & Laber, 2019), digital marketing (Chen et al. 2019) and robotics (Levine et al. 2020).
The performance guarantees of offline RL often rely on two quantities: the coverage of the offline data and the property of the function approximation used in the algorithms. For instance, for the classic Fitte---ittrraioon (FQI) algorithm (Ernst et al. 2005 Munos & Szepesvári, 2008). it requires (a) full coverage in the offline data, i.e., max(e..) d (8, (8,a)/ p(s, < oo for any stochastic policies non-Mar Mon-Markovian policies, where d (s, a) is state-action occupancy
including history-dependeer distribution of a policy π and p(s, a) is an offline distribution, (b) realizability in a Q function class, i.e., the optimal Q function belongs the function class, and (c) Bellman completeness, i.e., applying the Bellman operator on any function in the function class results in a new function that also belongs to the function class (see the first row in Table []. Among these three assumptions, the full coverage and the Bellman completeness are particularly strong. The full coverage means that the behavior policy needs to be exploratory enough, although figuring out an exploratory policy itself is extremely hard problem for large-scale MDPs. The Bellman completeness assumption does not have a monotonie property, i.e., even starting with a function class that originally permits Bellman completeness, slightly increasing the capacity of the function class could result in new class that does not have Bellman completeness anymore. Thus, we aim to relax the assumptions on the offline data and the function class. Particularly, are interested in the following question:
Given realizable function class and offline distribution that only provides partial coverage, can we learn a policy that able to compete with any policy that is covered by the offline distribution?
We study this question from model-bbsed learning perspective and provide an affirmative answer to the question. More specifically, different from FQI, we start with a realizable model class, i.e.,
the ground truth transition falls into the model class. We further abandon the strong full coverage assumption, and instead, assume partial coverage which means the offline data distribution only covers state-action distribution of some high-quality comparator policy n¹ (n" is not necessarily

---

Published as a conference paper at ICLR 2022
Methods
Type
Coverage
Additional Structures
FQI (Munos& & Szepesvári
2008
F
Full: máx, plaa
<. Vi
Bellman complete
Minimax Way (eehara el al.
2020
F
Full: maxx, glea) < oo, Vr
(ee)
Realizahility in density ratio
Duan et al.
2020
F
Full: Es Ex (0.000000)))))))) PSD
Linear Bellman complete
Xie & Jiang 2020
F
Full: m.
None
1iu et
2020
Partial' max,0 plam)
(aa)
<.
Bellman/ Policy class complete
Rashidincjad ct
2021
Partial: maX,a slas)
(a()) 4:00
Tabular MDP
Purtial":: max, "Byc-r" (lsn)ttea))) a
Jin al.
2020b
Zhang et al.
2021b
F
Linear MDP Jin al. 2020a
1/-T!l'e" Purtial: max, 1/-7/12
Xie al.
2021
F
Bellman complete
E. Kyuee - (isoliaaa) a
Zanette al.
2021
F
Purtial: maxx, v (ooo
Linear Bellinan complete
Batch Ross Bagnell
2012
Full: max,a plaaa < Co,
None
Milo Chang et al
2021
B
Partial: max, Rugggdlea))dlr
"",, saaee Haal)stea))
KNR / GP
Purtial'!1: max,,
2" Txal <.
None
Purtial: max, K. (l
Linear MDP /KNR//CC
CPPO (Ours)
Partial: mAN, Beaen (hale"
(eaa'ss
< 0o
Low-rank MDP (unknown d*)
Table 1: Comparison among existing works regarding their type, coverage, and additional structural assumptions on the function class or MDPs. Typee F means model-free and type B means model- based. Partial coverage means P hat the offline distribution p covers a state-action distribution of comparator policy n². f means it assumes an accurate density estimator for p(s, a). tt means although the analysis in Jin et al. (2020a) is done under the full coverage for linear MDPs, based on the argument (Zhang al. 20211), we can show the algorithm has the PAC guarantee under partial coverage in terms of the relative condition number for linear MDPs, t 1 i means that we can refine it to more adaptive quantity using the model class (i.e., Definition I All the methods in the table
require realizability in the function class.
the optimal policy, and n² could be non-Markovian), i.e., maxs, d' (s, (s,()) < co, We design an algorithm- - Constrained Pessimistic Policy Optimization (CPPO), which can learn a policy that as good as any comparator policy π that is covered by the offline data. The fact that CPPO can learn to compete against history-depende data does not cover the optimal policy.
policies is meaningful in offline RL when the offline
While one could assume density ratio based concentrability coefficient (max d (8, a) p(s, a)) to be under control for small size MDPs, in large-scale MDPs (e.g. continuous state space), the den- sity ratio could quickly become an extremely large quantity which makes the performance guarantee vacuous. When applying CPPO to MDPs with additional structural assumptions, we can seamlessly refine the density ratio based concentrability coefficient to more natural and tighter quantities. No- tably, we consider the offline representation learning setting where the underlying MDPs permit low-rank structure (unlikely linear MDPs (Jin et al.) 2020aa Yang & Wang 2020), we do not assume the ground truth state-action feature representation o² is known, and instead we need to learn Φ*) and we show that we can refine the density ratio to a relative condition number that is defined us- ing the unknown true state-action feature representation d* Intuitively this means that long as there exists a high-quality comparator policy that only visits the subspace (defined using the true representation Φ) that is covered by the offline data, CPPO can compete against such policy, even without knowing the true 3² Such bounded relative condition number assumption is much weaker than the bounded density ratio assumption While the concept of relative condition number was originally introduced in the online RL setting [e.g..Agaawwa et al. (2020c a) with a known linear feature Φ). and later was introduced in offline RL (Zhang et al. (202 Ib); Chang al. (202T). these prior works all rely on the fact that the feature representation is known to the learner priori (see Table for the comparison). Another interesting example is factored MDPs (Kearns Koller, 1999) where we show CPPO refines the density ratios to be density ratio associated with individual factors, which leverages the factored structure and is provably tighter. We also give examples on linear MDPs (Yang& & Wang 2020), kernelized nonlinear regulator (KNRs) (Kakade et al. 2020). where we again show that CPPO enjoys problem specific quantities for measuring the coverage.
Our contributions. Our contributions are two folds, which we summarize below:
'Strictly speaking. in Jin et al. 2020bb: Rashidinejad et al. 2021 a comparator policy is restricted to the
optimal policy. In [Chang al. (2021 Zanette et al. (2021) Xie al. (20T)) and CPPO, comparator policy be any policy.
2

---

Published as a conference paper at ICLR 2022
1. We show that in the model-based setting, realizabilitty and partial coverage is enough to learn a high-quality comparator policy (Theorem I). Notably, (1) this result holds for any MDPs with realizable model classes, (2) we can compete against even history-dependen policies. This is in sharp contrast to the state-of-art provable model-free offline RI. results: see Ta page detailed comparisons prior works.
2. Under additional structural assumptions (e.g., KNRs, linear MDPs YYang & Wang 2020),
linear mixture MDPs (Ayoub et al. 2020), low-rank MDPs, factored MDPs), we show that we can seamlessly refine the density ratio based concentrability coefficients to problem spe- cific quantities. This flexibility to adapt to problem specific coverage measuring quantities is in sharp contrast to other model-free offline RL algorithms such as minimax based ap- proaches (Uehara et al. (2200) which, to the best of our knowledge, cannot leverage MDP's structures (e.g. linear MDPs) to refine its density ratio based concentrability coefficients.
While we focus on the model-based setting and have demonstrated advantages of our approach over model-free ones (i.e., no more Bellman completeness assumption on function classes, being able to compete against a larger pool of policies, and the ability to seamlessly adapt to problem dependent structures), it worth noting that realizability in the model-based setting usually considered stronger than the one in the model-free setting. On the empirical side, model-based offline RI. algorithms are the state-of-art (c.g.. Yu et al. (idd))(Kidambii et al. (0t0)sMatssushmm et al. (2020); Cang et al. 20211; Chang et al. (202 ). Our theoretical results provide a sharp contrast between model-based and model-free approaches in offline RL.
RELATED WORK
We discuss two families of related works of offline RL. In Appendix C we discuss related works about representation learning in RI..
Insufficient coverage of the dataset due to the lack of online exploration is known as the main challenge in offline RL (Wang et al.) 2020). To deal with this problem, number of methods have been recently proposed from both model-free (Wu et al. 2019. Touati et al. 2020;
Kumar et al.) Liu et al. 2020 Rezaeifar et al. 2021 Fujimoto et al. 2019 Fakoor et al. 2021 Ghasemipour
2020
et al. 2021; Buckman et al. (2200) and model- perspectives (Yu et al., 2020; Kidambi et al., 2020
Matsushima et al. 2020 Yin et al. 2021). More or less, their methods rely on the idea of pessimism and its variants in the sense that the learned policy can avoid uncertain regions not covered by offline data. As a theoretical side, Munos & Szepesvári (2008); Duan et al.] (2020) 2021]: Fan et al. (2020) proved FQI has PAC (probably approximately correct) guarantee under realizability, the global coverage, and Bellman completeness conditions. Other offline model-free
RL methods such as minimax offline RL methods also require realizability and the global coverage
(Chen & Jang 2019 Antos et al.) 2008: Uehara et al. 2021 Duan et al.) 2021 Zhang et al. 2020
Nachum et al. 2019 J. Recently, by leveraging the aforementioned the pessimism idea, Jin et al.
(2020a): Rajaraman et al. (2020) showed that pessimistic FQI can be applied to partial coverage
setting for linear and tabular MDPs. Comparing to their works, our analysis focuses on model- based approaches with general function approximation. The offline model-based method is known to have a PAC guarantee under the realizability and the global coverage (Ross & Bagnell, 2012 Chen & Jiang 2019). As the most closely related work, Chang al. (021) proved model-based method with an additional penalty term can weaken the assumption from the global coverage to the partial coverage for structured MDPs such as KNRs and Gaussian Processes models (Deisenroth & Rasmussen| 2011). In this work, we consider arbitrary MDPs with a realizable model class and aim for PAC bounds under a partial coverage condition.
3 PRELIMINARIES
We consider a Markov Decision process (MDP) M = (S,A, P. r, do) where P: P:SxA- A(S) is the transition, r: S x A + [0, 1] is the reward function, y E 10, is the discount factor, and do E ASS) is the initial state distribution. A policy π maps from state (or history) to distribution over actions. Given policy and a transition distribution P. V denotes the expected cumulative reward of x under P,dg and r. Similarly, Q7 : S x A - A. : S x A - R are a Q- function and udvantage-function under P and и. Given transition P. we denote ((P) as the optimal policy associated with model P under reward r. We also denote dp C A(S x A) as the
average state-action distribution of π under the transition model P. i.e, d7. (1 7) E 7 ddd
3

---

Published as a conference paper at ICLR 2022
where di. A(S x A) is the distribution of (st, under and P at a time-step t. We denote the true transition distribution Pt, which we do not know in advance. For simplicity, we suppose known. The extension to the unknown reward is straightforward.
In the offline RL setting, we have an offline distribution E A(S x A), and an offline dataset Ji=1 which is sampled in the following way: 8, ~ p,r r(s,a) & ~ (*(s,,, We hope to obtaín TT( (P*) = arg m Vp. from this offline dataset without any further interaction with the environment. We often denote ED [f a, a,) = 1/n ((.,""))))) [(s a, s"). Our goal is to construct offline RL algorithm Alg, which maps from D to so that the subopti- mality gap V VAAl(() for any comparator policy x' E IT is minimized, where IT in this work can be an unrestricted policy class (e.g.. including non-Markovian policies). Hereafter, c, C,, are always universal constants.
D D= (8(0), (0 r((), 8/()
Partial coverage. Throughout this work, we do not assume p has global coverage. The global cov- crage in this work means that the density ratio based concentrability coefficient dī. (s, a)/p(s, p(s, a) is upper-bounded by some constant C' E -t for all polices E 11, or the feature covariance matrix corresponding to the offline distribution E, a) ())(())((()))) a) (ó E S x A - R is a feature representation) is full rank and has a non-zero minimum eigenvalue, which assumptions in offline RL (Munos] 2005: Antos et al. 2008 Chen & Jiang 2019) Duan et al.. 2020). Under the full coverage, they show the output policy can compete with the globally optimal policy T (P*). However, this assumption may not be true in practice as computing an exploratory policy itself is a challenging task for large-scale RL problems. Instead, we are interested in the partial a)
commonly used
coverage setting such d (s,a)/ p(s, a) I C, which means the aate-action occupancy measure under some comparator policy xt" is covered by the offline dataset. We want to design an algorithm that can compete against any policy x" that is covered by the offline data. This assumption is much weaker than the global coverage.
PESSIMISTIC MODEL BASED OFFLINE RL
We first introduce a general model-based algorithm that has a PAC guarantee of the suboptimality gap under partial coverage defined with newly introduced concentrability coefficient. The algo- rithm takes a realizable model class as input and outputs a policy that is as good as any comparator policy that is covered by the offline data in the sense of the bounded concentrability coefficient.
Our algorithm, Construined Pessimistic Policy Optimization (CPPO) (Algorithm 1). takes a realiz- able hypothesis class M (with Pa E .M) consisting of [M| candidate models as imput, computes the maximum likelihood estimator (MLE) PMILE using the given offline data D = {s, a, s'). It then forms min- objective subject to constraint. The min-max objective introduces pessimism via searching for the least favorable model P (in terms of its policy's 's value VP) that is feasible with re- spect to the constraint. We can also express the constrained optimization procedure using version space MD and a policy optimization procedure defined below:
max min VP,, where Mp {P P E M, (V(PMEE()ss)) P(-ss, s <t). (I) FEll PEM
where TV(P1, P2) is total variation (TV) distance between two distributions P1 and Ps. The version space MD contains models that are not far away from PALLE in terms of the average TV distance under D. The version space is constructed such that with high probability pa E MD.
Below we state the algorithm's performance guarantee. Assuming for now that P E MD holds with high probability, then, v= = minppep Vă is a pessimistic policy evaluation estimator, which satisfies vx < Vz. for all π E TT. Using the idea of pessimism, we have the following observation:
Vp Vp. = Vp. 8" + Vaa - vp. S VF. Va + V
V$..
< Vp.
V**
where the first inequality uses Ω = arg max E and the second inequality uses 10- < VE. for all II. Thus, the final error only incurs the policy evaluation error for the comparator policy n², which leads to the error only depending on the concentrability coefficient for the comparator policy.
We define the following new concentrability coefficient that uses the model class M
4

---

Published as a conference paper at ICLR 2022
Algorithm Constrained Pessimistic Policy Optimization (CPPO)
Require: Models M, dataset D, parameter Ç. policy class II (note II could be unrestricted)
2: Obtain the estimator PMIE by MLE: PMI.E. = arg max PaM ED[lu P(s' s.a)].
3: Constrained policy optimization:
arg ma minreM Vp, s.t., ED [TV(PMu((ss.), S.
4: Return
Definition 1 (Model-based Concentrability Coefficient). For comparator policy n², define the concentrability coefficient C follows:
ap (EV) c = suppieM B (TPP)
The following theorem shows CPPO learns policy that competes against x' when Ct- < co.
Theorem 1 (PAC Bound for CPPO with general function class), Assume p ... We set & 1t unrestricted policy class containing non-Markovian policies),
[n(ca|MM/88) Then, with probability 1 - 5, for any comparator policy x² IT (II can be the
C ln(es)MM55)
V - - cc(1-))))))) (1-11-)--
To the best of our knowledge, this is the first algorithm that achieves a PAC guarantee for any MDPs under the partial coverage assumption C_ < oo with only a realizable hypothesis class. We emphasize that the inequality in the above uniformly holds for all policies with probability 1 5 including history-dependent non-Markovian policies (see Remark 2}. Note that the ability to compete against Mon-Markovian policies in offline RL is meaningful when the offline data does not cover the optimal policy x* (i.e., there could be a high-quality history-dependent policy that covered by the offline data against which want to compete). In model-free approaches, this type of result generally cannot be obtained. Indeed, the model-free approach from Xie et al. (202T) requires to be a restricted Markovian policy class, since their bound contains poly poly(In([II)) dependence. For the detailed discussion, refer to Remark
The quantity C2,- adaptively captures the discrepancy between the offline data and the state-action occupancy measure under a comparator policy s* depending on the model class M. For example, C.- can be reduced to relative condition number in KNRs. Besides, it is always upper bounded by the density ratio based concentrability coefficient:
C == (uP().a)
(s.a) p(s,a)
One extreme case is that functions in M are all the same, which implies C regardless.
Theorem I consider the case where the hypothesis class M is finite. When the hypothesis class is infintte we can still obtain the PAC guarantee by utilizing the generalized result in(Section for any realizable model class with valid statistical complexity (e.g., localized Rademacher complexity).
Prior works that achieve PAC guarantees with only realizable model classes rely on much stronger global coverage sup, Cr < oo (Chen & Jiang, 2019). Even when the comparator policy the optimal policy T TPP*), the partial coverage condition Cz(P*),oe < is weaker. Existing pessimistic model-based algorithms and their theoretical results (Chang et al.) (002)) often assume that a point-wise model uncertainty measure is given by-product of model fitting, which limits the applicability to special linear models such as KNRs/GPs. CPPO can work for any MDPs with the realizable function class having a valid statistical complexity such that the MLE properly works.
Remark (Comparison to the model-free approach from Xie et al. (202I); Zanette et al. (2021)
). Xie et al. (202l) study the model-free setting where the function class @ models Q functions assumed be Bellman complete for any Markovian policy in II. While directly comparing model- based approaches to model-free approaches is hard as they use different inductive biases in function classes, we can leverage the approach from Chen & Jiang 2019 Corollary 6) to convert model
5

---

Published as a conference paper at ICLR 2022
class M to a pair of Q and II class. Specifically, we can convert model class M pair of Q class and II class such that Q will be realizable and also Bellman complete with respect to all π E II. After such such conversion from the model-base
setting the model-free setting, running the algorithu from Xie al. 202//) using Q and II achieves Vp. VB. VC [n[M)T//))) Vx II, where C is some concentrability coefficient. For the detailed derivation, we refer readers to Appendix D Since the suboptimality gap from such conversion incurs log [II|, a policy class II cannot be too large. Especially, unlike our results, it cannol take the unrestricted policy class as II. This restriction cannot be fixed even if we use natural policy gradient (NPG) algorithms unless models have special structures (Xie et al. 2021 Zanette et al. 2021). The details are given in Section D
Thus, theorem indicates two advantages of model-based approaches: (1) realizability in function class is enough to ensure a PAC guarantee under a partial coverage condition, (2) it can compete Maraovkovi policies,
against larger pool of candidate policies including history-dependent which is a meaningful property when the offline data does not cover the globally optimal policy. Next, we demonstrate another key advantage of our approach which is its flexibility to be seam- lessly applied to MDPs with special structures.
5 EXAMPLES WITH REFINED CONCENTRABILITY COEFFICIENTS
In the previous section, our results apply to any MDP as long as its true transition belongs to function class M. In this section, we consider several concrete MDPs with additional structural conditions. We show that by leveraging the additional structural conditions, we can refine the model- based concentrability coefficient more natural quantities. The examples that we discuss here are: (1) linear mixture MDPs which generalize linear MDPs from Yang & Wangl (2020) and tabular MDPs, (2) KNRs which generalize LQRs, (3) low-rank MDPs, and (4) factored MDPs.
Before proceeding, we clarify CPPO cannot capture linear MDPs in Jin et al. (2020a) that is differ- ent from the one (Yang & Wang| 2020) we use, and linear Bellman-comples
MDPs (Duan et al.) 2020) without any modification since MLE-based model learning is no longer applicable to them. However, other objective functions for learning models could be applied to these models (e.g., see
the nonparametric model- based learning approach from Lykouris al. (2021): Neu & Pike-Burke 2020) in the online setting), which we leave it as a future work.
5.1 TABULAR MDPS AND LINEAR MIXTURE MDPS
Tabular MDPs Tabular MDPs are MDPs where the state and action spaces are finite. Although the corresponding hypothesis class for tabular MDPs is infinite, we can still run MLE, that is, estimating pa by the empirical distribution. Then, Algorithm I has the following guarantee.
Corollary (PAC bound for tabular MDP). We set E bility 1 for all nT E II,
c1
Then with proba-
VF. - VF. S co((1 ca(11-))
1 |l S SlAA)e,/5)
= (P: P(.ss, a) E ASS), Vs a). the model-based concentrability coefficient in Detinition is equal to the density ratio based concentrability coefficient Car,,o which is the right quantity for small-size tabular MDPs.
Here, for tabular MDPs with =
Linear mixture MDPs We define linear mixture MDPs (Ayoub al.
2020 Modi et al. 2020).
Definition 2 (Linear mixture MDPs). Given a feature vector v (S, AA Rd, linear mixture MDP is an MDP where the ground truth transition is p* (5'(1s, [s, a) 0+ (s, 8'), 0* E Rd.
By setting, (sss s') = ((s')(( X o(s a) (8 denotes the Kronecker product), linear mixture MDPs include the following linear MDPs (Yang& & Wang 2020
Definition 3 (Linear MDPs). Linear MDP has P* (* a) == Σ di Eee Mi with :: S + dR and Φ= : S x A + Id2 are known features, and M C Rdixds
1=
We use CPPO to learn linear mixture MDPs. The corresponding M is MMix {0 ((s 0 e Rd, I 0J as s')(ss)) v(s,a)}.

---

Published as a conference paper at ICLR 2022
Given function V. S + R, define the state-action feature indexed by V as vv(s,,)
I (b(s,, a, v') (ss)), we have the following PAC guarantee.
Corollary 2 (PAC bound for linear mixture MDPs). Suppose inlsa,ss P* 8,a) 23 0.
θ {0- ||0||2 I R}. (s,v(s,))le I 1. E S [o, 1] and p MMix We set endln (cmmR//) //n Then, with probability 1 1- for any πt" in 11 (again 11 can be the unrestricted policy class), CPPO outputs policy & such that:
In In (c/nR/0)
Vp. - -V- Vp. c4(11))) =)= VV min(dC) d'Cx mix)
(2)
where the concentrabillity coefficient Ox* mix is defined as:
x Ex Wyz
Ca mix == sup sup PEZp, xERd
x E. D.W 26
with the localized class Zp. == (P: (s.a)) (VV(( s, a), s,a)) S E}. Ep. =
((s.))-llvv (s. (s, J and Exx Ahp Buaaddpi livg (s, v)v (s,
When specializing to linear MDPs, the above bound still holds with Cx. mix being replaced by the relative condition number C..:
x.
-EE.. where E,
Cz. = sup ZERd O.' E,px x
Ex. = Eaa))=a ((()))
This is the first PAC-guarante result in the offline setting under partial coverage CN- mix < 30 for linear mixture MDPs. Cz- mix is newly-introduced concentrability coefficient for linear mixture MDPs. This coefficient is measured on the integrated feature vectors (v a) for V : : + [0, IJ.
Note the class of V is localized, i.e., we consider state-value functions V (s) for all centered around Pa under data distribution P (i.e., P E 2p.). Such localization property ensures that Ox+ ,mix S C. (see Lemma 10 in Section F
Note that these relative condition number based quantifiers are always tighter than the density ratio based concentrability coefficients (i.e., max(C ,x+,mix) S Cz). For the special case where Φ(s.0) a.) is a one-hot encoding vector, then they are reduced to the density ratio based concentrability coefficient. In non-tabular setting, even if when the density ratio is infinite, the relative condition number can be still finite. Intuitively, the bounded relative condition number implies that the offline data covers the subspace that the comparator policy x visits.
> 0 in Corollary 2 is technical condition that allows to calculate the entropy integral of the hypothesis class easily. It can be potentially discarded by a more careful argument following (van de Geer 2000, Chapter 7). The norm assumption ||ty a)ll2 is commonly assumed in the online setting (Zhou et al. 2021).
We remark P* (s'
3 > s,a)
5.2 KERNELIZED NOLINEAR REGULATORS
We consider the example of KNRs in this section. A kernliizdd Nonlinear Regulator (KNR) Kakade al. 2020 is model where the ground truth transition P* (s'ls,, a) is defined as s' = W' - ( a)+e, [O, (I). with ó S x A + Hd being possibly nonlinear feature mapping. We denote the corresponding model on W by P(W). We can apply Algorithm I and obtain its guarantee. ([[[( W*)o(s a) a)l DDerroee al. 2018), Ct. upper-boundee by the relative condition number C...
Especially, since (VWP(W)( s, a), P(W*)( s, a))²
Then, we can also recover the result of Chang et al. (202T) which proposes reward penalty-based pessimistic offline RI. algorithm. The detail is given Section B summary, we can show
V vg. S Se - 7) min RVVR
deC.. In(1+n)
12
where R = rank(2,]] (n(c2/8)) and ds is the dimension of the state.
7

---

Published as a conference paper at ICLR 2022
This implies CPPO can learn policy that can compete against n' with partial coverage CN. Note that the condition Cz- < oo does not require Σ, to be full-rank. Also the bound uses rank instead of d, which means that our bound is distribution dependent and is still valid even when d = 0o as long as the offline data only concentrate on a low-dimensional subspace.
5.3
LOW-RANK MDPS WITH REPRESENTATION LEARNING
We consider the representation learning in offline RL. Following FLAMBE (Agarwal et al., 2020b), study low-rank MDPs but in the offline setting. Note that low-rank MDPs here are more generalized model of the aforementioned linear MDPs (Yang & Wang 2020) since the true feature representation o) in low-rank MDP unknown.
Definition 4 (Low rank MDPs). The ground-truth model P* admits low rank decomposition with dimension d if there exists two embedding functions p" S + Rd x= :8 x A Rd
P* (s 8, s, = μ¹ (s') q" (s, a). Neither y² nor o" is known to the learner.
One interesting special case of low-rank MDP is the following latent variable model (see Agarwal et al. (20205) for more details).
Definition (Latent variable models). There exists a latent space Z along with functions p² Z A(S) and 6² S x A + A(2) s.t. (* s, = Σvez 1² (.1 z)Φ (z 1s s.a).
To tackle representation learning under partial coverage on low-rank MDPs, we setup function classes as follows: given two function classes V/ C + R $ C S x A + Rd (both are re- alizable the sense that μ²" E V and d² E P), we consider a hypothesis class {u(s') TT ((ss())))) μ E L Φ }). Then, CPPO (Algorithm 1) and Theorem still work under this setting, Note that this function class setup is exactly the same as the one from FLAMBE.
Here we show that by leveraging the low-rankness, we can refine the concentrability coefficient to a relative condition number defined by the unknown true representation Φ" We emphasize that this does not depend on the other features. Particularly, given a comparator policy n²,, we define Ox+ ,
x Ex x En
Ox-,o- sup ZERd
Σg- == E saadd o" (s, (s, Ep == Ex (s, (0,
We can show CPPO learns policy that can compete against n² long as Ca. < oc.
Theorem (PAC bound for low-rank MDP). We set & = ai 1n(101101/a/1)
Suppose (a): (lo(s, $ 1, (s, E S A, Vo 4 I p(s)) o(s, a)d(s')= = and (la(s) S Vd. Ap V, v. TD, (b) p(s, a) Cp.. (s) (c) P (s'1ss,
(s') 80 ds'(s, a) for some μ³ E V E T With probability at least 1 1- for all Tt E ll (again 11 can be an unrestricted policy class), CPPO Algorithm 1/ finds such that:
Vp. Vp. I ca W rank (ank(Ep)))))))))))))))))
In [n(12/1/c./66
(1-2)*n Wp- = (max(s,a) x" (ale) mo(a|s)
(3)
To the best of our knowledge, this is the first established PAC result under the partial coverage condition Ox- .a. that our bound in Theorem 2 is distribution dependent, i.e., depends on rank(E,)) rather than the exact rank d. Note that rank(2,) S d, and rank(2,,) could be much smaller than d when the offline distribution only concentrates on a low-dimensional subspace (defined using Φ²). Note that the assumption that Wa < oo does not imply the state-action density ratio Cx is small. Indeed, Wr < oc is much weaker than Cx*,oc < 20.
Wy- oc for low-rank MDPs in the offline setting. We also emphasize
5.4 FACTORED MDPs
The last example we include is the factored MDP (Kears & Koller 1999) defined as follows:
Definition (Factored MDPs). Let E N+ and O being a small finite set. The state space S Od. and for each state s, we denote s|i] E O as the i-th variable of the state s. For each i E [l,... ,d, the parents of i, pa, C. [I...., dl, is the subset of state variables that directly influences i, i.e. the transition is defined as follows:
Vs,a, 8: (='(''s, = = IIL, (p
We will denote S; O1pa,, and given E S. we will have s(pa.) S
8

---

Published as a conference paper at ICLR 2022
Due to the factorization, the transition operator P can be described with = - | many parameters. In contrast, the non-factored transition will need O(1ord) parameters. When Ipa,1 < d'vi it is expected that we can learn this model with lower sample complexity by leveraging the factorization which has been demonstrated in the online setting (Kearns & Koller 1999). We remark a factored MDP is an example where model-based approaches are necessary as neither the optimal policy nor the Q functions are factored (Koller & Parr 2000).
We will slightly modify Algoriihh to take the factorization into consideration. First, we perform MLE for model learning: each factor P. is independently learned via MLE:
Vi E [d], PMLEE = arg max,, (B P ( [i]]s[pa,], a)], P= = II. PMLE,
Next, the constrained policy optimization procedure is defined as
.d). Note that in the above objective, there is no restriction on the policy, i... the arg max operator searches over all possible policies including non-Markovian ones.
म arg max min Vp, s.t., ( 8, a), PM | & (Vi
I==II, P;
To analyze the performance of the above modified CPPO, we introduce a specialized con- centration coefficient for factored MDPs that utilizes the factored structure. We focus on density ratio based concentrability coefficients since a factored MDP with the function class M (P 11, P; P. E S; x A + A(O)), the concentrability coefficient associated with M Definition I] will be reduced to the density ratio. For any n², coefficients for the factored MDP as follows:
we define the concentrability
(p.
Co max
max
je . SEA P(8j.a)
where for 8, E Sy, we denote v(8,, a) = E.
v(s, a) for any distribution v E ASSx
Comparing to Cx,,se defined on the original state space S, here Ca+,oo is defined over each state space Sj associated with each factor Note that when ppa, = (1), [Sj] is exponentially smaller than (S). One can verify that Č=-.co S CT (see Appendix F..7p. where Cx-,so ignores the factored structure and treat S as whole single space. This formally demonstrates the benefit of the factored structure in terms of the coverage condition in offline RL.
With the new definition of the concentrability coefficients, now we ready state the PAC bound of CPPO for factored MDPs. Recall I, -E- I,, L4 = 1+paal
Theorem 3 (PAC bound for factored MDP). We set & = c1
L: ln(L.cdd/8) Then with probability
1 8, CPPO finds a policy स such that for all comparator policy n- (11 can be unrestricted),
Vp. V S cs(1 - 7)- aë, L-a(Led)//
Note that our sub-optimality gap scales polynomially with respect to L, i.e. the complexity of the factored MDP, rather than [S] which can be (exx(d)).
CONCLUSION
We study model-based offline RL with function approximation under partial coverage. We show that for the model-based setting, realizability in function class and partial coverage together are enough learn policy that is comparable to any policies (including history-dependent policies) covered by the offline distribution. Our result demonstrates sharp contrast to model-free offline RL approaches which often require additional structural conditions in the function class (e.g., Bellman completion) and have restrictions on the pool of candidate policies that they can compete against.
Some readers might wonder whether CPPO is computationally efficient. The minimax optimiza- tion problem arg max=em minpe VY fits into framework of planning on robust MDPs (Nilim) & El Ghaoui, 20055 Iyengar 2005). By introducing a robust Bellman equation, they proposed value iteration and policy iteration algorithms, and showed that algorithms are practically tractable in the tabular setting. In the non-tabulan setting, Lim & Autef (2019); Tamar et al. (2014) propose the ex- tension using function approximation. Thus, we can apply their methods approximately solve the minimax optimization problem in a model-free fashion. We leave the formal theoretical justification
when using these approximation planning algorithms as important direction for future work.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
The authors would like to thank Nan Jiang, Tengyang Xie for valuable feedhack.
Masatoshi Ueharra is partially supported by Masason foundation.
REFERENCES
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed ex- ploration for provable policy gradient learning. In Advances in Neural Information Processing Systems, volume 33, pp. 13399-13413 13412, 2020a.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complex- ity and representation learning of low rank mdps. In Advances in Neural Information Processing Systems, volume 33, pp. 20095-20107, 2020b.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxima- tion with policy gradient methods in markov decision processes. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 64 66, 2020c.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 129, 2008.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value- targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed- dataset policy optimization. arXiv preprint vrXiv:2009.06799 2020.
Catherine Cang, Aravind Rajeswaran, Picter Abbeel, and Michael Laskin. Behavioral priors and dynamics models: Improving performance and domain transfer in offline rl. arXiv preprint arXiv:2/06.09) 19, 2021.
Jonathan D Chang, Masatoshi Uehara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift in imitation learning via offline data without great coverage. 2021.
Jinglin Chen and Nan Jiang. Information-theorett considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 1042- 1051, 2019.
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed Chi. Top-k off-policy correction for reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on web search and data mining, WSDM '19, pp. 456-464, 2019.
Mare Deisenroth and Carl E Rasmussen. Pilco: A model-based and data-efficient approach to policy search. In Proceedings of the 28th International Conference on machine learning (ICML-11), pp- 465-472. Citeseer, 2011.
Lue Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high- dimensional gaussians. arXiv preprint arXiv:1810.0869) 2018.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear func- tion approximation. In Proceedings of the 37th International Conference on Machine Learning, volume 1 11 of Proceedings of Machine Learning Research, pp. 2701-2709, 2020.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. arXiv preprint arXiv:2103.13883 2021.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
10

---

Published as a conference paper at ICLR 2022
Rasool Fakoor, Jonas Mueller, Pratik Chaudhari, and Alexander J Smola. Continuous doubly strained batch reinforcement learning. arXiv preprint arXiv:2102.09225, 2021.
Jianqing Fan, Zhaoran Wang. Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q- learning. In Pruceedings of the 2nd Conference on Learning for Dynumics and Control, volume 120 of Proceedings of Machine Leurning Reseurch, pp. 486-489, 2020.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 2262-2062. PMLR, 2019.
Seyed Kamyar Seyed Ghasemipour, Dale Schuurmans, and Shixiang Shane Gu. Emaq: Expected- max q-learning operator for simple yet effective offline and online rl. In International Conference on Machine Learning. pp. 1682-3691. PMLR, 2021.
Botao Hao, Yaqi Duan, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Sparse feature selec- tion makes batch reinforcement learning more sample efficient. In International Conference on Machine Learning, pp. 4063-4073. PMLR, 2021.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learn- ing with linear function approximation. Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2137-2143, 2020a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. pessimism provably efficient for offline rl? arXiv preprint arXiv:2012.15085 2020b.
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey Motoya Ohnishi, and Wen Sun. Infor- mation theoretic regret bounds for online nonlinear control. In Advances in Neural Information Processing Systems, volume 33, pp. 15312-15325, 2020.
Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored mdps. IJCAI, volume 16, pp. 740-747, 1999.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 21810-2110 111222.. Curran Associates, Inc., 2020.
Daphne Koller and Ronald Parr. Policy iteration for factored mdps. In Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence, pp. 326-334, 2000.
Michael R. Kosorok and Eric B. Laber. Precision medicine. 6:263-286, 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006.04777 2020.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto-
rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
Shiau Hong Lim and Arnaud Autef. Kernel-based reinforcement learning in robust markov decision processes. In International Conference on Machine Learning, pp. 3973-3981. PMIR, 2019.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off off-policy reinforcement learning without great exploration. In Advances in Neural Information Processing Systems, volume 33, pp. 1264-1274, 2020.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Comuption-robust exploration in episodic reinforcement learning. In Conference on Learning Theory, pp. 3242-3245. PMLR, 2021.
Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu. Deployment- efficient reinforcement learning via model-based offline optimization. ICLR, 2020.
11

---

Published as a conference paper at ICLR 2022
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2022 PMLR, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv: 2102.07035, 2021.
Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the National Confer- ence on Artificial Intelligence, volume 20, pp. 1006. Menlo Park, CA: Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9MMay):8158857, 2008
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074, 2019.
Gergely Neu and Ciara PirkeBurke. A unifying view of optimism in episodic reinforcement learning. arXiv preprint arXiv:2007.01891, 2020.
Chengzhuo Ni, Anru Zhang, Yaqi Duan, and Mengdi Wang. Learning good state and action repre- sentations via tensor decomposition. arXiv preprint arXiv:2105.01136 2021.
Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
Matteo Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Lever- aging good representations in linear contextual bandits. arXiv preprint arXiv:2/04.0378/ 2021.
Nived Rajaraman, Lin F Yang, Jiantao Jiao, and Kannan Ramachandran. Toward the fundamental limits of imitation learning. arXiv preprint arXiv:2009.05990 2020.
Paria Rashidinejad, Banghua Zhu, Cong Ma. Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: tale of pessimism. arXiv preprint arXiv:2103. 2021.
Shideh Rezaeifar, Robert Dadashi. Nino Vieillard, Léonard Hussenot, Olivier Bachem, Olivier Pietquin, and Matthieu Geist. Offline reinforcement learning as anti-exploration. arXiv preprint 106.:23/06.064411,, 2021.
Stéphane Ross and Andrew Bagnell. Agnostic system identification for model-based reinforcement learning. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1905-1912, 2012.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Proceedings of the Thirty-Second Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 2898-2933, 2019.
Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approximation. In International conference on machine learning, pp. 181-189. PMLR, 2014.
Ahmed Touati, Amy Zhang, Joelle Pincau, and Pascal Vincent. Stable policy optimization via off- policy divergence regularization. arXiv preprint arXiv:2003.0 04108, 2020.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off- policy evaluation. In Proceedings of the 37th International Conference on Machine Learning, pp- 9659-9668, 2020.
Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint arXiv:2102.02998) 2021.
12

---

Published as a conference paper at ICLR 2022
S van de Geer. Empirical Processes in M-Estimation. Cambridge Series in Statistical and Proba- bilistic Mathematics. Cambridge University Press, 2000.
Martin J Wainwright. Biigh-Dimensional Statistics A Non-Asymptotic Viewpoint.
Cambridge
University Press, New York, 2019.
Ruosong Wang, Dean P. Foster, and Sham M. Kakade. What are the statistical limits of offline with linear function approximation?. arXiv preprint arXiv:2010.1 1895, 2020.
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv: 2019.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. arXiv preprint arXiv:2008. 2020.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint arXiv:2106.06926, 2021.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. Proceedings of the 37th International Conference on Machine Learning, pp. 17746-10756, 2020.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01748, 2021.
Tianhe Yu, Garrett Thomas. Lantao Yu, Stefano Ermon, James Y Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. Advances Neural Information Processing Systems, volume 33, pp. 14129-14142, 2020.
Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic meth- ods for offline reinforcement learning. arXiv preprint arXiv:2108.0888 2021.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. In International Conference on Learning Representations, 2020.
Weitong Zhang, Jiafan He, Dongruo Zhou, Amy Zhang, and Quanquan Gu. Provably efficient
representation learning in low-rank markov decision processes. arXiv preprint arXiv:2106.11933. 2021a.
Xuezhou Zhang, Yiding Chen, Jerry Zhu, and Wen Sun. Corruption-oobus offline reinforcement learning. arXiv preprint arXiv:2106.06630) 2021b.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532- 4576. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2022
A GENERALIZATION OF THEOREM
We present the generalized version of Theorem when the hypothesis class is infinite. We define the modified function class M:
P+P P 2
PEMB.
H
Given a function class F, let No, d) be the bracketing number of F w.r. the metric d(a. b) given by
[ca(s' s.a) (s,a)) 1/2
d(a, b) = (s
Then, the entropy integral of F is given by
J, max (1e (log (
We also define the localized class of H:
H((6) {h E ((,a)))llh (P(- s, a. (P
ss s 8
where l.(P(.] 8, P* 8, a)) denotes Hellinger distance defined by
0.5 / [VP(s' s,a) - (s | d.())
Based on Theorem 7.4 (van de Geer 2000), the MLE has the following guarantee.
Theorem 4 (MLE guarantee with general function approximation). We take function G(c) [0, 1] + s.t. G(e) Z Jnle, H(e). d] and G(e)/e² is a non-increasing function w.El e. Then, letting &n be a solution to VNE" 2 cG(() w.rl e. With probability 1 6, we have
Bls.a) a) P(. a, s ce {sn. + vlog(c2/0)/n)
We remark that the original guarantee in (van de Geer 2000 is given for the estimation of uncondi- tional distributions. The adaption to the conditional case straightforward. For more details, refer to Section A. Besides, when assume the convexity of the function class, the entropy integral with bracketing (4) can be replaced with the entropy integral with covering number (Wainwright, 2019
Chapter 14).
By using the above notation and the MLE guarantee, we can generalize Theorem
Theorem (Finite sample error bound of CPPO with an infinite hypothesis class). Assume P E M. Let (s)) (P(( 8, a, (* a.). Define
ch +---... In(e/5) n
}
Mi = P: (x,))~ LI(P) 5c
M₂ = P: se G(MM) + In(c/8)
G(M)) El sup
(ED EP)I(())II, G(M2) = El sup
(ED [f)()]]]
PEM1
PEMp
Here, in G(M1) and G(M2), the expectation is taken over the data. We set & cG(Mi) cf3 + In(e/8) Then, for all x² E 11, have
In(c/0)
Vp. Vp. <11 (1-7)_2a1))
( +2
n
14

---

Published as a conference paper at ICLR 2022
This theorem shows once calculate GM1 GM, and En. obtain the tight rate. Im- portantly, GM, and GM2, are upper-bounded by the localized versions of Rademacher complexities based symmetrization argument. Hence, their rates are faster than the ones of the nonlocalized versions.
For example, when M is finite, first have = ///(.MM///8//. Then, from Bernstein's ' inequality (Wainwright, 2019, Exercise 2.8) and union bound, G(M1) is upper-bounded by
G(M1) X
/inlLMcc/0/// x E
Variance term
Union hound
Similarly, from empirical Bernstein's 's inequality,
G(M2) S
MinlMMc//0//n S.
Variance torm
Union bound
Then, we can obtain the result of Theorem
In(IMcc/8)
- (1-)))
Vx* e II.
We stress if we use Hoeffeding's inequality above, we would immediately get the slower rate O(n-1/1), To calculate ((M1) and G(M2) in tight manner, we need to leverage the knowl- edge that the variance each element MM and M2 is controlled from the restriction E M1 or P M2.
A.1 RATE OF CONVERGENCE OF MAXIMUM LIKELIHOOD ESTIMATION WITH INFINITE HYPOTHESIS CLASS
We aim for obtaining PAC guarantee of MLE following (van de Geer 2000). We explain how should modify the proof of van de Geer (2000) for unconditional density estimation to conditional density estimation. For simplicity, we assume P
We first introduce the notation:
P P = (P p*)/2, = 0.5 0.5 12 (VFIP- p.
Recall
(P(P) s.a), P2( (,))) (0.5 ( ss,a) (2/2 (ss(sss))d(())) s))))())) 0.5
Here, from Lemma 4.2 (van de Geer 2000 the following holds:
Lemma (Some property Hellinger distance).
[s.))>> (PP s, a, Pa(: s, a))] s 0.5E (z)) (P s, Pa( ss,a)),,
E (P( s,a), P* s, a))] S (s.))~ 110 ssa)) P* (,)))
We also recall Hellinger distance is stronger than TV distance: Lemma (Relation Hellinger distance and TV distance
TV (- P2( 8, a)) s V2h (-,,), s, P2(: s,))..
The following lemma is useful to connect the log-loss and the Hellinger distance.
Lemma 3 (Basic Inequality for MLE).
B(e.))~phh? (PMMEE 8, a), a), (* a,a))] < (Ep
a,
This is proved by Lemma 4.1 (van de Geer 2000). To simplify the notation, we define
1 (P,, P2) ( s. a, Pz(. (,,))s,))))) s,a))].
15

---

Published as a conference paper at ICLR 2022
Here, goal is showing with probability - 6,
(P PT) S (5n + /log(c//0//n)².
This is proved by showing for x 2 En.
P(H (PMLEE P*) 2 x²) S cexp(-na²/cl
This corresponds to the statement in Theorem 7.4 (van de Geer 2000). To prove the above, we first
use
P(HH x²) (PIL, PT) (2))20 x²),
from Lemma
Then, from Lemma this is upper-boundee by
P(
sup PEM.
(n(gp) (P,
where Pn
VI aa)p PPttaa To prove the term less than cexp(-no</c²
we use Theorem 5.11 vaan de Geer 2000), that is, some uniform inequality based on entropy with bracketing. The rest of the proof the same as Theorem 7.4 (van de Geer 2000). In summary, the only difference is we use the distance H b) tailored to the conditional density estimation instead of unconditional density estimation.
B MORE DETAILS FOR KNRS
We explain the algorithm and present the PAC guaranteed for KNRs. Here, we denote the dimension
of S by ds.
We tailor Algorithm I to KNRs as follows to obtain a tighter guarantee. First, MLE procedure is replaced with WMLE by regularized MLE:
WMLE
arg min Ep[l]Wo(s,o) - ss'1 M||W 12 xd xd
where || || is a Frobenius norm. Then, the final policy optimization procedure is
# arg ma minwew, VP(wy> s.t., WD { pdsxd |I(WMME W)(2,) s {}
where in Ei= o(si, a:)Ø (s;, a:). We state the theoretical guarantee for KNRs below. Corollary (PAC bound for KNRs). Assume [ a)ll V(s a) E A. We
= 2\|lW* + SC2 (ds ln( + In(1/5) + In): I, = In (E de(())).
Suppose the KNR model is well-specified. By letting | O(1). 0(1), A = O(1), with probability 8, for all xt., we have
dsCr. p. In(1 n)
VF. vp. S min (2, (2 RV
where R == rank frank([] II(ee//));
n
The proof is deferred to Section E.5
C MORE RELATED WORKS
We discuss literature related to representation learning in RL.
Representation learning for low-rank MDPs (ground truth feature representation is unknown) in
online learning is studied from model-based perspective (Agarwal et al. 2020b) and model-free perspective (Modi al., 2021). In the online setting, Zhang et al. (202 laj; Papini et al. (2021) also study representation learning under different model assumptions. Comparing with these works,
since our setting is offline, the algorithm and analysis are totally different.
16

---

Published as a conference paper at ICLR 2022
In the offline setting, Ni al. 2221)) study dimensionality reduction in given kernel space, and Hao et al. (202I) study feature selection in sparse linear MDPs. Their focus is different as they do not study PAC guarantees under partial coverage. Ni et al. (2021) assumes the transition operator can be properly embedded into predefined Reproducing Kernel Hilbert Spaces and learns low-dimensional state-action representations via kernelized embedding and low-rank tensor decomposition. However, they did not study the errors for policy optimization after using these learned features. Regarding offline distribution coverage, Ni et al. (202I) assumes that the feature covariance matrix (feature associated with the pre-defined kernel) of the offline distribution is full rank. HHao et al. (2.2TT studies an OPE problem on sparse linear Bellman complete MDPs in the offline learning setting where they assume all covariance matrices (covariance matrices that correspond to all possible subsets of features) under the offline distribution are full rank as well. We study policy optimization in low- rank MDPs (with unknown feature representation), and we do not assume full coverage, i.e., we do not assume the feature covariance matrix full rank, and indeed our result distrbbttio-dependen since it scales with respect to the rank of the covariance matrix that is defined using the ground truth feature representation.
D COMPARISON TO XIE ET AL.
(2021)
We compare a result (Xie et al., 2021) to our result in detail. Let F be a function class for Q- functions. Here, we consider a more general version of their algorithm by replacing the original ((;,;;)) ) in their algorithm with
E(S, m: D) ((S,Sim,
min L; J; D)
geg
In their original algorithm, they set G F. Here, consider the version such that discriminator class can be different from F.
They show the PAC result under partial coverage follows. Here, Tp. is Bellman operator under π and P*:
Tp. A (A R) - r(s, a) + [P x)) x A R).
Theorem 6 (Extension of Result in (Xie et al. 2021 ) Suppose realizaibility Q7-- F, Vz II and closeness f mingeg Es,arpplg n E II. we have
J) a)) = 0, VT E II. Then, with 1 - 8, for any
Vp. Vp. = -0 (1(10//)))))) C sup ((oa))=d (T fer (f-))-(((TT](((00)
By combining this result with the conversion from model-free results to model-based results in (Chen & Jiang 2019. Corollary 6), we can obtain the following result under partial coverage.
Theorem 7 (PAC guarantee from the direct application of (Xie et al. 2021 to mode-based RL ).
Assume P E M. Then, there exists an algorithm s.s. with d, for any policy " 11.
- - C (((
As we mentioned, this is worse than our result since includes [II]. Besides, the algorithm can only compete against policies restricted in 11, while our algorithm works for the unrestricted policy class II which could even include history dependent policies. For completeness, we give the proof as follows.
We remark that their results (Theorem 4.1) with NPG that can possibly compete with any stochastic policies, are not applicable here. This is because they need assumption that the comparator policy T needs to satisfy QT. E J and m mingeg Ex.o~p[( TØ. (s, a.)] 0, which does not hold for the corresponding Q-function class F after the conversion. As a notable exception, when the model is linear Bellman-complett MDP (Zanette al. (021I, any stochastic policies satisfy the Bellman completeness for the linear Q-function class; then. their algorithms can learn policies that compete with any stochastic policies satisfying partial coverage.
17

---

Published as a conference paper at ICLR 2022
Proof of function class:
Theorem 7
Given model class M, consider the following reduction. We define Q-
F= f MMM.
Then, we define discriminator class G:
G = (T qp
T E TT P.,
The above satisfies the realizabilitty QT. E F,VT and the closedness T GT I1. Thus, the assumptions in Theorem are satisfied. Then, we have
VT. vg. O [n((1)
OlVC Mn((1))MM)))m))
noting
FF
[ and | MM?
E MISSING PROOFS
... to denote universal constants. For d-dimensional vector a and matrix A dddd denote ||al a "Aa Here, S B means S cB for some universal constant.
Below we use c, C1, c.....
E.1 PROOFS FOR GENERAL FUNCTION APPROXIMATION
Proof of Theorem I From Lemma the MLE guarantee gives us the following generalization bound: with probability
E, s [V(PLLE(-1 s,a), |[,)) (,))ssa))11111 s In(lM//5)
(6)
Letting
A(P) = am (P( [TV s,, a), P-
-
P*( (*(.1s,a)){1
with probability 5, from union bound and Bernstein's 's inequality, we also have
A(P) S (vvarce))- 8, a), (- 8, a,) In( (2ln((M1/0)
YPEM.
n
n
Hereafter, we condition the above two events. Recall that construct the version space using D and PMLE follows:
PaI.(. ())))) =
Md: =
First Step: Show p* E MD in high-probabilitty above two events equations (6) and
We set E = e Iul(IM 18), Conditioning on the we prove Pa E MD. This is proved by
n
Ep ED[TV(PMLL( s, P
a
= =E EV s. a. P" a)) ~, TV (s,,)
(s.))>p (V a, P* s.
ED s, (: s, a)) ( TV(PMEL 88, P* P' Ci In(lM)/8)
var (a.)))) TV 8, a,)), P. a)) In (LM188) In([M]/8)
(From (7)
n
n
(VV s, s, (+ s, 0)) (I(18/88) In(LM1/8)
(TV(Pme s,, P* 8, 8, < 4)
1
(Plug in MLE guarantee)
n
18

---

Published as a conference paper at ICLR 2022
Second Step: Show a
[PV
s.)),
8, a)) I <... AP E My in high probabil-
ity. We show for any E MD. the distance between Pa is sufficiently controlled in terms of TV
distance. More concretely (conditioning the above two events (6) and (7) ). show
E sa (V (, a.)1s, MD.
In order to observe this, for any P E MD, we have
(P[TV(P(-1s,0)) P' ( a))²
- 2Ep/EE/ 2Epp/V((PLLEC s, P(- s, a.))) + 2 2V
s, (.( (. < <
(From (a + b)² S 2a +2bb.)
Thus, have:
Ex (V (8.( 8, 8,a), (- |8,a))
_. (V(((
s, a) PM (-1 - s.(.
$ A(P) o
(8)
Here, from (7) we have
Ci (ar [T[(P( 8,0), 8, a, M|(5)
c2 In(MM1/0)
A(P)
MP Mp.
Then, for any P E Ma. we have
Ci ( (V(( s.a), s, 8. Ln(1))/8)
(2In((MM/0)
A(P) S
4c, 4c,E(s,a)ppl TV(P(
s, (* 8, (n(
22 ln(MM11
(IV(P(-1s,a) P* n a)) 4.)
4c 4c1(A(P) + cn))
Co (m(M/)))/))
$
n
From (a+bb) 6)2 & 2a + +82,
c(A(P) + +) In (M//8) cln(IM1/6)
(A(P) ())(M11)())00)) (cI((IM//d)
A
n
7
n
n
(A(P) + In(MM))))) n
includes In(lM)/5)
(A(P) 1/n
n
Then, have
AP BIA(P) B2 50, 0, Bi = clncMM(M//8/n
B₁ = =((/n// (n(m/))
This concludes
B1 + / B + 4B,
< c B₂) I In((M//8)
0 A <
S g.
2
n
Thus, by using the above A(P) S {(P E MM) and 8 with probability we have:
Bg (P( a). PT a)) A +E PE
Third Step: Calculate the final error bound taking the distribution shift into account any P MD, we prove
For
(1--)) (1-7))-2 (1- -a/cttt In((M]/5)
Vp. -V <
(9)
19

---

Published as a conference paper at ICLR 2022
For any P E MD, this is proved follows:
Vp. Vp $ (1 -)) 2B
|.,))
(Simulation lemma, Lemma 5
s (1-7)) /B (TV(P s,a), P* ( s,a))
(1-7)-2 Co..Bo (V(( s, (* 8, s,a))²)
< 7) 3 c
(l((0 n
(Based on the consequence of the second step)
Combining all things together, with probability 1 - 5, for any x² E II, we have
Vp. V 1 Vi.
min
VØ
min
V Ví.
PEMp
PEMp
Vp.
min
Vp
min PEMp
Vp Vp.
(definition of ft)
PEMp
< Vp.
min Vp
(Fist step, P E MMp)
PEMp
In in(MMo//0
< 7) ca V C
(From (9)
n
Remark 2 (To compete with all history-depente polices). Consider the case where TI is all Markovian polices. We want to show we can compete with all distory-dependee non-Markovian polices:
80
(i[sxa) x - A=
-((A)
T Ts
E
We take an element n² from IT. Then, VB. and df. are still well-defied. Then, every step in the proof still holds. The only step we need to check carefully is this line:
Vp Vp.
Vp.
min
V +
min
V
Vp.
PEMp
PEMp
Vp.
min PEMp
V +
min PEMp
V Vp..
This is proved by max VJ max VT for any P.
E.2 PROOFS FOR GENERAL FUNCTION APPROXIMATION WITH INFINITE HYPOTHESIS CLASS
Proof of Theorem 5] From Theorem 4 the MLE guarantee gives us the following gemeralization bound: with probability
(x TV P' s,a)){s & In(e/8)
(10)
n
We define
In(c/0)
Mi =
P P"( so ch
n
for some large c. From functional Bernstein's inequality (Lemma 12). by defining
f(P)(s, = TV(P(- s.,),, P* ((,(sssa)) s. G(M1) = E sup
(Ep - (F)](]]
PeM:
20

---

Published as a conference paper at ICLR 2022
with probability 1 5, have
log(c1 /8)
log(c1/0)
sup PEM:
(ED Ep)lf(P)] G(M))
sup
EpIs(P)?T)1P 1/2
PEM,
n
n
log(c1/0 (
log(c1/0)
x G(( + ( + sup
PEM:
71
m
SG(M)) + + + (mlcc/0)
(11)
Similarly, by defining
+ + +c (I(c//)
M2 = P: (
G(M2) E[ sup (ED [p)l( PEMp
Zn sup PEMs
((
from functional Bernstein's s incquality, with probability - 8, we have
1og(cr/8)
log(e1/0)
sup PEM2
(ED Ep)[f())] & G(M2) + (G(M2) 1/22
n
n
x G(M2) + V 7, In(c/8)
In In(c/8)
(12)
n
Hercafter, we condition on the above three events (10) (11) and (22)
First step: Show P E MMp in high probability. From (10) we have
B(s,a)~pp (PMLL)) a)] s c In(e/6)
Thus, P* Mi. Then, from and (10)
of
= I [f (s,
(f a)] + (f a)]
$ GG(M)) + e In(c/8)
Thus, P* MD recalling the definition of MDD (we set 6 G(M1) + 52 In(c/0))
12
Second step: Show the upper bound of [p.))~ [[P [( a)] for any P E Ma. P E Mp. as the proof of Theorem we can prove P E M2. Thus,
For any
sup PEMp
[(sa))o s Zn.
Thus, will hereafter analyze Zn. Here from (12) for any P E M2. we have (PP(s))
sup (I(E)),a)>> PeM₂
[) a)ll + sup reMa
[(sa)))((PP)(..a)
GG(M))+ + / Zn In(c/5)
+ G(Mi) + + In(e/6)
n
Hence,
In(c/8)
G(MM)) S In(c/0)
Zn S G(M2)+
Zn
This shows
Zn S G(M2) + G(M1) + + In(c/8)
n
21

---

Published as a conference paper at ICLR 2022
Third step: Calculate the final error bound.
Following the proof of Theorem
we can prove
Vp. - S (1 -a
( 2a
((MM))+GAAN + c + In(c/0)
E.3 PROOFS FOR TABULAR MDPs
Proof of Corollary 7
We prove similar way as Theorem
First step We set CI Inín| Alcs/8)). Then, from Lemma 7
with probability 1 - 6,
can show P E MD since
Bs (V(PMnx(-1s,,)) s, s, S.
Hereafter, we condition on the above event.
Second step. have
Following the second step in the proof of l'heorem based on (8) for any E EMp,
Eg 2,00p
(-)-) +
(13)
where
A(P) == aE, 8, P' s, a)) Bee]--E-/Tyy TV/TVV((( 8, PM ("(,ss,,)))
Our goal here is showing with probability 1 1- 5,
A(P) S SP Mp.
(14)
To prove (14) consider e-net (si(s, a..... (s a)) covering simplex in terms of |1 for each fixed par (s, a) x A. We take = 1/n. Since the covering number is upper-bounded
by (c/e)lS Wainwright, 2019 Lemma 5.7), we can obtain M = (PI, ... PRISIXIAL s.t. for any possible P CSSA (8). there exists P. s.t.
TV(P( a), P(. s,a)) S e, V(s,a)
This implies for any P x A(S), there exists P.(. a) s.t. V(s,a).
[V P. a,a)² ().
I 4 (
- -T(()
s,)) (a² = (a - 6)(a + 6))
< 4TV(P- s,,)) P.( 8,a))
Al|aal ||b]| S ||a bl)
< 4e.
(15)
We often use this property (15) hereafter.
Next, we define M C M so that it covers Mp. Concretely, we define M':
M' (P M =p" E Mp, TV s, P. s.) Se e ((s,)))
(16)
The construction is illustrated in Figure find p' M' s.t.
Here, from the definition, for any P E Mp, can also
TV(P(- s, P' s, a)) S (,)
This is because from the definition of M, we can always find P E M satisfying the above. Such P belongs to M' from the definition M'. We use this fact later.
Then, from (16) and recalling (13) we have
Esgacup
[TV(P(- 8, s,, PM( (188)))) S A(P), YP
(17)
'In the tabular setting, since the space is countable, is equivalent I.1 distance.
22

---

Published as a conference paper at ICLR 2022
Figure I: Ma is colored in gray. MM' corresponds to the set of black dots. Orange dots correspond to M, which do not belong to M.
because
E s,a-p
[V 8, P' 8, s,)))
$ Ess
(VV(P(-1s.)) P" s, a)) + E S, [TV(P"(.\s,a),, P. 8,a))
(Take some p" E EMD noting (16) Then, with probability 1- 8, from Bernstein's inequality, we have
< Eg
(.V(P"(.1,,0) P- s'(+1s,a)) a)) +
S + A(P).
(From (13)
var var[TV(((( 8, a). (. a)) Inc an) (KISKXII /8)
cIn(A1s(x144 (8)
A(P) S
AP M.
n
Hereafter, we condition on the above event. Based (17) we can state
E[TV(P(( s, P- s. a)) A(P), E'EM', var[TV(P(- s, a), (. s, a))) with probability 1 5. Following the argument of Theorem for PE M', we have
In(K 1n(K(5ix(A)/)) (6)
In In(K(51x(A1/8)
(In(KISINAA1/0) 2
A²(P) A(P) B2 S O, B
B, =
Then, with probability 1 - 8, we have
A(P) < In(K15ix(A1/0) In(KISX|AA// (8) 10)) 1/2 VPEM'. (18)
This shows for any P E MD. we have
KED
E 0) ~ (V a), (7(188)))²)
< (|E E (..0))pp (TV( P(: 8, a, + TV(P'(. a,)), (*[.] s,a))
(We take p' E M' such that (16)
< [[Ep (TV(P (:1s,)))3 8e
(From the definition of M')
SE
(From and P' E EM)
Thus, (14) is proved.
Third step. We follow the third step of Theorem
Vp. vp. < (1 - 7) -2 V
23

---

Published as a conference paper at ICLR 2022
E.4
PROOFS FOR LINEAR MIXTURE MDPs
Proof of Corollary 2 Here, letting P(O) - 0 (s, a,,,,, 8'), recall
0 ((0))0E0CR) R.. /
v(s.a) , --- {
P+P MMix
MMix
Upper-bounding ats (TV(P())( (TP)))) | s, (-
By invoking Theorem we first show
E (Tea)=((V((P("))) 8, s, ( 8, a,a)) S Lldd/))ln + In(c/8)/n).
To do that, we calculate the entropy integral with bracketing. First, we have (r, H, d) s NNile, MMix.
(19)
where
d' d((a,)) (( [(alss,,))) - -(,,,,,,))) -
1/2
(20)
d(a, b) [ssa)> /
1/2
(21)
Here, we use two observations. The first observation is
d² P
P(0") + P
S (CI'
2
2
due to the mean-value theorem
Va vb s max(1/Va 1/ -
and assumption P*(s' 8, a, 2 co > 0. The second observation when we have P' < < P" we also have ((" + P-2 < Vlg + P*)/2 V(P" + P*)/2. Then, (19) concluded.
Next, by letting ((1, .... ((K) be an c-ooer of the d-dimensional ball with radius R, i.e, Ba we have the brackets {[P()()) - c, P()()) + <]] which cover Mmiz- This is because for any P(0) E Miiiz we can take g()) s.t. ||0 g( 1|2 S e, then,
P(O()) E P(O) < P(O te, v(s,a,5)
noting
IP(O)ss s') P(O (s, s')l s 10 1000000122 1 se, v(s,a,s)
(22)
The last equality is from Lemma 10
The brackets above are size of e. Therefore, have
Nf || (12) S W(c, Ba(cR),1l 1122)
where (E. Ba(eR) (22 is a covering number of Ba(elt) w.r.t || [2. This is upper-bounded by (cR/e)2 WWinwwighh integral JB( Mmias
2019 Lemma 5.7). Thus, we can caleulate the upper bound of the entropy
12)
d In (c//cc/R)dd < ( 1/2 In In(1/u)du /2 In(e
cd 12 (n( + /d In(eR)
< /22 (0
By taking G(z) = d2/2 In(e//2) in Theorem 4 8n (d/n) In(RR) satisfies the critical in- equality
Vn > / In(eR/ōn).
Finally, with probability 1-8
(,)), 1s, <e' g= ((dm))))))) In(c/))/n).
(23)
Hereafter, we condition this event.
24

---

Published as a conference paper at ICLR 2022
Upper bounding Ep (V)()())( | s,a), P()MLE)( s, s. We take é-cover of the ball (R( in terms of 1111112, i... M {0(1) ,0(K), }. where K = (cR/e)", We take 1/n. Then, for any 0 E Ba(R),, there exists 0 s.t. a(s
(V))(()) | 8, a), a), P(ÓNLE)( s, a)) - TV((())) |,, P(ÒMLE)( (,, (8,)))
< { s, (() s,a)) - TV(P((())( s, a, P((rLE)) s.a)) (a² = (a b) b))
$ <4TV(P(0) s.
( P(..). s,,))
[||a|l 11611 - ||a bl)
$ 4110 0 2
(From Lemma 10)
S 4e.
(24)
Hereafter, we condition on the event:
(ED ( 1 (,,), ( 8,a))²]]
(25)
8,a)) In(K/)) In(K/0) (T 8,0),, (100))(((1))))))))
vO M.
n
This event holds with probability from Bernstein's inequality.
Here, note for ÔMLE, we have g00 s.t. [[θMLE 8 S c. Then, following the first step of Theorem 1
(( TV(P(()( s,),) P(ŌML))( a))
TV
a))² +
(From (24)
I (Ep - E, 1s)
a))² + ((,,)~~ TV(P()) P(O()) s,)))²
var (ar (V(
ln(K/0)
TV(P))))) P(O |s,
(From (25)
(.)) ln(K/))
In(K/o)
n
+ c ((s,)) (T(()))) P(O(0) (- (..)))
(TV(P(0)((1 P(00))) P(O()) ( < 4)
Then, we have
s.a), EV(VV(P())) ( P(MMLE) s,a))
$ [VV())) a, P(MML.)( s, s, ln(K/)) In (K//)))
+ + (oo.))TT((P(C)) s, P()MLE) ss,))²
$ SV]+cln((//) ln(K/8) +e+E'.
(From 233
n
In the end, by taking 1/n, we have with probability 1-5. 5, EVTV()()') a, P((ML.) ( a))) SE,
E (m()))
This also implies with probability - P* E MD.
Show E(,,a)~
EV TV s. P(O) s, a,)) < E. (PP(( Mp.
We show for any P E MD. the distance between Pa controlled in terms of TV distance. Our
goal is showing
s,a), (T..))TT((P(()) I (s,)) 2 SE. VP(0) e Mp.
25

---

Published as a conference paper at ICLR 2022
First, following the second step of Theorem based equation 8 we have
(Va))-T((P(())) s, s,a), P(O) s.)))² I A(0) + c5. 4P(0) E MD
(26)
where
A(0) = [ED - B(ssa)-)) s,))), P()) (
From now on, we again consider an e-cover of the ball (R(R) in terms of || lll. ie., M = {0() .n.. {(K),, where K = (c.R/e)* (E = 1/n). This also covers the space Mp. We take M' 1 g622) C M which covers MD. that is,
M' = {e e M 3.'..t. E MM, 110 - 02 sc..
Recall Figure E M s.t. 1 1112 & 1/n. This is because we can take 0 E M s.t. ||e 811 S c noting M is an e-net, but such belongs to M' from the definition of M'.
which illustrates this definition. Here, for any 0 s.t. VP(0) E .MD we can take
Then, we have
40 E M'. E(O.a~~ TV(P(0*)( 8, a), P(O) 8, a,) S A(0) + og,
(27)
This is because for any 010) E M', we can take P(0) Mp such that
E B
s.a)) (
|
S E ( [V()((
a))² TV(P(0'( s,)) P(O)( a)
+ (x B
(
S 4e + ((a,))= (s. (8
(10 - 0 ||2 S 6 and from (24)
2 A(0) +
From (26)
Here, from (25) have
var (s,))~) (VV(p(())))))))) s,a), P(O)( (0000)18)0))))))))) (.a)))]ln((/bb) cln(K/8)
A(0) <
A0 M'
Based on the construction of M' and (27) we have
(=.)), (TV((()) 8, a), P())- s, a,))) A(0) +c, VO
Then, following the second step of Theorem A(0) satisfies
(2 - A(0) - B2 50, Bi = In(K/8)
B₂ = In(K/8) + (In(K/8)
n
Then, we have
A(0) In(K/0)
In(K/8)
112
SE.
VO e M'.
(28)
We combine all steps. Recall for any VP(0) MD. we can take of e M' s.t. |10 l'112 s 1/n. Then, for any P(0) E MD. we have
A(0) = [Ep ((,a))~p)) TTV((())))(((())) s, (=)0))((s))))))) s,)))²
< (ED ((r,a)~p) (
(. s.)), |s, -..))))-VV(P001111...) P(O a)))
+ (Ep - ((r,a)=))))
(8,)))
< 8e + (EED (.aa0))lIL((PP0)111sss..... (
a)
(From equation 24p
SE.
(From equation 28 and 6' E M')
Then, we have with probability 6,
A(O) E, VP(0) MD. Finally, for any P(0)= Mp. with probability 1 - 8, we have
(29)
E (is.a)=p[TV(P()) a.)) s))) < A(O) of
(From equation (From equation
26
S g
29
26

---

Published as a conference paper at ICLR 2022
Distribution shift part
Here, for P MM prove
VØ. Vp (1 7) dd
(30)
Vp. Vp $ (1 - 7) ~ C
(31)
Following the third step of the proof of Theorem 5 this immediately concludes the bound
Vp. Vp. / (1 - VdC.
Vp. Vp. z (1 7) 2 V
Since (31) is obvious from simulation lemma, we only prove (30) To prove (30)
we take a distri-
bution P(e) E MM. First, recall for P(0) E Ma, we have
(s,a)>> TV 8, a), P(O) s, a))² ss.
From the third statement Lemma 10, for any V S + [0, 1]. we have
E B(s.))o(((0--0) - 0*) Φ/ (s. a) 55
Thus,
: - [0,1] 1], (0 (0-00
Sc Dp = (eo.)
Here, we have
B(aa)adzi [(P(('10,0)- Pm 1= (s')dss))
VØ. Vp- s (1 (1-
(Simulation lemma, Lemma 5
(1 7) E ((sa))dpi (0-00)v: (8.a))
(Recall d/v = f sbsss, a, s'V3 (s')d(s'))
$ (1 - |10 0* 1*11++ n.v3" (e,)) [Ieiigs (s, (s,a)llo,, p.z +an)-
(0)
(b)
(CS inequality)
The first term (a) is upuer-bounded by v((1 ((11-))-2t + AR2] noting 0 s Vp < (1 (1-7))+ The term (b) is upper-bounded by
1/2
E ((.0))a3; [WVV (s,a)llss, v.''" +AI) +A1)
[Ivvr (s, (s,
< E ((aa)dd
w.V +
(Jensen's 's inequality)
Tr((aag vz- (AI + E 2. )-1)
Cnr Cr mix Tr(Ep.vE' (NI A++ (From Lemma 11)
Crr, p. S / Cnxdiix.
By taking À s.t. XR S (1 - -2. (30) is proved.
For linear MDPs, from the fourth statement of Lemma 10 C mix S Cr.. Then, the statement is concluded.
E.5 PROOFS FOR KNRs Proof of Corollary
We prove in similar way Theorem
27

---

Published as a conference paper at ICLR 2022
First Step Recall
= 2 + SÇ² (ds ln( + In(1/6) + In), In = (dett( det(AI)).
Thus, from Lemma 8
with probability
can show W E WD since
[WMLL ) (En) 1/2 1/2
5.
Hereafter, we condition on this event.
Second step
For any W E WD. with probability 1 6, we have
(W- 1/2 $ ( W) (E,, 1/2 1/2 + -1( (EM) Se
Third step
Note P = P(W*). Then,
Vp. Vp. < Vp.
min WEWo
WEWD VF(w) min P(WW) Vp.
Vp.
min WeWo
Vi(W min
V P(W) V
(definition of ft)
WeWo
<
Vp.
min Va Piwy
(Fist step, W E Wb)
WEWp
Then, by setting W" arg min WEMo Viwyy we have
V V S (1 7) 2 B (2))))77) (s) - P (*((s
(1 - 7) 2
E ((r [l(WW- W*)6(s, a)1l
Lemma 9p
(1 - 7)
B((.a)aa
(W' - (E,) 3/2 (1((,,a)ls
(CS inequality)
(1 7) -2
{ (B (11 1)),
(Second step)
From Chang al. [202 Theorem 20), with probability 8. we have
S ci I 12 ds (i, + In(c2/5)), d) In(1 + n).
addition, from Chang al. 2021
Theorem 21), with probability 1 - 6, we also have
Cr rank/EE (rank Epl + In (c2/
E (s.a)=pp; [ a) (>))= S e
n
Finally, by combining all things, we have
CsC In(1 + n)
V Vp. (1(1) m2n R
R = rank (rank(E,) + In(c2/8)) /8)}
E.6 PROOFS FOR LOW-RANK MDPs
Proof of Theorem 2 Until the second step. we can perform the same analysis as Theorem concretely, with probability 1-6 5, we have p* MD and
More
T5.>>PTV(2 P. (. VP IP. = In([M//8)
(32)
Hereafter, condition the above event.
28

---

Published as a conference paper at ICLR 2022
Letting ((,,a) TV(P(. s, P* s. s,)), we use Lemma 4 Then,
((aaa)ad [8,, a)] S (((a)))dz Illo* a))l=> IV Vnywa BrywwRBpleee ( a)) + 422 va 7)) a))
where E nEpp@0 AI. We consider how to bound ((aa))dy (s, |. This is
upper-bounded by
(ssa))dd3. [1lod' (8,0) a))s==111111 p.o.
S V Ir Ir(Biaa)mdz, 10 " ppppp)))
Cr ((((()a))pp o0 T 12
(From Lemma 11)
rank
Here, in the last line, by letting the SVD of D. EploØ " be U.P where Ep is d x d diagonal matrix and U is a x d orthogonal matrix, we use
tr Σ9 pp0 -
= UUUSS (NUÉ,UT + = tn(ttt" + +11--1
- =u(EūU- + UU
=
=ur(pp(E + (11) & rank Ep)/n.
Hence, when E MD. by setting s.t. Ad S n. we have Car rank(F,)) ln(MM/8)
y) ln(1)/88)
(( [f(s,a]] v
n
n1
We use
(22 here.
Finally,
V V
Vp.
min VB"
(Recall the proof of the third step in the proof of Theorem Ii
PEMp
7) 2 s.add:: (s, Pm (,)1,,))))
(P' arg mimp Vi
Onr rankk a- In( (1/8)
111 71
The following inequality is an important lemma to connect B(saa)=d7, (f(s, with an elliptical potential ((z,a)=55. Ilo
(8, a)llz=
Lemma 4 (One-step back inequality). Take any f C S x s)). for any policy n, we have Letting w max,, ( [0/T
[f S B and 0 < A E R.
[((,,))az (f(s,a)31 S B(a,a)=pp, 11000(6 a)lx) /
(nww ( [f² 2ddB2
+ v (1 y) B(a ({(
where E n 30 (s, a) (8, a)) + +X.
Proof of Lemma 4 First, have equality:
B(s.a)=d5, {f(s,a)} = 13..a) [f(s, + (1 (f(s,
(33)
29

---

Published as a conference paper at ICLR 2022
The second term in (33) is upper-bounded by
(s= (f(s. < (owdo, (f(s.a))3 (
Next we consider the first term in (33) By CS inequality, we have
(( (3. / | s)
( (f(s. a)}3
(s,ā))d 1 (5, p(s)T(al s)
Then,
f M(s)a(a a)dss
{/ p(o)T(a | (o) o { A(s)T(a s)
$
1
Fisamo / ((
} + B2
(Use the assumption || a)llo S and II A(s)d(s))l & vd)
n [ [f(s, a))} Bd
S n { [B (s, a)]} Xd.
(Jensen)
Finally, the the first term in (33) is upper- upper-bounded bounded by
P. amsl(s) (s, AdB
S nw-
( (s²(s) + AdB
(Importance sampling)
< nw's
(s, ( AdB²
(Definition p)
The final statement is immediately concluded.
E.7 PROOFS FOR FACTORED MDPs
Proof of Theorem 3 We denote the constrained Mp:
| s[par), a), Pa(. | a)>?] s Si vi (1, ..0,...,)) .
Mp II Ps ED (P
Following the first step in the proof of Corollary I Mp. i.e.,
with probability 1- 6, the product II, P is in
Eg,a~D TV(PLL slpa,). a), P.( s(payl a))p < E., Vi (1,...., ,d, = ==v/ log(L.d/6)
Note d comes from the union bound. Besides, following the second step in the proof of Corollary for any P MD, with probability 1 5,
Egaavp [VV(P( 1 s|pa,), a). P: s(pa,), a))²] s E. vi E [1....,d].
30

---

Published as a conference paper at ICLR 2022
After conditioning the above two events, then, for any P E Mp and x² E II, we have Vp. V$ < (1-7))33a (s,a))ad7; (TV( s, (* 8,a))]
(Simulation lemma, Lemma 5)
{1--))- 2E - 7)0 (s,)) E TV(P:( s(pa,). a), Pt s(pa;),
s(1-7)-22 B(oa))m (
(<leepuas (s.(aa)))) a.)
) 27
18 ([lsa)/p[TV(PP)) s(pa:], a), P. slpa.), a))
p(s(par), a)
(CS inequality)
5(1 Σ /VV P7(
(1->))² (1-))) Σ
<
Crr
{11-))- dd :00 Es
(CS inequality)
L LIn(Lnd/0)
<cl -1-- 7) V
/dxx,,
n
Here, recall
( p(s(pac). a) the statement concluded.
dp- (5 a)
27
C = max ((sa)> seil,-. al
Following the third step in the proof of Corollary
Next, we show that Cr. x0 S Cg+,p. = max,,a p(a.a)
(p.a
Proposition (Comparison of L -densitt based concentrabilitty coefficient between factored MDPs and non-factored MDPs) ). For any n², have:
Čze,oo S C
(34)
Proof. From now on, for any E [I, ,.,,,, by defining S s.t. S S= S; x S% we prove
dp. (8;.
dp. (81, (8),
max
max
REE p(5;, a)
p(s,, 8/,a) EE
Then, (34) is easily proved.
First, for any 8; E S., a A, we have
max dp. (s,, sy max p(s,, a(s s) p(s),a) max d'. (s¹ 8,.0)
(s/ s,,a) (s) a)
di (s
2
p( a)
p(s a)
(35)
Here, we use
(s) 8 a)
1 max o p(b/ 8i, a)
which is proved by the contradiction argument, that is, if 1 > max,; cannot be probability mass functions since we would get
d7 (dflewn)) p())).a))
both p and dz.
Σ dp (s) s., s,, I max si
ddp (s/
Ss, a) 81,a)
Σ p(5 8is a) Eplos a),
p(8)
Then, by taking the maximum over 8; E St a
A for both sides on (35) have
(st,
max (s,,
max
5,4
p(3),a)
8,86.a
31

---

Published as a conference paper at ICLR 2022
F AUXILIARY LEMMAS
Lemma (Simulation Lemma). Consider any two transitions P and P and any policy π : S - A(A). We have:
Vp [11 ?) "B))"EEy,aaa Bawdd [ ((s - Ex (F
(1 7) E aawdd TV(P(+(s, a). P())s,a))
Proof. Such simulation lemma is standard in model-based RL literature and the derivation can be found, for instance, in the proof of Lemma 10 from Sun et al. (019)).
Lemma (MLE guarantee). Given a set of models M = {P S A A(S)} with P M, and a dataset D = {8s, 0g &1 with 86 ag ~ P. and 5y (*, az). let PALLE be
PALEE = arg min PEM
In as)
With probability least 1 8, we have:
E Bg TV (V(PMLE( (+(ss,a))) In(1M1/0)
Proof. Refer to (Agarwal al. 20206 Section E)
Lemma (MLE guarantee for tabular models).
SSAHSS In Im(21S]144100)
Ep
2n
Proof. From Chang et al.
2021 Lemma 12), with probability 1 1 6,
SS] In 2 |n(2[5||A// V(8,a) Ex
(V(P(+ss,a) a), P MLL(-e a))² <
2N(s, a)
where (1s a) is the number of visiting times for (s, a). Then,
S 2n + (n(2(S||AA/6)
Ep TV(((-1s,, o), P s ED
2N(s, a)
In + (n(2 /6)
2n
(s.a)
||| In 2 In(2)
2n
Lemma 8 (MLE guarantee for KNRs). MMLEE - W+) (En,) 1/22) < Bn.
Proof.
The proof directly follows the confidence ball construction and proof from Kakade et al.
2020
Lemma 9 (Ei Distance between two Gaussians). Consider Gaussian distributions P (( (I) and Pd == (1p,, We have:
TV(P,, < <
1| H2ll2-
32

---

Published as a conference paper at ICLR 2022
Proof. This lemma is proved by Pinsker's inequality and the closed-form of the KL divergence between P1 and Pz. Refer to (Kakade et al., 2020).
Lemma 10 (Property of linear mixture MDPs), Let P(0) = AT (T a, 8). Suppose P(0) s x A + (SS). For any function V E S - [0, 1], letting Dy (s, = (sss, a, s') (s')d(ss,, we suppose [8v(s, a)ll2 S 1. The following theorems hold;
1. For any (s, a,a,s)), s'), we have (P(0) a, P(f')(s,,s')) ||0 81112
2. For any (8,a), have TV(P(0)ss.:)) s ||0 01 Besides, for any
V : S + [0, 1), we have
100 8
3.
x. TT (a.a))d ( a) (a,a.)) (8,
ct Tr sup x I B(ssa)~p(VV (s, ( (5,
x / (l8,a,
V(O,,,)) arg max V=S-+j0.1]
4. linear MDPs (i.e, (888 a, 8')= ob a) 3 p(8)), we have
( lyv 0) (0s
x Ex ((s.aa((s)))
sup sup (S x (Ta) (WV a) (x, a)}= sup ==
Proof. We prove the first statement. This is proved by
IP(0) - P(0)) 100 (') a, s')l S ||0 0' (22l1l(sss a, s')ll S |0 0'112.
Here, we use [|bb(s, a, s') 12 - 1 which is proved by the assumption by setting V(s) = I(s' s) for any s'.
Next, we prove the second statement. For fixed 0 E Rd and (8,a) E x A. we have
(.))
sup v:S-(0,11
|(0 8U) / v(ss
sup vis-(0.1)
10 0T)T /
10 0T) Vi (s,
In the third line, we define V(s, a, arg maxy 10.1) 100 - - 1b(ss, a, (s)
Then, from CS inequality, TV a,
(100 100-0 1lalyy,,,, (s, |10 0*1|2-
We use the assumption II (s. < 1. This concludes the second statement. Besides, for any V S + [0, 1], we have
(6 (') a)l < 100 - -T) To o (s)
< II
The third statement is immediately concluded by
((..))=d3:: ( (8,0, 2)
= E(o.a)ad3: [10- B*) oy
(36)
E (e (V(P(())s..))) ))3
[( (0 TT
V/V (s,
33

---

Published as a conference paper at ICLR 2022
Finally, prove the fourth statement. Suppose vis, o(s. a) @ jus') (8 denotes kronerker product). Then, (v, s') = o(s, a) @ ((s')V(s)dd(ss)) Then, by defining a vector vVV) =
we immediately have
E (s.)) (v ()) sup
x T E (..)) (6(s.0) ( @ ((V)) T/
x (8,
x ((ossa) (())) (()))
(V))
(37)
Here, we have
a) @0 (VV))(((s (V))" Epl(o(s, (()) ((V)))
(p(( @ (MVV)(V))).
We notice
(Epllo(s, ())(s, a) & (x(V)(())))">===<<d))) = a) T1 @ (n(V)u(V)T))
This is because the square root of matrix is unique and we have (A @ B1/2) & B1/2) AB for symmetric matrices A and B. Then, by denoting F, Eplo(s, a (o a) "1 Fap. Eag, (o(s, a)o(s, a) and denoting the pseudo inverse of F F+, can see (37) is equal to
(F//2 & (VVV)(()))) @ (u(V))(V) & (V(V)
= =(F, (N (VVV
(MVV) & (u(V) 1/23
-1F, F/) & 12) @ Is (k- rvnk(((V))u(V))))
Here, Is is diagonal matrix s.t. k N+ values in the diagonal entries and the rest of values are O. Then, the maximum singular value (FP 1F/1/2 Faz. Fp 1/2 @ La equal to the one of {FP Faz. Fp 1/23. This is equal to
x Fsz. F
sup
Hence, the fourth statement is concluded.
Lemma 11 (Distribution shift lemma). Suppose A1, A2, Ag are semipositive definite matrices:
Tr(ArAg) S o maxx (A 112 A 12) Tr(AgA2).
Note
sup AT
Tmax (Agx 11/2AAA
zERd AArr
Proof.
Tr(A142) = T A241/2) Tr 1/1/2 1/ A2 17
Tr 1/2 "114,"''114,1' A14, "//4"/////A/AA/
In addition, for any semipositive definite matrices A, B we have
Tr(AB) TrUAUT B) = Tr(AUT BU)= < m TrUU BU) Tmax (A) Tr(B),
where TAUT is the SVD decomoposition of A. This concludes that
Tr(A1A9) S Omax (A5 (
A1 1/2) 1
Tr(AyA2).
34

---

Published as a conference paper at ICLR 2022
The following lemma is useful to obtain the generalized result of Theorem Wainwright 2019 Theorem 3.27). We first define
The proof is given in
Z sup EDD Epp(f] feF
Σ sup ED ED[[[(s,a) E,l o² sup varl/(s, fer
fet
Lemma 12 (Functional Bernstein's inequality: Talagrand concentration inequality for empirical process), Suppose |// S B. With probability 5,
log(c/8)
B Blo(ee/5)
E| S 2
As an immediate corollary,
log(c/6)
B log(c/6)
Z - -|z] S (o² B
71
35


Reviews:
[{"review_id": "iUB2DGaMzG4", "reviewer": "Reviewer_Tgsy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Offline RL is a hot topic nowadays and relaxing the full coverage condition in theory is important. Overall, I feel this paper contains lots valuable results and is the first of such kind of guarantee for model-based algorithm+partial coverage. But more or less I feel a bit less exciting after reading the paper since it's hard to get the strong point. It should not be the case that If there exist guarantees for model-free algorithm under scenario A and B, we must have guarantees for model-based algorithm under scenarios A and B. I would like to gain some insights on why we want to study model-based algorithms in this offline setting over a model-free algorithm. Pessimism has been studied in quite a few other papers and so is the partial coverage condition. \n\nSome specific comments: \n\n1. One concern is about the algorithm. I do not feel it's a real algorithm and can be implemented in an efficient way. I hope the practitioner can gain some insights on algorithm design after reading the theory paper. In particular, even for linear mixture MDPs, you need to integrate over the whole state space which loses the computational efficiency. Please correct me if I am wrong. And no experiments which are a bit disappointed. It will be good to see the comparison between model-based algorithm and model-free algorithm with pessimism. \n\n2. I appreciate the authors would like to include as many examples as possible but some of them are not quite well-explained and the paper now is a bit dense. For example, the offline representation learning with a low-rank structure is not well-motivated. And there is no even motivation why people should study this. Is there any technical challenge? If so, it should be discussed clearly. Again, it might be hard to get the key point since for each setting, the rate has been studied and is not supervised.  \n\n3. It may not be fair to say model-free offline RL approaches often require additional structural conditions in the function class (e.g., Bellman completion). The linear mixture MDPs might be a worse condition since it compresses too much information and there is no empirical evidence to justify it as far as I know. It's purely invented to prove something.\n\n4. About the function class. What do you mean by \"general function class\"? What's your function class complexity measure, like VC-dimension or Rademacher complexity or else? In Theorem 1, I just saw |M|. Does it mean M has to be finite?", "summary_of_the_paper": "This paper studied offline RL for policy optimization and proposed a model-based algorithm with guarantees that can hold under partial coverage. The results can cover several existing popular model classes.  ", "summary_of_the_review": "This paper provides rich theoritical results for the important offline RL problem but it's a bit lacking a strong exciting point. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "e54M2gZCA_g", "reviewer": "Reviewer_3dYA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\"worse performance\": the theoretical performance provided here is somewhat worse than prior arts. For tabular MDP, many results show a linear dependence of S, which is much better than Corollary 1. In addition, the linear mixture MDP doesn't include linear MDP as a special case, which is misleading. Definition 3 is different from the standard definition of linear MDP, which doesn't assume $\\mu$ is known. This is substantial since the dimension of standard linear MDP is $Sd \\gg d^2$. Summing up, a linear rate w.r.t. model dimension is achieved for CPPO, which is worse than the general sub-linear rate.\n\n\"computational issue\": the authors should discuss the implementability of the proposed algorithm, which is missing here. As for me, CPPO is much more impractical than prior arts.\n\n\"model based vs. model free\": the definitions of model based/model free are strange for me. Many \"model free\" results stated in this paper are commonly considered as model based methods, such as methods for tabular MDP and linear MDP and so on. Specifically, in tabular MDP, one constructs an empirical MDP with penalized rewards first, and then solves this model to get an optimal policy. In linear MDP, one uses least square to deal with the empirical MDP with penalty. The authors should make clear of this point.\n\n\"technique correctness\": in Corollary 2, $c_3$ is at most $1/S$, which seems to be considered as a constant here.", "summary_of_the_paper": "This paper propose an algorithm named Constrained Pessimistic Policy Optimization (CPPO) for offline reinforcement learning, and PAC guarantees are provided for many specialized Markov Decision Processes under the partial coverage assumption of offline data.", "summary_of_the_review": "Given the above technique issues, I think this paper is not ready for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "cIF_akQAAaS", "reviewer": "Reviewer_gN7e", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work takes a model based perspective, where a general, intractable algorithm is proposed first.\n\nThe advantage of model based algorithm in certain applications (for example the lack requirement of Bellman completeness) is well motivated, e.g. remark 2 and also the conclusion. \n\nThe bound is then specialized to several well studied setting of interests. Among these, the low-rank setting with unknown features is of particular interests. Per my understanding the computational tractability of the method is not discussed, and the algorithm is therefore not efficient in that respect.\n\nSince the algorithm is model free but many proposals in this space are model-based, this work is a first serious attempt at a offline model based RL with pessimism.", "summary_of_the_paper": "The paper builds on a recent trend of pessimism for offline RL to return high performance policies on an event with large probability. \nThe contribution of the paper is theoretical, and about model-based methods.", "summary_of_the_review": "The paper provides a first good attempt at offline rl with pessimism, and should be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ZCnDg-TkMuo", "reviewer": "Reviewer_Pn6R", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThis work contributes to the literature of pessimism principle for offline RL by taking a model-based approach. It is an important complement to model-free type works by showing another way to get things done. \nThe various examples unveil some untackled problems that can actually be dealt with the model-free framework elegantly. \nComparison of state-of-the-art works is detailed and essential, which might be of use for upcoming works in the field. \nThe paper is in general clearly written and main points are neatly presented. \n\nWeakness: \nThe advantage of tackling infinite policy class is a little bit over-advertised. In model-based approach, the hardness of learning with complex policy class naturally takes over to complex model class. In fact, model-free approaches (e.g., Xie et al., 2021) can also deal with infinite policy class with bounded complexity. That’s why I feel the point a bit over-advertised. \nImplementation feasibility: Is the model-based approach easily implementable like function approximation with bonus functions (e.g., Jin et al, 2020)? It would be nice to have some discussions on this point. \n\nOther questions: \nDependence on model class complexity: When the model class is infinite, the learning performance of MLE requires complexity measures like bracket numbers, hidden in the \\xi_n in Appendix A. Is there any intuitions on how it compares to model-free approach? ", "summary_of_the_paper": "This paper studies the model-based approach to offline RL employing the pessimism principle, which complements the line of research on model-free pessimism. Based on TV distance between the learned MLE model and the realizable ground truth, PAC guarantee of the learned policy is established for various examples, some of which have not been tackled with model-free pessimistic methods. ", "summary_of_the_review": "In general, the paper is well written and main points are neatly addressed. With a model-based approach using concentration properties of MLE, this work contributes to the literature of pessimistic offline RL and shows various concrete examples the framework can deal with. Some weakness include the over-advertisement of tackling infinite policy class, and lack of discussion on feasibility of implementation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors consider the offline RL with only realizability and partial coverage assumption, under which a model-based pessimistic policy optimization algorithm has been proposed and rigorously justified. Moreover, variety of special MDP models, including kernelized nonlinear regulator and linear mixture MDP, have been plugged into the general framework, which leads to different specific algorithm and refined guarantees. 

In general, the reviewers are positive to the submission. However, there are still issues need to be further discussed, 

- *Computation feasibility*: most of the reviewers raise the same concern about the computation feasibility and efficiency. Specifically, the proposed algorithm is too complicated, and thus, may not be practical. 

- *Comparison with existing statistical results*: both reviewers and I appreciate the summary in the paper about the coverage assumptions in the existing methods. However, a similar table for summarizing the complexity of existing algorithms, as well as detailed discussion, is also necessary for a better position of the proposed method among the literature, including both model-based and model-free RL.
Decision: Accept (Poster)