Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
Year: 2021

Abstract:
We study the offline reinforcement learning (offline RL) problem, where the goal is to learn a reward-maximizing policy in an unknown Markov Decision Process (MDP) using the data coming from a policy μ. In particular, we consider the sample complexity problems of offline RL for finite-horizon MDPs. Prior works study this problem based on different data-coverage assumptions, and their learning guarantees are expressed by the covering coefficients which lack the explicit characterization of system quantities. In this work, we analyze the Adaptive Pessimistic Value Iteration (APVI) algorithm and derive the suboptimality upper bound that nearly matches O  H ∑

text: O  H∑ h=1 ∑ sh,ah dπ ? h (sh, ah) √ VarPsh,ah (V ? h+1 + rh) dµh(sh, ah) √ 1 n  . (1) In complementary, we also prove a per-instance information-theoretical lower bound under the weak assumption that dµh(sh, ah) > 0 if d π?
h (sh, ah) > 0. Different from the previous minimax lower bounds, the per-instance lower bound (via local minimaxity) is a much stronger criterion as it applies to individual instances separately. Here π? is a optimal policy, µ is the behavior policy and dµh is the marginal state-action probability. We call (1) the intrinsic offline reinforcement learning bound since it directly implies all the existing optimal results: minimax rate under uniform data-coverage assumption, horizon-free setting, single policy concentrability, and the tight problem-dependent results. Later, we extend the result to the assumption-free regime (where we make no assumption on µ) and obtain the assumption-free intrinsic bound. Due to its generic form, we believe the intrinsic bound could help illuminate what makes a specific problem hard and reveal the fundamental challenges in offline RL.

heading: 1 Introduction
text: In offline reinforcement learning (offline RL Levine et al. [2020], Lange et al. [2012]), the goal is to learn a reward-maximizing policy in an unknown environment (Markov Decision Process or MDP) using the historical data coming from a (fixed) behavior policy µ. Unlike online RL, where the agent can keep interacting with the environment and gain new feedback by exploring unvisited state-action space, offline RL usually populates when such online interplays are expensive or even unethical. Due to its nature of without the access to interact with the MDP model (which causes the distributional mismatches), most of the literature that study the sample complexity / provable efficiency of offline RL (e.g. Le et al. [2019], Chen and Jiang [2019], Xie and Jiang [2020, 2021],
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Yin et al. [2021a,b], Ren et al. [2021], Rashidinejad et al. [2021], Xie et al. [2021b]) rely on making different data-coverage assumptions for making the problem learnable and provide the near-optimal worst-case performance bounds that depend on their data-coverage coefficients. Those results are valuable in general as they do not depend on the structure of the particular problem, therefore, remain valid even for pathological MDPs. But is this good enough?
In practice, the empirical performances of offline reinforcement learning (e.g. Gulcehre et al. [2020], Fu et al. [2020, 2021], Janner et al. [2021]) are often far better than what those non-adaptive / problem-independent bounds would indicate. Although empirical evidence can help explain why we may observe better or worse performances on different MDPs, a systematic understanding of what types of decision processes and what kinds of behavior policies are inherently easier or more challenging for offline RL is lacking. Besides, despite the fact that a non-adaptive bound can learn even the pathological examples within the assumption family, there is no guarantee for the instances outside the family. However, practical offline reinforcement learning problems are usually beyond the scope of certain data-coverage assumptions, which limits the applicability of those results. Can we make as few assumptions as possible? Or even more, what can we guarantee when no assumption is made about offline learning?
Those motivate us to derive the provably efficient bounds that are adaptive to the individual instances but only require minimal assumptions so they can be widely applied in most cases. Ideally, such bounds should characterize the system structures of the specific problems, hold even for peculiar instances that do not satisfy the standard data-coverage assumptions, and recover the worst-case guarantees when the assumptions are satisfied. As mentioned in Zanette and Brunskill [2019], a fully adaptive characterization in RL is important as it might bring considerable saving in the time spent designing domain-specific RL solutions and in training a human expert to judge and recognize the complexity of different problems.

heading: 1.1 Our contribution
text: In this work, we provide the analysis for the adaptive pessimistic value iteration (APVI) (Algorithm 1) with finite horizon time-inhomogeneous (non-stationary) MDPs and derive a strong adaptive bound that is near-optimal under the weak assumption dµh(sh, ah) > 0 if d π?
h (sh, ah) > 0 (Theorem 4.1). Specifically, our bound (quantity (1)) explicitly depends on the marginal importance ratios (between the optimal policy π? and the behavior policy µ) and the per-step conditional variances. In addition, we provide an instance-dependent (local minimax) lower bound (Theorem 4.3) to certify (1) is nearly optimal at the instance level for offline learning and call it the intrinsic offline learning bound. The intrinsic bound has the following consequences.
• In the non-adaptive / worst-case regime (4.1-4.3), the intrinsic bound implies Õ(H3/dm 2) complexity under the uniform data-coverage 2.1, Õ(H3SC?/ 2) complexity under the single policy concentrability assumption 2.3 and Õ(H/dm 2) complexity when the sum of rewards is bounded by 1. All of those are optimal in their respectively regimes [Yin et al., 2021a, Rashidinejad et al., 2021, Xie et al., 2021b, Ren et al., 2021];
• In the adaptive domain (4.4), the intrinsic bound implies the tight problem-dependent counterpart of Zanette and Brunskill [2019], yields Õ(H3/ndm) fast convergence in the deterministic systems, has improved complexity in the partially deterministic systems and a family of highly mixing problems, and remains optimal when reducing to the tabular contextual bandits.
Beyond the above, due to the generic form of the intrinsic bound, we could come up with as many problem instances (that are of our interests) as possible and study their properties. In this sense, the intrinsic bound helps illuminate the fundamental nature of offline RL.
Furthermore, as a step towards assumption-free offline reinforcement learning, we build a modified AVPI and obtain an adaptive bound that could characterize the suboptimality gap in the state-action space that is agnostic to the behavior policy (Theorem 5.1). To the best of our knowledge, all of these results are the first of its kinds.

