Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
Authors: Ming Yin
Yu-Xiang Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Theory
Reinforcement Learning Theory
Markov Decision Process Theory

Abstract: We study the \emph{offline reinforcement learning}  (offline RL) problem, where the goal is to learn a reward-maximizing policy in an unknown \emph{Markov Decision Process} (MDP) using the data coming from a policy $\mu$. In particular, we consider the sample complexity problems of offline RL for the finite horizon MDPs. Prior works derive the information-theoretical lower bounds based on different data-coverage assumptions and their upper bounds are expressed by the covering coefficients which lack the explicit characterization of system quantities. In this work, we analyze the \emph{Adaptive Pessimistic Value Iteration} (APVI) algorithm and derive the suboptimality upper bound that nearly matches
\[
O\left(\sum_{h=1}^H\sum_{s_h,a_h}d^{\pi^\star}_h(s_h,a_h)\sqrt{\frac{\mathrm{Var}_{P_{s_h,a_h}}{(V^\star_{h+1}+r_h)}}{d^\mu_h(s_h,a_h)}}\sqrt{\frac{1}{n}}\right).
\]
We also prove an information-theoretical lower bound to show this quantity is required under the weak assumption that $d^\mu_h(s_h,a_h)>0$ if $d^{\pi^\star}_h(s_h,a_h)>0$. Here $\pi^\star$ is a optimal policy, $\mu$ is the behavior policy and $d(s_h,a_h)$ is the marginal state-action probability. We call this adaptive bound the \emph{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 \emph{assumption-free} regime (where we make no assumption on $
\mu$) 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.

Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
Ming Yin 1.2 and Yu-Xiang Wang'
Department of Computer Science, UC Santa Barbara Department of Statistics and Applied Probability, UC Santa Barbara ming-yin&ucsb. edu yuxiangvêcs ucsb. edu
Abstract
We study the offline reinforcement learning (offline RL) problem, where the goal is learn maximizin policy an unknown Markov Decision Process (MDP) using the data coming from policy μ.. In particular, we consider the sample complexity problems of offline RI. 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, analyze the Adaptive Pessimistic Value Iteration (APVI) algorithm and derive the suboptimality upper bound that nearly matches
Var (Vi+1 + rh) (H an)
Σ E h= ah
tf. an
(I)
In complementary, we also prove a per-instance information-theoreiien bound under the weak assumption that di (s), an.) > 0 if dj, (sk,a,) > 0. Differ- ent from the previous minimax lower bounds, the per-instance lower bound (via local minimaxity) is much stronger criterion as it applies to individual instances separately. Here is optimal policy, μ is the behavior policy and di 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-depee -epeeddde results. Later, extend the result to the assumption-free regime (where we make no assumption on μ)) and obtain the assumption ffre intrinsic bound. Due its generic form, we believe the intrinsic bound could help illuminate what makes specific problem hard and reveal the fundamental challenges offline RL.
lower
Introduction
In offline reinforcement learning (offline RL Levine et al. [2020], Lange et al. [2012]). the goal to learn a reward-maximizing policy in unknown environment (Markov Decision Process MDP) using the historical data coming from a (fixed) behavior policy Unlike online RI, where the agent 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 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 al. [2019], Chen and Jiang [2019], Xie and Jiang [2020, 2021],
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Yin et al. [2021a,b), Ren et al. [2021], Rashidinejad et al. [2021], Xie et al. [2021b]) rely on making different covarcoe 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, 2.21]. Janner et al. [2021]) are often far better than what those non-adaptive / problem-independee
bounds would indicate. Although empirical evidence can help explain why we may observe better or worse performances on different MDPs, 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 non von-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 dota-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 might bring considerable saving in the time spent designing domain-speciff RL solutions and in training a human expert to judge and recognize the complexity of different problems.
1.1 Our contribution
In this work, we provide the analysis for the adaptive pessimistic value iteration (APVI) (Algorithm 1) with finite horizon time-inhomogeneous noon-stationary) MDPs and derive strong adaptive bound that is near-optimal under the weak assumption di (s), ax) 0 if d% (s), an) (Theorem 4.1). Specifically, our bound (quantity (I)) explicitly depends on the marginal importance ratios (between the optimal policy x² and the behavior policy μ4) 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 Ö(H² /dm)²) complexity under the uniform data-coverage 2.1, OHHSSC" (2) complexity under the single policy concentrability assumption 2.3 and ((/dmme 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 0(H3/ //nd)) 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 step towards assumption-free offline reinforcement learning, we build 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.)). ). To the best of our knowledge, all of these results are the first of its kinds.

---

