What are the Statistical Limits of Offline RL with Linear Function Approximation?
Authors: Ruosong Wang
Dean Foster
Sham M. Kakade
Venue: ICLR 2021 Spotlight (2021)
Keywords: batch reinforcement learning
function approximation
lower bound
representation

Abstract: Offline reinforcement learning seeks to utilize offline (observational) data to guide the learning of (causal) sequential decision making strategies. The hope is that offline reinforcement learning coupled with function approximation methods (to deal with the curse of dimensionality) can provide a means to help alleviate the excessive sample complexity burden in modern sequential decision making problems. However, the extent to which this broader approach can be effective is not well understood, where the literature largely consists of sufficient conditions.

This work focuses on the basic question of what are necessary representational and distributional conditions that permit provable sample-efficient offline reinforcement learning. Perhaps surprisingly, our main result shows that even if: i) we have realizability in that the true value function of \emph{every} policy is linear in a given set of features and 2) our off-policy data has good  coverage over all features (under a strong spectral condition), any algorithm still (information-theoretically) requires a number of offline samples that is exponential in the problem horizon to non-trivially estimate the value of \emph{any} given policy. Our results highlight that sample-efficient offline policy evaluation is not possible unless significantly stronger conditions hold; such conditions include either having low distribution shift (where the offline data distribution is close to the distribution of the policy to be evaluated) or significantly stronger representational conditions (beyond realizability).

Published as a conference paper at ICLR 2021
WHAT ARE THE STATISTICAL LIMITS OF OFFLINE RL WITH LINEAR FUNCTION APPROXIMATION?
Ruosong Wang
Dean P. Foster
Carnegie Mellon University
University of Pennsylvania and Amazon dean foster net
ruosongwe andrew. cmu edu
Sham M. Kakade
University of Washington, Seattle and Microsoft Research shamêcs, washington edu
ABSTRACT
Offline reinforcement learning seeks to utilize offline (observational) data to guide the learning of (causal) sequential decision making strategies. The hope is that offline reinforcement learning coupled with function approximation methods (to deal with the curse of dimensionality) can provide a means to help alleviate the excessive sample complexity burden in modern sequential decision making prob- lems. However, the extent to which this broader approach well understood, where the literature largely consists of sufficient conditions.
be effective is not
This work focuses on the basic question of what are necessary representational and distributional conditions that permit provable sample-efficient offline reinforce- ment learning. Perhaps surprisingly, our main result shows that even if: i) we have realizability that the true value function of every policy is linear in given set of features and 2) our off-policy data has good coverage over all features (under a strong spectral condition), any algorithm still innfrrmation-hhoovetialllll requires theoretically)
number of offline samples that is exponential in the problem horizon non- trivially estimate the value of any given policy. Our results highlight that sample- efficient offline policy evaluation is not possible unless significantly stronger con- ditions hold; such conditions include either having low distribution shift (where the offline data distribution is close the distribution of the policy to be evaluated) or significantly stronger representational conditions (beyond realizability).
INTRODUCTION
Offline methods (also known off- off-policy methods batch methods) promising methodol- ogy to alleviate the sample complexity burden in challenging reinforcement learning (RL) settings, particularly those where sample efficiency is paramount (Mandel et al. 2014] Gottesman et al.) 2018 Wang et al.) 2018 Yu et al. 2019). Off-policy methods are often applied together with func- tion approximation schemes; such methods take sample transition data and reward values inputs, and approximate the value of a target policy or the value function of the optimal policy. Indeed, many practical deep RL algorithms find their prototypes in the literature of offline RL. For exam- ple, when rumning on off- off-policy data (sometimes termed as "experience replay"), deep Q-networks (DQN) (Mnih et al., 2015) can be viewed as an analog of Fitted Q Q-Iteration (Gordon 1999) with neural networks being the function approximators. More recently, there are an increasing number of both model-free (Laroche et al. 2019 Fujimoto et al. 2019 Jaques et al.) 2020 Kumar et al.,
2019 Agarwal et al. (0200) and model-baset (Ross & Bagnell 2012, Kidambi et al. (2020) offline RL methods, with steady improvements in performance (Fujimoto et al. 2019 Kumar et al. 2019
Wu al. 2020 Kidambi et 2020).
However, despite the importance of these methods, the extent to which data reuse is possible, espe- cially when off-policy methods are combined with function approximation, is not well understood. For example, deep Q-network requires millions of samples to solve certain Atari games (Miih et al.]
2015). Also important is that in some safety-critical settings, we seek guarantees when offiine-

---

