Should I Run Offline Reinforcement Learning or Behavioral Cloning?
Authors: Aviral Kumar
Joey Hong
Anikait Singh
Sergey Levine
Venue: ICLR 2022 Poster (2022)
Keywords: offline RL

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: When should we prefer offline RL over BC? In this paper, our goal is to characterize environments and dataset compositions where offline RL leads to better performance than BC.  In particular, 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.

Published as a conference paper at ICLR 2022
WHEN SHOULD WE PREFER OFFLINE REINFORCEMENT LEARNING OVER BEHAVIORAL CLONING?
Aviral Kumar ,1,2, Joey Hong*.,, 'Department of EECS, UC Berkeley "Google Research
Anikait Singh' A
Sergey Levine 1.2
(*Equal Contribution)
faviralk, (eey) www.eeeee.eeeeeeeeeeeeeeeeeeeeee
ABSTRACT
Offline reinforcement learning (RL) algorithms can acquire effective policies by utillizigg previously collected experience, without any online interaction. widely understood that offline RL is able to extract good policies even from highly suboptimal data, scenario where imitation learning finds suboptimal solutions that do not improve over the demonstrator that generated the dataset. However, another common use case for practitioners is to learn from data that resembles demonstrations. In this case, one can choose to apply offline RL, but can also use behavioral cloning (BC) algorithms, which mimic a subset of the dataset via supervised learning. Therefore, it seems natural to ask: when can 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 RI. methods to perform better than BC methods, even when only provided with expert data. Additionally, we show that policies trained on sufficiently noisy suboptimal data 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 dittdmmmnnional domains including robotic manipulation, maze navigation, and Atari games, with variety of data distributions. We observe that, under specific but common conditions such as sparse rewards or noisy data sources, modern offline RL methods can significantly outperform BC.
INTRODUCTION
Offline reinforcement learning (RL) algorithms aim to leverage large existing datasets of previously collected data to produce effective policies that generalize across wide range of scenarios, without the
need for costly active data collection. Many recent offline RI algorithms [16, 26, 66, 27, 69, 61, 25] can work well even when provided with highly suboptimal data, and number of these approaches have been studied theoretically [64, 71, 52, 20J. While 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 such methods are useful when the dataset consists 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 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 come to 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 [14]. 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 [38, 12, 17]. 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 offline RL algorithm might outperform BC for given task, even when BC is provided with expert data or is allowed to use rewards as side information. Our findings inform practitioner in determining whether offline RL is good choice in their domain, even when expert or near-expert data is available and BC might appear to be a natural choice.
Our contribution in this paper is theoretical and empirical characterization of certain conditions when offline RL outperforms BC. Theoretically, our work presents conditions on the MDP and dataset that sufficient for offline RL achieve better worst-case guarantees than even the best-case

---

Published as a conference paper at ICLR 2022
lower-bound for BC using the same amount of 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 eπror incurred by offline RL algorithms can scale significantly more favorably when the MDP enjoys some structure, which includes horizon- independent returns (i.., sparse rewards) or 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 BC methods ignore rewards, we consider generalized BC methods that use the observed rewards to inform learning, and show that it still preferable to perform offline RL (Section 4.4).
Empirically. we validate our theoretical conclusions on diagnostic gridworld domains [13] and large- scale benchmark problems in robotic manipulation and navigation and Atari games, using human data [14], scripted data [60], and data generated from RI. policies [3]. We verify that in multiple long-horizon problems where the conditions we propose are likely to be satisfied, practical off RL. methods can outperform BC and generalized BC methods. We show that using careful offline tuning practices, we show that is possible for offline RL to outperform cloning an expert dataset for the same task, given equal amounts of data. We also highlight open questions for hyperparameter tuning that have the potential to make offline RL methods work better in practice.
RELATED WORK
Offline RL [32, 34] has shown promise in domains such as robotic manipulation [22, 37, 60, 23], NLP [19] and healthcare [58, 63]. The major challenge in offline RL is distribution shift [16, 26]. where the learned policy might execute out-of-distribution actions. Prior offline RL methods can broadly be characterized into two categories: (1) policy- consty-constrains methods that regularize the learned policy to be "close" to the behavior policy either explicitly [16, 26, 36, 66, 15] or implicitly [59, 47, 45], or via importance sampling [35, 62, 43], and (2) conservative methods that learn a conservative, estimate of return and optimize the policy against it [27, 25, 24, 69, 70]. Our goal is not to devise new algorithm, but to understand when existing offline RL methods can outperform BC.
When do offline RL methods outperform BC? Rashidinejad et al. [52] derive 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 [41, 42, 64]. Laroche et al. [33], Nadjahi et al. [44], Kumar et al. [27]. Liu et al. [36]. Xie et al. [68] present safe policy improvement bounds expressed as improvements over the behavior policy, which imitation aims recover, but these bounds do not clearly indicate when offline RL is better or worse. Empirically. Fu et al. [14] show that offline RL considerably outperforms BC for tasks that require "stitching" trajectory segments to devise an optimal policy. In contrast, Mandlekar et al. [38], Brandfonbrener et al. [6], Chen et al. [8], Hahn et al. [17] suggest that BC or filtered BC using the top fraction of the data performs better on other tasks. While the performance results in D4RL [14], especially on the Adroit domains, show that offline RL outperforms BC even on expert data, Florence et al. [12] reported superior BC results, making it unclear if the discrepancy arises from different hyperparameter tuning practices. Kurenkov & Kolesnikov [31] emphasize the importance of the online evaluation budget for offline RL methods and show that BC is more favorable in limited budget. While these prior works discussed above primarily attempt to show that BC can be better than offline RI,, we attempt to highlight when offline RL is expected to be better by providing characterization of scenarios where we would expect offline RL to be better than BC, and empirical results verifying that offline RL indeed performs better on such problems [14, 60, 4].
Our theoretical analysis combines tools from a number of prior works. We analyze the total error incurred by RL via an error propagation analysis [41, 42, 11, 67, 36), which gives rise to bounds with concentrability coefficients that bound the total distributional shift between the learned policy and the data distribution [67, 36]. We use tools from Ren et al. [53]. which provide horizon- free bounds for standard (non conservvvvtt) offline Q-learning but relax their strict coverage assumptions. While our analysis studies a LCBB-ttyle algorithm similar to Rashidinejad et al. [52], Jin et al. [20], we modify it to use tighter Bernstein bonuses [73, 1], which key to improving the guarantee.
3 PROBLEM SETUP AND PRELIMINARIES
The goal in reinforcement learning is to learn a policy (-|ss) that maximizes the expected cumulative discounted reward in a Markov decision process (MDP), which is defined by a tuple (S,A, P, r, 7).
2

---

Published as a conference paper at ICLR 2022
represent state and action spaces, P(s'|s, a) and r(s. a) represent the dynamics and mean reward function, and y E (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 given policy is equal to the discounted long-term -eretterm reward attained by executing a at the state s and then following policy π thereafter. Q" satisfies the recursion: V/s, Sx.A, Q" (s, a) r(s, 4 x'xxxt [Q(s', a')] The value function
V considers the expectation of the Q-function over the policy (*(s)
(1))( [Q (s,
Meanwhile, the Q-function of the optimal policy, Q", satisfies the recursion: (s, a) = r(s, a)
Egr~p( s.a) [maxa' (s', a') a')], and the optimal value function is given by V* (s) = maxa Q" a). Finally, the expected cumulative discounted reward is given by J(T] = Exoup u (so)]
In offline RL, we are provided with dataset D of transitions, D = {(s,: a, r, s)) of size [D) = =N. We assume that the dataset D is generated i..d. from a distribution μu(s, a) that specifies the effective behavior policy Th Ta(ass) == p(s..a) Σ. ((s, a). Note that this holds even if the data itself is generated by running a Mon-aankovian policy Th [48]. Let n(s, a) be the number of times (8, a) appear in D, and P(-|s, a) and F(s, a) denote the empirical dynamics and reward distributions in D, which may be different from P and due to stochasticity. Following Rashidinejad et al. [52], the goal to minimize the suboptimality of the learned policy ã:
Sub = ED= [J(x') - [()] = Ep [aoop
((((s) - V* (Su)
We will now define some conditions on the offline dataset and MDP structure that we will use in our analysis. The first characterizes the distribution shift between the data distribution pus, a) and the normalized state-action marginal of x²", given by d' (s. a) = (1 - 7) Et= 7'P (s; = s, a = a; x"), via a concentrability coefficient C*.
Condition 3.1 (Rashidinejad et al. [52]. Concentrabiliity of the data distribution). Define C* to be the smallest. finite constant that satisfies: d' (s. (s, I C Vs E S,a A.
Intuitively, the coefficient C* formalizes how well the data distribution ju(s, a) covers the state-action pairs visited under the optimal π², where C* = corresponds to data from x². If j(s, a) primarily covers state-action pairs that are not visited by म², C* would be large. The next condition is that the return for any trajectory in the MDP is bounded by constant, which w.l.o.g., we assume to be 1.
Condition 3.2 (Ren et al. [53], the value of any trajectory is bounded by 1). The infinite-horizon discounted return for any trajectory
(so, an, To; S1, S..... ) is bounded as 2:=0?'re 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 [60, 22] and games [4], 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 [53, 73]. Let n 1 = max(n, 1}. Denote () H, N). We let be a polylogarithmic quantity, changing with context. For d-dimensional vectors x, y, xi) denotes its i-th entry, and define V(x,y) Σ. (i)) (E, (i))
THEORETICAL COMPARISON OF BC AND OFFLINE RL
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.
4.1 IMPROVED PERFORMANCE GUARANTEES OF BC AND OFFLINE RL
Our goal is to understand if there exist offline RL methods that can outperform BC for given task. As our aim is to provide a proof of existence, 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 representative policy-constraie method to Appendix C. Both algorithms are described in Algorithms and 2.
Guarantees for BC. For analysis purposes, consider 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 analyzed in prior work [49], and is worse than other
3

---

Published as a conference paper at ICLR 2022
schemes for acting at out-of-support states in general. Denoting the learned BC policy as fg. we have Vs E D, ( a 8) &- nss, a)/n(s). and Vs & D, {a(s)) <- 1/|.Al. We adapt the results presented by Rajaraman et al. [49] 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 as N -> oc) in scenarios where C = 1, as it aims to match the data distribution p(s., a), and a non-expert dataset will inhibit the cloned policy from matching the expert n². 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
(C*
2 + H
1)H
SubOpt(Tt)) 2
N
proof of Theorem 4.1 is presented in Appendix B.1. The first term 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 [54, 49]. We achieve (H1) suboptimality rather than ((1²) 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 class of offline RL algorithms that maintain conservative value estimator such that the estimated value lower-bounds the true one, i.e. V S <V" for policy æ. Existing offline RL algorithms achieve this by subtracting a penalty from the reward, either explicitly [69, 24] implicitly [27]. 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 methods, where similar algorithms can be amalyzed using the same technique. While the algorithm we consider is similar to VI-LCB which was proposed by Rashidinejad et al. [52] and subtracts a penalty b(s, a) from the reward during value iteration, we use different penalty that results in tighter bound. The estimated Q-values are obtained by iteratively solving the following Bellman backup: Q(s, < f(s. a) - b(s, a) + Eg P(s'|s, |s, a) max,' Q(s', a'). The learned policy is then given by 7" (s) < arg max, @(s, a). The specific b(s, a) is derived using Bernstein's 's inequality:
b(s,a) a)
(P((ss,)). (1(),a))1)
a(s, V a) + (n(s,a)A1)
L
The performance of the learned policy 7* 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
C² C HH + N
SubOpt(#*) S
We defer proof for Theorem 4.2 Appendix B.2. At a high level, first show that our algorithm always conservative, i.e., Vs, (s) S V (s). and then bound the total suboptimality incurred as a result of being conservative. Our bound 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. [53], (2) by using variance recursion techniques on the Bernstein bonuses, with Condition 3.2, we save ( factor over VI-LCB in Rashidinejad et al. [52], and (3) we shave [S] factor by introducing s-absorbing MDPs for each state as in Agarwal et al. [1]. Building on this analysis of the representative offline RL method, we will now compare BC and offline RL under specific conditions on the MDP and dataset.
4.2 COMPARISON UNDER EXPERT DATA
We first compare the performance bounds from Section 4.1 when the offline dataset is generated from the expert. In relation to Condition 3.1, this corresponds to small C Specifically, we consider C* E [1, 1+ /N) and in this case, the suboptimality of BC in Theorem 4.1 scales as ((S)H/H))) In this regime, perform nuanced comparison by analyzing specific scenarios where RL may outperform BC. We consider the case of C* 1 and C' 1 + ((1/N) separately.
What happens when C* = 1? In this case, we derive a lower-bound of |S H/N for any offline algorithm, by utilizing the analysis of Rajaraman al. [49] and factoring in Condition 3.2.
4

---

Published as a conference paper at ICLR 2022
Theorem 4.3 cetmmatioon-hhoretee lower-bound for offline learning with =+ 1). For any learner म. there exists an MDP M satisfying Assumption 3.2, and a deterministic expert n², such that the expected suboptimality of the learner is lower-bounded
|
sup SubOpt(a) ( Z N
M,
The proof of Theorem 4.3 uses the same hard instance from Theorem 6.1 of Rajaraman et al. [49], 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 Observation 4.1. When no assumptions are made on the environment structure. both offline RI. and BC perform equally poorly with trajectories from an expert demonstrator.
However, we argue that even with expert demonstrations as data, C* may not exactly be 1. Naively, seems plausible that the expert that collected the dataset did not perform optimally at every transition; this is often true for humans, or stochastic experts such as e-greedy or maximum-entropp policies. In addition, there are scenarios where C* > 1 even though the expert behaves optimally: for example, when the environment is stochastic or in the presence of small distribution shifts in the environment One practical example of this is when the initial state distribution changes between dataset collection and evaluation (e.g., in robotics [60]. or self driving [5]). Since the normalized state-action marginals d' (s, a), (s, a) depend p(s), this would lead to C* 1 even when the data collection policy acts exactly as the expert xt' at each state.
What happens when C* = + Ó(1/N)² Here C* is small enough that BC still achieves the same optimal ((SS)/NN) performance guarantee. However, there is suboptimality incurred by BC even for 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 discuss one such structure helow.
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 large proportion of states a trajectory where it is not costly to recover after deviating from the optimal trajectory, or when identifying an optimal trajectory is easy: this could be simply because there exists a large volume of near-optimal trajectories, or because at all but a few states, the volume of "good-enough" actions is large. Therefore, we would expect that offline RL can quickly identify and master such good-enough actions at a majority of the states while reward-agnoste BC would be unable to do so.
Agenti reces region
High mwand d441
Singl actionn
eacoped
succendol ortica")
Illustration showing the intu- ition behind critical states. The agent is supposed to navigate to a high-reward region marked as the yellow polygon, without crash- ing into the walls. For different states, A, and C that consider, the agent has high volume of actions that allow it to reach the goal at states A and C, but only few actions that allow it to do so at state B. States around A and C are not critical, and so this task has only a small volume of critical states (i.c., those in the thin tunnel).
Figure 1:
Two examples are in 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 because unless the object breaks, actions taken by the robot are typically reversible [21]. In this phase, the robot just needs to avoid performing actions that do not at all move it closer to the object since it will fail to grasp it, but it needs to know more than general sense of how to approach the object, which is casily identifiable from the reward information. 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, as we pictorially illustrate in Figure 1, there may exist multiple paths that end at the same goal, particularly in large, unobstructed areas [55]. 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, and identifying these good-enough actions using reward
5

---

Published as a conference paper at ICLR 2022
information is easy. However, there are "critical states" like narrow doorways where taking specific action is important. Domains that do not satisfy this structure include cliffwalk environments, where single incorrect action at any state will cause the agent to fall off the cliff. We can formally define one notion of critical states as follows:
Definition 4.1 (Non-critical states). A states s is said to be non-criticall (iee, s & C) if there exists a large subset (s) of E- E-good actions, such that,
Va E ((s), max Q" (s, a') (* a) H' and Va E A x ((s), max Q" a') (s, A(s).
Now the structural condition we consider is that for any policy, the total density of critical states, E C is bounded by pe, and will control pe. for our bound.
Condition 4.1 (Occupancy of critical states is small). Let Ap E (0, 1) such that for any policy the average occupancy of critical states is bounded above by Pe: Eeec d' S Pc-
We can show that, if the MDP satisfies the above condition with small enough Pe and and the number of good actions [s) are large enough, then by controlling the gap Ass) between suboptimality of good and bad actions some offline RL algorithms
outperform BC. We perform this analysis under a simplified setting where the state-marginal distribution in the dataset matches that of the optimal policy and find that policy constraint offline RL algorithm can outperform BC. We describe the informal statement below and discuss the details and a proof in Appendix B.3.
Corollary 4.1 (Offline RL vs BC with critical states). Let the dataset distribution be such that Vs, dd (s) = pu(s) and all for state-action pairs V(s, a); n(s, a) 2 no- Then, under Conditions I with Pe I/H, 3.1 and 3.2 policy 7*'' found by policy constraint offline RL (Equaatinn 10) satisfies SubOpt("*) X SubOpt(ftcc..
The above statement indicates that when we encounter O(1/H) critical states on average in any trajectory, then of full coverage over all states, the proof relies on showing that the particular offline RL algorithm we consider can collapse to good-enough actions non-critical states quickly, whereas BC is unable to do so since it simply mimics the data distribution. On the other hand, BC and RL perform equally well at critical states. We can control the convergence rate of RL by adjusting A, and [[()). whereas BC does not benefit from this and incurs a suboptimality that matches the information -thooretic lower bound (Theorem 4.3). While this proof only considers one offline RI. algorithm, we conjecture that should be possible to generalize such an argument to the general family of offline RI. algorithms.
achieve better performance via offline RL than BC. In this simplified setting
Practical Observation 4.2. Offline RI. can be preferred over BC, even with expert or near- expert data, when either the initial state distribution changes during deployment, or when the environment has a few "critical" states.
4.3 COMPARISON UNDER NOISY DATA
lekumior daaiin eper
In practice, is often much more tractable obtain subop- timal demonstrations rather than expert ones. For example, suboptimal demonstrations can be obtained by running a scripted policy. From Theorem 4.1, we see that for
Offive with manry dite:
C* = + ((1/VN), BC will incur suboptimality that worse asymptotically than offline RL. In contrast, 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. we hy- pothesize that RL can actually benefit from suboptimal data when this improves coverage. In this section, we aim to answer the following question: Can offline RL with suboptimal data outperform BC with expert data?
Figure 2: Illustration showing the intu- ition behind noisy data. BC trained on ex- pert data (data composition is shown the left) may diverge away from the expert and find a poor policy that does not solve the task. If offline RI. is provided with noisy expert data that sometimes ventures away from the expert distrihution, RL. can use this data to learn to stay on course the goal. in the horizon. This implies, perhaps surprisingly, that offline RL with suboptimal data can actually outperform BC, even when the latter is provided expert data. Formally:
We show in Corollary 4.2 that, if the suboptimal dataset DD satisfies an additional coverage condition, then running conservative offline RL can attain Õ(VH) suboptimality
6

---

Published as a conference paper at ICLR 2022
Condition 4.2 (Coverage of the optimal policy). 3b [log H/N, 1) such that p satisfies: V(s, a) x A where d' (s, a) 2 b/ H, we have μu(s, a) 2 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 constraint on the empirical state-action visitations fi(s, a) instead of p(s, a) [53, 73]. This condition is reasonable when the dataset collected by e-greedy or a maaximum-entrop" expert. which standard assumption in MaxEnt IRI. [74]. 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 [21, 233. Existing work has also simulated trajectories to increase coverage, as was done in self-driving by perturbing the vehicle location [5], or in robotics using learned simulators [51]. For intuition, we provide an illustrative example of the noisy data that can help offline RL in Figure 2.
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 7t found by conservative offline RL can satisfy:
Hc ON
6N + Vb + C*
Hu
SubOpt(#*) S
+
N
If we take VH/N, then SubOpt (7 S Ó(VH).
The bound in Corollary 4.2 has Ö( scaling compared to Õ(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 Observation 4.3. Offline RL outperforms BC on expert data on long-horizon tasks, when provided with noisy-expers data. Thus, if nxisy- data is easy to collect (e.g. through scripted policies or by first running standard behavioral cloning, and then storing data from evaluations of the behavior-clone policy), doing so and then using offline RL. can lead to better results.
4.4 COMPARISON OF GENERALIZED BC METHODS AND OFFLINE RL
So far we have studied scenarios where offline RL. can outperform naive BC. One might now wonder how offline RL methods perform relative generalized BC methods that additionally use reward information to inform learning. We study two such approaches: (1) filtered BC [8], 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 [6], which fits Q-function for the behavior policy, then uses the values to perform one-step of policy improvement over the behavior policy. this section, we aim to answer how these methods perform relative to RL.
Filtered BC. expectation, this algorithm uses aN samples of the offline dataset DD for a E [o, 1] to perform BC on. This means that the upper bound (Theorem 4.1) will have worse scaling in N. For C = I, 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 ((VH) suboptimality, whereas even filtered BC would always incur worse ((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- addaattae--weighted update: #1 (a|s) = म (a)s) exp(1) (s, a)) (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-advane transitions. In Theorem 4.4, show that more than one step of policy improvement can improve the policy under Condition 4.2, for the special case of the softmax policy parameterization [2].
Theorem 4.4 (One-step is worse than k-step policy improvement). Assume that the learned policies are represented via a softmax parameterization (Fquation 3, Agarwal et al. f2]). Let th denote the
7

---

Published as a conference paper at ICLR 2022
policy obtained after k-steps of policy improvement using exponentiated advantage weights. Then, under Condition 4.2, the performance difference between Th and म is cower-bounder by:
k log Z,s) Σ k
H² N
- - ズ
Eanu
Hn
proof of Theorem 4.4 is provided in Appendix B.5, This result implies that when the average exponentiated empirical advantage 1/k Ei=1 log (s) large enough (i.e., 2 co for some universal constant), which is usually the case when the behavior policy is highly suboptimal, then for & O(H), multiple steps of policy improvement will improve performance, i.e., J( - =
Ó(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 Observation 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 logether to give better performance.
5 EMPIRICAL EVALUATION OF BC AND OFFLINE RL
Having characterized scenarios where offline RL. methods can outperform BC in theory, we now validate our results empirically. Concretely, we aim to answer the following questions: (1) Does an existing offline RL method trained on expert data outperform BC on expert data in MDPs with few critical points?, (2) Can offline RL trained on noisy data outperform BC expert data?, and (3) How does full offline RL compare to the reward-awar BC methods studied in Section 4.4? We first validate our findings on high- high-dimensional domains below, but we provide some diagnostic experiments on a gridworld domain in Appendix H.
Evaluation in high- nigh-dimensional tasks. Next, we turn to nigh-dimensional problems. We consider
diverse set of domains and behavior policies that are representative of practical scenarios: multi-stage robotic manipulation tasks from state (Adroit domains from Fu al. [14]) and image observa- tions [60], antmaze navigation [14], and 7 Atari games [3]. We use the scripted expert provided by Fu et al. [14] for antmaze and those provided by Singh et al. [60] for manipulation,
RL-trained expert for Atari, and human expert for Adroit [50]. We obtain suboptimal data using failed attempts from 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. [27] as a representative RL method, and utilize Brandfonbrener et al. [6] as representative BC-PI method.
Tuning offline RL and BC. Naïvely running offline RL can lead to poor performance, as noted by prior works [38, 12]. This is also true for BC, but, some solutions such as early stopping based on validation losses, can help improve performance. We claim that an offline tuning strategy is utilize the offline workflow proposed by Kumar et al. [30] to perform policy selection, and address overfitting and underfitting, purely offline. While this workflow does not fully address all the tuning issues, we find that it is sufficient improve performance. When the Q-values learned by CQL are extremely negative (typically on the Adroit domains), we utilize a -ecceiiin dropout regularization 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 [29] 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 tuned offline RL can work well. For tuning BC and BC-PI, we applied regularizers such as dropout on the policy to prevent overfitting in Adroit, and utilized larger ResNet [18] architecture for the robotic manipulation tasks and Atari domains. For BC, we report the performance of the best checkpoint found during training, giving BC unfair advantage, but we still find that offline-tunee offline RL can do better better. More details about tuning each algorithm can be found in Appendix F.
also crucial for offline RL. In our experiments
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 and Figure 3. While naive 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 RL. for antmaze (large) with
8

---

Published as a conference paper at ICLR 2022
Domain/ Behavior Policy
Task/Data Quality
BC
Naive CQI.
Tumed CQL.
AntMaze (scripted)
Medium, Expert
53.2%%:4.8,7 7%%
20.8% = 1.0%
55.9% +: 3.2%
Large, Expert
4.83%-110.8%
0.0%
0.0%
0.0% :: 0.0%
Medium, Expert diverse initaal
55.2%:16.7%%
19.0%
5.2%
67.0%
=: 7.3%
Lirge, Expert w/ divense initial
1.35%:100.5%
0.0 0.0%
5.1% = 6.9%
Manipulation (scripted)
mick-paac--pen-grayee Expert
14.5%--t:1.8%
12.3%
23.5% 6..5%%.-.0....
close-open-grane Expert
17.4%
20.0%:t..00%
49.7% 10.7%%1:5.449
open-grasp. Expert
33.2% 1%
22.8%-++5530
51.9%
Adruit (Human)
hammer- hummn,, Expert
71.0%
9.33%
62.5%
39.0% 00.0%
78.1% 98.1% d: 6.7%
door-human Expert
86.3%
6.5%
70.3%
27.2%
79.1 +: 4.7%
pen-human, Expert
73.0 % 9.11%
64.0% + 6.9%
74.1 + 1
relocate-humant Expert
0.0% # 0.0%
0.0% = 0.0%
0.0% + 0.0%
Table 1: Offine CQL vs. BC with expert dataset compositions averaged over 3 seeds. While naïve offline CQL often performs comparable or worse than BC, the performance of offline RL improves drastically after offline tuning. Also note that offline RL can improve when provided with diverse initial states in the Antmaze domain. Additionally, note that offline- tuned offline RL outperforms BC significantly in the manipulation domains.
Median
IQM
Mean
Optimality Gap
BC with (Noisy Expert)
BC (Export)
Naive COL (Expert)
Tuned CQL (Export)
CQL (Noisy Expert)
0.4
0.6
0.8
1.0
0.6
0.8
1.0
0.6
0.8
1.0
0.2
0.3
0.4
0.5
Normalized Score IQM performance of various algorithms evaluated on 7 Atari games under various dataset composi- tions (per game scores in Table 3). Note that offfine-tuned CQL with expert data ("Tuned CQL") outperforms cloning the expert data ("BC (Expert)"), even though naive CQL is comparable to BC in this setting. When CQL is provided with expeet data, it significantly outperforms cloning the expert policy.
Figure 3:
expert data, it performs worse than RL when the data admits a more diverse initial state distribution such that C* * 1, even though the behavior policy matches the expert.
For (2), we compare offline RL trained on noisy- expert data with BC trained on on an equal amount of expert data, on domains where noisy- expert data is easy generate: (a) manipulation domains (Table 2) and (b) Atari games (Fig- ure 3). Observe that CQL outperforms BC and also improves over only using expert data. The performance gap also increases with H, i.e., open-grasp (H- 40) vs plw-c--ppe----eeeeeeee-ee----eee 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.
Task
BC (Expert)
CQL (Noisy Expert)
pleck-pacce-pen-gee close open grasp open-grasp
14.5% 1.8%
85.7%
3.1%
17.4%
3.1%
90.3%
2.3%
33.2% + 8.1%
92.4% + 4.9%
Table 2: CQL with noisy-expert data vs BC with expert data with equal dataset size on manipulation tasks. CQL outperforms BC as well as CQL with only expert data.
Finally, for (3), we compare CQL. to representative BC-PI method [6] 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 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.
6 DISCUSSION
We sought 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 approaches 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 nxisy-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 offline RL can outperform BC on various practical problem domains, with differentt kinds of expert policies. While our work is an initial step towards understanding when RL presents 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 sal-d data distributions is also important. Finally, 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 this discussion.
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank Dibya Ghosh, Su, Xinyang Geng, Tianhe Yu, Ilya Kostrikov and Michael Janner for informative discussions, Karol Hausman for providing feedback on an early version of this paper, and Bo Dai for answering some questions pertaining to Ren et al. [53]. AK thanks George Tucker for informative discussions. We thank the members of RAIL at UC Berkeley for their support and suggestions. We thank anonymous reviewers for feedback on an early version of this paper. This research is funded in part by the DARPA Assured Autonomy Program, the Office of Naval Research, an EECS departmental fellowship, and in part by compute resources from Google Cloud.
REFERENCES
[1] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with generative model minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[3] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. In International Conference on Machine Learning (ICML), 2020.
[4] Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. J. Artif. Int. Res., 47(1):253-22) 2-99,, May 2013. ISSN 1076-9757.
[5] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp. Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint arXiv:1604.0733 2016.
[6] David Brandfonbrener, William F Whitney, Rajesh Ranganath, and Joan Bruna. Offline rl without off-policy evaluation. arXiv preprint arXiv:2 106.08909, 2021.
[7] Jinglin Chen and Nan Jiang. Information-theoreii considerations in batch reinforcement learning. ICML, 2019.
[8] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Michael Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. arXiv preprint arXiv:2 2021.
[9] Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k off-policy correction for a reinforce recommender system. Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, pp. 456-464,7 2019.
[10] Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning. Shane Legg, and Koray Kavukcuoglu. IMPALA: scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning, 2018
[11]
Farahmand, Csaba Szepesvári. and Rémi Munos. Error propagation for approxi- mate policy and value iteration. In Advances in Neural Information Processing Systems (NIPS), 2010.
[12] Pete Florence, Corey Lynch, Andy Zeng, Osear A Ramirez, Ayzaan Wahid, Laura Downs, Adrian Wong, Johnny Lee, Igor Mordatch, and Jonathan Tompson. Implicit behavioral cloning. In 5th Annual Conference on Robot Learning, 2021. URL https: http////ppeeeeeee/eeeeeee/ net/
forum?
[13] Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep Q-learning algorithms. arXiv preprint arXiv: 10250, 2019.
10

---

Published as a conference paper at ICLR 2022
[14] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning, 2020.
[15] Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning. arXiv preprint arXiv:2 (0t.020000000000 2021.
[16] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. arXiv preprint arXiv:/8/2.02900 2018.
[17] Meera Hahn, Devendra Chaplot, Shubham Tulsiani, Mustafa Mukadam, James Rehg, and Abhinav Gupta. No rl, no simulation: Learning to navigate without navigating. In Advances in Neural Information Processing Systems, 2021.
[18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
[19] Natasha Jaques, Judy Hanwen Shen, Asma Ghandcharioun, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Shane Gu, and Rosalind Picard. Human-centric dialog training via offline reinforcement learning. arXiv preprint arXiv:2010.0584; 2020.
[20] Ying Jin, Zhuoran Yang. and Zhaoran Wang. pessimism provably efficient for offline ri? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021.
[21] Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning. pp. 651-673, 2018.
[22] Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning, pp. 651-673. PMLR, 2018.
[23] Dmitry Kalashnikov, Jacob Varley, Yevgen Chebotar, Benjamin Swanson, Rico Jonschkowski, Chelsea Finn, Sergey Levine, and Karol Hausman. Mt-opt: Continuous multi-tast robotic reinforcement learning at scale. arXiv preprint arXiv:2104.08212, 2021.
[24] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model-based offline reinforcement learning. arXiv preprint 0rXiv:2005.05995 2020.
[25] Ilya Kostrikov, Jonathan Tompson, Rob Fergus, and Ofir Nachum. Offline reinforcement learning with fisher divergence critic regularization. arXiv preprint arXiv:2103.08053) 2021.
[26] Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off- off-policy q-learming via bootstrapping error reduction. Advances Neural Information Processing Systems, pp. 1 11761-11771 2019.
[27] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint rrXiv:2006.04779 2020.
[28] Aviral Kumar, Rishabh Agarwal, Dibya Ghosh, and Sergey Levine. Implicit under- parameterization inhibits data-efficient deep reinforcement learning. International Con- ference on Learning Representations, 2021. URL https: :ttttpp::///ppee/e//e //opnreveeiieeeeeeeee ew net/ forum? id=O9bnihsF EXU.
[29] Aviral Kumar, Rishabh Agarwal, Tengyu Ma, Aaron Courville, George Tucker, and Sergey Levine. DR3: Value-Based Deep Reinforcement Learning Requires Explicit Regularization. arXiv preprint arXiv:21 2021.
[30] Aviral Kumar, Anikait Singh, Stephen Tian, Chelsea Finn, and Sergey Levine. A workflow for offline model-free robotic reinforcement learning. 5th Anmual Conference on Robot Learning, 2021. URL https: /openrvviiiveeeoeooooeeee ew. net formm? i d= fy4 ZBWxYbTo.
11

---

Published as a conference paper at ICLR 2022
[31] Vladislav Kurenkov and Sergey Kolesnikov. Showing your offline reinforcement learning work: Online evaluation budget matters. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[32] Sascha Lange, Thomas Gabel, and Martin A. Riedmiller. Batch reinforcement learning. In Reinforcement Learning, volume 12. Springer, 2012.
[33] Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International Conference Machine Learning, pp. 3652-3661. PMLR, 2019.
[34] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01645 2020.
[35] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. CoRR, hbss/194.00877, 2019.
[36] Yao Liu, Adith Swaminathan, Alckh Agarwal, and Emma Brunskill. Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08200 2020.
[37] Ajay Mandlekar, Fabio Ramos, Byron Boots, Silvio Savarese, Li Fei-Fei, Animesh Garg, and Dicter Fox. Iris: Implicit reinforcement without interaction at scale for learning control from offline robot manipulation data. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 4414 4420. IEEE, 2020.
[38] Ajay Mandlekar, Danfei Xu, Josiah Wong. Soroush Nasiriany, Chen Wang, Rohun Kulkarni, Fei-Fei Li, Silvio Savarese, Yuke Zhu, and Roberto Martin-Martin. What matters in learning from offline human demonstrations for robot manipulation. In 5th Annual Conference on Robot Learning, 2021. URL https: /ttt:::://pperevviie
net forum? id id-JrsfBJtDDdd
[39] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arxiv preprint arxiv:0907.3744) 2009.
[40] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1312 2013.
[41] Rémi Munos. Error bounds for approximate policy iteration. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML'03, pp. 560-567. AAAI Press, 2003. ISBN 1577351894.
[42] Rémi Munos. Error bounds for approximate value iteration. In AAAI Conference on Artificial intelligence (AAAI), pp. 1006-1011, AAAI Press, 2005.
[43] Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Al- gaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv: 2019.
[44] Kimia Nadjahi, Romain Laroche, and Rémi Tachet des Combes. Safe policy improvement with soft baseline bootstrapping. arXiv preprint 10X.::907700507 2019.
[45] Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online rein- forcement learning with offline datasets. arXiv preprint arXiv:2006.09335 2020.
[46] Xue Bin Peng, Angjoo Kanazawa, Jitendra Malik, Pieter Abbeel, and Sergey Levine. Sfv: Reinforcement learning of physical skills from videos. ACM Transactions On Graphics (TOG), 1716) 2018.
[47] Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. Advantage-weighte regression: Simple and scalable off-policy reinforcement learning, arXiv preprint 1rXv:0190.00017. 2019.
[48] Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994.
[49] Nived Rajaraman, Lin F Yang, Jiantao Jiao, and Kannan Ramachandran. Toward the fundamen- tal limits of imitation learning. arXiv preprint arXiv:2009.05999 2020.
12

---

Published as a conference paper at ICLR 2022
[50] Aravind Rajeswaran, Vikash Kumar, Abhishek Gupta, Giulia Vezzani, John Schulman, Emanuel Todorov, and Sergey Levine. Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. In Roboties: Science and Systems, 2018.
[51] Kanishka Rao, Chris Harris, Alex Irpan, Sergey Levine, Julian Ibarz, and Mohi Khansari. RI- cyclegan: Reinforcement learning aware simulation-to-real. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11157-1 2020.
[52] 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,001111 2021.
[53] Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. arXiv preprint 1:Xiv:2/03.44077 2021.
[54] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In International Conference on Artificial Intelligence and Statistics (AISTATS). pp. 661-668, 2010.
[55] Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, Devi Parikh, and Dhruv Batra. Habitat: A Platform for Embodied AI Research. In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), 2019.
[56] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. International Conference on Learning Representations (ICLR), 2015.
[57] Dhruv Shah, Benjamin Eysenbach, Gregory Kahn, Nicholas Rhinehart, and Sergey Levine. Ving: Learning open-world navigation with visual goals. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 13215-13222. IEEE, 2021.
[58] Susan M Shortreed, Eric Laber, Daniel J Lizotte, T Scott Stroup, Joelle Pineau, and Susan A Murphy. Informing sequential clinical decision-making through reinforcement learning: an empirical study. Machine learning, (111-2):109-13:: 2011.
[59] Noah Y Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Neunert, Thomas Lampe, Roland Hafner, and Martin Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning, arXiv preprint arXiv:2002.08339. 2020.
[60] Avi Singh, Albert Yu, Jonathan Yang, Jesse Zhang. Aviral Kumar, and Sergey Levine. Cog: Connecting new skills to past experience with offline reinforcement learning. arXiv preprint arXiv:2010. 14500, 2020.
[61] Samarth Sinha, Ajay Mandlekar, and Animesh Garg. S4RL: Surprisingly simple self-supervision for offline reinforcement learning in robotics. In 5th Annual Conference on Robot Learning, 2021. URL https:/t///.. /wwprrveeeeeeeeeee ew. net. / fo rum? i d= 3=CC5NNN
[62] Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. J. Mach. Learn. Res, 16:1731-1755, 2015.
[63] L. Wang, Wei Zhang, Xiaofeng He, and H. Zha. Supervised reinforcement learning with recurrent neural network for dynamic treatment recommendation. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018
[64] Ruosong Wang, Dean Foster, and Sham M. Kakade. What are the statistical limits of offline frl} with linear function approximation? In International Conference on Learning Representations, 2021. URL
[65] Ziyu Wang, Alexander Novikov, Konrad ZoIna, Jost Tobias Springenberg, Scott Reed, Bobak Shahriari, Noah Siegel, Josh Merel, Caglar Gulcehre, Nicolas Heess, et al. Critic regularized regression. arXiv preprint arXiv:2006. 15134, 2020.
[66] Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning, arXiv preprint ArXiv:1911.113 2019.
13

---

Published as a conference paper at ICLR 2022
[67] Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A coretical comparison. 2020.
[68] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. arXiv preprint, 2021.
[69] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. arXiv preprint arXiv:2005. 13239, 2020.
[70] Tianhe Yu, Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran. Sergey Levine, and Chelsea Finn. Combo: Conservative offline model-based policy optimization. arXiv preprint arXiv:2/02.08363, 2021.
[71] Andrea Zanette.
Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. arXiv preprint arXiv:2012.08005. 2020.
[72] Yufeng Zhang, Qi Cai, Zhuoran Yang. Yongxin Chen, and Zhaoran Wang. Can temporal- difference and q-learning learn representation? mean-field theory. arXiv preprint arXiv:2006.04766 04761, 2020.
[73] Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp. 4528-4531 PMLR, 2021.
[74] B. D. Ziebart, A. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In International Conference on Artificial Intelligence (AAAI), 2008.
14

---

Published as a conference paper at ICLR 2022
Appendices
A PSEUDOCODE FOR ALGORITHMS
Algorithm 1 Conservative Offline RL Algorithm
Require: Offline dataset D, discount factor and confidence level
I: Compute n(s, a) from D, and estimate F(s, a). P(s'|a a), v(s,a) ES 2: Initialize (ss, a) < 0, (ss) + 0, V(s,a) a)
3: for i = 1, 2. m do
4: Calculate bi(s, a)
v V(P a), V) log([S) Alm/8))
+ 7(s a) ass.a)lo(([S (A)mm)))))mmm (m(s, a) A
b(s,a) +
(n(s, a) 1)
(n(s, a)
S: Calculate 7" (s)
(s, a) t F(s, a) b(s. a) a)),
(ss) f max ((,
(s) t max (s,
6: Return R*
Algorithm 2 Policy- Constraint Offline RL Algorithm
Require: Offline dataset 2, discount factor 7, and threshold
I: Compute n(s, a) from D, and estimate F(s, a). P(s' fs/ls, a), a), ((s 6
2: Compute ((s, a) + [[,(s, a) 2 6}, v(s, a)
Initialize ?aaass) +- T Q as) < o. V (s) c V(s.a)
4: for = 1.2,..., do
for = 1,2.....,
6: Update &7 (s. a), V.5' (s)
Q (s, a) + f(s, 77(,a) D2
V (s) + Σ #* (als) a) (ss.a)
7: Compute #1
* - arg max ELND En (((s,a) a) (s, a)
8: Return *
B PROOFS
B. PROOF OF THEOREM 4.1
Let Fy the behavior policy that we fit our learned policy 7. to. Recall that the BC algorithm we analyze fits 7h to choose actions according to the empirical dataset distribution for states that appear in dataset D, and uniformly at random otherwise. We have
Ep [T(")) ( < J(x') ((5)) Ep ( ((a)]
The following lemma from Rajaraman et al. [49] 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.
15

---

Published as a conference paper at ICLR 2022
Lemma B.1 (Theorem 4.4, Rajaraman al. [49]). The policy returned by BC on behavior policy Rg has expected error bounded as
SH log N
ED (D( - J(Rg)] -
N
where a could be stochastic.
Using Lemma B.I, we have Ep (T)) < SHi/N. What remains is bounding the suboptimality of the behavior policy, which we can upper-bound
- -
'P (st = Bmp( n. (s)H]
1
di (s)
(aa() Ifa (s))
b (s) di (s. a)l
2
1=0
(s.a)
1
H
a( 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.
B.2 PROOF THEOREM 4.2
In this section, 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 penalty during each Q-update. Specifically, we initialize Qo(s,
0, Vo(s) 0 for all (s, a). Let ns, a) be the number times (s, a) appeared in D, and let f(s, a), P(s, a) be the empirical estimates of their reward and transition probabilities. Then, for each iteration i [m]]
(s a) - F(s, a) (s. a) + 7 a) Pi-1. for all s, a,a. (((() <- max (V-x max as) for 8,
In our algorithm we define the penalty function as
V ((((s, a), Pi-1)e (n(s, A)
F(s, a)e (n(s,a) A1) (n(s,a))
as) -
where we let to capture all poly-logaic terms. As notation, we drop the subscript i to denote the final Q and V at iteration m, where H log N. Finally, the learned policy #* satisfies (s) E arg max, @(s a) for all 8, if multiple such actions exist, then the policy samples an action uniformly at random.
B.2.1 TECHNICAL LEMMAS
Lemma B.2 (Bernstein's 's inequality). Let X, (X,),_ be i.idd random variables with values in [0, 1).
and let 8 0. Then we have
1
2ar X log(2/0)
log(2/8)
P
E
X
X
88.
7
16

---

Published as a conference paper at ICLR 2022
Lemma B.3 (Theorem 4, Maurer & Pontil [39]). Ler X, [ with 2 2 be i.idd random
variables with values in [0, 11. Define X 2x X; and Var(X) S. (X; x)² Ler 5 > O. Then we have
Var log(2/0)
7 (2/()
IP
[
B
Σ
X
+
5..
3(n 1)
Lemma B.4 (Lemma 4, Ren al. [53]). Let X1, O be constants. Let f Z20 function such that f(i) S H, Vi and f(i) satisfies the recursion
R be
f(i) S +)
X2
Then, we have that f(0) 6((A 22).
B.2.2 PESSIMISM GUARANTEE
The first thing we want to show is that with high probability, the algorithm provides pessimistic value estimates, namely that (s) (*)s) for all E [7] and S. To do so, we introduce notion of "good" event, which occurs when our empirical estimates of the MDP are not far from the true MDP.
We define E to be the event where
v(P(s, a), Vi)a (n(s, a) A1)
(P(s.a) a) P(s,a)) V
(3)
(n(s,a) A
holds for all i E [m] and (s.a) ES A. We also define & to be the event where
F(s,
((s,a) (os,a)-(ss.a)) r(s, S V (n(s,a) A1) (n(s,a)
(4)
holds for all (s,
We want to show that the good event & = = E n &S occurs with high probability. The proof mostly follows from Bernstein's 's inequality in Lemma B.2. Note that because P(s, a), V, are not independent, we cannot straightforwardly apply Bernstein's inequality. We instead use the approach of Agarwal et al. [1] who, for each state 8, partition the range (s) within a modified s-absorbing MDP to create independence from P. The following lemma from Agarwal et al. [1] is result of such analysis, and is slightly modified below account for bounded returns of trajectories, iee., Vi(s) 1:
Lemma B.5 (Lemma Agarwal et [1]). For any iteration state-action (s, a) E S x A such that ns, a) 2 1, and > O, we have
P [1((s.a) P(s,a)) R
a(P(s,)), + n(s, a) ni(s, a)
58.
Using this, we can show that & occurs with high probability:
Lemma B.6. (E) 2 1 - 2|SS|
Proof. For each and (s, a), if n(s, a) < 1, then equation 3 and equation 4 hold trivially. For nss a) 2 2, we have from Lemma B.5 that
P [[P(s.)) P(s,a)) v
v(P(s, V.)e n(s, a)
v
S6.
n(s a)
17

---

Published as a conference paper at ICLR 2022
Similarly, use Lemma B.3 to derive
f(s,a)
P F(s. (js,a)-r(er r(s,a)) > V as
+ L
n(s,
Var(F(s, a))
S (((s.a) - -r(s, a) V 2(n(s. a) - 1) 2(n(s. a) -1)
26,
where we use that Var(F(s, a)) S F(s, a) for [0, rewards, and with slight abuse of notation, let capture all constant factors. Taking the union bound over all and (s, a) yields the desired result. C
Now, we can prove that our value estimates are indeed pessimistic. Lemma B.7 (Pessimism Guarantee). On event we have that Vi(s) S V (s) S (s) for any iteration i E [m] and state s E S.
Proof. We aim to prove the following for any and Vi-1(s) Vi(s) S V (s) (s)... We prove the claims one by one.
(s) v (s):: This is directly implied by the monotonic update of our algorithm.
(s(s) < V (s): We will prove this via induction. We have that this holds for Vo trivially. Assume it
holds for 1, then we have
V (s) > (H6) [(ss,a) PP((s, Pi-1]
2 Eu a(s,a) - a) P V +
Ea (s(ss)) r(s, (P(ss a) - P(s. -
V((s))
where we use that
v(P(s, a), P/:
F(s,
(s a) V (n(ss a) A 1)
+ +1 (n(s,a)A1) A1) a)
2 (f(s.)) - r(s, a)) + (P(s,)) - a(s, Vi-1
under event E
Finally, the claim of V (s) S (*) 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.S. On event E, the following holds for any E [m] and (s, A:
(s,
5 ((( Q-1((==))) + 2h. a),
(5)
where f(;xx) satisfies f(;; = m()sssss(ss
Proof. We have,
(s - (s)
= =s(s,a) + + V - b(saa) v/-1)
= b,,ss + f(s. +P((s, (V- ((s.a)) Vi-
<>P(s,a) (V'- - + (b,
$ >PP(s,)) (Q"(;=") Q-1((:)7)) + (s.
18

---

Published as a conference paper at ICLR 2022
The first inequality is due by definition of & and the second is because V 2 max, Q1-1(;,0) 2 (+(..)).
By recursively applying Lemma B.8, we can derive the following value difference lemma: Lemma B.9 (Value Difference Lemma). On event &, at any iteration i [mn], we have
J(
E
(6)
[s.a]
where as) P (s. a a; 7*)
Proof. We have,
= Bp (s) v='(s) s SEp (V*(s) - s (:0'' (((7')))
where we use Lemma B.7 in the first inequality. As shorthand, let px E R(SxA)x(SxA) where (s a, s','') P(s'ls, |s, ()'(d'ss') be the transition matrix for policy x. Now, we can apply Lemma B,8 recursively to derive
-.) S0 (7pE' (Q (Q-))-1)+20
$ p"¹ (7pbr (7prr (Q" -Qi_2) + 26t--1) +2bi)
S sp (p'**) -Qo) + Σ p"
S 5/1+22 Σ di
where we use that di = p²¹ (Px")e This yields the desired result.
Now, we are ready to bound the desired quantity SubOpt(F*) = Ep [1(=*) -(( ((*'). We have
Ep [0(7))")-a -(*"") Ep Σ (((s)(( V v$))
ED
T{E) Σ ((s)(V V* (s))
Ep [1(3s E 8, nis n. (s)) 0) Σ ((s)(V V (s)))-aa
Ep [I['' S, (s) > 0]1{}} Σ p(s)(V y (s))}=a.
We bound each term individually. The first is bounded as A < P (8) < [) S for choice
of 8 HN
19

---

Published as a conference paper at ICLR 2022
B.2.4 BOUND ON A2
For the second term, we have
A S Σ Bs [[n(s = =0}
$ H d' (s, Es) [ (s)) = 0H
$ O'
H Σ
pls, n (s)) (ss))
4C"|8|H
9N
where we use that p(s) S (s,
T" (s)), and that maxpe p(1 -p) s EN.
B.2.5
BOUND ON A3
What remains is bounding the last term, which we know from Lemma B.9 is bounded by
Ag S N + 2ED [T(Vs E S, n(s (s))
m m di (8,, a)be a)},
1= (s.a)
where we use that nmh s tor for m H log N. Recall that (, a) given by
ass v(P(s, a), a), 1o-1)e n(s, a)
f(s, a)) n(s, a)
n(s a)
We can bound the summation of each term separately. For the third term we have,
m
m
EE
7 m- t
a)
7 (s, AD a))
m
n(s,al a)
(s.a)
(s,a)
rdd (s, x (s))
(
H
Σ
(1-7)
(s
N
pls, m (s))
t=
CH
N
Here we use Jensen's inequality and that (1 - 7) -) (s, a) S SC*M(s, a) for any (s, a). For the second term, we similarly have
a(s,
Ep
m- dx (s,
V
ass
(s,a)
< EE
7m1 cd m
(s, a)
m
de
(s, (s)
n((s, a)
(s.a)
(5.a)
S Hc
<
N
20

---

Published as a conference paper at ICLR 2022
where Cauchy-Schward then Condition 3.2 to bound the total estimated reward. Finally, consider the first term of be (s,
mP
V(P(s a). 11-1)u
ED
m- d (s,a))
V
(1s,a) a)
[s,ax)
P
7 m c
(8,
7 mm (s.a)) P.-1)
n((s a
(8,a)
(8.a)
CH N
-m (s, D.1))
(s.a)
Similar to what was done in Zhang et al. [72], Ren al. [53] for finite-horizon MDPs, bound this term using variance recursion for infinite-horizon ones. Define
1(1) =
mm m- (5.7,,)) (P-1))))
(8)
(s.a)
Using Lemma of Ren al. [53] for the infinite-horizon case, we have the following recursion:
f(i) S
f(i+1)+
+ + (++1),
N
N
where
H
m
d (s. a), P P()
(9)
N
N
(s.a)
Using Lemma B.4, we can bound f(0) -0
C'
1 +
Using that for constant
N
HH
f(0) + CH
N
N
HL
(OC-18HH
C'
+c++c)
N
N
N
20C*|S|Hi
2
N
we have that
4
< +
N
Substituting this back into the inequality for /b yields.
② o o0 C* SH
C* S
Finally, we can bound
CH
HH
A
N
Combining the bounds for the three terms yields the desired result.
21

---

Published as a conference paper at ICLR 2022
B.3 PROOF OF COROLLARY 4.1
In this section, we will provide proof of Corollary 4.1.
Intuition and strategy: The intuition for why offline RI. can outperform BC in this setting, despite the near-expert data comes from the fact that RL can better control the performance of the policy on non-critical states that it has seen before in the data. This is not true for BC since it does not utilize reward information. Intuitively, we can partition the states into two categories:
1. critical states including those that are visited enough and those that are not visited enough in the dataset - bound this via the machinery already discussed in Appendix B.2.
2. non-critical states - offline RL can perform well here: we show that under some technical conditions, it can exponentially fast collapse at good-enough action at such states, while BC might still choose bad actions.
We restate the definition of non-critical points below for convenience.
Definition B.1 (Non--ritiecl points, restated)). A state is said be non-critical (i.e., C) if there exists a subset (s) of s-good actions, such that,
Va E G(s), max ("((s)) c H' Va A (()), max max("(s.a')- Q' A(s).
and
and A(s) S Ao. where we will define Do later.
Recall that our condition on critical states was that for any policy æ in the MDP, the expected occupancy of critical states is bounded by Pe and Pe S I We restate this condition below: H. Condition B.1 ((Occupancy of critical states is low, restated)). For any policy the total occupancy of critical states in the MDP is bounded by Po. i.e.,
Σ d (s) ( SEC
Now, using this definition, will bound the total suboptimality of RL separately critical and non-critical states. At critical states, i.e., scenario (1) from the list above, we will reuse the existing machinery for the general setting from Appendix B.2. For non- non-critical states (2), we will utilize stronger argument for RL that relies on the fact that As and [(() are large enough, and consider policy-constraint offline RL algorithms that extract the policy via pessimistic policy extraction step.
This policy constraint algorithm follows Algorithm 2, but in addition to using the learned Q-function for policy extraction, it uses a local pessimistic term in Step 7, i.e.,
arg max BLND F Q* ab(s, a)
(10)
where b(s, a) refers to the bonus (Equation 2) and a > 0. This modification makes the algorithm more pessimistic but allows to obtain guarantees when a(s,a),no n(,, a) no the probability that the policy makes a mistake at a given state-action pair in terms of the count of the given state-action pair. Finally, as all state-action pairs are observed in the dataset, the learned
express
Q-values, @ can only differ from Q' in bounded manner, i.e., @ a) Q" (s. a) S Eo-
Lemma B.10 (Fast convergence non-critical states.). Consider a non-critical state E DD such that [D(s)] 2 no and let Va E A, n" (n|s)
p(als) < a < 2, where p(als) the conditional action distribution at state s. Then, the probability that the policy TRL obtained from the modified offline RL algoritium above does not choose a good action at state is upper bounded as (co is universal constant):
a²
(S(s)
172
P (f) & G()) < exp
(-no- 2(a
(c10 AA)
22

---

Published as a conference paper at ICLR 2022
Proof. First note that:
P (() $ [(s)] = P Ja & ((s), s.t. Va, E ((s). @(s,a) - ob(s.a) 2 a(s. - ob(s,
< P & (()), s.t. Vag E ((s), (s a) (s, 2 @(s.ag) - (s. + A ob(s,ag)
P Ma Eg(s) (ob(s, ag) 2 A 2
P (9)) (n(s, a) S m>)):
where na corresponds the maximum value of n(s, a) such that
A
280
b(s, a) vn(ssa)A1 A1
(11)
n(s.a) A1
We can then upper bound the probability using a Chernoff bound for Bernoulli random variables (the Bernoulli random variable here is whether the action sampled from the dataset p(als) belongs to the good set (s) or not):
(ee((s)) (n(s, S (n)(s)) SP
Σ n(s, S ((s))na(s)
mEG(s)
Ener(s) n(ss a)
(n(s)
P
no
n0
[(s))
-noKK.. KL. Bem
Bemm(1/a))
exp
7g
The above expression can then be simplified using the inequality that KL(p + allp) 2 2p(1-pp if
p 2 1/2, which the case here, since p = a and a S 2. Thus, we can simplify the bound as: 2
a²
[g(s) [[((s) (a((s)
2(a - 1) P ([negg)) (n(s,a) S [s)ss) s exp (-no-
no
To finally express the bound in terms of (s)), we note that the maximum-valued solution n. (8) to Equation 1I satisfies (s) co+A(s)) Substituting the above in the bound, we obtain:
a²
G[s) no (cio A)
1 a
PP (Nees(e) (n(s, a) S ( S exp
-no 2(a 1)
for some universal constants Co and C1-
We will now use Lemma B.10 prove the formal comparison of RL and BC when only a few critical states are encountered in given trajectory (i.e., under Condition B.
Theorem B.1 (Critical states). Assume that the data distribution μ satisfies p(s) == d= (s) 1 and
n(s)
C < 11 + N. Let A(s) 2 for all & C. Then, under Condition B.1, for an appropriate value of An and Pe S H. the worst-case suboptimality incurred by conservative offline RI. is upper bounded by the lower bound on performance from BC from Theorem 4.3, i.e.,
SubOpt(fRl)) S SubOpt(Frcc).
Proof. For any learning algorithm that returns policy # the suboptimality is given by:
J J( H Σ (s) (Q' (s: T3) (s;;s
H Σ l (s)(()))))
+H
Σ de (s" (s;
sgc
term (i): bound using techniques from Appendix B.2
term (it): we control this term better for RL
23

---

The first equation corresponds bounding the suboptimality due to good actions. The second term above bounds the suboptimality due to bad actions. The first term controlled as best as it can using the definition of critical states. The second term can be controlled by applying Lemma 1. Further note that since V(s, a), d" (s.a) p(s.a) < C*, and per the assumption in this theorem, Vs, d" (s) 1, where Published as a conference paper at ICLR 2022
The first term (i) corresponds to the value difference critical states, and the second term corresponds to the value difference at non-critical states. To bound the first term, we can consider as the value difference under modified MDP where the advantage for all actions at all states that are non-critical One way to construct such an MDP is to take each É C and modify the reward and transitions so that r(s, a) r(s. >r" (s)); P(s, a) P(s, x (s)) for all actions. Let denote the performance function for this modified MDP be Jc. then we have
J(x") J( S Je(#*) - Je(a") +
The first term be bounded as was done in Appendix B.2. Namely, we can show the following equivalent of Lemma B.9:
- Je( S
Bounding this for i Hi can be done exactly in was done in Appendix B.2.4 and B.2.5, except with the dependence on all states S replaced by only the critical ones. We get the following bound:
- S C' C'PoSSH N
N
Now, will focus the second term, which will control tightly for RL using Lemma B.10. We can decompose this term into separate components for good and bad actions:
ΣΣ of (a)s* (s; Q" (s,aa))
Ep [term (ii)
ED
LOEC DEAA
EE
Σ Σ
d' (s.
ED
Σ SEC REAAG((s)
Σ
((sa) Q(
sgC nEG(s)
We bound each term independently:
ED
Σ ΣΣ sgC nES(s)
de (s==)
$ SED
Σ lht (s) (G(s)ss) &
H
Ep
Σ
Σ
8' (s:T))(((=))))(((
< EE
(s) (1 (1- ((())
BBC aEA-g(s)
LBdC
p(s)
we assume that 0/0 are interested in the setting where C* 1 + O ) and result, J. R N4T upper bound for term (ii) is given by:
C², Also note that this case, Therefore, at each state, Ys, a, u<aas))
x (ala)
N_
Therefore, the
ED
*" (G(s))s)) A(s)
LECC
(N + 1)a
((())ooo
+ 112 N N+1
<
EED
f (8)
A(s) exp
-700
2(N)
(cro A(s))
Lo4C
-nu (N + 1)²
[((s)Coo
1+11
< (1 Po)
Ag exp
fN + 1, 1,))
2(N)
no (c10 + Ao)
N
24

---

Published as a conference paper at ICLR 2022
where 1 Pe appears from the condition of bounded critical states (Definition 4.1). On the other hand, the corresponding term for BC grows as
1 and is given by:
N+1
ED
Σ d (8) - (1- (G()))s)) (ss)
x (1 - po) max (s) N+1 = gno(N (N + 1, A,)
Lgc
The bound for BC matches the information- thhooreticc lower-bound from Theorem 4.3, implying that this bound is tight for BC.
We will now compare the bounds for RL and BC by noting that the function h(N, A) fRL (N +1,4
gie +1,4]
can be set to S VH since f is exponential function of -N, and decays linearly in N, by controlling Do and [ are implicitly defined as a function of N. Per condition (Condition B. A > Ao. then h(N, A) O (H). This means that the suboptimalities of RL and BC compare as follows:
C- + C'Pe -11-Pe) Pe)
SubOpt(fRI.) SubOpt(#BC))
Pc
VH
PeN + (1 -Pe)
By setting P. t. we get
SubOpt(fRc) Z SubOpt(fRR)) H 2 SubOpt(fRr.)
B.4 PROOF OF COROLLARY 4.2
The proof Corollary 4.2 is slight modification 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 7, which we restate below:
Ep [J(=T) [ Ed
{{}} Σ (s))( V (s))
A
ED [1 S, n(s, T" (s)) 0] Σ p(s) - V (s)))az
ED [I(ts E 8, n(s, x (s)) 1|1{8) Σ (V)) v* (s)))
A is bounded by N as before.
B.4.1 BOUND ON A2
The bound for Ag changes slightly from Appendix B.2.4 due accounting for the lower-bound on ((s a)
log f!
We have
N
A <
p(s) [n(ss x (s)) = 0}}
x" < Σ d' ((), ( (Hn(s, (s)) = =]}
< Σ d' TT (s)
_ + H Σ d'sss [Ifn(s, =*)ss = 0}}
< <| C² Σ u(s, n" (s)) u(s x (
1 C*
<
N where we use that p(s) = Hd (s, T" (s)), and that
log Hl
(1 11-
log H1
log Hl HN
max p log #
p(1 p) <
<
.1]
N
N
25

---

Published as a conference paper at ICLR 2022
B.4.2
BOUND ON As
Due to the lower bound on (s(s.a) 2 b, we can instead bound,
m
m
Ep
(s, m(s,a) a)
(s)
n(s,a)
(s.0)
(5.0)
(s, Nu(s;
1=0
< (s,
a)
- H1 | Σ
(1 (1- En 2ddd(s
1=0
H1
Σ
(1 71
Σ
2 ( (s))
Nc
t=0
Hi
< b+
bN
The analysis for bounding Aa proceeds exactly in Appendix B.2.5 but using the new bound. Namely, we end up with the recursion
H f(i) S V bN
Hi + b f(i+1))
+b+ 2 1),
bN
where
H ON
Hi (s as P(-1) Nb
+ b
m
+ b.
[=1
Using Lemma B.4 and proceeding in Appendix B.2.5 yields the bound
H
H Vb..
Aa
+
bN
bN
Combining the new bounds for 22, Ag results in the bound in the Corollary 4.2.
B.5 PROOF OF THEOREM 4.4
The proof of Theorem 4.4 builds on analysis by Agarwal et al. [2] that we apply to policies with softmax parameterization, which we define below.
Definition B.2 (Softmax parameterization). For a given E [| Ta(a|s)
exp(S.a)
E. exp(o_,.)
We consider generalized BC algorithms that perform advintage-weightedd policy improvement for improvement steps. A BC algorithm with k-step policy improvement is defined follows:
Definition B.3 (BC with k-step policy improvement). Let Â* a) denote the advantage of action state under a given policy Tiy where the policy a **(ss) is defined via the recursion:
* * (als) := f exp(n Ā' (s,
(s(s)
starting #0 (a(s) = Tg.. Then, BC with k-step policy improvement returns #
This advantage weighted update utilized in practical works such as Brandfonbrener al. [6], which first estimates the Q-function of the behavior policy using the offline dataset, i.e, Q* a). and then computes $ as the final policy returned by the algorithm. To understand the performance difference between multiple values k, we first utilize essentially Lemma from Agarwal et al. [2], which we present below for completeness:
26

---

Published as a conference paper at ICLR 2022
Lemma B.11 (Lower bound on policy improvement in the empirical MDP, M). The iterates Ht generated by k-steps of policy improvement. for any initial state distributions po(s) satisfy the following lower-bound on improvement:
J(ah+1)- -(th) = -Esompo ( (so)
Esgrup
2
1 n/
Beurpo log (so). (12)
Proof. We utilize the performance difference lemma in the empirical MDP to show this:
J(aht)) - -((*t) = HB d
Σ Th+ (a a)
g (a)s) (a|s))
E swd
Σ (a|s)
17
(+|ss] + -
E Bawdik+1 [DKL (+
Badd [log [s)]
2 E S (log (s))
Finally, note that the final term log (s) is always positive because of Jensen's 's inequality, and the fact that the expected advantage under given policy is 0 for any MDP.
IT
Utilizing Lemma B. 11, we can then lower bound the total improvement of the learned policy in the actual MDP as:
- 2 J(Th)
[(**)
+
J((t) -(7')
-(T') - J(7))
(b)
(c)
ChHi
E s log [s)] -V
N
where the HCHH guarantee for terms (a) and (c) arises under the conditions studied in Sec- tion 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., Ex [log (s) co 0, then the performance improvement obtained by k-steps of policy improvement is bounded below by kco/n 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 ((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-sty environments, where O(H) many possible high- advantage updates are possible on the empirical MDP, especially by "stitching" parts of suboptimal trajectories obtain a much better trajectory. Therefore, we expect that offline RI. problems where stitching is possible, offline RI. algorithms will attain an improved performance compared to one or few-steps of policy improvement.
C GUARANTEES FOR POLICY-CONSTRAINT OFFLINE RL
In this section, we analyze a policy-constraint offline algorithm [34] 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. [36], which truncates Bellman backups and policy improvement steps from low-density, out-of-support state-action pairs. The algorithm is described in detail Algorithm 2, but we provide a summary below. Let (s, a) denote the empirical state-action distribution and choose constant b. Then, let
27

---

Published as a conference paper at ICLR 2022
((s.a) a) (s a) 2 b) be the indicator of high-density state-action tuples. The algorithm analyze performs the following update until convergence:
(s, a() + 7
Σ
P(s' (s. ())m(mass)(((sss))) a') Q5' a'), for all (s,a),
(s' (s',a))
Bars' (((s.a) (s. a) a)]]
arg max E
In order to derive performance guarantees for this generic policy-constraint algorithm, we define the notion of a <oooered policy following Liu et al. [36] in Definition C.I. The total occupancy of all out-of-support state-action pairs (i.e., (s, a) such that ((s. = 0) under (-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 ((saa) (1 - ((s, a) a) S (1 (1-11) (b).
Equipped with this definition C.1, Lemma C.I shows that the total value estimation error of any given <-covered policy, т. (J(T) - [x)] is upper bounded in expectation over the dataset
Lemma C.1 (Value estimation error of Ç-covered policy). For any given Ç-covered policy n, under Condition 3.2, the estimation error [T) JT((T] is bounded as:
ED J(()) [4(m) &
CH
C* +U(b)
+
(13)
N
N
Proof. To prove this lemma, consider the following decomposition of the policy performance estimate:
[(x) [c(
y'd (s, a)
Σ ( - p(s (s') (s',a')
t= (s,a)
00
2 (s, a)
Σ
P(s'(s,))) ((s', -P(ssss x(a'ss)) ((s
(s.a)
(s',a')
Ag :bound using concentrability and variance recursion
Σ d (s, a)
Σ a() (1 ((s,aa)) (a'ls/) (s', a') (s',a")
Agtbias leaving support; upper bounded Ç-cover
To bound the inner summation over (s', a') in term (a), we can apply Lemma B.5 since ((s'|s, [[s'|s, a) and ((s', a') are not independent, to obtain a horizon-free bound. Finally, 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, get, with high probability 2 5:
v(P(s, a), VT
V(s, a) s.t. n(ss a) 21, ()) - -Pssaa) PZ S
n(ss
n(s, a)
where we utilized the fact that V < v= < due Condition 3.2. For bounding 22, we note that this term is bounded by the definition of (-covered policy:
A
1' (b)
(14)
t=
Thus, the overall policy evaluation error is given by:
36
V v(P(s, a), Ve) n(s, a)
J(T) -T((m)
Σ 1=
/ (s,
U(b).
(15)
n(s a)
28

---

Published as a conference paper at ICLR 2022
Agent can only move within this region
High reward, r(s)=1
A
C
multiple actions succeed
Single action
succeeds ("critticll")
Figure (Figure restated) Illustration showing the intuition behind critical points a navigation task. The agent supposed to navigate to high-reward region marked as the yellow polygon, without crashing into the walls, different states, A, B and C that we consider, reach the goal states A and C, but only few actions that allow it do so at state B. States around A and C are not critical, and so this task has only a small volume of critical states (i.e., those in the thin tunnel).
agent has a high volume of actions that allow
Equation 15 mimics the & term in equation 9 that is bounded in Section B.2.5, with an additional offset (b). Hence, we can reuse the same machinery to show the bound expectation over the randomness in the dataset, which completes the proof.
Using Lemma C.I, when compared to the best policy that is Ç-covered:
that the policy constraint algorithm attains favorable guarantec
Theorem C.1 (Performance of policy-constraint offline RL). Under Condition 3.2. the policy f* incurs bounded suboptimality against the best {-covered policy, with high probability 6:
C HL N
CH N
Ep [J(mZ) - -(
2U(())
To prove this theorem, use the result of Lemma C.I for the fixed policy, that is agnostic of the dataset, and then again use the recursion as before to bound the value the data-dependent policy. The latter uses Lemma B.5 and ends up attaining bound previously found in Appendix B.2.5, which completes the proof of this Theorem. When the term (b) is small, such that ((b) < O(H0.6-5) for > 0, then we find that the guarantee in Theorem C.1 matches that in Theorem 4.2, modulo term that grows slower in the horizon than the other terms in the bound. If (b) is indeed small, then all properties that applied conservative offline RL shall also follow for policy-constrain algorithms.
Note on the bound. We conjecture that it is possible to get rid of the (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, = 1, then we can derive stronger guarantee.
D INTUITIVE ILLUSTRATIONS OF THE CONDITIONS ON THE ENVIRONMENT AND PRACTICAL GUIDELINES FOR VERIFYING THEM
In this section, 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 Conditions 4.1 and 4.2, 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.
D.1 CONDITION 4.1
To provide intuition behind when this condition is satisfied, we first provide an example of a sample navigation domain in Figure 4, to build examples of critical states. As shown in the figure, the task is to navigate to the high-reward yellow-colore B and C are critical or not. The region where the agent 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 is likely to
region. We wish to understand if states marked as A,
move is very wide in the neighborhood
29

---

Published as a conference paper at ICLR 2022
sill finish the task, while if it executes the actions shown via red arrows it is likely not 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 allows so, as shown in the figure. Thus, state B a "critical state" as per Definition ??. But since most of the states in the wide regions of the tunnel are non-critical, this navigation domain satisfies Condition 4.1.
D.2 CONDITION 4.2
Now we discuss the intuition behind why offline RL run form of noisy-expert data outperform BC on expert data. As shown in Figure 5, the task is to navigate from the Start to the Goal. In this case, when BC trained using only expert trajectories, and the environment consists of 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 5. 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 RI, method should be able to figure out how to avoid such states and solve the task successfully.
Behavior cloning on expert:
Low reward
BC expert sata
Goal
Start
Offline RL with noisy data:
Offine
Goal
Gool
Start
Start
Datanet
Low reward
Offine RL can uSe notsy data Icorn what not
Pollcy
Figure 5: (Figure restated) Illustration showing the intuition behind suboptimal data in a simple navigation task. BC trained expert data (data composition is shown the left) may diverge away from the expert and find a poor policy that does not solve the task. On the other hand, if instead of expert data, offline RL is provided with noisy expert data that sometimes ventures away from the expert distribution, RL can this data to learn to stay on the course to the goal.
Condition 4.2 requires that state-action tuples with (s, a) b/1l under the expert policy have high-enough density yuss, a) 2 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) 2 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 explored more in the data. The latter can be satisfied when the agent is provided with "negative data", i.c., failed trajectories, starting from states in an optimal trajectory as shown in Figure 5. 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 5. On the other hand, BC cannot this negative data.
This condition is satisfied in the following practical problems:
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. [21] and Kalashnikov et al. [23] run partly trained RL policies for noisy collection for running offline RL). Another simple way to obtain such data is to first standard BC on the offline demonstrations, then store the rollouts obtained from the BC policy when evaluating it, and then run offline RL on the entire dataset (of expert demonstrations suboptimal/noisy BC evaluation rollouts).
Robotics:
30

---

Published as a conference paper at ICLR 2022
Autonomous driving and robotics: In some domains such autonomous driving and robotics, rolling out short counterfactual trajectories from states visited the offline data, and labeling it with failures is a common strategy [5, 51]. 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. [9] found that was practical to add additional stochasticity while rolling out 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 lo- comotion (e.g., in character animation in computer graphics [46], open-world robot navigation [57]) 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
D.3 PRACTICAL GUIDELINE'S FOR VERIFYING THESE CONDITIONS
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 well- explored the dataset is. However, we believe that practitioner who has sufficient fomain-specinf 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 large fraction of states along trajectory where either multiple good actions exist, or it is easy to recover from suboptimal actions?
Is the offline dataset collected from a noisy- policy, and if not, can the dataset be augmented using perturbed or simulated trajectories?
If either of those questions can answered positively, our theoretical and empirical results show that it favorable to offline RL algorithms, even over collecting expert data and using BC. At least, offline RI algorithms should be tried on the problem under consideration. Hence, the goal of our contributions not to provide a rigid 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, supervised learning, tuning the architecture of deep neural network depends heavily on domain knowledge, and choosing kernel in kernel machine again depends on the domain.
E EXPERIMENTAL DETAILS
In this section provide detailed deseription of the various tasks used in this paper, and de- scribe the data collection procedures for various tasks considered. We discuss the details of our tasks and empirical validation at the following website: https://sitee: google. com/ com/view/ view
s shoul di runrl orrc hoome.
E. TABULAR GRIDWORLD DOMAINS
The gridworld domains consider are described by 10 x 10 grids, with start and goal state, and walls and lava placed in between. We consider sparse reward where the agent earns reward of 1 upon reaching the goal state; however, the agent reaches lava state, then its reward 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 10% chance that the agent travels in 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 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 [56]. The renderings of each gridworld are in Figure 6.
31

---

Published as a conference paper at ICLR 2022
Figure 6: Renderings of three gridworld domains we evaluate on, where states are colored as: Start:blue, Goal:green, Lavared, Wall.grey, and Open:white. The domains have varying number of critical points. Left: Single Critical, Middle: Multiple Critical. Right: Cliffwalk.
E.2 MULTI-STAGE ROBOTIC MANIPULATION DOMAINS
Overview of domains. These tasks are taken from Singh et al. [60]. The robotic manipulation simulated domains comprise of 6-DoF WidowX robot that interacts with objects in the environment. There are three tasks of interest, all of which involve drawer and tray. The objective of each task to remove obstructions of the drawer, open the drawer, pick an object and place in tray. The obstructions of the drawer were varied giving rise to three different domains open-grasp (no obstruction of the drawer), caae-oopengrrayy (an open top drawer obstructs the bottom drawer), pick-plan place-open-graaays (an object obstructs the bottom drawer).
Open Grasp
Close Open Grasp
Pick Place Open Grasp
Figure 7: Filmstrip of the three tasks that stufy for robotic manipulation - open-ggass,, close-open-grasp and pick-place-open-graae
Reward function. For all the three tasks considered, a reward of + provided when the robot is successfully able to open the drawer of interest (bottom drawer in close-open open-grasp and pick-place- open-graspp the only drawer open-grasp and is able grasp the object inside If the robot fails at doing 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 this task. For our experiments with suboptimal data, which is used to train offline RL, ran noisy version of this near 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.
32

---

Published as a conference paper at ICLR 2022
E.3 ANTMAZE DOMAINS
This task is based on the antmaze-medium and antmaze-large environments from Fu et al. [14]. 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 al. [14]. 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-workd navigation scenarios.
Overview of the domain.
Scripted policies and datasets. We utilize the scripted policies provided by Fu et al. [14] to generate two kinds of expert datasets: first, we generate trajectories that actually traverse the path from 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 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) = if - - 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 [14), but the dataset composition in our case comes from an expert policy.
E.4 ADROIT DOMAINS
Overview of the domain. The Adroit domains [50, 14] involve controlling a 24-DoF simulated Shadow Hand robot tasked with hammering nail (hammer), opening door (door), twirling pen (pen) or picking up and moving a ball (relocate). This domain presents itself with nar- row data distributions, and we utilize the demonstrations provided by Rajeswaran et [50] as expert dataset for this task. The environments were instantiated via D4RL, and utilized door-human www.hh-momaaoreeeeeeeeee--eooe-e zon, for evaluation.
the environments marked as: hammer www.unn-nngghhhooo zon and re
pen-
Reward functions. We directly utilize the data from D4RL [14] for this task. However, we modify the reward function to be used for RL. While the D4RL adroit domains provide 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, first extract the D4RL dataset for these tasks, and then modify the reward function as follows:
r(s, a) +1 if PDAIL (s, a) 2 70.0
(hammer-human)
(16)
r(s, a) = +1 if rDANL (s, a) 2 9.0
(door-human)
(17)
r(s, a) +1 if (TAAR((S.8 2 47.0
(pen-human)
(18)
r(s, a) = =+1 if IDARLL (s, a) 2 18.0
(relocate-human
(19)
The constant thresholds for various tasks are chosen in way that only any transition that actually activates the flag aoallachiiee eved=True flag in the D4RL Adroit environments attains a reward +1, while other transitions attain reward O. We evaluate the performance of various algorithms on this new sparse reward that we consider for our setting.
E.5 ATARI DOMAINS
We utilized 7 Atari games which are commonly studied in prior work [27, 28]: ASTERIX, BREAKOUT, SEAQUEST, PONG, Spacelnvaders, QERT 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, qualities from the DQN- Rep-Replay dataset provided by Agarwal et al. [3]. The DQN-Replay dataset is stored 50 buffers consisting of sequentially stored data observed during training of online DQN agent over the course of training.
extracted datasets of different
Expert data. To obtain expert data for training BC and RL algorithms, utilized all the data from buffer with id 49 (i.c., the last buffer stored). Since each buffer in DQN-Replae consists of IM transition samples, all algorithms training expert data learn from 1 M samples.
33

---

Published as a conference paper at ICLR 2022
Domain / Behavior Policy
Task/Data Quality
BC
Naïve CQL
Tuned CQL
7 Atari games (RL policy)
Pong, Expert
109.78 + 2.93
102.03 + 4.43
105.84 + 2.22
Breakout, Expert
75.59 = 21.59
71.22 + 27.55
94.77 = 27.02
Asterix, Expert
41.10+99.
44.81 + 12.0
80.19 + 20.7
SpaceInvaders, Expert
40.88 4.17
45.27 7.32
54.15 + 2.96
hetert Expert
121.48 9.06
105.83 23.17
98.52 18.62
Enduro, Expert
78.67 3.98
141.53 18.79
127.02 10.53
Seaquest, Expert
63.15 =
64.03 + 27.67
85.28 + 21.28
Table 3: Per-game results for the Atari domains with expert data. Note that while naïve CQL does
not perform much better than BC (it performs similarly as BC), tuned CQL with the addition of the DR3 regularizer performs much better.
Task
BC-PI
CQL
Pong
100.03 + 5.01
94.48 +: 8.39
Breakout
25.99 + 1.98
86.92 + 13.74
Asterix
29.77 + 5.33
157.54 + 37.94
SpaceInvaders
31.45 + 1.96
63.7 16.18
Q*
106.06 8.63
88.72 1 20.41
Enduro
68.56 1 0.23
148.97 + 12.3
Seaquest
22.51 + 2.23
124.95 + 43.86
Table 4: Comparing the performance of BC-PI and offline RL noisy-expert data. Observe that in general, offline RL significantly outperforms BC-PI.
Noisy-expert data. For obtaining noisy-expert data, analogous to the gridworld domains we study, mix data from the optimal policy (buffer 49) with an equal amount of random exploration data drawn from the imitial replay buffers in DQN replay (buffers 0-5). i.c. we utilize 0.5M samples form buffer 49 in addition to 0.5M samples sampled uniformly at random from the first 5 replay buffers.
F TUNING AND HYPERPARAMETERS
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 [30]. We used default hyperparameters for the CQL algorithm (Q-function learning rate = 3e-4, policy learning rate le-4), based on prior works that utilize these domains. Note that prior works do not use the kind of data distributions we use, and 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, used a = 0.1 for all Atari games (following Kumar et al. [28]), and a = 1.0 for the robotic manipulation domains following [60]. For the Antmaze and Adroit domains, we CQL training with multiple values of a E {0.01, 0.1, 0.5, 1.0, 5.0, 10.0, 20.0). and then picked the smallest a that did not lead to eventually divergent Q-values (either positively negatively) with more (IM) gradient steps. Next, we discuss how we regularized the O-function training and performed policy selection on the various domains.
Detecting overfitting and underfitting: Following Kumar al. [30], as first step, detect whether the run is overfitting or underfitting, by checking the trend in Q-values. In our experiments, we found that Q-values learned Adroit domains exhibited decreasing trend throughout training, from which we concluded 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 decreas- ing regularizer to correct for overfitting, by utilizing dropout every layer of the Q-function. We ran with three values of dropout parobability, p E {0.1, 0.2, 0.4), and found that 0.4 was the most effective in alleviating the monotonically decreasing trend in Q-values, used that for our results.
34

---

Published as a conference paper at ICLR 2022
Then, 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 stable, convergent trend and did not decrease with more training. Following Kumar et al. [30], we concluded that this resembled underfitting and utilized a capacity-increasing regularizer (DR3 regularizer (29]) for addressing this issue. We used identical hyperparameter for the multiplier (8) on this regularizer term for both Atari and Antmaze, 3 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 forw-forward policy architectures sizes (256, 256,22222 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 lanh-Gaussian policy, typically used in continuous control to work well, since it overfitted very quickly giving rise to worse-than-Hee thae--t performance and therefore, we switched to utilizing a Gaussian policy network with hidden layer sizes (256, 256, 256, 256). and learned, state-dependent standard deviation. To prevent overfitting in BC, we applied strong dropout regularization of = 0.2 after each layer for Adroit domains. On Atari and the manipulation domains, utilizedd Resnet architecture borrowed from IMPALA [10], but without any layer norm.
Tuning BC-PI. Our BC-PI method is implemented by training a Q-function via SARSA, i... (s, r(s, a) + 7Q('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 Qo:
(()) = D
Σ 5,a.5' a'
(Qo a) - (r(s, a) + QQ0(s'
and then performing advantage-weit weighted policy extraction: s(als) x Ta(a))) exp(A(s, a)/n) on the offline dataset 2. The loss function for this policy extraction step. following Peng et al. [47] is given by:
(Qo(s, () (Vo()
T
max
Σ 8.8
log n (als) exp
where the value function given by V(s) = E. ne (a(a) a') and н is learned model of the behavior policy, as done in the implementation of Brandfonbrener et al. [6]. This model of the behavior policy is trained according the tuning protocol for BC, and is hence well-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) == ((s, a) V(s) between [-10, 2] and 1-10,4], 4). The Q-function architecture is identical tuned CQL, and the policy and the model of the behavior policy both utilize the architecture used by our BC baseline.
What we tuned:
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 the highest average performance across all games is r 0.005, and the advantage clipping between [-10, 2). We find a huge variation in the performance of given 17, we used single hyperparameter 7) across all games, in accordance with the Atari evaluation protocols [40], and as we did for all other baselines. For example, while on some games such as Qbert, BC-PI improves quite 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 17. i.e., utilizing (s)). however, this is not covered in definition of BC-PI from Section 4.4, and so chose to utilize single across all states. Additionally, we are unaware of any work that utilizes per-state (s)) values for exponentiated-advaatagg weighted policy extraction.
35

---

Published as a conference paper at ICLR 2022
G REGARDING OFFLINE RL LOWER BOUNDS
Here we address the connection between recently published lower-bounds for offline RL by Zanette [71] and Wang al. [64] and our work.
Zanette [71] worst-case analysis does address function approximation even under realizability and closure. However, this analysis concerns policy evaluation and applies 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 [71]'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 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. [65] only applies to non-pessimistic algorithms that do not tackle distributional shift. In fact, Section Theorem 5.1 in Wang et al. [64] 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.
H DIAGNOSTIC EXPERIMENTS ON A GRIDWORLD
We first evaluate tabular versions of the BC and offline RL methods analyzed in Section 4.1 on sparse-reward
10 gridworlds environments [13]. Complete details about the setup can be found in Appendix E. On 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 consider naive BC (BC), conservative RL (RL-C), policy-constral policy improvement (BC-PI, BC-kPI). In the left plot of Figure 8, 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 different initial state distribution (C* but (-(s) = n (-ls)). As expected from our discussion in Section 4.2, BC performs best under C 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 full offline RL. In Figure 8, we vary C* by interpolating the dataset with one generated by random policy, where a 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.
RL (RL-PC), and generalized BC with one-step and k-step
0.70
0..0
8.96
0.66
6.84
0.51
0.02
9:52
5:50
6.3
02
00
10 11
10 II
Figure 8: Offline RL vs BC on gridworld domains. Left: We compare offline RL and BC on three different gridworlds with varying number of critical points for expert and near-expert data. Right: Taking the "Multiple Critical" domain, we examine the effect of increasing the noisiness of the dataset by interpolating it with one generated by random policy, and show that RL improves drastically with increased noise BC.
36


Reviews:
[{"review_id": "wYNCq1ncYr", "reviewer": "Reviewer_b23W", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n1. The paper studies an interesting problem: when an offline RL algorithm has advantages over a simple BC algorithm. I think the problem is in the interests of many RL practitioners. \n2. The paper provides a good overview on related works.  \n\nWeaknesses (and questions)\n1.\tThe paper proposes several sufficient conditions that VI-LCB could have a better worst-case sub-optimality gap. However, it does not provide practitioners a clear guidance on when they should run BC and when they should run VI-LCB, which I think is one of the main purpose of the paper. How should we check if the sufficient conditions are satisfied in real world problems? Some of the parameters are even unknown (e.g., b in Corollary 4.2). \n2.\tI find it difficult to compare these upper bounds. Is it possible that some algorithms get larger bounds simply because the analysis is not tight?  Can we say that algorithm A is better than algorithm B because an upper bound (of the sup-optimality gap) for A is lower than an upper bound for B? \n3.\tSome conditions are not well-justified. The paper studies some sufficient conditions that VI-LCB outperforms BC, however, some conditions seems a little arbitrary to me (e.g., condition 3.2, condition 4.1 and condition 4.2). I guess the paper has some specific applications in mind and makes these conditions based on these applications. However, this makes the results less clear and less general. For example, how do the results extend without condition 3.2? do we expect to just see an extra H term in all bounds without the condition? If the paper considers some specific applications, the paper should clearly mention it instead of saying the conclusion holds in general.   \n4.\tThe paper studies a particular type of offline RL algorithm based on VI with LCB style penalty. However, the title and the paper seems to suggest that this particular algorithm can represent the class of offline RL algorithms? I don’t see how study one algorithm can generalize to a conclusion for offline RL algorithms? \n5.\tI am not sure what is the novelty and significance of the theoretical results. It seems the theoretical results are mostly borrowed from existing literature with some modifications. I want to make sure I am not missing something important there. Can you explain more about the novelty or significance for the theoretical results? \n\nMinor questions and comments:\n1. In the empirical section, does CQL lie in the VI-LCB framework? If not, why is it used in the empirical section while all theoretical results are for VI-LCB. \n2. VI-LCB with Bernstein style penalty is also used in [1], which is not cited in this paper. \n\n[1] Xie et al. (2021) “Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning”\n", "summary_of_the_paper": "The paper studies the sufficient conditions that VI-LCB would have a better worst-case sub-optimality gap than the gap of a BC algorithm, under expert data and noisy data. Moreover, the paper provide an empirical study to validate the theoretical results. ", "summary_of_the_review": "I am leaning towards a recommendation to reject the paper since I think the paper does not clearly answer the core question: whether should I run BC or offline RL for several reasons mentioned in the Main Review section. However, I am open to change my scores after author response. \n\n----\nAfter the author response, most of my concerns were addressed. I think the paper provides good empirical and theoretical understandings of the comparison between BC and pessimistic VI, so I raised my score to a 6. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "phuOd-y-u9X", "reviewer": "Reviewer_4pq1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Pros\n- The quality and clarity of the writing are remarkable. The assumptions are clearly stated and transparent to the reader. The discussion around the theoretical results is well conducted and the insights are informative to the reader.\n- The empirical evaluation on a tabular gridworld domain is appreciated as it removes the influence of function approximators on the results. The 3 types of girdworld instances provide the right settings to confront the theoretical results of section 4.\n    - On a side note, I appreciate the care of using the suggestions introduced in [1] to report the empirical results of RL experiments.\n    - I also appreciate the fact that the authors didn't shy away from highlighting potential discrepancies in their results due to the various tricks introduced in the literature to tune offline RL algorithms.\n\n### Questions\n- I would ask the authors to clarify the need for condition 3.2 as it seems that some of their results could be derived without it, e.g. theorem 4.1. How would the results be affected if we were to remove this condition?\n\n### Minor Comments\n- The space taken by the discussion around the theoretical results doesn't leave much space for the analysis of the experiments. As a reader, it is hard to digest and understand whether the results fully align with the theory.\n- Add an explanation of the terms for theorem 4.2, like it is done for theorem 4.1.\n1. Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Marc G Bellemare. Deep reinforcement learning at the edge of the statistical precipice. *Advances in Neural Information Processing Systems*, 2021b.", "summary_of_the_paper": "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:\n\n- 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.\n- 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.\n\nThese 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.\n\n1. 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*,", "summary_of_the_review": "Overall, I consider this paper to be a great contribution to the research community. The question investigated is important for the research in offline RL and practitioners. The theoretical analysis is well conducted and meaningful insights can be drawn from it. The experimental results are adequately reported and support the findings.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZYtLSwv0wja", "reviewer": "Reviewer_QvCh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\n1. The writing is clear throughout. The paper clearly explains its goals and is well organized. \n2. The proofs seem to be generally correct. \n3. The empirical analysis is relatively thorough and well documented. It seems to generally follow best practices with respect to tuning hyperparameters, reporting confidence intervals, and even reporting IQM on the Atari experiments. \n\n### Weaknesses\n\n1. I'm somewhat skeptical of the usefulness of the question the paper is trying to answer. First, from a practitioners perspective it is not clear why I have to choose between BC and offline RL. I can always run both and use some sort of validation procedure to decide which policy to deploy. Second, it seems to also be a false choice since offline RL algorithms often contain a hyperparameter that reduced the algorithm to BC if set to an extreme value, and in this sense BC is strictly contained in the offline RL algorithm. Third, the paper does not seem to consider the standard cases where BC is desirable and offline RL may not even apply. For example, BC is often used in problems where there is no obvious reward function (e.g. in many robotics problems), but we can get demonstrations of the desired behavior (e.g. from tele-operating). Finally, I am worried that the paper is arguing against a bit of a strawman. I am not aware of anyone making the argument that BC should be preferred to offline RL when a reward function and sufficient data are available. \n2. The theory only considers tabular representations and as a result avoids the central issues of offline RL. By limiting to the tabular case, the analysis does not have to deal with the notorious deadly triad. Wang et al., 2021 and Zanette, 2020 (cited in the paper) prove exponential lower bounds on sample complexity in the case of linear function approximation. Importantly the results depend on errors due to the function approximation. Empirically, Brandfonbrener et al., 2021 (also cited in the paper) bears out some of these concerns caused by amplifying approximation errors in offline RL. By assuming away this key part of the problem, it is not surprising to see positive results for offline RL. \n3. I am somewhat worried about novelty. On the theory side, the positive results largely exist in prior work and are even more general since guarantees exist beyond the tabular setting already. The comparison of the results across algorithms may be novel, but the results themselves do not seem to be a major contribution. On the empirical side, the sorts of results presented already exist even in the original paper that proposed the D4RL benchmark, showing that BC outperforms CQL sometimes and then in the paper proposing tuning methods for CQL demonstrating the improved performance from tuning. The emphasis on this comparison may be novel, but the results themselves do not seem to be.\n4. I couldn't find any details at all about the BC-PI implementation used in the experiments. Could the authors comment on how this algorithm was implemented? This is especially interesting to me because it seems that a naive algorithm that attempted to filter out the bottom half of state-actions from the dataset would work very well on a dataset that is just half random and half expert data, so I'm wondering if there is something strange going on with the implementation. ", "summary_of_the_paper": "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.", "summary_of_the_review": "While the paper is generally clear and technically sound, I found several serious issue with it and recommend rejection at this time. Specifically, I am skeptical of the usefulness of the central question, worried that the theory is assuming away the interesting part of the problem, worried about novelty, and had a few more minor concerns about the experimental setup. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2_F-ZCR9NVA", "reviewer": "Reviewer_9b7d", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\nOffline 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).\n\nThe 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.\n\n**Weaknesses**\n\nIt's unclear how much bearing the theory has on the actual empirical experiments as the authors themselves emphasize the importance of tuning offline RL. Tuning techniques seem domain dependent and exactly what features of the domain lead to particular tuning choices remains unexplored. Nevertheless, since the tuning methods are offline, it's not a major issue. Overall, some way to separate the [state] representation learning problem from the best action problem is likely important to really figure out the problem which the theory in the paper largely ignores.\n\nThe bigger issue is whether the \"noisy-expert\" data is a good proxy for real-world offline RL applications. While the paper cites a few examples of suboptimal data collection in Sec. 4.3 for most real world applications, the data is actually seldom noisy in the same way. Often a more realisitic assumption is that there are different suboptimal demonstrators (consider different human operators with different skill levels) who perform the task in different ways but their policies can't be simply described as noisy versions of each other (or the highest skill level). Moreover, there are often many safety constraints that simply would not allow running certain kind of behavior policies. Authors might find [1] an interesting read. Adroit results in Table 1 kind of point towards something similar (BC and CQL are not that different in performance).\n\n[1] Vladislav Kurenkov, Sergey Kolesnikov. \"Showing Your Offline Reinforcement Learning Work: Online Evaluation Budget Matters\". AAAI 2022.\n", "summary_of_the_paper": "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).\n\nThe 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.\n", "summary_of_the_review": "While some claims about offline RL doing better than BC as \"surprising\" are not necessarily something I agree with, overall it's an interesting paper and allows the community to make progress towards better understanding of the tradeoffs between different policy learning mechanisms and would recommend acceptance. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers helping to decide whether behavior cloning or offline RL is likely to be more effective given a particular offline dataset. The reviewers initially appreciated the importance of insights into this question around how to best leverage an existing dataset. They also had some initial concerns, due in part because the theory is restricted to tabular settings, whereas many challenges typically arise when function approximators are used, the realisticness of the assumptions over the data collection process, and a number of places where further details or clarifications would better situate and strengthen the work. The authors gave very extensive responses to the feedback which made reviewers feel much more confident about the revised paper and resulted in significantly higher scores. Though there remains many interesting areas for future work, this paper makes an interesting contribution that may be of interest to many using batch decision making data.
Decision: Accept (Poster)