heading: 1.2 Related work
text: Finite sample analysis for offline reinforcement learning can be traced back to Szepesvári and Munos [2005], Antos et al. [2008a,b] for the infinite horizon discounted setting via Fitted Q-Iteration (FQI) type function approximation algorithms. [Chen and Jiang, 2019, Le et al., 2019, Xie and Jiang, 2021, 2020] follow this line of research and derive the information-theoretical bounds. Recently, Xie and Jiang [2021] considers the offline RL with only the realizability assumption, Liu et al. [2020], Chang et al. [2021] considers the offline RL without sufficient coverage and Kidambi et al. [2020], Uehara and Sun [2021] uses the model-based approach for addressing offline RL. Under those weak coverage assumption, their finite sample analysis are suboptimal (e.g. in terms of the effective horizon (1− γ)−1). Recently, Yin et al. [2021a,b], Ren et al. [2021] study the finite horizon case. In the linear MDP case, Jin et al. [2020] studies the pessimistic algorithm for offline policy learning under only the compliance assumption, and, concurrently, Xie et al. [2021a] proposes the general pessimistic function approximation framework with instantiation in linear MDP and Zanette et al. [2021] shows actor-critic style algorithm is near-optimal for linear Bellman complete model. In addition, Wang et al. [2021], Zanette [2021] prove some exponential lower bounds under their linear function approximation assumptions.
Among them, there are a few works that achieve the sample optimality under their respective assumptions. Under the uniform data coverage (minimal state-action probability dm > 0), Yin et al. [2021a] first proves the optimal Õ(H3/dm 2) complexity in the time-inhomogeneous MDP. Recently, Yin et al. [2021b] designs the offline variance reduction algorithm to achieve the optimal Õ(H2/dm 2) rate for the time-homogeneous case. Under the setting where the total cumulative reward is bounded by 1, Ren et al. [2021] obtains the horizon-free result with Õ(1/dm). More recently, Rashidinejad et al. [2021] considers the single concentrability coefficient C? := maxs,a dπ ?
(s, a)/dµ(s, a) and derives the upper bound Õ[(1 − γ)−5SC?/ 2] in the infinite horizon setting which is recently improved by the concurrent work Xie et al. [2021b]. While those worst-case guarantees are desirable, none of them can explain the hardness of the individual problems.1

heading: 2 Preliminaries
text: Episodic non-stationary (time-varying) reinforcement learning. A finite-horizon Markov Decision Process (MDP) is denoted by a tuple M = (S,A, P, r,H, d1) [Sutton and Barto, 2018], where S is the finite state space and A is the finite action space with S := |S| <∞, A := |A| <∞. A nonstationary transition kernel Ph : S ×A× S 7→ [0, 1] maps each state action(sh, ah) to a probability distribution Ph(·|sh, ah) and Ph can be different across the time. Besides, r : S ×A 7→ R is the expected instantaneous reward function satisfying 0 ≤ r ≤ 1. d1 is the initial state distribution. H is the horizon. A policy π = (π1, . . . , πH) assigns each state sh ∈ S a probability distribution over actions according to the map sh 7→ πh(·|sh) ∀h ∈ [H]. An MDP together with a policy π induce a random trajectory s1, a1, r1, . . . , sH , aH , rH , sH+1 with s1 ∼ d1, ah ∼ π(·|sh), sh+1 ∼ Ph(·|sh, a),∀h ∈ [H] and rh is a random realization given the observed sh, ah.
Q-values, Bellman (optimality) equations. The value function V πh (·) ∈ RS and Q-value function Qπh(·, ·) ∈ RS×A for any policy π is defined as: V πh (s) = Eπ[ ∑H t=h rt|sh = s], Qπh(s, a) =
Eπ[ ∑H t=h rt|sh, ah = s, a], ∀s, a ∈ S,A, h ∈ [H]. The performance is defined as vπ :=
Ed1 [V π1 ] = Eπ,d1 [∑H t=1 rt ] , where we denote V πh , Q π h as column vectors and Ph ∈ RSA×S the transition matrix, then the vector form Bellman (optimality) equations follow ∀h ∈ [H]: Qπh = rh + PhV π h+1, V π h = Ea∼πh [Qπh], Q?h = rh + PhV ?h+1, V ?h = maxaQ?h(·, a).In addition, we denote the per-step marginal state-action occupancy dπh(s, a) as: d π h(s, a) := P[sh = s|s1 ∼ d1, π] · πh(a|s), which is the marginal state-action probability at time h. Offline setting and the goal. The offline RL requires the agent to find a policy π such that the performance vπ is maximized, given only the episodic data D = {(sτh, aτh, rτh, sτh+1)} h∈[H] τ∈[n] rolled out from some behavior policy µ. The offline nature requires we cannot change µ and in particular we
1We do mention Zanette et al. [2021] is near-optimal in their setting, but it is unclear whether it remains optimal in the standard setting where Qπ ∈ [0, H], since there is an additional H factor by rescaling.
do not assume the functional knowledge of µ. That is to say, given the batch data D and a targeted accuracy > 0, the offline RL seeks to find a policy πalg such that v? − vπalg ≤ .