Published as a conference paper at ICLR 2021
Thomas al., 2019). A basic question here is that if there are fundamental statistical limits on such methods, where sample-efficies offline RL is simply not possible without further restrictions on the problem.
trained policies can be effective (Thomas 2014
In the context of supervised learning, it is well-known that empirical risk minimization is sample- efficient if the hypothesis class has bounded complexity. For example, suppose the agent is given a d-dimensional feature extractor, and the ground truth labeling function is a (realizable) linear function with respect to the feature mapping. Here, it is well-known that a polynomial number of samples in d suffice for a given target accuracy. Furthermore, in this realizable case, provided the training data has good feature coverage, then we will have good accuracy against any test distribution!!
In the more challenging offline RL setting, it is unclear if sample-efficient methods are possible, even under analogous assumptions. This is our motivation to consider the following question:
What are the statistical limits for offline RL with linear function approximation?
Here, one may hope that value estimation for a given policy is possible in the offline RL setting under the analogous set of assumptions that enable sample-efficient supervised learning, i.e., 1) (realizabilitt) the features can perfectly represent the value functions and 2) (good coverage) the feature covariance matrix of our off-policy data has lower bounded eigenvalues.
The extant body of provable methods on offline RL. either make representational assumptions that are far stronger than realizabilityy assume distribution shift conditions that are far stronger than having coverage with regards to the spectrum of the feature covariance matrix of the data distribution. For example, Szepesvári & Munos (2055) analyze oflline RL methods by assuming a representational condition where the features satisty (approximate) closedness under Bellman updates, which is far Xie
stronger representation condition than realizability. Recently, Xie Jiang (2020a) propose offline RL algorithm that only requires realizability as the representation condition. However, the algorithm in (Xie Jiang 2020a) requires a more stringent data distribution condition. Whether it is possible to design a sample-efficient offline RI. method under the realizability assumption and a reasonable data coverage assumption - an open problem in (Chen & Jiang 2019) is the focus this work.
Our Contributions. Perhaps surprisingly, our main result shows that, under only the above two assumptions, it is information-tee iioomation-theortiiaall theoretically not possible to design a sample-efficient algorithm to non-trivially estimate the value of a given policy. The following theorem an informal version of the result in [ Theorem 1.1 (Informal). In the offline RL setting, suppose the data distributions have (polynomi- ally) lower bounded eigenvalues, and the Q-functions of every policy are linear with respect to given feature mapping. Any algorithm requires an exponential number of samples in the horizon H to output a non-trivially accurate estimate of the value of any given policy n, with constant probability.
This hardness result states that even if the Q-functions of all polices are linear with respect to the given feature mapping, we still require an exponential number of samples to evaluate any given policy. Note that this representation condition is significantly stronger than assuming realizability with regards to only a single target policy; it assumes realizability for all policies. Regardless, even under this stronger representation condition, it is hard to evaluate any policy, specified in our hardness result.
This result also formalizes key issue in offline reinforcement learning with function approxima- tion: geometric eтror amplification. To better illustrate the issue, in Section we analyze the clas- sical Least-Squares Policy Evaluation (LSPE) algorithm under the realizability assumption, which demonstrates how the error propagates as the algorithm proceeds. Here, our analysis shows that, if only rely the realizability assumption, then far more stringent condition is required for sample-efficient offline policy evaluation: the offlpy data distribution must be quite close to the distribution induced by the policy to be evaluated.
SSpecifically, if the features have uniformly bounded norm and if the minimum eigenvalue of the feature covariance matrix of our data is bounded away from 0, say by 1 1/poly(d), then we have good accuracy on any distribution. See Assumption and the comments thereafter.
2

---

Published as a conference paper at ICLR 2021
Our results highlight that sample-efficien offline RL is simply not possible unless either the distri- bution shift condition is sufficiently mild or we have stronger representation conditions that go well beyond realizability. See Section D for more details.
Furthermore, our hardness result implies an exponential separation on the sample complexity be- tween offline RL. and supervised learning, since supervised learning (which is equivalent to offline RL with H = 1) is possible with polynomial number of samples under the same set of assumptions.
A few additional points worth emphasizing with regards our lower bound construction:
Our results imply that Least-Squares Policy Evaluation (LSPE, i.., using Bellman backups with linear regression) will fail. Interestingly, while LSPE will provide an unbiased estimator, our results imply that it will have exponential variance in the problem horizon.
Our construction simple and does not rely on having a large state or action space: the size of the state space is only (d H) where d is the feature dimension and / is the planning horizon, and the size of the action space is only is 2. This stands in contrast to other RL lower bounds, which typically require state spaces that are exponential in the problem horizon (e.g. see (Du)
et al. 2020)).
We provide two hard instances, one with a sparse reward (and stochastic transitions) and another with deterministic dynamies (and stochastic rewards). These two hard instances jointly imply that both the estimation error reward values and the estimation error on the transition probabilities could be geometrically amplified in offline RL.
Of possibly broader interest is that hard instances are, to knowledge, the first concrete examples showing that geometric error amplification is real in RL problems (even with realizabil- ity). While this is known concern in the analysis of RL algorithms, there have been no concrete examples exhibiting such behavior under only realizability assumption.
2 RELATED WORK
We now survey prior work on offline RL, largely focusing on theoretical results. We also discuss results on the eтror amplification issue in RL. Concurrent to this work, Xie & Jiang (2020a) propose a offline RL algorithm under the realizability assumption, which requires stronger distribution shift conditions. We will discuss this work shortly.
Existing Algorithms and Analysis. Offline RL with value function approximation is closely re-
lated to Approximate Dynamic Programming [Bertsekas & Tsitsiklis 1995). Existing work (Munos)
2003 Szeeesvári & Munos 20055 Antos et al. [208]] Munos & Szepesvári, 2008 [Tosatto et al.
2017
Xie & Jiang 2020b] Duan & Wang. 2020) that analyze the sample complexity of approximate
dynamic programming- based approaches usually make the following two categories of assumptions::
(i representation conditions that assume the function class approximates the value functions well and (ii) distribution shift conditions that assume the given data distribution has sufficient coverage the state-action space. As mentioned in the introduction, the desired representation condition would be realizability, which only assumes the value function of the policy to be evaluated lies in the function class (for the case of offline policy evaluation) or the optimal value function lies in the function class (for the case of finding near-optimal policies), and existing works usually make stronger assumptions. For example, [Szepesvári & Munos (2005); Duan & Wang (2020) assume (ap- proximate) closedness under Bellman updates, which is much stronger than realizability. Whether is possible to design a sample-effie efficient offline RL method under the realizability assumption and reasonable data coverage assumption, is left as an open problem in (Chen & Jiang 2019).
To measure the coverage over the state-action space of the given data distribution, existing works assume the concentrability coefficient (introduced by Munos] (2003) to be bounded. The concen- trability coefficient, informally speaking, is the largest possible ratio between the probability for a state-action pair (s, a) to be visited by policy, and the probability that (s, a) appears the data distribution. Since we work with linear function approximation in this work, we measure the distri- bution shift in terms of the spectrum of the feature covariance matrices (see Assumption 2 which a well well-knowwn sufficient condition in the context of supervised learning and is much more natural for the case of linear function approximation.
3

---

Published as a conference paper at ICLR 2021
Concurrent to this work, Xie & Jiang (2020a) propose algorithm that works under the realizabil- ity assumption instead of other stronger representation conditions used in prior work. However, the algorithm in (Xie & Jiang 2020a) requires much stronger data distribution condition which as- sumes a stringent version of concentrability coefficient introduced by (Munos) 2003) to be bounded. In contrast, in this work we measure the distribution shift in terms of the spectrum of the feature covariance matrix of the data distribution, which is more natural than the concentrability coefficient for the case of linear function approximation.
Recently, there has been great interest in approaching offline policy evaluation (Precup) 2000) via importance sampling. For recent work on this topic, see (Dudik al.] 2011 Mandel et al. 2014
Thomas et al., [0155] Li et al.] [2015] Diang & Li [2066] Thomas & Brunskill [016]] Guo et al.
2017 Wang et al., 2017: Liu et al. 2018] Farajtabar et al. 2018: Xie et al. 2019 Kallus & Ue-
hara 2019 Liu et al.] [019]] Uehara & Jiang] 2019; Kallus & Uehara [020]] Jiang & Huang 2020
Feng et al. 2020). Offline policy evaluation with importance sampling incurs exponential variance
in the planning horizon when the behavior policy is significantly different from the policy to be evaluated. Bypassing such exponential dependency requires non-trivial function approximation as- sumptions (Jiang & Huang 2020, Feng et al., [020 Liu et al., 2018). Finally, Kidambi et al. (2020) provide a model-based offline RL algorithm, with a theoretical analysis based on hitting times.
Hardness Results. Algorithm-specifie hardness results have been known for long time in the
literature of Approximate Dynamic Programming. See Chapter 4 in (Van Roy, 1994) and also (Gor-) don 1995 Tsitsiklis& & Van Roy 1996). These works demonstrate that certain approximate dynamic programming-bee baasd methods will diverge on hard cases. However, such hardness results only hold for restricted class of algorithms, and to demonstrate the fundamental difficulty of offline RL, it is more desirable to obtain information-theone
lower bounds as initiated by Chen & Jiang (011)).
exponential lower bounds (Krishnamurtyy et al. 2016 Sun et al.) 2017 Chen & Jiang 2019) usually construct unstructured MDPs with an exponentially large state
Existing kinfrrmtionnthhorett
space. Du et al. (2020) prove exponential lower bound under the assumption that the optimal Q- function is approximately linear. The condition that the optimal Q-function is only approximately linear is crucial for the hardness result in Du et al. (2020). The techniques in (Du et al.. 2020
later generalized to other settings (Kumar et al. 20200 Wang et al.) 2020 Mou et al. 20200).
Error Amplification In RL. Error amplification induced by distribution shift and long planning horizon is a known issue in the theoretical analysis of RL algorithms. See (Gordon 1995; 1996. Munos & Moore 1999; Ormoneit & Sen 2002 Kakade, 2003; Zanette et al. 2019) for papers on this topic and additional assumptions that mitigate this issue. Error amplification in offline RL is also observed in empirical works (see e.g. (Fujimoto al. 2019)). In this work, provide the first information-theerrtie lower bound showing that geometric error amplification is real in offline RL.
THE OFFLINE POLICY EVALUATION PROBLEM
Throughout this paper, for a given integer H, we use [H] to denote the set (1, H}.
Episodic Reinforcement Learning. Let M = (S, be Markov Decision Process (MDP) where S is the state space, A is the action space, P S x + (S) is the transition operator which takes a state-action pair and returns a distribution over states, R ::S. S x A + A (R) the reward distribution, E 24 is the planning horizon. For simplicity, we assume a fixed initial state 81 E S. A (stochastic) policy π. S + A (A) chooses an action randomly based on the current state s. The policy π induces a (random) trajectory $1, 01 T1, $2 02, T2,..., $H dH TH, where 01 Ti (s1). Pi R($1, a1), 82 P(s1, a1), d2 T2(22), etc. To streamline our analysis, for each h E [H], we use Sn C S to denote the set of states at level h. and we assume Sn do not intersect with each other. We assume, almost surely, that Th E [-11,1] for all h [H].
Value Functions. Given a policy n, h E [H] and (s,a) Sn x A, define (s. a) = IT Ei' The sh = s, s,a, a, π. and (s) E define V* V(((ss) to be the value of from the fixed initial state $1.
H Σ#' TH |ss, = = For a policy म. we
4

---

Published as a conference paper at ICLR 2021
Linear Function Approximation. When applying linear function approximation schemes, it is commonly assumed that the agent is given a feature extractor Φ S x A A Rd which can either be hand-crafted or a pre- pre-trained neural network that transforms state-action pair to d-dimensional emhedding, and the Q-functions can be predicted by linear functions of the features. In this paper, are interested in the following realizability assumption.
Assumption 1 (Realizable Linear Function Approximation) For every policy :S + ((A), there exists 0T. ....... 8 IR4 such that for all (s, a) S A and E [H], Q7 a) = (0%) d(s.a). a).
Note that our assumption is much stronger than assuming realizability with regards to single policy T (say the policy that we wish to evaluate): our assumption imposes realizability for all policies.
Offline Reinforcement Learning. This paper is concerned with the offline RL setting. In this setting, the agent does not have direct access to the MDP and instead is given access to data dis- tributions {un)i= where for each h E [H], μ4h E (S,, x A). The inputs of the agent are H datasets [Dr) and for each h E [H], Dn consists i.d. samples of the form (s, a, r, s') e Sp x A x R x Sh+1 tuples, where (s,a) ph,, I' r(s, a), s' P(s.a).
In this paper, we focus on the offline policy evaluation problem with linear function approximation: given a policy
S + A (A) and feature extractor S x A + R., the goal is to output an accurate estimate of the value of π (i.e., V*) approximately, using the collected datasets {Da h== with as few samples possible.
Notation. For vector E RR,, we use || to denote its & norm. For a positive semidefinite matrix A, we use ||A|| to denote its operator norm, and mmin (m))(A) to denote its smallest eigenvalue. For two positive semidefinite matrices A and B, we write A >= B to denote the Löwner partial ordering of matrices, i.e, A 2 B if and only if A - B is positive semidefinite. For a policy л : - A (AA,, use ,4, to denote the marginal distribution of 8h. under æ,, i.e., 18, (s) Pr(sh- 8 m]
For a vector x E Rd and a positive semidefinite matrix E Raxd we use || |I to denote Vx Ar.
4 THE LOWER BOUND: REALIZABILITY AND COVERAGE ARE INSUFFICIENT
We now present our main hardness result for offline policy evaluation with linear function approxi- mation. It should be evident that without feature coverage in our dataset, realizability alone is clearly not sufficient for sample-efficient estimation. Here, we will make the strongest possible assumption, with regards to the conditioning of the feature covariance matrix.
Assumption 2 (Feature Coverage). For all (s,a) E S A. assume our feature map is bounded such that [ a)ll S 1. Furthermore, suppose for each h E [H], the data distributions un satisfy the following minimum eigenvalue condition: Jmin (B(s.a)>ux
a) a)((s,))))))) a) 1/d
Clearly, for the case where H = 1, the realizability assumption (Assumption D. and feature cov- erage assumption (Assumption 2) imply that the ordinary least squares estimator will accurately estimate 01 Our main result now shows that these assumptions are not sufficient for offline policy evaluation for long horizon problems.
Theorem 4.1. Suppose Assumption hoolds. Fix algorithm that takes as input both policy and a feature mapping. There exists a (deterministic) MDP satisfying Assumption []] such that for any policy : S - ((A), the algorithu requires (d/ samples to output the value of up to constant additive approximation error with probability at least 0.9.
Although we focus on offline policy evaluation in this work, our hardness result also holds for finding near-optimal policies under Assumption T in the offline RL setting. Below we give simple reduction. At the initial state, if the agent chooses action 01 then the agent receives a fixed reward value (say 0.5) and terminates. If the agent chooses action d2 then the agent transits to our hard
Note that 1/d is the largest possible minimum eigenvalue due to that, for any data distribution Ph. amin (B( [5(s, a))(s, ") )) & 1/d since [|o(s, a)]la 1 for all (s, E S A.
For H = 1, the ordinary least squares estimator will satisfy that ||0] Bous 2 5 O(d/n) with high prohability. See e.g. (Hsu et al. 20126).
5

---

Published as a conference paper at ICLR 2021
instance. In order to find a policy with suboptimality at most 0.5, the agent must evaluate the value of the optimal policy in our hard instance up to an error of 0.5, and hence the hardness result holds.
Remark 1 (The sparse reward case). As stated, the theorem uses a deterministic MDP (with stochas- tic rewards). See Appendix [ for another hard case where the transition is stochastic and the reward is deterministic and sparse (only occurring at two states at h H).
Remark (Least-Squares Policy Evaluation (LSPE) has exponential variance). For offline policy evaluation with linear function approximation, the most na've algorithm here would be LSPP,, i.e., using ordinary least squares (OLS) to estimate 0", starting at level h = H and then proceeding backwards to level h using the plug-in estimator from the previous level. Here, LSPE will pro- vide an unbiased estimate (provided the feature covariance matrices are full rank, which will occur with high probability). As a direct corollary, the above theorem implies that LSPE has exponential variance in H. See Section f a more detailed discussion on LSPE. More generally, our theorem implies that there is no estimator that can avoid such exponential dependence in the offline setting.
Remark 3 SquareS Value Iteration (LSVI) versus Least- Seast-S Policy Iteration (LSPI)). In the offline setting, under Assumptions I and 2 in order to find a near-optimal policy, the most naive algorithm would be I.SVI, i.e., using ordinary least squares (OI.S) to estimate 0", starting at level h = H and then proceeding backwards to level h = 1, using the plug-in estimator from the previous level and the bellman operator. The above theorem implics that LSVI will require an exponential number of samples to find a near-optimal policy. On the other hand, if the regression targets are collected by using rollouts (i.e. on-policy sampling) as in LSPI (Laooudakis & Parr 2003). then a polynomial number of samples suffice. See Section D in (Du et al.) (000)) for analysis. Thus, Theorem implies an exponential separation on the sample complexity between LSVI and LSPI. Of course, LSPI requires adaptive data samples and thus does not work in the offline setting.
One may wonder if Theorem 4.1 still holds when the data distributions {ua) are induced by a policy. In Appendix C. we prove another exponential sample complexity lower bound under the additional assumption that the data distributions are induced by fixed policy π. However, under such an assumption, it is impossible to prove a hardness result as strong as Theorem 4.] (which shows that evaluating any policy is hard), since one can least evaluate the policy π that induces the data distributions. Nevertheless, we are able to prove the hardness of offline policy evaluation, under a weaker version of Assumption See Appendix C for more details.
In the remaining part of this section, we give the hard instance construction and the proof of Theo- rem 4.1 We use d the denote the feature dimension, and we assume d is even for simplicity. We use d to denote d/2 for convenience. We also provide an illustration of the construction in Figure |
State Space, Action Space and Transition Operator.
The action space = ={a1, [2). For each ... sh and s d+1 For each h [H 1]. for each d+1 E 2,, d+ 1}, we have P(s a1) = h and P(sh, m1) = Sh
h E [H]. Sn contains d + 1 states s/. s ...,,,
Reward Distributions. Let 0 S ro S d-H/2 be a parameter to be determined. For each (h, c) E [H 1] x (d] and a E A, we set R(s,, a) = and R(s a) = To (d 11 d -2/ For
1 with probability (1 (1+ ru)/2
the last level, for each e E [d] and a E A. we set R( a) 1-1 with probability (1 (1-17) ro)/2
so that [S = To. Moreover, for all actions a E A, R(sa
d+1 .a) ro dd/2
Feature Mapping. Let G1, c ed be a set of orthonormal vectors in Rdd, Here, one possible choice is to set ei, e2, ed to be the standard basis vectors. For each (h, c) E [H] x [d], we set 0f a,) = c.e (s8 02) c and (bs s(s a) / for all A.
Verifying Assumption I
The following lemma shows that Assumption T holds for our construc- tion. The formal proof can be found in Appendix A
Lemma 4.2. For every policy क S + ((A), for each h E for all (s,a) E Sh x A. we have (8, = (0g) Φ(s, a) for some 0g E Rd.

---

Published as a conference paper at ICLR 2021
az) =
& (st-1.a .a)
+ + e,)/
Q (,) = r2 20-12
( .) = r,
d+1
R(5.0)
R(s .0) = jor w/25
Q a.) = mn R(r.0)
als .0) = 120
af
R( .a) = =n(diuu-ura - d0n-211)
0G.u.)) = "02
0 (5h t1 aa) nddl-muu
R(s.e)
R (st") .a) roldiu- aon
@ = m R(F.e)
(c = R(s61)aa) = 119))
---1
06.0) m [(((,,)] mo
Q - rydd
A(*3",,) 1,21/
An illustration of the hard instance. Recall that d = d/2. States on the top are those in the first level (h = 1), while states at the bottom are those in the last level (h H). Solid line (with arrow) corresponds to transitions associated with action 01, while dotted line (with arrow) corresponds to transitions associated with action dg. For each level h [H], reward values and Q-values associated with si ....... oy are marked on the left, while reward values and Q-values associated with sx+1 are mark on the right. Rewards and transitions are all deterministic, except for the reward distributions associated with 8/ value when it is stochastic. For each level É [H]] for the data distribution μu. the state chosen uniformly at random from those states in the dashed rectangle, i.e., (5), .h....,s,) while the action is chosen uniformly at random from {a1,a2) Suppose the initial state is s d+1 When ro = 0, the value of the policy is O. When = d H/2, the value of the policy is ro dH/2 1.
Figure I:
SH We mark the expectation of the reward
The Data Distributions. For each level [H], the data distribution μn a uniform distribution over [s) a1), (sh, a2), (sh, a1), (sh, a2), ..., (s), a1), (sh a2)). Notice that (s d+1 a) in the support of na for all a E A. It can be seen that, ( [0(s, a)d(s, a) = à Een Eoee = T.
The Lower Bound.
We show that it is information-
hard for any algorithm to distin-
guish the case To 0 and ro- H/2, We fix the initial state to be d+1 and consider any policy m. When To = 0, all reward values will be zero, and thus the value of π is zero. On the other hand, when To H/2 the value of π would be ro jd//2 = 1. Thus, if the algorithm approximates the value of the policy up to an error of 1/2, then it must distinguish the case that ro O and ro d-H/22
We first notice that for the case ro = 0 and ro = d-H/2, the data distributions {ux J the fea- ture mapping & : S x A + RRd, the policy to be evaluated and the transition operator P are the same. Thus, in order to distinguish the case ro 0 and ro d-H/2 the only way is to query the reward distribution by using sampling taken from the data distributions. For all acteon pairs (s, a) in the support of the data distributions of the first H 1 levels, the reward distributions will be identical. This is because for all E S, \ (o and a E A, we have R(s, a) = 0. For the case to and ro H-H/2 for all state-action pairs (s,a) in the support of the data dis- [1 with probability (1 + ro)/2 Therefore, to distinguish
tribution of the last level, R(s,a)= { -1 with probability (1 - ro)/2
7

---

Published as a conference paper at ICLR 2021
Algorithm Least-Squaree Policy Evaluation
Input: policy be evaluated, number of samples N, regularization parameter À 0
2: Let Qu++1(-- = 0 and V--+ =
3: for h= H, H 1, 1....... do
4: Take samples (s), ai) Mh. ry ~ r(s) ai) and 5/ a()
an) for each i E [M]
5:
Let An = Die(y @(5): (.)) at) +++
T AZ
6:
Let 0h = -A, (Ein o(sh, ag) (rih + (+++(5h)))
Let
7: Let Qn(:)) (())))))) -T, and (.) (+)(()))
the case that ro 0 and ro à- -122 the agent needs distinguish two reward distributions
1 with probability 1/2 and
with probability (1 + d ///
with probability (1 -dd-H/22/22 Now we in-
[-1 with probability 1/2
voke Lemma B.1 in Section B by setting d H/2 /2 and 0.9. By Lemma B.1 in order to distinguish 11 and 72 with probability at least 0.9, any algorithm requires 22d")) samples.
Remark 4. The key in our construction the state sh d+1 in each level, whose feature vector is defined to be Seedee//'/2 In each level, .f+1 amplifies the Q-value by a d'/2 factor, due the linearity of the Q-function. After all the H levels, the value will be amplified by d!/2 factor. Since d+1 not in the support of the data distribution, the only way to estimate the value of the policy is $h to estimate the expected reward value in the last level. Our construction forces the estimation error of the last level to be amplified exponentially and thus implies an exponential lower bound.
5 UPPER BOUNDS: Low DISTRIBUTION SHIFT OR POLICY COMPLETENESS ARE SUFFICIENT
In order to illustrate the error amplification issue and discuss conditions that permit sample-efficient offline RL, in this section, we analyze Least-Squares Policy Evaluation when applied to the offline policy evaluation problem under the realizability assumption. The algorithm is presented in Algo- rithm I For simplicity here we assume the policy x to be evaluated is deterministic.
Notation. For each h E [H), define A, B( [o(s, a) to be the feature covariance
matrix level h. For each h 11), define A++1 (( 3-..:n...PPPP...... [Ø(s, (B)) +()) T] to be the feature covariance matrix of the one-step lookahead distribution at level h. Moreover, define A1 (($1, π (s1)))(s1, (1 (s We define 4, be a N matrix, whose i-th row is Φ(s), a),), and define h to another N d matrix whose i-th row is d(s), x (3)))) For each E [H] and i [N] define 4/ = ri + V (5)) Q(s), a.,). We use & to denote vector whose i-th entry E
Now we present general lemma that characterizes the estimation error of Algorithm Tyy an equal- ity. The proof can be found in Appendix D Later, we apply this general lemma special cases.
Lemma 5.1. Suppose À in Algorithm 7 and the given policy n, there exists O2 .2....,................. Os 0h, for all (s, a) E Sn x A. Then we have
Rd such that for each h E [H). (% a) 0(s, T
H Σ
- -(ss,
A Φ T ... -A, En Ad 0%.
(1)
Now we consider two special cases where the estimation error in Equation can be upper bounded.
Low Distribution Shift. The first special we focus on is the case where the distribution shift between the data distributions and the distribution induced by the policy to be evaluated low. To measure the distribution shift formally, our main assumption is as follows.
Assumption 3. We assume that for each h [H), there exists C₁ 2 1 such that Ar CLA
8

---

Published as a conference paper at ICLR 2021
Remark 5. For each h E [H], if m (An) = / for some C₁ 2 1, we have A, 3I3 ChAR-
Therefore, Assumption 3 can be replaced with the assumption that C₁AA, = I. However, stick to the original version of Assumption B as it gives a tighter characterization of the distribution shift.
Now state the theoretical guarantee of Algorithm | The proof can be found in Appendix D
Theorem 5.2. Suppose for the given policy т, there exists 0,, .2....... Os E IRd such that for aa)TT) T0) On for all (s,a) E Sn x A and ||0xll2 I H Let for some C > O. With probability at least 1 5, for some O.
each h E [H], (u(s,a) = Φ(s,a)
A = CH (Hydlog(dHH) (QT ((11)) Q11 T (s1))) c. -T Cn ...H. /dlog(dH//8//
Remark 6. The factor IT C₁ in Theorem 5.22 that the estimation error will be amplified geometrically. Now we discuss how the error is amplified when running Algorithm oon the instance in Section 3 to better illustrate the issue. If we run Algorithm D on the hard instance in Section + when h = H. the estimation error on ((sH)) would be roughly N-1/2 for each E [d]. When using the linear predictor at level H to predict the value of sz the error will be amplified by d2/ When h = H - 1, the dataset contains only s for с E [d], and the estimation error on the value of # will be the same that of sH which is roughly (d/N)3/2, Again, the estimation error on the value of - will be (d² 1/2 when using the linear predictor at level H - 1. The error will eventually
H be amplified by a factor of d which corresponds to the factor II -== C in Theorem 5.2
Policy Completeness. In offline RL, another representation condition is closedness under Bellman update (Szepesvári & Munos 2005 Duan & Wang 2020), which is stronger than realizability. In the context of offline policy evaluation, we have the following policy completeness assumption.
Assumption 4. For the given policy n, for any for any (s, a) E Sh A. [[, a)] + Eves, P(s' |s a))(('s s,a))(ss'=(()))) ((s'))TB) On a(s,a)
and fn, E R.d, there exists 0' E Rd such that
Under Assumption 4 and the assumption that m (Aa) 2 Ao for all h E [[t] for some Ao > O. Duan & Wang (2020) have shown that for Algorithm | by taking N = poly(H, d, 1/e, Ao), we have (*1, x (81)) - (s1, (s1))) S E. We refer interested readers to (Duan & Wang 2020).
We remark that the above analysis again implies that geometric error amplification is real issue in offline RL, and sample-efficient offline RL is impossible unless the distribution shift is sufficiently low. i... I Cj is bounded, or strong representation condition (e.g. policy completeness) holds.
6 CONCLUSION
While the extant body of provable results in the literature largely focus on sufficient conditions for sample-efficient offline RI., this work focuses on obtaining better understanding of the necessary conditions, where we seek to understand to what extent mild assumptions can imply sample-efficient offline RL. This work shows that for off-policy evaluation, even if we are given a representation that can perfectly represent the value function of the given policy and the data distribution has good coverage over the features, any provable algorithm still requires an exponential number of samples to non-trivially approximate the value of the given policy. These results highlight that provable sample-efficient offline RL. is simply not possible unless either the distribution shift condition is sufficiently mild or we have stronger representation conditions that go well beyond realizability.
ACKNOWLEDGMENTS
The authors would like to thank Akshay Krishnamurthy, Alekh Agarwal, Wen Sun, and Nan Jiang for numerous helpful discussion. Sham M. Kakade gratefully acknowledges funding from the ONR award N00014-18-1-2247, and NSF Awards CCF-1703574 and CCF-1740551. Ruosong Wang was supported in part by the NSF 11S1763562, US Army W91 INF1920104, and ONR Grant N00014181 128611 Research performed while Ruosong Wang was an intern at Microsoft Research.
Without loss of generality, we can work in coordinate system such that 10 ||2 < H /dd and ( (dss,)))l a)ll2 S
1 for all (s, a) e S A. This follows due John's theorem (c.g. see (Ball 1997 Bubeck 2012)).

