Year: 2021

Abstract:
Offline reinforcement learning (RL) algorithms can acquire effective policies by utilizing only previously collected experience, without any online interaction. While it is widely understood that offline RL is able to extract good policies even from highly suboptimal data, in practice offline RL is often used with data that resembles demonstrations. In this case, one can also use behavioral cloning (BC) algorithms, which mimic a subset of the dataset via supervised learning. It seems natural to ask: under what environment and dataset conditions can an offline RL method outperform BC with an equal amount of expert data, even when BC is a natural choice? To answer this question, we characterize the properties of environments that allow offline RL methods to perform better than BC methods even when only provided with expert data. Additionally, we show that policies trained on suboptimal data that is sufficiently noisy can attain better performance than even BC algorithms with expert data, especially on long-horizon problems. We validate our theoretical results via extensive experiments on both diagnostic and high-dimensional domains including robot manipulation, maze navigation and Atari games, when learning from a variety of data sources. We observe that modern offline RL methods trained on suboptimal, noisy data in sparse reward domains outperform cloning the expert data in several practical problems.

heading: 1 INTRODUCTION
text: Offline reinforcement learning (RL) algorithms aim to leverage large, existing datasets of previously collected data to produce effective policies that generalize across a wide range of scenarios, without the need for costly active data collection. Many recent offline RL algorithms (Fujimoto et al., 2018; Kumar et al., 2019; Wu et al., 2019; Kumar et al., 2020; Yu et al., 2020; Sinha et al., 2021; Kostrikov et al., 2021) can work well even highly suboptimal data. With recent advances, the performance of offline RL algorithms has improved significantly, and a number of these approaches have been studied theoretically (Wang et al., 2021; Zanette, 2020; Rashidinejad et al., 2021). While it is clear that offline RL algorithms are a good choice when the available data is either random or highly suboptimal, it is less clear if these methods should even be tried when the datasets consist of demonstration that come from expert or near-expert demonstrations. In these cases, imitation learning algorithms, such as behavorial cloning (BC), can be used to train policies via supervised learning. It then seems natural to ask: When should we prefer to use offline RL over imitation learning?
To our knowledge, there has not been a rigorous characterization of when offline RL perform better than imitation learning. Existing empirical studies comparing offline RL to imitation learning have mixed conclusions. Some works show that offline RL methods appear to greatly outperform imitation learning, specifically in environments that require “stitching” parts of suboptimal trajectories (Fu et al., 2020). In contrast, a number of recent works have argued that BC performs better than offline RL on both expert and suboptimal demonstration data over a variety of tasks (Mandlekar et al., 2021; Florence et al., 2021; Hahn et al., 2021). This makes it confusing for practitioners to understand whether to use offline RL or simply run BC on collected demonstrations. Thus, in this work we aim to understand if there are conditions on the environment or the dataset under which an offline RL algorithm might outperform BC for a given task, even when BC is provided with expert data or is allowed to use reward as side information. Our insights can inform a practitioner with sufficient domain knowledge on whether offline RL is a good idea, even when expert or near-expert data is available and BC is considered to be a natural choice.
Our contribution in this paper is a theoretical and empirical characterization of certain conditions when offline RL can outperform BC. Theoretically, we are the first to derive conditions on the environment or offline dataset where offline RL achieves better worst-case guarantees than even the best-case lower-bound for BC using expert demonstrations. These conditions are grounded in practical problems, and provide guidance to the practitioner as to whether they should use RL or BC. Concretely, we show that in the case of expert data, the error incurred by offline RL algorithms can scale significantly more favorably when the MDP enjoys some structure including horizonindependent returns (i.e., sparse rewards), or a low volume of states where it is “critical” to take the same action as the expert (Section 4.2) Meanwhile, in the case of sufficiently noisy data, we show that offline RL again enjoys better guarantees on long-horizon tasks (Section 4.3). Finally, since traditional BC methods ignore rewards, we consider generalized BC methods that use the observed rewards to inform learning, and show that it is still preferable to perform offline RL (Section 4.4).
Empirically, we validate our theoretical conclusions on diagnostic gridworld domains (Fu et al., 2019) and large-scale benchmark problems in robotic manipulation and navigation and Atari games, using human data (Fu et al., 2020), scripted data (Singh et al., 2020) and data generated from RL policies (Agarwal et al., 2020b). We verify that in multiple long-horizon problems where the conditions we propose are likely to be satisfied, practical offline RL methods can outperform BC and generalized BC methods. Using careful offline tuning practices, we show that it is possible for offline RL to outperform cloning an expert dataset for the same task, given equal amounts of data.

heading: 2 RELATED WORK
text: Offline RL (Lange et al., 2012; Levine et al., 2020) has shown promise in domains such as robotic manipulation (Kalashnikov et al., 2018b; Mandlekar et al., 2020; Singh et al., 2020; Kalashnikov et al., 2021), NLP (Jaques et al., 2020) and healthcare (Shortreed et al., 2011; Wang et al., 2018). The major challenge in offline RL is distribution shift (Fujimoto et al., 2018; Kumar et al., 2019), where the learned policy might execute out-of-distribution actions. Prior offline RL methods can broadly be characterized into two categories: (1) policy-constraint methods that regularize the learned policy to be “close” to the behavior policy either explicitly (Fujimoto et al., 2018; Kumar et al., 2019; Liu et al., 2020; Wu et al., 2019; Fujimoto & Gu, 2021) or implicitly (Siegel et al., 2020; Peng et al., 2019; Nair et al., 2020), or via importance sampling (Liu et al., 2019; Swaminathan & Joachims, 2015; Nachum et al., 2019), and (2) conservative methods that learn a lower-bound, or conservative, estimate of return and optimize the policy against it (Kumar et al., 2020; Kostrikov et al., 2021; Kidambi et al., 2020; Yu et al., 2020; 2021). Our goal is not to devise a new offline RL algorithm, but rather to understand when existing offline RL methods can outperform BC.
When do offline RL methods outperform BC? Rashidinejad et al. (2021) derive a conservative offline RL algorithm based on lower-confidence bounds (LCB) that provably outperforms BC in the simpler contextual bandits (CB) setting, but do not extend it to MDPs. While this CB result signals the possibility that offline RL can outperform BC in theory, this generalization is not trivial, as RL suffers from compounding errors (Munos, 2003; 2005; Wang et al., 2021). Laroche et al. (2019); Nadjahi et al. (2019); Kumar et al. (2020); Liu et al. (2020); Xie et al. (2021a) present safe policy improvement bounds expressed as improvements over the behavior policy, which imitation aims to recover, but these bounds do not clearly indicate when offline RL is better or worse. Empirically, Fu et al. (2020) show that offline RL considerably outperforms BC for tasks that require “stitching” trajectory segments to devise an optimal policy. In contrast, Mandlekar et al. (2021); Brandfonbrener et al. (2021); Chen et al. (2021); Hahn et al. (2021) suggest that BC or filtered BC using the top fraction of the data performs better on other tasks. While results on Adroit domains in D4RL (Fu et al., 2020) show that offline RL outperforms BC even on expert data, Florence et al. (2021) reported superior BC results, making it unclear. Kurenkov & Kolesnikov (2022) emphasize the importance of the online evaluation budget for offline RL methods and show that BC is more favorable in a limited budget. We provide a characterization of certain scenarios where we would expect offline RL to be better than BC, and empirical results verifying that offline RL performs well on such problems, spanning robotics, navigation, games (Fu et al., 2020; Singh et al., 2020; Bellemare et al., 2013).
Our theoretical analysis combines tools from a number of prior works. We analyze the total error incurred by RL via an error propagation analysis (Munos, 2003; 2005; Farahmand et al., 2010; Chen & Jiang, 2019; Xie & Jiang, 2020; Liu et al., 2020), which gives rise to bounds with concentrability coefficients that bound the total distributional shift between the learned policy and the data distribution (Xie & Jiang, 2020; Liu et al., 2020). We use tools from Ren et al. (2021), which provide
horizon-free bounds for standard (non-conservative) offline Q-learning but relax their strict coverage assumptions. While our analysis studies a LCB-style algorithm similar to Rashidinejad et al. (2021), we modify it to use tighter Bernstein bonuses (Zhang et al., 2021; Agarwal et al., 2020a), which is key to improving its suboptimality guarantee. Xie et al. (2021b) consider a similar algorithm with Bernstein bonuses, but take a different approach to analysis it and use it for policy finetuning.

heading: 3 PROBLEM SETUP AND PRELIMINARIES
text: The goal in reinforcement learning is to learn a policy π(·|s) that maximizes the expected cumulative discounted reward in a Markov decision process (MDP), which is defined by a tuple (S,A, P, r, γ). S,A represent state and action spaces, P (s′|s,a) and r(s,a) represent the dynamics and mean reward function, and γ ∈ (0, 1) represents the discount factor. The effective horizon of the MDP is given by H = 1/(1− γ). The Q-function, Qπ(s,a) for a given policy π is equal to the discounted long-term reward attained by executing a at the state s and then following policy π thereafter. Qπ satisfies the recursion: ∀s,a ∈ S×A, Qπ(s,a) = r(s,a)+γEs′∼P (·|s,a),a′∼π(·|s′) [Q(s′,a′)]. The value function V π considers the expectation of the Q-function over the policy V π(s) = Ea∼π(·|s) [Qπ(s,a)]. Meanwhile, the Q-function of the optimal policy, Q∗, satisfies the recursion: Q∗(s,a) = r(s,a) + Es′∼P (·|s,a) [maxa′ Q∗(s′,a′)], and the optimal value function is given by V ∗(s) = maxaQ∗(s,a). Finally, the expected cumulative discounted reward is given by J(π) = Es0∼ρ [V π(s0)].
In offline RL, we are provided with a dataset D of transitions, D = {(si,ai, ri, s′i)}Ni=1 of size |D| = N . We assume that the dataset D is generated i.i.d. from a distribution µ(s,a) that specifies the effective behavior policy πβ(a|s) := µ(s,a)/ ∑ a µ(s,a). Note that holds even if the data itself is generated by running a non-Markovian policy πβ (Puterman, 1994). Let n(s,a) be the number of times (s,a) appear in D, and P̂ (·|s,a) and r̂(s,a) denote the empirical dynamics and reward distributions in D, which may be different from P and r due to stochasticity. Following Rashidinejad et al. (2021), the goal is to minimize the suboptimality of the learned policy π̂:
SubOpt(π̂) = ED∼µ [J(π∗)− J(π̂)] = ED [ Es0∼ρ [ V ∗(s0)− V π̂(s0) ]] . (1)
Dataset and MDP conditions. Here we introduce some conditions on the offline dataset and MDP structure that we make for our analysis. The first characterizes the distribution shift between the data distribution µ(s,a) and the normalized state-action marginal of π∗, given by d∗(s,a) = (1− γ) ∑∞ t=0 γ
tP (st = s,at = a;π∗), via a concentrability coefficient C∗. Condition 3.1 (Rashidinejad et al. (2021), Concentrability of the data distribution). Define C∗ to be the smallest, finite constant that satisfies: d∗(s,a)/µ(s,a) ≤ C∗ ∀s ∈ S,a ∈ A. Intuitively, the coefficient C∗ scales with how suboptimal the data µ(s,a) is relative to the optimal π∗, where C∗ = 1 corresponds to data from π∗. The next condition we consider is that the discounted return for any trajectory in the MDP is bounded by a constant, which w.l.o.g., we assume to be 1. Condition 3.2 (Ren et al. (2021), the value of any trajectory is bounded by 1). The infinite-horizon discounted return for any trajectory τ = (s0,a0, r0, s1, · · · ) is bounded as ∑∞ t=0 γ
trt ≤ 1. This condition holds in sparse-reward tasks, particularly those where an agent succeeds or fails at its task once per episode. This is common in domains such as robotics (Singh et al., 2020; Kalashnikov et al., 2018b) and games (Bellemare et al., 2013), where the agent receives a signal upon succeeding a task or winning. This condition also appears in prior work deriving suboptimality bounds for RL algorithms (Ren et al., 2021; Zhang et al., 2021).
Notation. Let n ∧ 1 = max{n, 1}. Denote ι = polylog(|S|, H,N). We let ι be a polylogarithmic quantity, changing with context. For d-dimensional vectors x,y, x(i) denotes its i-th entry, and define V(x,y) = ∑ i x(i)y(i) 2 − ( ∑ i x(i)y(i)) 2.

