On the Role of General Function Approximation in Offline Reinforcement Learning
Authors: Chenjie Mao
Qiaosheng Zhang
Zhen Wang
Xuelong Li
Venue: ICLR 2024 spotlight (2024)
Keywords: reinforcement learning theory
offline reinforcement learning
general function approximation
learnability
minimax lower bounds
Primary area: reinforcement learning
TL;DR: This paper clarifies the use of general function approximation in offline RL and proposes lower bounds for learnability.

Abstract: We study offline reinforcement learning (RL) with general function approximation. General function approximation is a powerful tool for algorithm design and analysis, but its adaptation to offline RL encounters several challenges due to varying approximation targets and assumptions that blur the real meanings of function assumptions. In this paper, we try to formulate and clarify the treatment of general function approximation in offline RL in two aspects: (1) analyzing different types of assumptions and their practical usage, and (2) understanding its role as a restriction on underlying MDPs from information-theoretic perspectives. Additionally, we introduce a new insight for lower bound establishing: one can exploit model-realizability to establish general-purpose lower bounds that can be generalized into other functions. Building upon this insight, we propose two generic lower bounds that contribute to a better understanding of offline RL with general function approximation.

Published as a conference paper at ICLR 2024
ON THE ROLE OF GENERAL FUNCTION APPROXIMA- TION IN OFFLINE REINFORCEMENT LEARNING
Chenjie Mao 2, Qiaosheng Zhang', Zhen Wang", Xuelong Li*
'Shnnghai Artificial Intelligence Laboratory, 'Huazhong University of Science and Technology "Nortwwestern Polytechnical University
Institute of Artificial Intelligence (TeleAI), China Telecom Corp Ltd
ABSTRACT
We study offline reinforcement learning (RL) with general function approximation. General function approximation is a powerful tool for algorithm design and analysis, but its adaptation to offline RI encounters several challenges due to varying approximation targets and assumptions that blur the real meanings of function assumptions. In this paper, we try to formulate and clarify the treatment of general function approximation in offline RL in two aspects: (1) analyzing different types of assumptions and their practical usage, and (2) understanding its role as restriction on underlying MDPs from rnformation-thhereee introduce new insight for lower bound establishing: one can exploit model- realizability to establish seneral-purpose lower bounds that can be generalized into other functions. Building upon this insight, we propose generic lower bounds that contribute to a better understanding of offline RL with general function approximation.
perspectives. Additionally, we
INTRODUCTION
Reinforcement Learning (RL: Sutton & Barto (2018)) studies learning optimal policies by interacting with the environment. Thanks the increase computation powers and the development of powerful function approximators, this learning-based control methodology has had tremendous success in recent years, as seen studies such as Mnih et al. (2013); Silver et al. (2016); Kalashnikov et al. (2018). However, despite the significant progress and its great potential, RL algorithms face challenges in real-workd applications like Hcalthcare (Gottesman et al., 2018; 2019; Tang et al., 2023) and Autonomous Driving (Kiran et al., 2021), due to the risk, cost, or ethical concerns associated with online explorations. A promising idea for applying RL to these domains is to utilize the dataset collected in advance to learn policies-thh line of research falls into the area of offline RL (also known as batch RL; Lange et al. (2012); Levine et al. (2020)).
Theoretical studies of offline RL range from exceptional cases such tabular Markov decision processes (MDPs; Wang et al. (2022); Rashidinejad et al. (2021); Xie et al. (2021b); Yin & Wang (2021); Li et al. (2022): Yan al. (2022)) and low-rank MDPs (Jin et al., 2020; Xie et al., 202 la; Zanette et al., 2021; Yin et al., 2022: Huang et al., 2023) to the broader and more general setting of function approximation (Chen Jiang, 2019; Liu et al., 2020; Xie Jiang, 2020a; Foster et al., 2021b; Xie et al., 2021a; Cheng et al., 2022; Zhan et al., 2022). As algorithms and accompanying theoretical results for tabular MDPs and low-rank MDPs are incompatible with complex problems attributable to the enormous states/actions or the complicated dynamics, general function approximation is often favored.
From the perspective of practical applications, general function approximation also enjoys its own significance. It characterizes how the approximation power and the complexity of approximators (c.g., support vector machine (Cortes & Vapnik, 1995) and neural net (Goodfellow et al., 2016)) jointly affect the performance of learning algorithms. In the analysis of offline RL, the approximation powers of function classes can be categorized into types (Chen & Jiang, 2022; Zhan et al., 2022; Ozdaglar et al., 2022; Mao, 2023): realizubility-type and completeness-Ispe. Given a function class F and an approximation target F the assumption F F is considered realizability-type (F is
Corresponding authors: Zhen Wang (w-zhen @ wwwpu.ed..cn) and Xuelong Li (xuelongll@iicce.oogg li@icce.org). Xue- long Li is the Chief Technology Officer (CTO) and the Chief Scientist of the China Telecom.

---

Published as a conference paper at ICLR 2024
then called realizable) [F (e. exists a (known) bijection between F and another realizable function class G. Most theoretical algorithms and analyses assume an exponentially large function class to achieve realizabiliity assumptions and provide sample-complexity guarantees that are polynomial in (og()F)). As a consequence, completeness-type assumptions can lead an exponential performance bound since the approximation target itself may be exponentially large. Moreover, one of the most common completeness-lype assumptions is Bellman- compleeeeco (the value function class is closed under Bellman backup), where two function classes (e.g.. F and G above) are identical. This form of "self- completeness" is more stringent because the performance guarantee may be violated by just adding one function into the function class (in contrast to the general intuition in supervised learning (Chen & Jiang, 2019)). Thus, in most cases, realizability-typp assumptions are preferred.
and is considered completeness- tyye if there
The assumptions of functions are also impacted by the quality of the dataset, which forms another aspect of learnability in offline RL. On one hand, Xie & Jiang (2020a) shows that realizability-tye assumptions (concretely, Q" "r-reaiizabilitt) combined with data assumptions that are even stronger than the classic and stringent exploratory coverage (Precup et al. (2000); Antos et al. (2006); see also Section 2.2), are enough for learning near-optimal policy. 2 On the other hand, there are works (e.g.. Liu et al. (2020); Xie et al. (2021a); Rashidinejad et al. (2022); Zhu et al. (2023)) showing that with some mild completeness-type assumptions, even a dataset with partial coverage is enough for learning good policy. However, despite numerous efforts devoted, no work has yet achieved learnability under both weak assumptions on function classes and datasets. This raises the question: what are the limitations of general function approximation in offline RL?
In learning theory, the fundamental limitations of problems are often identified by the minimax lower bound. However, establishing such lower bounds becomes a challenging task when dealing with general function approximation in offline RL. This is primarily due to the significant variation in the functions that want to approximate and the relationships between them. What is even worse is that establishing lower bounds for certain properties does not necessarily imply a fundamental barrier to learnability. For instance, if lower bound is established for value functions, it does not necessarily imply that the problem cannot be learned. Additional assumptions on properties such as the density ratio (Liu et al., 2018; Uehara et al., 2019) may make it learnable.
This paper enhances the understanding of general function approximation in offline RL in the following aspects:
1. (Section 3) Following the insight from Chen Jiang (2022); Zhan al. (2022); Ozdaglar et al. (2022); Mao (2023), we classify function assumptions in offline RL into completeness-type and wealizability-typee Based on this taxonomy, we analyze their practical usage and demonstrate that completeness-type assumptions are often necessary to approximate targets for every possible policy in algorithms.
2. (Section 4) We show that function classes in RL can be viewed as restriction possible MDPs. We can concretize this restriction as model-realiaabiliyy i.e., the assumption that we have a MDP class M containing the real MDP. This allows us establish lower bounds for model-realizability and extend them to other function classes.
3. (Section 5) We propose a generic lower bound in Theorem for general function approximation. Based on the principle of lower bound construction presented in Section 4, we derive some interesting corollaries from Theorem 1:3
(a) Informal version of Corollary 1: Given realizability-tye assumptions on the value function and the density ratio for a specific policy within a policy class, along with "any" data-coverage assumption, we cannot learn a better policy than the aforementioned one.
(b) Informal version of Corollary 2: Given exploratory-accurae realizability--yy assumptions on any functions that take the state space as input for specific policy within a policy class, along with "any" data-coverage assumption, we cannot learn better policy than the aforementioned one.
2 Theei data assumptions require that (i) the state margin of the data distribution both scales with the transition kernel and scales with the initial distribution, and (ii) for every state, the behavior policy (i.c., the conditional distribution of the action given that state, which is derived from the data distribution) should cover all actions. See Section 3 for the definitions of citoorattor--ccuurao and behaviour-accurayy
2

---

Published as a conference paper at ICLR 2024
(c) Informal version of Corollary 3: Given behaviour-accuratt realizability-type assumptions on any functions for a specific policy within a policy class, along with "any" data-coverage assumption, cannot learn better policy than the aforementioned one.
4. (Section 6) We augment results from Section 5 with Q' Q'-realizability at the cost of introducing partial coverage (Theorem 2). A limitation of this augmented lower bound is that the covered policy is not optimal.
PRELIMINARIES AND RELATED WORKS
This section introduces basic settings and concepts in offline RL. See Table in Appendix A for the full list of notations.
2.1 MARKOV DECISION PROCESSES (MDPS)
This paper studies infinite-horizon discounted Markov Decision Processes (abbreviated as MDPs for short). An MDP is characterized by tuple (S, P. R. Mo. ?), where S is the state space, AA is the action space, S A - ((S) is the transition kernel, R S A + [0. Rmax]] is the (deterministic) reward function," Nr A(S) is the initial state distribution, and [0, 1) is the discount rate. We use v to denote the uniform measure of A. S, or S x A, depending on the context. We will add a subscript M to certain symbol (e.g.. PAr) when we want to highlight the dependency with specific MDP M. A policy : S + ((A) is a mapping from the state space to a distribution on the action space, 5 and with a slight abuse of notation, we sometimes use π to denote deterministic policies. We say policy induces (random) trajectory {So, dn, ru. $1, 41, ................................ St. Qg, Ti, Si+1,...] if S Sy-1
so ~ Po. a; ~ T-((s)). r3 R(s;, 0z),
N. For a policy T,, we define its value function as the expected return from specific state or a state-action pair, i.e., (8) BIEi=o? 7*ri|80 = 8, 02 T T-|[s))] and Q= a) == TR[ T1
P(-ss, a;) for all
= 8, ag = a, 04 ~ o (-[+:)] Since Ti [0, Rmax]. the value function is upper bound by Vmax == Rmax/ 7). We denote Q* as the unique solution of the celebrated Bellman-optinn opttmmllty equation and name it as optimal value function. The state version of Q is defined as (s(s) max (*,s,, a). We assess the performance of æ through the expected return from the initial state so that follows from μo: [Tr = Ex-po [Vr (s)]. We also define J max, (Tr) the optimal return, and take policy т as an optimal policy if ((T) J We say that a policy is optimal everywhere if its state value function is V*, and such a policy is denoted m². For a policy and a transition kernel P, we define the state transition kernel Px S + ASS) as (s'(s) = ʃA P(s (s, (a)(s))dr((). An S-trajectory of a policy π is a sequence {8u, ro, 81, f1,-.., 81, Tr, 1:+1....} such that sp ~ Ao,, Pi = Easx((es)) [[ss,, a)], 8:41 ~ P=(+ for all E N. The induced distribution on the state-action pair of a policy π is defined as dz (8,a) a) = (1 -7) [E 7 (s; = 8, ag = al8o Mo, r)] (o, In certain cases, we may come across trajectories and induced distributions that do not originate from po. However, unless specified otherwise, we default to using μo as the initial distribution.
2.2 OFFLINE POLICY LEARNING
In the general framework of offline policy learning, are given dataset 'D consisting of N i.i.d. (s, r')') tuples. Given a data distribution d', the dataset 'D collected such that (s, a) ~ dD, R(s, a) and s' P(-|s, a). A learning algorithm, that is denoted as 21 is mapping from the dataset D to a policy Ā.
Difficulties in offline policy learning arise from limited access to pre-collected datasets, with no further interaction with the environment permitted. The representability of the dataset, which determines the fundamental limit of algorithms, is often evaluated through the concentration coefficient (Munos, 2003; 2005). The concentration coefficient measures the distribution shift from the data distribution d' to the induced distribution of some policies. Concretely, the classical exploratory coverage assumption assumes that there exists a constant Ceep such that for any (sometimes also non-stationary) policy x, Cesp 2 +
Il.. The partial coverage assumption (Liu et al., 2020; Xie et al., 2021a), 1)), on
the other hand, assumes that there exists a constant pprr such that for some policy n, Cpar 2 d Ilac
$ Stoohasttic rewards contain deterministic rewards. Thus, our lower bound can also be applied the stochastic reward setting.
*This paper primarily focuses on stationary policies. Non-stationary policies, which can change over different. steps, denoted as Tnon-
3