---

Published as a conference paper at ICLR 2021
REFERENCES
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. International Conference on Machine Learning, 2020.
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical fonndatical cambridge university press, 2009.
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, 2008.
Keith Ball. An elementary introduction to modern convex geometry. Flavors of geometry, 31:1-58, 1997.
Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: overview. In Pro- ceedings of 1995 34th IEEE Conference on Decision and Control, volume 1, pp. 560-564. IEEE, 1995.
Sébastien Bubeck, Nicolò Bisa-Bianchi, and Sham M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In COLT 2012 The 25th Annual Conference Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pp- 41.1-41.14, 2012.
Jinglin Chen and Nan Jiang. Information-theorete considerations in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042-1051, 2019.
Herman Chernoff. Sequential analysis and optimal design. SIAM, 1972.
Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is a good representation suf- ficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020.
Yaqi Duan and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approx- imation, arXiv preprint 2xXi::2002.095/6 2020.
Miroslav Dudik, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 1097-1104, 2011.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference Machine Learning, pp. 1447-1456, 2018.
Yihao Feng, Tongzheng Ren, Ziyang Tang, and Qiang Liu. Accountable off-policy evaluation with kernel bellman statistics. arXiv preprint arXiv:2008.0660 066668 2020.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 2052-2062. 2019.
Geoffrey Gordon. Stable function approximation in dynamic programming. Machine Learning Proceedings 1995, pp. 261-268. Elsevier, 1995.
Geoffrey Gordon. Stable fitted reinforcement learning. In Advances in neural information pro- cessing syslems, pp. 1052-1058, 1996.
Geoffrey J Gordon. Approximate solutions to markov decision processes. Technical report, BARNEGIE-MELLOOK UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE, 1999.
Omer Gottesman, Fredrik Johansson, Joshua Meier, Jack Dent, Donghun Lee, Srivatsan Srinivasan, Linying Zhang, Yi Ding, David Wihl, Xuefeng Peng. Jiayu Yao, Isaac Lage, Christopher Mosch, Li wei H. Lehman, Matthieu Komorowski, Matthieu Komorowski, Aldo Faisal, Leo Anthony Celi, David Sontag, and Finale Doshi- Velez. Evaluating reinforcement learning algorithms in observational health settings, 2018.
10