heading: 2.1 Assumptions in offline RL
text: We revise several types of assumptions proposed by existing studies that can yield provably efficient results. Recall dµh(sh, ah) is the marginal state-action probability and µ is the behavior policy.
Assumption 2.1 (Uniform data coverage [Yin et al., 2021a]). The behavior policy obeys that dm := minh,sh,ah d µ h(sh, ah) > 0. Here the infimum is over all the states satisfying there exists certain policy so that this state can be reached by the current MDP with this policy.
This is the strongest assumption in offline RL as it requires µ to explore each state-action pairs with positive probability. Under 2.1, it mostly holds 1/dm ≥ SA. This reveals offline learning is generically harder than the generative model setting [Agarwal et al., 2020] in the statistical sense. On the other hand, this is required for the uniform OPE task in Yin et al. [2021a] as it seeks to simultaneously evaluate all the policies within the policy class and it is in general a harder task than offline learning itself.
Assumption 2.2 (Uniform concentrability Szepesvári and Munos [2005], Chen and Jiang [2019]). For all the policies, Cµ := supπ,h ||dπh(·, ·)/d µ h(·, ·)||∞ <∞.
This is a classical offline RL condition that is commonly assumed in the function approximation scheme (e.g. Fitted Q-Iteration). Qualitatively, this is a uniform data-coverage assumption that is similar to Assumption 2.1, but quantitatively, the coefficient Cµ can be smaller than 1/dm due the dπh term in the numerator.
Assumption 2.3 (Liu et al. [2019]). There exists one optimal policy π?, s.t. ∀sh, ah ∈ S,A, dµh(sh, ah) > 0 if d π?
h (sh, ah) > 0. We further denote the trackable set as Ch := {(sh, ah) : dµh(sh, ah) > 0}.
Assumption 2.3 is (arguably) the weakest assumption needed for accurately learning the optimal value v? and we will use 2.3 for most parts of this paper. It only requires µ to trace the state-action space of one optimal policy and can be agnostic at other locations. Rashidinejad et al. [2021], Xie et al. [2021b] considers this assumption and provide analysis is based on the single concentrability coefficient C? := maxs,a dπ ?
(s, a)/dµ(s, a). The dependence on C? makes their result less adaptive since there can be lots of locations that have the ratio dπ ?
(s, a)/dµ(s, a) much smaller than C?. Furthermore, what could we end up with when 2.3 is not met? We will provide our answers in the subsequent sections.

