Bellman-consistent Pessimism for Offline Reinforcement Learning
Authors: Tengyang Xie
Ching-An Cheng
Nan Jiang
Paul Mineiro
Alekh Agarwal
Venue: NeurIPS 2021 Oral (2021)
Keywords: offline reinforcement learning
Bellman-consistent pessimism
sample complexity bounds
linear MDP
function approximation

Abstract: The use of pessimism, when reasoning about datasets lacking exhaustive exploration has recently gained prominence in offline reinforcement learning. Despite the robustness it adds to the algorithm, overly pessimistic reasoning can be equally damaging in precluding the discovery of good policies, which is an issue for the popular bonus-based pessimism. In this paper, we introduce the notion of Bellman-consistent pessimism for general function approximation: instead of calculating a point-wise lower bound for the value function, we implement pessimism at the initial state over the set of functions consistent with the Bellman equations. Our theoretical guarantees only require Bellman closedness as standard in the exploratory setting, in which case bonus-based pessimism fails to provide guarantees.  Even in the special case of linear function approximation where stronger expressivity assumptions hold, our result improves upon a recent bonus-based approach by $\mathcal O(d)$ in its sample complexity (when the action space is finite). Remarkably, our algorithms automatically adapt to the best bias-variance tradeoff in the hindsight, whereas most prior approaches require tuning extra hyperparameters a priori.