---

Published as a conference paper at ICLR 2021
Zhaohan Guo, Philip S Thomas, and Emma Brunskill. Using options and covariance testing for long horizon off-po policy evaluation. In Advances in Neural Information Processing Systems, pp. 2492-2501, 2017.
Daniel Hsu, Sham Kakade, Tong Zhang, et al. tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability. 17, 2012a.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference on learning theory, pp. 9-1, 2012b.
Natasha Jaques, Asma Ghandcharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-policy batch deep reinforcement learning of human preferences in dialog, 2020. URL Dettps::/openrevieee wet.e/ewwweeeeeeeeeeeeeeeeeeeeee net/forummit
BJ15rRVEVH
Nan Jiang and Jiawei Huang. Minimax confidence interval for off-policy evaluation and policy optimization. arXiv preprini arXiv:2002.0208/ 2020.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 652-661. PMLR, 2016.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.
Nathan Kallus and Masatoshi Uchara. Efficiently breaking the curse of horizon in off-policy evalu- ation with double reinforcement learning. arXiv preprint urXiv://09.05830 2019.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evalu- ation in markov decision processes. Journal of Machine Learning Research, 21(167):1-6) 2020.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity best-arm identifi- cation in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. based offline reinforcement learning, 2020.
Morel Model-
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. In Advances Neural Information Processing Systems, pp. 1840-1848, 2016.
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. neural information processing systems, pp. 11761- 11771, 2019.
Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedhack in reinforcement learning via distribution correction. arXiv preprint arXiv:2003.07305, 2020.
Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of machine learning research, 4(Dec): 2003.
Romain Laroche, Paul Trichelair, and Rémi Tachet des Combes. Safe policy improvement with baseline bootstrapping. Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
Lihong Li, Remi Munos, and Csaba Szepesvari. Toward minimax off-policy value estimation. In Artificial Intelligence and Statistics, pp. 608-616, 2015.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5356- 5366, 2018
Yao Liu, Pierre-Lue Bacon, and Emma Brunskill. Understanding the curse horizon off-policy evaluation via conditional importance sampling, arXiv preprint arXiv: 1990066500 2019.
11