heading: 3 A warm-up case study: Vanilla Pessimistic Value Iteration
text: As a step towards the optimal and strong adaptive offline RL bound, we analyze the vanilla pessimistic value iteration (VPVI), a tabular counterpart of pessimistic value iteration (PEVI initiated in Jin et al. [2020]), to understand what is missing for achieving the fully adaptivity. In particular, VPVI relies on the model-based construction. Model-based Components. Given data D = {(sτh, aτh, rτh, sτh+1)}h∈[H]τ∈[n] , we denote nsh,ah :=∑n τ=1 1[s τ h, a τ h = sh, ah] be the total counts that visit (sh, ah) pair at time h, then we use the offline plug-in estimator to construct the estimators for Ph and rh as:
P̂h(s ′|sh, ah) =
∑n τ=1 1[(s τ h+1, a τ h, s τ h) = (s ′, sh, ah)]
nsh,ah , r̂h(sh, ah) =
∑n τ=1 1[(a τ h, s
τ h) = (sh, ah)] · rτh nsh,ah ,
(2) if nsh,ah > 0 and P̂h(s
′|sh, ah) = 1/S, r̂h(sh, ah) = 0 if nsh,ah = 0. In particular, we use the word “vanilla” as it directly mirrors Jin et al. [2020] with a pessimistic penalty of order O(H/√nsh,ah).2
With P̂h, r̂h in Algorithm 2 (which we defer to Appendix), VPVI guarantees the following:
2This is due to √ φ (sh, ah) > Λ−1h φ (sh, ah) reduces to √
1/nsh,ah when setting φ(sh, ah) = 1(sh, ah) and λ = 0.
Theorem 3.1. Under the Assumption 2.3, denote d̄m := minh∈[H]{dµh(sh, ah) : d µ h(sh, ah) > 0}. For any 0 < δ < 1, there exists absolute constants c0, C ′ > 0, such that when n > c0 · 1/d̄m · ι (ι = log(HSA/δ)), with probability 1− δ, the output policy π̂ of VPVI satisfies
0 ≤ v? − vπ̂ ≤ C ′H H∑ h=1 ∑ (sh,ah)∈Ch dπ ? h (sh, ah) · √
ι
n · dµh(sh, ah) . (3)
The full proof can be found in Appendix C. Theorem 3.1 makes some improvements over the existing works. First, it is more adaptive than the results with uniform data-coverage Assumption 2.1 (Yin et al. [2021a], Ren et al. [2021]). In addition, by straightforward calculation (3) can be bounded by Õ( √ H4SC?/n) which improves VI-LCB [Rashidinejad et al., 2021] by a factor of H .3 Besides, the analysis of VPVI also improves the direct reduction of PEVI [Jin et al., 2020] in the tabular case by a factor SA since their β = SAH when d = SA.
However, VPVI is not optimal as the dependence on horizon is H4 which does not match the optimal worst case guaranteeH3 [Yin et al., 2021a] in the nonstationary setting. Also, the explicit dependence on H in (3) possibly hides some key features of the specific offline RL instances. For example, no improvement can be made if the system has the deterministic transition.
Algorithm 1 Adaptive (assumption-free) Pessimistic Value Iteration or LCBVI-Bernstein 1: Input: Offline dataset D = {(sτh, aτh, rτh, sτh+1)}n,Hτ,h=1. Set C1 = 2, C2 = 14, failure probability δ. 2: Initialization: Set V̂H+1(·)← 0. Set ι = log(HSA/δ). (if assumption-free, set M†, M̂† as in Section 5.) 3: for time h = H,H − 1, . . . , 1 do 4: Set Q̂h(·, ·)← r̂h(·, ·) + (P̂h · V̂h+1)(·, ·) (use r̂†h + (P̂ † h · V̂h+1) if assumption-free)
5: ∀sh, ah, set Γh(sh, ah) = C1
√ Var
P̂sh,ah (r̂h+V̂h+1)·ι
nsh,ah + C2H·ι nsh,ah if nsh,ah ≥ 1, o.w. set to CHι1 . 6: (If assumption-free, use C1 √
Var P̂ † sh,ah (r̂†h + V̂h+1) · ι/nsh,ah + C2H·ι nsh,ah if nsh,ah ≥ 1, o.w. use 0.)
7: Set Q̂ph(·, ·)← Q̂h(·, ·)− Γh(·, ·). Set Qh(·, ·)← min{Q̂ p h(·, ·), H − h+ 1} +. // Pessmistic update 8: ∀sh, Select π̂h(·|sh)← argmaxπh〈Qh(sh, ·), πh(·|sh)〉. Set V̂h(sh)← 〈Qh(sh, ·), π̂h(·|sh)〉. 9: end for
10: Output: {π̂h}.

