Mitigating Covariate Shift in Imitation Learning via Offline Data With Partial Coverage
Authors: Jonathan Daniel Chang
Masatoshi Uehara
Dhruv Sreenivas
Rahul Kidambi
Wen Sun
Venue: NeurIPS 2021 Poster (2021)
Keywords: Offline Imitation Learning
Imitation Learning

Abstract: This paper studies offline Imitation Learning (IL) where an agent learns to imitate an expert demonstrator without additional online environment interactions. Instead, the learner is presented with a static offline dataset of state-action-next state triples from a potentially less proficient behavior policy. We introduce Model-based IL from Offline data (MILO): an algorithmic framework that utilizes the static dataset to solve the offline IL problem efficiently both in theory and in practice. In theory, even if the behavior policy is highly sub-optimal compared to the expert, we show that as long as the data from the behavior policy provides sufficient coverage on the expert state-action traces (and with no necessity for a global coverage over the entire state-action space), MILO can provably combat the covariate shift issue in IL. Complementing our theory results, we also demonstrate that a practical implementation of our approach mitigates covariate shift on benchmark MuJoCo continuous control tasks. We demonstrate that with behavior policies whose performances are less than half of that of the expert, MILO still successfully imitates with an extremely low number of expert state-action pairs while traditional offline IL methods such as behavior cloning (BC) fail completely. Source code is provided at https://github.com/jdchang1/milo.

Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
Jonathan D. Chang"
Masatoshi Uehara"
Department of Computer Science
Department of Computer Science Cornell University mu223@cornell.ede
Cornell University Jdc396@cornell.edd
Dhruv Sreenivas
Rahul Kidambi!
Wen Sun
Department of Computer Science
Amazon Search & AI
Department of Computer Science
Cornell University
rk773@cornell.cm edu
Cornell University ws455@cornel1. edu
ds8440cornell.ed
Abstract
This paper studies offline Imitation Learning (IL) where an agent learns to imitate expert demonstrator without additional online environment interactions. In- stead, the learner is presented with a static offline dataset of state-action-next state transition triples from a potentially less proficient behavior policy. We introduce Model-basee IL from Offline data (MILO): an algorithmic framework that utilizes the static dataset to solve the offline IL problem efficiently both in theory and in practice. In theory, even the behavior policy is highly sub-optimal compared the expert, show that long the data from the behavior policy provides sufficient coverage on the expert state-action traces (and with no necessity for a global coverage over the entire state-action space), MILO can provably combat the covariate shift issue in IL. Complementing our theory results, we also demon- strate that practical implementation of our approach mitigates covariate shift on benchmark MuJoCo continuous control tasks. We demonstrate that with behavior policies whose performances are less than half of that of the expert, MILO still successfully imitates with an extremely low number of expert state-action pairs while traditional offline IL methods such as behavior cloning (BC) fail completely. Source code is provided at https: / tiithuu...... com/ jdchang1/milo.
Introduction
Covariate shift is issue in Imitation Learning (IL). Traditional IL methods like behavior cloning (BC) [49], while simple, suffer from covariate shift, learning a policy that can make arbitrary mistakes parts of the state space covered by the expert dataset. This leads compounding errors in the agent's performance [57], hurting the generalization capabilities in practice.
Prior works have presented several means to combat this phenomenon in IL. One line of thought utilizes an interactive expert, i.e. an expert that can be queried at an arbitrary state encountered during the training procedure. Interactive IL algorithms such DAgger [59], LOLS [15]. DART [40], and AggreVaTees VaTe(D) [58; 66] utilize reduction to no-regret online learning and demonstrate that under certain conditions, they successfully learn policy that imitates the expert. These interactive IL algorithms, however, cannot provably avoid covariate shift the expert is not recoverable. That is,
Equaal contribution
Work done outside Amazon
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