---

Published as a conference paper at ICLR 2021
Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications to educational games. In AAMAS, pp. 1077- 1084, 2014.
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-arme bandit problem. Journal of Machine Learning Research, 5(Jun):623-66 648, 2004.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 5 518(7540):529, 2015.
Wenlong Mou, Zheng Wen, and Xi Chen. On the sample complexity compleco reinforcement learning with policy space generalization. arXiv preprint arXiv:2008.07353, 2020.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pp. 560-567. 2003.
Remi Munos and Andrew W Moore. Barycentric interpolators for continuous space and time re- inforcement learning. In Advances in neural information processing systems, pp. 1024-1030, 1999.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, (1May):8158857, 2008.
Dirk Ormoneit and Šaunak Sen. Kernel-based reinforcement learning. Machine learning, 49(2-3); 161-178, 2002.
Doina Precup. Eligibility traces for off- off-policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 2000.
Stéphane Ross and Drew Bagnell. Agnostic system identification for model-based reinforcement learning. In Proceedings of the 29th International Conference on Machine Learning. ICML 2012, Edinburgh. Scotland, UK. June 26 - July 1, 2012. ieml.cc / Omnipress, 2012.
Wen Sun, Arun Venkatraman, Geoffrey J Gordon, Byron Boots, and Andrew Bagnell, Deeply ag- grevated: Differentiable imitation learning for sequential prediction. In International Conference on Machine Learning, pp. 3309-3318, 2017.
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, pp. 880-887, 2005.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation reinforcement learning. In International Conference Machine Learning, pp. 2139-2148, 2016.
Philip S. Thomas. Safe reinforcement learning. PhD thesis, University of Massachusetts, Amherst, 2014.
Philip S Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off- policy evaluation. In Twenty-Ninth AAAI Conference Artificial Intelligence, 2015.
Philip S. Thomas, Bruno Castro da Silva, Andrew G. Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior intelligent machines. Science, 366(6468): 999-1004, 2019. ISSN 0036-8075. doi: 10.1 10.111/ccccnccc.agg33.
Samuele Tosatto, Matteo Pirotta. Carlo d' Eramo, and Marcello Restelli. Boosted fitted q-iteration. In International Conference on Machine Learning, pp. 3434.3443. PMLR, 2017.
Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learming,
2015.
J Tsitsiklis and B Van Roy. An analysis of lemporal-differeme learning with function approximation (technical report lids-p-2322). Laboratory for Information and Decision Systems, 1996.
Masatoshi Uchara and Nan Jiang. Minimax weight and q- q-function learning for off-policy evaluation. arXiv preprint arXiv: /0/0./99////00 2019.
12

