Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism
Authors: Paria Rashidinejad
Banghua Zhu
Cong Ma
Jiantao Jiao
Stuart Russell
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement learning theory
offline reinforcement learning
imitation learning
lower confidence bound (LCB)
minimax optimality

Abstract: Offline (or batch) reinforcement learning (RL) algorithms seek to learn an optimal policy from a fixed dataset without active data collection. Based on the composition of the offline dataset, two main methods are used: imitation learning which is suitable for expert datasets, and vanilla offline RL which often requires uniform coverage datasets. From a practical standpoint, datasets often deviate from these two extremes and the exact data composition is usually unknown. To bridge this gap, we present a new offline RL framework that smoothly interpolates between the two extremes of data composition, hence unifying imitation learning and vanilla offline RL. The new framework is centered around a weak version of the concentrability coefficient that measures the deviation of the behavior policy from the expert policy alone. Under this new framework, we ask: can one develop an algorithm that achieves a minimax optimal rate adaptive to unknown data composition? To address this question, we consider a lower confidence bound (LCB) algorithm developed based on pessimism in the face of uncertainty in offline RL. We study finite-sample properties of LCB as well as information-theoretic limits in multi-armed bandits, contextual bandits, and Markov decision processes (MDPs). Our analysis reveals surprising facts about optimality rates. In particular, in both contextual bandits and RL, LCB achieves a faster rate of $1/N$ for nearly-expert datasets compared to the usual rate of $1/\sqrt{N}$ in offline RL, where $N$ is the batch dataset sample size. In contextual bandits with at least two contexts, we prove that LCB is adaptively optimal for the entire data composition range, achieving a smooth transition from imitation learning to offline RL. We further show that LCB is almost adaptively optimal in MDPs.

Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism
Paria Rashidinejad Department of EECS
Banghua Zhu Department of EECS UC Berkeley Berkeley, CA, 94709 banghua@berkelly. edu
UC Berkeley
Berkeley, CA, 94709
paria. paria.rashi janee edu
Cong Ma
Jiantao Jiao
Stuart Russell
Department of Statistics University of Chicago
Department of EECS UC Berkeley Berkeley, CA. 94709 j iantao@berkeley, edu
Department of EECS UC Berkeley Berkeley, CA, 94709 russell@berkeley edu
Chicago, IL, 60637 congm@uchicago..dd
Abstract
Offline (or batch) reinforcement learning (RL) algorithms seek to learn an optimal policy from fixed dataset without active data collection. Based the composition the offline dataset, two main methods are used: imitation learning which is suitable for expert datasets, and vanilla offline RL which often requires uniform coverage datasets. From a practical standpoint, datasets often deviate from these extremes and the exact data composition usually unknown. To bridge this gap. we present a new offline RL framework that smoothly interpolates between the two extremes of data composition, hence unifying imitation learning and vanilla offline RL. The new framework is centered around weak version of the concentrability coefficient that measures the deviation of the behavior policy from the expert policy alone. Under this new framework, we ask: can one develop an algorithm that achieves minimax optimal rate adaptive composition? To address this question, we consider a lower confidence bound (LCB) algorithm developed based on pessimism RL. We study finite-sample properties of LCB as well as information-theoree limits multi-armed bandits, contextual bandits, and Markov decision processes (MDPs). Our analysis reveals surprising facts about optimality rates. In particular, in both contextual bandits and RL, LCB achieves a faster rate I/N for nearly- expert datasets compared to the usual rate of 1/VN in offline RL, where is the batch dataset sample size. In contextual bandits, we prove that LCB adaptively optimal for the entire data composition range, achieving a smooth transition from imitation learning offline RL. We further show that LCB is almost adaptively optimal in tabular MDPs.
unknown data
face uncertainty offline
Introduction
Reinforcement learning (RI.) algorithms have recently achieved tremendous empirical success including beating Go champions [45 46) and surpassing professionals in Atari games [30 31]. to name few. Most success stories, however, in the realm of online RL in which active data collection is necessary. This online paradigm falls short of leveraging previously-collected datasets and dealing with scenarios where online exploration is not possible [0]] To tackle these issues, offline
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

