Bellman-consistent Pessimism for Offline Reinforcement Learning
Year: 2022

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 Bellmanconsistent 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 byO(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.

heading: 1 Introduction
text: Using past experiences to learn improved behavior for future interactions is a critical capability for a 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 a 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 a good policy from historical datasets, typically called batch or offline RL, has a long history [see e.g., Precup et 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 or trajectory with a lower bounded probability. These assumptions are evidently prohibitive in practice, particularly for problems with large state and/or action spaces. Furthermore, the methods developed under these assumptions routinely display unstable behaviors such as lack of convergence or error amplification, when coverage assumptions are violated [Wang et al., 2020, 2021].
35th Conference on Neural Information Processing Systems (NeurIPS 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 to replace the stringent assumptions on the dataset with a dataset-dependent performance bound, which 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. 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 a 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 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 to 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 an 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 a 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 O(d) improvement for a 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 a bias-variance decomposition, where most prior approaches had to commit to a particular point through their choice of hyperparameters (see the discussion following Theorem 3.1).

heading: 2 Preliminaries
text: Markov Decision Processes We consider dynamical systems modeled as Markov Decision Processes (MDPs). An MDP is specified by (S,A, P,R, γ, s0), where S is the state space, A is the action space, P : S × A → ∆(S) is the transition function with ∆(·) being the probability simplex, R : S × A → [0, Rmax] is the reward function, γ ∈ [0, 1) is the discount factor, and s0 is a 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) specifies a decision-making strategy, and induces a random trajectory s0, a0, r0, s1, a1, r1, . . ., where at ∼ π(·|st), rt = R(st, at), st+1 ∼ P (·|st, at), ∀t ≥ 0. We denote the expected discounted return of a policy π as J(π) := E[ ∑∞ t=0 γ
trt|π], and the learning goal is to find the maximizer of this value: π⋆ := argmaxπ J(π). A related concept is the policy-specific Q-function, Q
π : S ×A → R. Qπ(s, a) is the discounted return when the trajectory starts with (s, a) and all remaining actions
are taken according to π. Qπ is the unique fixed point of the (policy-specific) Bellman operator T π : RS×A → RS×A, defined as:
∀f, (T πf)(s, a) = R(s, a) + γEs′∼P (·|s,a)[f(s′, π)],
where f(s′, π) is a shorthand for Ea′∼π(·|s′)[f(s′, a′)].
Another important concept is the notion of discounted state-action occupancy, dπ ∈ ∆(S × A), defined as dπ(s, a) := (1 − γ)E[ ∑∞ t=0 γ
t1[st = s, at = a]|π], which characterizes the states and actions visited by a policy π.
Offline RL 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, r, s′) tuples generated as (s, a) ∼ µ, r = R(s, a), s′ ∼ P (·|s, a) for some data distribution µ. We will also use Eµ[·] for taking expectation with respect to µ. We will frequently use the data-weighted 2-norm (squared) ∥f∥22,µ := Eµ[f2], and the definition extends when we replace µ with any other state-action distribution ν. The empirical approximation of ∥f∥22,µ is ∥f∥22,D := 1n ∑ (s,a,r,s′)∈D f(s, a) 2.
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 a policy class Π ⊂ (S → ∆(A)) with the help of a value-function class F ⊂ (S × A → [0, Vmax]) to model Qπ, where Vmax = Rmax/(1 − γ). 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 Π 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 we instantiate our 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 1 (Realizability). For any π ∈ Π, we have
inf f∈F sup admissible ν
∥f − T πf∥22,ν ≤ εF ,
where an admissible distribution ν means that ν ∈ {dπ′ : π′ ∈ Π}.
Assumption 1 requires that for every π ∈ Π, there exists f ∈ F that well-approximates Qπ. This assumption is often called realizability.1 Technically this is asserted by requiring f to have small Bellman error w.r.t. T π under all possible admissible distributions. As a sufficient condition, we have εF = 0 if Qπ ∈ F ,∀π ∈ Π. Assumption 2 (Completeness). For any π ∈ Π, we have
sup f∈F inf f ′∈F
∥f ′ − T πf∥22,µ ≤ εF,F .
Assumption 2 asserts that F is approximately closed under T π .2 Such an 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 et al., 2021; Zanette, 2021]). We also emphasize that we only measure the violation of completeness under µ and do not need to reason about all admissible distributions.
1In the exploratory setting, realizability is usually stated in the form of inff∈F ∥f − T πf∥22,µ ≤ εF for any π ∈ Π. However, the exploratory setting also usually has data coverage assumptions in the form of supν ∥ν/µ∥∞ ≤ C. Combining them together implies Assumption 1.
2Sometimes 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.
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 µ, 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]: Definition 1. We define C (ν;µ,F , π) as follows to measure the distribution shift from an arbitrary distribution ν to the data distribution µ, w.r.t. F and π,
C (ν;µ,F , π) := max f∈F ∥f − T πf∥22,ν ∥f − T πf∥22,µ .
Intuitively, C (ν;µ,F , π) measures how well Bellman errors under π transfer between the distributions ν and µ. For instance, a small value of C (dπ;µ,F , π) enables accurate policy evaluation for π using data collected under µ. More generally, we observe that
C (ν;µ,F , π) ≤ ∥ν/µ∥∞ := sup s,a
ν(s, a) µ(s, a) , 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, our measure can be tighter than ∥ν/µ∥∞: Even two distributions ν and µ that are sufficiently disparate might admit a reasonable transfer, so long as this difference is not detected by π and F . 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 our definition (i.e., boundedness of C for all admissible ν) can be implied from the standard coverage assumption for linear MDPs that considers the spectrum of the feature covariance matrix under µ; see Section 3.1 for more details.