---

Published as a conference paper at ICLR 2021
Benjamin Van Roy. Feature-based methods for large scale dynamic programming. PhD thesis, Massachusetts Institute of Technology, 1994.
L. Wang, Wei Zhang, Xiaofeng He, and H. Zha. Supervised reinforcement learning with recurrent neural network for dynamic treatment recommendation. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018.
Ruosong Wang, Simon S Du, Lin F Yang, and Ruslan Salakhutdinov. On reward-free free reinforcement learning with linear function approximation. arXiv preprint arXiv:2006. 1274, 2020.
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evaluation in contextual bandits. In International Conference Machine Learning, pp. 3589-3597, PMLR, 2017.
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning, 2020. htW.apppss/pppeereee...e./errrra
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. arXiv preprint arXiv:2008. 000000000000099000 2020a.
Tengyang Xie and Nan Jiang. Q' approximation schemes for batch reinforcement learning: A theoretical comparison. arXiv preprint arXiv:2003.03924, 2020b.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for rein- forcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, pp. 9668-9678, 2019.
C. Yu, G. Ren, and J. Liu. Deep inverse reinforcement learning for sepsis treatment. In 2019 IEEE International Conference on Healthcare Informatics (ICHI), pp. 1-3, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill. Limiting ex- trapolation in linear approximate value iteration. In Advances in Neural Information Processing Systems, pp. 5616-5625, 2019.
13

---