dataset composition
expert data
uniform coverage data
imitation learning
vanilla offline RL
Figure 1: Dataset composition range for offline RL problems.
(or batch) reinforcement learning [24 26 arises which the agent aims at achieving competence by exploiting a batch dataset without access to online exploration. This paradigm is useful in diverse array of application domains such as healthcare
[51 15 35 autonomous driving [57 36 and
recommendation systems 47 12 49
The key component of offline RL a pre-collected dataset from an unknown stochastic environment. Broadly speaking. there exist two types of data composition for which offline RI. algorithms have shown promising empirical and theoretical success; see Figure [ for an illustration.
Expert data. One end of the spectrum includes datasets collected by following an expert policy. For such datasets, imitation learning algorithms (e.g.. behavior cloning (40) are shown be effective in achieving a small sub-optimality w.r.t. the expert policy. Recently, Rajaraman et al. (39 showed that the behavior cloning algorithm achieves the minimal sub-optimality of 1/N in episodic Markov decision processes (MDPs), where N is the sample size in the expert dataset.
Uniform coverage data. On the other end of the spectrum lies the datasets with uniform coverage, which aim to cover all states and actions, even the states never visited or actions never taken by satisfactory policies. Most vanilla offline RL algorithms are only suited in this region and are shown to diverge-both empirically I1 [22 and theoretically 2 for narrower datasets [10] (0),, such as those collected via human demonstrations or hand-crafted policies. In this regime, a widely-adopted requirement is the bounded uniform concentrability coefficient which assumes that the ratio of the state-action occupancy density of any policy and the data distribution is bounded uniformly over all states and actions [32
9 6 52]. Another common assumption is uniformly lower bounded data distribution on all states and actions [43 M. which ensures all states and actions are visited with sufficient probabilities. Algorithms developed for this regime are demonstrated to achieve a 1/ L/VN
sub-optimality competing with the optimal policy [53 16 50
1.1 Motivating questions
Both of these two ends impose strong assumptions on the dataset: expert-driven dataset; at the other extreme, we require the dataset to cover every, even sub-optimal, actions. In practice, there are numerous scenarios where the dataset deviates from these two extremes, which has motivated new offline RL benchmark datasets with different data compositions [10] 20) With this need in mind, the first and foremost question is regarding offline RL formulations:
extreme, we hope for solely
Question (Formulation) Can we propose an offline RL framewokk that accommodates the entire data composition range?
We answer this question affirmatively by proposing interpolates between two regimes: expert data and data with uniform coverage. More specifically, we characterize the data composition in terms of the ratio between the state-action occupancy density of an optimal policy d' (x, a and that of the data distribution yuss, a), i.e., we define C* to be the smallest constant that satisfies d' (s,a)/u(s,a) C* for all S and A; see Definition T for precise characterization.
formulation for offline RL that smoothly
In words, C* can be viewed distribution induced by the optimal policy, C* = describes the expert datasets as by definition, the behavior policy is identical to the optimal policy. In contrast, when C* 1, the dataset is no longer purely expert-driven
measure of the deviation between the data distribution and the
could contain "spurious" samples states and actions that are not visited by the optimal policy. As another example, when the data distribution is lower bounded by Mmin over all states and actions, C* is upper bounded by pmin
'Our developments can accommodate arbitrary competing policies, however, we restrict ourselves to the optimal policy for of presentation.

---

Assuming finite C* is the weakest concentrability requirement [42 13 52 that is currently enjoyed only by some online algorithms such as CPI [8] C* imposes a much weaker assumption in contrast to other concentrability requirements which involve taking maximum over all policies; see [42] for a hierarchy of different concentrability definitions. We would like to immediately point out that existing works on offline RL either do not specify the dependency of sub-optimality on data coverage 55 or do not have a batch data coverage assumption that accommodates the entire data spectrum 15 [9] For instance, Yin et al. [54] requires uniformly lower bounded data distribution that traces an optimal policy, which implies that optimal actions should be included in states not visited by the optimal policy. Furthermore, this characterization of data coverage does not recover imitation learning: even if the behavior policy is exactly equal to the optimal policy, data distribution lower bound can be arbitrarily small. Further discussion of related work is presented in Appendix A.
With this formulation in mind, a natural next step is designing offline RI algorithms that can handle various data compositions, i.e., for all C* 2 1. Recently, efforts have been made toward reducing the offline dataset requirements based on a shared intuition: the agent should act conservatively and avoid states and actions less covered in the offline dataset. Based on this intuition, variety
of model-based [55] 19 56) and model-free 22 33
34 25 37
14 28 23 3 offline RL
algorithms are proposed that achieve promising empirical results. However, it is observed empirically that existing model-free ffree methods perform better when the dataset is nearly expert-driven whereas
existing model-based methods perform better when the dataset is candolly-collected [55 56).
remains unclear whether a single algorithm exists that performs well regardless of data composition an important challenge from a practical perspective [21 IO 20 More importantly, the knowledge of the dataset composition may not be available a priori to assist in selecting the right algorithm. In practice, imitation learning often succeeds with very few samples in contrast to offline RL [41]. Unifying offline RL and imitation learning via a single algorithm is thus beneficial, as it can result in tremendous sample savings, in case the dataset has good coverage on expert policy. This motivates the second question on the algorithm design:
Question (Adaptive algorithm design) Can we design algorithms that can achieve minimal sub- optimality when facing different dataset compositions (i.e., different C*)? Furthermore, can this be achieved in an adaptive manner, i.e., without knowing C* beforehand?
To answer the second question, we analyze a pessimistic variant of a value-based method in which we first form lower confidence bound (LCB) for the value function of policy using the batch data and then seek to find a policy that maximizes the LCB. The idea of pessimism has appeared in the literature of risk minimization turns out that such a simple algorithm- fully agnostic to the data
48 8- A similar algorithm design has recently appeared in [17]. It almost optimal performance in multi-armed bandits and MDPs, and optimally solves the offline learning problem in contextual bandits.
Results summary. Figure 2 summarizes theoretical findings. For multi- armed bandits, we prove that LCB achieves / /C/N sub-optimality for any C* > 1. Yet, we prove lower bounds showing that LCB cannot be adaptively optimal for any C* > the knowledge of C* is not available. For contextual bandits with at least two contexts, we prove that LCB enjoys a rate of
V(C* - 1)/N + I/N, which translates to a fast rate of I/N when C* xe akin to the performance of behavioral cloning and smoothly transitions from 1/N to 1/VN as C* increases. This rate matches the information theoretic limit, showing adaptive optimality of LCB in contextual bandits. Establishing the C* - dependency requires a novel analysis based on a careful policy sub-optimality decomposition and directly analyzing the probability of taking wrong actions. For MDPs, we similarly show that LCB achieves fast rate of 1/N for C* R 1 and rate of /C* /N for larger values of C*.
We conjecture that LCB upper bound also has the form v 1)/N. We verify this conjecture in a simple example and show that establishing the C* - dependency in MDPs requires a delicate analysis that accounts for the value gap between optimal and sub-optimal actions.
2 Background and problem formulation
Notation. The probability simplex over set X' is denoted by A(X). We write x S y when there exists > 0 such that x S ey and write x x y if e,, 62 > 0 exist such that ei |ar
S
[y]] S c2fo//. We
write x V y to denote the supremum of x and y. We write f(x) = O(o(z)) if M
0, 20 exist such
3

---

MAB
CB with at least two contexts
MDP
s0bb albeppiimkk
1+0(1)
11+ +
1+0
+( 1 (1(1)
LCB upper bound
Information-thcorciic lower bound
LCB conjecture
Figure 2: The sub-optimality upper bounds and cefformmtiiontthoorettt lower bounds for the LCB-based algorithms. In all setting, C** unknown the algorithm.
that [f()) I Mg(x) for all 2 To. We use Ō(-) be the big-O notation ignoring logarithmic factors. We write f(z)= = (g((x) M > 0, Fy exist such that [f(x) Z Mg(x) for all x 2 To-
2.1 Markov decision processes
An infinite-horizon discounted MDP is described by tuple M = AS 7). where S is finite state space with S [S), A a finite action space, P: x A (SS) is a transition matrix, R S A + ( 1)) encodes family of reward distributions with r 8 A + [0, 1] as the expected reward function, p + (S) is the initial distribution, and 7 E [0,1) is a discount factor.
A stationary deterministic policy S + AA is function that maps state to an action. Correspond- ingly, the (normalized) state-action discounted occupancy measure d= :S x A r> [0, is defined as d' (s.a) a) (1 7) E. 7 Pr(s:
G4 a: T) for all E S, E A, where (st
0g x)
denotes the probability of 8, = 8, 0g = a after executing policy π and starting from 5o ~ p(-).
The value function V S + IR of the policy is defined as (*))) == - 7'1, 30 = 8,
(s;) for all 0] for S. The quality function (or Q-function) Q" S A R of policy
is defined analogously (s = EI 7' So = 8.00 ag a, a = T(s,) for all 2 1.. is
convenient to define a scalar summary of the performance of policy π as J(T) = Ex-pl [V (s)]
is well known (38] that stationary deterministic policy x= exists that simultancously maximizes (=(s) for all s E S, and hence maximizing the expected value (TT). We use shorthands V* == V* and Q* = Q" to denote the optimal value function and Q-function.
2.2 Offliin data and offline RL
The current paper focuses offline RL, where the agent cannot interact with the MDP and instead is given a batch dataset DD consisting of tuples (s, a, r, 8'), where r ~ R(- 8, a) and s' ~ P(- 88, a). For simplicity,
data distribution μ x A, which is unknown to the agent We denote by N N(s, a) 2 0 the number of times (s, a) is observed in D and by N = the number of samples. The goal of offline RL is to find a policy # based on D- so as to minimize the expected sub-optimality with respect to the optimal policy x², i.., ED [xx*) J [.)], where the expectation is taken with respect to the randomness in the dataset.
assume (s, a) pairs are generated i..d. according
2.3 Dataset coverage assumption
Definition (Single policy concentrability) Given a policy n, define C be the smallest constant that satisfies d' (s, a)/p(s,a) < C" for all E S and E A.
In words, C characterizes the distribution shift between the occupancy measure induced by and data distribution μ.. For stationary deterministic optimal policy, C* C" is the "best"
concentrability coefficient definition 42 13 2 52 which is often much smaller than the widely-used uniform concentrability coefficient C = max, C which takes the maximum over all policies. A
small C implies that data distribution covers (s, a) pairs visited by policy म, whereas a small C
The i..dd. assumption is motivated by the data randomization performed in experience replay B1

---

requires the coverage of (s, a) visited by all policies. A similar notion of concentratbility coefficient in 2 norm instead of &o. norm has appeared the literature of off off-policy evaluation 27 29
3 A warm-up: LCB in multi-armed bandits
We begin with the simplest example of an MDP, the multi-armed bandit (MAB) model, where S S 1 and y 0. For MABs, the offline dataset simplifies to D ((a,r,)) where a; μ(-) and r; ~ R(a:). Competing with an optimal arm a", the data coverage assumption becomes 1/u(a*) v C The goal of offline learning in MAB is select an arm à that minimizes the expected sub-optimality Ep Ep[J(=*) - J( = Ep(r(a") - r(ā)], where r(a) is the expected reward of arm a.
3.1 Why does the best empirical arm fail?
natural choice for solving the offline learning problem is to select the arm with the highest empirical average reward, i.e., â == arg max, f(a). Though intuitive, the empirical best arm is quite sensitive to the arms with a small N (a): a less-explored sub-optimal arm might have a high empirical mean just by chance (due to large variance) and overwhelm the true optimal arm. The following proposition formalizes this intuition; see Appendix 1 for a proof.
Proposition 1 (Failure of the best empirical arm) For any Forany < 0.3, N 2 500, there exists a bandit problem with two arms such that for â arg max, M(a), one has Ep (r(a*) r(a)] 2
3.2 LCB: The benefit of pessimism
Given the failure of best empirical arm, one soon realizes that it is not sensible to put every arm on an equal footing: one should be pessimistic about the true mean reward the arms pulled less often. Strategically, pessimism can be deployed by first constructing a penalty function b(a) that shrinks as (a) increases and then returning á E arg max, f(a) b(a). When b(a) captures a confidence level about the empirical reward, f(a) - b(a) can be viewed as lower confidence bound (LCB) on the true mean reward r(a). Algorithm I shows one instance of the LCB, in which the penalty function originates from Hoeffding's inequality. The following theorem captures the performance of this algorithm in the MAB setting. The proof can be found in Appendix B.2.
Theorem (LCB sub-optimality, MAB) For a MAB, assume that 1/m(a") < C* for some C** 2 1. with 1/N obeys
Provided that N 2 SC* log N, arm à returned by Algorithm 1
1og(2NN
Epir(a") r(a)] S min 1,
(1)
N
Applying the above guarantee to the failure instance given in Proposition 1 one sees that LCB secures a out-optimality of applies larger penalties to the arms with small number of samples, which helps to rule them out.
which beats the best empirical arm. This is because the LCB approach
3.3 Is LCB optimal for solving offline multi-armed bandits?
Given the performance bound (I) it is natural to ask whether LCB is optimal for solving offline MAB problems. To address this question, we resort the usual minimax criterion. Define the following MAB family: MAB(C*) {(u, R) 11/u(a*) < C*), which includes all possible pairs of μı and R such that the data coverage assumption 1/u(a*) S C* holds. We define the worst-case risk of any estimator à to be R)EMABCC) E ED(r(a*) -r(())) An estimator à is measureable function of the dataset DD collected under the MAB instance and R. The following theorem shows that LCB is optimal up to a logarithmic factor when C* 2; see Appendix B.3 for the proof.
Theorem 2 (Infrrmation-theorrei limit, MAB) For C* 2, one has
inf sup (p.R))MAB(C*)
Eplr(a") - -(a)] min
1,
C"
N
5

---

For C* E (1, one has
ED(r(a") r())) 2 exp (-(2-C*) Cr) (c--1) N)..
inf (H.R))MAA((C)
sup
3.4 Imitation learning in bandit: the most played arm achieves a better rate
Theorem reveals that when C* 2 2, the best possible expected sub-optimality is VC-/N, which is achieved by LCB. On the other hand, in the case of C* E (1, which corresponds to juaa) > 1/2, we can simply use imitation learning to improve the rate by picking the most frequently selected arm in the dataset, i.e., à arg max, N (a). The performance guarantee of the most played arm is stated in the following proposition. The proof is deferred to Appendix B.4.
Proposition 2 (Sub-optimality of the most played arm) Assume that 1/p(a") S C for some C* E [1, 2). For à = arg max, Na), we have
Ed(r(a*) r(ā) S exp (-N-KL KL-
(Bern (-N-KL(Bern (t) Bern (t)))
When C* E (1,2), the most played arm achieves an exponential rate N, whereas the upper bound for LCB is only I/vN. On the other hand, the most played arm algorithm completely fails when C* > 2, while LCB secures the rate 1/vN. N. In terms of C* dependence, the KL. divergence above evaluates to log(C* /2) + log(1/(C* - 1))/2. As C - the rate increases to the order of 1/(C* 1)",, matching the lower bound in Theorem
3.5 Non-adaptivity LCB
One may wonder whether LCB can achieve optimal rate under both cases of C (1.2) and C* > 2. Unfortunately, we show in the following theorem that regardless of the parameter in Algorithm LCB cannot be optimally adaptive in both regimes. The proof is deferred Appendix B.5.
Theorem (Non-adaptivity of LCB, MAB) Let C* 1.5. There exists a two-armed bandit in- stance (No, Ra) E MAB(C**) such that Algorithm with = /log(2)AA/66)) satisfies
Ep(r(a") r(a)] 2 min
(32L).
N VN
On the other hand, when C = there exists (M1, R1)= E MAA(CC*) such that
Ed(r(a*) r(a)) 2 min (I.
Intuitively, a larger L means that we put greater weight on penalty instead of empirical average. As L + oo, the LCB algorithm recovers the most played arm algorithm; while as L - 0, the LCB algorithm recovers the best empirical arm algorithm. When C* (1,2), achieve an exponential rate similar to the most played arm (Theorem 2) we need to select such that L ス No for a >> 0. However, under this choice of L, the algorithm fails to achieve L/VN N rate when C* 2 6, which can be achieved by setting 1/N (and thus log(2)A[N)) based on Theorem [ Hence, is impossible for LCB to achieve optimal rate in both C* E (1, (1 and C* > 2 regimes simultaneously.
4 LCB in contextual bandits
We take the analysis one step further by studying offline learning in contextual bandits (CBs). CB a special case of MDP described in Section 2.1 with 7 0. In CB setting, the batch dataset and the coverage assumption simplifies to max, p(s)/u(s, x (s)) C
is D {(si, 0g r:)) = W=
The offline learning objective in CB is to find a policy मे based on D that minimizes the expected sub-optimality EE [T(") J [+)] ED [r(s, T' (s)) r(s, (s))).
4.1 LCB algorithm and its performance guarantee
The pessimism principle introduced for MAB can naturally extended to CB by subtracting a penalty function b(s, a) from the empirical rewards f(x, a) and returning #(s) arg max,7 f(s, (a) b a) for every state s. The following theorem establishes an upper bound on the expected sub-optimality of the policy returned by Algorithm see Appendix C. for complete proof.

---

Algorithm LCB for bandits and contextual bandits
1: Inputs: Batch dataset
{(3,, as (;)];=> and confidence level
2: for S, A do
3: if (s, = then Set f(s, + +.
1 4: else Set F(s, a) t N(s.a) E r 1[(;, a.) = (s,a))
5: Compute the penalty b(s, a) = 2000 Log (4/6))
NaaaavI
6: Return: fs) arg max, f(s, b(s, a) for each & S.
Theorem (LCB sub-optimality, CB) For CB with some
assume max, p(s)//(s, z
C* for some C* 2 1. The policy it returned by Algorithm 1 with 8 = 1/N obeys
ED[J(T")- - [(+) S min (1.0(
S(C N
2))
The sub-optimality in Theorem 4 consists of two terms. The first term has the usual statistical estimation rate of 1/ /VN. The second term is due to missing mass, which captures the suboptimality incurred in states for which an optimal arm is never observed in the dataset. Importantly, the dependency of the first term data composition is C* 1. When C* is close one, LCB enjoys a faster rate of 1/N, reminiscent of the behavioral cloning rate. Furthermore, the convergence rate smoothly transitions from 1/N to 1/VN as C' increases.
4.2 Optimality of LCB for solving offline contextual bandits
We now establish an information -ieemattio--thorettic lower bound for the contextual bandit setup de- scribed above. Define the following family of CB problems CB(C*) == {(p, μu, R) max, (/////(sx(((( < C*). Let & S + A be arbitrary estimator of the best arm xt for any state 8, which a measurable function of the data. For the worst-case risk of defined as RECB))) ED []][[(r [(x*) J(+)], we have the following minimax lower bound:
Theorem (Information-
limit, CB) Assume that S 2 2. For any C* 2 1, one has
( J()) Z min 1, V s(a +
inf # (P.p,))ECB(C*)
sup
The proof is provided in Appendix C.2. Comparing with Theorem 4 one sees that LCB enjoys regardless of C* This is in stark contrast to the MAB case.
near-optimal rate CB with
On a closer inspection, the C* E [1,2) regime, there is a clear separation between the information- theoretic difficulty of offline learning in MAB, which has an exponential rate in N, and CB with at least 2 states, which has a 1/N rate. The reason behind this separation is the missing mass rate when S > 2. Informally, when there is only one state, the probability that an optimal action never observed in the dataset decays exponentially. On the other hand, when there are more than one states, the probability that an optimal action is never observed in least one state has a 1/N rate.
Assume hypothetically that we know C** E (1,2). Under this circumstance, one might wonder whether simply picking the most played arm in every state achieves fast rate, analogous MAB. Strikingly, the answer is negative as the following proposition shows that the most played arm fails to achieve vanishing rate when C* E (1,2). The proof of this theorem is deferred Appendix C.3.
Proposition 3 (Failure of the most played arm, CB) For any C* E (1, 2), there exists a contextual bandit problem (p, R) CB(C") such that for the policy i(s) = arg max, N(s
Jim [=( [ 2 C* 1.
N No000
LCB in Markov decision processes
5.1 Offline value iteration with LCB
Now we are ready to instantiate the LCB principle to the full-fledged MDP case. Our algorithm design builds upon the classic value iteration algorithm. As we do not have access to the true expected
7

---

Algorithm 2 Offline value iteration with LCB (VI-LCB)
1: Inputs: Batch dataset D, discount factor y, and confidence level d.
2: Set T log N L = 2000 log(2(T + 1)S Al))) Vmax (1 (1-7)
3: Split D into T 1 sets D. = {ss, 0;, Fas s for t {0, (0.,,,.,, T).
4: Set (s. = - 1 [[(s; a:) = (s, } based on dataset Dr for t E {0, 10.......Ty T).
5: Initialize Qo(s. 0) 0, Vo(s) and set (o(s) = arg max, mo(s, a), for a E A and s E S.
6: for for.=
7: for (8, AS) do
8: if (,, = then Set (r, a) 0 and (- 8, a) to be random probability vector.
9: else Set P' 8, to be empirical transitions and rx(8, a) be empirical rewards.
Compute penalty be(s, a) Vmaxx V (a.aaviii
11:
Set Qr(s, a) < (ts, - bx(8, + +7 E. P'(8' v.
12:
Compute 1.mid <- max, Qi a) and o. mii((s) max, Qe(s,a).
for E S do
14:
if Vi < 1 (s) then Va(a) ( and (+()) + Rt-1(6)
15:
else Vi(() 4- Villd 88 and (8) f (s).
16:
Return म == TT.
rewards r and transitions P. we replace them with the empirical counterparts and P. Furthermore, mimicking the LCB algorithmic design for MABs and CBs, we subtract penalty function b(s, a) from the update as the finishing touch, which yields the value iteration algorithm with LCB:
()) < f(s, a) b(s + Σ P(s (8))), for all (s,
(4)
((s) + max ass.a), for all s.
(5)
Algorithm 2 Jses the update rule as its key component as well as few other tricks:
Data splitting, Instead of using the full dataset D to form f and P, Algorithm 2 splits D and uses
different samples in each update (4). This procedure is not needed in practice, however, it alleviates the dependency issues in the analysis, which removes an extra factor of S in the sample complexity.
Monotonic update. Agorithm@uupacee
value function V and policy only when the correspond- ing value estimate is larger than that in the previous iteration. The key benefit of the monotonic update is to shave 1/(1- - 7) factor in the sample complexity; see [43] for further discussions.
Now we turn to the performance guarantee of VI-LCB, whose proof is given in Appendix D.6.
Theorem (LCB sub-optimality, MDP) For a MDP, assume that max,, d' (s..)//((s,d C*. Then, for all C* 2 policy ă returned by Algorithm 2 with d = 1/N achieves
Ed [J(=²) J(+)] S min (12 Ō ( sC [log(N) In addition, if < C* < 1+ 200(1-7]N' we have a tighter performance upper bound
(6)
ED (J(²)) J(+)] $ min ( (m=))
The upper bound shows that for all C* 2 1, we can guarantee a rate of Ō( Õ(VSC' ((11((1))))) which is similar to the rate of CB when the C* 1 + R(1) by taking y 0. When C' C= C0=1+((/N), we have a rate 5/(( - 7 N)), which also recovers the result in the CB case. However, in the regime of C* E [1 + (11/N), + ((1)], while CB enjoys /S(C** 1)/N rate, we fail to give the same dependence on C* MDP; see Section for further discussion on sub-optimality in this regime.
5.2 Information-theww lower bound for offline RL in MDPs
To capture the statistical limits of offline learning in MDPs, as before we define the following family d'(a))
of instances MDP(C") = {p. P. R) max,,a p(s.a) < C*.. We have the following minimax lower bound for offline policy learning in MDPs, with the proof deferred to Appendix D.7.
8

---

Theorem 7 (Information- limit, MDP) For any C* 2 1, 2 0.5, one has
inf sup [p[J(=') [ E min (o.....R)EMDP(C))
S [Iー +
S(C--1) [1-TPN
Imitation learning and offline learning. Similar to the CB lower bound, the statistical limit in Theorem Tinvolves two terms. The first term captures the imitation learning regime under which fast rate 1/N is expected, while the second term deals with the large C* regime with a rate 1/VN. More interestingly, the dependence C* appears to be C* 1, which is different from the performance We will comment more on this in the coming section.
upper bound of VI-LCB in Theorem 6
Dependence on the effective horizon. Comparing the upper bound in Theorem 6 with the lower bound in Theorem 7 one sees that the sample complexity of VI-LCB is loose by an extra 1/(1 - 7)² factor in sample complexity. We believe that this extra factor can be shaved by replacing the Hoeffding- based penalty to a Bernstein- one and using variance reduction similar to [43]
Proof techniques and conjecture
To prove the crude rate of /C+/N for any C* 2 in all three MAB, CB, and MDP settings, it sufficient to bound the sub-optimality by an expectation over penalty followed by the coverage assumption. Since the penalty is proportional to 1/VN,, this technique only yields a 1/v/N rate.
The - -1/ + S/N rate in CB. We carefully decompose the sub-optimality and charac- terize the probability of choosing sub-optimal arms to prove the tighter bound in CB, which closes the gap between upper and lower bounds. We achieve this goal by directly analyzing the policy sub-optimality via gradual decomposition of the sub-optimality of illustrated in Figure 3
(s)) =0 - Ti
Ep[J(=*) - J(A)]
1(89) + T2
(())
pls) < 20 + T3 N
1(8)
uuss, (s)) < 107((s) + T4
p(s)
20 N
(x), 2 107(()) -> Ts
Figure 3: Decomposition of the sub-optimality of the policy á returned by Algorithm
In the first level of decomposition, certain state s. When ((s,, x (s)) = 0, there is absolutely no basis for the LCB approach to figure out the correct action x (s). Fortunately, this type of error, incurred by missing mass, can be bounded by Ti S S.S.
separate the error based on whether N(s, n (s)) is zero for
The second level of decomposition hinges on the following clean/good event: = {Vs, a: |n(s, a) f(s, a)] < b(s, a)}. In words, the event & captures the scenario in which the penalty function provides valid confidence bounds for every state-action pair. Standard concentration arguments tell us that & takes place with high probability, i.e., the term T2 in the figure is no larger than 8. By setting 5 small, say 1/N, we are allowed to concentrate on the case when È holds.
The third level of decomposition relies on the observation that states with small weights (i.e., p(s) is small) have negligible effects on the sub-optimality J(x*) J(t). More specifically, the aggregated contribution T3 from the states with p(s) S C*L is upper bounded by T3 S. N
C*SL This allows us to
N
focus on the states with large weights. We record an immediate consequence of large p(s) and the data coverage assumption, that is su(s, π (s)) Z p(s)/C* x L/N..
Now comes the most important part of the error decomposition, which is not present in the MAB analysis. We decompose the error based on whether the optimal action has a higher data probability u(s, n (s)) than the total probability of sub-optimal actions (i(s) Eapar(o M(s, a). In particular,

---

when j (s)) < 1s), we can repeat the analysis of MAB and show that T4 2 / -1)
N
Here, the appearance of C* 1, as opposed to C* is due to the restriction u(s, 'T (s)) < 10pr(s).
One can verify that pls, n- (s)) < (0]((s) together with the data coverage assumption ensures that Exsp(s)220 L/N,"((,.""( (0pp(s))))))))))))))))))))))>>)) p(s) S C* 1. On the other hand, when yu(s, ''' (s)) 2 10p(s))
ie., when the optimal action is more likely to be seen in the dataset, the penalty function b(s, x xT()s)
associated with the optimal action would be much smaller than those of the sub-optimal actions. Thanks to the LCB approach, the optimal action will be chosen with high probability, i.e., Ts X 1/N10.
C* dependency in MDPs. Ignoring the dependency on 1/(1-7), by comparing Theorems and 7
one realizes that VI-LCB is optimal both when C* 2 1 + ((1) and C* S 1 1+ (1/N)) However, in the middle region, the upper and lower bounds differ in their dependency on C*, We conjecture that VI-LCB is optimal even this regime and the current gap is an artifact of our analysis.
Conjecture (Adaptive optimality of LCB) The LCB approach, together with value iteration is adaptively optimal for solving offline MDPs for all ranges of C
Technical hurdle. turns out that closing the gap in MDPs is significantly more challenging due to error propagation. Naively applying the decomposition in the CB case fails to achieve the C* 1
dependence in the regime C*+ E [1 + (111NN) + O()). O(1). Major difficulties arise in controlling case (i), where pls, xt (s)) > Eatr( (o) p(s,a). a). Recall that VI-LCB picks the right action if
L (T + (1ls (1)) > (1( V mi(s,a) tyP'
re(8, (s))
for all a (s). The presence of the previous values V drastically changes the picture: even we know that (s, x² (s)) >> ms(s, a), the current analysis does not guarantee the above inequality. is likely that the value gap g(x) == Q* (s)) - (s,s, a) affects whether VI-LCB chooses the optimal action. How to study the interplay between the gap and the policy chosen by VI-LCB forms the main obstacle to obtaining tight performance guarantees when C* E [1 + ((1/N), 1 + ((1)].
confirmation from an episodic MDP. In Appendix E.6, we present an episodic example to demonstrate that (1) episodic variant of VI-LCB achieves the optimal dependency on C* and hence closes the gap between upper and lower bounds, and (2) a tight analysis of the sub-optimality is rather intricate and depends As a preview, our example is an episodic MDP with H = 3. To tackle case (i) above, we decompose the error based on whether g(8) is small. If g(s) is small for state 8, the contribution to the sub- optimality is well controlled. Otherwise, we manage to show that VI-LCB selects the right action with high probability. What is more interesting and surprising that the right threshold for value gap given by v(C* 1/C*+1)/AA 1)/N. Ultimately, this allows us achieve the optimal dependency on C**
Q* delicate decomposition based on the gap Q" x (s)) Q" (s. a).
7 Discussion
We propose new batch RL framework based on the single policy concentrability coefficient C* that smoothly interpolates the two extremes of data composition encountered in practice, namely the expert data and uniform coverage data. Under this new framework, we pursue the statistically optimal algorithms that can even be implemented without the knowledge of the data composition. More specifically, focusing on the lower confidence bound (LCB) approach inspired by the principle of pessimism, we find that LCB is adaptively minimax optimal for addressing the offline learning problems in most settings. Under the new framework, there exist numerous avenues for future study. One interesting direction is to provide a tighter bound for LCB in MDP for the regime where a significant fraction of the data comes from the optimal policy (Conjecture[], [ Furthermore, it would be important to extend this work to function approximation setting. We expect to see our characterization of offline RL via single-policy concentrability to be extended to the function approximation setting and used in the development of new offline RL algorithms that only require partial coverage. Another interesting direction for future work is to analyze whether alternative conservative methods such as value regularization can achieve adaptivity and/or minimax optimality.
10

---

Acknowledgements
The authors are grateful Nan Jiang, Aviral Kumar. Yao Liu, and Zhaoran Wang for helpful discussions and suggestions. PR was partially supported by the Open Philanthropy Foundation and the Leverhulme Trust. BZ and JJ were partially supported by NSF Grants IIS- 1901252, CCF-1909499 and DMS-2023505.
References
[1] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in Markov decision processes. Conference on Learning Theory, pages 64 66. PMLR, 2020.
[3] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. International Conference on Machine Learning pages 104-114. PMLR, 2020.
[4] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint arXiv:/604. 660_07336, 2016.
[5] Jacob Buckman, Carles Gelada, and Marc G Bellemare. The importance of pessimism in fixed-dataset policy optimization. arXiv preprint arXiv:2009.06799, 2020.
[6] Jinglin Chen and Nan Jiang. Information-theoreee theoretic considerations in batch reinforcement learning. arXiv preprint arXiv: 00360, 2019.
[7] Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. good representation sufficient for sample efficient reinforcement learning? In International Conference Learning Representations, 2020.
[8] John Duchi and Hongseok Namkoong. Variance-based regularization with convex objectives. The Journal of Machine Learning Research, 20(1):2450-255 2504, 2019.
[9] Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for ap- proximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
[10] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4RL: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.0722 07219, 2020.
[11] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pages 2052-2062. PMLR, 2019.
[12] Florent Garcin, Boi Faltings, Olivier Donatsch, Ayar Alazzawi, Christophe Bruttin, and Amr Huber. Offline and online evaluation of news recommender systems at swissinfo.ch. In Proceedings of the 8th ACM Conference Recommender systems, pages 169-176, 2014.
[13] Matthieu Geist, Bilal Piot, and Olivier Pietquin. Is the Bellman residual bad proxy? In Advances in Neural Information Processing Systems, pages 3205-3214, 2017.
[14] Seyed Kamyar Seyed Ghasemipour, Dale Schuurmans, and Shixiang Shane Gu. EMaQ: Expected-max Q-learning operator for simple yet effective offline and online RL. arXiv preprint arXiv:2007. 1091, 2020.
[15] Omer Gottesman, Fredrik Johansson, Matthieu Komorowski, Aldo Faisal, David Sontag, Finale Doshi- Velez, and Leo Anthony Celi. Guidelines for reinforcement learning in healthcare. Nature medicine, 25(1):16-18, 2019.

---

[16] Botao Hao, Yaqi Duan, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Sparse fea- ture selection makes batch reinforcement learning more sample efficient. arXiv preprint arXiv:2011 M.Ki::0011000019 1.04019, 2020.
[17] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? arXiv preprint Xii:20002.1508.. 2020.
[18] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2, pages 267-274, 2002.
[19] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. MOReL::
Model-based offline reinforcement learning. arXiv preprint (rXiv:200550555// 2020.
[20] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Sara Beery, et al. WILDS: A benchmark of in-the-wild distribution shifts. arXiv preprint arXiv:2012.07421, 2020.
[21]
Aviral Kumar and Sergey Levine. Offline reinforcemeett learning: From algorithms to practi- cal challenges. https://sitee secitess.gooll htw.o//eeaaooeee//oooaoaoootooaa neurips2000 home 2020.
[22] Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off aff-policy Q-learning via bootstrapping error reduction. arXiv preprint /906v:/906.000 2019.
[23] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for offline reinforcement learning. arXiv preprint arXiv:2006. 00w,2006.00479, 2020.
[24] Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
[25] Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International Conference on Machine Learning, pages 3652-3661. PMLR, 2019.
[26] 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.
[27] Lihong Li. Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In Artificial Intelligence and Statistics, pages 608-616. PMLR, 2015.
[28] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202, 2020.
[29] Cong Ma, Banghua Zhu, Jiantao Jiao, and Martin Wainwright. Minimax off-policy evaluation for multi-armed bandits. arXiv preprint arXiv:2101.0778) 2021.
[30] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint 13Xiv:1312.5602, 2013.
[31] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning. nature, 518(7540):529-55 -333 2015.
[32] Rémi Munos. Performance bounds in l norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-56) 2007.
[33] Ofir Nachum and Bo Dai. Reinforcement learning via Fenkhel-Rockafellar duality. arXiv preprint orXiv:2001.01860 2020.
[34] Kimia Nadjahi, Romain Laroche, and Rémi Tachet des Combes. Safe policy improvement with soft baseline bootstrapping. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 53-68. Springer, 2019.
12

---

[35] Xinkun Nie, Emma Brunskill, and Stefan Wager. Learning when-to-treat policies. Journal of the American Statistical Association, pages 1-18, 2020.
[36] Yunpeng Pan, Ching-An Cheng, Kamil Saigol, Keuntaek Lee, Xinyan Yan, Evangelos Theodorou, and Byron Boots. Agile autonomous driving using end-to-end deep imitation learning. arXiv preprini arXiv:/709.077720 2017.
[37] Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. wdvantage-weighted regression: Simple and scalable off-policy reinforcement learning. arXiv preprint arXiv:1910.00177 2019.
[38] Martin L Puterman. Markov decision processes. Handbooks in operations research and management science, 2:331 4344, 1990.
[39] Nived Rajaraman, Lin F Yang, Jiantao Jiao, and Kannan Ramachandran. Toward the fundamen- tal limits of imitation learning. arXiv preprint wwXiv:209.059990 2020.
[40] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668. 2010.
[41] Tim Salimans and Richard Chen. Learning Montezuma's 's revenge from a single demonstration. arXiv preprint arXiv: 2018.
[42] Bruno Scherrer. Approximate policy iteration schemes: A comparison. International Conference Machine Learning, pages 1314-1322, 2014.
[43] Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving discounted Markov decision process with generative model. arXiv preprint arXiv: 1806. 01492, 2018
[44] Noah Y Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Neunert, Thomas Lampe, Roland Hafner, and Martin Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. arXiv preprint arXiv:2002.08336, 2020.
[45] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of Go with deep neural networks and tree search. nature, 529(7587):484-48) 2016.
[46] David Silver, Julian Schritwiesser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go without human knowledge. nature, 550(7676):354 359, 2017.
[47] Alex Strehl, John Langford, Sham Kakade, and Lihong Li. Learning from logged implicit exploration data. arXiv preprint arXiv: 1003.0100 2010.
[48] Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference on Machine Learning, pages 814-823. PMLR, 2015.
[49] Philip S Thomas, Georgios Theocharous, Mohammad Ghavamzadeh, Ishan Durugkar, and Emma Brunskill. Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing. In AAAI, pages 4740-4745, 2017.
[50] Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint arXiv:2102.00998), 2021.
[51] Lu Wang, Wei Zhang, Xiaofeng He, and Hongyuan Zha. Supervised reinforcement learning with recurrent neural network for dynamic treatment recommendation. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2447-2456, 2018
13

---

[52] Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. arXiv preprint arXiv:2008. 04990, 2020.
[53] Ming Yin, Bai, and Yu-Xiang Wang. Near optimal provable uniform convergence in off-policy evaluation for reinforcement learning. arXiv preprint arXiv:2007.03760) 2020,
[54] Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01749 2021.
[55] Tianhe Yu. Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPO: Model-based offline policy optimization. arXiv preprint arXiv:2005.13239 2020.
[56) Tianhe Yu, Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. COMBO: Conservative offline model-based policy optimization. arXiv preprint arXiv:2102.08363 2021.
[57] Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A survey of au- tonomous driving: Common practices and emerging technologies. IEEE Access, 8:58443-58469, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the pa- per's contributions and scope? [Yes] In the abstract, we describe our contributions on proposing new offline RL framework and analyzing the adaptive optimality of pessimism under this framework. In the introduction, we discuss these contributions in more detail, compare them with related work, and give a summary Figure on our theoretical findings.
(b) Did you describe the limitations of your work? [Yes] We discuss our analysis limitation in proving adaptive optimality of LCB in MDP and provide extensive discussion on our conjecture in Section 6 In Section 5.2 we also point out that Algorithm 2 does not achieve optimal dependency in effective horizon and discuss possible methods to address this limitation. Furthermore, as explained in Section 7 this work is limited to the tabular setting and analyzes adaptive optimality of one conservative algorithm developed based on the pessimism principle.
(c) Did you discuss any potential negative societal impacts of your work? [No] The frame- work, algorithm, and theoretical analysis presented in this paper are general-purpose and can help RL algorithms utilize previously-collecte datasets more effectively. We do not foresee any direct negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have read the ethics review guidelines and our paper conforms to them.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions layed out in theorem statements.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are presented in the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [N/A] We do not include any experiments.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
14

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] Our work does not use any assets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not use crowdsourcing or conduct research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "uYfP1GlreL", "reviewer": "Reviewer_M9C5", "summary": "This work presents a simple algorithm for offline reinforcement learning based on optimizing the sum of lower confidence bounds of rewards for each transition (where the confidence bound is constricted using the offline dataset of transitions).  Theoretical bounds are given on the suboptimality of the resulting policy, based on the quantity $C^*$, which bounds the proportion of non-optimal transitions in the dataset.  Conditional on there being a finite ratio of non-optimal to optimal actions in each state, the presented algorithm has good performance in both the \"expert data\" case, in which the behavioral policy that generated the data is close to optimal, and the \"uniform coverage\" case, in which the behavioral policy covers all possible transitions.\n", "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": "Overall, the paper is clearly written, and the problem is important.  I did not carefully check the proofs, but clear intuitions are provided for the results.  The paper does a good job of focusing on the important details, and of expressing why the results are significant.\n\nMy main concern is with the novelty of the results; the following paragraph on p.3 is very worrying:\n\n> A similar algorithm design has recently appeared in [16]. It turns out that such a simple algorithm—fully agnostic to the data composition—achieves almost optimal performance in multi-armed bandits and MDPs, and optimally solves the offline learning problem in contextual bandits.\n\nThis sounds like more or less exactly the results of the current paper.  Could the authors comment on the differences between [16] and this work?\n\nI am going to rate the paper lower than I otherwise would in light of this question about novelty, but I am willing to increase my rating if the novelty question is addressed to my satisfaction.\n\n#### Minor comments:\n\n* p.2: \"Assuming a finite $C^*$ is the weakest concentrability requirement [39, 12, 48] that is currently enjoyed only by some online algorithms such as CPI [17]\": It's not clear what this means.\n\n* p.6 L227: The subscripts on the expectation operator seem inconsistent; $\\mathcal{D}$ is a random variable, and $\\rho$ is a distribution, so what do these signify?\n\n* p.7 L248-255: These paragraphs are very helpful and give exactly the right amount of detail.\n\n* alg.2: Are rewards assumed to have a maximum magnitude of 1 here?  I can't make sense of $V_{max} = (1-\\gamma)^{-1}$ otherwise.\n\n* p.5: Should the inequality in equation (3) be $\\lesssim$?\n\n* p.7: Similarly, should the inequality in prop.3 actually be $\\gtrsim$?\n\n* p.9 L323: $a$ is free in the definition of $g(s)$; what is it meant to bind to?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have done a good job of specifying the technical limitations of their work.  I do not see any societal impacts that require further comment.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "l66yyrNpsKe", "reviewer": "Reviewer_ivrh", "summary": "This is a strong paper that is well-motivated and well-written. I enjoy reading the paper, thinking about the questions and learning the new results.\n\nContribution on problem formulation: The paper provides a new offline RL framework that accommodates the entire data composition range, smoothly interpolating between two regimes: expert data and data with uniform coverage. \n\nContribution on algorithm design and the upper bounds: The paper provides a lower-confidence-bound algorithm that achieves almost optimal performance in multi-armed bandits and MDPs, and optimally solves the offline learning problem in contextual bandits. It is interesting to see that in all the three settings, LCB achieves a faster rate of 1/N for nearly-expert datasets compared to the usual rate of 1/\\sqrt{N} in offline RL.\n\nContribution on the lower bounds: The paper provides information-theoretical lower bounds to capture the fundamental hardness for this new offline RL framework. The paper also has interesting discussion on whether the knowledge of C* is necessary to design optimal algorithm.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is really well-written. The authors think about the questions throughly and do a very complete study. I particularly like the fact that the proposed LCB algorithm is very simple and intuitive. I think the paper is self-contained and addresses its two proposed questions very well. \n\nThe paper make contributions in both the problem formulation and a bunch of new theoretical claims (some of them are insightful). On the other hand, it is not clear whether the existing theoretical claims have significant technical challenges that require very original methodology. If there are, it may be good to add some high-level descriptions in Section 6 and discuss whether the proof techniques can be used to analyze other problems. I appreciate that the author point out the technical hurdle to improve their current results and close the gap.\n\nI did not read the proofs but the results looked solid (based on the writing and the organization of their theoretical claims). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I like what the authors honestly point out in the checklist question 1(b). For me, a major limitation of the work is that all the results are limited to the tabular setting, which is fairly well-studied in both the realm of online RL and the realm of off-policy evaluation. It is not clear whether the new concept of C* is still fundamental and meaningful when the cardinality of states is very large. But this is still a clear accept given that the paper is already full and addresses the tabular setting throughly.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "8JMFHpqlOHR", "reviewer": "Reviewer_eXEz", "summary": "The authors present a new offline RL framework that builds the gap between imitation learning (data are generated by experts) and vanilla offline RL (data are generated with large coverage). Under this framework, the authors consider the Lower Confidence Bound (LCB) algorithm and obtain adaptive optimality on Contextual Bandit problem, sub-optimality for Multi-arm Bandit problem and conjecturely adaptive optimality for MDP. ", "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": "Strength:\n- The paper is very clear and well-written. Though many theorems are proposed, the paper is easy to follow by only listing the theorems and their intuitive explanations. \n- The new framework of constructing bounds on single policy concentrability assumption is neat and clean: it covers the entire data spectrum and is applicable to all three cases (MAB, CB and MDP)\n\nWeakness:\n- The adaptive optimality of LCB on MDPs is not proved completely.  \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "2UrJvd-EQf0", "reviewer": "Reviewer_9pjr", "summary": "This paper aims to bridge the gap between offline reinforcement learning algorithms that are “vanilla” (which perform well in the “diverse data” regime) and ones based on imitation learning (which perform well in the “optimal data” regime). They propose and study an algorithm with pessimism that performs well both in the diverse data regime and in the optimal data regime, and prove bounds on the error of their approach.", "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": "Strengths\n- Important problem\n- Interesting theoretical analysis\n- Upper and lower bounds\n\nWeaknesses\n- Doesn’t compare to MOPO, even though the algorithms are similar\n- Motivation is model-based vs. model-free, but they are purely studying model-based approaches\n\nThis paper is studying an important problem. There are significant differences between the two classes of algorithms (vanilla vs. imitation learning), and understanding which of these approaches is ideal or how to combine them is an important research direction.\n\nHowever, I’m not sure this paper really addresses this problem. My main concern is that their algorithm closely resembles the MOPO algorithm [51], which uses a pessimism term to penalize parts of the state space with high uncertainty. In particular, for finite MDPs, this pessimism term can be instantiated with rigorous bounds based on the state-action visitation counts, which is similar to how the pessimism term in this paper is defined. Furthermore, the MOPO paper includes an error guarantee that appears to be quite similar to the one achieved by the authors (in particular, by using the total variation norm on the transition probability estimates). Thus, it is not clear to me that the authors’ algorithm and analysis are novel.\n\nA related issue is that in their related work, the authors claim that there is a gap between model-free and model-based approaches in terms of pessimism, and that their work aims to clarify this gap. However, since the authors’ paper is model-based, I’m not sure how it achieves this goal.\n\nFinally, the authors do not provide any experimental results to validate their approach. Given that the performance tradeoffs are primarily of interest from an empirical point of view, I think experiments would be very helpful in clarifying this paper’s insights.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Authors show novel and interesting theoretical results that provide scale-sensitive minimax upper and lower bounds to off-policy learning, which correctly quantify the difficulty of the problem as the behavior policy becomes near-optimal. I agree with the reviewers that the contributions are significant and substantive. 
Decision: Accept (Poster)