heading: 4 Intrinsic Offline Reinforcement Learning bound
text: Now we go deeper to understand what is the more intrinsic characterization for offline reinforcement learning. From the study of VPVI, penalizing the Q-function by Õ(H/√nsh,ah) is crude as it estimates the confidence width of Q̂h in Algorithm 2 too conservatively therefore loses the accuracy (the bound is suboptimal). This motivates us to use empirical standard deviation instead to create a more adaptive (and also less conservative) Bernstein-type confidence width as the pessimistic penalty:
Γh(sh, ah) = Õ [√√√√VarP̂sh,ah (r̂h + V̂h+1) nsh,ah + H nsh,ah ] (if nsh,ah > 0); = Õ(H) (if nsh,ah = 0). (4)
and update Q̂h ← Q̂h − Γh. On one hand, √
VarP̂sh,ah (r̂h + V̂h+1)/nsh,ah is a “less pessimistic” penalty than VPVI due to √
VarP̂ (r̂h + V̂h+1) ≤ H and critically this design is more data-adaptive since it holds negative view towards the locations with high uncertainties and recommends the locations that we are confident about, as opposed to the online RL (which encourages exploration in the uncertain locations). Such principles are not reflected by the isotropic design in VPVI. On the other hand, it carries the extremely negative view towards fully agnostic locations Õ(H) which in turn causes the agent unlikely to choose them. We summarized the this adaptive pessimistic value
3To be rigorous, translating the result from the infinite horizon setting to the finite horizon setting requires explanation. We add this discussion in Appendix D.
iteration (APVI) into the Algorithm 1, with P̂h, r̂h defined in (2). APVI has the following guarantee. A sketch of the analysis is presented in Section B and Appendix F includes the full proof. Theorem 4.1 (Intrinsic offline RL bound). Under the Assumption 2.3, denote d̄m := minh∈[H]{dµh(sh, ah) : d µ h(sh, ah) > 0}. For any 0 < δ < 1, there exists absolute constants c0, C ′ > 0, such that when n > c0 · 1/d̄m · ι (ι = log(HSA/δ)), with probability 1− δ, the output
policy π̂ of APVI (Algorithm 1) satisfies (Õ hides log factor and higher order terms)
0 ≤ v? − vπ̂ ≤ C ′ H∑ h=1 ∑ (sh,ah)∈Ch dπ ? h (sh, ah) ·
√ VarPsh,ah (rh + V ? h+1) · ι
n · dµh(sh, ah) + Õ
( H3
n · d̄m
) (5)
Remark 4.2. APVI (Algorithm 1) can also be called LCBVI-Bernstein as it creates the offline counterpart of UCBVI in Azar et al. [2017]. However, to highlight that the resulting bound fully adapts to the specific system structure, we use the word “adaptive” instead.
APVI makes significant improvements in a lot of aspects. First and foremost, the dominate term is fully expressed by the system quantities that admits no explicit dependence on H,S,A. To the best of our knowledge, this is the first offline RL bound that concretely depicts the interrelations within the problem when the problem instance is a tuple (M,π?, µ): an MDP M (coupled with the optimal policy π?) with the data rolling from an offline logging policy µ. As we will discuss later, this result indicates (nearly) all the optimal worst-case non-adaptive bounds (and clearly also the VPVI) under their respective regimes / assumptions. Thus, (5) is generic. More interestingly, Theorem 4.1 caters to the specific MDP structures and adaptively yields improved sample complexities (e.g. faster convergence in deterministic systems) that existing works cannot imply. Such features are crucial as it helps us to understand what type of problems are harder / easier than others, and even more, in a quantitative way. Last but not least, to illustrate this bound exhibits the intrinsic nature of offline RL, we prove a per-instance dependent information-theoretical lower bound that shares a similar formulation. The proof of Theorem 4.3 can be found in Appendix G. Theorem 4.3 (Instance-dependent information theoretical offline lower bound). Denote G := {(µ,M) : ∃π? s.t. dµh(s, a) > 0 if dπ ?
h (s, a) > 0}. Fix an instance P = (µ,M) ∈ G. Let D consists of n episodes and define ξ =
suph,sh,ah,sh+1,dµh(sh,ah)·VarPsh,ah (V ? h+1)>0
Ph(sh+1|sh,ah)(V ?h+1(sh+1)−EPsh,ah [V ? h+1])√
2·dµh(sh,ah)·VarPsh,ah (V ? h+1)
. Let π̂ to be
the output of any algorithm. Define the local non-asymptotic minimax risk as
Rn(P) := sup P′∈G inf π̂ max Q∈{P,P′}
√ n · EQ [ v?(Q)− vπ̂ ] (6)
where v?(Q) denotes the optimal value under the instance Q. Then there exists universal constants c0, p, C > 0, such that if n ≥ c0H6ξ4/( ∑H h=1 ∑ sh,ah dπ ? h (sh, ah)
√ VarPsh,ah (V ?h+1)
ζ·dµh(sh,ah) )2, with
constant probability p > 0, Then we have (here ζ = H/d̄m):
Rn(P) ≥ C · H∑ h=1 ∑ (sh,ah)∈Ch dπ ? h (sh, ah) ·
√ VarPsh,ah (rh + V ? h+1)
ζ · dµh(sh, ah) , (7)
where P = (µ,M) and M = (S,A, P, r,H, d1). The interpretation of Theorem 4.3 is: for any instance P , learning requires (7) (divided by 1/ √ n) for any algorithm. Note this notion is significantly stronger than the previous minimax offline lower bounds [Yin et al., 2021a, Rashidinejad et al., 2021, Xie et al., 2021b, Jin et al., 2020] (where they only select a particular family of hard problems), therefore, their lower bounds in general do not hold for individual instances.
The quantity (1) nearly-matches the per-instance lower bound (7) (they deviate by a factor of ζ = H/d̄m due to the technical reason) and, in addition, we provide a matching minimax lower bound in Appendix H. These results certify Theorem 4.1 is not only adaptive but also near-optimal.
Hence, we call the quantity ∑H h=1 ∑ (sh,ah)∈Ch d π? h (sh, ah) · √ VarPsh,ah (rh+V ?h+1) n·dµh(sh,ah) intrinsic offline
reinforcement learning bound. In the sequel, we provide thorough discussions to explain the intrinsic bound embraces the fundamental challenges in offline RL and the strong adaptivity. The detailed technical derivations that are missing in Section 4.1-4.4 are deferred to Appendix I.

heading: 4.1 Optimality under Uniform data-coverage assumption
text: Under the uniform exploration Assumption 2.1 with parameter dm := minh,sh,ah d µ h(sh, ah) > 0, Yin et al. [2021a] analyzes the model-based plug-in approach and obtains the optimal sample complexity Õ(H3/dm 2) and shows Ω(H3/dm 2) is also the lower bound. Indeed, this rate can be directly implied by the intrinsic RL bound via Cauchy inequality and the Sum of Total Variance (Lemma J.6):4
H∑ h=1 〈dπ ? h (·),
√ VarP(·)(rh + V ? h+1)
n · dµh(·) 〉 = H∑ h=1 〈 √ dπ ? h (·),
√ dπ ?
h (·) VarP(·)(rh + V ?h+1) n · dm 〉
≤ H∑ h=1 ∥∥∥∥√dπ?h (·)∥∥∥∥ 2 ∥∥∥∥∥∥ √ dπ ? h (·) VarP(·)(rh + V ?h+1) n · dm ∥∥∥∥∥∥ 2 ≤ √ H ·Varπ?( ∑H h=1 rh) n · dm ≤ √ H3 n · dm (8)
which translates to Õ(H3/dm 2) complexity. Our result maintains the optimal worst-case guarantee when µ has the uniform data-coverage:
Proposition 4.4. Under Assumption 2.1 and apply Theorem 4.1, APVI achieves the sample complexity of minimax-rate Õ(H3/dm 2) (Theorem 4.1 and Theorem G.2 in Yin et al. [2021a]).
Remark 4.5. We believe if the MDP is time-invariant, then by a modified construction of P̂ , r̂ in (2) our result will imply the minimax-rate of Õ(H2/dm 2) as achieved in Yin et al. [2021b]. We include this discussion in Appendix I.