heading: 4 THEORETICAL COMPARISON OF BC AND OFFLINE RL
text: In this section, we present performance guarantees for BC and offline RL, and characterize scenarios where offline RL algorithms will outperform BC. We first present general upper bounds for both algorithms in Section 4.1, by extending prior work to account for the conditions discussed in Section 3. Then, we compare the performance of BC and RL when provided with the same data generated by an expert in Section 4.2 and when RL is given noisy, suboptimal data in Section 4.3. Our goal is to characterize the conditions on the environment and offline dataset where RL can outperform BC. Furthermore, we provide intuition for when they are likely to hold in Appendix D.

heading: 4.1 GENERAL PERFORMANCE GUARANTEES OF BC AND OFFLINE RL
text: Our goal is to understand if there exist offline RL methods can outperform BC for a given task. As our aim is simply to provide a proof of existence, we analyze representative offline RL and BC algorithms that achieve optimal suboptimality guarantees. For brevity, we only consider a conservative offline RL algorithm (as defined in Section 2) in the main paper and defer analysis of a policy-constraint method to Appendix C. Both algorithms are detailed in Algorithms 1 and 2.
Guarantees for BC. For analysis purposes, we consider a BC algorithm that matches the empirical behavior policy on states in the offline dataset, and takes uniform random actions outside the support of the dataset. This BC algorithm was also used in prior work (Rajaraman et al., 2020), and is no worse than other schemes for acting at out-of-support states, in general. Denote the learned BC policy as π̂β , then ∀s ∈ D, π̂β(a|s)← n(s,a)/n(s), and ∀s /∈ D, π̂β(a|s)← 1/|A|. We adapt the results presented in Rajaraman et al. (2020) to the setting with Conditions 3.1 and 3.2. BC can only incur a non-zero asymptotic suboptimality (i.e., does not decrease to 0 as N → ∞) in scenarios where C∗ = 1, as it aims to match the data distribution µ(s,a), and a non-expert dataset will inhibit the cloned policy from matching the expert π∗. The performance for BC is bounded in Theorem 4.1. Theorem 4.1 (Performance of BC). Under Conditions 3.1 and 3.2, the suboptimality of BC satisfies
SubOpt(π̂β) . (C∗ − 1)H 2 + |S|Hι N .
A proof of Theorem 4.1 is presented in Appendix B.1. The first term is the additional suboptimality incurred due to discrepancy between the behavior and optimal policies. The second term in this bound is derived by bounding the expected visitation frequency of the learned policy π̂β onto states not observed in the dataset. The analysis is similar to that for existing bounds for imitation learning (Ross & Bagnell, 2010; Rajaraman et al., 2020). We achieve Õ(H) suboptimality rather than Õ(H2) due to Condition 3.2, since the worst-case suboptimality of any trajectory is 1 rather than H .
Guarantees for conservative offline RL. We consider guarantees for a class of offline RL algorithms that maintain conservative value estimator such that the estimated value lower-bounds the true one, i.e., V̂ π ≤ V π for policy π. Existing offline RL algorithms achieve this by subtracting a penalty from reward either explicitly (Yu et al., 2020; Kidambi et al., 2020) or implicitly (Kumar et al., 2020). We only analyze one such algorithm that does the former, but we believe the algorithm can serve as a theoretical model for general conservative offline RL algorithms, where analyzing similar algorithms can be accomplished using the same outline. The algorithm we consider is similar in spirit to VI-LCB proposed by Rashidinejad et al. (2021) that subtracts penalty b(s,a) from the reward during value iteration; we consider a different penalty that results in a tighter bound. The estimated Q-values are obtained by iteratively solving the following Bellman backup: Q̂(s,a)← r̂(s,a)− b(s,a) + ∑ s′ P̂ (s
′|s,a) maxa′ Q̂(s′,a′). The learned policy is then given by π̂∗(s)← arg maxa Q̂(s,a). Building on work in online RL (Zhang et al., 2021), our specific b(s,a) is derived using Bernstein’s inequality, and is shown below:
b(s,a) ←
√ V(P̂ (·|s,a), V̂ )ι
(n(s,a) ∧ 1) +
√ r̂(s,a)ι
(n(s,a) ∧ 1) +
ι
(n(s,a) ∧ 1) .
The performance of the learned policy π̂∗ can then be bounded as: Theorem 4.2 (Performance of conservative offline RL). Under Conditions 3.1 and 3.2, the policy π̂∗ found by conservative offline RL algorithm can satisfy
SubOpt(π̂∗) .
√ C∗|S|Hι
N + C∗|S|Hι N .
We defer a proof for Theorem 4.2 to Appendix B.2. On a high level, we first show that our algorithm is always conservative, i.e., ∀s, V̂ (s) ≤ V π̂∗(s), and then bound the total suboptimality incurred as a result of being conservative. Novelty: Our bound in in Theorem 4.2 improves on existing bounds several ways: (1) by considering pessimistic value estimates, we are able to remove the strict coverage assumptions used by Ren et al. (2021), (2) by using variance recursion techniques on the Bernstein bonuses, with Condition 3.2, we save a O(H2) factor over VI-LCB in Rashidinejad et al. (2021), and (3) we shave a |S| factor by introducing s-absorbing MDPs for each state as in Agarwal et al. (2020a).

heading: 4.2 COMPARISON UNDER EXPERT DATA
text: We first compare the performance bounds from Section 4.1 when the offline dataset is generated from expert demonstrations. In relation to Condition 3.1, this corresponds to small C∗. Specifically, we considerC∗ ∈ [1, 1+Õ(1/N)] so that the suboptimality of BC in Theorem 4.1 scales as Õ(|S|H/N). In this regime, we perform a nuanced comparison by analyzing specific scenarios where RL may outperform BC. We consider the case of C∗ = 1 and C∗ = 1 + Õ(1/N) separately. What happens when C∗ = 1? In this case, we derive a information-theoretic lower-bound of |S|H/N for any offline algorithm. Our result in Theorem 4.3 utilizes the analysis of Rajaraman et al. (2020) but additionally factoring in Condition 3.2. Theorem 4.3 (Information-theoretic lower-bound for offline learning with C∗ = 1). For any learner π̂, there exists an MDPM satisfying Assumption 3.2, and a deterministic expert π∗, such that the expected suboptimality of the learner is lower-bounded:
sup M,π∗ SubOpt(π̂) & |S|H N
The proof of Theorem 4.3 uses the same hard instance from Theorem 6.1 of Rajaraman et al. (2020), except that one factor of H is dropped due to Condition 3.2. The other factor of H arises from the performance difference lemma and is retained. In this case, where BC achieves the lower bound up to logarithmic factors, we argue that we cannot improve over BC. This is because the suboptimality of BC is entirely due to encountering states that do not appear in the dataset; without additional assumptions on the ability to generalize to unseen states, offline RL must incur the same suboptimality, as both methods would choose actions uniformly at random.
Practical Insight 4.1. When no assumptions are made on the environment structure, both offline RL and BC perform equally poorly with trajectories from an expert demonstrator.
However, we argue that even with expert demonstrations as data, C∗ = 1 is an unrealistic assumption. Naively, it seems plausible that the expert who collected the dataset did not perform optimally at every transition; this is often true for humans, or stochastic experts as -greedy of maximumentropy policies. In addition, a scenario where C∗ > 1 even though the expert behaves optimally is under distribution shift of the environment. One practical example of this is when the initial state distribution changes between dataset collection and evaluation (e.g., in robotics (Singh et al., 2020), or self-driving (Bojarski et al., 2016)). Since the normalized state-action marginals d∗(s,a), µ(s,a) are impacted by ρ(s), this would lead to C∗ > 1 even when the expert behaves exactly as π∗.
What happens when C∗ = 1 + Õ(1/N)? Here C∗ is small enough that BC still achieves the same optimal Õ(|S|H/N) performance guarantee. However, there is suboptimality incurred by BC for even states that appear in the dataset due to distribution shift, which allows us to argue about structural properties of MDPs that allow offline RL to perform better across those states, particularly for problems with large effective horizon H . We motivate one such structure below.
In several practical problem domains, the return of any trajectory can mostly be explained by the actions taken at a small fraction of states, which we call critical states. This can occur when there exist a large proportion of states where it is not costly to recover after deviating from the optimal trajectory, or when there exist a large volume of optimal trajectories. We give two example domains: robotic manipulation and navigation. In manipulation tasks such as grasping, if the robot is not near the object, it can take many different actions and still pick up the object by the end; this is because unless the object breaks, actions taken by the robot are typically reversible (Kalashnikov et al., 2018a). It is only at a few “critical states” when the robot grasps the object, where the robot should be careful to not drop and break the object. In navigation, there may exist multiple paths that end at the same goal, particularly in large, unobstructed areas (Savva et al., 2019). For example, while navigating through a wide tunnel, the exact direction the agent takes may not matter so much as multiple directions will take the agent through the tunnel, in contrast, there are “critical states” like narrow doorways where taking a specific action is important. An illustration is shown in Figure 3. Domains that do not satisfy this structure include cliffwalk environments, where a incorrect action at any state will cause the agent to fall off the cliff (Schaul et al., 2015). Formally: Definition 4.1 (Critical states). A state s is said to be non-critical, i.e., s ∈ S \ C if the advantage of any action a ∈ A is close to 0 under the optimal policy, i.e, |maxa′ Q∗(s,a′)−Q∗(s,a)| ≤ ε/H .
Condition 4.1 (Volume of critical states is small.). ∃pc ∈ (0, 1) that satisfies: |C| ≤ pc|S|. We can show that, if the MDP satisfies having a small fraction or volume of critical states, then conservative offline RL enjoys stronger guarantees than BC. Corollary 4.1 (Performance of conservative offline RL with critical states). Under Conditions 4.1, 3.1 and 3.2, a policy π̂∗ found by the conservative offline RL can satisfy
SubOpt(π̂∗) ≤ √ pcC∗|S|Hι
N + pcC ∗|S|Hι N + ε .
For ε = O( √ H), if the environment satisfies pc = O(1/ √ H), meaning we encounter O( √ H) critical states on average in any trajectory, then we achieve better scaling in H with offline RL than BC. Note that BC does not enjoy the benefit of few critical states because it is agnostic to the reward of the environment and therefore limited by the O(H) suboptimality of the behavior policy.
Practical Insight 4.2. Offline RL is preferred over BC, even with expert or near-expert data, when either the initial state distribution changes during deployment and when the environment has a few “critical” states, i.e., states where precisely taking the expert action is necessary.