Bellman-consistent Pessimism for Offline Reinforcement Learning
Tengyang Xie
Ching-An Cheng
Nan Jiang
UICC tx1001llinois.cm edu
Microsoft Research chinganc@mi www.aaccccioooooooocooooooo
UIUC
nanjiang@illinois..ed
Paul Mineiro
Alekh Agarwal
Microsoft Research
Google Research
pmineiro@microooff com
alekthagarval@googgee.coo
Abstract
The of pessimism, when reasoning about datasets lacking exhaustive explo- ration, has recently gained prominence in offline reinforcement learning. Despite the robustness it adds to the algorithm, overly pessimistie reasoning can be equally damaging in precluding the discovery of good policies, which is an issue for the popular bonus based pessimism. In this paper, introduce the notion of Bellman- consistent pessimism for general function approximation: instead of calculating point-wise lower bound for the value function, implement pessimism the initial state over the set of functions consistent with the Bellman equations. Our the- oretical guarantees only require Bellman closedness standard the exploratory setting, in which case bonus-based pessimism fails to provide guarantees. Even in the special case of linear function approximation where stronger expressivity assumptions hold, our result improves upon a recent bonus-based approach by (d) in its sample complexity when the action space is finite and small. Remarkably, our algorithms automatically adapt to the best bias-variance tradeoff in the hindsight, whereas most prior approaches require tuning extra hyperparameters a priori.
Introduction
Using past experiences learn improved behavior for future interactions a critical capability for Reinforcement Learning (RL) agent. However, robustly extrapolating knowledge from a historical dataset for sequential decision making is highly challenging, particularly in settings where function approximation is employed to generalize across related observations. In this paper, we provide systematic treatment of such scenarios with general function approximation, and devise algorithms that can provably leverage an arbitrary historical dataset to discover the policy that obtains the largest guaranteed rewards, amongst all possible scenarios consistent with the dataset.
The problem of learning good policy from historical datasets, typically called batch or offline RL, has a long history [see e.g., Precup al., 2000; Antos et al., 2008; Levine et al., 2020, and references therein]. Many prior works [e.g.. Precup et al., 2000; Antos et al., 2008; Chen and Jiang, 2019] make the so-called coverage assumptions on the dataset, requiring the dataset to contain any possible state, action pair trajectory with lower bounded probability. These assumptions prohibitive in practice, particularly for problems with large state and/or action spaces. Furthermore, the methods developed under these assumptions routincly display unstable behaviors such as lack of convergence or error amplification, when coverage assumptions are violated [Wang et al., 2020, 2021].
evidently
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Driven by these instabilities, a growing body of recent literature has pursued a so-called best effort style of guarantee instead. The key idea is replace the stringent assumptions on the dataset with a dataset-dependent performance bound, which gracefully degrades from guaranteeing near-optimal policy under standard coverage assumptions to offering no improvement over the data collection policy in the most degenerate case. Algorithmically, these works all leverage the principle of pessimistic extrapolation from offline data and aim to maximize the rewards the trained agent would obtain in the worst possible MDP that is consistent with the observed dataset. These methods have been shown to be typically more robust to the violation of coverage assumptions in practice, and their theoretical guarantees often provide non-trivial conclusions in settings where the previous results did not apply.
Even though many such best-effort methods have now been developed, very few works provide comprehensive theory for using generic function approximation, unlike the setting where the dataset satisfies the coverage assumptions [Antos et al., 2008; Munos, 2003; Szepesvári ári and Munos, 2005; Munos and Szepesvári, 2008; Farahmand et al., 2010: Chen and Jiang, 2019; Xie and Jiang, 2020]. For example, [Kidambi et al., 2020] provides a partial theory under the assumption of an uncertainty quantification oracle, which however is highly nontrivial obtain for general function approximation. [Fujimoto et al., 2019; Kumar et al., 2020] develop sound theoretical arguments in the tabular setting. which were only heuristically extended to the function approximation setting. The works that explicitly consider function approximation in their design either use an ad-hoc truncation of Bellman backups [Liu et al., 2020] or strongly rely on particular parameterizations such as linear function approximation [Jin et al., 2021]. In particular, [Liu et al., 2020] additionally requires the ability to approximate stationary distribution of the behavior policy, which is a challenging density estimation problem for complex state spaces and cannot be provably performed in the standard linear MDP setting (see Section 3.1).
Our paper takes an important step in this direction. We provide a systematic way to encode pessimism compatible with arbitrary function approximation class and MDP and give strong theoretical guarantees without requiring any coverage assumptions on the dataset. Our first contribution is an information theoretic algorithm that returns a policy with small regret to any comparator policy, for which coverage assumptions (approximately) hold with respect to the data collection policy. This regret bound is identical to what can be typically obtained when the coverage assumptions hold for all policies [Antos et al.. 2008; Chen and Jiang, 2019]. But our algorithm requires neither the coverage assumptions, nor additional assumptions such as reliable density estimation for the data generating distribution used by existing best-effort approaches [Liu et al., 2020]. We furthermore instantiate these results in the special case of linear parameterization; under the linear MDP assumption, our sample complexity bound leads to a factor of ((d) improvement for d-dimensional linear MDP, compared with the best known result translated to our discounted setting [Jin et al., 2021], when the action set is small in size. In addition to the information theoretic algorithm, we also develop a computationally practical version of our algorithm using a Lagrangian relaxation combined with recent advances in soft policy iteration [Even-Dar et al., 2009; Geist et al., 2019; Agarwal et al., 2019]. We show that this algorithm can be executed efficiently by querying a (regularized) loss minimization oracle over the value function class, although it has slightly worse theoretical guarantees than the information theoretic version. Both our algorithms display an adaptive property in selecting the best possible form of bias-variance decomposition, where most prior approaches had to commit to particular point through their choice of hyperparameters (see the discussion following Theorem 3.1).
2 Preliminaries
Markoy Decision Processes We consider dynamical systems modeled as Markov Decision Pro- cesses (MDPs). An MDP is specified by (S,A, R, 7, so). where S the state space, A is the action space, P: : S x A + A(S) is the transition function with A(-) being the probability sim- plex, R : S x A + [0, R is the reward function, 7 E [0, 1) is the discount factor, and so is deterministic initial state, which is without loss of generality. We assume the state and the action spaces are finite but can be arbitrarily large. A (stochastic) policy т S + A(A) spec- ifies a decision-makiee
strategy, and induces a random trajectory su, ag. To, $1, r1........ where a, ~ (--(s)), Tt- = R(*,, at), 8141 ~ P(- at). V1 2 O. We denote the expected discounted return of a policy π as (TT) := E ?'r:/m], /r. and the learning goal is to find the maximizer of this value: n²' := argmax, Jm). A related concept is the policy-specific Q-function, Q" S x A + IR. Q* (s,s a) is the discounted return when the trajectory starts with (s, a) and all remaining actions
2

---

are taken according to x. Q is the unique fixed point of the (policy-specific) Bellman operator T :=5AA S defined as:
vf. (T f)), = R(s, a) + +nBssp(ssa)ffff where f('', Rt) is shorthand for (a(=)(-)=)) [f a')).
Another important concept is the notion of discounted state- actionction occupancy, de E A(S x AA), defined (s, a) == (1 >) ('((s s, or al /r], which characterizes the states and actions visited by policy π.
Offline RI In the offline setting, the learner only has access to a pre-collected dataset and cannot directly interact with the environment. We assume the standard i.i.d. data generation protocol in our theoretical derivations, that the offline dataset D consists of n i.i.d. (s, a. s') tuples generated as (s, a) r. R(s, a), s' P(-|s, a) for some data distribution μ. We will also use [[,[[]] for taking expectation with respect μs. We will frequently use the data-wert weighted 2-norm (squared) Il EyIf and the definition extends when we replace μ with any other state-action distribution v. The empirical approximation of || is
|| " "(t.aneee) (ssa)²
Function Approximation Function approximation is crucial to generalizing over large and complex state and action spaces. In this work, we search for a good policy in policy class 1I C (S - ((4)) with the help of value-function class F C (S A + [0, Vmax]) to model QT, where Vinax = Rmaaa (1 7). Such a combination is commonly found in approximate policy iteration and actor-critic algorithms [e.g., Bertsekas and Tsitsiklis, 1996; Konda and Tsitsiklis, 2000]. For most part of the paper we do not make any structural assumptions on II and F, making our approach and guarantees applicable to generic function approximators. For simplicity we will assume that these function classes are finite but exponentially large, and use log-cardinality to measure their statistical complexities in the generic results (Section 3 and Section 4). These guarantees easily extend to continuous function classes where log-cardinalities are replaced by the appropriate notions of covering numbers, which we demonstrate when instantiate results in the linear function approximation setting and work with continuous linear classes (Section 3.1).
We now recall two standard expressivity assumptions on F [e.g.. Antos et al., 2008]. To our knowledge, no existing works on offline RL with insufficient data coverage have provided guarantees under these standard assumptions for general function approximation, and they often require stronger or tweaked assumptions (see Section 1).
Assumption (Realizabilityy. For any E II, we have
inf sup admissible
- 11- SEF,
fEF
where admissible distribution means that {dz r/' E II].
Assumption I requires that for every II, there exists e F that well-approximates Q=. This assumption is often called realizability. Technically this is asserted by requiring f to have small Bellman eиror w.r.t. T under all possible admissible distributions. As sufficient condition, we have E, 0 if Q" E F, VT E II. Assumption (Completeness). For any и E IT, we have
sup inf I1 - fEF
T f112 f1 S EFFFF
Assumption 2 asserts that F is approximately closed under T ? Such assumption is widely used in RL theory and can be only avoided in some rare cases [Xie and Jiang, 2021], and the hardness of learning with realizability alone has been established in various settings (e.g., [Weisz al., 2021; Zanette, 2021]). We also emphasize that we only measure the violation of completeness under μ and do not need reason about all admissible distributions.
In the exploratory setting, realizability is usually stated in the form inf Ilf - fT S Err for any E II. However, the exploratory setting also usually has data coverage assumptions in the form of sup, ||///|/ < C. Combining them together implies Assumption "Sometimes completeness implies realizability, so the latter does not need to be assumed separately [Chen and Jiang, 2019]. However, this often relies on μ being exploratory, which is not the case here.
3

---

Distribution shift A unique challenge in RL is that the learned policy may induce a state (and action) distribution that is different from the data distribution μt, and the issue is particularly salient when we do not impose any coverage assumption on μ.. Therefore, it is important to carefully characterize the distribution shift, which we measure using the following definition, which generalizes prior definitions specific to linear function approximation [Agarwal et al., 2019; Duan et al., 2020]:
x) as follows to measure the distribution from an arbitrary distribution v to the data distribution p., w.E.t. F and n,,
Definition 1. We define
J T fll22
E(v:,, = max JEP
[s T 1
Intuitively, (l5 μu, F, measures how well Bellman errors under æ transfer between the distribu- tions and μu. For instance, a small value of '6 (dxx; ,4, F, x) enables accurate policy evaluation for using data collected under μ. More generally, we observe that
6 (V; S |1//|| == sup ((8,a) 3,0 ass
for any F.
and the RHS is a classical notion of bounded distribution ratio for error transfer (e.g.. [Munos and Szepesvári, 2008; Chen and Jiang. 2019; Xie and Jiang, 2020]). Moreover, measure can be tighter than / Even two distributions y and j that are sufficiently disparate might admit a reasonable transfer, long as this difference is not detected by and FF. To this end, our definition better captures the crucial role of function approximation in generalizing across different states. As an example, in the special case of linear MDPs, full coverage under definition (i.e., boundedness of '6 for all admissible v) can be implied from the standard coverage assumption for linear MDPs that considers the spectrum of the feature covariance matrix under μa; Section 3.1 for more details.
3
Results with Bellman-consistent Pessimism
In this section, we provide our first theoretical result which is information-theorrtiii,, in that it uses computationally inefficient algorithm. The approach uses the offline dataset to first compute a lower bound on the value of each policy æ E II, and then returns the policy with the highest pessimistic value estimate. While this high-level template is at the heart of many recent approaches [e.g., Fujimoto al., 2019; Kumar al., 2019; Liu al., 2020; Kidambi et al., 2020; Yu et al., 2020; Kumar et al., 2020], our main novelty is in the design and analysis of Bellman-consistent consistent pessimism for general function approximation.
For a policy т, we first form a version space all the functions / E F which have a small Bellman error under the evaluation operator T We We then return the predicted value of in the initial state so by the functions in this version space. The use of pessimism at the initial state, while maintaining Bellman consistency (by virtue of having small Bellman error) limits over pessimism, which is harder to preclude in the pointwise pessimistic penalties used in some other works [Jin et al., 2021]. More formally, given dataset D, let define
C(f', f, n: D)
1
Σ
n
(s,0,
and an empirical estimate of the Bellman error E(f, n D) is
{(fm;:) D) w(f.
min f(f l'ej
(3.1)
Our algorithm. With this notation, our information information-thhorrticc theoretic approach finds a policy by optimizing:
= argmax min ()) where Fr.s = { F {; <s)
(3.2)
Hell JEF+,r
In the formulation above, Fr.c is the version space of policy m. To better understand the intuition behind the estimator in Equation 3.2, let us define
fin -= argmin [50, T), Ja,max == argmax [80, T), and (s, a) == Sr, (8, a) a)- -f (8, a). JEF..c
JEF,.e

---

Intuitively, if the parameter is defined to ensure that Q" (or its best approximation in FF is in F we easily see that (s ιт) an upper bound on the enror in our estimate of J ((T) for any π E II. In fact, easy argument in our analysis shows that if Q" E Fr.c for all π E II, then A (s x) is an upper bound on the regret J(x) - J(z) of our estimator relative to any и we wish to compete with.
Theoretical analysis. To leverage this observation, we first define the a critical threshold e, which ensures that (the best approximation of) Q is indeed contained our version spaces for all m
139V max log FI + 39
(3.3)
With this definition, we now give more refined bound on the regret of our algorithm (3.2) by further splitting the error estimate A (=000 ιT) which random owing to its dependence on the version space, and analyze it through a novel decomposition into on-support and off-support components. While we bound the on-support error using standard techniques, the off-support error is akin to a bias term which captures the interplay between the data collection distribution and function approximation in the quality of the final solution. Also note that our choice é, requires the knowledge of Ex, which is a common characteristic of version-space-basee algorithms [e.g.. Jiang et al., 2017]. The challenge of unknown Ey can be possibly addressed using model-selection techniques in practice and we leave further investigation future work.
Theorem 3.1. Let e = Er where is Er defined in (3.33.3) and ßे be obtained by (3.(). Then, for any policy II and any constant C2 1, with probability least 1 - 6,
Vimx 7
log
F FI
VC2lEFFF +
-(x) - J( s
n
1-7
ertan (T)) on-support
Σ (da (L/1o(ss.))AA/(s.c))) (olss)/Af(aaa--/PPAAAalllll
min v: (v:p.
1
S0 (s,a)SXAA
orrotr(ar): off-support evtor
where (1; is defined in Definition 1, (dm \ (s, = max(dn(s,a) - ((s,a), 0) and (P* ()),)) = E/s.((]s..))[(( for any f.
Bias- variance decomposition. Note that decomposition of our error bound into on-support and off-support parts ef- fectively achieves a faas-nariance tradeoff. A small value of the concentrability threshold C2 requires the choice of the distribution closer μ4, which results in better estimation error guarantee (which is O ((VCa) (Cafn) when we transfer from j to v, but potentially pays a high bias due to the mismatch between d and A larger threshold permits more flexibility in choosing v similar to dz for a smaller bias, but results in larger variance and estimation error. Rather than commit to a particular tradeoff, our estimator automatically adapts to the best possible split- ting (Figure I illustrates this concept) by allowing us to choose the best threshold C2. The on-support part matches the n rate (fast rate error bound) of API or AVI analysis (e.g.. [Pires and Szepesvári, 2012; Lazaric et al., 2012: Chen and Jiang, 2019]). The dependency on horizon is only linear and matches the best previous result with concentrability assumption [Xie and Jiang, 2020]. For the off-support part, it depends on the off-support mass dz v and the "quality" of the off-support estimation: if all value functions in the version space are close to each other in the off-support region for policy æ, the gap between J(T) and J(T) can still be small even with large off-support mass. The following corollary formally states this property.
max de/ju 25.8
max de/u 3.7
4
An example illustrating dif- ferent on-support and off-support split- tings (denoted by two different vertical lines). Different splitting has different C2 values, and further yields different trade-offs.
Figure 1:
Corollary 1 ("Double Robustness"). Under conditions of Theorem 3. for any x and C2 2 erroff (T) = 0 when either (1) ((dz p. F, T) S C2 on (2) Afx 7P" Afx = 0.
5

---

Adaptive guarantees by algorithm design. As mentioned above, Theorem 3.1 implicitly selects the best vass-varannee decomposition through the best choice of C2 in hindsight, with this decomposition being purely a proof technique, not an knob in the algorithm. In contrast, many prior approaches [Liu al., 2020; Fujimoto et al., 2019; Kumar et al., 2019] employ explicit thresholds to control density ratios in their algorithms, which makes the tradeoff a hyperparameter in their algorithms. Since choosing hyperparameters particularly challenging offline RL, where even policy evaluation can be unreliable, this novel axis of adaptivity is extremely desirable property of our approach.
Comparison to guarantees in the exploratory setting, When dataset with full coverage is given, classical analyses provide near-optimality guarantees that compete with the optimal policy ' with a polynomial sample complexity, when x² E II and both realizability and completeness hold for F; see [Antos et al., 2008) for a representative analysis. As mentioned earlier, such analysis often requires boundedness of ||//u|>> for all admissible distributions {dz E II]. On the other hand, it is easily seen that we can compete with n² under much weaker conditions.
Corollary (Competing with optimal policy). Under conditions of Theorem 3.1, if E (d F,,FF,FF x²) & C2 we have
VinxVCa
log
F
E
(C(leFF+EF)) 1-7
J(T)) - ((F) O
1 1-7
Notably, these milder coverage assumptions in Corollaries 1 and 2 provide offline RL counterparts to the benefits of selicy-gradient-ttlle methods with online access to the environment [Kakade and Langford, 2002: Scherrer, 2014; Agarwal et al., 2019].
Comparison with Liu al. [2020]. The closest prior result to our work is that of [Liu al., 2020], who develop pessimistic estimator that truncates Bellman backups from state-action pairs infrequently visited by 14, and analyzes the resulting pessimistic policy and value iteration algorithms under general function approximation. For truncating Bellman backups, however, their work requires estimating the state-action distribution of data, which can be challenging high-dimensions and they incur additional errors from density estimation which we avoid. Further, their algorithms only compete with policies æ where |/dz//l /4//0oo oo is bounded instead of the more general result that we provide, and makes their results vacuous in a lincar MDP setting under typical feature coverage assumptions.
Safe Policy Improvement. Some prior works (e.g. Laroche et al., 2019; Liu et al., 2020) discuss the scenario where the dataset D is collected with behavior policy ma with μ da. and demonstrate that their algorithms always return a policy competitive with Tp. In our setup, this is straightforward as da, is always covered, as shown next.
Corollary 3 (Bounded degradation from behavior policy). Under conditions of Theorem 3.1, if J dag for some policy T E 11, we have
Vmux
log
EF.F +
J(TO) J(A) S 50
1 1-7
Proof sketch of Theorem 3.1. We now briefly describe the core ideas in the proof. More detailed arguments deferred to the full proof in Appendix B.I.
The key to prove Theorem 3.1 is to translate the ((T) - ( to the Bellman error of value functions follows:
in the version space Fx.e- Our main proving strategies
1. As the selection of E, ensures the accurate estimation Q" is contained in the version space Fr.c for any æ, we can obtain J(x) J(a) < max f( σ) min [So. क) approximation error.
2. By the optimality of â. have min fsu, 7) > minsef... f x). This indicates that ( (() max f(00, minseF, of f(s. π) + approximation error.

---

3. By using standard telescoping argument (e.g.. [Xie and Jiang, 2020, Lemma ID). fax, f(sp. т) jen, f( π) can be upper bounded by the Bellman error of argmax,eF... f55, т) and argmin f(50, т) over distribution dæ.
After combining all the three steps above together and considering the distribution shift effect, we complete the proof.
3.1 Results for Linear Function Approximation
Here we perform case study in linear function approximation. We will show that our results-wher instantiated under linear function approximation (with realizability and completeness assumptions) automatically provides state-of-the-art guarantees, improving over existing results specialized to this setting by factor of (d) [Jin et al., 2021] when the action space is finite and small.
We recall the linear function approximation setup (we set Rmax 1 and Vmax with literature).
for consistency
Definition (Linear Function Approximation). Let Φ 8 A - Rdd be a feature mapping. Without loss of generality, we assume [] a)ll S 1, V(s, a) E x A. We define the value-function class Fo as Fo == {) E Rd .(;;)) T T E [0, Vmax]]. and the policy class Hh consists of the greedy policies of each value function in Fe. Assumption (Realizability and Completeness).
= =0 0.
Note that, when the feature mapping Φ( is the one induced by the linear MDP [Jin et al., 2020], it automatically ensure that x* E 1l and Fa satisfies Assumptions 3. In contrast, we highlight that the standard linear function approximation or linear MDP setup does not entail all the assumptions needed by Liu et al. [2020] as mentioned earlier.
Below our main result in the linear funetion approximation setting.
Theorem 3.2. Suppose the value-function class J is a linear function class that satisfies realizability and completeness (Definition and Assumption 3) and ã is the output of (3.2). using value-
function class Fs and policy class II.. If we choose e = caaa d log Vmax All (n, then, for any policy π. S + A(A), we have
Vmax
dlog Vimaz (Ald
Edd Vo(s,a) ((000)))))))
J(m) ((
1
where c is an absolute constant, and Ed = ED [dls, a)
The detailed proof of Theorem 3.2 is provided in Appendix B.2. Our guarantee is structurally very similar to that of Jin et al. [2021, Theorem 4.4], except that we only need linear function approximation with realizability and completeness assumptions, and they consider the hniieeh linear MDP setting. If we translate their result to the discounted setting by setting = (11((1 - 7)), we enjoy a net improvement of order ((d) in sample complexity when the action space is finite and small. To vs. Ol ( (olog(d)A//////a) error bounds. The bound also shows that having a full-rank Ep (which is ensured by a full-rank covariance under (4) is sufficient for consistent offline RL in linear function approximation. Crucially, the full-rank covariance is an casily checkable condition on data, as opposed to unverifiable concentrability assumptions. As caveat, our results do imply a computationally efficient algorithm, as a naïve implementation involves evaluating each policy pessimistically to pick the best. We discuss computationally efficient adaptation of our approach in the next section.
make it concrete, that is O( ((V/logdd//))))
Practical Algorithm - Regularized Offline Policy Optimization
major challenge using the proposed algorithm in Section 3 in practice is that searching the policy with the best pessimistic evaluation the policy space II is not computationally tractable. In this section, we present a practical algorithm that is computationally efficient assuming access to a (regularized) loss minimization oracle over the value function class F, and also comes with rigorous theoretical guarantees.
Our practical algorithm summarized Algorithm It has three key differences from the ceemmatioo-thhoreeee version in (3.2).
7

---

Algorithm PSPI: Pessimistic Soft Policy Iteration
Input: Batch data D, regularization coefficient X.
Initialize policy л1 as the uniform policy.
2: for = 1, .., . do
3: Obtain the pessimistic estimation for nं as ft.
argmin (f(su, Te) + XE(F. mT D)))),
(4.1)
fEF
where Eff me; D) is defined Eq.(3.1) Calculate Te-1 by,
4:
met((ass =x(als) exp (nfe(ss))) Vx,
5: end for
6:
Output == Unif (ni
uniformly mix T1y... कT at the Irajectory level
1. The pessimistic policy evaluation performed via regularization (Line 3) instead of con- strained optimization.
2. Instead of searching over explicit policy space II, we search over policy class implicitly induced from JF (defined Eq.(4.2) and therefore no longer have policy class independent of FF separately, which is common practice in API-style algorithms [Munos, 2003; Antos et al., 2008; Lazaric et al., 2012].
We optimize the policy using mirror descent updates, which yiclds computationally tractable optimization over the implicit policy class. This property has been leveraged in many prior works, although typically in online RL settings [Even- et al., 2009; Agarwal et al., 2019; Geist et al., 2019; Cai et al., 2020; Shani et al., 2020].
Note that the use of a specific policy class above can relaxed if stronger structural assumption is made the MDP (e.g., linear MDPss [Jin et al., 2020, 2021]).
4.1 Analysis of Algorithm
We now provide the analysis of Algorithm 1 in this section. For ease of presentation, formally define the implicit policy class for this section:
Iss = { (+1ss x exp(1 Σ (s))
F},
(4.2)
which is the natural policy class for soft policy-iteration approaches. The following theorem describes performance guarantee of
Theorem 4.1. Let >= VVmns/u->)2 with E, in Eq.(3.3, = V
log AA 2V2
max T. and ā be obtained from
Algorithm For any policy ग A(A) we wish compete with, suppose Assumptions and hold with respect to the policy class Hy U {π). Then, for any constant C2 2 1, we have with probability least 8.
J(T) (
VET +ET 1-7
V Vmax
T Too F
Viaxer 7)2
Vinax
log [A] T
0
VO2
+
1-
+
n
aprimization arme
ottan (TT): on-support evior
1
Σ
(dz (da)
(e(e),))) -T (()
min ve 5c
T
1-7
(8.0)ESXA
ortan (sT): off-sspport error where Elvi F.T....) T.) is defined in Definition 1, (dz, \ ()) = max(d, v(s, F.

---

We provide proof sketch of Theorem 4.1 at the end of this section, and defer the full proof to Appendix C. We now make few remarks about the results in Theorem 4.1.
Measurement of distribution shift effect. Compared with the informmtion-thhoretice result (provided in Theorem 3. the measurement of distribution shift in Theorem 4.1 depends on the optimization trajectory. That is, it measures the distance between two distribution v and μ by 6 (V: J.F. TT) (T[IT]] is the sequence of policies produced by the algorithm) whereas Theorem 3.1 uses (v: p. F, TT) (I is the baseline policy we compete with). We remark that both of these two measurements are weaker then traditional density-ratio definitions (e.g.. [Munos and Szepesvári, 2008; Chen and Jiang, 2019; Xie and Jiang, 2020]) as we demonstrated before, as the dependence of & on π is relatively secondary.
Dependence on T. The number of optimization rounds T affects the bound in two opposite ways: as T increases, the optimization error term decreases, whereas the second term of the on-support error increases. The latter increase due to the complexity of the implicit policy class growing exponentially with T. which affects our concentration bounds. To optimize the bound, the optimal choice is T = (n²//5, leading to an overall O(n O(n-1/5) rate. While such rate is relatively slow, we remark that the complexity bound of II is conservative, and in certain cases it is possible to obtain much sharper bounds: for example, in linear function approximation (Section 3.1). I[spt are a priori captured by the space of softmax policies, whose complexity has no dependence on (up to mild logarithmic dependence due to norms). That is, the erT (T) term in Theorem 4.1 reduces to O O(Ym d//n) (EF.F E 0 in linear function approximation), and yields overall Onn-1/3)
rate.
Bias-variance decomposition. Similar to Theorem 3.1, Theorem 4.1 also allows arbitrary decom- position of the error bound into on-support and ouppst components by setting the concentrability threshold C2 which serves as a bias virianar tradeoff as before. In fact, the splitting can be done separately for each 7e in 1 S t T and we omit such flexibility for readability. The optimization error does not depend on the splitting. Our performance guarantee naturally adapts to the best possible decomposition as before. As in Theorem 3.1, if the estimation on the off-support region is "high- quality", we can further simplify the performance guarantees, but the requirement of "high-quality different from that of Corollary 1. We make formal in the following corollary.
Corollary 4 ("Double Robustness"). For any т and C2 2 O, err (T) = 0 when either (1) '6 (dxi μt F. me) I for all t E [T) or (2) ft - Aft for all E [T].
We note that the conditions above depend the optimization trajectory through their dependence on Tr, but can be made algorithm-independedr by instead asserting the stronger requirement that E (di,, He, F, 7') < C2 for all n' E 1sspi in the first condition.
Competing with the optimal policy. As before, we can provide guarantee for competing with the optimal policy, under coverage assumptions weaker than the typical batch RL literature, albeit slightly stronger than those of Corollary 2. We state the formal result below.
Corollary 5 (Competing with optimal policy). Under conditions of Theorem 4.1, if E (U, S for all क E IIspI, we have
V Vina V2 VinneVCa Iog F log (A)
(1007)
(108
1/5
/CalEn,+EEN) + 1-7
J(*')- - J(F) S
1-7
n
Note that the conditions of Corollary 5 are satisfied as before whenever ||dx. /Mllo S C2.
Computationnall--ffiieee implementation with linear function approximation We remark that our algorithm is computationally efficient when the value-function class F is linear, that is, F : {Ø(: To 0 E [R.. In this case, the objective of E4. has closed-form expression which is quadratic in In addition, under additional matrix invertibility conditions, (4. has a closed-form solution which generalizes LSTDQ [Lagoudakis and Parr, 2003; Sutton et al., 2009; Dann et al., 2014]. A similar connection has been made by Antos et al. [2008], but our derivation is more general. See Appendix Appendix D for further details.
We conclude the section with proof sketch showing the key insights used in establishing the proof.

---

Proof sketch of Theorem 4.1. Our proof constructs a corresponding MDP M, for every ft, na pair. Each M, has the same dynamics as the ground -ruuth MDP, but chooses a different reward function, such that ft is the Q-function of Te in Mr, QM, (we use the subscript of M, to denote the corresponding value or operator in MDP My). Our proof relies on some key properties of Mr. such as Q TM. Q" ft TT fc- We decompose J(xr J(+ as follows.
J(x) J( =
T E
1
E (J(T) J.C
T
optimizaation error
controlled by -IQ=-TZ, 12..2. I1fe TIfe-T" la.dz
+ approximaaiion/statisiialll emoos.
The proof is completed by bounding fl ft fella, on both on-support and off-support regions.
5 Conclusions
This paper investigates sample-efficient offline reinforcement learning without data coverage assump- tions (c.g.. concentrability). To achieve that goal, our paper contributes several crucial improve- ments to the literature. We introduce the concept of Bellman-consistent pessimism. It enables the sample-efficient guarantees with only the Belliman-completeess assumption which is standard the exploratory setting, whereas the usually requires stronger and/or extra assumptions. Algorithmically. we demonstrate how to implicitly infer policy value lower bound through version space and provide tractable implementation. A particularly important aspect our results is the ability to adapt to the best bias-variance tradeoff in the hindsight, which no prior algorithms achieve to the best of our knowledge. When applying our results in linear function approximation, we attain an (d) improvement in sample complexity, compared with the best-known recent work of offline RL in linear MDPs, whenever the action space finite and small.
wwis/bbonus-based pessimism popularly adopted in the literature
As of limitations and future work, the sample complexity of our practical algorithm is worse than that of the information-theoreti approach, and it will be interesting close this gap. Another future direction is to empirically evaluate PSPI on benchmarks and compare it to existing approaches.
Acknowledgment
Part of this work carried out while TX and AA worked Microsoft Research. NJ acknowledges funding support from the ARL Cooperative Agreement W911NE-17-2-0196, NSF IIS- ASS-211,771, and Adobe Data Science Research Award.
References
Doina Precup, Richard S Sutton, and Satinder P Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the Seventeenth International Conference on Machine Learning. pages 759-766, 2000.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning optrmoltimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005. 00464, 2020.
Jinglin Chen and Nan Jiang. Information theooreii considerations in batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051, 2019.
Ruosong Wang, Dean Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? In International Conference on Learning Representations, 2020.
Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, and Sham Kakade. Instabilities of offline with pre-trained neural representation. arXiv preprint arXiv:2103.04944 2021.
10

---

Rémi Munos. Error bounds for approximate policy iteration. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning. pages 560-567, 2003.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration, In Proceedings of the 22nd international conference Machine learning, pages 880-887, 2005.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference Uncertainty in Artificial Intelligence, pages 550-559. PMLR, 2020.
Rahul Kidambi, Aravind Rajeswaran, Pranceth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. In NeurIPS, 2020.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pages 2052-2062, 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006.04777 2020.
Yao Liu, Adith Swaminathan, Alckh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, 34(3):726-73,, 2009.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision
processes. In International Conference on Machine Learning, pages 2160 2169. PMLR, 2019.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. arXiv preprint arXiv: 1908.0028.0 2019.
Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1st edition, 1996. ISBN 1886529108.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, pages 1008-1014. Citeseer, 2000.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference Machine Learning, pages 11404-11413, PMLR, 2021.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-rellizbbee optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR, 2021.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. In International Conference on Machine Learning, pages 12287-12297. PMLR, 2021.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Mininax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709. PMLR, 2020.
11

---

Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. Advances Neural Information Processing Systems, 32:1 1784-11794, 2019.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 53:14129-14142 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pages 170--1713. PMLR, 2017.
Bernardo Ávila Pires and Csaba Szepesvári. Statistical linear estimation with penalized estimators: an application to reinforcement learning. In Proceedings of the 29th Interaational Coference on International Conference Machine Learning, pages 1755-1762, 2012.
Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Finite-sample analysis of least-
squares policy iteration. Journal of Machine Learning Research, 13:3041-3074, 2012.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning, In ICML, volume pages 267-274, 2002.
Bruno Scherrer. Approximate policy iteration schemes: a comparison. In International Conference on Machine Learning, pages 1314-1322. PMLR, 2014.
Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. International Conference on Machine Learning, pages 3652-3661,
2019.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
Qi Cai, Zhuoran Yang. Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pages 1283-1294 PMLR, 2020.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8613. PMLR, 2020.
Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. The Journal of Machine Learning Research, 4:1 1110-01144 2003.
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 993-1000, 2009.
Christoph Dann, Gerhard Neumann, Jan Peters, et al. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research, 15:809-883 08998883222 2014.
Amit Daniely, Sivan Sabato, Shai Ben- Devid, and Shai the erm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207-232. JMLR Workshop and Conference Proceedings, 2011.
Multiclass Icarnability and
Shai Ben-David, Nicolo Cesa-Bianchi, David Haussler, and Philip M Long. Characterizations of learnability for classes of {0, (0,...,n.)-................. nn......-vvllued functions. Journal of Computer and System Sciences, 50(1):74-86, 1995.
David Haussler and Philip M Long, A generalization of sauer's lemma. Journal of Combinatorial Theory, Series A, 71(2):219-240, 1995.
David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik- chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217-232, 1995.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT
press, 2018
12


Reviews:
[{"review_id": "iW8zCrb-9e6", "reviewer": "Reviewer_uzvJ", "summary": "This paper studies the pessimism in offline RL with general function approximation given i.i.d. transition data. An information-theoretic analysis is established for an inefficient method, where instead of point-wise pessimism, a notion of Bellman-consistent pessimism is considered. In this way, the theoretical guarantee is established only under closedness assumptions. An instantiation to linear MDP is considered and improved upon literature. Besides, a practical and efficient policy iteration method is proposed, whose performance is analyzed as well.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nThe work falls under the umbrella of pessimism for offline RL. The notion of Bellman consistent pessimism is novel and settles the problem of offline RL with general function approximation in an elegant and standard way. \n\nQuality:\nThe results are generally technically sound. I've briefly gone through the proofs and they look sound. \n\nClarity:\nThe paper is clearly written and well organized, with examples illustrating implications of main results.\n\nSignificance:\nThis work is an important step forward in understanding and practicing pessimism for offline RL under general function approximation. Though the data generating process (i.i.d. transitions) is a bit simplified, it will open the possibility for future research. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "ZggFC_BIrnh", "reviewer": "Reviewer_BXJd", "summary": "This paper studies offline reinforcement with function approximation, where the function class is general (but finite), without the strong assumption of coverage of the dataset. It proposes an algorithm based on a new notion of Bellman-consistency combined with pessimism that is applied globally (at the initial state) and not point-wise. Under realizability and completeness, the authors prove general suboptimality guarantees against any policy that depends on the level of \"mismatch\" with the data distribution. This bias-variance trade-off is optimized implicitly in the analysis without requiring tuning of specific hyperparameters. Finally, the authors provide a computationally efficient version of the algorithm that preserves the nature of these theoretical guarantees.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a good paper. It addresses an important subject - offline RL with general function approximation (actually general without assumptions like bounded Eluder dimension), and attempts to eliminate a problematic assumption - coverage of the dataset is clearly not achievable in many settings. I really like the approach for dealing with limited coverage - the implicit trade-off using the $C_2$ constant is a powerful result that is also very intuitive. I also like the practical variant of the algorithm although its convergence rate is quite slow, since it manages to leverage mirror descent techniques in the offline setting. I am familiar with these only in the online setting, were they previously used for offline RL as well? If so, it should be discussed.\n\nHowever, I still think that there are some concerns that must be addressed before I can vote this paper a clear accept.\nOne thing that really bothered me is that $\\epsilon_r$ depends on $\\epsilon_{\\mathcal{F}} $. The problem is that $\\epsilon_{\\mathcal{F}} $ cannot be computed (even without thinking of efficiency) since we do not have access to the Bellman operator. I understand that in many related work this is completely circumvented by assuming strong realizability (i.e., $\\epsilon_{\\mathcal{F}} =0 $), but I feel that it is a little bit of a hidden assumption - one cannot really instantiate this algorithm and get the guarantees of theorem 3.1. Do the authors have a suggestion about unknown $\\epsilon_{\\mathcal{F}} $?\n\nWhile the authors provide a good amount of discussion, there are a few points where I needed more intuition and explanation.\nThe first point is definition 1 which is hard to process so early in the paper and could use better explanation/intuition in the lines that follow. For example, is there a good reason for this parameter to be small for many policies?\nAnother point is in theorem 3.1 where the second term in the bound is very hard to comprehend. Although the authors try to explain this in the discussions that follow, I was still missing a basic description of this term (in words) and maybe some examples.\nMoreover, I couldn't understand how figure 1 helps to illustrate it.\n\nAs a non-expert in offline reinforcement learning, I was missing more comparisons to related work and clear statements about what a previous paper did compared to what the authors did - both in terms of results and more importantly techniques. For example, what is state-of-the-art for offline RL with coverage explicitly? what techniques did they use? why does it break when there is no coverage? how does your approach deal with that?\nA specific point that bothered in the context of related work is line 120 where the authors say that completeness assumption can be only avoided in some rare cases and cite [22]. I looked at that paper and it looks like this case is not that rare - general function class with only realizability assumption albeit with some coverage assumption. Does the \"rare\" term reflect the coverage assumption? Is it because this is the only paper? I feel like this should be described a lot more clearly.\n\nTo me it looks like the bound on the complexity of $\\Pi_{SPI} $ in the efficient algorithm is way too trivial. Did you attempt to prove better bounds on it in the general case (of course in many examples it is going to be small)? Is it not possible in the general case? If so, you should provide an example where this complexity really grows exponentially with $T $.\n\nFinally, just two typos I found. In the equation after line 151 you use $\\epsilon_r $, but it is defined only a few lines afterwards. Is it supposed to be $\\epsilon$ there? Also, I couldn't find equation 4.1. Looks like it should be the equation after line 284. Is that correct?\n\nPost rebuttal: I thank the authors for these clarifications and raise my score to 7.\n  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "J8Afvd5OjsC", "reviewer": "Reviewer_mdnB", "summary": "The paper proposes the use of Bellman-consistent pessimism for offline RL with general function approximation (under realizability and completeness assumptions), and manages to obtain non-trivial \"dataset-dependent\" sample complexity guarantees that generally hold under all possible data coverage scenarios of the dataset (i.e., the sample complexity bound gracefully degrades from guaranteeing a near-optimal policy under standard coverage assumptions to offering no improvement over the data collection policy in the most degenerate case). Such adaptivity makes the proposed approach attractive as it does not rely on any specific data coverage assumption. The paper provides two algorithms: the first attains sharp theoretical guarantees in a computationally inefficient manner, while the second attains worse guarantees in a more practical way.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: While the use of pessimism in offline RL to avoid strong data coverage assumptions has already been studied in many recent papers, this paper has a clear discussion of prior works and clearly demonstrates its new contributions beyond prior works. I particularly enjoy the decomposition of the error bound (into on-support and off-support components) and the related statistical analysis, which bring new technical insights to this field.\n\nQuality: The paper is technically sound and the claimed results are correct.\n\nClarity: The paper is well-written and I enjoy reading this paper.\n\nSignificance: Compared with prior works which use other notions of pessimism to obtain other forms of \"dataset-dependent\" performance guarantees (e.g., Liu et al. 2020 [15], Jin et al. 2020 [16]), the approach proposed in this paper enjoys several advantages such as more general guarantees under weaker coverage/function class assumptions. The ability to automatically adapt to the best bias-variance tradeoff in terms of $C_2$ is particularly important, as the hyperparameters tuning tasks commonly required in prior works are in fact very challenging in offline RL. \nOn the downside, I would like to say that most of the results in this paper are still far from being practical (see the limitation section for more details). Still, they are definitely important theoretical contributions.\n\nMinor Comments:\n\n1. In the abstract, the notation $d$ is used without any explanation. It would be better to say something like \"$d$-dimensional linear MDP\" earlier.\n\n2. Line 69: The use of \"where\" before \"most prior approaches\" seems strange. Did you mean \"whereas\"?\n\n3. Line 154: It should be $\\Delta f_{\\pi}(s_0,\\pi)$ rather than $\\Delta f(s_0,\\pi)$.\n\n4. Line 177: \"Rather than committing to\"\n\n5. Algorithm 1: $\\eta$ should also be input.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While Bellman-consistent pessimism brings some theoretical advantages over prior pessimistic approaches, it also introduces additional issues which may make it perform worse than prior approaches in practice. The original form of Bellman-consistent pessimism (described in Section 3) is definitely very difficult to implement, and the paper provides a more practical variant PSPI in Section 4. However, PSPI only has a much slower $O(n^{-1/5})$ rate in general, which makes it not necessarily more appealing than prior algorithms (e.g., the ones in Liu et al. 2020 [15]) when one wants strong statistical performance. Moreover, since the algorithms in Liu et al. (2020) may converge much faster than PSPI (the former should converge in $O(\\frac{\\log n}{1-\\gamma})$ optimization rounds while the latter may require $O(n^{2/5})$ optimization rounds), the computational complexity of PSPI can be much higher (as in each optimization round PSPI needs to solve a regularized loss minimization problem). Finally, while the authors claim that an important advantage of Bellman-consistent pessimism is that it does not require a density estimation step (and I fully agree with this point), the current paper assumes a known deterministic initial state $s_0$; when $s_0$ is generated by an initial state distribution $d_0$, I would expect Bellman-consistent pessimism to require the knowledge of $d_0$ --- note that estimating $d_0$ from the batch data may also involve density estimation, and the final performance bound may degrade with the estimation error of $d_0$.\n\nOf course, every approach has limitations. The paper's theoretical contributions are significant. \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "B3FvQczKZ2e", "reviewer": "Reviewer_W5J5", "summary": "The paper studies the idea of pessimism in offline RL not through the addition of (negative) bonuses, but by incorporating pessimism implicitly in the loss function. This brings several advantages, see detailed comments below.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There are several things to like about the paper.\n\n1) handling of general function classes\n2) approximation error evaluated over distributions rather than point wise\n3) related to 2), the transfer error notion is the weakest I’ve seen in this space\n4) while the algorithm is theoretical, a computationally tractable implementation is given. \n\nThe implementable version has a bad convergence rate but the authors give a sound explanation for why this is the case (increased complexity of the policy class). I agree with them that this can likely be lowered substantially on specific function classes.\n\nWhile I have a very high opinion of the work, I think in few places the exposition may need to be improved. Already in the abstract:\n\n1) “Our theoretical guarantees only require Bellman closedness as standard in the exploratory setting, in which case bonus-based pessimism fails to provide guarantees”\nAsm 2 requires `completeness’ with regards to any policy in the prescribed class, not just the greedy one as commonly done in online RL (e.g., Zanette et al ’20, Jin et al ’21, Du et all ‘21, Jiang et al. '17). Thus, your assumption is much stronger as every policy in your policy class needs to play nice with the prescribed function class. \n\n2) ``Our result improves upon a recent bonus-based approach by O(d) in its sample complexity when the action space is finite.’’ \nI would put more emphasis that the action space needs to be small (non-exponential in d). There is a well known sqrt(d) gap between the small & large action space already in linear bandits.\n\nMinor: the completeness assumption could be further motivated by recent lower bounds already in the linear setting (which you cover with your more general theory); for policy learning, the work Weisz et al ’21 (Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions) implies an offline lower bound of the same order and likewise Zanette ’21 (Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL) has explicit lower bounds for policy learning in the offline setting. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agreed that this paper constitutes a significant step forward for offline reinforcement learning with general function approximation, as it facilitates weaker notions of both transfer error and approximation error than prior work. While the algorithm in the paper is primarily theoretical, the authors also give a more practical/implementable version, which is valuable as well. In addition, the paper is clear and well-written.
Decision: Accept (Oral)