heading: 4.2 Bounded sum of total rewards and the Horizon-Free case
text: There is another thread of studies that follow the bounded sum of total rewards assumption: i.e. rh ≥ 0, ∑H h=1 rh ∈ [0, 1] [Krishnamurthy et al., 2016, Jiang et al., 2017, Zhang et al., 2021]. Such a setting is much weaker than the uniform bounded instantaneous reward condition, as explained in Jiang and Agarwal [2018]. In offline RL, Ren et al. [2021] derives the nearly horizon-free worst case bound Õ( √ 1/ndm) for the time-invariant MDPs, under the Assumption 2.1. As a comparison, our Theorem 4.1 achieves the following guarantee for the time-varying (non-stationary) MDPs.
Proposition 4.6. Assume rh ≥ 0, ∑H h=1 rh ≤ 1. Then in the time-varying case AVPI (Theorem 4.1)
outputs a policy π̂ such that the suboptimality gap v? − vπ̂ is bounded by Õ( √ H/ndm) with high probability under the Assumption 2.1.
4Here denotes element-wise multiplication. Also note under 2.1, our d̄m = dm.
The derivation is straightforward by using Varπ?( ∑H h=1 rh) ≤ 1 in (8). This proposition is interesting since it indicates when the MDP is non-stationary, Õ(H/dm 2) is required in the worst case even under ∑H h=1 rh ≤ 1.5 The extra H factor resembles the challenge that we have H transitions (P1, . . . , PH ) to learn, as opposed to the bandit-type 1/dm 2 result due to there is only one P throughout (time-invariant). This reveals that one hardness in solving the MDP is in proportion to the number of different transition kernels within the MDP. Such a finding could help researchers understand the special settings like low switching cost in transitions [Bai et al., 2019] or nonstationarity [Cheung et al., 2020].

heading: 4.3 Optimality with Single Concentrability
text: In the finite horizon discounted setting, Rashidinejad et al. [2021] proposes the single policy concentrability assumption which is defined as C? := maxh,s,a dπ ?
h (s,a) dµh(s,a) <∞ in the current episodic nonstationary MDP setting. As discussed in Appendix D, their lower bound translates to Ω( √ H3SC?
n ) and their VI-LCB algorithm yields Õ( √ H5SC?
n ) suboptimality gap in H-horizon case. Since single policy concentrability is strictly weaker than its uniform version (Assumption 2.2), we only discuss this set up. In particular, we have the following implication from our Theorem 4.1 (whose derivation can be found in Appendix I):
Proposition 4.7. Let π? be a deterministic policy such that C? := maxh,s,a dπ ?
h (s,a) dµh(s,a) < ∞. Then by Theorem 4.1, with high probability the output policy of APVI satisfies the suboptimality gap
Õ( √ H3SC?
n ) in the time-varying (non-stationary) MDPs.
This can computed similar to (8) except we use d π?
h (s,a) dµh(s,a) ≤ C?. Our implication improves the VI-LCB by the factor H2 (in terms of sample complexity) and is optimal (recover the concurrent Xie et al. [2021b]). Qualitatively, single concentrability is the same as Assumption 2.3, but the use of C? makes the bound highly problem independent and limits the adaptivity. Problem dependent bound is a more interesting domain as it tailors to each MDP separately. We discuss it now.