heading: 4.3 COMPARISON UNDER NOISY DATA
text: In practice, it is often much more tractable to obtain suboptimal demonstrations rather than expert ones. From Theorem 4.1, we see that for C∗ = 1 + Ω(1/ √ N), BC will incur suboptimality that is worse asymptotically than offline RL. In constrast, from Theorem 4.2, we note that offline RL does not scale nearly as poorly with increasing C∗. Since offline RL is not as reliant on the performance of the behavior policy due to explicitly modeling the rewards, we hypothesize that RL can actually benefit from suboptimal data that is well-explored. In this section, we aim to answer the following question: Can offline RL with suboptimal data outperform BC with an equal amount of expert data?
We show in Corollary 4.2 that if the suboptimal dataset D satisfies an additional coverage condition, then running conservative offline RL can attain Õ( √ H) suboptimality in the horizon. This implies, perhaps surprisingly, that for long horizon tasks, offline RL using noisy, suboptimal data can outperform even BC on expert data. Formally, our coverage condition is the following: Condition 4.2 (Coverage of the optimal policy). ∃b ∈ [logH/N, 1) such that µ satisfies: ∀(s,a) ∈ S ×A where d∗(s,a) ≥ b/H , we have µ(s,a) ≥ b. Intuitively, this means that the data distribution puts sufficient mass on states that have non-negligible density in the optimal policy distribution. Note that this is a weaker condition than prior works that require (1) full coverage of the state-action space, and (2) enforce a constraint on the empirical state-action visitations µ̂(s,a) instead of µ(s,a) (Ren et al., 2021; Zhang et al., 2021). This condition is reasonable when the dataset is collected by -greedy or a maximum-entropy expert, which is a standard assumption in MaxEnt IRL (Ziebart et al., 2008). Even if the expert is not noisy, we argue that in several real-world applications, creating noisy-expert data is feasible. In many robotics applications, it is practical to augment expert demonstrations with counterfactual data by using scripted exploration policies (Kalashnikov et al., 2018a; 2021). Existing work has also simulated trajectories to increase coverage, as was done in self-driving by perturbing the vehicle location (Bojarski et al., 2016), or in robotics using learned simulators (Rao et al., 2020). For intuition, we provide an illustrative example of the noisy data that can help offline RL in Figure 4. Corollary 4.2 (Performance of conservative offline RL with noisy data). If µ satisfies Condition 4.2, and under Conditions 3.1 and 3.2, the policy π̂∗ found by conservative offline RL can satisfy:
SubOpt(π̂∗) .
√ Hι
bN + Hι bN + √ bι+ C∗|S|ι N .
For some b, offline RL can improve upon the lower-bound for BC in Theorem 4.3, e.g, if b = O( √ H/N), then the bound in Corollary 4.2 has Õ( √ H) scaling rather than Õ(H) for BC. Thus, when the data satisfies the practical coverage conditions (more discussion in Appendix D), offline RL performs better in long-horizon tasks compared to BC with the same amount of expert data.
Practical Insight 4.3. Offline RL outperforms BC on expert data on long-horizon tasks, when provided with an equal amount of noisy-expert data. So, if noisy-expert data is easy to collect, doing so and running offline RL can be a much better option.

heading: 4.4 COMPARISON OF GENERALIZED BC METHODS AND OFFLINE RL
text: So far we have studied scenarios where offline RL can outperform naive BC. One might now wonder how offline RL methods perform relative to generalized BC methods that additionally use reward information to inform learning. We study two such approaches: (1) filtered BC (Chen et al., 2021), which only fits to the top k-percentage of trajectories in D, measured by the total reward, and (2) BC with one-step policy improvement (Brandfonbrener et al., 2021), which fits a Q-function for the behavior policy, then uses the values to perform one-step of policy improvement over the behavior policy. In this section, we aim to answer how these methods perform relative to RL.
Filtered BC. In expectation, this algorithm uses αN samples of the offline dataset D for α ∈ [0, 1] to perform BC on. This means that the upper bound (Theorem 4.1) will have worse scaling in N . For C∗ = 1, this leads to a strictly worse bound than regular BC. However, for suboptimal data, the filtering step could decrease C∗ by filtering out suboptimal trajectories, allowing filtered BC to outperform traditional BC. Nevertheless, from our analysis in Section 4.3, offline RL is still preferred to filtered BC because RL can leverage the noisy data and potentially achieve sub-linear suboptimality O( √ H) in the horizon, whereas even filtered BC would always incur O(H) suboptimality.
BC with policy improvement. This algorithm utilizes the entire dataset to estimate the Q-value of the behavior policy, Q̂π̂β , and performs one step of policy improvement using the estimated Q-function, typically via an advantage-weighted update: π̂1(a|s) = π̂β(a|s) exp(ηHÂπ̂β (s,a))/Z1(s). When would this algorithm perform poorly compared to offline RL? Intutively, this would happen when multiple steps of policy improvement are needed to effectively discover high-advantage actions under the behavior policy. This is the case when the the behavior policy puts low density on high-advantage transitions. In Theorem 4.4, we show that more than one step of policy improvement can improve the policy under Condition 4.2 for the softmax policy parameterization (Agarwal et al., 2021a).
Theorem 4.4 (One-step is worse than k-step policy improvement). Assume that the learned policies are represented via a softmax parameterization (Equation 3, Agarwal et al. (2021a)). Let π̂k denote the policy obtained after k-steps of policy improvement using exponentiated advantage weights. Then, under Condition 4.2, the performance difference between π̂k and π̂1 is lower-bounded by:
J(π̂k)− J(π̂1) & k Hη Es∼µ
[ 1
k k∑ t=1 logZt(s)
] − √ C∗Hι
N .
A proof of Theorem 4.4 is provided in Appendix B.5. This result implies that when the average exponentiated empirical advantage 1/k ∑k i=1 logZt(s) is large enough (i.e., ≥ c0 for some universal constant), which is usually the case when the behavior policy is highly suboptimal, then for k = O(H), multiple steps of policy improvement will improve performance, i.e., J(π̂k) − J(π̂1) = Õ(H − √ H/N), where the gap increases with a longer horizon. This is typically the case when the structure of the MDP allow for stitching parts of poor-performing trajectories. One example is in navigation, where trajectories that fail may still contain segments of a successful trajectory.
Practical Insight 4.4. Using multiple policy improvement steps (i.e., full offline RL) can lead to greatly improved performance on long-horizon tasks, particularly when parts of various trajectories can be concatenated or stitched together to give better performance.

heading: 5 EMPIRICAL EVALUATION OF BC AND OFFLINE RL
text: Having characterized scenarios where at least some offline RL algorithms can outperform BC in theory, we now validate our results empirically. Concretely, we aim to answer the following questions: (1) Does some offline RL method trained on expert data outperform BC on expert data in practice? (2) Can offline RL trained on noisy data outperform BC on expert data?, and (3) How does full offline RL compare to the generalized BC methods studied in Section 4.4? We will first validate our findings on a tabular gridworld domain, and then on several high-dimensional offline RL problems.
Diagnostic experiments in gridworld. We first evaluate tabular versions of the BC and offline RL methods analyzed in Section 4.1 on sparse-reward 10 × 10 gridworlds environments (Fu et al., 2019). Complete details about the setup can be found in Appendix E.1. On a high-level, we consider three different environments, each with varying number of critical states, from “Single Critical” with
exactly one, to “Cliffwalk” where every state is critical and veering off yields zero reward. The methods we consider are: naive BC (BC), conservative RL (RL-C), policy-constraint RL (RL-PC), and generalized BC with one-step and k-step policy improvement (BC-PI, BC-kPI).
In the left plot of Figure 1, we show the return (normalized by return of the optimal policy) across all the different environments for optimal data (C∗ = 1) and data generated from the optimal policy but with a different initial state distribution (C∗ > 1 but πβ(·|s) = π∗(·|s)). As expected from our discussion in Section 4.2, BC performs best under C∗ = 1, but RL-C and RL-PC performs much better when C∗ > 1; also BC with one-step policy improvement outperforms naive BC for C∗ > 1, but does not beat RL. In Figure 1 (right), we vary C∗ by interpolating the dataset with one generated by a random policy, where α is the proportion of random data. RL performs much better over all BC methods, when the data supporting our analysis in Section 4.3. Finally, BC with multiple policy improvement steps performs better than one step when the data is noisy, which validates Theorem 4.4.
Evaluation in high-dimensional tasks. Next, we turn to deep offline RL. We consider a diverse set of domains (shown on the right) and behavior policies that are representative of scenarios where we would decide between offline RL and BC: multi-stage robotic manipulation tasks from state (Adroit domains from Fu et al. (2020)) and image observations (Singh et al., 2020), antmaze navigation (Fu et al., 2020), and 7 Atari games (Agarwal et al., 2020b). We use the scripted expert provided by Fu et al. (2020) for antmaze and the one provided by Singh et al. (2020) for manipulation, an RL-trained expert for Atari, and human expert for Adroit (Rajeswaran et al., 2018). In scenarios where suboptimal data is used to train offline RL, we use failed attempts to solve the task from a noisy expert policy (i.e., previous policies in the replay buffer for Atari, and noisy scripted experts for antmaze and manipulation). All these tasks utilize sparse rewards such that the return of any trajectory is bounded by a constant much smaller than the horizon. We use CQL (Kumar et al., 2020) as a representative offline RL method, and utilize Brandfonbrener et al. (2021) as a representative BC-PI method.
Tuning offline RL and BC. Naı̈vely running offline RL can lead to poor performance, as noted by prior works (Mandlekar et al., 2021; Florence et al., 2021). This is also true for BC, but, some solutions such as early stopping based on validation losses, can help improve performance. We claim that a similar tuning strategy is also crucial for offline RL. In our experiments we utilize the offline workflow proposed by Kumar et al. (2021c) to perform policy selection, and address overfitting and underfitting, purely offline. When the Q-values learned by CQL are extremely negative (typically on the Adroit domains), we utilize dropout with probability 0.4 on the layers of the Q-function to combat overfitting. On the other hand, when the Q-values exhibit a relatively stable trend (e.g., in Antmaze or Atari), we utilize the DR3 regularizer (Kumar et al., 2021a) to increase capacity. Consistent with prior work, we find that naı̈ve offline RL generally performs worse than BC without offline tuning, but we find that offline-tuned offline RL generally outperforms BC. To make a stronger comparison, we tuned BC using the online rollouts. We applied regularizers such as dropout on the BC policy to prevent overfitting in Adroit, and utilized a larger ResNet (He et al., 2016) architecture for the robotic manipulation tasks and Atari domains. For BC, we report the performance of the best checkpoint found during training, giving BC an unfair advantage, but we still find that offline-tuned offline RL performs better. More details about tuning can be found in Appendix F.
Answers to questions (1) to (3). For (1), we run CQL and BC on expert data in each task, and present the comparison in Table 1 and Figure 2. While naı̈ve CQL performs comparable or worse than BC in this case, after offline tuning, CQL outperforms BC. This tuning does not require any
additional online rollouts. Note that while BC performs better or comparable to RL for antmaze (large) with expert data, it performs worse than RL when the data admits a more diverse initial state distribution such that C∗ 6= 1, even though the behavior policy matches the expert.
For (2), we compare offline RL trained on noisyexpert data with BC trained on on an equal amount of expert data, on domains where noisyexpert data is easy to generate: (a) manipulation domains (Table 2) and (b) Atari games (Figure 2). Observe that CQL outperforms BC and also improves over only using expert data. The
performance gap also increases withH , i.e., open-grasp (H = 40) vs pick-place-open-grasp (H = 80) vs Atari domains (H = 27000). This validates that some form of offline RL with noisy-expert data can outperform BC with expert data, particularly on long-horizon tasks.
Finally, for (3), we compare CQL to a representative BC-PI method (Brandfonbrener et al., 2021) trained using noisy-expert data on Atari domains, which present multiple stitching opportunities. The BC-PI method estimates the Q-function of the behavior policy using SARSA and then performs one-step of policy improvement. The results in Figure 2 support what is predicted by our theoretical results, i.e., BC-PI still performs significantly worse than CQL with noisy-expert data, even though we utilized online rollouts for tuning BC-PI and report the best hyperparameters found.