---

Published as a conference paper at ICLR 2024
The learning goal (i.e., the criterion of learnability) in offline RL is to obtain policy that is least no worse than the covered one (i.e., if π is covered, J()) 2 J(T) asymptotically).
2.3 GENERAL FUNCTION APPROXIMATION
General function approximation RL a broader framework that extends beyond tabular MDPs or low-rank MDPs. It is assumed that we have some function classes with good properties (c.g.. contain- ing the approximation target) while still maintaining limited complexity (measured by cardinality, metric entropy, etc.). Most works allow function classes have exponential cardinalities covering numbers. The complexity of function classes is determined by the complexity of the underlying MDPs. Thus, these modeling assumptions can also be viewed as implicit structural assumptions for MDPs. Further, when considering algorithm designs and analyses in tabular or low-rank settings, careful investigations suggest that the structures of MDPs are influential because of their role in function classes modeling (e.g., modeling state-action value functions or transition kernels) and some structure-specific quantities (e.g., the feature covariance matrix). In particular, generalizing these structural-specific quantities to complex real-world problems is much more challenging. Thus, general function approximation is erucial when considering algorithm design in RI..
From a historical perspective, the analyses of offline RL with general function approximation are extended from approximate dynamic programming (ADP; Bertsekas & Tsitsiklis (1996); Munos (2003; 2005)). Works in the early stages mainly focus on the error propagation bounds in the process of dynamic programming. For instance, in policy iteration, how errors from value estimation in each step affect the finally approximated optimal value function. Later on, the complexity of the function classes being used (mainly the value function class) and non-asymptotic analyses for the dataset are taken into consideration (Szepesvari & Munos, 2005; Antos et al., 2006; 2007; Munos & Szepesvari, 2008). Through the development, concepts like concentration coefficient and Bellman-com compleeessss are proposed, and strong assumptions on both function classes and datasets are considered necessary for learning near-optimal policies (Chen& Jiang, 2019). The lack of understanding of the fundamental requirement of offline RI was first noticed long later by Chen & Jiang (2019), and it asks if learning under weaker assumptions is possible for offline RL. From then on, there have been emerging works proposing PAC-learnable algorithms under either mitigated assumptions 2020; Liu et al., 2020; Xie & Jiang, 2020a; Uehara & Sun, 2021; Xie et al., 2021a; Cheng et al., 2022; Rashidinejad et al., 2022; Zhu et al., 2023) despite these advancements, comprehension of general function approximation (e.g., how different assumptions interact and play their roles) is still lacking.
dataset (Jiang & Huang,
function classes (Xie & Jiang, 2020a). However,
2.4 LOWER BOUNDS IN OFFLINE RL
While cntemattion-thoorede lower bounds have been extensively studied in both tabular MDPs (Rashidinejad et al., 2021; Xie et al., 2021b; Li et al., 2022) and linear MDPs (Jin et al., 2020; Wang et al., 2020; Amortila al., 2020; Zanette, 2020; Chen al., 2021; Wang et al., 2021), lower bounds considering general function approximation in offline RL. are still lacking. The most notable work is Foster et al. (2021a), demonstrating that learning impossible without Bellman- completeness, even in the presence of an exploratory dataset. However, their lower bounds are limited since they only consider value functions and are value-based, while recent years have seen the significant development of newly proposed properties such as the density ratio. The complexity and difficulty of analyses general function approximation explode for the increasing number of properties we can model. Moreover, the fundamental requirement of learnability in general func- tion approximation- which properties we should approximate and what assumptions we should demand- is still unclear.
3 ON THE PRACTICAL USAGE OF GENERAL FUNCTION APPROXIMATION
Recall that in the analysis of general function approximation, the assumptions can be categorized into two types: realizability-type and completeness-type (Chen & Jiang, 2022; Zhan et al., 2022; Ozdaglar et al., 2022; Mao, 2023). Since the gap between these two types of assumption sometimes vague in previous works, we first formalize our discussion with some definitions.
Definition 1 (Realizability -typ assumption). Given function class F and target function class F., we say that the assumption F C F is realizability- type if [F = (we can thus denote F {f*}), and say that F is realizable under this assumption.
4

---

Published as a conference paper at ICLR 2024
Additionally, an exploratory-accure realizability-type assumption assumes that F* is only accurate under the induced distribution of any non-stationary policy, i.., VT m
f dlo..d 0. A behaviour accuurate realizability-type assumption assumes that F is only accurate under the induced distribution of a specific policy æ, i.e., minfezlls flo,, = 0. In the above definition,
| denotes the q-weighted LP norm, i.c., ||=||p. = (ʃ =gdq) 2/P
Example 1 (Example of realizability -tppe assumptions). We have state-action value function class @ C (S x A + 00, Vmax] such that { S Q. Corresponding to Definition 1, we thus have F {Q*} and F F
Definition 2 (Completeness--y type assumption). Given a function class F and a target function class F', we say that the assumption F S F completeness-type [F [g] for another realizable function class G, and we say that F is complete with respect to (w.rt.) G under this assumption.
Example 2 (Example of completeness-type assumptions). We have a policy class II S (S -> ((A)) and a state- catt-acctin value function class Q ( x A + [0, Vmax]). We assume that x² E II. The assumption that [Qa т E [I] C Q is completeness-lspe, and we say that Q is complete w.E.l. II under this assumption. Corresponding to Definition 9 g= IT.
thus have F = [Qx| E II,
Q and
Remark 1. The completeness-type assumption commonly used to ensure the existence of a function class that can minimize set of loss functions indexed by another function class.
Completeness-type type assumptions are common but may be harmful. Intuitively, making a completeness- type assumption is like making as many realizability- assumptions the number of functions in another realizable function class. This tiered structure would introduce a dilemma in the approximator design. Assuming that F is complete w.r.t. 9, one may wish to be rich enough to capture the approximation target of itself. However, even adding just one function into G may break the completeness-type assumption on JF, rendering the guarantees associated with this assumption no longer applicable.
Remark 2. Although the richness of function classes would also affect the generalization error, the influence is monotonic in sample complexity and can be mitigated by large samples. This contrasts the completeness-tye assumption since it can induce a constant performance gap for having just one more function in the function class (which is referred to non-monotonic, therefore).
Moreover, constructing a function FF that can model [g] targets is overly complicated and can spoil the final results. For universal approximator without prior knowledge, assuming that we can approximate a single target (in cases of realizability-type assumptions) with an exponentially large function class (matching the classical log sample complexity bound), complete function class would be sooubly-xxponentialy. large. In such situation, the sample complexity, measured in terms of the polylogarithm of the cardinality of the complete function class, would become exponentially large. This renders it impractical and no longer meaningful."
Why do we need completeness-type assumptions In RL, the primary goal is to learn policy that meets certain criteria. We argue that most algorithms in RL can be considered "policy-based" and are designed with a specific set of policies in mind. For instance, value-based methods focus on updating policies that take actions with the highest value each state for each value function, and model-based methods would consider optimal policies under the MDPs from the model class. Policies considered in these methods are pre-defined even before algorithms start. This means that most algorithms in RL can be regarded as those that take a policy class II, a function class F. and set of assumptions as input. Completeness -ytee assumptions are required to approximate targets well for each π E II.
Example 3. The Fitted Q-iteration requires a state-action value function class satisfying Bellman- completeness, i.e., given a state-action value function class Q C (S x A [0, Vmax)), for each
'In the case that f is defined on S instead of S x A, we can substitute d, with its state margin pax Forr example, the typical union bound would introduce logarithmic dependency sample complexity, whichever function class we use. If we can approximate a target with a function class with cardinality exp(C)) (C). as the completeness- type assumption requires us to approximate exp(C") targets, the cumpleteness-typ as- sumption would require function class with exp(exp(C") elements. The sample complexity bound would be log(ex)(exp(C)) exp(C).
5

---

Published as a conference paper at ICLR 2024
q E Q. we have its Bellman update Tq contained by Q. It can be regarded pholicy-based such that II= { q E 2}, == Q, and assumess that there is a known mapping & (maps from q to Tg) such that for all ı E TT, F for all f E Φ (m).
In the above example, T denotes the Bellman operator, "q denotes the optimal policy for q. and T denotes the Bellman operator policy n.
Two instances that contradict the aforementioned statements are model-realizabiiity and the algorithm from Xie & Jiang (2020a). On one hand, while the upper bound for model-realizability has already been proposed (Uchara & Sun, 2021), reall-tealizability subsumes completeness-type assump- tions (cf. Proposition 3). On the other hand, Xie & Jiang (2020a) use discretization to ensure good approximations for refined Tq for each q, and they require dataset with quite strong coverage assumptions that are a bit unrealistic.
In summary, want to ask:
Question 1. Can we learn good policies without approximating targets well for all π E II?
To provide more concise presentation, we will first introduce insights and tools related to learnability and general function approximation in the next section. This will provide the necessary background for answering Question 1.
4 ANATOMY OF GENERAL FUNCTION APPROXIMATION APROPOS OF LEARNABILITY
This section provides a detailed analysis of general function approximation in offline RL. with a focus on learnability.
On the role of function classes A reinforcement learning problem can be defined by an MDP M, supplemented by additional information in the form of a function class F and set of assumptions A. F is allowed to encompass multiple function classes through cartesian products. From a theoretical perspective, it is crucial to understand the significance of F in the context of tifoori lcarnability, A key insight into this problem is given by the well-known definition of the minimax lower bound, which we denote as L.
C(F,A) = min max (EM(F.A)
C(),,M.
where C is a real-valued objective function we can ask algorithms to minimize, and M A) enumerates all possible MDPs with A satisfied w.r.t. F we may encounter.
The "max" part of Eqn. (1) can be understood as the presence of an adversary who selects the worst-case MDP from M(F A) for algorithms. Specifying to the concrete problem, there a real model M* that serves the ground truth. Note that M* E EMFF, A) by the definition of MMF,, A). In other words, The adversary can only select elements from M(F,FFF A) as the real model M*. To summarize, Eqn. (1) asserts implicitly that: function class JF and assumption set A are restriction on possible underlying MDPs that the adversary can select.
Remark 3. In offline RL, we are also given a dataset D with data distribution dP, With slight abuse of notations, one can view D as a part of F, dd as a part of the MDP M, and the assumptions on the dataset D part of A, respectively. These inclusions are only assumed in this section.
Modii-iraliaabilit:: a principle for lower bound construction Lower bounds for general function approximation are inherently specific the type of function being considered. It is often believed that lower bounds derived for one type of function are not applicable to another. However, this is not the case for nodel-realizabilityy We argue that the lower bounds derived for model-realizabiliy can also be applied to other types of functions. For any function class F, we denote (((FF as the set of all possible algorithms taking F as inputs. We denote F(M, A) as a constructed function class from M and A such that A is satisfied for all M E M. It is assumed that the construction process is known. Proposition below shows that lower bounds for a realizable M (M* E M) apply to F(M, A) for any A.
Proposition 1. Algorithms taking F(M, A) as inputs must perform no better than the best algorithm
that takes the realizable M as input in the worst case:
min (EAA((MAA) (MM))
max
C(21, M) > min max C(2, M).
(2)
(EA((M) MEM

---

Published as a conference paper at ICLR 2024
Proposition 1 can be justified by the facts that: (i) the set of algorithms taking F(M, A) imputs is a subset of the set of algorithms that takes M as imputs (we can transfer before applying algorithms); and (ii) the set MMF(M A), A) is superset of the MDP class M. The significance of Proposition I is that provides a general principle for lower bound construction: one can first establish lower bounds based the assumption of model-realizabblity, and then extend the bound to any function that may not have been accessible previously.
more detailed discussion of how can construct JF from M and A is deferred to Appendix C due to the page limitation. Moreover, F may also depend on properties other than M (e.g. the value function of policy). This type of functions is related to completeness- type assumptions. We also defer the elaboration of this to Appendix C.
Remark 4. It worth noting that upper bounds for partial concentrability and model realizability have been established in previous works (e.g., Uehara & Sun (2021)). As consequence, the lower bound we establish for M requires certain weakening of assumptions.
LOWER BOUNDS UNDER STRONG DATA ASSUMPTIONS
This section provides a negative answer to Question I, even when the policy class II only contains two elements. We first interpret Question I through the goal presented below.
Goal. Given dataset D, a policy class I1, a function class F, and a set of assumptions A, we wish to learn a policy सt such that ( 2 (TT) for any policy T. while only assuming that we can approximate certain targets for न.
This goal is closely related to the target of robust policy improvement (Cheng et al., 2022). Our data assumption is modified from Xie & Jiang (2020a), and is stronger than classic partial coverage or exploratory coverage assumptions, as well as the more refined data assumptions presented in recent years (Xie Jiang, 2020a; Uehara et al., 2023). The primary lower bound is presented in Theorem 1. A detailed comparison with assumptions in previous works is deferred to Appendix F.
Theorem 1. For any sample size N and y E [0, 1), there exist a family of MDPs M with the same functionn state-action spaces, a reward function R, a transition kernel P, a dataset 'D with distribution dp, policy class 11, a state-action value function class and a state transition probability class Ps, such that
1. du
16 for any (possibly non-stationary) policy Tuea and for all M M,
du
2. the behaviour policy vs (obtained from dP) satisfies Ta 8) 2 for all 8 E and A.
3. the state margin μP (obtained from d') satisfies PM(s' s,a)/p((s') I for all s e S, A, s' E S and M E M,
4. |A| = 10=121- = (Psl = III = 2,
5. R is the reward function for all M E M,
6. there exists a (unknown) mupping & E -II such that for all M E M.
{(M) has its state-action value function realized by Q (i.e Q..(MM) E Q) the state transition kernel of E(M) is realized by Ps with exploratory-uccuracy i.e. 3Ps Ps. such that for all (possibly non-stationary) policy Taaa. PPs PM..(M))looodd =0,
.P is partially accurate under the induced distribution of {(M) (i.e., ||
PM Par (olloodde 0).
Any learning algorithm A which takes S, A, R, No: D.D. d,II,, Q. and Ps as input and outputs a policy 7-must satisfy
(M(((MM)--[JMM( 22
max MEM
We define 0/0

---

Published as a conference paper at ICLR 2024
Moreover. for all M M, have that Jxr(5(M)) Jās-
Remark 5, While we are provided with the policy class II, the learner has the freedom to select policies that do not belong to II.
Our counterexample construction technique inspired by the concept of "over-coverage" from Xie Jiang (2020a); Foster et al. (2021b). Through the function transfering principle presented in Section 4, several interesting corollaries can be derived from Theorem These corollaries are presented in Section 5.1 below.
We defer the proofs for this section to Appendix D.
5.1 INTERPRETION OF THEOREM
To answer Question 1, we need first clarify what are the targets of a policy.
Definition We say that a function mapping from S A or S is x-related for each entry of this function, we can calculate its value from the induced trajectory of a from this entry. A function mapping from (u, ---rllated if we can calculate its values from the induced S-trajectory of from each entry.
Qu is x-related since its value for each (s,a) E S x A is the sum of the cumulative rewards of the trajectory thereby. Moreover, Vn (IT, S-rrelated.
Example 4.
First, response to marginalized importance sampling (MIS), show in Corollary 1 that the realizability w.r.t. the density ratio is insufficient for learning a better policy. We denote the density ratio class as W C. (S policy π is defined as wx (s, a) = dg (s, a) (s,
[0. W max)) where max constant, while the density ratio of
Corollary 1. Under the condition of Theorem 1, any algorithm that also takes W, which has the density ratio realized (VM E M, Wg(ar) E W) and only contains 4 elements, as input must have maxMeM (Ja(E(MM) (f))( 2
The following corollary shows that modeling any function defined on S (as consequence of Ps) with peploratory-accuraae is not enough for learning a better policy.
Corollary 2. Under the condition of Theorem for any function (which we denote as f*) we want approximate that is (T. rrelated for certain E II specified by &, we can construct a function class F such that
only contains four elements,
2. for all M E M, there exists f E F such that for any (possibly non-stationary) policy Tnon-
|f firll
Algorithms from Theorem that also take F as input must have maxMEM (JM(E(M))
E (f)(
Furthermore, modeling any --related function that accurate under the induced distribution of π (as a consequence of P) is not enough for learning better policy.
Corollary 3. Under the condition of Theorem for any function (which we denote as f*) we want to approximate that is x-related for a certain x E II specified by &, we can construct fuuucttoon class FF such that
1. F only contains two elements,
2. for all M -,, there exists f F such that f f (or flf flo,
0 if f is defined S).
Algorithms from Theorem 1 that also take F as input must have maxMEM (JMM)
E [[)M( 2
Thhss is primarily dependent M M since & is also function of M.
8

---

Published as a conference paper at ICLR 2024
5.2 LIMITATION OF THE LOWER BOUND
The major drawback of Theorem is the use of "over-coverage" our dataset covers states that are unreachable from the initial state. Another concern may be that while {(M) can be optimal, the value function class Q does not contain the optimal value function Q .owweerr,, the exclusion of
Q* unavoidable since Xie Jiang (2020a) has proposed an upper bound under the condition of Q' realizability under weaker data assumptions compared with ours.
ON EXACTLY Q"-REALIZABILITY
The seminal work Xie & Jiang (2020a) presents an algorithm with state abstraction, showing that Q* Q'-realizability, together with their refined data assumptions, is enough for learning near-optimal policies. Since the data assumption in Theorem is stronger than the one from Xie Jiang (2020a), Theorem I is, of course, incapable of Q"-realizability. This section bridges this gap by showing that even with Q"-realizability, learning near-optimal policies is impossible under the weaker partial coverage data assumption.
Theorem 2. For any sample size N and E [0, 1), there exist a family of MDPs M with the same state-action spaces, reward fanction class R, a transition kernel P, dataset DD with distribution dP, a policy class II, state-action value function class Q, a state trunsition probability class Ps. such that
1. A = iPs - - 1
2. for all M M, Qi E and RM R.
3. there exists a (unknown) mupping & E (M II) such that for all M E M,
decs Ilee S 32,
E(M) has its state-action value function realized by Q (i.e. QM.((M) E 2),
the state transition kernel of {(M) is realized by Ps with exploratoryaccuurcy (i.e., 3Ps E Ps, for all (possibly non-stationary) policy nno PPs PM..(an)llooooo 0),
P is partially accurate under the induced distribution of E(M) (ie., ||P
PM (ooloon = 0).
D. Any learning algorithmm 2 which takes S,A, R. no: Y,, dP, dDP, III Q, and Ps as input and outputs policy 7-must satisfy
72
(JA(E((M)) MEM
16'
The proof of Theorem is provided in Appendix E.
limitation of Theorem 2 that while this counterexample considers Q*trealizability, the dataset does not cover the optimal policy. However, we argue that this result is still interesting since allows the function class contain the corresponding functions of the covered policy, and the dataset with partial coverage that does not cover optimal policies is more prevalent in real-world scenarios. Moreover, this theorem demonstrates the impossibility of achieving robust policy improvement with Q' -realizability.
CONCLUSION
This paper serves as an elaboration on offline RI. with general function approximation. We clarify different types of function assumptions of offline RL Rl-nay the completeness-type and the realizabilliy-tyye-
providing clear definitions and analyzing their practical usage. We interpret completeness-type assumptions all possible policies considered the algorithm. To determine the necessity of this requirement, we delve into the role of general function approximation in offline RL on learnability, and also propose principle for establishing lower bounds. With the help of this principle, we propose two lower bounds showing the necessity of completeness-type assumptions.
typical requirement for the good approximation of targets under

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work is supported by the National Science Fund for Distinguished Young Scholars (No. 62025602), the National Natural Science Foundation of China (No. U22B2036), the Tencent Foundation and XPLORER PRIZE, and Shanghai Artificial Intelligence Laboratory. We also thank anonymous reviewers for their valuable comments and suggestions.
REFERENCES
Philip Amortila, Nan Jiang, and Tengyang Xie. variant the wang-foster-kakade lower bound for the discounted setting. ArXiv, abs/2011.00 1.01075, 2020.
András Antos, Csaba Szepesvari, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71:89-129, 2006.
András Antos, Rémi Munos, and Csaba Szepesvári. Fitted q g-iteration in continuous action-space mdps. In NIPS, 2007.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Mohak Bhardwaj, Tengyang Xie, Byron Boots, Nan Jiang, and Ching-An Cheng. Adversarial model for offline reinforcement learning, 2023.
Jinglin Chen and Nan Jiang. Information-thhoortii considerations in batch reinforcement learning. ArXiv, abs/ ftbs/1995.00360, 2019.
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-rati realizability: the power of gaps. ArXiv, abs/2203. 13335, 2022.
Lin Chen, Bruno Scherrer, and Peter L. Bartlett. Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm. ArXiv, abs/2103.098477, 2021.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. ArXiv, abs/2202.02446, 2022.
Corinna Cortes and Vladimir Vapnik. Support networks. Machine learning, 20(3):273-297 1995.
Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. ArXiv, abs/21 12. 13487, 2021a.
Dylan J. Foster, Akshay Krishnamurthy, David Simchi-Levi and Yunzong Xu. Offline reinforce- ment learning: Fundamental barriers for value function approximation. In Annual Conference Computational Learning Theory, 2021b.
I. Goodfellow, Y. Bengio, and Courville. Deep Learning. Adaptive computation and machine learning, MIT Press, 2016. ISBN 9780262035613.
Omer Gottesman, Fredrik D. Johansson, Joshua Meier, Jack Dent, Donghun Lee, Srivatsan Srinivasan, Linying Zhang, Yi Ding, David Wihl, Xuefeng Peng, Jiayu Yao, Isaac Lage, Christopher Mosch, Li wei H. Lehman, Matthieu Komorowski, A. Aldo Faisal, Leo Anthony Celi, David A. Sontag, and Finale Doshi-Velee Evaluating reinforcement learning algorithms in observational health settings. ArXiv, hbb//8855.1299. 2018.
Omer Gottesman, Fredrik Johansson, Matthieu Komorowski, Aldo Faisal, David Sontag, Finale Doshi-Velez, and Leo Anthony Celi. Guidelines for reinforcement learning in healthcare. Nature Medicine, 25:16 - 18, 2019.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-38) 1963. ISSN 01621459. URL http: www. jstor wwtp:/tttl////////ee..
10

---

Published as a conference paper at ICLR 2024
Audrey Huang, Jinglin Chen, and Nan Jiang. Reinforcement learning in low-rank mdps with density features. ArXiv, abs/2302.02252, 2023.
Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. arXiv: Learning, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang- Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, 2020.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, and Sergey Levine. Scalable deep reinforcement learning for vision-based robotic manipulation. In Aude Billard, Anca Dragan, Jan Peters, and Jun Morimoto (eds.). Proceedings of The 2nd Conference on Robot Learning. volume 87 of Proceedings of Machine Learning Research, pp. 651 PMLR, 29-31 Oct 2.18. URL https:
mlr prwssrrssvsee.. v ppwpss/vv//aaaaaankkkk.... http//aaaaaaaankaa www.hhiiikviaa..mm html.
Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey, 2021.
Sascha Lange, Thomas Gabel, and Martin A. Riedmiller. Batch reinforcement learning. Reinforce- ment Learning. 2012.
Sergey Levine, Aviral Kumar, G. Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. ArXiv, abs/2005.01643, 2020.
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning. ArXiv, abs/2204.05275, 2022.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. In Neural Information Processing Systems, 2018.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. ArXiv, abs/2007 008002, 2020.
Chenjie Mao. Offline reinforcement learning with additional covering distributions, 2023.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Joannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. ArXiv, abs/1312.5602,, 2013.
Rémi Munos. Error bounds for approximate policy iteration. In International Conference on Machine Learning, 2003.
Rémi Munos. Error bounds for approximate value iteration. In AAAI Conference on Artificial Intelligence, 2005.
Rémi Munos and Csaba Szepesvari. Finite-time bounds for fitted value iteration. J. Mach. Learn. Res., 9877 2008.
Asuman F. Ozdaglar, Sarath Pattathil, Jiawei Zhang, and K. Zhang. Revisiting the linear-programmingg framework for offline rl with general function approximation. ArXiv, abs/2212. 2022.
David F. Pollard. Empirical processes: Theory and applications. 1990.
Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge University Press, 2022. URL https::/peopppeeee lids mit mit.teeu///ee.i edue yp /homepage///aaa/////// itbook brrbook-xxpor..poo
Doina Precup, Richard S. Sutton, and Satinder Singh. Eligibility traces for off-policy policy evaluation. In International Conference on Machine Learning, 2000.
Paria Rashidinejad, Banghua Zhu, Cong Ma. Jiantao Jiao, and Stuart J. Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. IEEE Transactions on Information Theory, 68:8156-81 2021.
11

---

Published as a conference paper at ICLR 2024
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao. Optimal conservative offline with general function approximation via augmented lagrangian. ArXiv, abs/2211.0071e 2022.
David Silver, Aja Huang. Chris Maddison, Arthur Guez, Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam,, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484 489, 2016.
Matthew Skala. Hypergeometric tail inequalities: ending the insanity, 2013.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
Csaba Szepesvari and Rémi Munos. Finite time bounds for sampling based fitted value iteration. Proceedings of the 22nd international conference Machine learning, 2005.
Shengpu Tang, Maggie Makar, Michael W. Sjoding, Finale Doshi-Velez. and Jenna Wiens. Lever- aging factored action spaces for efficient offline reinforcement learning in healthcare. ArXiv, abs/2305.01738, 2023.
A. Tsybakov. Introduction to nonparametric estimation. In Springer Series in Statistics, 2008.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. International Conference Learning Representations, 2021.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference Machine Learning, 2019.
Masatoshi Uehara, Nathan Kallus, Jason D. Lee, and Wen Sun. Refined value-based offline under realizability and partial coverage. ArXiv, abs/2302.02392,, 2023.
Aad W. Vaart and Jon A. Wellner. Weak convergence and empirical processes: With applications to statistics. Springer New York, NY, 1996.
Ruosong Wang, Dean Phillips Foster, and Sham M. Kakade, What are the statistical limits of offline with linear function approximation? ArXiv, abs/2010. 18895 2020.
Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, and Sham M. Kakade. Instabilities of offline with pre-trained neural representation. In International Conference Machine Learning, 2021.
Xinqi Wang, Qiwen Cui, and Simon Shaolei Du. On gap-dependent bounds for offline reinforcement learning. ArXiv, abs/2206.00177, 2022.
Wikipedia. Hypergeometric distribution Wikipedia, the free encyclopedia. http://en www.leeeeeerreemmmmeee wiiiaiittttttttiiiooooo oldid=116700533 2023. [Online; accessed 04-August-2023).
wikipedia http:///a.../////////////// Indxx.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. ArXiv, abs/2008.04990, 2020a.
Tengyang Xie and Nan Jiang. Q" approximation schemes for batch reinforcement learning: A theoretical comparison. ArXiv, abs/2003.00 003924, 2020b.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. In Neural Information Processing Systems, 2021a.
Tengyang Xie, Nan Jiang. Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. In Neural Information Processing Systems, 2021b.
Tengyang Xie, Dylan J. Foster, Yu Bai, Nan Jiang, and Sham M. Kakade. The role of coverage in online reinforcement learning, 2022.
12

---

Published as a conference paper at ICLR 2024
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous q-learning. ArXiv, abs/2203.07368, 2022.
Yuhong Yang and Andrew R. Barron. Information-thcorrtiic determination of minimax rates of convergence. Annals of Statistics, 27:1564-1599, 1999.
Ming Yin and Yu- Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. In Neural Information Processing Systems, 2021.
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. ArXiv, Abs/2203.05804, 2022.
Bin Yu. Assouad, Fano, and Le Cam, pp. 423-435. Springer New York, New York, NY, 1997. ISBN 978-1-4612-1180-7, doi:
1-8--11--18-72999 URL https://ddo. org/
10.1007 91117799881-5-888 4612 188007_29.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch can be exponentially harder than online rl. In International Conference Machine Learning, 2020.
Andrea Zanette, Martin J. Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. In Neural Information Processing Systems, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D. Lee. Offline reinforcement learning with realizability and single-policy concentrability. ArXiv, abs/2202.04634, 2022.
Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement learning. ArXiv, abs/2301. 2023.
13

---

Published as a conference paper at ICLR 2024
A
NOTATIONS
Table 1: Notations.
T
Bellman operator, Ts(s, a) = R(s, a) + E ~( max f(s'
T"
Bellman operator policy я, 7 [{s,a) = R(s, a) + PlB..Pttll.a [s', [s'),a)] uniform distributions distributions on X
Xni
(e.g., normalized Lebesgue measure for subsets of R
A(X
state space
A
action space
Q
state-action value function class state-action density ratio function class state value function for policy π state-action value function for policy optimal state value function optimal state-action value function induced distribution of density ratio of Wn (s, a) = (s, a)
W
V
Q
V
Q*
dR
(1-))) s,a; = also μo, m)
Ur
uniform measure of A, S, dataset used in the algorithm
A, depending on the context
D
d
state-action distribution the dataset
P
state distribution of dataset (margin of dP)
Tg
policy that takes actions that maximize value function q in each state, (s(s) argmax ((8)))
behaviour policy (s(s a) = (s, if p(s)) > 0
Tb
v(aa) otherwise.
M40
initial state distribution
di >> d2
d2 is absolutely continuous w.r.t. d1
E
the complementary event of F. the law of events under MDP M with size N, mainly used for datasets the law of events under MDP M with size 1, mainly used for datasets Px (b'1s) = [A P(s'|s, a))(ala (a)s)dee((() total variation distance between IP and Q x2 -ivvergeece between TP and Q
PN
PM
Pa
TV(P, Q
(PP,QQ
||>||p
q-weighted L norm, |æ]|p- = V Pg
While т, μ. and are mainly used to denote the Radon derivatives of the underlying probability measures w.r.t v, we sometimes also use them to represent the corresponding distribution measures with slight abuse of notations.
B HELPER LEMMAS
Lemma (Hypergeometric tail bound (Hoeffding. 1963; Skala, 2013)), Let N, be a hypergeometric random variable, and define = K/N. For any pN' 2 2220,
P[X P PN' 2 NN 5 exp(-2222
Lemma For any probability space defined with a sample space Ω, a sigma-algebra E, and probability measures F and Q, the total variation distance between the conditional measures is upper bounded by the origin one:
VE E, TV(P,Q) 2 TV(P(- E),Q( (()))
Je follow the definition from Wikipedia (2023y: the hypergeometric distribution is a discrete probability distribution that describes the probability of X successes (random draws for which the object drawn has specified feature) in N' draws, without replacement, from finite populotion of size N that contains exactly K objects with that feature, wherein each draw either success failure.
14

---

Published as a conference paper at ICLR 2024
Proof. For a fixed E &, define
{'=(EnE\ E' EJ.
Since sigma-algebra is closed under intersection, we have E' C E. Through the definition of total variation distance,
TI Q)
max E'EE
mmaxpP((")) Q(E')
max P(EE)) Q(E")
E'EE"
P(F' n F.) Q(E n F))
E'EE
max F'EE
PPEE" E}P(E) QE'' B)Q(E)
max E'EE
|P(''
E) Q E) min()
= -TV(P(-) E), Q0 B)) (P),
This completes the proof.
C ON EXACT CONSTRUCTION OF F(M,A)
In most cases, function we want to approximate a property summarized from a MDP. We can define property (the concept of function) suppose we have a function class F. used to approximate properties in advance, an F-property is mapping from M x JF!" !l For example, the action space and the optimal value function are properties, and the value functions of policies from II are Il-properties. We can instantiate property given one specific M E M (or f E and M E M for F-property), such as computing the exact optimal value function of this M. The instantiation for the real model M is always the target we want to approximate.
mapping from MDP class M. Furthermore,
The uniqueness of properties under any specific M E M means that we can derive a function class for any properties by collecting their instantiations for each MDP from a realizable M.
Proposition 2. Given a model class M which contains the real model, for any property (denoted as f). we can construct a function class F with the realizability-tyee type assumptions satisfied and IM
Proposition Given a model class M which contains the real model and a function class F, for any F-property (denoted as I'), assumptions w.r.. F satisfied and [F' [M] Fi.
construct function class F' with the completeness-lyp
Thus, among all assumptions, model-realizability (M* E -M) is the strongest.
Remark This tiered structure is incapable of completeness-lype assumptions on one function class like Bellman--comlltennss. However, most completeness-type assumptions are built different function classes, and even the cellman-commleeeness can be reconstructed into a completeness- assumption between two function classes (Chen & Jiang, 2019).
Example 5 (Value functions all policies). The state-action value function is a Il-property. If there a policy class II and model class M, we calculate the value function of policy æ E II under MDP M E M as QM, with integration. If we want a value function class containing all value functions for policies from II, we can take (QM, |M M, E I1].
D PROOFS OF SECTION
This section provides a detailed proof for Section 5. Appendix D.I and Appendix D.2 first introduce the MDPs and the function classes used in the counterexamples, Appendix D.3 then sketches the proof of Theorem 1 with the help of some high-level proofs. Appendix D.6 provides proofs for the corollaries in Section 5.1. The remainder of this section is then devoted to the proof of some lemmas.
We assume that these mappings are known-we can compute the desired property if we have M M (and
h E F).
15

---

Published as a conference paper at ICLR 2024
Note that throughout the proof, sometimes introduce the multiplication of decimal terms and integers. We assume implicitly that we tune the terms so that the result are integers if necessary.
D.1 MDP STRUCTURES
I
In
P
X
1/2
1/2
I
f2
In
13
In
P
Figure 1: A counterexample from MM1 (above) and counterexample from Ma (below).
As shown in Figure 1, the constructed MDP class M contains M₁ and its axisymmetric M2. MDPs Mi and M2 only differ in their transition kernels.
State space and action space As shown in Figure 1, S consists of an initial state s, collection of intermediate states that belong to either set or set I, and a set terminal states sets I and Z are disjoint, and have the same cardinality that will be specified later. We denote states from I as {I1, I2, I3... ), and states from I as {T,, Iz, .y...). ). We take I (resp. as a subset of I (resp. Σ) with half cardinality that would be used determine the identities of the MDPs from M. 1 and 7 can be summarized by sets J {T I || [2]/2) and J = (7 c 7 7 222 There are two actions (AA = {1,2}) in each state.
The
Transition kernel
For MDPs from Mi with / specified,
Unif(Z)
if s = s and a if s and a = 2
Unif(Z \ 7) Unif([X,Y))
if E I if E i if if E otherwise.
P1(-1800)
Unif((X{))
Unif((Y{))
Unif([s))
Also, for MDPs from M2, we "swap" the transition probability vertically,
Unif(I I)
if s = 5 and a = 1
Unif(Z)
if and a = 2 if E if I if otherwise.
Unif(fX,Y))
Pa(: 8,a)
Unif([X])
Unif((YY) Unif([s})
16

---

Published as a conference paper at ICLR 2024
As each I E J and each I E 3 will determinate the transition kernel for MDPs from Mr and M2, which is the only difference between them, M and M2 can actually be written as
M1 = M I 5} and M2 = (M, Je.
Reward
One can only receive non-zero rewards by taking action 2 at states (X,X), which gives reward:
R(s, a) = { y if E (X, and a 0
otherwise.
D.2
FUNCITON CLASSES AND DATA DISTRIBUTION
Policy function class by
The policy function class IT contains policies and π2, which given
(2 1 otherwise,
=
T2( = [1 =
(8)
otherwise.
It is worth pointing out that, in the context of Theorem 1, is optimal for all the MDPs belonging
to M₁, and T2 is optimal for all the MDPs from M2.. { thus maps MDPs in M1 to m1, and maps MDPs in M2 to T2 in this circumstance.
Value function class which are given by
The state-action value function class @ contains two functions and d2.
2/2
if 5 and a
if and a if s s and a 2
0
if s and a = 2
72/2
7/2
if s E I
0
if E I
0
if E I
7/2
if E I
(s(s,)) a)
?
if X and
(2(s, a)
if X and
1
if 8 = X and =
1 1-7
if X and a =
0
if X and 1 if X and
if X and
1
1
X and if Y.
if
0
if Y,
0
One can check that gi is the value function of क, for MDPs in Mi, and qa the value function of m2 for MDPs in M2.
Partially accurate transition kernel
We set P as Unif(Z)
if and and if e I otherwise.
Unif(Z)
P(. (()18,a)=
Unif([X,Y))
s
Unif({X,Y))
Unif((s})
State transition kernel with exploratory-accuracy below:
The set Ps contains two elements described
Unif(Z]
if = if E I if I otherwise,
Unif(Z)
if =
(nif((X,Y))
Unif( (aif((X,YY
if E I ffee otherwise.
(s)
and Ps.p(: ())
Unif((Y))
Unif( (Y})
Unif([s])
Unif((s})
We point out that Ps.1 is the state transition kernel for कं under MDPs from M1, and Ps.2 the transition kernel for T2 under MDPs from M2.
Remark All functions mentioned above are independent with the choice of / and
17

---

Published as a conference paper at ICLR 2024
Data distribution states repectively. The behaviour policy is a uniform distribution w.n.. the action space A, regardless of the underlying state,
The state distribution is uniform distribution the "endpoint" and intermediate
d - Unif (x, x A) + Unif ((UUI) x A)
2
D.3 PROOF SKETCH THEOREM
From learning to hypothesis testing Following the similar principle of deriving minimax lower bounds (Yu, 1997; Yang & Barron, 1999 Tsybakov, 2008), we begin with transferring an estimation problem to hypothesis testing problem, of which the corresponding error probability can be related to the total variation distance between certain distributions.
First, the optimallty of the learned policies mainly comes from the chance of selecting action 2 in MDPs from Mi, and the chance selecting action in MDPs from M2. For MDP M E M and learning algorithm 21, denote this event F Letting тM #i for M Mi and TM 22 for M E M2. For any M E M, we have
( - B[JM(R) 12
P. 2
(
= P (
(4)
2
Furthermore, we transfer the minimax lower bound into a Bayesian problem. [PM 2 EM-UMIM [PM (E
max
(5)
MEM
For any learning algorithm 21 we have
(Mr-Uai((MM) [P (EM)
[P (EM)
Ess EEM PM (EM)
(6)
1 2
TV
1
Σ
P.N.
Σ
P.N
MM
M2
MEM:
MEMo
(), and (ii) the event EM when M E M, is the complement with itself when M E M2. While the total variation distance from Eqn. (7) algorithm dependent, we can extend it as probability the dataset D through data processing inequality, for which we add subscript D for clarify:
where Eqn. (7) follows from (i) the inequality P(E) + Q(E)
TV [M1l
Σ P.N.
P.N M
S
TVD
Σ MEM:
P.N Mi
Σ MEM₂
P. M
(8)
M22
MM2
[M2l
MEM,
MEM;
Combining Eqns. (4), (5), (7) and (8), we obtain
72 2
)
inf sup 2 MEM
(M((M)) ED [M((
1
TVp
Σ
P.N
Σ
PN
4
[i
M2
MEM:
ME
M
(9)
Bounding the Total variation distance
For notational convenience, we define
P
Σ
P M
and
Σ
P.N
(10)
M1
M2
M
MEM:
MEM,
The remaining task is to bound the total variation distance between IP- and Ie,, and it is done through the following lemma.
Lemma 3. For any sample size N, we can choose the cardinality of I to achieve
TIP P.) 1/2.
(11)
The proof of Lemma 3 is provided in Appendix D.5. Finally, combining Eqns. (9) and (11) yields that
JMM (TM) [[]M 2 22
inf sup a MEM
This completes the proof.
18

---

Because of the use of divierggene,, we first construct an Published as a conference paper at ICLR 2024
D.4 A GENERAL BOUND
Lemma 4. For any 0 S E I1/4.
5e <11+
N
TVD P.Y. (PN, Puy S
+ eex
- + Nlog
21 16
1.
8
The proof of Lemma 4 adapted from Foster et al. (2021b) with appropriate modifications. Specif- ically, first construct dominating measure that follows the left branch of Mi and the right branch of M2, then we transfer the total variance distance to x >²-divergence and bound via the hypergeometric tail bound.
Proof.
Construct the dominating measure MDP Mo whose transition kernel is
Unif(Z)
if s s and a 1
Unif(I)
if s 5 and a = 2 if E I dfsel I otherwise
Po(. 8,a)
Unif(1X,Y))
Unif(fs})
and whose reward function follows Eqn. (3) (as shown in Figure 2). We define the data collecting process under Mo and the data distribution dº with sample size N as P.N.
Y
y
1
I
I
I.
ig
P
Figure 2: The MDP of the dominating measure.
From total variance distance to ddivergence the triangular inequality and transfer it to x" -divergence," 12
- We first decouple the total variance distance via
TVp IPN P.
<TVD
INN ..Y.PN) TVD IPN. ".N.P.) P.N)
1 / (PN. .N)) + 2 x2 PNN (PN,PN))
(PN
We refer the interested readers Polyanskiy & Wu (2022) for details about these inequalitics.
19

---

Published as a conference paper at ICLR 2024
As the last two terms in the above inequality symmetric, will introduce how to bound the first term, while skipping the proof for the second term for simplicity. By the definition of --divergence,
MM. EMEM, (D))
x² (PPP pD) -Bowry
(PN(D))
Mil² EMAREM (D)PMM
=EDwry
(PN(D) 2
1
PN (MIPP
E
EDWPN
M2
(P)
M,M'EMI
Par ai, rs, Mrr ris ri)
1
Σ
1
[Ml
N
M.M'EM
II
(PM(ss ais ris s() ais aiss
1
121
Σ
((
NPg
II
(Po(s).a,..)
1.
M.M'EM
Since the dataset is generated in an i.i.d. manner, we can take the multiplication out from the expectation,
(arlsa.r -1, (12)
x² P.N. PN
Σ M,M'E.M,
IM1
(Po(s,a,,;)))
where Fo and I are the one sample version of P. and I., correspondingly. Through the definition of the data collecting process, for any M, M' M1, have
Par E's.a,r,"'>PB
Po((,,,r,s')
11
(M 2s,
E
16
16
(Po(s,2,r,
Par(s, a, (P's...,,s'PArrss.... PNr
R
4
(ols,,ar,s')
11
Par 5,2)I Ar (s' 2s
Eg
16
16
[Po(s' s,
4 (fs.ae))))
Par(s' s, (r (s,)) s,
+ E
4 ((nn))-Un(((xAA))ss/edddd
(Po(s') 8, s,)))
The last equality holds since the reward function is ths same. As the last two variables only depend on the number of overlapped states between I MM and Mr, which denote as M,M', define them as Q (lM,M) and (M respectively.
20

---

Published as a conference paper at ICLR 2024
Model as hyper-geometric distribution We take the summation in Eqn. (12) as taking the expecta- tion of sampling two MDPs uniformly from Mi.
Bismanayyp a. ". ( -1
1
Σ
MiP
(Fo(s,a,,,s))
M,M'EM,
P PM a, P - (P)(s,
E MM
(11
Nr 16 16 (IM,, + (22(tas,)r))
BM
As MDPs from Mi are indexed by E 5, for any fixed M E MM.
( 11
+ (IM,, + (02(l
16 16
equal to taking the expectation for a function of M, w.r.t. the following process:
Fix T M, we are selecting M without replacement uniformly from I. Take the number of overlapped state between TM and Tax M,,, and denote this random variable T.
Through the definition, we have T ~ (0, for any choice of M and M'. Thus,
(
N
11
1
Φ (IM,M) (12,
16
16
11
1
4 (T) + 1 (T))
-EM E
+
16
16
4
[1: + 16
4 1 (T) + ( 7
ET Hyperto..5 21,10 0.55Z)
By definition,
Φ (
40,
22(0[Z) = 0.5
+ (1 - 0.5)
40.
(13)
0.52
0.52
(1 (1- 0.5)
Note that both of them monotonic.
Bound via exponential tail bound
Eqn. (12) is finite only if the probability that
11 1 Φ (T)
(T) 1
16
16
21

---

Published as a conference paper at ICLR 2024
is exponentially small. We divide the expectation into two parts,
[
N1
I11
1 (x((T)
+
$ (T)
16
16
0.5/7
( 0.5/21
N
Σ
0.5
11
+
1
(1)
+ =22(1)
IZ
16
16
(0.5+())..5z]
(0.5 2
0.3|z
11
1
1
Σ
+
t (1)
1 $2((1)
16
16
0
0.5
0.5
(0.3121)
0.5/
Σ
0.5
11
(1()) +
1
(2(()
16
16
4
(0.5++))0
(o.5/Z)
N
110.5 + e)
(0.5 (0. +)).,5
16 16
(1)
M
+ P(T 2 (0.5 + e)0.5[Z()
41 (0.5 (0.55
16
16
4
By the definition of o and 422 we have
11
(10.0 + e)0.5/Z)) *f25(005 + c)).5[Z))
16
N
11
(0.5
+0.55
(0.5 c)..5
+ (1 0.5) 1 0.5 - 0.5 +
+ 0.5
16
16
0..2
4. 0.5.2
4
(by definition)
N
11
1
0.25 0.5c
+
16
8
4
2
56
1 +
8
and
11
1
+
(0.5
+ (0.5
16
16
4
N
11
0.5
0.5
0.5 0.5 + 0.5
+ 0.5
+..
+ (1
(0.))
16
16
16-0.5
4.0.2
4(1 - 0.5)2
11
1
16
21
16
22

---

Published as a conference paper at ICLR 2024
The probability presented in term (2) is exponentially small due to the hypergeometric tail bound (Lemma 1), which yields that
NV
11
(O.5(z) 1 2
P(T 2 ()..5))))))
16
16
21
N
Sexp(-2e* .
Se e H|I)
16
21
eexp
- + N log
Combining them, we have
5e
211
x2 PI Po
eex
- + N Nlog
1.
8
16
Through the similar arguments, also have
5c
21
P PN
+
cxp
- - + log
1.
8
16
Thus by noting that [
[Z], we have
5c
21
TV P.N. P
1
+ exp
- - + log
- 1.
8
16
This completes the proof.
D.5 PROOF OF LEMMA 3
Lemma (Restatement of Lemma 3). For any sample size N, we can choose the cardinality of I to achieve
(PP(PP,PP)) $ 1/2.
This lemma is a direct consequence of Lemma 4.
Proof. From Lemma we have
56
21
TVD(PY,PY)
S
+
+ cxp
- - [ + N Nlog
8
16
5.cc
exp
+ exp
-e2 + N log
16
N log
(t) +log8
Taking 0 < <
8 5N
log(9/8) and [
IZ
yields that
TV IPN) $1/2.
This completes the proof.
D.6 PROOF OF THE COROLLARIES
We can prove Corollary 1 by constructing the density ratio class from the state transition kernel class.
23

---

Published as a conference paper at ICLR 2024
Proof of Corollary 1. For each state transition kernel, there is S-sequence {su, $1, $2..... st....) such So ~ Po: 8441 ~ Ps(- 8t). We can compute the state distribution of a state transition kernel Ps
pls) (1-7) -1l-))>ne 1
If Ps is the state transition kernel of is the induced state distribution of π (i.e., px). Moreover, j consistent Ps is only accurate under Ux. i.c., have the same value with the real one on the support of p..- The induced distribution of π would be (s) = pas) x a), and the density ratio Wi follows that
W (8, a) = dn(s, a) (())T((,a)
d do (s,
We take the above process mapping from state transition kernels and policies density ratios, and denote it as O. We can construct the density ratio class as W = (O(Ps, +) Ps E Ps, π E IT..
For any M M, due the existence of exploratory-accurat state transition kernel of E(M) in Ps. W must contain the density ratio of {(M).
Since the function in Corollaries 2 and 3 are derived from trajectories, the proofs for them mainly devoted to construct set of functions mapping from S x AA (or S) to the trajectories (or the S-trajectories) thereby. Specifically, we want function class H such that
for all M E M, there exists E H that can return accurate trajectories of E(M) in certain level.
This is true due to the fact that can calculate trajectories directly from the transition kernel.
Proof of Corollary 2. Exploratory-accurac requries that for any entry reachable from μ4 by non- stationary policy, the value of function is the same with the target. For any entry reachable from the inital distirbution distribution by specific non-stationary policy Toon we can denote the state of this entry as 8, S. Given state transition kernel Ps, there is S-sequence
S,, 814 S Setis...
such that Seti+1 Ps(-(seti). The S-trajecroty from this entry can be caculated with the S- sequence and policy æ as
Se, Pes Seti, Peti...
(14)
such that re++ (-
[R( [R(s+ts]))]
Given policy æ. Eqn. (14) is the S-trajectory from 8, induced by π if Ps has the same value with Ps on the states of real S-trajectory from s, induced by æ. This can always be achieved if Ps is exploratory-accurate w.r.t. Pr.
We take the above process as mapping from state transition kernels and policies function from S to trajectories, and denote it as O.
We then construct as {O(Ps, =) Ps E Ps, 11J. For any M e M. any function can be derived from one element from this class with exploratory-accuracy
Proof of Corollary 3. Behaviour-aceuracyy w.r.t. a policy xr requries that for any entry reachable from No by म, the value of a function is the same with the target. For any entry reachable from the inital distirbution distribution by æ. we can denote this entry s, or (se, aee,ae) depending on the context. Given a transition kernel P and policy n, there is a trajectory
Se: Ge: Tes Set1 ae+1, Tetls
Setis Octis Netirre-i...
for the s, entry such that Gcti ~ (--1se+3) Teti = R(seti acti) and Sets+1 ~ P(-|seti, acts) for all > 0. For the (Se, a entry, there is also a trajectory
se, Ter Set1, det1,Tet1. Setis Te-d....
Probabiliiy of trajectories, to be accurate.
24

---

Published as a conference paper at ICLR 2024
such that aeti rT(((s++)), reti except that we fix the value of de.
acts), and set1+1 P(- Geti) for all 2 0,
The trajectory above is the trajectory from Se (or (se, de) respectively) induced by if P has the same value with the real transition kernel on the state-action pairs of the real trajectory from se (or (Se,0e) 0e) respectively) induced by This always be achieved if P behaviour-accurate w.r.t.
We can take the above process as a mapping from transition kernels and policies to a function from S (or S x A) to trajectories, and denote it as O. We can construct set as {O(P, T) т E II}.
For any M M,, any ((M))rrlated function can be derived from one element from this class with behaviour-accuracy.
E
THE DETAILED PROOF OF THEOREM 2
>>/>
Y
The changes in state Y. By selecting action 1, agents would transfer state Z. Selecting actions in state Z will only cause a self-loop, through which we can receive reward (1 7)/ with action 1 (resp. 2) for MDP in M₁ or M2 (resp. M3 or M4). The dataset does not cover state Z.
Figure 3:
Compared to the counterexamples in Theorem we introduce the following changes:
1. we modify state to introduce the insufficient data-coverage for selecting action in state Y (see Figure for more details),
2. we introduce state with variable rewards between MDPs,
3. the cardinalities of T and 7 increase 7[Z]/8,
4. there are two transition kernels such that
UZi
s and a if and 2 if I if T if E Z if = Y and =1 otherwise,
Unif(Z \ 7)
7Unif((X Unif((Y))/8
Pi (8,0)
Unif((X])
Unif({Y})
Unif(
Unif((s))
Unif(I (7)
if and if and a 2 I
Unif(Z)
+ Unif(())))8
P2 s)
Unif({{X})
if E I if E I if Y and otherwise.
Unif((Y)))
Unif([2])
Unif((s})
5. there are two reward functions such that if E (X,X) and 2
1
1-2
if E (X,X) and
(s,
1// if Z and otherwise,
R2(3, a)
(1 3//
if Z and otherwise.
0
25

---

Published as a conference paper at ICLR 2024
There four MDP classes denoted M == MM, MM, Ma) and M M U M2 Mg U M1. They share the same state space and action space, but differ the following perspectives:
the transition kernels for MDPs from M and M2 follow Pt, while those for MDPs from M3 and M4 follow P2,
the reward functions for MDPs from M₁ and M3 follow R1, while those for MDPs from M2 and M4 follow R2.
This structure allows the optimal value function to be the same in I or I, breaking the barrier of Q"-realizability. However, as we can receive return by selecting action 1 in state with some policies, the dataset only covers suboptimal policies.
E.1
FUNCITON CLASSES AND DATA DISTRIBUTION
Policy function class by
The policy function class Il contains two policies and which are given
(2 {{2 if xors
[i if X or Z
(s) [1 otherwise,
T2
2 otherwise.
& maps MDPs from MM U MM2 to T1 and maps MDPs from M3 UM4 to n2.
Value function class contains functions as summaried Table
Table 2: Functions in Q.
Qn for M1/M2
Qu, for Ma/M4 Q" for Mi/Ma Q" for Ma/Ma
7-2/8
8 6 a
7y2/8
72
q2
8 I
7n/8
7
7
8 I
7x/8
7
7
X & =1
7
X & 2
1 Y
1
8 X & a
7
7
= X & =
1 1-7
1
1
= Y & a a=
1
8 Y-Y&& Y a 2
7
=
=1
1/7 1/y-10m 1
1/7 - or
1/yor1
1 7/1
2& 2
0r 1/1-1
1/7 -1
1/7
1/y or
Partially accurate transition kernel
We set P as Uni
if = 5 and a = 1
Unif(Z)
if and a = 2 if s E I if s T if s = and a = otherwise.
7Unif((XX)//8 Un) 7Unif((X))/8 + Un))(())//8
P(| (,,)
Unif([Z])
Unif((s))
State transition kernels with exploratory-accuracy The set Ps contains two elements described below:
Unif(I)
if if E i otherwise,
7Unif((X])] Unif (Y))/8
(s |s)
Unif({{Y})
Unif((s})
26

---

Published as a conference paper at ICLR 2024
UZi
if =
UY)
if e I if e otherwise.
Ps,2(- (8)
Unif((Y))
[nif((s})
Reward function class
We set R as R2}.
Data distribution dh follows that
d =
Unif (x,X,Y,s)xx A) + Unif (IUT) A).
E.2 PROOF SKETCHI OF THEOREM
This subsection proves Theorem through some high-level lemmas. The proof of these lemmas are deferred to the remainder of this section.
denote event of selecting action 1 in state as E,, and the event of selecting action state Z as Eg. For an algorithm A. policies behave suboptimally under MDP classes from M if events from Table 3 happen (which we denote as E for M E M) correspondingly. The exact value of this suboptimality follows Lemma 5.
Lemma 5. Algorithm A that outputs से behaves suboptimally compared with E(M) if EM happens, i.e., for all M E M.
72
(Es))())) (B(0)))>E[[MMR) [[) 2 21 PP((
(15)
8
Table 3: When policies behave suboptimally for MDPs in each MDP class. v: the event happens. X: the event does not happen.
M1
M2
M3
Ma
E
X
d
/
E2
X
x
V
Constructing distribution over MDP classes M as
dm = Un),
we can transfer the minimax lower bound into a Bayesian bound,
inf sup (J - - B[MM
2 inf E EM
- [[MM -x(S(AM))E([M((A))
(16)
a M
2x inf E [P(E*) - -7218.
(17)
We define P(E M) as the averaged probability under M with sample size N, but omit N for simplicity,
PE M) EM- (E))
Egn. (17) could be bounded with the total variation distance between some MDP families from M.
Lemma 6. The fail probability is bounded by the total variation distances between certain MDP families from M.
inf EMsds. ((E))) 2 max (T(PP(MM)P((Mss)) (T(T))))))T(((M)))PPMMMM)) (IMM)//))MMM))...M///)).MM)) 2 max (FL(B)))). (((MM))))))(())))))(()))M))
2
27

---

Published as a conference paper at ICLR 2024
For notational convience, abbreviate the total variation distance
:TW
Intuitively, the difference in the reward function in state Z does not matter since it is not covered by the dataset, and the difference in the transition kernel follows the same argument of Theorem 1. Thus, the total variation distance is small enough.
Lemma 7. For any sample size N, we can choose the cardinality of to ensure that the total variation distance is bounded between MDP classes from [M1,M2} and MDP classes from {M3, Ma}.
max M" TV(M', S 1/4.
Lemma 8. The total variation distance between Mi and M2, as well as the one between Ma and MA satisfies,
TV(Mi, = TV(M3, = 0.
Combining the above arguments yields that
sup inf (JM(E(A)) - [[]r(()]] 2 27//16. a
This completes the proof.
E.3 PROOF OF LEMMA 5
Lemma (Restatement of Lemma 5). Algorithm 2 that outputs से behaves suboptimally compared with E(M) if EM happens, i.e,, for all M E M,
2²
(s((((M)) - E [M)( 2 PP(
(18)
8
Proof. If Fi happens, can have return in the best case. Since the optimal return from s is 7
we have
E Egg [Ja( S 2P S -
Thus, we have
- -M(((M))EE(MM(A)) 27/2/8 - 21P 213P(EM
This completes the proof.
E.4
PROOF OF LEMMA
Lemma (Restatement of Lemma 6). The fail probability is bounded by the total variation distances between certain MDP families from M.
inf EMSdsM 2
((E))) 2 max (T(PPLMM)PPPMMM)) (P((M))))))
2 max TV (TV(B(MM))P((MM)) (T(I)))))))(((L)s)P))M)))))
28

---

Published as a conference paper at ICLR 2024
Proof. Due to the definition of d.M-
inf E ((E ]]
Mndd
1
inf
P E and E M1)+ P(E) and M22 P and E Mss + P(E))
and E Mii
4
1
[F(ET] Ey Mi) PE M2)] min (M)
inf
4 2
+ | x0 E M +(EE)EET Ma)] min (PEE
inf
-min (RI
+ [ (V(P((1E) Ma). P(1 min Ms) Min
We can use Lemma 2 to simplify the total variation distance of conditional probabilities,
inf EMrddm [
Q
min -MM
inf 4
2
min Ma), | - (T((G))))((M)
inf
min
+ P(ETIMM),
M2) + PPET (2) + :P(E9IMa)
1 max (TV(P((MM))PP(MMM))) TT(()))))(( P((Ma)) }
2
The first term again can be transferred into the total variation distance,
inf E [(EE)))
EMddM
min f (I-T((R(MM).((MM)) (WTRRMMS))MLLLTTRMMPPPP..MM.
inf a
1 (TTPPM/))PPM)))),,TT(((M)).
1
(TM(P(L)M)).PPIMMMM) (TTMMM)))TT((F(LMMM... (FP((L))).PP)))
2 max
29

---

Published as a conference paper at ICLR 2024
Rearranging terms yields that
inf [MM-d (((EN))
21
1 max (MMA))TA(R(MMM))P11 (VPEM))..LLL..)). |
2 inf a
(P((MMb)) P((Ma)))) ((NN)) | |
TV(P(LM)).P((MM)) TWPPL
TV (TT 
max
((H)) - 
max ((M)) (EMMM))NNNN
1
max TV (TPGGM))..(MMM)) TYPPLLM...P(MMM)))
This completes the proof.
E.5 PROOF LEMMA
Lemma (Restatement of Lemma 7). For any sample size N, we can choose the cardinality of I to ensure that the total variation distance is bounded between MDP classes from (M1 and MDP classes from (M,MM3)
Mi) TV(M', 1/4
max
Proof. Denote M' E [M11.M2h and M 1.M3.Mak we first transfer the algorithm dependentte total variation distance into the dataset version through the data processing inequality,
- (T
STVD (P( MM), I
We take IP(- IMM' as P. and take P(- IM" as P.Y. We then construct the dominating MDPs Mo as done in Lemma 4, whose transition kernel follows that
Unif(Z)
if s and a if s = a and a =
Unif(ZZ)
7Unif((X))/8 + Unif((Y))/8
if E I
Pol: s,a)
(X]i)((X))// + Unif((Y))/88
if I if = and a = otherwise,
Unif((Z))
Unif({s})
and whose reward is Ri. We can follow exactly the argument from Lemma 4 until Eqn. (13).
By definition,
1/8 - 17/8 0) 640 48,
7 0
1/8 - (7/8 - 0)
640
① ()
22(0
+ (1-7/8)
7 6.
(1/8)2
8 (7/8)²
(1 7/8)2
Both of them monotonic.
30

---

Published as a conference paper at ICLR 2024
Since T ~ H7per(7)[1/8, [[,
21 (T) + (2((T) "7
"
11
1
E (7 2/00)
+
16
16
4
7/1/8 18)
1///8
/111/811
11
1
=
t1 (1)
+
(1)
16
16
4
10
/7/888
T(7/8+6)/
(7
1/21//))) .)
[Z
11
1
Σ
$1
(t)
(2(())
[Z]
16
16
4
7////8)
/8
(712)/8)
[
7/Z1/8-1
11
1
21
(t)
+
4 02(()
(0 S S
19 61
I
[
16
16
[7
(1Z11/8)
11
- (7((88
1
/2 + - (7 (
16
16
(1)
11
1
1 4
P(T
+
21
(7[Z)/8))
16
16
For term (1), we can rewrite it as
11
1
1
+
(7)
16
16
11
1
49
7c
1
64
7(7/8 + c)/8 23/8--081 (3188-66
(0///-666 6))
+
64
+
3
+
16
16
64
8
4
7
N
+
For term (2), we rewrite its latter part as
11
(7(08188)
+ .2
16
16
4
N
(
(7 8 - 6)
64
(56
48) +
16
16
27 N
16
The probability part of term (2) exponentially small because of the hypergeometric tail bound (Lemma 1), which yields that
N
27
P(T 2 7(7/8+
16
27
<exp(-2e² 7II/8)
16
7 2 (-7-21
27
exp
N log
16
31

---

Published as a conference paper at ICLR 2024
Thus, the total variation distance is bounded
N
TVD P.N
(P
Po))
-
1
1 +
7e
+ exp
2 + N log
27
2
2
-4"
16
1
TeN 2
2 + log
27
exp
+ exp
1.
2
16
N
(+))
+2og
2 Taking 0 << 7N
1og(33/32) and
7
yields that
7ea
TV (VD(P( PD) $1/8.
Following the same argument, we also have
TVD(P(IM"),PN)) 51/8.
Therefore,
max Me(MMMM)
TV(M',
$1/4.
This completes the proof.
E.6 PROOF LEMMA
Lemma (Restatement of Lemma 8). The total variation distance between Mi and M2, as well as the one between M3 and M4, satisfies,
- =
Proof. We can first transfer the total variation distance between Mi and Ma into the total variation distance of the dataset via data processing inequality.
TV(M1. STVD (P(- MM). MM2)).
(.).P((IM22)).
Under the data distribution dD, the dataset generating principle of Mi and M2 is exactly the same since their different part is not covered by d=. This means that
TV (P(: (.). ( = =. 0.
One can also prove TV(Ma, M4) = 0 in similar manner.
F COMPARING THE ASSUMPTIONS FROM THIS PAPER AND PRIOR WORKS
This section reviews assumptions in offline RL with general function approximation and presents a comparison of these assumptions across different studies (including ours). Note that our results lower bounds the strength of assumptions should be viewed inversely in some cases. We first elaborate data assumptions in Appendix F.I, and then function assumptions in Appendix F.2. A summary of their usage in the literature can be found in Table 4.
A worth-mentioning point is that model-based assumptions are aligned with the toy assumptions (such as tabular MDPs), since they assume that the possible underlying models are "small." Model realizability implies most function class assumptions. For the stringency of model realizability, do not discuss the mosel-based assumptions that appears in other works (Uchara & Sun, 2021; Bhardwaj al., 2023) in this section,
32

---

Published as a conference paper at ICLR 2024
Table 4: Summary of major assumptions in Offline RL with general function approximation. Realizability-tpp means that the results in the papers only require realizability-type assumptions, and completeness-typ means that the results in the papers make completeness-type assumptions. The rows summarize the data assumptions made in the papers. We mark papers with model-based assumptions with M superseript.
Realizabilitt-ype
Complelensss-lppe
Theorem (ours); Zhan et al. (2022);
Liu et al. (2020); Xie & Jiang (2020b);
Single Coverage
Cehara Sun (2021)M;
Xie et al. (2021a); Cheng al. (2022);
Bhardwaj et al. (2023)
Rashidinejad et al. (2022); Zhu et al. (2023)
Exploratory Coverage
Chen & Jiang (2019)
The data ussumptions made by Xic & Jiang (2020a)
Theorem (ours); Xie Jiang (2020a)
F.1 DATA ASSUMPTIONS
Data assumption are the cornerstones of offline RL-they essentially determine what we can access as empirical facts. When comparing to online RL, data assumptions are always considered as an alternative of the frameworks general function approximation (Xie et al., 2022). As discussed in Chen & Jiang (2019), data assumptions can also be viewed as implicit model assumptions.
As briefly introduced in Section 2.2, bounds on the coverage coefficient are the main stream of data assumptions. An interesting alternative for the ratio of distributions is to involve loss functions, as done in works such as Xie et al. (2021a); Cheng et al. (2022); Bhardwaj et al. (2023). This approach takes the form of
ES [C(]]] JEF Egp [C()]]
C = max
(19)
where v is the distribution we want shift (e.g., the induced distribution of the optimal policy), F is the function class, C is the loss function in the algorithm, and C is the refined concentration coefficient. This refined notion of coverage is yet no-surprising since most cases we only use the coverage assumptions for loss-shifting, or namely, distribution rescaling.
Concentration w.r.t. P and A The coverage assumptions in Xie Jiang (2020a) require that
1t² (the state margin of d should scale at the same level as the transition kernel P(|ss, a) and the initial state distribution, namely, there exists constant > such that for all s E S,a A,
P(5'ls,a\/1 S
C and (s)))//p(() S.
for every state s E S, the behavior policy (-(s)) should be lower-bounded for all actions a A (thus covers all possible actions).
These assumptions are remarkably strong, exploiting the access of the dataset and making strong restrictions the possible MDPs. Conditions and 3 in Theorem I are specifications of these assumptions, and the data assumptions in Theorem I are thus stronger than the ones in Xie & Jiang (2020a).
One can also verify that the data assumptions in Theorem I are stronger than almost all those made in offline RL literature (e.g., Chen & Jiang (2019); Xie & Jiang (2020b); Xie et (2021a); Cheng et al. (2022); Ozdaglar al. (2022); Zhu et al. (2023); Uchara et al. (2023)).
F.2 FUNCTION ASSUMPTIONS
Function assumptions in offline RL can be approximately characterized in three aspects: the loss to be minimized, the number of loss presented in the assumption, and the complexity the function class. The last aspect is used to analysis the generalization property of the function class, and its treatment in offline RL does not differ from its use in the one in empirical processes (Pollard, 1990; Vaart & Wellner, 1996). We therefore only elaborate the first two aspects in the reminder of this
33

---

Published as a conference paper at ICLR 2024
section. A summary of function assumptions is presented in Table 5. It is worth mentioning that this treatment primarily aimed at real-world applications, Much the analysis in RL still focuses on simpler scenarios such tabular MDPs and linear MDPs, in which cases most function assumptions are naturally met, since the university of all possible functions is simple enough.
F.2.1 ON THE LOSS BE MINIMIZED
Functions classes, or approximators, are designed to minimize losses, and the quality of a function class can be determined by the scale of the minimum loss of the function class. We would like to mention that, the assumptions described below can often be converted to weaker ones by modifying the proofs without loss of generality.
Strictly Containing One may assume that the function exactly contains certain desired elements, or can optimally minimize loss function. For instance, we may assume value function class containing the optimal value functions, or equally, have function minimize the Bellman optimal equation. From the perspective of loss, we can interpret it as having a function class F satisfying
min FEF the loss
s7 = O.
This approach has more stringent requirements but also offers greater flexibility in application, possibly easing the proof process. Taking the optimal value function example, function class to minimize the optimal Bellman error, as well as to serve as a discriminator for the density ratio in MIS.
the
Approximately Containing A refined approach is to measure the violation of an assumption by an constant and then state the final result as a function of this constant. For instance, we may assume having function class F satisfying
min |I 1o S JEF the loss
by including a constant > 0 to measure the sub-optimality. We can also replace the loss above with more refined ones such as the Bellman error (Zhu et al., 2023).
F.2.2 ON THE NUMBER OF LOSSES
The number of losses required to be minimized measures another aspect of function assumptions. Having exponentially many losses to minimize versus having just a few are completely different, which forms the fundamental difference between realizability- type assumptions. real-world applications, completeness-tye assumptions may not always be met, leading to instability in the training process that could potentially destroy the final result.
assumptions and completeness-
Realizability-tyee Realizability-yyee assumptions are the assumptions that there are only a few losses to minimize. For example, we may assume that have function class F such that
max (min Li(f), min C2(1)) = 0, JEF
fEF
where &1 and C2 are two loss functions. These assumptions are natural extension of the ones in supervised learning, and are typically considered standard and relatively mild.
Completeness-typt Completeness -yppe assumptions are the assumptions in which the number of objective losses are exponentially many, or are approximately the same as the cardinality of function class. For example, we may assume that we have a function class F such that
max min JEF PEF
L(f, f') = O.
where F:Fx F + R is a certain loss function, e.g., the Bellman residual,
C(f.f') |l 1
These assumptions arise from the requirements of iterative algorithms such as FQI. Concretely, taking FQI as an example, let J A + E be the value function class. In each step of the algorithm, denoted as t, we assign a new function ft+1 based on the previous one ft, as
f minl Telll,
(20)
feF
34

---

Published as a conference paper at ICLR 2024
FQI aims for the assignment to follow fi+1 ffe which corresponds to the Bellman update. The assumption above famously addressed as the Bellman completeness.
Table 5; Summary of the Function Assumptions in the offline RL literature. Realizability- type means that the results in the papers only require realizability--ype assumptions, and completeness- -typ means that the results in the papers make completeness-type assumptions. The rows correspond to two different types of losses used in the assumption. The superscript '+' means that there are some accompanying assumptions (e.g., the gap assumption (Chen & Jiang, 2022)) for the function classes this paper. We mark papers with model-based assumptions with a superscript 'M'.
Realizabilit-type
Completeness-tppe
Uehara Sun (2021) M;
Jiang (2022)+ Uehara al. (2023)*;
Strietly Containing
Bhurdwaj al. (2023) M; Zhan al. (2023);
Theorem (ours)
Jiang (2019); Rashidinejad (2022); Theorem (ours)
al. (2020), al. (2021a));
Approximated Containing
Cheng et (2022); Zhu al. (2023);
Xie & liang (20206)
F.2.3 COMPARING THE FUNCTION ASSUMPTIONS WITH OURS
Our function class assumptions in Theorem are weaker than those made in model-based analy- (Uehara & Sun, 2021). When specifying concrete functions such the value function and the density ratio, one can show that our function class assumptions are weaker than those with completeness-type assumptions (Chen & Jiang, 2019; Liu et al., 2020; Xie al., 2021a; Rashidine- jad et al., 2022), and are comparable (and sometimes the same) with the works that make only realizability--tn -type assumptions (Xie & Jiang, 2020a: Zhan et al., 2022). We aim to demonstrate that completeness-tyie assumptions are particularly challenging to be mitigated.
35


Reviews:
[{"review_id": "7hT756YiLt", "reviewer": "Reviewer_XLGY", "summary": "This paper studies the role of function approximation in offline reinforcement learning (RL). Specifically, the paper first propose various types of function classes used in offline RL, and then show the learning lower bound under these types of function classes. Generally speaking, given functions with a policy class domain, it is impossible to learn a good policy.", "questions": "It seems like function approximation on policy class or value function class results in impossible learning tasks, does it mean that learning with a model class might have positive results?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper proposes a unified way to study general function approximation in offline RL.\n2. The theoretical results are solid and interesting.", "weaknesses": "1. The presentation is not clear. Some new words, such as exploratory-accurate(accuracy) and data assumption are used without pre-defined.\n2. While there are examples about those assumptions, I think a big table summarizing and connecting existing concrete examples and assumptions and the proposed general assumptions can make the paper easier to understand.", "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": "", "extra_scores": {}}, {"review_id": "avqTi2lPhq", "reviewer": "Reviewer_PRdx", "summary": "This paper focuses on offline learning setting with general function approximation.\nThe authors first formalize different types of assumptions in offline RL (realizability, completeness).\nIn Section 3, the authors reveal that the lower bounds derived for model-realizability can also be applied to other types of functions.\nAfter that, in Section 4 and 5, they establish lower bounds for learning in offline setting either without $Q^*$-realizability or weaker data coverage assumptions.", "questions": "I'm still trying to understand more about Def. 2. Consider the completeness assumption that $\\forall f\\in\\mathcal{F}$ we have $\\mathcal{T}^* \\in \\mathcal{F}$. I wonder what the corresponding $\\mathcal{F}$ and $\\mathcal{G}$ in Def. 2 should be in this case?\n\nIt also seems unclear to me how Def. 2 \"captures\" what common completeness assumptions ensure: \"the existence of a\nfunction class that can minimize a set of loss functions indexed by another function class\".", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper writing is relatively clear to me. The authors contribute interesting lower bounds, which reveal new understanding for learning in offline setting with general function approximation.", "weaknesses": "1. Although lower bound results are also meaningful, it would be better if there are some upper bound results to understand what we can do.\n\n2. As for the results in Section 6, can you explain more about the difference between the data coverage assumptions in (Xie & Jiang 2020) and the lower bound instance in Theorem 2?\n\n    Besides, as for the data coverage assumption used in Theorem 2, how does it compare with the practical scenarios? Would it be too restrictive in practice (maybe in practice we may rarely encounter such bad case)?", "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": "", "extra_scores": {}}, {"review_id": "4PRYxCwMdl", "reviewer": "Reviewer_85dZ", "summary": "This paper studies general function approximations in offline reinforcement learning (RL) settings. The authors firstly formally defined two types of usual assumptions on function approximations, i.e., realizability-type and completeness-type. They then discussed the relationship between assumptions on function approximations and the Markov decision processes (MDPs) those can be realized. Section 5 presented the main Theorem 1, which says that only realizability-type of assumptions are not enough to learn better policies. Corollaries 1-3 then assure similar results for different variants of realizability-type assumptions. The authors later discussed the limitations of the lower bound results, i.e., using over-coverage and not containing $Q^*$-realizability. Theorem 2 then shows a lower bound for $Q^*$-realizability but with partial coverage which may not cover optimal policy.", "questions": "Could you explain how it happens for $\\xi(M)$ can be optimal while the value function class does not contain optimal $Q^*$. Example or intuition could be helpful.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The presentation is clear, with enough discussion about the background and related work.\n2. The problem is convincingly motivated and important.\n3. The results are novel to my knowledge.", "weaknesses": "1. As the authors also noted, the main point of arguing that only realizability-type assumptions are not enough to learn better policies is kind of weakened by the fact that upper bounds for $Q^*$-realizability already exist, and Theorem 2 also feels short of compensating since as mentioned the covered policy is not optimal.", "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": "", "extra_scores": {}}, {"review_id": "nVIj5wADJe", "reviewer": "Reviewer_REan", "summary": "This paper studies offline RL with general function approximation, focusing on an information-theoretic understanding of different types of assumptions (such as completeness and realizability) and how they translate to assumptions on the underlying MDP. This results in a principled way of constructing lower bounds in offline RL with general function approximation via model-realizability, and with this method the authors prove the necessity of completeness assumptions.", "questions": "--", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This a well-motivated and interesting work and I enjoyed reading the paper. The work puts common assumptions for PAC learning of offline RL with general function approximation under scrutiny and provides a clear overview and concrete definitions of completeness and realizability assumptions. \n- Connecting the model-free completeness assumptions to assumptions that impose restrictions on the underlying MDP is very useful as it unifies lower-bound constructions for different function approximation methods. Particularly given that worst-case information-theoretic lower bounds are specific to function-class assumptions—e.g., Foster et al. 2021 prove a lower bound for value-based and exploratory data settings while recent papers such as Zhan et al. 2022 overcame the difficulty by changing the function approximation method. \n- With the model-realizability technique introduced in this paper, the authors show the necessity of the completeness-type assumptions.", "weaknesses": "There are no major 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": "", "extra_scores": {}}, {"review_id": "YsAxtasZq1", "reviewer": "Reviewer_MhTC", "summary": "This paper studies the offline RL with general function approximation.\n\nThe central problem of this topic is to identify the structural assumptions that empower sample-efficient learning. Many previous works impose assumptions on the data coverage and/or assumptions on the function class/MDP structures. Recently, foster et. al. established the fundamental limit when the completeness is missing but there are also works like [1] and [2], bypassing the lower bound in foster et. al. with different function approximation target.\n\nThis work aims  to present a rather unified framework to connect the function approximation to the realizability, which is interesting and very relevant to the community.\n\n\n[1] Offline reinforcement learning with realizability and single-policy concentrability\n[2] When is realizability sufficient for off-policy reinforcement learning?", "questions": "See weakness.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The topic is interesting. I have been curious about what we can do without strong completeness-type assumption and super-strong data coverage conditions since [1]. While there are works bypassing the lower bounds in [1] with different type of realizability assumptions and refined characterization of completeness [2, 3], the relationship between various assumptions in the literature is still not very clear. So it is exciting to see that the authors are trying to fill the gap.\n\nHowever, the current version is still not ready for publication due to the writing quality and since the relationships to previous works are not clear. \n\n[1] Offline reinforcement learning: Fundamental barriers for value function approximation\n[2] Offline reinforcement learning with realizability and single-policy concentrability\n[3] When is realizability sufficient for off-policy reinforcement learning?", "weaknesses": "The main drawback of this paper is the writing. The authors state many things without concrete examples and arguments but only abstract summarizations (by using the word certain). For instance, the authors mention the previous works of ``Xie and Jiang''by their refined data assumptions, which assuming that the audience is familiar with these previous works. Meanwhile, many notations are used without a formal definitions although I can understand some of them as they have been used by the previous papers but this can still be a problem for general readers. \n\n1 It would be great if the authors could instantiate the definitions present in this paper or discuss the relationships with the previous assumptions like the Bellman completeness in [1] and the realizability in [2]. For instance, in the example 2, it would be better to prove that the standard Q-pi-realizability is a special case of definition 2 by explicitly specifying the $\\mathcal{F}$ and $\\mathcal{G}$.\n\n2 In example 3, may I take \\phi as the mapping from a Q-function to its greedy policy? So completeness w.r.t. $\\mathcal{T}^\\pi$ for all the functions whose greedy policy is $\\pi$ is indeed completeness w.r.t. $\\mathcal{T}$ for all the functions in $\\mathcal{F}$?\n\n3 While proposition 1 is intuitive and reasonable, it seems that many previous works are indeed constructing the lower bounds through a worst-case consideration on the MDP by constructing a family of MDP classes satisfying the assumptions (e.g. [3]). \n\n4 How did the conditions of theorem 1 compare to the assumptions in [1,2]? This should be highlighted so that the readers can evaluate the roles of the corollaries presented in section 5.1.\n\n5 Most of the coverage assumptions are made with respect to the $\\xi(M) \\in \\Pi$, which is more related to the coverage over $\\Pi$, in contrast to the single-policy coverage assumption ($\\pi^*$) commonly used in the previous works. I am trying to understand the case of $\\pi^* \\in \\Pi$. But due to the presence of $\\xi$, the obtained lower bound may not compete with $\\pi^*$. Can you give an example of the unknown mapping $\\xi(\\cdot)$ so that we can understand the meaning of the target $J_M(\\xi(M))-J_M(\\hat{\\pi})$?\n\n\n\n[1] Bellman-consistent Pessimism for Offline Reinforcement Learning\n\n[2] Offline reinforcement learning with realizability and single-policy concentrability\n\n[3] is pessimism provably efficient for offline rl", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)