heading: 4.4 Problem dependent domain
text: We define the pre-step environmental norm (the finite horizon counterpart of Maillard et al. [2014]) as: Q?h = maxsh,ah VarPsh,ah (rh + V ? h+1) for all h ∈ [H], and relax the total sum of rewards to be
bounded by any arbitrary value B (i.e. ∑H h=1 rh ≤ B), then Theorem 4.1 implies:
Proposition 4.8. Under Assumption 2.1, with high probability, subopmality of AVPI is bounded by
min { Õ ( H∑ h=1 √ Q?h nd̄m ) , Õ (√H · B2 nd̄m )} + Õ( H3 nd̄m ).
Such a result mirrors the online version of the tight problem-dependent bound Zanette and Brunskill [2019] but with a more general pre-step environmental norm for the non-stationary MDPs.6 For the problem instances with either small B or small Q?h, our result yields much better performances, as discussed in the following.
Deterministic systems. For many practical applications of interest, the systems are equipped with low stochasticity, e.g. robotics, or even deterministic dynamics, e.g. the game of GO. In those scenarios, the agent needs less experience for each state-action therefore the learning procedure could be much faster. In particular, when the system is fully deterministic (in both transitions and rewards) then Q?h = 0 for all h. This enables a faster convergence rate of order H3 nd̄m and significantly improves
5Suppose in this case we can achieve Õ(1/dm 2) just like Ren et al. [2021], then by a rescaling we obtain the Õ(H2/dm 2) under the usual 0 ≤ rh ≤ 1 assumption which violates the Ω(H3/dm 2) lower bound.
6Zanette and Brunskill [2019] uses the maximal version by maximizing over h.
over the existing non-adaptive results that have order 1√ n . The convergence rate 1n matches Wen and Van Roy [2013] by translating their constant (in T ) regret into the PAC bound.
Partially deterministic systems. Practical worlds are complicated and we could sometimes have a mixture model which contains both deterministic and stochastic steps. In those scenarios, the main complexity is decided by the number of stochastic stages: suppose there are t stochastic Ph, rh’s and H − t deterministic Ph′ , rh′ ’s, then completing the offline learning guarantees t · √ maxQ?h/nd̄m
suboptimality gap, which could be much smaller than H · √
maxQ?h/nd̄m when t H .
Fast mixing domains. Consider a class of highly mixing non-stationary MDPs (a variant of Zanette and Brunskill [2018]) that satisfies the transition Ph(·|sh, ah) := νh(·) depends on neither the state sh nor the action ah. Define s̄t := arg maxV ?t (s) and st := arg maxV ? t (s). Also, denote rngV ? h to be the range of V ?h . In such cases, Bellman optimality equations have the form
V ?h (s̄h) = max a
( rh (s̄h, a) + ν > h V ? h+1 ) , V ?h (sh) = max
a
( rh (sh, a) + ν > h V ? h+1 ) ,
which yields rngV ?h = V ? h (s̄h) − V ?h (sh) = maxa rh (s̄h, a) − mina rh (sh, a) ≤ 1, and this in turn gives Q?h ≤ 1 + (rngV ?h )2 = 2. As a result, the suboptimality is bounded by Õ( √ H2/ndm) in the worst case. This result reveals, although this is a family of stochastic non-stationary MDPs, but it is only as hard as the family of stationary MDPs in the minimax sense (Ω(H2/dm 2)).
Tabular contextual bandits. Our result also implies Õ( ∑ x1,a1 dπ ? 1 (x1, a1) √ Var(r1) n·dµ1 (x1,a1) ) gap for the offline tabular contextual bandit problem and improves to Õ(1/ndm) when the reward is deterministic. In either cases, the result is optimal and this is due to: when r1 is deterministic, the agent only needs one sample at every location (see Bubeck and Cesa-Bianchi [2012] for a survey).