heading: 6 DISCUSSION
text: We sought to understand if offline RL is at all preferable over running BC, even provided with expert or near-expert data. While in the worst case, both methods attain similar performance on expert data, additional assumptions on the environment can provide certain offline RL methods with an advantage. We also show that running RL on noisy-expert, suboptimal data attains more favorable guarantees compared to running BC on expert data for the same task, using equal amounts of data. Empirically, we observe that offline-tuned CQL can outperform BC on various practical problem domains, with different kinds of expert policies. While our work is an initial step towards understanding when RL presents a favorable approach, there is still plenty of room for further investigation. Our theoretical analysis can be improved to handle function approximation. Understanding if offline RL is preferred over BC for other real-world data distributions is also important. Finally, our work focuses on analyzing cases where we might expect offline RL to outperform BC. An interesting direction is to understand cases where the opposite holds; such analysis would further contribute to this discussion.

heading: REPRODUCIBILITY STATEMENT
text: For theoretical results, we provide explanations of all the assumptions and a complete proof of the claims in Appendix B. We provide complete experimental details regarding the tasks and tuning strategy in the Appendix F. Additionally, we follow the recommendations of Agarwal et al. (2021b) for reliable evaluation in deep RL and report the statistical uncertainty in reported results including aggregate performance metrics (Figure 2). We provide individual scores in Table 3 and we will open-source our code.