1.2 Related work
Finite sample analysis for offline reinforeement 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 cermmation-theorttice 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. 200la, 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 dmm. >> 0), Yin et al. [2021a] first proves the optimal O(H3 /dm, complexity in the time-inhomogeneous MDP. Recently, Yin et al. [2021b] designs the offline variance reduction algorithm to achieve the optimal Ö(H²) /dme.)
rate for the time- heee-hooomeeuuus case. Under the setting where the total cumulative reward is bounded by 1, Ren et al. [2021] obtains the horizon-free result with Ó(1/dm). More recently, Rashidinejad et al. [2021] considers the single concentrability coefficient C* = max,,a d= (s, a) /))dd((s (s, a) and derives the upper bound Ō[(1 - ?) SC** /ca] 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.'
2 Preliminaries
Episodic non-stationary (time-varying) reinforcement learning. A finite-horizon Markov Deci- sion Process (MDP) is denoted by a tuple M (S, A, P.r. H. d:) [Sutton and Barto, 2018], where is the finite state space and AA is the finite action space with S := |S] < 00, A := |A| < 00. A non- stationary transition kernel Pa S x A S [o, 1] maps each state action az.) to a probability distribution (r a₂) and Ph. can be different across the time. Besides, r S x A + R is the ex- pected instantaneous reward function satisfying 0 S
1. d1 is the initial state distribution. H is the horizon. A policy = (Ti,..., TH) assigns each state 8s E S a probability distribution over actions according to the map 8%, - T. (-Is)) vh (H). An MDP together with a policy induce a random tra- jectory $1, Q1, Ti,...... ................................ SH, aH TH, $ with 81 d1, an ~ (-119)), Sh+11
(- aj Vh E [4]
and r4 is random realization given the observed sh, ah.
Q-values, Bellman (optimality) equations. The value function V E RS and Q-value function (%:)) E RSS for any policy is defined as: V (s) = R. EE rz/sh s]. (s, = E, 1> rr Prlsn, On s, s, Vs,a E S,A,h h E [H]. The performance is defined as vd == E,, [VT] = En,di [Σ"] 1 rr] where we denote VT, QT, as column vectors and Ph. E SSAXS the transition matrix, then the vector form Bellman (optimality) equations follow Vh. [M] O = ra + Pa V VI"" = -Ea_,, [Q]], Qi = ти + Pr. Pi Vi = max, ().:a))In ad- dition, we denote the per-step marginal state-action occupancy d', a) as: d) == PP(A = s|s1 ~ di, T] (als), 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 x such that the performance :. is maximized, given only the episodic data D = {(s), oh rh s1+1)) hellm) rolled out from some behavior policy p. The offline nature requires we cannot change μ and in particular we
We 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" E [0, H]. since there additional H factor by rescaling.
3

---

do not assume the functional knowledge of That is to say, given the batch data D and targeted accuracy >> the offline RL seeks to find a policy Taly such that a I E.
2.1 Assumptions in offfine RL
We revise several types of assumptions proposed by existing studies that can yield provably efficient results. Recall di (sh, as) ) is the marginal state-action probability and μ is the behavior policy.
Assumption 2.1 (Uniform data coverage [Yin et al., 2021al). The behavior policy obeys that dm == ming,5.,9, d% (8h, ah) O. 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 S.A. 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 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, Cp == sup,, [|d (.. (
< cc.
This is a classical offline RL condition that commonly assumed in the function approximation scheme (e.g. Fitted Q-Iteration). Qualitatively, this is uniform data-coverage assumption that is similar to Assumption 2. but quantitatively, the coefficient C₁, can be smaller than 1 1/dm due the d' term in the numerator.
Assumption 2.3 (Liu et al. [2019]). There exists one optimal policy x², s.s. Ash, an E S.A. df (hh, an) > 0 if dz (sh, an) > 0. We further denote the trackable set as Cn. == as)) 0}.
dg (sh, an)
Assumption 2.3 is (arguably) the weakest assumption needed for accurately learning the optimal value o* and we will use 2.3 for most parts of this paper. It only requires fu 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' == max a d= a) ( (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)/ /) a) much smaller than C
Furthermore, what could end up with when 2.3 is not met? We will provide our answers in the subsequent sections.
3 A warm-up case study: Vanilla Pessimistic Value Iteration
As step towards the optimal and strong adaptive offline RL bound, we analyze the vanilla pessimistic value iteration (VPVI), 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 [(Th, ah. rh. $541) AE[H! we denote nsa.en.
En [ of = 8h,4H, 4.] be the total counts that visit (Sh, an) pair at time ht then we use the offline plug-in estimator to construct the estimators for Pn. and rh as:
Pr (1s))s)aa)) an) Em [[(5++1, ah. (h) = (6',8n, Maxion
8h, an, Fh(ss, an) DT
r [aah (7) = (sh,
Raysan
(2)
ny,,a, and (s')sn, an) = 1/5, Fr (8h, an) "vanilla" as it directly mirrors Jin et al. [2020] with a pessimistic penalty of order O(H/ (nn
= 0 Noy.on O. particular, we use the word
With Pa, Fu in Algorithm 2 (which we defer to Appendix), VPVI guarantees the following:
This is due
& (sn, ax)" A (sh, as) reduces to VI/ne, when setting c(sn, an) 1 1(st, an)
and A 0.

---

Theorem 3.1. Under the Assumption 2.3, denote dm == min in (5 an) ::::%/o (s an) > 0}.
For any 0 < ô < L, there exists absolute constants co, C' > O, such that when co 1/dm (HS) with probability 1 the output policy गे of VPVI satisfies
(1 = loglog((H) lolloog(HHHA
H
0 5 0" - 0² S SC'
Σ h= (SC,
Σ
dh (Sh, an)
(3)
V n (sh
The full proof can be found in Appendix 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 al. [2021a], Ren al. [2021]). In addition, by straightforward calculation (3) can be bounded by Ö( /n) which improves VI-LCB [Rashidinejad al., 2021] by a factor of H. Besides, the analysis of VPVI also improves the direct reduction of PEVI [Jin et al., 2020] in the tabular case SAH when d SA.
by a factor SA since their
However, VPVI is not optimal as the dependence on horizon is H which does not match the optimal worst case guarantee H [Yin 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- Pessimistic Value Iteration or LCBVI-Bernster
I: Input: Offline dataset D {(5], of rh. sh+1))+++))) 7, Set 2, 14, failure probability 8.
2: Initialization: Set V V (+) <- 0. Set = log( (566). (if assumption-free, set M M as in Section 5.)
3: for time h = H, H 1, .,.... do
4: Set (x()-) + (x.) (Ph. - (use F1, + (PA D/-1) assumption--rree
5: Vsh ah. set (s),, an) = CiV Panion CntVi
+
Caft.e if Reg.an 2 1. O.W. set CH.
nay.es
6: (If areum use Ci /i / Var pl (Ph. Vn+1) . c/mennns + CyHli if Monin 2 1, o.w. use 0.) men.aa
7: Set 2.(())) < Qu(:.)) [.. Set Qa(:s)) ) t- min((R(s)))))....)))..))))))(()) -
1---- 1 1) // Pessmistii update 8: VSa. Select (n(-11))) + argmax,, (Qn (sh. ) mi (-b1)))). Set (ss) + (Q, -), (-1s)))
9: end for
10: Output: {.
4 Intrinsic Offline Reinforcement Learning bound
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/ (Ts,,,a)))) is crude as
estimates the confidence width of Qn, 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:
Var Varpan.n Pen.on (Fn + Vntt)
[x an) an))= =o[
H. Mayian
(if ni > >0); = =Ō(H) (if Danion = 0). (4)
Te
and update @n + Qn - -r. On one hand, /Var,, aa (Fh Vnt1)/n is a "less pessimistic"
penalty than VPVI due to / V + Vn+1) I 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 Õ(H) which in turn causes the agent unlikely to choose them. We summarized the this adaptive pessimistic value
'To be rigorous, translating the result from the infinite horizon setting to the finite horizon setting requires explanation. We add this discussion in Appendix D.
5

