Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism
Year: 2022

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 nearlyexpert datasets compared to the usual rate of 1/ √ N in offline RL, where N is the batch dataset sample size. In contextual bandits, 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 tabular MDPs.

text: √ N in offline RL, where N is the
batch dataset sample size. In contextual bandits, 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 tabular MDPs.

heading: 1 Introduction
text: Reinforcement learning (RL) algorithms have recently achieved tremendous empirical success including beating Go champions [45, 46] and surpassing professionals in Atari games [30, 31], to name a few. Most success stories, however, are 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 [10]. To tackle these issues, offline
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
(or batch) reinforcement learning [24, 26] arises in which the agent aims at achieving competence by exploiting a batch dataset without access to online exploration. This paradigm is useful in a diverse array of application domains such as healthcare [51, 15, 35], autonomous driving [57, 4, 36], and recommendation systems [47, 12, 49].
The key component of offline RL is a pre-collected dataset from an unknown stochastic environment. Broadly speaking, there exist two types of data composition for which offline RL algorithms have shown promising empirical and theoretical success; see Figure 1 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 to 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 [11, 22] and theoretically [2, 7]—for narrower datasets [10, 20], 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, 1], which ensures all states and actions are visited with sufficient probabilities. Algorithms developed for this regime are demonstrated to achieve a 1/ √ N sub-optimality competing with the optimal policy [53, 16, 50].