heading: 5 Towards Assumption-Free Offline RL
text: While assumption 2.3 is (arguably) the weakest assumption for correctly learning the optimal value, for the real-world applications even this might not be guaranteed. Can we still learn something meaningful? In this section, we consider this most general setting where the behavior policy µ can be arbitrary. In this case, µ might not cover any optimal policy π? (i.e. there might be high reward location (s, a) that µ can never visit, e.g. in the extreme case where a clumsy doctor only uses one treatment all the time), and, irrelevant to the number of episode n, a constant suboptimality gap needs to be suffered. To tackle this problem, we create a fictitious augmented MDP M† that can help characterize the discrepancy of the values between the original MDP M and the estimated MDP M̂†. In particular, M† is negative towards agnostic state-actions sh, ah by setting r † h = 0 and transitions to an absorbing state s†h+1.
Pessimistic augmented MDP. M† is defined with one extra state s†h for all h ∈ {2, . . . ,H+ 1} with the augmented state space S† = S ∪ {s†h}. The transition and the reward are defined as follows:
P †h(· | sh, ah) = { Ph(· | sh, ah), nsh,ah > 0, δ s † h+1 , sh = s † h or nsh,ah = 0. r†(sh, ah) = { r(sh, ah), nsh,ah > 0, 0, sh = s † h or nsh,ah = 0.
here δs is the Dirac measure and we denote V †π h and v †π to be the values under M†. M̂† is the empirical counterpart of M† with P̂ , r̂ (the same as (2)) replacing P , r. By Algorithm 1, we have Theorem 5.1 (Assumption-free offline reinforcement learning). Let us make no assumption for µ and still denote d̄m := minh∈[H]{dµh(sh, ah) : d µ h(sh, ah) > 0}. For any 0 < δ < 1, there exists absolute constants c0, C ′ > 0, such that when n > c0 · 1/d̄m · ι (ι = log(HSA/δ)), with probability 1− δ, the output policy π̂ of APVI satisfies (recall Ch := {(sh, ah) : dµh(sh, ah) > 0})
v?−vπ̂ ≤ H+1∑ h=2 d†π ? h (s † h)+C ′ H∑ h=1 ∑ (sh,ah)∈Ch d†π ? h (sh, ah)· √√√√VarP†sh,ah (r†h + V †π?h+1 ) · ι n · dµh(sh, ah) +Õ ( H3 nd̄m ) , (9)
where d†π ? h (sh, ah) ≤ dπ ? h (sh, ah), V †π? h (sh) ≤ V ?h (sh) for all sh, ah ∈ S ×A, and for all h ∈ [H], d†π ?
h (s † h) = ∑h−1 t=1 ∑ (st,at)∈S×A\Ct d †π? t (st, at). The proof is in Appendix E.
Take-aways of Theorem 5.1. In M†, there is no agnostic location any more since the original unknown spaces now all have known deterministic transitions to s† in M†. At a price, the algorithm has to suffer the constant suboptimality ∑H+1 h=2 d †π? h (s
† h) due to no data in the region. The quantity∑H+1
h=2 d †π? h (s † h) helps characterize the hardness when nothing is assumed about µ: it is always less than H (cannot suffer more than H suboptimality); under Assumption 2.1, it is 0 since M† = M with high probability (by Chernoff bound) and this causes S ×A\Ch = ∅; under Assumption 2.3, it is also 0 and 5.1 reduces to Theorem 4.1 (see Appendix F).

heading: 5.1 Assumption Free vs Without Great Coverage (Partial Coverage)
text: Recently there is a surge of studies that aim at weakening the assumptions of provable offline / batch RL. Those learning bounds are derived (mostly) under the insufficient data coverage assumptions. One type of works consider the assumption without great coverage (or partial coverage): Chang et al. [2021], Uehara and Sun [2021] assume maxs,a dπe(s, a)/µ(s, a) <∞ where πe is either an expert policy or a policy of great quality and they further compete against with this policy πe. Those assumptions are similar to 2.3 and therefore are stronger than the assumption-free RL we considered in 5.1.
In addition, there are other studies that apply to the case where µ can be arbitrary: Liu et al. [2020] considers the behavior policy with insufficient coverage probability ζ (see their Definition 1), and they end up with the constant suboptimality gap Vmax ζ1−γ (their Theorem 1), when the insufficient coverage probability ζ > 0, this gap has order (1− γ)−2, which is larger in order than the biggest possible suboptimality gap (1−γ)−1 therefore unable to characterize the essential statistical gap over the region that can never be visited by the behavior policy (and this happens similarly in Kidambi et al. [2020], see their Theorem 1); Jin et al. [2020] derive the nice assumption-free result via regularization and their bound can incur O(H2) constant gap when there is at least one (sh, ah) cannot be obtained by µ for all h ∈ [H] (i.e. replacing ndµh(sh, ah) by 1 in (3)). The concurrent work Xie et al. [2021a] provides a better characterization (and they call it off-support error) with roughly 11−γ ∑ (s,a)∈S×A (dπ\ν) (s, a) [∆fπ(s, a)− (T π∆fπ) (s, a)], however, in the worst case ∆fπ(s, a) − (T π∆fπ) (s, a) might be large (which depends on the quality (assumption) of the function approximation class).
In contrast, our ∑H+1 h=2 d †π? h (s † h) quantity (with d †π? h (s † h) = ∑h−1 t=1 ∑ (st,at)∈S×A\Ct d †π? t (st, at) ≤ 1) describes the “must-suffer” gap in a more precise way by absorbing all the agnostic probabilities into s† and it is always bounded between 0 and H . It reduces to 0 when π? is covered. The gap is always of order H (as opposed to O(H2)).

heading: 6 Discussion and Conclusion
text: This work studies the offline reinforcement learning problem and contributes the intrinsic offline learning bound which is a near-optimal and strong adaptive bound that subsumes existing worst-case bounds under various assumptions. The adaptive characterization of the intrinsic bound abandons the explicit dependence on H,S,A,C?, dm and helps reveal the fundamental hardness of each individual instances. In this sense, it draws a clearer picture of what offline reinforcement learning looks like and serves as a step towards instance optimality in offline RL.
Nevertheless, it is still unclear whether (5) is optimal over all the instances. For example, for fully deterministic systems, our bound provides a faster convergence H3/nd̄m, however, H3 might be very suboptimal comparing to algorithms that are designed specifically for deterministic MDPs, since the agent only need to experience each location (s, a) once to fully acquire the dynamic P (·|s, a) and r(s, a). Recently, Xiao et al. [2021] goes beyond the minimax (worst case) optimality and studies the instance optimality behavior for the simplified batch bandit setting. One of their findings is: for “easy enough” tasks, different type of algorithms can be equally good, provably. This seems to suggest instance optimality only matters for problems that are hard to learn. How to formally define the instance optimality metric for different problems remains an open problem and how to design a single algorithm that can achieve optimality for all instances could be challenging (or even infeasible). We leave those as the future works.

heading: Acknowledgment
text: The research is partially supported by NSF Awards #2007117 and #2003257. MY would like to thank Chenjun Xiao for bringing up a related literature [Xiao et al., 2021] and Masatoshi Uehara, Yu Bai for helpful suggestions.

Review summaries:
The paper proposes and analyzes the adaptive pessimistic value iteration algorithm for offline reinforcement learning. The authors study the sample complexity of the proposed algorithm and prove matching upper and lower bound. The paper also studies the regime where no assumption about the behaviour policy is made and provide a sub-optimality upper bound.   

They propose a lower bound under the weak coverage assumption for offline RL. The lower bound is also reduced to several lower bounds in specific examples. They also show how this lower bound is achieved.  

This paper studies the capability and intrinsic hardness of pessimistic value iteration algorithm in the finite-horizon tabular MDP case when data is i.i.d. collected from a behavior policy. By a fine-grained analysis, the PEVI (reduced to the i.i.d. tabular case) is modified to incorporate empirical variance into the pessimistic penalty term. These empirical quantities converge to their population counterparts, which is also shown by a lower bound as the intrinsic hardness of learning the MDP with data collected by the policy. Extensive examples & special cases are analyzed to provide a comprehensive analysis of pessimistic offline RL in this setting.