Published as a conference paper at ICLR 2021
A PROOF OF LEMMA 4.2
Proof. We first verify Q is linear for the first H- levels. For each (h, c) E [H - 1] x [d]. we
have
d+1 a1) = =R(sh, a( R(1 +.... R(s
d+1
d+1 ,01) ro - h1/2
Moreover, for all a E A. d+1 .0) R d+1 a) R( a1) R( 01) +.... R(s d+1 ,01) ro -
d+1
Therefore, if we define
d 0% Σ ro d h2/2 ce Σ
d
(s 02) c
then a)) = ) oss a) for all (s, E S₁ x A.
Now verify that the Q-function is linear for the last level. Clearly, for all E [d] and A, (T( a) ro and (0
d+1 ; ,a) -r- Vd. Thus by defining 07 Eeen we have (s, (0T) Φ(s,a) a) for all (s,a) E Sh x A.
B A TECHNICAL LEMMA
We need the following lemma in the proof of our hardness results.
Lemma B.1. Let be a random variable uniformly distributed on {a_, J. where a = 1/2 and a+ 1/2 + with 0 < < 1. Suppose that &1, ....... Em are i.i.d. {+1, - 1]-valued random
variables with Pr(c = +1] = o for all E [m). Let f be a function from { [+1, - 1 to fat, a
Suppose S C/e² log(1 (lgg1/))fo for some fixed constant C. Then
C2....
+ a)
To our best knowledge, Lemma B.1 was first proved in (Chernoff) 1972) and has enormous ap- plications in statistical learning theory (see, e.g., Chapter 5 in (Anthony & Bartlett (009h) and bandits (Mannor & Tsitsiklis 2004).
To prove Lemma B. one can first prove that the maximum likelihood estimator (MLE) is optimal and then show that MLE requires 2(1/e² log(1/8)) samples to correctly output a with probability 1 - 8 by anti-concentration. Lemma B.I can also be proved by using information theory. See, e.g..
Kaufimann et al. 2016 for such a proof.
C ANOTHER HARD INSTANCE
In this section, we present another hard case under a weaker version of Assumption [ Here the transition operator is stochastic and the reward is deterministie and sparse, meaning that the reward value is non-zero only for the last level. Moreover, the data distributions {pn 1/1 are induced by fixed policy Tdata- We also illustrate the construction in Figure 2 Throughout this section,
d the denote the feature dimension, and assume is even integer for simplicity. We use d to denote d/2 -
In this section, adopt the following realizability assumption, which is weaker version of As- sumption [
Assumption 5 (Realizability). For the policy ा S + A(A) to be evaluated, there exists 0..... OH E IRd such that for all (s, a) E S x and h E [M].
(s, 0 ((s.a))
14

---

Published as a conference paper at ICLR 2021
C1 0g 9212
(6).4))) - Ga
PGs 1ofth.ag = + loft), 2/1y22 (fse" .aa) -raalraaaann 1520-1193
005,0)= =
P(Ats laft), ag) (1 + trad w/2//2
Plaies 1sf (1-7dd9--orn 7000-3013/22 (sé*) (erttes)) rydor
(6E.0) 0/2
(0%-..0)
Plsh Is ( Pla leftl, ag) = (1--dd/1y2 (fff 1.)) n221
PGd = =1 (1+ POsl 151-1.0) =1--))))=)11)))
%/-1
((%..))
RGG x) R(
SW
Figure 2: An illustration of the hard instance. Recall that d = d/2 1. States on the top are those in the first level (h = 1), while states at the bottom are those in the last level (h H). Dotted line (with arrow) corresponds to transitions associated with actions a1, a2, Qg. while solid line (with arrow) corresponds to transitions associated with actions ad+ ad421.... ag We omit the transition associated with 01, 02 .2....,,4 ag the figure if all actions give the same transition. For
each level [H] Q-values associated with s/,- S2 ......., . Sh S Sh marked the left, while transition distributions and Q-values associated with d+1 are marked on the right. Rewards are all deterministie, and the only two states (s and HH) with non-zero reward values are marked in black and grey. Consider the fixed policy that returns ag for all input states. When ro = 0, the value the policy is O. When ro = d (Hf 2)/2 the value of the policy is = rod 22/22/222222 1.
State Space, Action Space and Transition Operator. In this hard case, the action space {ai, az. ar} contains d elements. S₁ contains a single state s1. For each h 2 2, S₁. contains 3 3 states s7, ,.,,..., d+1 ,8 and 87.
Let 0 < To S d (2-222 be a parameter to be determined. We first define the transition operator for the first level. We have
a aes E [d]
89
a as+l
P(s
82
d
d+1
a E {0143) Ad44 od)
Now we define the transition operator when h E (2,3....,
2}. For each h E (2,3...., 2), d+1 p( a) 8 and P(s a) 8p-1. For each d+1 aa.) ih+1. For Foralla {a ".2 ad). h (2,3,.... H- and [d], we have P(
A and [d], have P(s a) sh41.
15

---

Published as a conference paper at ICLR 2021
have
with probability (1 + /(H-2)/2))/2
P
%/2
d+1
a
h+1
with probability (1 - ro d -//
sh+1
Now we define the transition operator for the second last level. For all c E [d] and a E A, we have
{ $ with probability (1 + ro)
P P(5 - { S1 with probability r2
For all a E A. we have -() = Hi and ((SH-1.0) SH. For each E [d]. we have d+1 P(* P1*H-1: 0e) = 54g- For all a E {a "d42' aa), we have
with probability (1+ ro- vdd /2
P(1d11 d+1 P(s -
a)
8H
8H1 with probability
(1 (1-ro) ro- vd
Reward Values. In this hard case, all reward values are deterministic, and reward values can be non-zero only for the last level. Formally, we have
8/1
R(s a)
8
otherwise
Feature Mapping. As in the in hard instance in Section let el 62, ..., ea be a set of of orthonor- mal vectors in R For the initial state, for each c E [d], we have Φ(51, ao) = ec.
Now define the feature mapping when 32, .,,,, H}. For each h E (2,3,... H}. A and E [d], (88,,) a) = ees (08 a) = cdt1 and (08) a) = cd+2. Moreover, for all actions a E A.
a = ac [d] a {adtr 0242 ad]
(1 h a)
2172 (e + + + +... +22)
Clearly, for all (s, E S A. (0(s, a) l)l 1.
Verifying Assumption 5
Now consider the deterministic policy S + A. which is defined holds.
to be (ss) = ad for all s E S. We show that Assumption
When h 1, define
d
Σ c=1
ro HH-3)//
32/2 ec + ejtt 6442
Σ ro C44246
For each h (2,3.... H 2}, define
d
0 = Σ
e2t2 + Σ ro . (HHhh22)/2 08424e"
e + E141
=11
For the second last level H define
0 = Σ ro e, + C241 6242
Finally, for the last level H, define
0H = ed41 - Ed42'
It can be verified that for each h [M]. (s, 0% p0 a) for all (s, E Sn A.
16

---

Published as a conference paper at ICLR 2021
The Data Distributions. distribution over {(51, ae) distribution over {(s), a1), (5 a.)..... (sh+ a1), (5) 01), (5% 01), (s a1), (shtt ,,2),..., (5% .aa)-
For the first level, the data distribution μl is defined to be the uniform E [d]. For each 2 2. the data distribution H4 is a uniform
Notice that again (5 a) is not in the support of b4 for all actions {aa+D (0241 2842:-1- ad) lt can be seen that for all h [/]].
E (es.)ma
1
Σ
c
1 -/
cm
Moreover, by defining
Uniform((A)
5 =
8 {s% h E (2.3...... H), [d]
a1 a1 a1 Uniform( (a1, ,.,.a..,.................. aal)
Tdata(
8 8 {s e ( H}}
8 E {8) (23, H}}
8 E (0 (od41
| (2,3,
have 14h
Tuate for all h E [M]. 1th
The Lower Bound. Now we show that it is information-theorrttiaall hard for any algorithm to distinguish the case = 0 and To = d (2--2) in the offline setting by taking samples from the data distributions {pA h==1 /== Here we consider the above policy æ defined above which returns action ag for all input states, Notice that when To 0, the value of the policy would be zero. On the other hand, when d the value of the policy would be H-//2 1. Therefore, if the algorithm approximates the value of the policy up to an approximation error of 1/2, then it must distinguish the case that ro = 0 and rg = dH
We first notice that for the case ro = 0 and ro = d-(H-2)/2 the data distributions { the feature mapping é x A + Rd, the policy æ to be evaluated and the reward distributions are the same. Thus, in order to distinguish the case = 0 and тo = 2 the only way is to query the transition operator P by using sampling taken from the data distributions.
Now, for all state-action pairs (s, a) in the support of the data distributions of the first H - 2 lev- els (namely /2, HH 22) the transition operator will be identical. This is because chang- ing ro only changes the transition distributions of (sQ+1 ;4a+)): (s (1842)....,,$77) (oa+1 (a)), and such state-actions are not in the support of Ps for all h E [H 2). Moreover, for any d+1 (s, a) E { 8 # H-11 x A in the support of pH-1, P(s, a) will also be identical no mat-
ter To 0r To d 2)/2 For those state-action pairs (s, a) in the support of pH-1 with
$ 1
+ 87 #H-13:
à+1
J. we have
with probability (1 ro)/2 SH with probability ro)
P(s,a)=
Again, this is because (sd41 a) is not in the support of pa- for all {ai+1: ".42 aa))
Therefore, in order to distinguish the case two transition distributions
0 and ro (H--22) the agent needs distinguish
with probability 1/2
H
P1
with probability 1/2
H1
and
H with probability (1 di (MM-2222)) 2)/2)/2 P2
SH with probability (1 d= (2--222//2//
Again, by Lemma B.1 in order to distinguish P1 and P2 with probability at least 0.9, needs -2) samples. Formally, have the following theorem.
17

---

N Published as a conference paper at ICLR 2021
Theorem C.I. Suppose Assumption holds, and rewards are deterministic and could be none- zero only for state-action pairs in the last level. Fix an algorithm that takes as input both a policy and a feature mapping. There exists MDP satisfying Assumption 5 such that for fixed policy n S - A, the algorithm requires (ddd/2 1)H/2) samples to output the value of up to constant additive approximation error with probability at least 0.9.
D ANALYSIS OF ALGORITHM
D. PROOF OF LEMMA 5.1
Clearly,
On = A/11
(sh. (rh + 1
An
Mshh ah) (rh. + (3)
And
((5h, ah) (1% + o(3 n (3x))) 00-1)
= An
6(5 oh) (rh + ((3,, 1 + Σ
olsh. ah) 6(3), {3,1)) ((0ut) - -b--1)
==1
= -
Σ (6sh (rh + 6(3 (3x))) (
+ &ri''
Σ (s on) o(3 (Bh))) (0ut1 0nti))
For the first term, we have
ps5 oi) (rh + o65 (()))) B141))
1
Σ
h
A h
(sh (rh + a
(bh ( (rh ( v
(bh a (Q" (sh, ab) + =hi
-A
Mshh abh Eh. + A Σ pls ah) al)) To
=A Σ (6s), a/i) Eh + A 11)00
= =A 1 2 + 0/ - اd On.
Therefore,
0 0, 1 \A 10)) + o T2 82)
= - ΛY (0,) + 1 o
AA, Oz)
1 T21 2 Oz,0 0%)
"
\ + و 1 23 .. (A, - En 2d
1=1
18

---

Published as a conference paper at ICLR 2021
Also note that
(Q=(s1, - ((1))) = =10 - 0011
D.2 PROOF OF THEOREM 5.2
By matrix concentration inequality (Tropp 2015). we have the following lemma.
Lemma D.I. For each [H), with probability 8/(H), for universal constant C, have
1 tn - An |
s SC (CVdlo(dH//8/M
N
and
1
Nat1 s <CVdlog|((H/)//) h+1 h+1
N
Therefore, since X CH ddoog (dH / with probability 1 8/(4H), we have
Ån 2/ Φn + NAs
Note that
(0 (81)) - ((1))
11
<H.
\ 1 T 12 25 13
(A T Eo - A 10x)
h=1
H
<2H
Σ
Φ 22
2 43
A 3 1 En
2
Σ
AT
10
12
-AA 8/
T,
For each h E [H].
| の2 03
< X A,A Φ.
12
T ,,
1 T3 A, TT 5x
// A, 1/2
| Φ T1 1 2 L2 ... An Ea
h-1
</ 1/21/2
A 2
1 1 16 Th 1 +w
11En 11a.llan,, t
h=11
Similarly,
2 T 1 D3 ... AA 12
h-1
1/1
1/2
A . $ llz |1A P
T 112) -22. 11000101 1 (o
h-1
A A 2T
-
X H2d.
#==1
For all h [H]. we have
1 ll2 1
and
1/, T S 1 1/2 A, i
-1/2
+ 11
1/2 ( क5 - ~,
Conditioned on the event in Lemmal D.I
N Ans
A 2 NA - C
19

---

Published as a conference paper at ICLR 2021
which implies , 1/2 A,,,,
A, 1/2| S Cn. Moreover, conditioned the event in Lemma D.I
||,, 1/2 ( Dh NA, 1/112 - CVdlog(d//O)N/A
Thus,
"AT 1/2 CI/N.
and
1/2112 12 - C₁ + C logg(dH/))) /X. Finally, by Theorem 1.2 in Hsu et al. 2012a). with probability 64H).. for some constant C",
||A,,
( - 2/ A,
1/2
have
|
11
I (HH)d)og(HH)))
Therefore,
A 1 P24 1 43 1 En
12 A2
+ + 22 2. 43
C
(C2 (C2+0v (V0oOoloo///))//
(Cn, + CV (llog(//)))/// (C'HIdlog(HH0)) + d12
Ci
(C2+1/H)
(Ch + 1/H) x (C'H + AH
C1 C2 Ch (C' H CaH \log(dHH8)))
Let > 0 be a large enough constant. We now have
H II
dlog(dH/B
E. ((1 (ss)) (()))) sc.
Ch dH
N
20


Reviews:
[{"review_id": "yQNWw3LkjoI", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "It's an interesting paper showing provably efficient batch RL is impossible when only two assumptions holding: a) Realizability, and b) Feature Coverage. By providing counter-examples, which is quite persuasive as the State/Action Space is only polynomially dependent in H, the sample complexity could be exponentially dependent in H w.h.p. \n\nHowever, I still have doubts about the Assumption Feature Coverage. Different than Assumption Concentrability [Chen & Jiang(2019), Xie & Jiang(2020a)], Feature Coverage only assumes that feature covariance matrix has minimum eigenvalue 1/d. My doubts then follow: \n1) Is Asp Concentrability a more stringent asp than Asp Feature Coverage (from a mathematical perspective)? If so, why we would concern Asp Feature Coverage while Chen & Jiang(2019) already proves Asp Concentrability is necessary for efficient batch RL?\n2) Can Asp Feature Coverage really represent exploratory of the batch dataset? In RL's perspective, exploratory is important empirically and theoretically. However, in the hard instance, the important states $s_h^*$ are even not in the support of the dataset (maybe also breaks the Asp Concentrability?), though I understand it's necessary to obtain the exponential lower bound.\n3) Theorem 5.1 confuses me a little. I understand the main goal is to illustrate Error Amplification. But why we would concern upper bound instead of the lower bound? Or Sec5 aims to say that Error Amplification is unavoidable under Realizability and Feature Coverage?\n\nIn conclusion, I argue that this paper is well-written and answers the question perfectly with certain assumptions. I have also checked the proof and there are no significant errors. Though I have some doubts about whether certain assumptions are reasonable enough in RL, I still stay positive about this paper. My doubts may be incorrect, but I'm looking forward to the discussion.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XKXmbY5ftOI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a impossibility result for value-function approximation in batch-mode RL. The chart below puts this work in context. This work essentially shows -- through a constructive example of an MDP -- that the amount of data needed for approximating Q values must increases exponentially with the horizon in episodic RL tasks even if we assume that the Q-values are realizable and that the features gathered by the behavior policy -- that collected the data -- are uncorrelated. This problem arises because the data gathering policy can fail to get data from all states even though the features themselves are uncorrelated. \n\nThe authors claim that this setting is interesting because these conditions only require polynomial-number of samples in the standard supervised learning case, and I agree with that. Broadly I checked the main construction in the paper and the result seems correct. I think this paper will be a good addition to ICLR.\n\n      |                | Strong Concentratibility|  \n      |                | extra conditions on     | (Xie Jiang 2020)\n      |                |  the dynamics of the MDP|  [✓]\n      |                |\n      |Coverage of the | Concentrability         |       Szepesvári and Munos 2005\n      |behavior policy | (experience gathered    |                      [✓]\n      |                |  from every state)      |\n      |                | \n      |                | Uncorrelated            | This work\n      |                | Features                | [x]\n      |________________|______________________________________________________________\n      |                                           Realizability     Bellman Closedness\n      | bellman closed = Every intermediate value function arrived at after \n      | bellman update is also linearly realizable\n      |_______________________________________________________________________________\n      |                             Representability of Q values\n\n\n## Some comments\n\n1. Assumption 2 will actually imply that  σ_max = 1/d as well because (σ_min + ... + σ_max) ≥ d σ_min = 1 and sum of eigenvalues equals the trace, and exchanging trace and expectation will give (σ_min + ... + σ_max) ≤ 1. I.e. the covariance is necessarily scaled identity matrix ⇒ the features are uncorrelated.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DJxzMXQlAFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides a theoretical analysis on the sample complexity of OPE with linear function approximation and assumptions on representation and distribution shift. The main results shows that realizability and feature coverage are not sufficient to guarantee a polynomial sample complexity. The paper also provides a performance guarantee for LSVI with a stronger assumption on the distribution shift. \n\nIn general, the paper provides a sound (and correct) theoretical analysis, the construction of the hard instance is new. In section 5,  I think the measure of the distribution shift in terms of the covariance matrix is also new. I believe the paper can have a significant contribution to the batch RL/offline RL community. Therefore, I recommend to accept this paper. \n\n##### Comments and clarification questions\nIn terms of clarity, the main text is clearly written, and the related work section is comprehensive.\n\nThe paper mentions that ”batch RL is not guaranteed unless stronger conditions on the distribution shift or stronger representation conditions beyond realizability”. However, the paper seems to focus on the former and does not have any analysis for the latter in the main text. For example, what is the guarantee of LSVI under closeness under Bellman update (without mild distribution shift assumption)?\n\nThe paper might benefit from giving some explanations on why low C_h (defined in assumption 3) implies mild distribution shift.  Moreover, can you elaborate more on this sentence \"we measure the distribution shift in terms of the spectrum of the feature covariance matrix of the data distribution, which is more natural than the concentrability coefficient for the case of linear function approximation\"? What is the connection between assumption 3 and the concentrability coefficient?\n\nI did not carefully check the proof in the appendix, therefore, I give myself a slightly low confidence score. \n\n**\nPost-rebuttal update: the score is increased from 7 to 8.\n**", "extra_scores": {}, "extra_text": {}}, {"review_id": "C7PVmL799wn", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThis is a theoretical paper proving an MDP exists in which there is a lower bound on the number of off-policy samples necessary to sufficiently linearly approximate the Q-functions which is exponential in the time horizon of the MDP.  In addition, they demonstrate that while this can be mitigated with samples pulled from a similar policy to the optimal one, the sample distribution must be quite similar, due to cascading geometric error.  The paper is a challenging one to read, and I can't say I followed the whole proofs, but I understand the results.\n\n### Significance\n\nThis result is quite important in understanding the feasibility of off-policy approximation.  While the proofs are on linear approximation schemes, it provides intuition into the behaviors of more modern off-policy non-linear schemes, as well.  Of course we intuitively knew off-policy approximation becomes more difficult the more dissimilar the samples are from the optimal policy, but the theoretical support of exponential sample size is very useful and meaningful.\n\n### Originality\n\nThe paper's results are new, to my experience.\n\n### Quality and Clarity\n\nThe proofs are creative and well done.  I do wish the intuitive explanations of the theorems were better organized and more fleshed out.  There is a heavy dependence on citation.  For example, \"It is well known that in order to distinguish r_1 and r_2 with probability at least 0.9, any algorithm requires <many> samples.\" fills a very key place in understanding the theorem.  I'm not familiar with this result, and without it, I don't understand a key moment of the proof.\n\n### Conclusion\n\nI think it's an important paper, and is highly relevant to the large amount of work that uses off-policy samples.  I don't think it's written very clearly, which is a shame.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows hardness results for batch reinforcement learning. Authors show that even if all value functions are linear in a given set of features and the exploration data covers all directions, evaluating any policy might require a sample size that is exponentially large in the problem horizon. This is an interesting and somewhat surprising result, and I believe it would be of interest to the wider RL community. I recommend acceptance of this paper.
Decision: Accept (Spotlight)