heading: A PSEUDOCODE FOR ALGORITHMS
text: Algorithm 1 Conservative Offline RL Algorithm Require: Offline dataset D, discount factor γ, and confidence level δ 1: Compute n(s,a) from D, and estimate r̂(s,a), P̂ (s′|s,a), ∀(s,a) ∈ S ×A 2: Initialize Q̂(s,a)← 0, V̂ (s)← 0, ∀(s,a) 3: for i = 1, 2, . . . ,m do
Calculate b(s,a) as:
b(s,a)←
√ V(P̂ (s,a), V̂ ) log(|S||A|m/δ))
(n(s,a) ∧ 1) +
√ r̂(s,a) log(|S||A|m/δ)
(n(s,a) ∧ 1) + log(|S||A|m/δ) (n(s,a) ∧ 1)
Calculate π̂∗(s) as:
Q̂(s,a)← r̂(s,a)− b(s,a) + γP̂ (s,a) · V̂
V̂ (s)← max a Q̂(s,a)
π̂∗(s)← argmax a Q̂(s,a)
4: Return π̂∗
Algorithm 2 Policy-Constraint Offline RL Algorithm Require: Offline dataset D, discount factor γ, and threshold b 1: Compute n(s,a) from D, and estimate r̂(s,a), P̂ (s′|s,a), µ̂(s,a), ∀(s,a) ∈ S ×A 2: Compute ζ(s,a)← 1{µ̂(s,a) ≥ b} , ∀(s,a) 3: Initialize π̂∗(a|s)← 1|A| , Q̂ π̂∗ ζ (s,a)← 0, V̂ π̂ ∗ ζ (s)← 0, ∀(s,a)
4: for ` = 1, 2, . . . , k do 5: for i = 1, 2, . . . ,m do
Update Q̂π̂ ∗ ζ (s,a), V̂ π̂∗ ζ (s) as:
Q̂π̂ ∗ ζ (s,a)← r̂(s,a) + γP̂ (s,a) · V̂ π̂ ∗ ζ
V̂ π̂ ∗ ζ (s)← ∑ a π̂∗(a|s)ζ(s,a) · Q̂(s,a)
Compute π̂∗ as:
π̂∗ ← argmax π
Es∼D [ Ea∼π′ [ ζ(s,a) · Q̂πζ (s,a) ]] 6: Return π̂∗.

heading: B PROOFS

heading: B.1 PROOF OF THEOREM 4.1
text: Let πβ be the behavior policy that we fit our learned policy π̂β to. Recall that the BC algorithm we analyze fits π̂β to choose actions according to the empirical dataset distribution for states that appear in dataset D, and uniformly at random otherwise. We have
ED [J(π∗)− J(π̂β)] ≤ J(π∗)− J(πβ) + ED [J(πβ)− J(π̂β)] The following lemma from Rajaraman et al. (2020) bounds the suboptimality from performing BC on a (potentially stochastic) expert, which we adapt below factoring in bounded returns of trajectories from Condition 3.2. Lemma B.1 (Theorem 4.4, Rajaraman et al. (2020)). The policy returned by BC on behavior policy πβ has expected error bounded as
ED [J(πβ)− J(π̂β)] ≤ SH logN
N ,
where πβ could be stochastic.
Using Lemma B.1, we have ED [J(πβ)− J(π̂β)] ≤ SHι/N . What remains is bounding the suboptimality of the behavior policy, which we can upper-bound as
J(π∗)− J(πβ) ≤ ∞∑ t=0 ∑ s γtP (st = s)Eπβ(·|s) [1{a 6= π ∗ t (s)}]
= 1
2 ∞∑ t=0 ∑ s γtd∗t (s) ∑ a |πβ(a|s)− 1{a = π∗t (s)}|
= 1
2 ∞∑ t=0 ∑ (s,a) γt |d∗t (s)πβ(a|s)− d∗t (s,a)|
≤ C ∗ − 1 2 H ∑ (s,a) µ(s,a)
= (C∗ − 1)H
2 ,
where we use the definition of C∗ in Condition 3.1. Taking the sum of both terms yields the desired result.

heading: B.2 PROOF OF THEOREM 4.2
text: In this section, we proof the performance guarantee for the conservative offline RL algorithm detailed in Algorithm 1. Recall that the algorithm we consider builds upon empirical value iteration but subtracts a penalty during each Q-update. Specifically, we initialize Q0(s,a) = 0, V0(s) = 0 for all (s,a). Let n(s,a) be the number of times (s,a) appeared in D, and let r̂(s,a), P̂ (s,a) be the empirical estimates of their reward and transition probabilities. Then, for each iteration i ∈ [m]:
Q̂i(s,a)← r̂(s,a)−bi(s,a) + γP̂ (s,a) · V̂i−1, for all s,a, V̂i(s)← max{V̂t−1(s),max
a Q̂i(s,a)}, for all s,
In our algorithm we define the penalty function as
bi(s,a)←
√ V(P̂ (s,a), V̂i−1)ι
(n(s,a) ∧ 1) +
√ r̂(s,a)ι
(n(s,a) ∧ 1) +
ι
(n(s,a) ∧ 1) ,
where we let ι to capture all poly-logarithmic terms. As notation, we drop the subscript i to denote the final Q̂ and V̂ at iteration m, where m = H logN . Finally, the learned policy π̂∗ satisfies π̂∗(s) ∈ arg maxa Q̂(s,a) for all s, if multiple such actions exist, then the policy samples an action uniformly at random.

heading: B.2.1 TECHNICAL LEMMAS
text: Lemma B.2 (Bernstein’s inequality). Let X, {Xi}ni=1 be i.i.d random variables with values in [0, 1], and let δ > 0. Then we have
P (∣∣∣∣∣E [X]− 1n n∑ i=1 Xi ∣∣∣∣∣ > √ 2Var [X] log(2/δ) n + log(2/δ) n ) ≤ δ .
Lemma B.3 (Theorem 4, Maurer & Pontil (2009)). Let X, {Xi}ni=1 with n ≥ 2 be i.i.d random variables with values in [0, 1]. Define X̄ = 1n ∑n i=1Xi and V̂ar(X) = 1 n ∑n i=1(Xi − X̄)2. Let δ > 0. Then we have
P ∣∣∣∣∣E [X]− 1n n∑ i=1 Xi ∣∣∣∣∣ > √ 2V̂ar(X̄) log(2/δ) n− 1 + 7 log(2/δ) 3(n− 1)  ≤ δ .
Lemma B.4 (Lemma 4, Ren et al. (2021)). Let λ1, λ2 > 0 be constants. Let f : Z≥0 → R be a function such that f(i) ≤ H, ∀i and f(i) satisfies the recursion
f(i) ≤ √ λ1f(i+ 1) + λ1 + 2 i+1λ2 .
Then, we have that f(0) ≤ 6(λ1 + λ2).

heading: B.2.2 PESSIMISM GUARANTEE
text: The first thing we want to show is that with high probability, the algorithm provides pessimistic value estimates, namely that V̂i(s) ≤ V ∗(s) for all t ∈ [T ] and s ∈ S . To do so, we introduce a notion of a “good” event, which occurs when our empirical estimates of the MDP are not far from the true MDP. We define E1 to be the event where∣∣∣(P̂ (s,a)− P (s,a)) · V̂i∣∣∣ ≤ √ V(P̂ (s,a), V̂i)ι (n(s,a) ∧ 1) + ι (n(s,a) ∧ 1) (2)
holds for all i ∈ [m] and (s,a) ∈ S ×A. We also define E2 to be the event where
|r̂(s,a)− r(s,a)| ≤
√ r̂(s,a)ι
(n(s,a) ∧ 1) +
ι
(n(s,a) ∧ 1) (3)
holds for all (s,a).
We want to show that the good event E = E1 ∩ E2 occurs with high probability. The proof mostly follows from Bernstein’s inequality in Lemma B.2 . Note that because P̂ (s,a), V̂i are not independent, we cannot straightforwardly apply Bernstein’s inequality. We instead use the approach of Agarwal et al. (2020a) who, for each state s, partition the range of V̂i(s) within a modified s-absorbing MDP to create independence from P̂ . The following lemma from Agarwal et al. (2020a) is a result of such analysis, and is slightly modified below to account for bounded returns of trajectories, i.e., V̂i(s) ≤ 1: Lemma B.5 (Lemma 9, Agarwal et al. (2020a)). For any iteration t, state-action (s,a) ∈ S × A such that n(s,a) ≥ 1, and δ > 0, we have
P ∣∣∣(P̂ (s,a)− P (s,a)) · V̂i∣∣∣ > √
V(P̂ (s,a), V̂i)ι n(s,a) + ι n(s,a)  ≤ δ . Using this, we can show that E occurs with high probability: Lemma B.6. P (E) ≥ 1− 2|S||A|mδ.
Proof. For each i and (s,a), if n(s,a) ≤ 1, then equation 2 and equation 3 hold trivially. For n(s,a) ≥ 2, we have from Lemma B.5 that
P ∣∣∣(P̂ (s,a)− P (s,a)) · V̂i∣∣∣ > √
V(P̂ (s,a), V̂i)ι n(s,a) + ι n(s,a)  ≤ δ . Similarly, we can use Lemma B.3 to derive
P ( |r̂(s,a)− r(s,a)| > √ r̂(s,a)ι
n(s,a) +
ι
n(s,a)
)
≤ P |r̂(s,a)− r(s,a)| > √ V̂ar(r̂(s,a))ι
2(n(s,a)− 1) +
ι
2(n(s,a)− 1)  ≤ δ , where we use that V̂ar(r̂(s,a)) ≤ r̂(s,a) for [0, 1] rewards, and with slight abuse of notation, let ι capture all constant factors. Taking the union bound over all i and (s,a) yields the desired result.
Now, we can prove that our value estimates are indeed pessimistic.
Lemma B.7 (Pessimism Guarantee). On event E , we have that V̂i(s) ≤ V π̂ ∗ (s) ≤ V ∗(s) for any iteration i ∈ [m] and state s ∈ S.
Proof. We aim to prove the following for any i and s: V̂i−1(s) ≤ V̂i(s) ≤ V π̂ ∗ (s) ≤ V ∗(s). We prove the claims one by one.
V̂i−1(s) ≤ V̂i(s): This is directly implied by the monotonic update of our algorithm.
V̂i(s) ≤ V π̂ ∗ (s): We will prove this via induction. We have that this holds for V̂0 trivially. Assume it holds for t− 1, then we have
V π̂ ∗ (s) ≥ Ea∼π̂∗(·|s) [ r(s,a) + γP (s,a) · V̂i−1 ] ≥ Ea [ r̂(s,a)− bi(s,a) + γP̂ (s,a) · V̂t−1 ] +
Ea [ bi(s,a)− (r̂(s, a)− r(s,a))− γ(P̂ (s,a)− P (s,a)) · V̂i−1 ] ≥ V̂t(s) ,
where we use that
bi(s,a) =
√ V(P̂ (s,a), V̂i−1)ι
(n(s,a) ∧ 1) +
√ r̂(s,a)ι
(n(s,a) ∧ 1) +
ι
(n(s,a) ∧ 1)
≥ (r̂(s, a)− r(s,a)) + γ(P̂ (s,a)− P (s,a)) · V̂i−1 under event E . Finally, the claim of V π̂ ∗ (s) ≤ V ∗(s) is trivial, which completes the proof of our pessimism guarantee.
B.2.3 VALUE DIFFERENCE LEMMA
Now, we are ready to derive the performance guarantee from Theorem 4.2. The following lemma is a bound on the estimation error of our pessimistic Q-values. Lemma B.8. On event E , the following holds for any i ∈ [m] and (s,a) ∈ S ×A:
Q∗(s,a)− Q̂i(s,a) ≤ γP (s,a) · (Q∗(·;π∗)− Q̂i−1(·;π∗)) + 2bi(s,a) , (4)
where f(·;π) satisfies f(s;π) = ∑
a π(a|s)f(s,a).
Proof. We have,
Q∗(s,a)− Q̂i(s,a) = r(s,a) + γP (s,a) · V ∗ − (r̂(s,a)− bi(s,a) + γP̂ (s,a) · V̂t−1) = bi(s,a) + r(s,a)− r̂(s,a) + γP (s,a) · (V ∗ − V̂t−1) + γ(P (s,a)− P̂ (s,a)) · V̂t−1 ≤ γP (s,a) · (V ∗ − V̂t−1) + 2bi(s,a) ≤ γP (s,a) · (Q∗(·;π∗)− Q̂t−1(·;π∗)) + 2bi(s,a) .
The first inequality is due by definition of E and the second is because V̂t−1 ≥ maxa Q̂t−1(·, a) ≥ Q̂i(·, π∗).
By recursively applying Lemma B.8, we can derive the following value difference lemma: Lemma B.9 (Value Difference Lemma). On event E , at any iteration i ∈ [m], we have
J(π∗)− J(π̂∗) ≤ γi + 2 i∑ t=1 ∑ (s,a) γi−td∗i−t(s,a)bt(s,a) , (5)
where d∗t (s,a) = P (st = s,at = a;π∗).
Proof. We have, J(π∗)− J(π̂∗) = Eρ [ V ∗(s)− V π̂ ∗ (s) ] ≤ Eρ [ V ∗(s)− V̂i(s) ] ≤ ρ(Q∗(·;π∗)− Q̂i(·;π∗))
where we use Lemma B.7 in the first inequality. As shorthand, let Pπ ∈ R(S×A)×(S×A) where Pπ(s,a, s′, a′) = P (s′|s,a)π(a′|s′) be the transition matrix for policy π. Now, we can apply Lemma B.8 recursively to derive
ρπ ∗ (Q∗ − Q̂i) ≤ ρπ ∗ ( γPπ ∗ (Q− Q̂i−1) + 2bi ) ≤ ρπ ∗ ( γPπ ∗ ( γPπ ∗ (Q∗ − Q̂i−2) + 2bi−1 ) + 2bi
) ≤ . . .
≤ ρπ ∗ (γPπ ∗ )i(Q∗ − Q̂0) + 2 i∑ t=1 ρπ ∗ (γPπ ∗ )i−tbt
≤ γi1 + 2 i∑ t=1 γi−td∗i−tbt
where we use that d∗t = ρ π∗(Pπ ∗ )t. This yields the desired result.
Now, we are ready to bound the desired quantity SubOpt(π̂∗) = ED [J(π∗)− J(π̂∗)]. We have
ED [J(π∗)− J(π̂∗)] = ED [∑ s ρ(s)(V ∗(s)− V π̂ ∗ (s)) ] (6)
= ED [ 1 { Ē }∑
s
ρ(s)(V ∗(s)− V π̂ ∗ (s)) ] :=∆1
+ ED [ 1{∃s ∈ S, n(s, π∗(s)) = 0}
∑ s ρ(s)(V ∗(s)− V π̂ ∗ (s)) ] :=∆2
+ ED [ 1{∀s ∈ S, n(s, π∗(s)) > 0} 1{E}
∑ s ρ(s)(V ∗(s)− V π̂ ∗ (s)) ] :=∆3 .
We bound each term individually. The first is bounded as ∆1 ≤ P ( Ē ) ≤ 2|S||A|mδ ≤ ιN for choice of δ = 12|S||A|HN .
B.2.4 BOUND ON ∆2
For the second term, we have ∆2 ≤ ∑ s ρ(s)ED [1{n(s, π∗(s)) = 0}]
≤ H ∑ s d∗(s, π∗(s))ED [1{n(s, π∗(s)) = 0}]
≤ C∗H ∑ s µ(s, π∗(s))(1− µ(s, π∗(s)))N ≤ 4C ∗|S|H 9N ,
where we use that ρ(s) ≤ Hd∗(s, π∗(s)) , and that maxp∈[0,1] p(1− p)N ≤ 49N .
B.2.5 BOUND ON ∆3
What remains is bounding the last term, which we know from Lemma B.9 is bounded by
∆3 ≤ 1
N + 2ED 1{∀s ∈ S, n(s, π∗(s)) > 0} m∑ t=0 ∑ (s,a) γm−td∗m−t(s,a)bt(s,a)  , where we use that γm ≤ 1N for m = H logN . Recall that bt(s,a) is given by
bt(s,a) =
√ V(P̂ (s,a), V̂t−1)ι
n(s,a) +
√ r̂(s,a)ι
n(s,a) +
ι
n(s,a)
We can bound the summation of each term separately. For the third term we have,
ED  m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a) ι n(s,a)  ≤ m−1∑ t=0 ∑ (s,a) γtd∗t (s,a)ED [ ι n(s,a) ]
≤ ∑ s ∞∑ t=0 γtd∗t (s, π ∗(s))
ι
Nµ(s, π∗(s))
≤ Hι N ∑ s
( (1− γ)
∞∑ t=0 γtd∗t (s, π ∗(s))
) 1
µ(s, π∗h(s))
≤ C ∗|S|Hι N .
Here we use Jensen’s inequality and that (1− γ) ∑∞ t=1 γ
td∗t (s,a) ≤ C∗µ(s,a) for any (s,a). For the second term, we similarly have
ED  m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a) √ r̂(s,a)ι n(s,a)  ≤ ED
√√√√ m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a) ι n(s,a)  √√√√ m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a)r̂(s,a)
≤ √ C∗|S|Hι
N ,
where we use Cauchy-Schwarz, then Condition 3.2 to bound the total estimated reward. Finally, we consider the first term of bt(s,a)
ED  m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a) √ V(P̂ (s,a), V̂t−1)ι n(s,a)  ≤ ED
√√√√ m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a) ι n(s,a)  √√√√ m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a)V(P̂ (s,a), V̂t−1)
≤ √ C∗|S|Hι
N
√√√√ m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a)V(P̂ (s,a), V̂t−1) .
Similar to what was done in Zhang et al. (2020); Ren et al. (2021) for finite-horizon MDPs, we can bound this term using variance recursion for infinite-horizon ones. Define
f(i) := ∞∑ t=1 ∑ (s,a) γm−td∗m−t(s,a)V(P̂ (s,a), (V̂t−1)2 i ) . (7)
Using Lemma 3 of Ren et al. (2021) for the infinite-horizon case, we have the following recursion: f(i) ≤ √ C∗|S|Hι
N f(i+ 1) + C∗|S|Hι N + 2i+1(Φ + 1) ,
where
Φ :=
√ C∗|S|Hι
N
√√√√ m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a)V(P̂ (s,a), V̂t−1) + C∗|S|Hι N (8)
Using Lemma B.4, we can bound f(0) = O ( C∗|S|Hι N + Φ + 1 ) . Using that for constant c,
Φ =
√ C∗|S|Hι
N f(0) + C∗|S|Hι N
≤
√ C∗|S|Hι
N
( cC∗|S|Hι
N + cΦ + c
) + C∗|S|Hι
N
≤ cΦ 2
+ 2cC∗|S|Hι
N + c 2
we have that
Φ ≤ c+ 4cC ∗|S|Hι N .
Substituting this back into the inequality for Φ yields,
Φ = O
(√ C∗|S|Hι
N + C∗|S|Hι N
)
Finally, we can bound
∆3 ≤ √ C∗|S|Hι
N + C∗|S|Hι N .
Combining the bounds for the three terms yields the desired result.

heading: B.3 PROOF OF COROLLARY 4.1
text: The proof of Corollary 4.1 mostly relies on the existing machinery in Appendix B.2. In this section, we will only point out the differences and defer details to the comprehensive proof in Appendix B.2. Recall that C is the set of critical states, and from Definition 4.1, that all s ∈ S \ C satisfy having negligible advantage, i.e., Q∗(s, π∗(s))−Q∗(s,a) ≤ ε/H for any suboptimal action a. Recall that for anyQ, π, we use the notationQ(s;π) = Ea∼π [Q(s, a)]. The main difference between this proof and the one for Theorem 4.2 is that under the critical point structure outlined in Section 4.2, we can handle critical and non-critical states differently to derive a tighter bound. Namely, we bound the suboptimality using:
J(π∗)− J(π̂∗) = H ∑ s ¯ ∈S dπ̂ ∗ (s) (Q∗(s;π∗)−Q∗(s; π̂∗))
≤ H ∑ s∈C dπ̂ ∗ (s) (Q∗(s;π∗)−Q∗(s; π̂∗)) +H ∑ s6∈C dπ̂ ∗ (s) ε H
= H ∑ s∈C dπ̂ ∗ (s) (Q∗(s;π∗)−Q∗(s; π̂∗)) + ε
= H ∑ s∈C d∗(s) ( Qπ̂ ∗ (s;π∗)−Qπ̂ ∗ (s; π̂∗) ) + ε ,
where we use the performance difference lemma, then condition on whether a state is critical. We propose an alternative interpretation for the bound. The first term is the value difference under a
modified MDP where the advantage for all states that are non-critical is 0. One way to construct such an MDP is to take each s 6∈ C and modify the reward and transitions so that r(s,a) = r(s, π∗(s)), P (s,a) = P (s, π∗(s)) for all actions. Let us denote the performance function for this modified MDP be JC , then we have J(π∗)− J(π̂∗) ≤ JC(π∗)− JC(π̂∗) + ε The first term can be bounded as was done in Appendix B.2. Namely, we can show the following equivalent of Lemma B.9:
JC(π ∗)− JC(π̂∗) ≤ γi + 2 i∑ t=1 ∑ s∈C γi−td∗i−t(s, π ∗(s))bt(s, π ∗(s)) .
Bounding this for i = Hι can be done exactly as in was done in Appendix B.2.4 and B.2.5, except with the dependence on all states S replaced by C only the critical ones. We get the following bound:
JC(π ∗)− JC(π̂∗) ≤
√ C∗|C|Hι
N + C∗|C|Hι N
Combining the above result with Condition 4.1, which bounds |C| ≤ pc|S|, completes the proof.

heading: B.4 PROOF OF COROLLARY 4.2
text: The proof of Corollary 4.2 is a slight modification of the one for Theorem 4.2. For brevity, we will point out the parts of the proof that change, and simply defer to the proof in Appendix B.2 for parts that are similar. Recall the decomposition for suboptimality in equation 6, which we restate below:
ED [J(π∗)− J(π̂∗)] = ED [ 1 { Ē }∑
s
ρ(s)(V ∗(s)− V π̂ ∗ (s)) ] ∆1
+ ED [ 1{∃s ∈ S, n(s, π∗(s)) = 0}
∑ s ρ(s)(V ∗(s)− V π̂ ∗ (s)) ] ∆2
+ ED [ 1{∀s ∈ S, n(s, π∗(s)) > 0} 1{E}
∑ s ρ(s)(V ∗(s)− V π̂ ∗ (s)) ] ∆3 .
∆1 is bounded by ιN as before.
B.4.1 BOUND ON ∆2
The bound for ∆2 changes slightly from Appendix B.2.4 due to accounting for the lower-bound on µ(s,a) ≥ b ≥ logHN . We have
∆2 ≤ ∑ s ρ(s)ED [1{n(s, π∗(s)) = 0}]
≤ H ∑ s d∗(s, π∗(s))ED [1{n(s, π∗(s)) = 0}]
≤ H ∑ s d∗(s, π∗(s))1 { d∗(s, π∗(s)) ≤ b H } +H ∑ s d∗(s, π∗(s))ED [1{n(s, π∗(s)) = 0}]
≤ |S|c+ C∗H ∑ s µ(s, π∗(s))(1− µ(s, π∗(s)))N ≤ |S|b+ C ∗|S|ι N ,
where we use that ρ(s) ≤ Hd∗(s, π∗(s)) , and that
max p∈[ logHN ,1]
p(1− p)N ≤ logH N
( 1− logH
N
)N ≤ logH
HN .
B.4.2 BOUND ON ∆3
Due to the lower bound on µ(s,a) ≥ b, we can instead bound,
ED  m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a) ι n(s,a)  ≤ m−1∑ t=0 ∑ (s,a) γtd∗t (s,a)ED [ ι n(s,a) ]
≤ ∑ s ∞∑ t=0 γtd∗t (s, π ∗(s))
ι
Nµ(s, π∗(s))
≤ 1 { d∗(s,a) ≤ b
H } H ∑ s ( (1− γ) ∞∑ t=0 γtd∗t (s, π ∗(s)) ) +
Hι
Nc ∑ s
( (1− γ)
∞∑ t=0 γtd∗t (s, π ∗(s))
)
≤ b+ Hι bN .
The analysis for bounding ∆3 proceeds exactly as in Appendix B.2.5 but using the new bound. Namely, we end up with the recursion
f(i) ≤ √ Hι
bN + b
√ f(i+ 1) + Hι
bN + b+ 2i+1(Φ + 1) ,
where
Φ :=
√ Hι
bN + b √√√√ m∑ t=1 ∑ (s,a) γm−td∗m−t(s,a)V(P̂ (s,a), V̂t−1) + Hι Nb + b .
Using Lemma B.4 and proceeding as in Appendix B.2.5 yields the bound ∆3 ≤ √ Hι
bN + Hι bN + √ bι .
Combining the new bounds for ∆2,∆3 results in the bound in the Corollary 4.2.

heading: B.5 PROOF OF THEOREM 4.4
text: The proof of Theorem 4.4 builds on analysis by Agarwal et al. (2021a) that we apply to policies with a softmax parameterization, which we define below. Definition B.1 (Softmax parameterization). For a given θ ∈ R|S|×|A|, πθ(a|s) = exp(θs,a)∑ a′ exp(θs,a′ ) .
We consider generalized BC algorithms that perform advantage-weighted policy improvement for k improvement steps. A BC algorithm with k-step policy improvement is defined as follows:
Definition B.2 (BC with k-step policy improvement). Let Âk(s,a) denote the advantage of action a at state s under a given policy π̂k, where the policy π̂k(a|s) is defined via the recursion:
π̂k+1(a|s) := π̂k(a|s)exp(ηHÂ k(s,a))
Zk(s) ,
starting from π̂0(a|s) = π̂β . Then, BC with k-step policy improvement returns π̂k.
This advantage weighted update is utilized in practical works such as Brandfonbrener et al. (2021), which first estimates the Q-function of the behavior policy using the offline dataset, i.e, Q̂0(s,a), and then computes π̂1 as the final policy returned by the algorithm. To understand the performance difference between multiple values of k, we first utilize essentially Lemma 5 from Agarwal et al. (2021a), which we present below for completeness:
Lemma B.10 (Lower bound on policy improvement in the empirical MDP, M̂ ). The iterates π̂k generated by k-steps of policy improvement, for any initial state distributions ρ0(s) satisfy the following lower-bound on improvement:
Ĵ(π̂k+1)− Ĵ(π̂k) := Es0∼ρ0 [ V̂ π̂k+1(s0) ] − Es0∼ρ0 [ V̂ π̂k(s0) ] ≥ 1 ηH Es0∼ρ0 logZt(s0). (9)
Proof. We utilize the performance difference lemma in the empirical MDP to show this:
Ĵ(π̂k+1)− Ĵ(π̂k) = HE s∼dπ̂k+1 [∑ a π̂k+1(a|s)Âk(s,a) ]
= 1
η E s∼dπ̂k+1 [∑ a π̂k+1(a|s) log π̂ k+1(a|s)Zk(s) π̂k(a|s) ]
= 1
η E s∼dπ̂k+1
[ DKL(π̂ k+1(·|s)||π̂k(·|s)) ] + 1
η E s∼dπ̂k+1 [logZk(s)]
≥ 1 η E s∼dπ̂k+1 [logZk(s)] .
Finally, note that the final term logZt(s) is always positive because of Jensen’s inequality, and the fact that the expected advantage under a given policy is 0 for any MDP.
Utilizing Lemma B.10, we can then lower bound the total improvement of the learned policy in the actual MDP as:
J(π̂k)− J(π̂l) ≥ J(π̂k)− Ĵ(π̂k) (a) + Ĵ(π̂k)− Ĵ(π̂l) (b) − J(π̂l)− Ĵ(π̂l) (c)
≥ 1 η k∑ j=l Es∼dπ̂j+1 [logZj(s)]− √ C∗Hι N
where the √ C∗Hι/N guarantee for terms (a) and (c) arises under the conditions studied in Section 4.3.
Interpretation of Theorem 4.4. Theorem 4.4 says that if atleast k many updates can be made to the underlying empirical MDP, M̂ , such that each update is non-trivially lower-bounded, i.e., Es∼dπ̂k+1 [logZk(s)] ≥ c0 > 0, then the performance improvement obtained by k-steps of policy improvement is bounded below by kc0/η − O( √ H/N). This result indicates that if k = O(H) many high advantage policy updates are possible in a given empirical MDP, then the methods with that perform O(H) steps of policy improvement will attain higher performance than the counterparts that perform only one update.
This is typically the case in maze navigation-style environments, where O(H) many possible highadvantage updates are possible on the empirical MDP, especially by “stitching” parts of suboptimal trajectories to obtain a much better trajectory. Therefore, we expect that in offline RL problems where stitching is possible, offline RL algorithms will attain an improved performance compared to one or a few-steps of policy improvement.

heading: C GUARANTEES FOR POLICY-CONSTRAINT OFFLINE RL
text: In this section, we analyze a policy-constraint offline algorithm (Levine et al., 2020) that constrains the policy to choose a safe set of actions by explicitly preventing action selection from previously unseen, low-density actions. The algorithm we consider builds upon the MBS-PI algorithm from Liu et al. (2020), which truncates Bellman backups and policy improvement steps from low-density, out-of-support state-action pairs. The algorithm is described in detail in Algorithm 2, but we provide a summary below. Let µ̂(s,a) denote the empirical state-action distribution and choose a constant b.
Then, let ζ(s,a) = 1{µ̂(s,a) ≥ b} be the indicator of high-density state-action tuples. The algorithm we analyze performs the following update until convergence:
Q̂πζ (s,a) ← r̂(s,a) + γ ∑
(s′,a′)
P̂ (s′|s,a)π(a′|s′)ζ(s′,a′) · Q̂πζ (s′,a′), for all (s,a),
π̂ ← arg max π
Es∼D [ Ea∼π′ [ ζ(s,a) · Q̂πζ (s,a) ]] ,
In order to derive performance guarantees for this generic policy-constraint algorithm, we define the notion of a ζ−covered policy following Liu et al. (2020) in Definition C.1. The total occupancy of all out-of-support state-action pairs (i.e., (s,a) such that ζ(s,a) = 0) under a ζ-covered policy is bounded by a small constant U , which depends on the threshold b. Let π∗ζ denote the best performing ζ-covered policy. Definition C.1 (ζ-covered). π is called ζ-covered if ∑ (s,a)(1− ζ(s,a))dπ(s,a) ≤ (1− γ)U(b).
Equipped with this definition C.1, Lemma C.1 shows that the total value estimation error of any given ζ−covered policy, π, |J(π)− Ĵζ(π)| is upper bounded in expectation over the dataset Lemma C.1 (Value estimation error of a ζ-covered policy). For any given ζ-covered policy π, under Condition 3.2, the estimation error |J(π)− Ĵζ(π)| is bounded as:
ED [∣∣∣J(π)− Ĵζ(π)∣∣∣] .√C∗|S|Hι
N + C∗|S|Hι N + U(b) (10)
Proof. To prove this lemma, we consider the following decomposition of the policy performance estimate:∣∣∣J(π)− Ĵζ(π)∣∣∣
= ∞∑ t=0 ∑ (s,a) γtdπt (s,a)  ∑ (s′,a′) ( P̂ (s′|s,a)ζ(s′,a′)− P (s′|s,a) ) · Q̂π(s′,a′)  =
∞∑ t=0 ∑ (s,a) γtdπt (s,a) ∑ (s′,a′) (P̂ (s′|s,a)− P (s′|s,a)) · ζ(s′,a′) · π(a′|s′) · Q̂(s′,a′)
∆1:bound using concentrability and variance recursion
+ ∞∑ t=0 γtdπt (s,a) ∑ (s′,a′) P (s′|s,a) · (1− ζ(s′,a′)) · π(a′|s′) · Q̂π(s′,a′)
∆2:bias due to leaving support; upper bounded due to ζ-cover
To bound the inner summation over (s′,a′) in term (a), we can apply Lemma B.5 since P̂ (s′|s,a) and ζ(s′,a′) are not independent, to obtain a horizon-free bound. Finally, we use Condition 3.1 to bound the density ratios, in expectation over the randomness in dataset D, identical to the proof for the conservative lower-confidence bound method from before. Formally, using Lemma B.5, we get, with high probability ≥ 1− δ:
∀(s,a) s.t. n(s,a) ≥ 1, ∣∣∣(P̂ (s,a)− P (s,a)) · V̂ πζ ∣∣∣ ≤
√ V(P̂ (s,a), V̂ πζ )ι
n(s,a) +
ι
n(s,a) ,
where we utilized the fact that V̂ πζ ≤ V̂ π ≤ 1 due to Condition 3.2. For bounding ∆2, we note that this term is bounded by the definition of ζ-covered policy:
∆2 ≤ ∞∑ t=0 γt(1− γ)U(b) ≤ U(b). (11)
Thus, the overall policy evaluation error is given by:∣∣∣J(π)− Ĵζ(π)∣∣∣ . ∞∑ t=0 γtdπt (s,a) √V(P̂ (s,a), V̂ πζ )ι n(s,a) + ι n(s,a) + U(b). (12)
Equation 12 mimics the Φ term in equation 8 that is bounded in Section B.2.5, with an additional offset U(b). Hence, we can reuse the same machinery to show the bound in expectation over the randomness in the dataset, which completes the proof.
Using Lemma C.1, we can now that the policy constraint algorithm attains a favorable guarantee when compared to the best policy that is ζ-covered:
Theorem C.1 (Performance of policy-constraint offline RL). Under Condition 3.2, the policy π̂∗ incurs bounded suboptimality against the best ζ-covered policy, with high probability ≥ 1− δ:
ED [ J(π∗ζ )− J(π̂∗) ] .
√ C∗|S|Hι
N + C∗|S|Hι N + 2U(b) .
To prove this theorem, we use the result of Lemma C.1 for the fixed policy, that is agnostic of the dataset, and then again use the recursion as before to bound the value of the data-dependent policy. The latter uses Lemma B.5 and ends up attaining a bound previously found in Appendix B.2.5, which completes the proof of this Theorem. When the term U(b) is small, such that U(b) ≤ O(H0.5−ε) for ε > 0, then we find that the guarantee in Theorem C.1 matches that in Theorem 4.2, modulo a term that grows slower in the horizon than the other terms in the bound. If U(b) is indeed small, then all properties that applied to conservative offline RL shall also follow for policy-constraint algorithms.
Note on the bound. We conjecture that it is possible to get rid of the U(b) term, under certain assumptions on the support indicator ζ(s,a), and by relating the values of ζ(s,a) and ζ(s′,a′), at consecutive state-action tuples. For example, if ζ(s′,a′) = 1 =⇒ ζ(s,a) = 1, then we can derive a stronger guarantee.
D INTUITIVE ILLUSTRATIONS OF DERIVED CONDITIONS AND PRACTICAL GUIDELINES FOR VERIFYING THEM
In this section, we present intuitive illustrations of the various conditions we study and discuss practical guidelines that allow a practitioner to verify whether they are likely to hold for their problem domain. We focus on Conditions 4.1 and 4.2, as Condition 3.2 is satisfied in very common settings such as learning from sparse rewards obtained at the end of an episode, indicating success or failure.

heading: D.1 CONDITION 4.1
text: To provide intuition behind when this condition is satisfied, we first provide an example of a sample navigation domain in Figure 3, to build examples of critical states. As shown in the figure, the task is to navigate to the high-reward yellow-colored region. We wish to understand if states marked as A, B and C are critical or not. The region where the agent can move is very wide in the neighborhood around state A, very narrow around state B and wide again around state C. In this case, as marked on the figure if the agent executes actions shown via green arrows at the various states, then it is likely to
sill finish the task, while if it executes the actions shown via red arrows it is likely not on track to reach the high-reward region.
Several actions at states A and C allow the agent to still reach the goal, without crashing into the walls, while only one action at state B allows so, as shown in the figure. Thus, state B is a “critical state” as per Definition 4.1. But since most of the states in the wide regions of the tunnel are non-critical, this navigation domain satisfies Condition 4.1.

heading: D.2 CONDITION 4.2
text: Now we discuss the intuition behind why offline RL run on a form of noisy-expert data can outperform BC on expert data. As shown in Figure 4, the task is to navigate from the Start to the Goal. In this case, when BC is trained using only expert trajectories, and the environment consists of a stochastic dynamics, then running the BC policy during evaluation may diverge to low reward regions as shown in the second row, second column of Figure 4. On the other hand, if RL is provided with some noisy-expert data that visits states around expert trajectories which might eventually lead to low-rewarding states, then an effective offline RL method should be able to figure out how to avoid such states and solve the task successfully.
Condition 4.2 requires that state-action tuples with d∗(s,a) ≥ b/H under the expert policy have high-enough density µ(s,a) ≥ b under the data distribution. There are two ways to attain this condition: (1) the expert policy already sufficiently explores the state (d∗(s,a) ≥ b), for example, when the environment is mostly deterministic or when trajectories are cyclic (e.g., in locomotion tasks discussed below), or, (2) the offline dataset is noisy such that states that are less-frequently visited by the expert are explored more in the data. The latter can be satisfied when the agent is provided with “negative data”, i.e., failed trajectories, starting from states in an optimal trajectory as shown in Figure 4. Such counterfactual trajectories allow the agent to observe more outcomes starting from a state in the optimal trajectory. And running offline RL on them will enable the agent to learn what not to do, as illustrated in Figure 4. On the other hand, BC cannot use this negative data.
This condition is satisfied in the following practical problems:
• Robotics: In robotics noisy-expert data may not be directly available via demonstrations but can be obtained by a practitioner by running some limited autonomous data collection using noisy scripted policies (e.g., Kalashnikov et al. (2018a) and Kalashnikov et al. (2021) run partly trained RL policies for noisy collection for running offline RL).
• Autonomous driving and robotics: In some domains such as autonomous driving and robotics, rolling out short counterfactual trajectories from states visited in the offline data, and labeling it with failures is a common strategy (Bojarski et al., 2016; Rao et al., 2020). A
practitioner could therefore satisfy this condition by tuning the amount of counterfactual data they augment to training.
• Recommender systems: In recommender systems, Chen et al. (2019) found that it was practical to add additional stochasticity while rolling out a policy for data collection which could be controlled, enabling the practitioner to satisfy this condition.
• Trajectories consist of cyclic states (e.g., robot locomotion, character animation in computer graphics): This condition can be satisfied in several applications such as locomotion (e.g., in character animation in computer graphics (Peng et al., 2018), or open-world robot navigation (Shah et al., 2021)) where the states observed by the agent are repeated over the course of the trajectory. Therefore a state with sufficient density under the optimal policy may appear enough times under µ.

heading: D.3 PRACTICAL GUIDELINES FOR VERIFYING THESE CONDITIONS
text: These conditions listed above and discussed in the paper can be difficult to check for in practice; for example, it is non-obvious how to quantitatively compute the volume of critical states, or how wellexplored the dataset is. However, we believe that a practitioner who has sufficient domain-specific knowledge has enough intuition to qualitatively reason about whether the conditions hold. We believe that such practitioners can answer the following questions about their particular problem domain:
• Does there only exist a large fraction of states along a trajectory where either multiple good actions exist, or it is easy to recover from suboptimal actions?
• Is the offline dataset collected from a noisy-expert policy, and if not, can the dataset be augmented using perturbed or simulated trajectories?
If either of those questions can be answered positively, our theoretical and empirical results show that it is favorable to use offline RL algorithms, even over collecting expert data and using BC. At least, offline RL algorithms should be tried on the problem under consideration. Hence, the goal of our contributions is not to provide a rigid set of guidelines, but rather provide practical advice to the ML practitioner. We would like to highlight that such non-rigid guidelines exist in general machine learning, beyond RL. For example, in supervised learning, tuning the architecture of a deep neural network depends heavily on domain knowledge, and choosing kernel in a kernel machine again depends on the domain.

heading: E EXPERIMENTAL DETAILS
text: In this section we provide a detailed description of the various tasks used in this paper, and describe the data collection procedures for various tasks considered. We discuss the details of our tasks and empirical validation at the following website: https://sites.google.com/view/ shouldirunrlorbc/home.

heading: E.1 TABULAR GRIDWORLD DOMAINS
text: The gridworld domains we consider are described by 10× 10 grids, with a start and goal state, and walls and lava placed in between. We consider a sparse reward where the agent earns a reward of 1 upon reaching the goal state; however, if the agent reaches a lava state, then its reward is 0 for the rest of the trajectory. The agent is able to move in either of the four direction (or choose to stay still); to introduce stochasticity in the transition dynamics, there is a 10% chance that the agent travels in a different direction than commanded.
The exact three gridworlds we evaluate on vary in the number of critical points encountered per trajectory. We model critical states as holes in walls through which the agent must pass; if the agent chooses a wrong action at those states, it veers off into a lava state. The exact three gridworlds we evaluate on are: (a) “Single Critical” with one critical state per trajectory, (b) “Multiple Critical” with three critical states per trajectory, and (c) “Cliffwalk”, where every state is critical (Schaul et al., 2015). The renderings of each gridworld are in Figure 5.
0
1
2
3
4
5
6
7
8
9

heading: E.2 MULTI-STAGE ROBOTIC MANIPULATION DOMAINS
text: Overview of domains. These tasks are taken from Singh et al. (2020). The robotic manipulation simulated domains comprise of a 6-DoF WidowX robot that interacts with objects in the environment. There are three tasks of interest, all of which involve a drawer and a tray. The objective of each task is to remove obstructions of the drawer, open the drawer, pick an object and place it in a tray. The obstructions of the drawer were varied giving rise to three different domains — open-grasp (no obstruction of the drawer), close-open-grasp (an open top drawer obstructs the bottom drawer), pick-place-open-grasp (an object obstructs the bottom drawer).
Reward function. For all the three tasks considered, a reward of +1 is provided when the robot is successfully able to open the drawer of interest (bottom drawer in close-open-grasp and pick-placeopen-grasp; the only drawer in open-grasp) and is able to grasp the object inside it. If the robot fails at doing so, it gets no reward.
Dataset composition. For each task, we collected a dataset comprising of 5000 trajectories. For our experiments where we utilize expert data, we used the (nearly)-expert scripted policy for collecting trajectories and discarded the ones that failed to succeed. Thus the expert data attains a 100% success rate on this task. For our experiments with suboptimal data, which is used to train offline RL, we ran a noisy version of this near-expert scripted policy and collected 5000 trajectories. The average success rate in the suboptimal data is around 40-50% in both opening and closing the drawers with, 70% success rate in grasping objects, and a 70% success rate in place those objects at random locations in the workspace.

heading: E.3 ANTMAZE DOMAINS
text: Overview of the domain. This task is based on the antmaze-medium and antmaze-large environments from Fu et al. (2020). The goal in this environment is to train an 8-DoF quadraped ant robot to successfully navigate to a given, pre-specifcied target location in a maze. We consider two different maze layouts provided by Fu et al. (2020). We believe that this domain is well-suited to test BC and RL methods in the presence of multiple critical points, and is representative of real-world navigation scenarios.
Scripted policies and datasets. We utilize the scripted policies provided by Fu et al. (2020) to generate two kinds of expert datasets: first, we generate trajectories that actually traverse the path from a given default start location to the target goal location that we consider for evaluation, and second, we generate trajectories that go from multiple random start positions in the maze to the target goal location in the maze. The latter has a wider coverage and a different initial state distribution compared to what we will test these algorithms on. We collected a dataset of 500k transitions, which was used by both BC and offline RL.
Reward functions. In this task, we consider a sparse binary reward r(s,a) = +1, if |s′ − g| ≤ ε = 0.5 and 0 otherwise. This reward is only provided at the end of a trajectory. This reward function is identical to the one reported by D4RL (Fu et al., 2020), but the dataset composition in our case comes from an expert policy.

heading: E.4 ADROIT DOMAINS
text: Overview of the domain. The Adroit domains (Rajeswaran et al., 2018; Fu et al., 2020) involve controlling a 24-DoF simulated Shadow Hand robot tasked with hammering a nail (hammer), opening a door (door), twirling a pen (pen) or picking up and moving a ball (relocate). This domain presents itself with narrow data distributions, and we utilize the demonstrations provided by Rajeswaran et al. (2018) as our expert dataset for this task. The environments were instantiated via D4RL, and we utilized the environments marked as: hammer-human-longhorizon, door-human-longhorizon, pen-human-longhorizon and relocate-human-longhorizon for evaluation.
Reward functions. We directly utilize the data from D4RL (Fu et al., 2020) for this task. However, we modify the reward function to be used for RL. While the D4RL adroit domains provide a dense reward function, with intermediate bonuses provided for various steps, we train offline RL using a binary reward function. To compute this binary reward function, we first extract the D4RL dataset for these tasks, and then modify the reward function as follows:
r(s,a) = +1 if rD4RL(s,a) ≥ 70.0 (hammer-human) (13) r(s,a) = +1 if rD4RL(s,a) ≥ 9.0 (door-human) (14) r(s,a) = +1 if rD4RL(s,a) ≥ 47.0 (pen-human) (15) r(s,a) = +1 if rD4RL(s,a) ≥ 18.0 (relocate-human) (16)
The constant thresholds for various tasks are chosen in a way that only any transition that actually activates the flag goal achieved=True flag in the D4RL Adroit environments attains a reward +1, while other transitions attain a reward 0. We also evaluarte the performance of various algorithms on this new sparse reward that we consider for our setting.

heading: E.5 ATARI DOMAINS
text: We utilized 7 Atari games which are commonly studied in prior work (Kumar et al., 2020; 2021b): ASTERIX, BREAKOUT, SEAQUEST, PONG, SpaceInvaders, Q*BERT, ENDURO for our experiments. We do not modify the Atari domains, directly utilize the sparse reward for RL training and operate in the stochastic Atari setting with sticky actions for our evaluations. For our experiments, we extracted datasets of different qualities from the DQN-Replay dataset provided by Agarwal et al. (2020b). The DQN-Replay dataset is stored as 50 buffers consisting of sequentially stored data observed during training of an online DQN agent over the course of training.
Expert data. To obtain expert data for training BC and RL algorithms, we utilized all the data from buffer with id 49 (i.e., the last buffer stored). Since each buffer in DQN-Replay consists of 1M transition samples, all algorithms training on expert data learn from 1M samples.

heading: Domain / Behavior Policy Task/Data Quality BC Naı̈ve CQL Tuned CQL
text: Noisy-expert data. For obtaining noisy-expert data, analogous to the gridworld domains we study, we mix data from the optimal policy (buffer 49) with an equal amount of random exploration data drawn from the initial replay buffers in DQN replay (buffers 0-5). i.e. we utilize 0.5M samples form buffer 49 in addition to 0.5M samples sampled uniformly at random from the first 5 replay buffers.

heading: F TUNING AND HYPERPARAMETERS
text: In this section, we discuss our tuning strategy for BC and CQL used in our experiments.
Tuning CQL. We tuned CQL offline, using recommendations from prior work (Kumar et al., 2021c). We used default hyperparameters for the CQL algorithm (Q-function learning rate = 3e-4, policy learning rate = 1e-4), based on prior works that utilize these domains. Note that prior works do not use the kind of data distributions we use, and our expert datasets can be very different in composition compared to some of the other medium or diverse data used by prior work in these domains. In particular, with regards to the hyperaprameter α in CQL that trades off conservatism and the TD error objective, we used α = 0.1 for all Atari games (following Kumar et al. (2021b)), and α = 1.0 for the robotic manipulation domains following (Singh et al., 2020). For the Antmaze and Adroit domains, we ran CQL training with multiple values of α ∈ {0.01, 0.1, 0.5, 1.0, 5.0, 10.0, 20.0}, and then picked the smallest α that did not lead to eventually divergent Q-values (either positively or negatively) with more (1M) gradient steps. Next, we discuss how we regularized the Q-function training and performed policy selection on the various domains.
• Detecting overfitting and underfitting: Following Kumar et al. (2021c), as a first step, we detect whether the run is overfitting or underfitting, by checking the trend in Q-values. In our experiments, we found that Q-values learned on Adroit domains exhibited a decreasing trend throughout training, from which we concluded it was overfitting. On the Antmaze and Atari experiments, Q-values continued to increase and eventually stabilized, indicating that the run might be underfitting (but not overfitting).
• Correcting for overfitting and policy selection: As recommended, we applied a capacity decreasing regularizer to correct for overfitting, by utilizing dropout on every layer of the Q-function. We ran with three values of dropout parobability, p ∈ {0.1, 0.2, 0.4}, and found that 0.4 was the most effective in alleviating the monotonically decreasing trend in Q-values, so used that for our results.
Then, we performed policy checkpoint selection by picking the earliest checkpoint that appears after the peak in the Q-values for our evaluation.
• Correcting for underfitting: In the Atari and Antmaze domains, we observed that the Q-values exhibited a stable, convergent trend and did not decrease with more training. Following Kumar et al. (2021c), we concluded that this resembled underfitting and utilized a capacity-increasing regularizer (DR3 regularizer (Kumar et al., 2021a)) for addressing this issue. We used identical hyperparameter for the multiplier (β) on this regularizer term for both Atari and Antmaze, β = 0.03 and did not tune it.
Tuning BC. In all domains, we tested BC with different network architectures. On the antmaze domain, we evaluated two feed-forward policy architectures of sizes (256, 256, 256) and (256, 256, 256, 256, 256, 256) and picked the one that performed best online. ON Adroit domains, we were not able to get a tanh-Gaussian policy, typically used in continuous control to work well, since it overfitted very quickly giving rise to worse-than-random performance and therefore, we switched to utilizing a Gaussian policy network with hidden layer sizes (256, 256, 256, 256), and a learned, state-dependent standard deviation. To prevent overfitting in BC, we applied a strong dropout regularization of p = 0.2 after each layer for Adroit domains. On Atari and the manipulation domains, we utilized a Resnet architecture borrowed from IMPALA (Espeholt et al., 2018), but without any layer norm.
More details are at: https://sites.google.com/view/shouldirunrlorbc/home.
Tuning BC-PI. Our BC-PI method is implemented by training a Q-function via SARSA, i.e., Q(s,a) ← r(s,a) + γQ(s′,a′), where (s′,a′) is the state-action pair that appears next in the trajectory after (s,a) in the dataset using the following Bellman error loss function to train Qθ:
L(θ) = 1 |D| ∑ s,a,s′,a′∼D ( Qθ(s,a)− (r(s,a) + γQ̄θ̄(s′,a′) )2 ,
and then performing advantage-weighted policy extraction: π(a|s) ∝ π̂β(a|s) · exp(A(s,a)/η) on the offline dataset D. The loss function for this policy extraction step, following Peng et al. (2019) is given by:
πφ ← max πφ ∑ s,a log πφ(a|s) · exp ( Qθ(s,a)− V (s) η ) ,
where the value function was given by V (s) = ∑
a′ πβ(a ′|s)Qθ(s,a′) and πβ is a learned model of
the behavior policy, as done in the implementation of Brandfonbrener et al. (2021). This model of the behavior policy is trained according to the tuning protocol for BC, and is hence well-tuned.
What we tuned: We tuned the temperature hyperparameter η using multiple values spanning various levels of magnitude: {0.005, 0.05, 0.1, 0.5, 1.0, 3.0} and additionally tried two different clippings of the advantage values A(s,a) := Q(s,a)− V (s) between [−10, 2] and [−10, 4]. The Q-function architecture is identical to tuned CQL, and the policy and the model of the behavior policy both utilize the architecture used by our BC baseline.
Our observations: We summarize our observations below:
• We found that in all the runs the temporal difference (TD) error for SARSA was in the range of [0.001, 0.003], indicating that the SARSA Q-function is well behaved.
• The optimal hyperparameters that lead to the highest average performance across all games is η = 0.005, and the advantage clipping between [−10, 2]. We find a huge variation in the performance of a given η, but we used a single hyperparameter η across all games, in accordance with the Atari evaluation protocols (Mnih et al., 2013), and as we did for all other baselines. For example, while on some games such as Qbert, BC-PI improves quite a lot and attains 118% normalized return, on Enduro it attains only 78% and on SpaceInvaders it attains 31.7%.
• These results perhaps indicate the need for per-state tuning of η, i.e., utilizing η(s), however, this is not covered in our definition of BC-PI from Section 4.4, and so we chose to utilize a single η across all states. Additionally, we are unaware of any work that utilizes per-state η(s) values for exponentiated-advantage weighted policy extraction.
Finally, we would note that we tuned this implementation to the best of our abilities, within our compute capabilities. We used online rollouts for tuning BC-PI, and the results shown in Figue 2 is what we obtain.

heading: G REGARDING OFFLINE RL LOWER BOUNDS
text: Here we address the connection between recently published lower-bounds for offline RL by Zanette (2020) and Wang et al. (2021) and our work.
Zanette (2020) worst-case analysis does address function approximation even under realizability and closure. However, this analysis concerns policy evaluation and applies to policies that go out of the support of the offline data. This does not necessarily prove that any conservative offline RL algorithm (i.e., one that prevents the learned policy from going out of the support of the offline dataset) would suffer from this issue during policy learning, just that there exist policies for which evaluation would be exponentially bad. Offline RL can exactly prevent the policy from going out of the support of the dataset in Zanette (2020)’s counterexample since the dynamics and reward functions are deterministic. This policy can still improve over behavior cloning by stitching overlapping trajectories, similar to the discussion of one-step vs multi-step PI in Theorem 4.4. Thus, while the lower-bound applies to off-policy evaluation of some target policies, it doesn’t apply to evaluation of every policy in the MDP, and specifically does not apply to in-support policies, which modern offline RL algorithms produce, in theory and practice. Certainly, their lower bound would apply to an algorithm aiming to estimate Q∗ from the offline data, but that’s not the goal of pessimistic algorithms that we study. Finally, our practical results indicates that offline RL methods can be made to perform well in practice despite the possibility of any such lower bound.
The lower bound in Wang et al. (2020) only applies to non-pessimistic algorithms that do not tackle distributional shift. In fact, Section 5, Theorem 5.1 in Wang et al. (2021) provides an upper bound for the performance of offline policy evaluation with low distribution shift. The algorithms analyzed in our paper are pessimistic and guarantee low distribution shift between the learned policy and the dataset, and so the lower bound does not apply to the algorithms we analyze.

Review summaries:
The paper considers a setting where we are given access to a dataset of expert or noisy-expert data collected from some MDP and need to decide whether to use either behavior cloning (BC) or offline RL. It conducts a theoretical analysis in a tabular setting showing that offline RL will recover a better policy than BC when the data is sufficiently suboptimal and has sufficient coverage. Finally it conducts an empirical analysis that confirms the results in some diagnostic gridworld tasks and shows that a tuned variant of the CQL offline RL algorithm outperforms BC in several larger-scale tasks.

Offline RL approaches are of quite great interest because of potentially easier real world applications. But as the paper points out in the extensive related work, there are a lot of conflicting results in the literature when it comes to comparison with plain old behavior cloning. To this end, the paper functions as fairly clear exposition of the current state of offline RL literature and proposes a formalization to allow comparison between these approaches. This formalization leads to a better characterization for the conditions for offline RL methods to outperform behavior cloning (and the importance of planning horizon and critical states).  The paper performs experiments on a wide number of domains which allows the readers to make their own inferences for the conditions for offline RL successes. 

The paper provides an attempt to help practitioners answer the question "For what type of environments and datasets should we prefer Offline RL over Behavioural Cloning". To do so, the authors extend the previous work of [1] studying this problem for contextual bandits to MDPs. These theoretical results enable them to draw some conclusions on when we can expect Offline RL to have an edge on Behavioural cloning. To name a few:  - When the dataset provided is not optimal, offline RL can scale more favourable with the horizon especially for environments with horizon-independent returns or with a low volume of critical states,i.e. states for which there is no significant advantage to select one action over another. - For long horizon tasks again, offline RL trained on noisy data displaying higher coverage can outperform BC trained on the same amount of expert demonstrations.  These theoretically grounded insights are then empirically validated on a tabular gridworld domain, after which they validate their findings on high dimensional offline RL problems (continuous control and navigation, and some atari games). On the tabular gridworld, the experiments strongly agree with their theoretical results. When turning to deep RL, the experiments mostly aligned although the various tuning mechanisms introduced in previous work to train efficiently offline RL algorithms introduce a few discrepancies.  1. Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. *arXiv preprint arXiv:2103.12021*,