heading: 1.1 Motivating questions
text: Both of these two ends impose strong assumptions on the dataset: at one extreme, we hope for a solely 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:
Question 1 (Formulation) Can we propose an offline RL framework that accommodates the entire data composition range?
We answer this question affirmatively by proposing a new formulation for offline RL that smoothly 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?(s, a)1 and that of the data distribution µ(s, a), i.e., we define C? to be the smallest constant that satisfies d?(s, a)/µ(s, a) ≤ C? for all s ∈ S and a ∈ A; see Definition 1 for a precise characterization.
In words, C? can be viewed as a measure of the deviation between the data distribution and the distribution induced by the optimal policy. C? = 1 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: it 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 µmin over all states and actions, C? is upper bounded by µ−1min.
1Our developments can accommodate arbitrary competing policies, however, we restrict ourselves to the optimal policy for ease of presentation.
Assuming a finite C? is the weakest concentrability requirement [42, 13, 52] that is currently enjoyed only by some online algorithms such as CPI [18]. C? imposes a much weaker assumption in contrast to other concentrability requirements which involve taking a 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 [17, 55], or do not have a batch data coverage assumption that accommodates the entire data spectrum [54, 19]. For instance, Yin et al. [54] requires a 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 RL algorithms that can handle various data compositions, i.e., for all C? ≥ 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, a variety of model-based [55, 19, 56] and model-free [22, 33, 11, 34, 25, 37, 44, 14, 28, 23, 3] offline RL algorithms are proposed that achieve promising empirical results. However, it is observed empirically that existing model-free methods perform better when the dataset is nearly expert-driven whereas existing model-based methods perform better when the dataset is randomly-collected [55, 5, 56].
It remains unclear whether a single algorithm exists that performs well regardless of data composition— an important challenge from a practical perspective [21, 10, 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 an expert policy. This motivates the second question on the algorithm design:
Question 2 (Adaptive algorithm design) Can we design algorithms that can achieve minimal suboptimality 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 a lower confidence bound (LCB) for the value function of a 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 [48, 8]. A similar algorithm design has recently appeared in [17]. 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.
Results summary. Figure 2 summarizes our theoretical findings. For multi-armed bandits, we prove that LCB achieves a √ C?/N sub-optimality for any C? ≥ 1. Yet, we prove lower bounds showing that LCB cannot be adaptively optimal for any C? ≥ 1 if the knowledge of C? is not available. For contextual bandits with at least two contexts, we prove that LCB enjoys a rate of√
(C? − 1)/N + 1/N , which translates to a fast rate of 1/N when C? ≈ 1 akin to the performance of behavioral cloning and smoothly transitions from 1/N to 1/ √ N as C? increases. This rate matches the information theoretic limit, showing adaptive optimality of LCB in contextual bandits. Establishing the C?−1 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 a fast rate of 1/N for C? ≈ 1 and a rate of √ C?/N for larger values of C?.
We conjecture that LCB upper bound also has the form √
(C? − 1)/N . We verify this conjecture in a simple example and show that establishing the C? − 1 dependency in MDPs requires a delicate analysis that accounts for the value gap between optimal and sub-optimal actions.

heading: 2 Background and problem formulation
text: Notation. The probability simplex over set X is denoted by ∆(X ). We write x . y when there exists c > 0 such that x ≤ cy and write x y if c1, c2 > 0 exist such that c1|x| ≤ |y| ≤ c2|x|. We write x ∨ y to denote the supremum of x and y. We write f(x) = O(g(x)) if M > 0, x0 exist such
that |f(x)| ≤ Mg(x) for all x ≥ x0. We use Õ(·) to be the big-O notation ignoring logarithmic factors. We write f(x) = Ω(g(x)) if M > 0, x0 exist such that |f(x)| ≥Mg(x) for all x ≥ x0.

heading: 2.1 Markov decision processes
text: An infinite-horizon discounted MDP is described by a tuple M = (S,A, P,R, ρ, γ), where S is a finite state space with S = |S|, A is a finite action space, P : S ×A 7→ ∆(S) is a transition matrix, R : S × A 7→ ∆([0, 1]) encodes a family of reward distributions with r : S × A 7→ [0, 1] as the expected reward function, ρ : S 7→ ∆(S) is the initial distribution, and γ ∈ [0, 1) is a discount factor. A stationary deterministic policy π : S 7→ A is a function that maps a state to an action. Correspondingly, the (normalized) state-action discounted occupancy measure dπ : S ×A 7→ [0, 1] is defined as dπ(s, a) := (1−γ) ∑∞ t=0 γ
t Pt(st = s, at = a;π) for all s ∈ S, a ∈ A, where Pt(st = s, at = a;π) denotes the probability of st = s, at = a after executing policy π and starting from s0 ∼ ρ(·). The value function V π : S 7→ R of the policy π is defined as V π(s) := E[ ∑∞ t=0 γ
trt | s0 = s, at = π(st) for all t ≥ 0] for s ∈ S. The quality function (or Q-function) Qπ : S × A → R of policy π is defined analogously Qπ(s, a) := E[ ∑∞ t=0 γ
trt | s0 = s, a0 = a, at = π(st) for all t ≥ 1]. It is convenient to define a scalar summary of the performance of a policy π as J(π) := Es∼ρ[V π(s)]. It is well known [38] that a stationary deterministic policy π? exists that simultaneously maximizes V π(s) for all s ∈ S , and hence maximizing the expected value J(π). We use shorthands V ? := V π? and Q? := Qπ ? to denote the optimal value function and Q-function.

heading: 2.2 Offline data and offline RL
text: The current paper focuses on offline RL, where the agent cannot interact with the MDP and instead is given a batch dataset D consisting of tuples (s, a, r, s′), where r ∼ R(· | s, a) and s′ ∼ P (· | s, a). For simplicity, we assume (s, a) pairs are generated i.i.d. according to a data distribution µ over S × A, which is unknown to the agent.2 We denote by N(s, a) ≥ 0 the number of times (s, a) is observed in D and by N = |D| 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 π?, i.e., ED [J(π?)− J(π̂)], where the expectation is taken with respect to the randomness in the dataset.

heading: 2.3 Dataset coverage assumption
text: Definition 1 (Single policy concentrability) Given a policy π, defineCπ to be the smallest constant that satisfies dπ(s, a)/µ(s, a) ≤ Cπ for all s ∈ S and a ∈ A.
In words, Cπ characterizes the distribution shift between the occupancy measure induced by π and data distribution µ. For a 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
2The i.i.d. assumption is motivated by the data randomization performed in experience replay [31].
requires the coverage of (s, a) visited by all policies. A similar notion of concentratbility coefficient in `2 norm instead of `∞ norm has appeared in the literature of off-policy evaluation [27, 29].

heading: 3 A warm-up: LCB in multi-armed bandits
text: We begin with the simplest example of an MDP, the multi-armed bandit (MAB) model, where S = 1 and γ = 0. For MABs, the offline dataset simplifies to D = {(ai, ri)}Ni=1, where ai ∼ µ(·) and ri ∼ R(ai). Competing with an optimal arm a?, the data coverage assumption becomes 1/µ(a?) ≤ C?. The goal of offline learning in MAB is to select an arm â that minimizes the expected sub-optimality ED[J(π?)− J(π̂)] = ED[r(a?)− r(â)], where r(a) is the expected reward of arm a.

heading: 3.1 Why does the best empirical arm fail?
text: A natural choice for solving the offline learning problem is to select the arm with the highest empirical average reward, i.e., â := arg maxa r̂(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 B.1 for a proof.
Proposition 1 (Failure of the best empirical arm) For any < 0.3,N ≥ 500, there exists a bandit problem with two arms such that for â = arg maxa r̂(a), one has ED[r(a?)− r(â)] ≥ .

heading: 3.2 LCB: The benefit of pessimism
text: 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 of the arms pulled less often. Strategically, pessimism can be deployed by first constructing a penalty function b(a) that shrinks as N(a) increases and then returning â ∈ arg maxa r̂(a)− b(a). When b(a) captures a confidence level about the empirical reward, r̂(a) − b(a) can be viewed as a lower confidence bound (LCB) on the true mean reward r(a). Algorithm 1 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 1 (LCB sub-optimality, MAB) For a MAB, assume that 1/µ(a?) ≤ C? for someC? ≥ 1. Provided that N ≥ 8C? logN , arm â returned by Algorithm 1 with δ = 1/N obeys
ED[r(a?)− r(â)] . min ( 1, √ C? log(2N |A|)
N
) . (1)
Applying the above guarantee to the failure instance given in Proposition 1, one sees that LCB secures a sub-optimality of Õ(1/ √ N), which beats the best empirical arm. This is because the LCB approach applies larger penalties to the arms with a small number of samples, which helps to rule them out.

heading: 3.3 Is LCB optimal for solving offline multi-armed bandits?
text: Given the performance bound (1), it is natural to ask whether LCB is optimal for solving offline MAB problems. To address this question, we resort to the usual minimax criterion. Define the following MAB family: MAB(C?) = {(µ,R) | 1/µ(a?) ≤ C?}, which includes all possible pairs of µ and R such that the data coverage assumption 1/µ(a?) ≤ C? holds. We define the worst-case risk of any estimator â to be sup(µ,R)∈MAB(C?) ED[r(a?)− r(â)]. An estimator â is a measureable function of the dataset D 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 (Information-theoretic limit, MAB) For C? ≥ 2, one has
inf â sup (µ,R)∈MAB(C?)
ED[r(a?)− r(â)] & min ( 1, √ C?
N
) . (2)
For C? ∈ (1, 2), one has
inf â sup (µ,R)∈MAB(C?)
ED[r(a?)− r(â)] & exp ( −(2− C?) log ( 2
C?−1
) ·N ) .

heading: 3.4 Imitation learning in bandit: the most played arm achieves a better rate
text: Theorem 2 reveals that when C? ≥ 2, the best possible expected sub-optimality is √ C?/N , which is achieved by LCB. On the other hand, in the case of C? ∈ [1, 2), which corresponds to µ(a?) > 1/2, we can simply use imitation learning to improve the rate by picking the most frequently selected arm in the dataset, i.e., â = arg maxaN(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/µ(a?) ≤ C? for some C? ∈ [1, 2). For â = arg maxaN(a), we have
ED[r(a?)− r(â)] ≤ exp ( −N · KL ( Bern ( 1 2 ) ∥∥∥ Bern ( 1C? ))) . (3) When C? ∈ [1, 2), the most played arm achieves an exponential rate in N , whereas the upper bound for LCB is only 1/ √ N . On the other hand, the most played arm algorithm completely fails when C? > 2, while LCB secures the rate 1/ √ N . In terms of C? dependence, the KL divergence above evaluates to log(C?/2) + log(1/(C? − 1))/2. As C? → 1, the rate increases to the order of 1/(C? − 1)N , matching the lower bound in Theorem 2.

heading: 3.5 Non-adaptivity of LCB
text: 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 1, LCB cannot be optimally adaptive in both regimes. The proof is deferred to Appendix B.5.
Theorem 3 (Non-adaptivity of LCB, MAB) Let C? = 1.5. There exists a two-armed bandit instance (µ0, R0) ∈ MAB(C?) such that Algorithm 1 with L := √ log(2|A|/δ)/2 satisfies
ED[r(a?)− r(â)] & min (√ L N , 1√ N ) · exp(−32L).
On the other hand, when C? = 6, there exists (µ1, R1) ∈ MAB(C?) such that ED[r(a?)− r(â)] & min ( 1, √ L N ) .
Intuitively, a larger L means that we put greater weight on penalty instead of empirical average. As L → ∞, 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), to achieve an exponential rate similar to the most played arm (Theorem 2), we need to select δ such that L & Nα for α > 0. However, under this choice of L, the algorithm fails to achieve 1/ √ N rate when C? ≥ 6, which can be achieved by setting δ = 1/N (and thus L = log(2|A|N)) based on Theorem 1. Hence, it is impossible for LCB to achieve optimal rate in both C? ∈ (1, 2) and C? ≥ 2 regimes simultaneously.

heading: 4 LCB in contextual bandits
text: We take the analysis one step further by studying offline learning in contextual bandits (CBs). CB is a special case of MDP described in Section 2.1 with γ = 0. In CB setting, the batch dataset is D = {(si, ai, ri)}Ni=1 and the coverage assumption simplifies to maxs ρ(s)/µ(s, π?(s)) ≤ C?. The offline learning objective in CB is to find a policy π̂ based on D that minimizes the expected sub-optimality ED[J(π?)− J(π̂)] = ED,ρ [r(s, π?(s))− r(s, π̂(s))] .

heading: 4.1 LCB algorithm and its performance guarantee
text: The pessimism principle introduced for MAB can be naturally extended to CB by subtracting a penalty function b(s, a) from the empirical rewards r̂(s, a) and returning π̂(s) ∈ arg maxa r̂(s, a)− b(s, a) for every state s. The following theorem establishes an upper bound on the expected sub-optimality of the policy returned by Algorithm 1; see Appendix C.1 for a complete proof.
Algorithm 1 LCB for bandits and contextual bandits 1: Inputs: Batch dataset D = {(si, ai, ri)}Ni=1, and confidence level δ. 2: for s ∈ S, a ∈ A do 3: if N(s, a) = 0 then Set r̂(s, a)←[ 0. 4: else Set r̂(s, a)← [ 1N(s,a) ∑N i=1 ri 1{(si, ai) = (s, a)}.
5: Compute the penalty b(s, a) = √
2000 log(2S|A|/δ) N(s,a)∨1 .
6: Return: π̂(s) ∈ arg maxa r̂(s, a)− b(s, a) for each s ∈ S.
Theorem 4 (LCB sub-optimality, CB) For a CB with S ≥ 2, assume maxs ρ(s)/µ(s, π?(s)) ≤ C?, for some C? ≥ 1. The policy π̂ returned by Algorithm 1 with δ = 1/N obeys
ED[J(π?)− J(π̂)] . min ( 1, Õ (√ S(C?−1) N + S N )) .
The sub-optimality in Theorem 4 consists of two terms. The first term has the usual statistical estimation rate of 1/ √ N . 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 on data composition is C? − 1. When C? is close to 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/ √ N as C? increases.

heading: 4.2 Optimality of LCB for solving offline contextual bandits
text: We now establish an information-theoretic lower bound for the contextual bandit setup described above. Define the following family of CB problems CB(C?) := {(ρ, µ,R) | maxs ρ(s)/µ(s, π
?(s)) ≤ C?}. Let π̂ : S 7→ A be an arbitrary estimator of the best arm π(s) for any state s, which is a measurable function of the data. For the worst-case risk of π̂ defined as sup(ρ,µ,R)∈CB(C?) ED[J(π?)− J(π̂)], we have the following minimax lower bound:
Theorem 5 (Information-theoretic limit, CB) Assume that S ≥ 2. For any C? ≥ 1, one has
inf π̂ sup (ρ,µ,R)∈CB(C?)
ED[J(π?)− J(π̂)] & min ( 1, √ S(C?−1) N + S N ) .
The proof is provided in Appendix C.2. Comparing with Theorem 4, one sees that LCB enjoys a near-optimal rate in CB with S ≥ 2 regardless of C?. This is in stark contrast to the MAB case. On a closer inspection, in the C? ∈ [1, 2) regime, there is a clear separation between the informationtheoretic 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 is 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 at least one state has a 1/N rate.
Assume hypothetically that we know C? ∈ (1, 2). Under this circumstance, one might wonder whether simply picking the most played arm in every state achieves a fast rate, analogous to MAB. Strikingly, the answer is negative as the following proposition shows that the most played arm fails to achieve a vanishing rate when C? ∈ (1, 2). The proof of this theorem is deferred to Appendix C.3. Proposition 3 (Failure of the most played arm, CB) For anyC? ∈ (1, 2), there exists a contextual bandit problem (ρ, µ,R) ∈ CB(C?) such that for the policy π̂(s) = arg maxaN(s, a),
lim N→∞
ED[J(π?)− J(π̂)] ≥ C? − 1.

heading: 5 LCB in Markov decision processes

heading: 5.1 Offline value iteration with LCB
text: 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
Algorithm 2 Offline value iteration with LCB (VI-LCB) 1: Inputs: Batch dataset D, discount factor γ, and confidence level δ. 2: Set T := logN1−γ , L := 2000 log(2(T + 1)S|A|/δ), Vmax = (1− γ)
−1. 3: Split D into T + 1 sets Dt = {(si, ai, ri, s′i)}mi=1 for t ∈ {0, 1, . . . , T}. 4: Set mt(s, a) := ∑m i=1 1{(si, ai) = (s, a)} based on dataset Dt for t ∈ {0, 1, . . . , T}. 5: Initialize Q0(s, a) = 0, V0(s) = 0 and set π0(s) = arg maxam0(s, a), for a ∈ A and s ∈ S. 6: for t = 1, . . . , T do 7: for (s, a) ∈ (S,A) do 8: if mt(s, a) = 0 then Set rt(s, a) = 0 and P t(· | s, a) to be a random probability vector. 9: else Set P t(· | s, a) to be empirical transitions and rt(s, a) be empirical rewards.
10: Compute penalty bt(s, a) := Vmax · √
L mt(s,a)∨1 . 11: Set Qt(s, a)←[ rt(s, a)− bt(s, a) + γ ∑ s′ P
t(s′ | s, a)Vt−1(s′). 12: Compute V midt ← maxaQt(s, a) and πmidt (s) ∈ arg maxaQt(s, a). 13: for s ∈ S do 14: if V midt (s) ≤ Vt−1(s) then Vt(s)← Vt−1(s) and πt(s)← πt−1(s). 15: else Vt(s)← V midt (s) and πt(s)← πmidt (s). 16: Return π̂ := πT .
rewards r and transitions P , we replace them with the empirical counterparts r̂ and P̂ . Furthermore, mimicking the LCB algorithmic design for MABs and CBs, we subtract a penalty function b(s, a) from the Q update as the finishing touch, which yields the value iteration algorithm with LCB:
Q(s, a)← [ r̂(s, a)− b(s, a) + γ ∑ s′ P̂ (s′ | s, a)V (s′), for all (s, a), (4)
V (s)←[ max a Q(s, a), for all s. (5)
Algorithm 2 uses the update rule (4) as its key component as well as a few other tricks: • Data splitting. Instead of using the full dataset D to form r̂ 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. Algorithm 2 updates value function V and policy π only when the corresponding value estimate is larger than that in the previous iteration. The key benefit of the monotonic update is to shave a 1/(1− γ) 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 6 (LCB sub-optimality, MDP) For a MDP, assume that maxs,a d?(s, a)/µ(s, a) ≤ C?. Then, for all C? ≥ 1, policy π̂ returned by Algorithm 2 with δ = 1/N achieves
ED [J(π?)− J(π̂)] . min ( 1 1−γ , Õ (√ SC? (1−γ)5N )) . (6)
In addition, if 1 ≤ C? ≤ 1 + L log(N)200(1−γ)N , we have a tighter performance upper bound ED [J(π?)− J(π̂)] . min ( 1 1−γ , Õ ( S (1−γ)4N )) . (7)
The upper bound shows that for all C? ≥ 1, we can guarantee a rate of Õ( √ SC?/((1− γ)5N)),
which is similar to the rate of CB when the C? = 1+Ω(1) by taking γ = 0. When C = 1+ Õ(1/N), we have a rate S/((1− γ4)N), which also recovers the result in the CB case. However, in the regime of C? ∈ [1 + Ω̃(1/N), 1 +O(1)], while CB enjoys √ S(C? − 1)/N rate, we fail to give the same dependence on C? in MDP; see Section 6 for further discussion on sub-optimality in this regime.

heading: 5.2 Information-theoretic lower bound for offline RL in MDPs
text: To capture the statistical limits of offline learning in MDPs, as before we define the following family of instances MDP(C?) := {(ρ, µ, P,R) | maxs,a d ?(s,a) µ(s,a) ≤ C
?}. We have the following minimax lower bound for offline policy learning in MDPs, with the proof deferred to Appendix D.7.
Theorem 7 (Information-theoretic limit, MDP) For any C? ≥ 1, γ ≥ 0.5, one has
inf π̂ sup (ρ,µ,P,R)∈MDP(C?)
ED[J(π?)− J(π̂)] & min ( 1 1−γ , S (1−γ)2N + √ S(C?−1) (1−γ)3N ) .
Imitation learning and offline learning. Similar to the CB lower bound, the statistical limit in Theorem 7 involves two terms. The first term captures the imitation learning regime under which a fast rate 1/N is expected, while the second term deals with the large C? regime with a rate 1/ √ N . More interestingly, the dependence on C? appears to be C? − 1, which is different from the performance upper bound of VI-LCB in Theorem 6. We will comment more on this in the coming section.
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− γ)2 factor in sample complexity. We believe that this extra factor can be shaved by replacing the Hoeffding-based penalty to a Bernstein-based one and using variance reduction similar to [43].

heading: 6 Proof techniques and conjecture
text: To prove the crude rate of √ C?/N for any C? ≥ 1 in all three MAB, CB, and MDP settings, it is sufficient to bound the sub-optimality by an expectation over penalty followed by the coverage assumption. Since the penalty is proportional to 1/ √ N , this technique only yields a 1/ √ N rate.
The √
(C? − 1)/N + S/N rate in CB. We carefully decompose the sub-optimality and characterize 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 a gradual decomposition of the sub-optimality of π̂ as illustrated in Figure 3.
In the first level of decomposition, we separate the error based on whether N(s, π?(s)) is zero for a certain state s. When N(s, π?(s)) = 0, there is absolutely no basis for the LCB approach to figure out the correct action π?(s). Fortunately, this type of error, incurred by missing mass, can be bounded by T1 . C ?S N .
The second level of decomposition hinges on the following clean/good event: E := {∀s, a : |r(s, a)− r̂(s, a)| ≤ b(s, a)}. In words, the event E captures the scenario in which the penalty function provides valid confidence bounds for every state-action pair. Standard concentration arguments tell us that E takes place with high probability, i.e., the term T2 in the figure is no larger than δ. By setting δ small, say 1/N , we are allowed to concentrate on the case when E holds. The third level of decomposition relies on the observation that states with small weights (i.e., ρ(s) is small) have negligible effects on the sub-optimality J(π?)− J(π̂). More specifically, the aggregated contribution T3 from the states with ρ(s) . C ?L N is upper bounded by T3 . C?SL N . This allows us to focus on the states with large weights. We record an immediate consequence of large ρ(s) and the data coverage assumption, that is µ(s, π?(s)) ≥ ρ(s)/C? 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 µ(s, π?(s)) than the total probability of sub-optimal actions µ(s) := ∑ a 6=π?(s) µ(s, a). In particular,
when µ(s, π?(s)) < 10µ(s), we can repeat the analysis of MAB and show that T4 . √ S(C?−1)L N . Here, the appearance of C? − 1, as opposed to C? is due to the restriction µ(s, π?(s)) < 10µ(s). One can verify that µ(s, π?(s)) < 10µ(s) together with the data coverage assumption ensures that∑ s:ρ(s)≥2C?L/N,µ(s,π?(s))<10µ(s) ρ(s) . C
? − 1. On the other hand, when µ(s, π?(s)) ≥ 10µ(s), i.e., when the optimal action is more likely to be seen in the dataset, the penalty function b(s, π?(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., T5 . 1/N10.
C? dependency in MDPs. Ignoring the dependency on 1/(1−γ), by comparing Theorems 6 and 7, one realizes that VI-LCB is optimal both when C? ≥ 1 + Θ(1) and C? ≤ 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 1 (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. It 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? ∈ [1 + Ω(1/N), 1 +O(1)]. Major difficulties arise in controlling case (i), where µ(s, π?(s)) ∑ a 6=π?(s) µ(s, a). Recall that VI-LCB picks the right action if
rt(s, π ?(s))−
√ L
mt(s, π?(s)) ∨ 1 +γP t(·|s, π?(s))·Vt−1 > rt(s, a)−
√ L
mt(s, a) ∨ 1 +γP t(·|s, a)·Vt−1,
for all a 6= π?(s). The presence of the previous values Vt−1 drastically changes the picture: even if we know that mt(s, π?(s)) mt(s, a), the current analysis does not guarantee the above inequality. It is likely that the value gap g(s) := Q?(s, π?(s))−Q?(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? ∈ [1 + Ω(1/N), 1 +O(1)].
A confirmation from an episodic MDP. In Appendix E.6, we present an episodic example to demonstrate that (1) an 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 on a delicate decomposition based on the gap Q?(s, π?(s))−Q?(s, a). 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(s) is small. If g(s) is small for state s, the contribution to the suboptimality is well controlled. Otherwise, we manage to show that VI-LCB selects the right action with high probability. What is more interesting and surprising is that the right threshold for value gap is given by √ (C? − 1)/N . Ultimately, this allows us to achieve the optimal dependency on C?.

heading: 7 Discussion
text: We propose a 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 1). 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.

heading: Acknowledgements
text: The authors are grateful to 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.

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

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.  Contribution 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.   Contribution 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.  Contribution 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.