---

iteration (APVI) into the Algorithm 1, with PR. Fr defined in (2). APVI has the following guarantee. sketch of the analysis is presented in Section B and Appendix includes the full proof.
Theorem 4.1 (Intrinsic offline RL bound). Under the Assumption 2.3, denote dm
min (d an) dy (8h, an) > 0}. For any 0 < < 1, there exists absolute constants
co, C' > O, such that when n > 1/dm 6 log (HS)))))) with probability 1 - 5, the output
policy कt of APVI (Algorithm 1) satisfies (O hides log factor and higher order terms)
H
Varp.... (rh + V h+1)
H3 dm
0 e² - 8 SSC' Σ h=l (ECC
Σ
dh (sh, an)
+ Ō
(5)
n d (Sh ax)
Remark 4.2. APVI (Algorithm 1) can also be called LCBVI-Bernsee 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 fully expressed by the system quantities that admits no explicit dependence on H, S 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 a tuple (M, x : an MDP M (coupled with the optimal policy π²" with the data rolling from an offline logging policy μu. As will discuss later, this result indicates (nearly) all the optimal worst-case non-adaptive bounds (and clearly also the VPVI) under their respective regimes/ assummtions. 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 crucial as helps us to understand what type of problems are harder easier than others, and even more, in quantitative way. Last but not least, to illustrate this bound exhibits the intrinsic nature of offline RL, we prove a per-instance dependent formulation. The proof of Theorem 4.3 can be found in Appendix G.
thheoatiintthooretical lower bound that shares a similar
Theorem 4.3 (Instance-dependen)
information theoretical offline lower bound). Denote 0). Fix an in- Let DD consists of n. episodes and define & = Pilenni (M(en4ilonaan)) (er-l(eat1)-Br, (R-il) Let i to be /2-d2 Varps, (Viz1)
G = {(1,, M) 7n¹ s.l. (s, > -O if di (s,a)
stance P
M)
G.
suph.sn.nnse 11, (sn.a))))) (asn Narpenan (Vi11)>0 the output of any algorithm. Define the local non-asymptotic minimax risk
Rp)P) = sup inf max p'eg QE(P,P')
Vn. Be [ (0) -0a
(6)
where u² (Q) denotes the optimal value under the instance Q Then there exists universal con- )2, with
Vaar (Vir1)
stants co, P. C > O, such that i 2 Ho Esn,an dy. (sn, Son S: (sh
constant probability p > 0, Then we have (here < H/dm):
H (P) CC) Σ
di (sh an) v Var pn (ru +Vit))
Σ
S (s2,
h=1 (4% JCC
where P = (1,, M) and M = (S, H.d)).
The interpretation of Theorem 4.3 is: for any instance P. learning requires (7) (divided by 1/vr) for any algorithm. Note this notion is significantly stronger than the previous minimax offline lower bounds [Yin al., 2021a. a, Rashidinejad et al., 2021, Xie al., 2021b. lb. Jin et al., 2020] (where they only select particular family of hard problems), therefore, their lower bounds in general do not hold for individual instances.
The quantity (1) nearly-matcher the per-instance lower bound (7) (they deviate by a factor of < H/dm due the technical reason) and, in addition, we provide 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 Σl Σ (eesewnEcs d% (sh, an)
Varr on (rit Vitz)) intrinsic offline n-d" (sh.as)

---

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.144.4 are deferred to Appendix I.
Intrinsic Offline Learning Bound
Var (Vi+1 m di (Sp, Rh)
dh (Sn, ax)
JIL
Uniform Visitation
Adaptive Domain
Single Concentrability
H
dg
H2SC
Go di
A pe-day
Figure A visualization on how intrinsic learning bound subsumes cxisting best-known results: uniform visitation, single concentrability (partial coverage) and adaptive domain.
4.1 Optimality under Uniform data-coverage assumption
Under the uniform exploration Assumption 2.1 with parameter dm := ming.s.. d' (8h, an) > O, Yin et al. [2021a] analyzes the model-based plug-in approach and obtains the optimal sample complexity / and shows [(HH//dme 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.
Varp () (Fn + Viit)), (.)())
d (.) Varp (T% + Viitn) dm
Σ Soh O.
Elvar
of ONV.
h=1
(8)
d (.) Varr (rh + Vi+t) n dm
H H Var (E Ph) dm
H
dr O
$
n
dm
which translates to ((H3/ (HH3/dmme?) complexity. Our result maintains the optimal worst-case guarantee when y has the uniform data-coverage:
Proposition 4.4. Under Assumption 1 and apply Theorem 4.1, APVI achieves the sample complexity of minimax-rate ( (d (Theorem 4. and Theorem G.2 in Yin al. [2021a]).
Remark 4.5. We believe if the MDP is time-innariin invariant, then by modified construction of P, 7 in (2) result will imply the minimax-rate of Ó(H2/ ((112/dm"") dm as achieved in Yin al. [2021b]. We include this discussion Appendix
)
4.2 Bounded sum of total rewards and the Horizon-Free case
There is another thread of studies that follow the bounded sum of total rewards assumption: i.e. rh 2 0, Σ ta E [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-fig free worst case bound Õ / /1/n/dm ) 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 Th 2 0. EH Th < 1. Then in the time-varying case AVPI (Theorem 4.1) outputs policy ãे such that the suboptimality gap o² 3 is bounded by Ō H H/ndd))) with high probability under the Assumption 2.1.
Herr @ denotes element-wiss multiplication. Also note under 2. our dm dm-
7

---

The derivation is straightforward by using Var,- Eh Th) S 1 (8). This proposition is interesting since it indicates when the MDP is non-stationary, ((H1/mm=)) is required in the worst case even under Σh=1 Th I 1. The extra H factor resembles the challenge that we have H transitions (Pl....; PH) to learn, as opposed to the bandit-type 1/dm=* 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] non- stationarity [Cheung et al., 2020].
4.3 Optimality with Single Concentrability
In the finite horizon discounted setting, Rashidinejad et al. [2021] proposes the single policy concen- dE (s.a)
trability assumption which is defined as C* maN
< oo in the current episodic non-
(e.0)
stationary MDP setting, As discussed in Appendix D, their lower bound translates to S2( HASC
and their VI-LCB algorithm yields σ(V H²sCr) suboptimality gap in H-horizon case. Since single policy concentrability 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):
(s.a) < <c. Then ()
Proposition 4.7. Let x² be a deterministic policy such that C* := maX,, by Theorem 4.1, with high probability the output policy of APVI satisfies the suboptimality gap o( HSSC* in the fime-varying (non-stationary) MDPs. n
(a.a)
This can computed similar to (8) except we use (g.)) C .ur implication improves the VI-LCB
by the factor 2 (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 more interesting domain as tailors to each MDP separately. We discuss now.
4.4 Problem dependent domain
We define the pre-step environmental norm (the finite horizon counterpart of Maillard et al. [2014]) as: Q7 = maxs, Varp.,.on, (Th + V for all h E [M]] and relax the total sum of rewards to be bounded by any arbitrary value (i.e. ΣH Th S B), then Theorem 4.1 implies:
Proposition 4.8. Under Assumption 2.1, with high probability, subopmality of AVPI is bounded by
Q ndw
H.B. B
H
min
o 1=1
+
0
ndm
nd
Such 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 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 = 0 for all h. This enables a faster convergence rate of order nd... and significantly improves
Suppose in this case we can achieve Ō(1/dm=²) just like Ren et al. [2021], then by rescaling we obtain the Ö(H² H2 /dm under the usual 0 S F4 5 assumption which violates the 2t H /dn, lower bound. Zanette and Brunskill [2019] uses the maximal version by maximizing over h.

---

over the existing non-adaptive results that have order 1 The convergence rate 1 matches Wen and Vn 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 stochastic Ph. Ta ss and H t deterministic Piy, The 's, then completing the offline learning guarantees t mmxx Qi mm
suboptimality gap, which could be much smaller than H V Qj./ /1m/ 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 (-(-s,, an) := (-) depends on neither the state 8/ nor the action a₁- Define & := arg max V (s) and 8, == arg max V,((s,, Also, denote rngV to be the range of V In such cases, Bellman optimality equations have the form
V (3)) = max (rx (5), a) + 2/ Vit1). VT (s,) = max (rA (5n, a) + + +1t
which yields rngV VI (5x) Vū (s,,) max, Th (5) ming I'h (S/, 0 1, and this in turn gives Q2 < 1 (m 2. As a result, the suboptimality is bounded by Õ(v / /ndm,) in the worst case. This result reveals, although this is family of stochastic non-stationary MDPs, but it is only as hard as the family of stationary MDPs in the minimax sense (SHH2 20Hl2/dme* /dmm=))..
Tabular contextual bandits. Our result also implies Ō(Ezy,0 oi (II, 01 >
gap for the offinne tabular contextual bandit problem and improves to Õ(1 (11/dd)) when the reward deter- ministic. In either cases, the result is optimal and this due to: when r1 is deterministic, the agent only needs one sample at every location (see Bubeck and Cesa-Bianchi [2012] for survey).
Var(r)) (21.(1)))3))
5 Towards Assumption-Free Offline RL
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, be arbitrary. In this case, might not cover any optimal policy n (i.e. there might be high reward location (s, a) that ya can never visit, e.g. in the extreme case where 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 the values between the original MDP M and the estimated MDP Mt, In particular, Mt is negative towards agnostic state-actions Sh, ag by setting rk. = 0 and transitions to an absorbing state s $/41
consider this most general setting where the behavior policy y can
Pessimistic augmented MDP. Mt is defined with one extra state sf, for all h E (2...., + 1} with the augmented state space St = S {s//). The transition and the reward are defined as follows:
(. sh. an), Ma mn > O, p. 8h; an) = 8 ".t 8n = $), or 1as =0 O. r¹ r'(sn, an) = r(sh: an), no, > 0,
{
0, 8h s) nen,on
here 6, is the Dirac measure and we denote v and o to be the values under Mt. M/ is the empirical counterpart of Mt with P, f (the same (2)) replacing P, By Algorithm 1. we have Theorem 5.1 (Assumption- offline reinforcement learning). Let us make no assumption for μ and still denote dm ;= minneea (d% an) d% (Bh, an) > 03. For any 0 << 5 < 1, there exists absolute constants co. C' >> O, such that when co 1/dm . (e log (igHSAA/8) with probability 1 - 8, the output policy के of APVI satisfies (recall Cn == {(sh, an) d (sh, on) > 03)
#+1
H
Var rla (r) + V
H
0'
Σ
Σ
df d3' (sn,an))
+ō
(9)
n (sn, an)
ndm
2=22
(EC.
where d!=²" (sh, an) S dl an),
V/l (sn) I (sn) for all sh, on E S x A, and for all {H].
dit (s)) Σ/=1 E(era)esxAic, d," at). The proof is in Appendix E.
h-1

---

Take-aways of Theorem 5.1. In Mt, there is no agnostic location any more since the original unknown spaces now all have known deterministic transitions sf in M At a price, the algorithm has to suffer the constant suboptimality M d/. (s),) due to no data in the region. The quantity Ex=2 df." (s/) helps characterize the hardness when nothing is assumed about μc: 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 x A²C,, = 0; under Assumption 2.3, it also 0 and 5.1 reduces to Theorem 4.1 (see Appendix F).
5.1 Assumption Free vs Without Great Coverage (Partial Coverage)
Recently there is 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 (s, a)//a(s//000 a) < oo where ITe is either an expert policy or a policy of great quality and they further compete against with this policy we. 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 the case where μ can be arbitrary: Liu et al. [2020] considers the behavior policy with insufficient coverage probability eg (see their Definition 1), and they end up with the constant suboptimality gap 1-7
Viaszc (their Theorem 1), when the insufficient
coverage probability <ç >> 0, this gap has order (1 - -)--, which is larger in order than the biggest possible suboptimality gap (1 - therefore unable to characterize the essential statistical gap over the region that 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-frue free result via regularization and their bound can ineur ( constant gap when there is at least one (5h, on)) cannot be obtained by for all h E [H] (i.e. replacing nd (8h, ax) by 1 in (3)). The concurrent work Xie et al. [2021a] provides a better characterization (and they call off-support error) with roughly T- E ( (da \o) (s, a) [A a) (Tx A A ) (s, a)), however, in the worst case (s, (T"Afm) (s, a) might be large (which depends on the quality (assumption) of the function approximation class).
In contrast, our Σ d,"" (s)) quantity (with at."" (sh) = E'= E (s..,, dt (st, az) S 1) describes the "must-suffer" gap in a more precise way by absorbing all the agnostic probabilities into st and it is always bounded between 0 and H. It reduces to 0 when x² is covered. The gap is always of order H (as opposed to O(H2)).
6 Discussion and Conclusion
This work studies the offline reinforcement learning problem and contributes the intrinsic offline learning bound which is 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 /2dddmm however, H 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 fully acquire the dynamic P(-ss, 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 single algorithm that can achieve optimality for all instances could be challenging (or even infeasible). We leave those as the future works.
10

---

Acknowledgment
The research is partially supported by NSF Awards #2007117 and #2003257. MY would like thank Chenjun Xiao for bringing up related literature [Xiao et al., 2021] and Masatoshi Uchara, Yu Bai for helpful suggestions.
References
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67-83, 2020.
Andras Antos, Remi Munos, and Csaba Szepesvari. Fitted q-iteration in continuous action-space mdps. In Advances in Neural Information Processing Systems, pages 9-16, 2008a.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning. 71 (1):89-129, 2008b.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning-Von Voluum 70, pages 263-272. JMLR. org, 2017.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. In Advances in Neural Information Processing Systems, volume 32, 2019.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213-2)) 2002.
Sébastien Bubeck and Nicolo Cesa-Bianchi Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 2012.
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed-dataset policy optimization. International Conference on Learning Representations, 2021.
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.
Tony Cai and Mark Low. An adaptation theory for nonparametric confidence intervals. The Annals of statistics, 3205):180511840, 2004.
Jonathan D Chang, Masatoshi Uehara, Dhruy Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift in imitation learning via offline data without great coverage. Advances in Neural Information Processing Systemx, 2021.
Jinglin Chen and Nan Jiang. inoommttion-thoretti considerations batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051, 2019.
Herman Chernoff al. measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):493-501 1952.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism. In International Conference on Machine Learning, pages 1843-1854, PMLR, 2020.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax cotimma--ptimall off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages
2020.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.072199 2020.
Justin Fu, Mohammad Norouzi, Ofir Nachum, George Tucker, Ziyu Wang, Alexander Novikov, Mengjiao Yang, Michael R Zhang, Yutian Chen, Aviral Kumar, et al. Benchmarks for deep off-policy evaluation. International Conference Learning Representations, 2021.
11

---

Caglar Gulcehre, Ziyu Wang, Alexander Novikov, Tom Le Paine, Sergio Gómez Colmenarejo, Konrad Zolna, Rishabh Agarwal, Josh Merel, Daniel Mankowitz, Cosmin Paduraru, et al. RI unplugged: Benchmarks for offline reinforcement learning. Advances in neural information processing systems, 2020.
Michael Janner, Qiyang Li, and Sergey Levine. Reinforcement learning as one big sequence modeling problem. Advances in neural information processing systems, 2021.
Nan Jiang and Alckh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory. pages 3395-3398, 2018.
Nan Jiang and Lihong Li. Doubly robust off- aff-policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Learning-Volume Volume 48. pages 652-661. JMLR. org. 2016.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning- Starning-Volume 70, pages 1704-1713, 2017.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? Interna- tional Conference on Machine Learning, 2020.
Tobias Jung and Peter Stone. Gaussian processes for sample efficient reinforcement learning with rmax-like exploration. In Joint European Conference on Machine Learning and Knowledge Discovery Databases, pages 601-616 616.6 Springer, 2010.
Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J Wainwright, and Michael I Jordan. Is temporal difference learning optimal? an instance-dependent analysis. SIAM Journal on Mathematics of Data Science, 2021a.
Koulik Khamaru, Eric Xia, Martin J Wainwright, and Michael Jordan, Instance-optimaliig in optimal value estimation: Adaptivity via variance-reduced q-learning. arXiv preprint arXiv:2106. 14352, 2021b.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. Advances in neural information processing systems, 2020.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
Hoang Le, Cameron Voloshn,, and Yisong Yue. Batch policy learning under constraints. In Interna- lional Conference on Machine Learning, pages 3703-3712, 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. In Uncertainty in Artificial Intelligence, 2019.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforee- ment learning without great exploration. Advances in neural information processing systems, 2020.
Edalric-Ambryn Maillard, Timothy A Mann, and Shie Mannor. How hard is my mdp?" the distribution-norm the rescue". Advances Neural Information Processing Systems, 27:1835- 1843, 2014.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. Conference on Learning Theory, 2009.
12

---

Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: tale pessimism. arXiv preprint arXiv:2103. 12021,, 2021.
Tongzheng Ren, Jialian Li, Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. Advances in neural information processing systems, 2021.
Karthik Sridharan. A gentle introduction to concentration inequalities. Dept. Comput. Sci., Cornell Univ. Tech. Rep, 2002.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pages 880-887, 2005.
Joel Tropp et al. Freedman's 's inequality for matrix martingales. Electronic Communications in Probability, 16:262-270, 2011.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage. arXiv preprint arXiv:2 2021.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? International Conference on Machine Learning. 2021.
Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deterministic systems. Advances in Neural Information Processing Systems, 26, 2013.
Chenjun Xiao, Yifan Wu, Jincheng Mei, Bo Dai, Tor Lattimore, Lihong Li, Csaba Szepesvari, and Dale Schuurmans. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning, pages 11362-11371 11371. PMLR, 2021.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. In Uncertainty in Artificial Intelligence, pages 550-559, 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. Interna- tional Conference on Machine Learning, 2021.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consisterr pessimism for offline reinforcement learning. Advances in neural information processing systems, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 2021b.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-po evaluation for tabular rein- forcement learning. In International Conference Artificial Intelligence and Statistics, pages PMLR, 2020.
Ming Yin and Yu-Xiang Wang- Optimal uniform ope and model-based offline reinforcement learning in time-homogeneous, reward-free and task-agnostic settings. Advances in neural information processing systems, 2021.
Ming Yin, Yu Bai, and Yu-Xie Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1567-1575. PMLR, 2021a.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances in neural information processing systems, 2021
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch can be exponentially harder than online rl. International Conference on Machine Learning, 2021.
13

---

Andrea Zanette and Emma Brunskill. Problem dependent reinforcement learning bounds which can identify bandit structure in mdps. In International Conference on Machine Learning, pages 5747-5755. PMLR, 2018
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 1304-73122 PMLR, 2019.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 2021.
Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. Conference of Learning Theory, 2021.
14


Reviews:
[{"review_id": "jWz8nSLw4JS", "reviewer": "Reviewer_EcDg", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "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:\nThis work falls under the umbrella of the pessimistic value iterations framework [Jin et al., 2020], and provides a fine-grained and comprehensive analysis of a special case: tabular MDP with i.i.d. data from a behavior policy. The approach is not novel, but new insights and deeper understanding of offline RL with pessimism are established, which adds to the knowledge of the community. \n\nQuality & Clarity:\nThe paper is technically sound and clearly written.\n\nSignificance:\nThe work adds to the knowledge of the community on offline RL by a fine-grained analysis. It might open possibilities of finer understanding of offline RL in more general settings, e.g., beyond tabular, beyond i.i.d. \n\nMore comments:\nStrength:\n1. The fine-grained analysis of penalty function provides more insights and understanding of the offline RL with pessimism. \n2. The minimax optimal lower bound shows the intrinsic hardness of the problem.\nWeakness / concerns:\n1. The papers studies the special case of tabular MDP and i.i.d. trajectories, which might be a bit specific compared to the vanilla version [Jin et al., 2020]. \n2. The upper bound is not data-dependent, hence requires large sample size, while the work [Jin et al., 2020] poses no assumptions on the data except a minimal 'compliance' assumption. Would it be possible to give a data-dependent finite-sample version of the upper bound? Why do you prefer the current one?\n\n\n\n\n\n\n\n\n\n\n\nReference:\n[Jin et al., 2020] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? arXiv preprint arXiv:2012.15085, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. Maybe more discussions on limitations of the work can be an improvement. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "4xJabM2Heph", "reviewer": "Reviewer_8b9i", "summary": "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. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main idea of the paper is to use Bernstein-type confidence interval in the algorithm and analysis, which gives the improved bound over the Hoeffding-type analysis (Jin et al. 2020). The authors provide thorough theoretical analysis including matching regret upper and lower bounds which is very nice. This paper is also well written and the problem setup is clearly defined. \n\nHowever, I still have the following concerns and questions. Please address these in the rebuttal and correct me if I misunderstand some critical part of the work. \n\nThe advantage of using Bernstein-based analysis over the Hoeffding-based analysis is well established in the theoretical RL literatures. This makes the contribution of the paper somehow incremental and less interesting, although it seems that this is the first attempt to use such technique in offline RL. \n\nI think to study the sample complexity in offline RL, we first need to understand how to define “the optimal” algorithm in this problem. The minimax optimality is too weak as a criterion in the offline setting as it only considers the worst case, which gives a dependency on the minimum data coverage. So it seems that any algorithm that makes prediction based on the confidence interval is minimax optimal. Also, it is recently known that in offline RL, no algorithm can be instance-dependent optimal. And in fact, any “reasonable” algorithm, including pessimism, plug-in or even optimism, can find some niche where it dominates all the other algorithms (see [1] for details). So no matter how the confidence interval is constructed in practice (either Hoeffding-type or Berstain-type), it’s still not possible to get an \"optimal\" algorithm in the instance level. This seems to be a closely related issue that should be discussed in the paper. \n\nSince we cannot use minimax optimality or instance optimality to study the problem, one can instead define a “weighted minimax” with different weighting scheme, like the one used in the paper, the visitation under the optimal policy used in Jin et al. 2020, and the optimal value prediction error used in [1]. The choice of the weighting is kind of arbitrary as we have already known that any algorithm is good in some problem instance and we just need to find a weighting that is attached to the properties of good problems. I think this is the reason why both APVI and PVI can match the \"corresponding\" lower bound. \n\nRegarding the extension to the no-assumption case, I think the result presented in Theorem 5.1 is not very interesting. The result just says that if $\\pi^*$ is not covered the algorithm will suffer linear regret. I think the assumption that $\\pi^*$ is covered by the behaviour policy is actually acceptable. Otherwise if there is no information can be collected in the data the best an algorithm can do is to make a random guess. Please correct me if I made a mistake on this. \n\n[1] Xiao, C., Wu, Y., Mei, J., Dai, B., Lattimore, T., Li, L., Szepesvari, C. and Schuurmans, D., 2021, July. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning (pp. 11362-11371). PMLR.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal issue has been found. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issue has been found. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "4o9QL9WSJ2", "reviewer": "Reviewer_HoUV", "summary": "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. \n", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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: Main results (lower bound and upper bound) are novel and very meaningful. This paper also unifies several scattered lower bound for offline RL. That’s also a nice contribution. \n\n* Quality:  In the interest of time, I did not check the proof. But, according to a sketch of the analysis, it sounds correct. \n\n* Clarity: Yes, it is clear\n\n* Significance: Many theory offline RL people would be excited with this work. I enjoyed it a lot. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some minor comments: \n\n* Line 304:  Var(r_1) is correct? Is it conditional variance? \n*  Line 272:  the use of C^{*} makes the bound sightly problem independent: I guess in the time-invariant setting, the dependence on C^{*}  sounds very natural since we can get the upper-bound characterized by  C^{*}.  Does it mean using C^{*}  in the time-variant setting is problematic? \n* Probably, worthwhile to note Liu et.al (2020) is assumption-free in a tabular case somewhere. They get an assumption-free result by setting the threshold for the offline data distribution. Then, they obtained an error based on the augmented MDP by this thresholding. Basically, I feel people can always get this assumption-free result by some type of thresholding on top of the original algorithm. Actually, Jin (2020) result is assumption-free (at least they claimed in this way) since there is a threshold parameter lambda.  So, might be not needed to emphasize too much. \n* Is they any relation for the Cramer-Rao lower bound for OPE?  \n", "review_text": "", "extra_scores": {"ethical_concerns": "No ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents adaptive sample complexity bounds for offline RL. While the technique is not entirely novel, the results are new and interesting in the literature and thus the AC recommends acceptance. The authors are encouraged to incorporate comments from the reviewers.
Decision: Accept (Poster)