1-200
[= 400
[- 800
t= 1000
BC (Expert Data)
Normalized Scores
1.0
(Expert Offline Data)
0.6
0.4
0.2
0.0
MILO (Ours)
ValusDICI
BC (Export Dasa)
BC (Expert Offiine Dan))
MILO
Figure 1: (Left) Frames at timesteps 200, 400, 600, 800, and 1000 for Humanoid-v2 from policies trained with BC on 100 state-action pairs from the expert (blue), BC on IM offline samples plus 100 expert samples (yellow), and our algorithm MILO (red). The expert has a performance of 3248 and the behavior policy used to collect the offline dataset has performance of 1505 = 473 (=z 46% of the expert's) s). (Right) Expert performance normalized scores averaged across 5 seeds.
A* a) ((H) where ne is the expert, A is the usual (dis)advantage function, and H is the planning horizon (52; 4, Chapter 15]. A second line of work that avoids covariate shift utilizes either known transition dynamics model [2: 86] or uses real world interactions [27; 10; 65; 38; 56; 33). Prior works have shown that with known transition dynamics or real world interactions, agents can provably avoid covariate shift in both tabular and general MDPs [4; 52] even without a recoverable expert. While these results offer strong theoretical guarantees and empirical performance, online interactions often costly and prohibitive for real world applications where active trial-and-error exploration in the environment could be unsafe or impossible. A third perspective towards addressing this issue is assume that the expert visits the entire state space [62]. where the expert effectively informs the learner what actions to take in every state. Unfortunately. such full coverage expert distribution might be rare and holds only for special MDPs and expert policies (for e.g. an expert that induces ergodicity in the MDP).
In this work, consider new perspective towards handling the covariate shift issue in II. In particular, we investigate a pure offline learning setting where the learner has access to neither the expert nor the environment for additional interactions. The learner, instead, has access pre-collected dataset of state-action pairs sampled from the expert and large batch offline dataset of state-action-ne next state transition triples sampled from behavior policy that could be highly sub-optimal (see Figure where BC on the offline data results in a low-quality policy). Unlike prior works that require online interactions, our proposed method, MILO performs high fidelity imitation in offline, data-driven manner. Moreover, different from interactive II., we do not require the expert be present during learning, significantly relieving the expert's s burden. Finally, in contrast to the prior work [62] that assumes the expert distribution covers the entire state-action space (i.e., max, max,,a a d= (s, a)/d" (s, a) < oo where d' denotes the state-action distribution of policy T), we require the offline dataset to provide partial coverage, i.e., only needs to cover the expert's 'ss state-actions (i.e., maxs,a d= (s, a).a)/pls. a) < where is the offline distribution of some behavior policy).*
small
In summary, we list our main contributions below:
1. We propose Model based Imitation Learning from Offline data, MILO: model-based framework that leverages offline batch data with only partial coverage (see Section 4.1 for definition) to overcome covariate shift IL.
in this work, cost instead of reward, thus call A the disadvantage function. 'In our analysis, we refine the density ratio d' (s, p(s a) via the concept of relative conditional number which allows extend it to large MDPs where the ratio infinite but the relative condition number is finite.

---

2. Our analysis is modular and covers common models such as discrete MDPs and linear models. Notably, our new result on non- con-paraettric models (e.g. Gaussian Processes) with relative condition number is new even considering all existing results in offline RI. (see Remark 4,7.11).
3. The practical instantiation of our general framework leverages neural network model ensembles, and demonstrates its efficacy on benchmark MuJoCo continuous control problems. Specifi- cally, even under low-quality behavior policies, our approach can successfully imitate using an extremely small number of expert samples while algorithms like BC completely fail (Figure I).
1.1 Related work
Imitation Learning As summarized above, avoiding covariate shift in IL is an important topic. Another relevant line of research IL algorithms that use offline or off-policy learning. ValueDICE [38] presents principled way to leverage ooolpy data for IL. In theory, the techniques from ValueDICE (and more broadly, DICE [46; 84J) require the data provided to the agent have global coverage. Moreover in practice, VaIueDICE uses online interaction and maintains an increasing replay buffer which may eventually provide global coverage. Instead, we aim to study offline IL without any online interactions and are interested in the setting where offline data does not have global coverage. Another line of work [29; 14] studies IL. in an offline setting by only using the expert dataset. In contrast to these works, our goal is to study the use of an additional offline dataset collected from a behavior policy to mitigate covariate shift, as information theoretically any algorithm that relies solely on expert data will still suffer from covariate shift in the worst case [52].
Similar in setting, Cascaded Supervised IRL (CSI) [35] performs imitation offline with both an expert dataset and a static offline dataset by first fitting a reward function that is then used in Least Squares Policy Iteration. CSI, however, requires the expert data to have global coverage and does not mitigate covariate shift with partial coverage like MILO does. Finally, Variational Model--asee Adversarial IL (V-MAIL) [50] learns a dynamics model from static offline dataset and performs offline imitation within the model. V-MAIL, however, studies zero- shot IL where the static offline data is samples from a variety of source tasks, and the expert dataset samples from the transfer target task. contrast, MILO investigates avoiding covariate shift in IL with an offline dataset collected by potentially suboptimal policy from the same task.
Offiine RL In offline RL, algorithms such as FQI [22] have finite-sample error guarantees under the global coverage [45; 5J. Recently, many algorithms to tackle this problem have been proposed from both model-free [76; 68; 43; 26; 23; 39] and model-based perspectives [82; 34; 44] with some pessimism ideas. The idea of pessimism features in offline RL with an eye to penalize the learner from visiting unknown regions of the atatenaction space [54; 31; 79; 12]. We utilize pessimism within the IL context where, unlike RL, the learner does not have access to an underlying reward signal. Our work expands prior theoretical results by (a) formalizing the partial coverage condition using notion of a relative condition number, and (b) offering distribution-dependen results when working with non-parametric models including gaussian processes. See Appendix C for detailed literature review.
2 Setting
We consider an episodic finite-horizon Markov Decision Process (MDP), M
d
where S is the state space, AA is the action space, S A
ASS) is the MDP's transition, H is the horizon, dg is an initial distribution, and c : S x A - [0. 1] is the cost function. A policy S + A(A) maps from state to distribution over actions. We denote dJ. A(S A) as the average state-action distribution of ा under transition kernel P. that is, dp I d:p.:. where d A(S A) is the distribution of (s(t), a))) under at t. Given a cost function T:SxA + [0, 1]. V7,,, denotes the expected cumulative cost of a under the transition kernel P and cost function f. Following standard IL setting, the ground truth cost function is unknown. Instead, we have the demonstrations by the expert specified by Te : S - A(A) (potentially stochastic and not necessarily optimal). Concretely, we have expert dataset in the form of i.i.d tuples D. = {st, a, )e, sampled from distribution d'...
x
In our setting, we also have an offline static dataset consisting of i.i.d tuples D. = (si, di 8 Vi s.t. (s, a) ~ p(s,a),** ~ P(s, a)), where p E ASS x A) is an offline distribution resulting from some behavior policies. Note behavior policy could be much worse policy than the expert x². Our goal is
3

---

Algorithm 1 Framework for model-based Imitation Learning with offline data (MILO)
1: Require: IPM class F, model class P, policy class II, datasets D. {8, a). D, = {s, a
2: Train Dynamies Model and Bonus: P: S A S and b: S A - RR+ offline data D.
3: Pessimistic model-based min-max IL: with P. b, De, obtain ALL by solving the following:
TLL argmin E ((s,))=zz [f(s b(s, a)] (s,a) ((s.))
(1)
to only leverage (De + Do) to learn a policy x that performs as well as T.. with regard to optimizing the ground truth cost More specifically, our goal is utilize the offline static data D, combat covariate shift and learn a policy that can significantly outperform traditional offline II. methods such as Behavior cloning (BC), without any interaction with the real world expert.
Function classes We introduce function approximation. Since we do not know the true cost function and transition kernel P. we introduce cost function class F C S x A + [0, 1] and transition model class P PSS A + A(S). We also need policy class II. For the analysis, we assume realizability:
Assumption 1. CE PEP, II.
We use Integral Probability Metric (IPM) as distribution distance measure, i.e,, given two distribu- tions P1 and P2. IPM with F is defined maxjer (B(s.))pılf(s, [s)] (( (f
3 Algorithm
The core idea of MILO is to imitate the expert by optimizing IPM distance between the agent and the expert with a penalty term for pessimism over the policy class. MILO consists three steps:
1. Model learning: fit a model P from the offline data D, to learn P.
2. Pessimistic penalty design: construct penalty function b(s, a) such that there is a high penalty state-action pairs that not covered by the offline data distribution p.
3. Offline min-max model- policy optimization: optimize Eq. (1)
Algorithm provides the details of MILO. We explain each component in detail as follows.
Model learning and Penalty: Our framework assumes we can learn a calibrated model (P, from the dataset D., in the sense that for any 8, a. we have: ( a) - P(1ss,)) a))] S minn(2 a)}- Such model training possible in many settings including classic discrete MDPs, linear models (KNR [32]), and non-parametric models such as GP. In practice, it is also common to train a model ensemble based on the idea of bootstrapping and then use the modellddisagreement approximate With such a calibrated model, the penalty will simply be b(s, a) O(Ho(s, a)). We will formalize this model learning assumption in Section We give several examples below.
For any discrete MDP, use the empirical distribution, i.e., P(s'|s, a) N(s', s, (s), X), where ((ss, a.) is the number (s, a) in D,,, and N(s', s, a) is the number (s, a, s') in D,,, and R In this case, we can set a(s a) = (VISI/N(ss
See example for more details.
For continuous Kernelized Nolinear Regulator (KNR (32]) model where the ground truth transition P(s'(s,a) a) is defined as s' W* (T*o(s,)) + c (0, E), with é being (nonlinear) feature mapping, we can learn P by classic Ridge regression on offline dataset D.,. Here we can set (s. a) Ō (BVo(s,)) om) for some B E R+, where E, the data covariance matrix E,, := Em (88, as ( T+) T + AI. See example for more details.
For non-parametric nonlinear model such as Gaussian Process (GP), under the assumption that P is in the form of s' = g" (s, a) + e ~ (0, Σ) (here S C Rd ). we can simply represent P using GP posteriors induced by Do. i... letting GP posterior be GP )n we have P(s' (s, a) being

---

represented as s' = ā(s,a) + e, Then, we can set a(s.a) = (3kn, ((s, (s. a))) with some parameter R (see example 3 for more details). GP a powerful model and has been being widely used in robotics problems, see [36; 18; 8; 71; 25] for examples.
In practice, we also use model ensemble of neural networks with the maximum disagreement between models as a. This has been widely used in practice (e.g., [47; 6; 48J). We leave the details Section 5 where we instantiate a practical version of MILO, and the experiment section. As we can see from the examples mentioned above, in general, the penalty b(s, a) = O(Ho(s, a)) is designed such that it has a high value in state-action space that is not covered well by the offline data Do, and has a low value in space that is covered by D Adding such a penalty automatically forces our policy to stay away from these regions where P is not accurate. On the other hand, for regions where has good coverage (thus P is accurate), we force π to stay close to T².
Pessimistic model-based min-max IL: Note Eq. is purely computational, i.e., we do need any real world samples. To solve such max objective. we can iteratively (1) perform the best response on the max player, i.c., compute the argmax discriminator f given the current 9, and (2) perform incremental update on the min player, e.g., use policy gradient (PG) methods (e.g. TRPO) inside the learned model P with cost function f(, a) + b(s.a). We again leave the details to Section 5.
3.1 Specialization to offline RI.
In RL. the cost function is given. The goal is obtain n' argmax Vg.e- The pessimistic policy optimization procedure [81; 31] is TRL = argmin ()) [c(s, a) b(s, a)]. While this is not our main contribution, we will show a byproduct of our result a novel non-parametric analysis for offline RL which does not assume p has global coverage (see Remarks 4,7,11).
4 Analysis
Our algorithm depends on the model P estimated from the offline data. We provide unified analysis assuming that İ is calibrated in that its confidence interval is provided. Specifically, we assume:
Assumption 2. With probability 1- the estimate model P satisfies the following: [|P(-|s. a) P(-[s, a I
a). 2) V(s,a) E S x A. We set the penalty as b(s,a) = H min(o a). 2).
We give the following three examples. For details, refer to appendix A.
Example 1 (Discrete MDPs). Set uncertainty measure (ss, a)= V S log 2+1og
2(N(s.))
M(sa)+
Example 2 (KNRs). In KNRs, the ground truth model is s' W W* a) e~ E~ NO0 (2) where E Rdd a RdA, & : S A + Rd is some known state-action feature mapping. The estimator is
((-) = WW--) W = argminweR4ex4, 1/n, IIl ((,,((s))) - s'1121 + +/
where 111 is frobenius norm. We set the uncertainty measure as)
En, = -In blsi a:) (8i, + AI with 3n. = 12 8c8 log(5) + log(1/8) + M1. where In., = log(dot AI)). Example (GPs). In GPs, the ground truth model is defined as s' = (s, e, E NO 12 where 9r belongs to an RKHS Hy with a kernel k(-,-). Denote x == (s,a), we have GP posterior as
as = (1/()3,, o os (s.
g(-) S(Kn, + ( (,,,))),,,))) (+), S S= 1811
[k(11,)), ... k((nn x))T kn (x,xx) k(1, - knn (a)) (Kn, + (I2 - (x"), with o() = Bn, kno (,.)/5, Bn. = =(dss logo (dsn. 1/2), In. = log(det(II+ ( (-2Knn))
K E Bede xno,
Tin
(Kn. Jis (()1,15) (1 si 5 no. 1 S Siinnn sn).
General results We show our general error bound results. For the proof, refer appendix B. For analytical simplicity, we assume [F] is finite (but the bound only depends on In((F))) 5.
When [F] is infinite, we can show that the resulting error bound scales w.r.t its metric entropy.
5

---

Theorem 3 (Bound of MILO), Suppose assumptions 1,2. Then, with probability 1 1--2 26,
V. Vp. Err, Err,: ErT, 8H (s,)) (min(o((s, a). 1)]. Err, =2H,
(2 2nc
We will show through a set of examples where ((. (min(o a). 1)] shrinks to zero no oo under the partial coverage, i.e. when p covers di Asymptotically. EIT, will dominate the bound. Note that ErT, has two components, linear H and term that corresponds to the statistical error related to expert samples and function class complexity. Comparing to BC, which has rate O(H² Vlog )/n.) [4, Chapter 14], we see that the horizon dependence improved.
Before going to each analysis of Err., we highlight two important points in our analysis, First, our bound requires only the partial coverage, i,e., it depends on T.-Concentrability coefficient which measures the discrepancy between the offline data and expert data. This is the first work deriving the bound with Te ce-concentrability coefficient in IL with offline data. Second, our analysis covers non- parametric models. This is a significant contribution as previous pessimistic offline RL finite-sample error results have been limited the miite-dimensionll linear models or discrete MDPs [31: 54].
Remark 4 (Implications on offline RL). As in theorem 3, we have V VF.- = O (sa))aap" (a(s, a))) (appendix B). Note similar results have been obtained in [82; 34). Since this term ErT, by just replacing ne with n², this offline RL result is a by-product of our analysis.
4.1 Analysis: Discrete MDPs
We start from discrete MDP as a warm up. Denote C.. = ma,(ssaa) di (ss.a//((s) a). Theorem 5. Suppose x (1(1) and the partial coverage C* co. With probability 8,
Err, S H2H
CTa]SPIA||
C (S11S|1A|
log((
where C₁, C2 are universal constants.
The error does not depend on supxem C* or C supxen maX(s.) d'p(s, a)d (s. a). We only require the partial coverage C* < 0o, which is much weaker than suprem C* < do (p has global coverage) and C oo (d% has global coverage [62]). When C is small and n, is large enough, Err. 0 (H
dominates ErT, in theorem 3. Then, the error is linear in horizon H.
4.2
Analysis: KNRs and GPs for Continuous MDPs
Now we move to continuous state-action MDPs. In continuous MDPs, assuming the boundedness of density ratio C is still strong assumption. As we dive into the KNR and the nonparametric GP model, we will replace the density ratio with a more refined concept relative condition number.
Let E, = B(e,a)=llo(s a) and Σm.. B(s,a)=a7= [ø(s, (o(s,a)dle a))(s, a) We define the relative condition number as C sup number could still be finite as concerns subspaces on ((s, a) rather than the whole S x A.
KNRs
Er. En Even when density ratio is infinite, this
To further gain its intuition, we consider discrete MDPs and the feature mapping Φ(s, E IR ISIIIA which is a one-hor hot encoding vector that has zero everywhere except one at the entry corresponding to the pair (s. a). In this case, the relative condition number is reduced to max(s.a) de (s, a))p(ss a).
Theorem 6 (Error for KNRs). Suppose sups,a [|o(s, a)ll < 1, X 22 2(1), W 2(1)
and the partial coverage C. < Oc. With probability 1 6,
Err. S e, H2 (rank?(E,) + rank(E,) log( (+)) /
doChe no
log" 1/2 no))
where ej and 02 are some universal constants.
Theorem 6 suggests Err, is are small and the offline sample size n, is large enough, ErT, dominates ErT, in theorem 3. Again, this case, Err. = O Vln(F)/m)) and we see that grows linearly w.r.t horizon H.
stee//no)) In other words, when Cm.,, rank [Σp]]

---

Our result is distribution dependent and captures the possible low-rankness of the offline data, i.e., rank[E,l depends on p and could be much smaller than the ambient dimension of feature ((s. a). The quantity C corresponds to the discrepancy measured between the batch data and expert data. This is much smaller than the worst-case concentrability coefficient: Supup
ae C"..
Remark 7. In RI, similar quantity has been analyzed in [31], which studies the error bound of linear FQI with pessimism. Comparing to our result only requiring partial coverage, [31, Corollary 4.5] assumes the global coverage, i.e., Ep is full-rank, which is stronger than Ö < co.
GPs Now we specialize our main theorem to non-parametrie GP models. For simplicity, following [63], we assume S x A is compact space. We also suppose the following. Recall I := (s, a). Assumption 8. k at) S 1, Va E S x A. k(.;)) is a continuous and positive semidefinite kernel.
Under the assumption 8, we can use Mercer's theorem [73], which shows that there exists a set of pairs of eigenvalues and eigenfunctions {Mt ) where ʃ (x)))) (x))xx for all i and J p(x))))(())) (x))d 0 for i # j. Figenfunctions and eigenvalues essentially defines an infinite-dimensional feature mapping <(x) =- Iv (2), ..... Voc (x)]². Here, k(r, x)) <(z) ((z), and any function f E H. can represented as f(-)
Φ(-). Note that the eigenvalues and eigenfunctions are defined w.r.t the offline data p. thus our result here is still distribution dependent rather than a worst case analysis which often appears in online RI/II settings [63; 32; 78; 17).
Assume eigenvalues {MII,..., Moa}} } are non-increasing order, we define the effective dimension, Definition (Effective dimension). d' min(j N: N:1 j 2 B + 1)mo/(3) B(j) ΣE= Mk-
The effective dimensions d' is widely used and calculated for many kernels [85; 7; 72; 28]. In finite- dimensional linear kernels {a + a o(z); a E { (k(x, x)) o' (x))(z)) have d' I rank p Thus, d" is considered to be a natural extension of rank[Ep) [Ep] to dimenss-iimenionalll models.
Theorem 10 (Error for GPs). Let E,,, Ed (0(x))(a) ", Ep Ex-pl ((==)((=))(()]] Suppose assumption 8, <² = (2(1) and the partial coverage C = sup |alaas (x /x, x/x Epx) < co. With probability 8,
Err. S e1 H2 ((d*)² + d' log(c2/8))
V
dsC no
(c2dsn//2/ log(1 + no).
(3)
where C12 02 are universal constants.
The theorem suggests that Err, is 2(H22t² /dgCa=/ /no). Thus, when CM d' are not so large and no is large enough, Err, asymptotically dominates Err, in theorem 3 (again Err, is linear in H).
While defer the detailed proof of the above theorem Appendix C.3, highlight some techniques we used here. The analysis is reduced to how to bound the information gain In, and Exwar (,,,(,,, aI). In both cases, we analyze them into two steps: transforming them into the variational representation and then bounding them via the uniform low with localization (Lemma 39).
Remark 11 (Implication to Offline RL). As related literature, in model-free offline RI, 170; 21] obtain the finite-sama sample error bounds using nonparametric models. Though their bounds can be char- acterized by the effective dimension, their bounds assume full coverage, i.e., maX(s,a) 1/ l/p(s,a) < co.
5 Practical Algorithm
In this section we instantiate a practical version of MILO using neural networks for the model class P and policy class II. We use the Maximum Mean Discrepancy (MMD) with a Radial Basis Function kernel as our discriminator class F. Note using MMD as our discrepancy measure allows us to compute the exact maximum discriminator argmaxfee in closed form (and is detailed in appendix). We use a KL-based trust-region formulation for incremental policy update inside the learned model P. Based on Eq. (1), we first formalize the following constrained optimization framework:
min f (a( (ss, a) + b(s, a)) ((..,) [f(ss((, a)) s.t. (.))) /e (a, 8, x))
where L: A x
+ TR is loss function (e.g., negative likelikel or any supervised learning loss one would use in BC). Essentially, since we have D. available, we use it together with any
7

---

Algorithm 2 A practical instantiation of MILO
1: Require: expert dataset D. {s, a). offline dataset D, := {8, s'}
2: Train an ensemble neural network models random initialization;
Bn where each P; starts with different
3: Set bonus b(s, a) = maxi, (19.(s, - g (3(3,0) a)ll and initialize ne.
4: for = 0 + T - 1 do
5: Wy = arg maxxplllast TT (E(s.a)mz (0(5, a)] E ((sa) (ot,,,,l((s))) (o(, f((s (()))s
6: Bct1 = 0, - nFo
E (((a))
(
P. P.tto (3. + \B Vella, mo,))
7: end for
supervised learning loss to constrain the policy hypothesis space. Note for a deterministic expert me- the expert policy is always feasible solution. Thus adding this constraint reduces the complexity of the policy class but does not eliminate the expert policy, and our analysis in Section still applies.
In our practical instantiation, we replace the hard constraint instead by Lagrange multiplier, i.e. we use the behavior cloning objective regularization term when solving the min-max problem:
mil fax [E(s,a)ddz (f(s, a) + b(s, a)) - (.).,)) (f a)] + À B(s,a))D, [ (a, 8, m)].
Given policy Te, (0, denotes the parameters), we update the discriminator ft. Then, with fixed ft. in order to update policy π use NPG in line 6 in Algorithm where A P.f+b is the disadvantage function of тe and Fe, == E ( Th V In Te, (als ( In ne. (als)"] is the fisher information matrix.
6 Experiments
We aim to answer the following questions with our experiments: (1) How does MILO perform relative to other offline IL methods, (2) What is the impact of pessimism MILO's performance? (3) How does the behavior policy's s coverage impact MILO's performance? (4) How does MILO's result vary when we increase the number of samples drawn from the expert policy?
We evaluate MILO on five environments from OpenAI Gym [11] simulated with MuJoCo [67]: H2p Walker2d-v2, HalfCheetah-v2. Ant-v2, and Humanoid-v2. We compare MILO against the following baselines: (1) ValueDICE [38], state-of-the-ars off-policy IL method modified for the offline II. setting; (2) BC on the expert dataset; and (3) BC on both the offline and expert dataset.
Hopper (125 Expert Samples)
Walker2d (125 Expert Samples)
HalfCheetah (125 Expert Samples)
1000
6000
2000
2000
4000
MILO
BC (Eagart Date)
1000
2000
Faport Data)
Expert Score
SU
100
350
200
160
100
150
200
Ant (125 Expert Samples)
Humannid (200 Expert Samples)
Normalized Scores
3000
3000
0.75
2010
2000
0.50
1000
1000
0:00
50
100
15C
200
100
300
700
500
1lugptr
Walkerdd
Vussotoo
Iterations
Berations
Figure 2: Learning curves across five seeds for MILO plotted against the best performance of BC after 1000 epochs of training the expert/offlinctexxee after 10 thousand iterations. The bottom right bar graph shows the expert performance normalized scores where plot the performance the last iteration for MILO.
data and the best performance of VaCueDICE

---

For the expert dataset, we first train expert poli- cies and then randomly sample (s, a)-parrs from pool of 100 expert trajectories collected from these expert policies. We randomly sample to create very small expert (s, (s,a))pp a)pair datasets where BC struggles to learn. Note that BC is effective at imitating the expert for MuJoCo tasks even with a single trajectory; prior works [27; 37; 38] have used similar sub-sampling strategies to create expert datasets to make it harder for BC to learn. The offline datasets are collected building on prior Offline RL works [76; 34]; each dataset contains million samples from the environment. We first train behavior policies with mean performances often less than half of the expert performance (Table 1, column 2). All results are averaged over five random seeds. See appendix for details hyperparameters, environments, and dataset composition.
Table Performance for expert and behavior pol- icy used to collect expert and offline datasets re- spectively.
Expert
Behavior
Environment
Performance
Performance
Hopper-v2
3012
752 (25%)
walker2d-v2
3082
1383 (45%)
HalfCheetah-v2
5986
3972 (66%)
Ant-v2
3072
1208 (40%)
Humanoid-v2
3248
1505 (46%)
6.1 Evaluation on MuJoCo Continuous Control Tasks
Figure 2 presents results comparing MILO against benchmarks. MILO is able to achieve close expert level performance on three out of the five environments and outperforms both BC and ValueDICE on all five environments. Both MILO and ValueDICE were warmstarted with on the offline dataset. We significantly outperform BC's performance when trained on the expert dataset, suggesting MILO indeed mitigates covariate shift through the use of a static offline dataset of (s, a)-pairs. BC on both the offline and expert dataset does improve the performance, but this still cannot successfully imitate the expert since BC has no way of differentiating random//ubboppimal trajectories from the expert samples. ValueDICE, on the other hand, does explicitly aim to imitate the expert samples; however, in theory, it would require either the offline data (i.e. the replay buffer) or the expert samples to have full coverage over the state-actin action space. Since our offline dataset mainly collected from a sub-optimal behavior policy and our expert samples are from a high quality expert, neither our offline nor our expert dataset is likely to have full coverage globally; thus potentially hurting the performance of algorithms like ValueDICE. Note that MILO still able to perform reasonably well across environments even with these offline and expert datasets.
epoch of BC
6.2 Ablation
Impact of Pessimism Figure 3 (Left 2) presents MILO's performance on two representative envi- ronments with and without pessimism (i.e., setting penalty to be zero) added to the imitation objective. Pessimism stabilizes and improves the final performance for MILO. In general, MILO consistently outperforms benchmarks and/or achieves expert level performance for given set of hyperparameters. See the Appendix for evaluation on other environments.
Behavior with more expert samples We investigate whether MILO is able to achieve expert per- formance with more expert samples in the two environments (walker and humanoid) that it did not
Hogper (125 Expert Sumples)
Walter Expert Samples]
Wilker (1000 Expert Sumples)
Humanodd (1000 Expen Sumples)
1300
2:30
250
2000
1000
3309
50C
3.5
Figure 3: (Left 2) Learning curves for Hopper and Walker2d with (red) and without (blue) pessimism. MILD generally performs worse without pessimism. (Right 2) Learning curve for Walker2d and Humanoid with more expert samples.

---

solve with very small expert datasets in Figure 2. Figure 3 (Right 2) shows that with one trajectory worth of expert samples, MILO able to achieve expert performance on walker and humanoid.
Impact of Coverage As our analysis suggests, MILO's performance degrades as the offline data's s coverage over the expert's ss state-action space decreases. use the behavior policy's value as surrogate for lower coverage, i.e. lower value suggests lower coverage. We gen- erate two additional offline datasets for cach environment by lowering the performance of the behavior policy. The three datasets are: (1) the original offline datasets used in Table (== 25% for Hvpper-v2 and 50% for others); (2) ones
Table 2:
Expert performance normalized scores on three different offline datasets collected from behavior policies with approximately 50%, 25%, and random performance relative to the expert.
Environment
50%
25%
Random
Hoppar-v2
0.95 0.01
0.66
0.33
0.42 0.36
Nalker2d-v2
0.72 0.02
0.27
0.006
0.23 0.12
HalfCheetab-v2
0.96 0.01
0.02
0.01 0.02
Ant-v2
1.02 0.02
0.99
0.21 + 0.52
Humanoid-v2
0.88 0.10
0.72 0.03
0.08 0.01
that have roughly half the performance of (1) (12% for Hopper-v2 and = 25% for others); and (3) ones collected from random behavior policy (Random). Table 2 shows that MILO performs reasonably on three environments even with lower coverage dataset (second column) and achieves more than 20% of the expert performance three environment even with the Random dataset.
7 Conclusion
MILO investigates how to mitigate covariate shift in IL using an offline dataset of environment interactions that has partial coverage of the expert's state-action space. We show the effectiveness of MILD both in theory and in practice. In future works, we hope to scale to image-based control.
work. An IL algorithm We want highlight the potential negative societal/ethical impacts is only as good as the expert that it is imitating, not only in terms of performance but also with regards to the negative biases and intentions that the demonstrator has. When designing real-world experiments/applicann
for MILO we believe the users should do their due diligence on removing any negative bias malicious intent the demonstrations that they provide.
10

---

References
[1] Y. Abbasi-yadkori, Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[2] P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In ICML, page ACM, 2004.
[3] A. Agarwal, M. Henaff, Kakade, and W. Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. NeurIPS, 2020.
[4] A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep. 2019.
[5] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71:89- 129, 2008
[6] K. Azizzadenesheli, E. Brunskill, and A. Anandkumar. Efficient exploration through bayesian deep q-nerworks. In 2018 Information Theory and Applications Workshop (ITA), pages 1-9, IEEE, 2018.
[7] Bach. On the equivalence between kernel quadrature rules and random feature expansions. Journal of machine learning research, 18(21):1-38. 2017.
[8] S. Bansal, R. Calandra, T. Xiao, S. Levine, and C. J. Tomiin. Goal-driven dynamics learning via bayesian optimization. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 5168-5173. IEEE, 2017.
[9] L. Bartlett, O. Bousquet, and S. Mendelson. Local rademacher complexities. Annals of Statistics, (3(4):1477-153) 08 2005.
[10] K. Brantley, W. Sun, and M. Henaff. Disagroement-rrgularizze imitation learning. In Interna- tional Conference on Learning Representations, 2019.
[11] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym, 2016.
[12] Buckman, C. Gelada, and M. G. Bellemare. The importance pessimism fixed-dataset policy optimization. arXiv preprint arXiv:2009.06799, 2020.
[13] D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco. Gaussian process opti- mization with adaptive sketching: Scalable and no regret. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 533-557, 2019.
[14] A. J. Chan and M. van der Schaar. Scalable bayesian inverse reinforcement learning. arXiv preprint 2ii.:22002.0642 2021.
[15] K.-W. Chang, H. He, H. Daumé III, and J. Langford. Learning to search for dependencies. arXiv preprint arXiv: 150.00561, 2015.
[16] Chen and Jiang. Information-theorrticc considerations in batch reinforcement learning. In Proceedings of the 36th International Conference Machine Learning, volume 97, pages 1042-1051, 2019.
[17] S. R. Chowdhury and A. Gopalan. Online learning in kernelized markov decision processes. In K. Chaudhuri and M. Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3197-3205. PMLR, 16-18 Apr 2019.
[18) M. Deisenroth and C. F. Rasmussen. PILCO: model-based and data-efficient approach to policy search. In International Conference on Machine Learning, pages 465-472, 2011.

---

[19] S. S. Du, S. M. Kakade, J. D. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: structural framework for provable generalization in rl. JCML, 2021.
[20] Y. Duan, Z. Jia, and M. Wang. Minimax-optimal off-policy evaluation with linear function approximation. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2701-2709, 2020.
[21] Y. Duan, C. Jin, and Z. Li. Risk bounds and rademacher complexity in batch reinforcement learning, arXiv preprint arXiv:2103. 13883, 2021.
[22] D. Ernst, P. Geurts, and L.. Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
[23] R. Fakoor, J. Mueller, P. Chaudhari, and A. J. Smola. Continuous doubly constrained batch reinforcement learning. arXiv preprint arXiv:2 2021.
[24] J. Fan, Z. Wang, Y. Xie, and Z. Yang. A theoretical analysis of deep q-learning. In Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 486-489, 2020.
[25] J. F. Fisac, A. K. Akametalu, M. N. Zeilinger, S. Kaynama, J. Gillula, and C. J. Tomlin. A general safety framework for learning- control in uncertain robotic systems. IEEE Transactions Automatic Control, 64(7):2737-2755 2018.
[26] S. Fujimoto, D. Meger, and D. Precup. Off-policy deep reinforcement learning without explo- ration. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2052-2062. PMLR, 09-15 Jun 2019.
[27] Ho and S. Ermon. Generative adversarial imitation learning. NIPS, 2016.
[28] D. Janz, D. Burt, and J. Gonzalez. Bandit optimisation of functions in the matérn kernel rkhs. In Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1486-2495. 2020.
[29] D. Jarrett, I. Bica, and M. van der Schaar. Strictly batch imitation learning by energy-based distribution matching. In Advances in Neural Information Processing Systems, volume 33, pages 7354-7365, 2020.
[30] N. Jiang. Notes on tabular methods, 2020.
[31] Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offiine rI? arXiv preprint arXiv:2012. 15085, 2020.
[32] S. Kakade, A. Krishnamurthy, K. Lowrey, M. Ohnishi, and W. Sun. Information theoretic regret bounds for online nonlinear control. In Advances in Neural Information Processing Systems, volume 33, pages 15312-15325, 2020.
[33] R. Kidambi, J. Chang, and W. Sun. Optimism is all you need: Model-based imitation learning from observation alone. arXiv preprint arXiv:2 10769, 2021.
[34] R. Kidambi, A. Rajeswaran, P. Netrapalli, and T. Joachims. Morel: Model-based offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 21810-21 10-11122..... Curran Associates, Inc., 2020.
[35] E. Klein, B. Piot, M. Geist, and O. Pietquin. A cascaded supervised learning approach inverse reinforcement learning. In ECML/KKD, 2013.
[36] J. Ko, D. J. Klein, D. Fox, and D. Haehnel. Gaussian processes and reinforcement learning for identification and control of an autonomous blimp. In Proceedings 2007 ieee international conference on robotics and automation, pages 742-747, IEEE, 2007.
[37] I. Kostrikov, K. K. Agrawal, D. Dwibedi, S. Levine, and J. Tompson. Discriminator-actorrrriic Addressing sample inefficiency and reward bias in adversarial imitation learning. ICLR. OpenReview.net, 2019.
12

---

[38] I. Kostrikov, O. Nachum, and J. Tompson. Imitation learning via off off-policy distribution matching. ICLR, 2019.
[39] A. Kumar, A. Zhou, G. Tucker, and S. Levine. Conservative q-learning for offline reinforcement learning. arXiv preprini Stti:200060047799 2020.
[40] M. Laskey, J. Lee, W. Y. Hsich, R. Liaw, J. Mahler, R. Fox, and K. Goldberg. Iterative noise injection for scalable imitation learning. CoRR, abs/1703.09327, 2017.
[41] L. Le Gratiet, L. Le Gratiet, Garnier, and J. Garnier. Asymptotic analysis of the learning curve for gaussian process regression. Machine learning, 98(3):407-433,
2015. 2015.
[42] Liao, Z. Qi, and Murphy. Batch policy learning in average reward markov decision processes, arXiv preprint vrXiv:2007.11771, 2020.
[43] Y. Liu, A. Swaminathan, A. Agarwal, and E. Brunskill. Provably good batch off-policy reinforcement learning without great exploration. In Advances in Neural Information Processing Systems, volume 33, pages 1264-1274, 2020.
[44] T. Matsushima, H. Furuta, Y. Matsuo, O. Nachum, and S. Gu. Deployment-efficient reinforce- ment learning via model-based offline optimization. ICLR, 2020.
[45] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(May):815 857, 2008.
[46] O. Nachum, Y. Chow, Dai, and I.. Li. Dualdice: Sehavior-agnosee estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems 2019, 2019.
[47] I. Osband, J. Aslanides, and A. Cassirer. Randomized prior functions for deep reinforcement learning. In Advances in Neural Information Processing Systems, volume 31, 2018.
[48] D. Pathak, D. Gandhi, and A. Gupta. Self-supervised exploration via disagreement. In K. Chaudhuri and Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5062- 5071. PMLR, 09 15 Jun 2019.
[49] D. A. Pomerlau. ALVINN: An autonomous land vehicle in a neural network. In D. S. Touretzky, editor, Advances in Neural Information Processing Systems, pages 323-331, San Mateo, CA, 1989. Morgan Kaufmann Publishers inc.
[50] R. Rafailov, T. Yu, A. Rajeswaran, and C. Finn. Visual adversarial imitation learning using variational models. CoRR, abs/2107.08822 2021.
[51] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, vol- ume 20. Curran Associates, Inc., 2008.
[52] N. Rajaraman, I. F. Yang. J. Jiao, and K. Ramachandran. Toward the fundamental limits of imitation learning. arXiv preprint arXiv:2009.05990, 2020.
[53] A. Rajeswaran, V. Kumar, A. Gupta, G. Vezzani, J. Schulman, Todorov, and S. Levine. Learn- ing Complex Dexterous Manipulation with Deep Reinforcement Learning and Demonstrations. In Proceedings of Robotics: Science and Systems (RSS), 2018.
[54] P. Rashidinejad, B. Zhu, C. Ma, Jiao, and S. Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv:2103. 2021.
[55] C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005.
[56) Reddy, A. D. Dragan, and Levine. Sqil: Imitation learning via reinforcement learning with sparse rewards. In ICLR, 2020.
13

---

[57] S. Ross and J. A. Bagnell. Efficient reductions for imitation learning. In AISTATS, pages 661-668, 2010.
[58] S. Ross and A. Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arX.5:1406.5979 2014.
[59] S. Ross, G. Gordon, and J. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In A/STATS, 2011.
[60] M. W. Seeger, S. M. Kakade, and D. Foster. Information consistency of nonparametric gaussian process methods. IEEE Transactions on Information Theory, 54(5):2376 2222222,,,,, 2008.
[61] P. Sollich and A. Halees. Learning curves for gaussian process regression: Approximations and bounds. Neural computation, 14(6):1393 1428, 2002.
[62] Spencer. S. Choudhury, A. Venkatraman, B. Ziebart, and A. Bagnell. Feedback in imitation learning: The three regimes of covariate shift. arXiv preprint arXiv:2102.00887, 2021.
[63] N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, page 1015-1022, 2010.
[64] W. Sun, N. Jiang, A. Krishnamurthy, A. Agarwal, and J. Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-fre approaches. In Proceedings of the Thiody-Second Conference on Learning Theory, volume 99 of Proceedings 2019.
of Machine Learning Research, pages
[65] W. Sun, A. Vemula, B. Boots, and D. Bagnell. Provably efficient imitation learning from observation alone. In International Conference on Machine Learning, pages 6036-604 PMLR, 2019.
[66] W. Sun, A. Venkatraman, G. J. Gordon, B. Boots, and J. A. Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. arXiv preprint 17Xiv:1703.010300 2017.
[67] E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physies engine for model-based control. In IROS, pages 5026-5033. IEEE, 2012.
[68] A. Touati, A. Zhang, J. Pineau, and P. Vincent. Stable policy optimization via off-policy divergence regularization. arXiv preprint arXiv:2003.04100 2020.
[69] M. Uehara, J. Huang, and N. Jiang. Minimax weight and q- funeetioo learning for off-policy evaluation. In Proceedings of the 37th International Conference on Machine Learning, pages 9659-9668, 2020.
[70] M. Uehara, M. Imaizumi, N. Jiang, N. Kallus, W. Sun, and T. Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint arXiv:2102.029881 2021.
[71] Umlauft, I.. Pöhler, and Hirche. An uncertainty-based control Цyарunov approach for control-affine systems modeled by gaussian process. IEEE Control Systems Letters, 2(3):483- 488, 2018
[72] M. Valko, N. Korda, R. Munos, I. Flaounas, and Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference Uncertainty in Artificial Intelligence, UAI 13, page 654-663, Arlington, Virginia, USA, 2013. AUAI Press
[73] M. J. Wainwright. Dime--iie Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, New York, 2019.
[74] R. Wang. D. P. Foster, and S. M. Kakade. What are the statistical limits of offline rl with linear function approximation?. arXiv preprint 2rXiv:2010.11895 2020.
[75] C. K. Williams and F. Vivarelli. Upper and lower bounds on the learning curve for gaussian processes. Machine learning, 40(1):77-102, 2000.
14

---

[76] Y. Wu, G. Tucker, and O. Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv: 191.11911 2019.
[77] Xie and N. Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. UA12020, 2020.
[78] Z. Yang. C. Jin, Z. Wang. M. Wang, and M. Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. In Advances in Neural Information Processing Systems, volume 33, pages 13903-13916, 2020.
[79] M. Yin, Bai, and Y.-X. Wang. Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01748, 2021.
[80] M. Yin and Y.-X. Wang. Asymptotically efficient off-po evaluation for tabular reinforcement learning. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages 3948 3958, 2020.
[81] T. Yu, A. Kumar, R. Rafailov, A. Rajeswaran, S. Levine, and C. Finn. Combo: Conservative offline model-based policy optimization. arXiv preprint arXiv:2102.08363, 2021.
[82] T. Yu, G. Thomas, L. Yu, S. Ermon, J. Zou, S. Levine, C. Finn, and T. Ma. Mopo: Model- based offline policy optimization. In Advances in Neural Information Processing Systems, volume 33, pages 14129-14142, 2020.
[83] A. Zanette, Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. arXiv preprint arXiv:2012.08005 2020.
[84] R. Zhang, Dai, L. Li, and D. Schuurmans. Gendice: Generalized offline estimation of stationary values. In International Conference on Learning Representations, 2020
[85] T. Zhang. Learning bounds for kernel regression using effective data dimensionality. Neural computation, 17(9):2077-2088, 2005.
[86] B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In AAAI, 2008
15


Reviews:
[{"review_id": "h2oACvQXj7Q", "reviewer": "Reviewer_UUFL", "summary": "The authors present MILO an offline imitation learning algorithm that uses a learned model of the environment to generate trajectories from arbitrary policies. This allows to reuse similar algorithms than in the online case such as GAIL or Wasserstein GAIL.  In addition, the authors use a bonus (pessimism) to penalize data that is generated in places with high model uncertainty. This can be achieved using an ensemble. They present experimental results as well as an ablation study on OpenAI Gym.  ", "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": "I think the paper is still not ready for publication in a venue such as Neurips for the following reasons.\n\nFirst, the literature may have not been studied properly. Indeed,  the idea of offline imitation or offline inverse reinforcement learning using a set of expert trajectories and a set of non-expert trajectories to add dynamics information is not new :\n\n - A Cascaded Supervised Learning Approach to Inverse Reinforcement Learning (ECML 2013)\n\nUnfortunately, this paper is not cited.  Also the authors do not cite DART (DART: Noise Injection for Robust Imitation Learning) which is also one way to avoid covariate shift by adding noise when collecting trajectories from the expert.  Finally the idea of framing the IL/IRL problem as a min-max problem dates at least from the 2004 seminal paper of Peter Abbeel (Apprenticeship Learning via Inverse Reinforcement Learning) and could have been cited. \n\nSecond, the experiments section should prove the main point against online methods raised by the authors in the introduction: \"online interactions are often costly and prohibitive for real world applications where active trial-and-error exploration in the environment could be unsafe or impossible\". Unfortunately, I was not convinced. Indeed, in the experiments section the non-expert data set to train the generative model uses 1 million transitions. Therefore, one possible experiment could be to see how much data an online imitation learning algorithm such as GAIL needs to generate to reach the same performance as MILO and show that MILO is at least one order of magnitude below that. Without this experiment we can't really judge how data-efficient is MILO compared to GAIL. One other interesting experiment could be to see what is the proportion of low-score trajectories generated by GAIL compared to the dataset used to train the generative model. This experiment would tell you how unsafe GAIL is compared to MILO. Those two experiments could prove clearly the point you were making in the introduction. I encourage strongly the authors to run those experiments which will make the paper stronger.\n\nThird, you should have an offline IRL or IL baseline (such as CSI) and not baselines that are artificially weakened such as behaviour cloning baselines with sparse expert data. It is known that this is an adversarial setting for these methods. The same goes for MILO when the non-expert data is random which results on poor results as shown in Table 2. \n\nFourth, the analysis section could be moved in the appendix section because it covers cases such as discrete MDPs and GPs that are not related to the practical algorithm presented and used in the experiments. Indeed different instanciations of the general algorithms are presented and this can be confusing for the reader. For instance the algorithm is presented with and without behaviour cloning loss and then the exact cost function is only provided in the appendix. An exact and detailed description of the algorithm used for the experimental section should be done in the main paper.  In addition, the authors should focus more on how could we learn the model \\hat{P} on more challenging environments. This is the main bottleneck of this algorithm. This scaling problem seems quite challenging if the states are images or high-dimensional in general. How much data will be needed in that case? Should this model be learned at the latent level?\n\nOverall I think the paper has some strong points like the idea of learning the bonus b with an ensemble of networks and could be published in a top-tier conference. However, there is still a lot of work on the experiment section to show quantitatively what is the advantage of using offline methods versus online methods and on the method section to present more clearly the exact algorithm.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes the authors address the limitations and potential negative societal impact of their work adequately.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "fBytB2p4Gq4", "reviewer": "Reviewer_aRRv", "summary": "This paper studies imitation learning without access to the environment. The agent is provided with two datasets: one containing expert policy state-action pairs and one containing state-action-next state triplets collected from the environment. The authors propose the algorithm MILO that leverages pessimism to mitigate covariate shift and provide performance upper bound in discrete MDPs, kernelized nonlinear regulators, and Gaussian processes. The authors show improved performance achieved by MILO compared to other baselines such as behavioral cloning in MuJoCo control tasks. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n- Theory on non-parametric models in offline RL is new.\n- The authors derive bounds depending on the relative condition number w.r.t. expert policy in the KNR setting. In linear function approximation, the presented bound depends on the rank of offline data instead of assuming a full rank covariance. \n- The authors thoroughly discuss related work. \n- Novelty in algorithmic design is limited (e.g. can be considered a natural variant of MOPO in IL utilizing a cost function class).\n\nQuality:\n- The claims are supported with both theoretical analysis and empirical studies.\n- BC can perform much better than MILO in certain scenarios and it is unclear how one should choose between these two algorithms based on the datasets. For example, when the expert dataset has good coverage but the offline dataset doesn’t, MILO performs worse than BC by avoiding parts of the environment that are not covered in the offline dataset. On the other hand, when the expert dataset is extremely small but the offline dataset is large with good coverage on expert policy, MILO performs well (e.g. the setting considered in the experiments).\n\nClarity:\n- The paper is very well-written and easy to follow.\n\nSignificance:\n- The message that pessimism only requires partial coverage is already discussed in prior works. \n\nQuestions/comments:\n- Below Theorem 3, the authors compare MILO upper bound $O(H/\\sqrt{N})$ with BC upper bound $O(H^2/\\sqrt{N})$ in [3]. However, the upper bound of BC in [3] is not tight and the comparison is not fair. A tight upper bound of BC is $O(H^2/N)$ given in [47] which is much faster.\n- Could you explain the particular choice for characterization of expert policy coverage, e.g. using a ratio in discrete MDP setting? Why didn’t you use alternative measures such as the ones mentioned in Remark 26 in Appendix C.3?\n\nMinor points:\n- $b(s,a)$ is referred to as penalty and bonus interchangeably.\n- Should cost function class in line 103 be $\\mathcal{F} \\in \\mathcal{S} \\times \\mathcal{A} \\rightarrow [0,1]$?\n- A few capitalization errors in the references.\n\n___\nAfter the rebuttal:\n\nI thank the authors for responding to my questions. I am happy with the answers and stick to my score in favor of accepting this paper.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations and potential negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_1S3DNXmW_c", "reviewer": "Reviewer_Fuia", "summary": "This work considers an offline imitation learning setting where both expert and sub-optimal demonstrations are assumed to be known. While the covariate shift issue (the gap between training and test distributions) is a critical problem in offline imitation learning, e.g., behavioral cloning, authors address this issue by training a dynamics model through the sub-optimal demonstration (having state-action-successor state triples) and applying pessimistic penalty (incentivizing visiting the state-action pairs in the expert demonstration). With the theoretical derivations for various settings for dynamics modeling and the assumption that the demonstration does not have to cover the entire state-action space, authors show the theoretical guarantee of their proposed method. Also, the empirical results support their claim by showing that MILO (proposed algorithm) outperforms ValueDICE and BC.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I’m generally satisfied with the submission due to the authors’ clear writing, various experiments (including ablation studies like the impact of coverage), and rigorously defined mathematical terms. While I believe the submission is sufficient to be accepted, there are minor comments below:\n- I wonder why the authors did not check the performance of other recent baselines on offline imitation learning that cite the ValueDICE paper. For example,\n  - Jarret et al., “Strictly batch imitation learning by energy-based distribution matching,” (NeurIPS 2020, the reference [28] in the submission)\n  - Chan et al., “Scalable Bayesian inverse reinforcement learning,” (ICLR 2021, the reference [13] in the submission)\n- The citation style is not consistent with the normal NeurIPS citation style.\n- Would you please increase the size of figures and fonts in Figures 2, 3, and Table 1,2?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors pointed out the negative biases that are inherently given in expert demonstration, which I believe hasn’t been addressed in the submission. I couldn’t clearly imagine how to perfectly solve this but I believe recent works on using ranking in expert demonstrations might be helpful. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "HE3NUH6gJ8K", "reviewer": "Reviewer_WrHs", "summary": "This work proposes a new method for offline imitation learning. The setup is slightly different than usual as it supposes that, additionally to the expert dataset we want to imitate, we have access to a large dataset of non-expert interactions.\nThe method is the following: \n\n1) learn a model of the transition kernel from the data.\n\n2) Along with the model, learn an “uncertainty penalty” (the converse of an exploration bonus) that will encourage the agent to stay on the expert support.\n\n3) Train *offline* a min-max model-based policy-optimization with the uncertainty penalty. \n\nThe contributions also include theoretical analysis on the proposed method in simplified cases.", "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": "Thank you for this interesting work. A few questions, particularly on the experimental part:\n\nMethods:\n\n- Why don’t you also use the expert dataset for training the model? I see no interest in leaving it out.\n\n- Have you thought about any connection to the GAIL algorithm? What you call the pessimistic model-based offline IL is, I am not mistaken, an instantiation of the “adversarial imitation learning” framework with trajectories played in the model rather than online, and an additional non-exploration bonus. \n\nExperiments:\n\n- It is said (both in title and analysis) that the method does not require full coverage of the state space. I would have appreciated to see an experiment with the results of the methods when decreasing the size of $D_o$ (which is really important: 1M samples is not quite a “partial coverage” for these locomotion environments).\n\n- I find it slightly problematic that no presented baselines make use in a principled way of $D_o$ (BC just learns from it like it was expert data). In particular, one natural baseline (feel free to disagree) to me would be to train any offline RL learner on $D_e+D_o$ with the following reward: 1 for any sample in $D_e$, 0 for any sample in $D_o$ (in the spirit of SQIL [1]). In a GAIL-like manner, you could also define the reward as $log(D)$ with D a discriminator between $D_e$ and $D_o$ and train an offline agent on  $D_e+D_o$ with this reward function. \n\n- It would be great to detail in the appendix how hyperparameter selection was performed. In particular, I would encourage you to check out [2], that encourages not to select hyperparameters on the underlying reward function when performing imitation.\n\n- Can you clarify Appendix E.1? Why did you modify the base environments most people in the community use? I find this quite surprising and I do not feel comfortable with this. According to me, you should either switch back to the widely used environments or justify very clearly why you needed these modifications.\n\n- From Fig.2 it looks like the method is initialized with BC. As far as I can tell, this is not specified in the paper. Otherwise, why is MILO’s curve not starting at random behavior’s performance?\n\n\nI would increase my score if you can provide clear explanations concerning the experimental setup. Bonus if you can elaborate a bit on the link to GAIL and add these additional baselines.\n\n\n\n[1] Reddy, S. et. al., 2019. Sqil: Imitation learning via reinforcement learning with sparse rewards. arXiv preprint arXiv:1905.11108.\n[2] Hussenot, Leonard, et al. \"Hyperparameter Selection for Imitation Learning.\" arXiv preprint arXiv:2105.12034 (2021).\n\n\n\n# Update after rebuttal\n\nI would like to thank the authors for clearly answering my questions and providing additional experiments/ablation supporting the method's results.\n\nI encourage the authors to include the feedback they provided here in the paper itself.\n\nI would say that the methodology for hyperparameter selection is not following best practices (e.g. taking best of with/without BC init) and I encourage the authors to improve this for future works. Yet, most of my concerns were answered and, although HP selection could be improved, the presented results look valid.\n\nI will thus increase my score to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers in most part agree that paper is well-written, is tackling an interesting problem and also the authors have engaged constructively during the reviewer feedback period and addressed the main concerns and questions. Please address the minor points raised by the reviewers in the final version.
Decision: Accept (Poster)