heading: 3 Information-Theoretic Results with Bellman-consistent Pessimism
text: In this section, we provide our first theoretical result which is information-theoretic, in that it uses a computationally inefficient algorithm. The approach uses the offline dataset to first compute a lower bound on the value of each policy π ∈ Π, 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 et al., 2019; Kumar et al., 2019; Liu et 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 pessimism for general function approximation.
For a policy π, we first form a version space of all the functions f ∈ F which have a small Bellman error under the evaluation operator T π . We then return the predicted value of π in the initial state s0 by the functions in this version space. The use of pessimism at the initial state, while maintaining Bellman consistency (by virtue of having a 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 a dataset D, let us define
L(f ′, f, π;D) := 1 n ∑ (s,a,r,s′)∈D (f ′(s, a)− r − γf(s′, π))2 ,
and an empirical estimate of the Bellman error E(f, π;D) is E(f, π;D) := L(f, f, π;D)− min
f ′∈F L(f ′, f, π;D). (3.1)
Our algorithm. With this notation, our information-theoretic approach finds a policy by optimizing:
π̂ = argmax π∈Π min f∈Fπ,ε
f(s0, π), where Fπ,ε = {f ∈ F : E(f, π;D) ≤ ε}, (3.2)
In the formulation above, Fπ,ε is the version space of policy π. To better understand the intuition behind the estimator in Equation 3.2, let us define
fπ,min := argmin f∈Fπ,ε f(s0, π), fπ,max := argmax f∈Fπ,ε f(s0, π), and ∆fπ(s, a) := fπ,max(s, a)−fπ,min(s, a).
Intuitively, if the parameter ε is defined to ensure that Qπ (or its best approximation in F ) is in Fπ,ε, we easily see that ∆fπ(s0, π) is an upper bound on the error in our estimate of J(π) for any π ∈ Π. In fact, an easy argument in our analysis shows that if Qπ ∈ Fπ,ε for all π ∈ Π, then ∆f(s0, π) is an upper bound on the regret J(π)− J(π̂) of our estimator relative to any π we wish to compete with.
Theoretical analysis. To leverage this observation, we first define the a critical threshold εr which ensures that (the best approximation of) Qπ is indeed contained in our version spaces for all π:
εr := 139V 2max log |F||Π| δ
n + 39εF . (3.3)
With this definition, we now give a more refined bound on the regret of our algorithm (3.2) by further splitting the error estimate ∆fπ(s0, π) which is 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 of εr requires the knowledge of εF , which is a common characteristic of version-space-based algorithms [e.g., Jiang et al., 2017]. The challenge of unknown εF can be possibly addressed using model-selection techniques in practice and we leave further investigation to future work. Theorem 3.1. Let ε = εr where is εr defined in Eq.(3.3) and π̂ be obtained by Eq.(3.2). Then, for any policy π ∈ Π and any constant C2 ≥ 1, with probability at least 1− δ,
J(π)− J(π̂) ≤ O Vmax√C2 1− γ √ log |F||Π|δ n + √ C2(εF,F + εF ) 1− γ  ︸ ︷︷ ︸
erron(π): on-support error
+ 1
1− γ · min ν:C (ν;µ,F,π)≤C2 ∑ (s,a)∈S×A
(dπ \ ν)(s, a) [∆fπ(s, a)− γ(Pπ∆fπ)(s, a)]︸ ︷︷ ︸ erroff (π): off-support error ,
where C (ν;µ,F , π) is defined in Definition 1, (dπ \ ν)(s, a) := max(dπ(s, a) − ν(s, a), 0) and (Pπf)(s, a) = Es′∼P (·|s,a)[f(s′, π)] for any f .
Bias-variance decomposition. Note that decomposition of our error bound into on-support and off-support parts effectively achieves a bias-variance tradeoff. A small value of the concentrability threshold C2 requires the choice of the distribution ν closer to µ, which results in better estimation error guarantee (which is O( √ C2/n)) when we transfer from µ to ν, but potentially pays a high bias due to the mismatch between dπ and ν. A larger threshold permits more flexibility in choosing ν similar to dπ for a smaller bias, but results in a larger variance and estimation error. Rather than commit to a particular tradeoff, our estimator automatically adapts to the best possible splitting (Figure 1 illustrates this concept) by allowing us to choose the best thresholdC2. 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 dπ \ ν 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(π) and J(π̂) can still be small even with a large off-support mass. The following corollary formally states this property. Corollary 1 (“Double Robustness”). Under conditions of Theorem 3.1, for any π and C2 ≥ 0, erroff(π) = 0 when either (1) C (dπ;µ,F , π) ≤ C2, or, (2) ∆fπ − γPπ∆fπ ≡ 0.
Adaptive guarantees by algorithm design. As mentioned above, Theorem 3.1 implicitly selects the best bias-variance 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 et 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 is particularly challenging in offline RL, where even policy evaluation can be unreliable, this novel axis of adaptivity is an extremely desirable property of our approach.
Comparison to guarantees in the exploratory setting. When a dataset with full coverage is given, classical analyses provide near-optimality guarantees that compete with the optimal policy π⋆ with a polynomial sample complexity, when π⋆ ∈ Π 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 ∥ν/µ∥∞ for all admissible distributions ν ∈ {dπ : π ∈ Π}. On the other hand, it is easily seen that we can compete with π⋆ under much weaker conditions.
Corollary 2 (Competing with optimal policy). Under conditions of Theorem 3.1, if C (dπ⋆ ;µ,F , π⋆) ≤ C2, we have
J(π⋆)− J(π̂) ≤ O Vmax√C2 1− γ √ log |F||Π|δ n + √ C2(εF,F + εF ) 1− γ  . Notably, these milder coverage assumptions in Corollaries 1 and 2 provide offline RL counterparts to the benefits of policy-gradient-style methods with online access to the environment [Kakade and Langford, 2002; Scherrer, 2014; Agarwal et al., 2019].
Comparison with Liu et al. [2020]. The closest prior result to our work is that of [Liu et al., 2020], who develop a pessimistic estimator that truncates Bellman backups from state-action pairs infrequently visited by µ, 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 in high-dimensions and they incur additional errors from density estimation which we avoid. Further, their algorithms only compete with policies π where ∥dπ/µ∥∞ is bounded instead of the more general result that we provide, and makes their results vacuous in a linear 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 a behavior policy πb with µ = dπb , and demonstrate that their algorithms always return a policy competitive with πb. In our setup, this is straightforward as dπb is always covered, as shown next.
Corollary 3 (Bounded degradation from behavior policy). Under conditions of Theorem 3.1, if µ = dπb for some policy πb ∈ Π, we have
J(πb)− J(π̂) ≤ O  Vmax 1− γ √ log |F||Π|δ n + √ εF,F + εF 1− γ  . Proof sketch of Theorem 3.1. We now briefly describe the core ideas in the proof. More detailed arguments are deferred to the full proof in Appendix B.1.
The key to prove Theorem 3.1 is to translate the J(π)− J(π̂) to the Bellman error of value functions in the version space Fπ,ε. Our main proving strategies are as follows:
1. As the selection of ε = εr ensures the accurate estimation Qπ is contained in the version space Fπ̂,ε for any π, we can obtain J(π) − J(π̂) ≤ maxf∈Fπ,ε f(s0, π) − minf∈Fπ̂,ε f(s0, π̂) + approximation error.
2. By the optimality of π̂, we have minf∈Fπ̂,ε f(s0, π̂) ≥ minf∈Fπ,ε f(s0, π). This indicates that J(π)− J(π̂) ≤ maxf∈Fπ,ε f(s0, π)−minf∈Fπ,ε f(s0, π) + approximation error.
3. By using a standard telescoping argument (e.g., [Xie and Jiang, 2020, Lemma 1]), maxf∈Fπ,ε f(s0, π) − minf∈Fπ,ε f(s0, π) can be upper bounded by the Bellman error of argmaxf∈Fπ,ε f(s0, π) and argminf∈Fπ,ε f(s0, π) over distribution dπ .
After combining all the three steps above together and considering the distribution shift effect, we complete the proof.

heading: 3.1 Results for Linear Function Approximation
text: Here we perform a case study in linear function approximation. We will show that our results—when 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 a factor of O(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 = 11−γ for consistency with literature). Definition 2 (Linear Function Approximation). Let ϕ : S ×A → Rd be a feature mapping. Without loss of generality, we assume ∥ϕ(s, a)∥2 ≤ 1, ∀(s, a) ∈ S ×A. We define the value-function class FΦ as FΦ := {ϕ(·, ·)Tθ : θ ∈ Rd, ϕ(·, ·)Tθ ∈ [0, Vmax]}, and the policy class ΠΦ consists of the greedy policies of each value function in FΦ. Assumption 3 (Realizability and Completeness). εF,F = εF = 0.
Note that, when the feature mapping ϕ(·, ·) is the one induced by the linear MDP [Jin et al., 2020], it automatically ensure that π⋆ ∈ ΠΦ and FΦ 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 is our main result in the linear function approximation setting. Theorem 3.2. Suppose the value-function class F is a linear function class that satisfies realizability and completeness (Definition 2 and Assumption 3) and π̂ is the output of Eq.(3.2) using valuefunction class FΦ and policy class ΠΦ. If we choose ε = cV 2maxd log Vmax|A|d δ /n, then, for any policy π : S → ∆(A), we have
J(π)− J(π̂) ≤ O  Vmax 1− γ √ d log Vmax|A|dδ n Edπ [√ ϕ(s, a)TΣ−1D ϕ(s, a) ] , where c is an absolute constant, and ΣD := ED [ ϕ(s, a)ϕ(s, a)T ] .
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 finite-horizon linear MDP setting. If we translate their result to the discounted setting by setting H = O(1/(1− γ)), we enjoy a net improvement of order O(d) in sample complexity when the action space is finite and small. To make it concrete, that is O( √ d2 log(dn/δ)/n) vs. O( √ d log(d|A|/δ)/n) error bounds. The bound also shows that having a full-rank ΣD (which is ensured by a full-rank covariance under µ) is sufficient for consistent offline RL in linear function approximation. Crucially, the full-rank covariance is an easily checkable condition on data, as opposed to unverifiable concentrability assumptions. As a caveat, our results do not imply a computationally efficient algorithm, as a naïve implementation involves evaluating each policy pessimistically to pick the best. We discuss a computationally efficient adaptation of our approach in the next section.

heading: 4 Practical Algorithm — Regularized Offline Policy Optimization
text: A major challenge using the proposed algorithm in Section 3 in practice is that searching the policy with the best pessimistic evaluation over the policy space Π 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 is summarized in Algorithm 1. It has three key differences from the information-theoretic version in Eq.(3.2):
Algorithm 1 PSPI: Pessimistic Soft Policy Iteration Input: Batch data D, regularization coefficient λ.
1: Initialize policy π1 as the uniform policy. 2: for t = 1, 2, . . . , T do 3: Obtain the pessimistic estimation for πt as ft,
ft ← argmin f∈F (f(s0, πt) + λE(f, πt;D)) , (4.1)
where E(f, πt;D) is defined in Eq.(3.1). 4: Calculate πt+1 by,
πt+1(a|s) ∝ πt(a|s) exp (ηft(s, a)) , ∀s, a ∈ S ×A.
5: end for 6: Output π̄ := Unif(π[1:T ]). ▷ uniformly mix π1, . . . , πT at the trajectory level
1. The pessimistic policy evaluation is now performed via regularization (Line 3) instead of constrained optimization.
2. Instead of searching over an explicit policy space Π, we search over a policy class implicitly induced from F (defined in Eq.(4.2)) and therefore no longer have a policy class independent of F separately, which is a common practice in API-style algorithms [Munos, 2003; Antos et al., 2008; Lazaric et al., 2012].
3. We optimize the policy using mirror descent updates, which yields computationally tractable optimization over the implicit policy class. This property has been leveraged in many prior works, although typically in online RL settings [Even-Dar 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 be relaxed if a stronger structural assumption is made on the MDP (e.g., linear MDPs [Jin et al., 2020, 2021]).

heading: 4.1 Analysis of Algorithm 1
text: We now provide the analysis of Algorithm 1 in this section. For ease of presentation, we formally define the implicit policy class for this section:
ΠSPI := {π′(·|s) ∝ exp(η t∑
i=1
f (t)(s, ·)) : 1 ≤ t ≤ T, f (1), . . . , f (i) ∈ F}, (4.2)
which is the natural policy class for soft policy-iteration approaches. The following theorem describes the performance guarantee of π̄.
Theorem 4.1. Let λ = 3 √ Vmax/(1−γ)2ε2r with εr in Eq.(3.3), η = √
log |A| 2V 2maxT
, and π̄ be obtained from Algorithm 1. For any policy π : S → ∆(A) we wish to compete with, suppose Assumptions 1 and 2 hold with respect to the policy class ΠSPI ∪ {π}. Then, for any constant C2 ≥ 1, we have with probability at least 1− δ,
J(π)− J(π̄)
≤ O √C2 √εF,F + εF
1− γ + Vmax 1− γ 3
√ T log |F|δ
n + 3 √ VmaxεF (1− γ)2  ︸ ︷︷ ︸
erron(π): on-support error
+O ( Vmax 1− γ √ log |A| T ) ︸ ︷︷ ︸
optimization error
+ 1
T T∑ t=1  min ν:C (ν;µ,F,πt)≤C2 ∣∣∣∣∣∣ ∑ (s,a)∈S×A (dπ \ ν)(s, a) [ft(s, a)− (T πtft)(s, a)] 1− γ ∣∣∣∣∣∣ 
︸ ︷︷ ︸ erroff (π): off-support error
,
where C (ν;µ,F , πt) is defined in Definition 1, (dπ \ ν)(s, a) := max(dπ(s, a)− ν(s, a), 0).
We provide a proof sketch of Theorem 4.1 at the end of this section, and defer the full proof to Appendix C. We now make a few remarks about the results in Theorem 4.1.
Measurement of distribution shift effect. Compared with the information-theoretical result (provided in Theorem 3.1), the measurement of distribution shift in Theorem 4.1 depends on the optimization trajectory. That is, it measures the distance between two distribution ν and µ by C (ν;µ,F , πt) (π[1:T ] is the sequence of policies produced by the algorithm) whereas Theorem 3.1 uses C (ν;µ,F , π) (π 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 C 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 is 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 = O(n2/5), leading to an overall O(n−1/5) rate. While such a rate is relatively slow, we remark that the complexity bound of Π is conservative, and in certain cases it is possible to obtain much sharper bounds: for example, in linear function approximation (Section 3.1), ΠSPI are a priori captured by the space of softmax policies, whose complexity has no dependence on T (up to mild logarithmic dependence due to norms). That is, the erron(π) term in Theorem 4.1 reduces to Õ(Vmax1−γ 3 √ d/n) (εF,F = εF = 0 in linear function approximation), and yields an overall O(n−1/3) rate.
Bias-variance decomposition. Similar to Theorem 3.1, Theorem 4.1 also allows arbitrary decomposition of the error bound into on-support and off-support components by setting the concentrability threshold C2, which serves as a bias-variance tradeoff as before. In fact, the splitting can be done separately for each πt in 1 ≤ 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 “highquality”, we can further simplify the performance guarantees, but the requirement of “high-quality” is different from that of Corollary 1. We make it formal in the following corollary. Corollary 4 (“Double Robustness”). For any π and C2 ≥ 0, erroff(π) = 0 when either (1) C (dπ;µ,F , πt) ≤ C2 for all t ∈ [T ], or, (2) ft − T πt∆ft ≡ 0 for all t ∈ [T ].
We note that the conditions above depend on the optimization trajectory through their dependence on πt, but can be made algorithm-independent by instead asserting the stronger requirement that C (dπ, µ,F , π′) ≤ C2 for all π′ ∈ ΠSPI in the first condition.
Competing with the optimal policy. As before, we can provide a 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 C (dπ⋆ ;µ,F , π) ≤ C2 for all π ∈ ΠSPI, we have
J(π⋆)− J(π̂) ≤ O Vmax√C2 1− γ ( log |F|δ log |A| n )1/5 + √ C2(εF,F + εF ) 1− γ  . Note that the conditions of Corollary 5 are satisfied as before whenever ∥dπ⋆/µ∥∞ ≤ C2.
Computationally-efficient implementation with linear function approximation We remark that our algorithm is computationally efficient when the value-function class F is linear, that is, F := {ϕ(·, ·)Tθ : θ ∈ Rd}. In this case, the objective of Eq.(4.1) has a closed-form expression which is quadratic in θ. In addition, under additional matrix invertibility conditions, Eq.(4.1) 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 a proof sketch showing the key insights used in establishing the proof.
Proof sketch of Theorem 4.1. Our proof constructs a corresponding MDPMt for every ft, πt pair. EachMt has the same dynamics as the ground-truth MDP, but chooses a different reward function, such that ft is the Q-function of πt in Mt, QπtMt (we use the subscript of Mt to denote the corresponding value or operator in MDPMt). Our proof relies on some key properties ofMt, such as Qπ − T πMtQ π = ft − T πtft. We decompose J(π)− J(π̄) as follows.
J(π)− J(π̄) ≤ 1 T T∑ t=1
(JMt(π)− JMt(πt))︸ ︷︷ ︸ optimization error
+ 1
T T∑ t=1
(J(π)− JMt(π))︸ ︷︷ ︸ controlled by ∥Qπ−T πMtQ π∥2,dπ=∥ft−T πtft∥2,dπ
+ approximation/statistical errors.
The proof is completed by bounding ∥ft−T πtft∥2,dπ on both on-support and off-support regions.

heading: 5 Conclusions
text: This paper investigates sample-efficient offline reinforcement learning without data coverage assumptions (e.g., concentrability). To achieve that goal, our paper contributes several crucial improvements to the literature. We introduce the concept of Bellman-consistent pessimism. It enables the sample-efficient guarantees with only the Bellman-completeness assumption which is standard in the exploratory setting, whereas the point-wise/bonus-based pessimism popularly adopted in the literature usually requires stronger and/or extra assumptions. Algorithmically, we demonstrate how to implicitly infer a policy value lower bound through a version space and provide a tractable implementation. A particularly important aspect of 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 O(d) improvement in sample complexity, compared with the best-known recent work of offline RL in linear MDPs, whenever the action space is finite and small.
As of limitations and future work, the sample complexity of our practical algorithm is worse than that of the information-theoretic approach, and it will be interesting to close this gap. Another future direction is to empirically evaluate PSPI on benchmarks and compare it to existing approaches.

heading: Acknowledgment
text: Part of this work was carried out while TX and AA worked at Microsoft Research. NJ acknowledges funding support from the ARL Cooperative Agreement W911NF-17-2-0196, NSF IIS-2112471, and Adobe Data Science Research Award.

Review summaries:
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.

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.

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.