Robust Imitation Learning from Corrupted Demonstrations
Authors: Liu Liu
Ziyang Tang
Lanqing Li
Dijun Luo
Venue: ICLR 2022 Submitted (2022)
Keywords: Robust Estimation
Imitation Learning
Reinforcement Learning

Abstract: We consider offline Imitation Learning  from corrupted demonstrations where a constant fraction of data can be noise or even arbitrary outliers. Classical approaches such as Behavior Cloning assumes that demonstrations are collected by an presumably optimal expert, hence
may fail drastically when learning from corrupted demonstrations. We propose a novel robust algorithm by minimizing a Median-of-Means (MOM) objective which guarantees the accurate estimation of policy, even in the presence of constant fraction of outliers. 
Our theoretical analysis shows that our robust method in the corrupted setting enjoys nearly the same error scaling and sample complexity guarantees as the classical Behavior Cloning in the expert demonstration setting. Our experiments on continuous-control benchmarks validate that existing algorithms are fragile under corrupted demonstration while our method exhibits the predicted robustness and effectiveness.

Under review as a conference paper at ICLR 2022
ROBUST IMITATION LEARNING FROM CORRUPTED DEMONSTRATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider offline Imitation Learning from corrupted demonstrations where a constant fraction of data can be noise or even arbitrary outliers. Classical ap- proaches such as Behavior Cloning assumes that demonstrations are collected by an presumably optimal expert, hence may fail drastically when learning from cor- rupted demonstrations. We propose a novel robust algorithm by minimizing a Median-of-Mentt (MOM) objective which guarantees the accurate estimation of policy, even in the presence of constant fraction of outliers. Our theoretical analy- sis shows that our robust method in the corrupted setting enjoys nearly the same er- ror scaling and sample complexity guarantees the classical Behavior Cloning in the expert demonstration setting. Our experiments on aatiiuouu-contrre bench- marks validate that existing algorithms are fragile under corrupted demonstration while our method exhibits the predicted robustness and effectiveness.
INTRODUCTION
Recent years have witnessed the success of using autonomous agent to learn and adapt to complex tasks and environments in a range of applications such as playing games (e.g. Mnih et al., 2015; Sil- ver al., 2018; Vinyals al., 2019), autonomous driving (e.g. Kendall et al., 2019; Bellemare al., 2020), robotics (Haarnoja et al., 2017), medical treatment (e.g. Yu et al., 2019) and recommendation system and advertisement (e.g. Li et al., 2011; Thomas et al., 2017).
Previous success for sequential decision making often requires two key components: (1) careful design reward function that can provide the supervision signal during learning and (2) an unlimited number of online interactions with the real-world environment (or carefully designed simulator) to query new unseen region. However, in many scenarios, both components are not allowed. For ex- ample, it is hard to define the reward signal in uncountable many extreme situations in autonomous driving: and it is dangerous and risky to directly deploy learning policy on human to gather infor- mation in autonomous medical treatment (Yu et al., 2019). Therefore offline sequential decision making algorithm without reward signal is in demand.
Offline Imitation Learning (IL.) offers elegant way train intelligent agents for complex task without the knowledge of reward functions or using a simulator. Since the offline imitation learning does not interact with the environment, in order to guide intelligent agents correct behaviors, it is crucial to have high quality expert demonstrations. The well-known Behavior Cloning (BC) algorithm (Pomerleau, 1988) requires that the demonstrations given for training are all presumably optimal and it aims to learn that mapping from state to action from expert demonstration data set.
However in real world scenario, since the demonstration often collected from human, we cannot guarantee that all the demonstrations we collected have high quality. An human expert can make mistakes by accident or due to the hardness of complicated scenario (e.g., medical diagnosis). Fur- thermore, even an expert demonstrates successful behavior, the recorder or the recording system can have a chance to contaminate the data by accident or on purpose (c.g. Eykholt et al., 2018; Neff & Nagy, 2016).

---

Under review as a conference paper at ICLR 2022
300
Reward
100
Expert
-100
RBC corrupted
coruppted demos
-20
0.00
0.05
0.10
0.15
0.20
0.25
0.30
Fraction of Corruption
Figure 1: Reward vs. fraction of corruptions Lunar Lander environment. Shaded region represents standard deviation for 50 trials. We fix the sample size N 4000 for the demonstration data set, and vary the fraction of corruptions up to 30%. Our algorithm Robust Behavior Cloning (RBC) on corrupted demonstrations has nearly the same performance as BC on expert demonstrations (this is the case when c = 0), which achieves expert level. Also, it barely changes when grows larger. By contrast, the performance vanilla BC on corrupted demos fails drastically.
This leads to the central question of the paper:
Can the optimality assumption expert demonstrations be weakened tolerate arbitrary outliers under offline imitation learning settings?
More concretely, we consider corrupted demonstrations setting where the majority of the demon- stration data collected by an expert policy (presumably optimal), and the remaining data can be even arbitrary outliers (the formal definition is presented in Definition 2.1). This has great signifi- cance in many applications, such as automated medical diagnosis for healthcare (Yu al. (2019)) and autonomous driving (Ma et al., 2018), where the historical data (demonstration) is often com- plicated and noisy which requires robustness consideration.
However, the classical offline imitation learning approaches such Behavior Cloning (BC) fails drastically under this corrupted demonstration settings. We illustrated this phenomenon Figure 1. We use BC continuous control environment, and the performance of the policy learned by BC drops drastically as the fraction of corruptions increases the offline demonstration data set. How- ever, proposed algorithm Robust Behavior Cloning (Algorithm I)- resilient to corruptions in the offline demonstrations. The detailed experimental setup is included in Section We now summarize contributions follows.
1.1 MAIN CONTRIBUTIONS
(Algorithm) We consider robustness in offline imitation learning where we have corrupted demon- strations. Our definition for corrupted demonstrations significantly weakens the presumably opti- mal assumption on demonstration data, and can tolerate a constant e-fraction of state-action pairs to arbitrarily corrupted. We refer to Definition 2.1 for more precise statement.
To deal with this issue, propose novel algorithm Robust Behavior Cloning (Algorithm 1) for robust imitation learning. Our algorithm works in the offline setting, without any further interaction with the environment. The core ingredient of our robust algorithm is using novel median of means objective in policy estimation compared to classical Behavior Cloning. Hence, it's simple to implement, and computationally efficient.
(Theoretical guarantees) We analyze our Robust Behavior Cloning algorithm when there exists constant fraction of outliers the demonstrations under the offline setting. We show that our RBC achieves nearly the same emrr scaling and sample complexity compared to vanilla BC with expert
2

---

Under review as a conference paper at ICLR 2022
demonstrations. To this end, algorithm guarantees robustness to corrupted demonstrations no cost of statistical error. This is the content of Section 4.
(Empirical support) We validate the predicted robustness and show the effectiveness of our al- gorithm on different high-dimensional continuous control benchmarks- - the vanilla BC is fragile indeed with corrupted demonstrations, and our Robust Behavior Cloning achieves nearly the same performance compared to vanilla BC with expert demonstrations. This is the content of Section 5.
2
PROBLEM SETUP
2.1 REINFORCEMENT LEARNING AND IMITATION LEARNING
Markoy Decision Process and Reinforcement Learning. We start the problem setup by intro- ducing the Markov decision process (MDP). An MDP M (8, AS,A,r, P, Ma: 7) consists of state space S, an action space A. an unknown reward function r S x A + [0, Rmax]. an unknown transition kernel P S X A + (S)) initial state distribution μl (SS), and discounted factor E (0, 1). We use A to denote the probability distributions on the simplex.
An agent acts in MDP following policy T(-(s). which prescribes distribution over the action space A given each state S. Running the policy starting from the initial distribution yields a stochastic trajectory T == (s,, at, I')) ssssos where St, a Fr represent the state, action, re- ward at time & respectively, with a, (-)(s)) and the next state S1+1 follows the unknown transition kernel 1 P(+|s, az). We denote Px. E ASS A) as the marginal joint stationary distribution for state, action at time step 6, and we define Pr (1 7) 2i 7 Pa.t visitation distribution for policy æ. For simplicity, we reuse the notation P (s) = Soea Par (s, a) to denote the marginal distribution over state.
The goal of reinforcement learning is to find the best policy æ to maximize the expected cumulative return J, = -- /ا== r'r.]. Common RL algorithms (e.g.. please refer to Szepesvári (2010)) requires online interaction and exploration with the environments. However, this is prohibited in the offline setting.
Imitation Learning. Imitation learning (IL.) aims obtain policy mimic expert's behavior with demonstration data set = (S;, a;) a:) where N is the sample size of DD Note that we do need any reward signal. Tradition imitation learning assumes perfect (or near-optimal) expert demonstration - for simplification we assume that each state-action pair (s;, a;) is drawn from the joint stationary distribution of an expert policy Tg:
(s a.) PaR
Learning from demonstrations with or without online interactions has a long history (e.g.. Pomerleau (1988); Ho & Ermon (2016)). The goal of offline IL to learn a policy f AD) through an IL algorithm A, given the demonstration data set D, without further interaction with the unknown true transition dynamic
Behavior Cloning, The Behavior Cloning (BC) is the well known algorithm (Pomerleau, 1988) for IL which only uses offline demonstration data without any interaction with the environment. More specifically, BC solves the following Maximum Likelihood Estimation (MLE) problem, which minimizes the average Negative Log-L.ikelihodd (NLL) for all samples in offline demonstrations D:
BCC
arg min xell
Σ - (lo((T(ass))
(s.0)ED
Recent works (Agarwal et al., 2019; Rajaraman et al., 2020; Xu et al., 2021) have shown that BC optimal under the offline setting, and can only be improved with the knowledge of transition dynamic P in the worst case. Also, another line of research considers improving BC with further online interaction of the environment (Brantley et al., 2019) or actively querying an expert (Ross et al., 201 I; Ross & Bagnell, 2014).
3

---

Under review as a conference paper at ICLR 2022
2.2 LEARNING FROM CORRUPTED DEMONSTRATIONS
However, it is sometimes unrealistic to assume that the demonstration data set is collected through a presumably optimal expert policy. In this paper, we propose Definition 2.1 for the corrupted demonstrations, which tolerates gross corruption or model mismatch in offline data set.
Definition 2.1 (Corrupted Demonstrations). Let the state-action pair (s,: a)) drawn from the joint stationary distribution of a presumably optimal expert policy gg. The corrupted demonstration data 'D are generated by the following process: an adversary can choose an arbitrary e-fraction (c < 0.5) of the samples [N] and modifies them with arbitrary values. We note that a constant independent of the dimensions of the problem. After the corruption, we use DD to denote the corrupted demonstration data set.
This corruption process can represent gross corruptions or model mismatch the demonstration data set. To the best of our knowledge, Definition 2.1 is the first definition for corrupted demonstrations in imitation learning which tolerates arbitrary corruptions.
In the supervised learning, the well-known Huber's contamination model (Huber (1964)) considers sid
(x. v) ~ (1 [1-e) where æ E TR the explanatory variable (feature) and y E IR is the response variable. Here, P denotes the authentic statistical distribution such Normal mean estimation or linear regression model, and Z denotes the outliers.
Dealing with corrupted and y in high dimensions has long history in the robust statistics com- munity (e.g. Rousseeuw, 1984; Chen et al., 2013; 2017; Yin et al., 2018). However, it's only until recently that robust statistical methods can handle constant e-fraction (independent of dimensional- ity IR") of outliers in æ and y (Klivans al., 2018; Prasad et al., 2020; Diakonikolas al., 2019; Liu et al., 2019; 2020; Shen & Sanghavi, 2019; Lugosi & Mendelson, 2019; Lecué & Lerasle, 2020; Jalal al., 2020). We note that in Imitation Learning, the data collecting process for the demonstrations does not obey i.i.d. assumption in traditional supervised learning due to the temporal dependency.
Notations, Throughout this paper, we use {citi=1.2.3 to denote the universal positive constant. We utilize the big-O notation (() = (gg()) to denote that there exists a positive constant 0j and a natural number no such that, for all n 2 no, we have fn) S cig(n).
OUR ALGORIHTMS
is well known that the Median-of -ffaan-n--- (MOM) estimator achieves sub- GobuGasssian concentration bound for one-dimensional mean estimation even though the underlying distribution only has sec- ond moment bound (heavy tailed distribution) (interested readers are referred to textbooks such as Nemirovsky & Yudin (1983); Jerrum et al. (1986); Alon et al. (1999)).
The vanilla MOM estimator for one-dimensional mean estimation works like following: (1) ran- domly partition N samples into M batches; (2) calculates the mean for each batch; (3) outputs the median of these batch mean. Very recently, MOM estimators are used for high dimensional robust regression (Brownlees et al., 2015; Hsu & Sabato, 2016) by applying MOM estimator on the loss function of empirical risk minimization process.
3.1 ROBUST BEHAVIOR CLONNNGG
Motivated by using MOM estimators on the loss function, we propose Definition 3.1 which uses a MOM objective to handle arbitrary outliers in demonstration data set (s. E D.
Definition 3.1 (Robust Behavior Cloning). We split the corrupted demonstrations D into M batches
1. The Robust Behavior Cloning solves the following randomly': { with the batch size < ze. optimization
RBC
arg min max median nell n' e'lll 15J5M
Without loss of generality, we assume that M exactly divides the sample size N, and h is the batch
M
size.
4

---

Under review as a conference paper at ICLR 2022
Algorithm Robust Behavior Cloning.
Input: Corrupted demonstrations D
2: Output: Robust policy RRBC
3: Initialize и and I².
4: for f- t 1, do
5: Randomly partition D M batches with the batch size b I Se
6: For each batch [M]] calculate the loss (TT) (xx)) by eq. (4).
7: Pick the batch with median loss within batches
median (L)( - (T()) ISJMM
and evaluate the gradient for and x' using back mack-propagation on that batch (i) perform gradient descent on n.
(ii) perform gradient ascent n².
8: end for
9: Return: Robust policy RRBC I..
where the loss function (T) is the average Negative Likeliiod in the batch By:
1 Σ - -log(T(a)s)).
(T(
(4)
(e.c)EB,
The workhorse of Definition 3.1 is eq. (3), which uses novel variant of Median-of-Mean (MOM) tournament procedure (Le Cam (2012); Lugosi & Mendelson (2019); Lecué & Lerasle (2020); Jalal et al. (2020)). In eq. (4), we calculate the average Negative Log-Likelihood (NLL) for a single batch, and RBC is the solution of min-max formulation based the batch loss (T). Though our algorithm minimizes the robust version of NLL., we do not utilize the traditional iid assumption in the supervised learning.
To gain some intuition of the formulation eq. (3), if we replace the median operator by the mcan operator, then RBC equivalent BC which just minimizes the empirical average of Negative Log-Likelihhod. This is due to the linearity of using the mean operator. However, this is not robust corrupted demonstration. Hence, we use the median operator on the loss function.
The intuition behind solving this min-max formulation is that the inner variable n' needs to get close тE maximize the difference of loss function, and the outer variable also need to get close to Tg. Hence we can guarantee that RBBC will be close to Tg. In Section 4, we show that under corrupted demonstrations, RRBC in eq. (3) has the same error scaling and sample complexity compared to
In Section 4, we provide rigorous statistical guarantees for Definition 3.1. However, the objective function eq. (3) in Definition 3.1 is not convex (in general), hence we use Algorithm 1 as a compu- tational heuristic to solve it.
In each iteration of Algorithm 1, we randomly partition the demonstration data set D into M batches, and calculate the loss (x( - (=') by eq. (4). We then pick the batch BMed with the median loss, that batch. We use gradient descent on for the arg min part and
and evaluate the gradient gradient ascent on n' for the arg max part. In Section 5, we empirically show that this gradient- based heuristic Algorithm is able to minimize this objective and has good convergence properties. As for the time complexity, when using back prockpppppattionn on one batch of samples, our RBC incurs overhead costs compared to vanilla BC, in order to evaluate the loss function for all samples via forward propagation.
5

---

Under review as a conference paper at ICLR 2022
4 THEORETICAL ANALYSIS
In this section, we provide theoretical guarantees for our RBC algorithm. Since our method (Defi- nition 3.1) directly estimates the conditional probability ([]ss) over the offline demonstrations, theoretical analysis provides guarantees on Eg-p.g ||* the total variation
TE ( which upper bounds compared to T under the expectation of Psg- The ultimate goal of the learned policy is to maximize the expected cumulative return, thus we then provide an upper bound for the sub-optimality Jrg JSRBC.
We begin the theoretical analysis by Assumption 4.1, which simplifies our analysis and is common in literature (Agarwal al., 2019; 2020). By assuming that the policy class II discrete, our upper bounds depend on the quantity log( //N, which matches the error rates and sample complexity for using BC with expert demonstrations (Agarwal et al., 2019; 2020).
Assumption 4.1. We assume that the policy class II is discrete, and realizable, i.e., Te II.
We first present Theorem 4.1, which shows that minimizing the MOM objective via eq. (3) guaran- tees the closeness of robust policy optimal policy in total variation distance.
Theorem 4.1. Suppose we have corrupted demonstration data set 'D with sample size N from Definition 2.1, and there exists constant corruption ratio 0.5. Under Assumption 4.1, let T to
be the outpul objective value with RRBC in the optimization eq. (3) with the batch size b S L 3e then
with probability at least 61,, we have
-0(08 log (1) [0g((1110) N
E B
|RBB
TE((|s) 0
+T)
(5)
The proof is collected in Appendix A. We note that the data collection process does not follow the iid assumption, hence we use martingale analysis similar to (Agarwal et al., 2019; 2020). The first part of eq. (5) is the statistical error [T/() The second part is the final objective value in the optimization eq. (3) which includes parts the first part scales with O ( ()), which is equivalent to the fraction of corruption Oee). The second part is the sub-optimality gap due to the solving the non-convex optimization.
Our main theorem - Theorem 4.1 guarantees that a small value of the final objective implies an accurate estimation of policy and hence we can certify estimation quality using the obtained final value of the objective.
Next, we present Theorem 4.2, which guarantees the reward performance of the learned robust policy @RÉC.
Theorem 4.2. Under the same setting as Theorem 4.1, we have
Jan Janne SO 0o
1 (1 7)2
log II (0) +
(6)
N
with probability at least 618.
The proof is also collected in Appendix A. We note that the error scaling and sample complexity of Theorem 4.1 and Theorem 4.2 matches the vanilla BC with expert demonstrations (Agarwal et al., 2019; 2020).
Remark 4.1. The quadratic dependency on the effective horizon (1-2332 in the discounted setting or H² in the episodic setting) is widely known as the compounding error or distribution shift in literature, which is due to the essential limitation of offline imitation learning setting. Recent work (Rajaraman et al., 2020; Xu et al., 2021) shows that this quadratic dependency cannot be improved without any further interaction with the environment or the knowledge of transition dynamic P. Hence BC is actually optimal under no-interaction setting. Also, a line of research considers im- proving BC by further online interaction with the environment even active query of the experts (Ross et al., 2011; Brantley et al., 2019; Ross Bagnell, 2014). Since our work, as a robust coun- terpart of BC, focuses the robustness to the corruptions in the offline demonstrations setting, can be naturally used in online the online setting such as DAGGER (Ross et al., 201 and Brantley al. (2019).

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTS
In this section, we study the empirical performance of our Robust Behavior Cloning. We eval- uate the robustness of Robust Behavior Cloning on several continuous control benchmarks simu- lated by PyBullet Coumans & Bai (2016) simulator: HopperBulletEav-vo) Walker2DBulletEnvww HalsCheetahBullleEnvwww and AntBulletEnv-vo Actually, these tasks have true reward function al- ready in the simulator. We will use only state observation and action for the imitation algorithm, and we then use the reward to evaluate the obtained policy when running in the simulator.
For each task, we collect the presumably optimal expert trajectories using pre-trained agents from Standard Baselines3'. In the experiment, we use Soft Actor-Critic (Haarnoja et al. (2018)) in the Standard Baselines3 pre-trained agents, and we consider it to be an expert.
For the continuous control environments, the action space are bounded. Hence we generate cor- rupted demonstration data set D follows: first randomly choose fraction of samples, and corrupt the action to the boundary (normally -1 or +1). We note that Definition 2. allows for arbi- trary corruptions, and choose these outliers' action since it has the maximum effect, and cannot be easily detected.
We compare our RBC algorithm (Algorithm 1) to a number of natural baselines: the first baseline directly using BC on the corrupted demonstration D without any robustness consideration. The second one is using BC on the expert demonstrations with the same sample size. In different settings, we fix the policy network as 2 hidden layer feed-forward Neural Network of size (500, 500} with ReLU activation, which is standard in the baselines.
5.1 CONVERGENCE OF OUR ALGORITHM
We illustrate the convergence and the performance of algorithm support our theoretical analy- sis. We track the performance metric of different algorithms vs. epoch number in the whole training process. More specifically, we then evaluate current policy in the simulator for 20 trials, and obtain the mean and standard deviation of cumulative reward for each epoch. This metric corresponds to theoretical bounds in Theorem 4.2.
We focus on four continuous control environments, where the observation space has dimensions around 30, and the action space has boundary [-1, 1]. We fix the sample size as 60000, and vary the corruption fraction to be 10%, 20%. Figure 2 validates our theory that our Robust Behavior Cloning nearly matches the performance of BC on expert demonstrations for different environments and corruption ratio.
5.2 PERFORMANCE UNDER DIFFERENT SETUPS
This is the experiment we have shown in Section 1. In the Lunar Lander control environment, we fix the sample size N 4000, and then vary the fraction of corruptions As expected, Figure shows that our RBC is resilient to constant-fractio 30%, and achieves nearly the same performance as the BC on expert demonstrations. In contrast, directly using BC corrupted demonstrations obtains worse reward performance as the fraction of outliers grows.
of outliers in the demonstrations ranging from 0 to
6 DISCUSSIONS
6.1 RELATED WORK
Imitation Learning. Behavior Cloning (BC) the most widely-used imitation learning algorithm (Pomerleau, 1988; Osa et al., 2018) due to its simplicity, effectiveness and scalability, and has been widely used in practice. From a theoretical viewpoint, it has been showed that BC achieves infor- mational optimality in the offline setting (Rajaraman al., 2020) with further online interactions or the knowledge of the transition dynamic P.
TThe pre-trained agents were cloned from the following repositories: httpa: htt://gttttt thub. DiR--MM/stabl baaee nea3, https://gi thub. htm.///RRRMM/---- nea3-200.
7

---

Under review as a conference paper at ICLR 2022
With online interaction, there's line of research focusing improving BC in different scenarios for example, Ross et al. (2011) proposed DAgger (Data Aggregation) by querying the expert policy in the online setting. Brantley et al. (2019) proposed using an ensemble of BC as uncertainty measure and interacts with the environment to improve BC by taking the uncertainty into account, without the need query the expert. Very recently, (Xu et al., 2021; Rajaraman et al., 2021) leveraged the knowledge of the transition dynamic P to eliminate compounding error/distribution shift issue in BC.
Besides BC, there are other imitation learning algorithms: Ho & Ermon (2016) used generative ad- versarial networks for distribution matching learn reward function; Reddy et al. (2019) provided a reinforcement learning framework to deal with imitation learning by artificially setting the re- ward; Chasemipour et al. (2020) unified several existing imitation learning algorithm as minimizing distribution divergence between learned policy and expert demonstration, just to name a few.
Offline RL. Reinforcement learning leverages the signal from reward function to train the policy. Different from IL, offline RL often does not require the demonstration to be expert demonstration (e.g. Fujimoto et al., 2019; Fujimoto & Gu, 2021; Kumar et al., 2020) (interested readers are referred to (Levine et al., 2020)), and even expects the offiin data with higher coverage for different sub- optimal policies (Buckman et al., 2020; Jin et al., 2021; Rashidinejad et al., 2021). Behavior-agnostic setting (Nachum et al., 2019; Mousavi et al., 2020) even does not require the collected data from single policy.
The closest relation between offline RL and IL is the learning of stationary visitation distribution, where learning such visitation distribution does not involve with reward signal, similar to IL. A line of recent research especially for off off-policy evaluation tries to learn the stationary visitation distribution of given target policy (e.g. Liu et al., 2018; Nachum et al., 2019; Tang et al., 2020; Mousavi et al., 2020; Dai et al., 2020). Especially Kostrikov et (2020) leverages the off-policy evaluation idea to IL area.
Robustness in IL and RL. There are several recent papers consider corruption- robusst in either RL or II.. In RI., Zhang al. (2021b) considers that the adversarial corruption may corrupt the whole episode in the online RI. setting while more recent one (Zhang et al., 2021a) considers offline RI. where e-fraction of the whole data set can be replaced by the outliers. However, the dependency scales with the dimension in Zhang et al. (2021a), yet can be a constant in this paper for robust offline IL. Many other papers consider perturbations, heavy tails, or corruptions in either reward function (Bubeck et al., 2013) or in transition dynamic (Xu & Mannor, 2012; Tamar et al., 2014; Roy et al., 2017).
The most related papers follow similar setting of robust II. are (Wu et al., 2019; Tangkaratt et al., 2020; 2021; Brown et al., 2019; Sasaki & Yamashina, 2020), where they consider imperfect or noisy observations in imitation learning. However, their algorithms cannot handle outliers in the demon- strations, and (Wu et al., 2019; Tangkaratt et al., 2020; 2021) require additional online interactions with the environment. Our algorithm achieves robustness guarantee from purely offline demonstra- tion, without the potentially costly or risky interaction with the real world environment.
6.2 SUMMARY AND FUTURE WORKS
In this paper, we considered the corrupted demonstrations issues in imitation learning, and pro- posed a novel robust algorithm, Robust Behavior Cloning, to deal with the corruptions in offline demonstration data set. The core technique is replacing the vanilla Maximum Likelihood Estima- tion with Median-of-Means (MOM) objective which guarantees the policy estimation and reward performance in the presence of constant fraction of outliers. Our algorithm has strong robustness guarantees and works well in practice.
There are several avenues for future work: since our work focuses on the corruption in offline data set, any improvement in online imitation learning which utilizes Behavior Cloning would benefit from the corruption-robustees guarantees by our offline Robust Behavior Cloning. Also, it would also be of interest apply our algorithm for real-world environment, such automated medical diagnosis and autonomous driving.
8

---

Under review as a conference paper at ICLR 2022
3000
2302
2500
2383
Expert
Expert
RBC on corrupted data corrupted data
1500
RBC comupted cata
BC comppped cata
2000
30
300
125
130
275
200
50
200
123
130
175
200
Epochs
Epontts
(a) Hopper environment with 0.1.
(b) Hopper environment with 0.2.
2300
3300
-2000
-1002
100 Epocho
135
150
175
200
300 Epochs
120
(c) HalfCheetah environment with 0.1.
(d) HalfCheetah environment with 0.2.
2500
2000
2002
3900
1502
2300
Epocho
Epochs
(c) Walker2D environment with e 0.1.
(f) Walker2D environment with c 0.2.
2200
2502
2300
3500
300
502
2000
1.25
120
375
230
320
325
150
175
200
Epochs
(g) Ant environment with 0.1.
(h) Ant environment with 0.2.
Figure 2: Offline Imitation Learning on four different continuous control tasks with demonstration data of size 60000. We vary the corruption ration 10%, 20%. For every 5 epochs, we evaluate the current policy in the environment for 20 trials, and the shaded region represents the standard deviation. Vanilla BC on corrupted demonstrations fails converge expert policy. Using the robust counterpart Algorithm on corrupted demonstrations has good convergence properties. Sur- prisingly, our RBC on corrupted demonstrations has nearly the same reward performance of using BC on expert demonstrations.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Alckh Agarwal, Nan Jiang, S. Kakade, and Wen Sun. Reinforcement learning: rithms. 2019.
Theory and algo-
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complex- ity and representation learning of low rank mdps. In Advances in Neural Information Processing Systems, volume 33, pp. 20095-201000 2020.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
Mare Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos Machado, Sub- hodeep Moitra, Sameera S Ponda, and Ziyu Wang. Autonomous navigation of stratospheric bal- loons using reinforcement learning. Nature, 588(7836):77-82, 2020.
Kianté Brantley, Wen Sun, and Mikael Henaff. Disagreement-regullaaiied imitation learning. In International Conference on Learning Representations, 2019.
Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learning, pp. 783-792. PMLR, 2019.
Christian Brownlees, Emilien Joly, and Gábor Lugosi. Empirical risk minimization for heavy-tailed losses. The Annals of Statistics, 43(6):2507-25533 2015.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Trans- actions on Information Theory, (911))77111777777 2013,
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed- dataset policy optimization. In International Conference on Learning Representations, 2020.
Yudong Chen, Constantine Caramanis, and Shie Mannor. Robust sparse regression under adversarial corruption. In International Conference on Machine Learning, pp. 774-782, 2013.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning adversarial set- tings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems. 1(2):44, 2017.
Erwin Coumans and Yunfei Bai. Pybullet, a python module for physics simulation for games, robotics and machine learning. 2016.
Bo Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Coindice: Off-policy confidence interval estimation. In Advances in Neural Information Processing Systems, 2020.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stew- art. Sever: A robust meta-algorithm for stochastic optimization. In International Conference on Machine Learning, pp. 1596-1606, 2019.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1625-1634, 2018
Scott Fujimoto and Shixiang Shane Gu. minimalist approach to offline reinforcement learning. arXiv preprint arXiv:2106.068800 2021.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 0052-2062. PMLR, 2019.
Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimization perspective on imitation learning methods. In Conference on Robot Learning, pp. 1259-1277. PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2022
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep anergy-based policies. In International Conference on Machine Learning, pp. 1352-1361. PMLR. 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural information processing systems, 29:4565-4573, 2016.
Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. The Journal of Machine Learning Research, 17(1):543-522, 2016.
J. Huber. Robust estimation of a location parameter. Annals of Mathematical Statistics, 35: 492-518, 1964.
Ajil Jalal, Liu Liu, Alexandros G Dimakis, and Constantine Caramanis. Robust compressed sensing using generative models. Advances in Neural Information Processing Systems, 2020.
Mark R Jerrum, Leslie Valiant, and Vijay Vazirani. Random generation of combinatorial struc- tures from uniform distribution. Theoretical Computer Science, 43:169-188, 1986.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International Conference on Machine Learning, pp. 5084-5096. PMIR, 2021.
Alex Kendall, Jeffrey Hawke, David Janz, Przemyslaw Mazur, Daniele Reda, John-Mark Allen, Vinh-Dieu Lam, Alex Bewley, and Amar Shah. Learning drive in day. In 2019 International Conference on Robotics and Automation (ICRA). pp. 8248-8254, IEEE, 2019.
Adam Klivans, Pravesh K Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regres- sion. In Conference On Learning Theory, pp. 1420- 1430. PMLR, 2018.
llya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribution matching. In International Conference on Learning Representations, 2020.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006. 200.29006.04779, 2020.
Lucien Le Cam. Asymptotic methods in statistical decision theory. Springer Science & Business Media, 2012.
Guillaume Lecué and Matthicu Lerasle. Robust machine learning by median-of-means: theory and practice. The Annals of Statistics, 48(2):906-931, 2020.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems, arXiv preprint arXiv:2005.01643 2020.
Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of contextual- bandit-based news article recommendation algorithms. In Proceedings of the 4th International Conference on Web Search and Data Mining (WSDM), pp. 297-306, 2011.
Liu Liu, Tianyang Li, and Constantine Caramanis. High dimensional robust m-estimation: Arbitrary corruption and heavy tails. arXiv preprint arXiv: 1901. 0083370777,7.. 2019.
Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis. High dimensional robust sparse regression. In International Conference Artificial Intelligence and Statistics, pp. 411-421. PMLR, 2020.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off- off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5356- 5366, 2018
Gabor Lugosi and Shahar Mendelson. Risk minimization by median-of-mean tournaments. Journal of the European Mathematical Society, 22(3):925 2019.

---

Under review as a conference paper at ICLR 2022
Xiaobai Ma, Katherine Driggs Campbel,, and Mykel J Kochenderfer. Improved robustness and safety for autonomous vehicle control with adversarial reinforcement learning. In 2018 IEEE Intelligent Vehicles Symposium (IV), pp. 1665-1671. IEEE, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-5333 2015.
Ali Mousavi, Lihong Li, Qiang Liu, and Denny Zhou. Black-box off-policy estimation for infinite- horizon reinforcement learning. In International Conference on Leurning Representations, 2020.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pp. 2318-23322 2019.
Gina Neff and Peter Nagy. Automation, algorithms, and politics- talking bots: Symbiotic agency and the case of tay. International Journal of Communication, 10:17, 2016.
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, Jan Peters, et al. An algorithmic perspective on imitation learning. Foundations and Trends& in Robotics, 7(1-2): 1-179, 2018.
D. Pomerleau. Alvinn: An autonomous land vehicle in a neural network. In Advances in Neural Information Processing Systems, 1988.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estima- tion via robust gradient estimation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(3):601-62) 2020.
Nived Rajaraman, Lin Yang, Jiantao Jiao, and Kannan Ramchandran. Toward the fundamental limits of imitation learning. Advances Neural Information Processing Systems, 33, 2020.
Nived Rajaraman, Yanjun Han, Lin F Yang, Kannan Ramchandran, and Jiantao Jiao. Provably breaking the quadratic error compounding barrier in imitation learning, optimally. arXiv preprint arXiv:2102. 12948, 2021.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: tale of pessimism. arXiv preprint arXiv:2103. 12021, 2021.
Siddharth Reddy, Anea D Dragan, and Sergey Levine. Sqil: Imitation learning via reinforcement learning with sparse rewards. In International Conference on Learning Representations, 2019.
Stephane Ross and Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv:1406.573 2014.
Stéphane Ross, Geoffrey J. Gordon, and J. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In AISTATS, 2011.
Peter Rousseeuw. Least median of squares regression. Journal of the American statistical associ- ation, 79(388):871-88,, 1984.
Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. In Advances in Neural Information Processing Systems, volume 30, 2017.
Fumihiro Sasaki and Ryota Yamashina. Behavioral cloning from noisy demonstrations. In Interna- tional Conference on Learning Representations, 2020.
Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss mini- mization. In International Conference on Machine Learning, pp. 5739-5748. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2022
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 362(6419):1140- 1144, 2018.
Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelli- gence and machine learning, 4(1):1-103, 2010.
Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approximation. In International conference machine learning, pp. 181-189. PMLR, 2014.
Ziyang Tang, Yihao Feng, Lihong Li, Dengyong Zhou, and Qiang Liu. Doubly robust bias reduction in infinite horizon off aff-policy estimation. In International Conference on Learning Representations (ICLR), 2020.
Voot Tangkaratt, Bo Han, Mohammad Emtiyaz Khan, and Masashi Sugiyama. Variational imitation learning with diverse-quality demonstrations. In International Conference on Machine Learning, pp. 9407-9417. PMLR, 2020.
Voot Tangkaratt, Nontawat Charoenphakdee, and Masashi Sugiyama. Robust imitation learning from noisy demonstrations. In International Conference Artificial Intelligence and Statistics, pp. 298-306. PMLR, 2021.
Philip S. Thomas, Georgios Theocharous, Mohammad Ghavamzadeh, Ishan Durugkar, and Emma Brunskill. Predictive off-policy policy evaluation for nonstationary decision problems, with appli- cations to digital marketing. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 4740-4745, 2017.
A. Tsybakov. Introduction to nonparametric estimation. In Springer series statistics, 2009.
Sara van de Geer. Empirical Processes in M-estimation, volume Cambridge university press, 2000.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamnekki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)350-354) 2019.
Yueh-Hua Wu, Nontawat Charoenphakdee, Han Bao, Voot Tangkaratt, and Masashi Sugiyama. Imi- tation learning from imperfect demonstration. In International Conference on Machine Learning, pp. 6818-6827. PMLR, 2019.
Huan Xu and Shie Mannor. Distributionally robust markov decision processes. Mathematics of Operations Research, 37(2):288 1000220880000000 2012.
Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments for reinforce-
ment learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Byzantine- robust distributed learning: Towards optimal statistical rates. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5650-5659. PMLR, 10-15 Jul 2018.
Chao Yu, Jiming Liu, and Shamim Nemati. Reinforcement learning in healthcare: A survey. arXiv
preprint arXiv: 1900008796 2019.
Tong Zhang. From e-entropy kl-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 34(5):2180-2) 2006.
Xuezhou Zhang, Yiding Chen, Jerry Zhu, and Wen Sun. Corruption-robust offline reinforcement learning. arXiv preprint arXiv:2106. 06630, 2021a.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust policy gradient against strong data corruption. arXiv preprint arXiv:2/02.0553 2021b.
13

---

Under review as a conference paper at ICLR 2022
A PROOFS
The analysis of maximum likelihood estimation is standard in i.id. setting for the supervised learn- ing setting (van de Geer, 2000). In our proofs of the robust offliee imitation learning algorithm, the analysis for the sequential decision making leverages the martingale analysis technique from (Zhang, 2006; Agarwal et al., 2020).
Our Robust Behavior Cloning (Definition 3.1) solves the following optimization
RBC
arg min max median (4,(T) - (z
π
xell xell ISJSM
where the loss function (T) is the average Negative Log-L.kellihod in the batch By:
(TT)=
Σ (s.
lag(((())))..
(8)
This can be understood as robust counterpart for the maximum likelihood estimation in sequential decision process.
With slight abuse of notation, we use x; and y: denote the observation and action, and the underlying unknown expert distribution is yi ~ p(-[a)) and p(y|z) = (x, y). Following Assump-
tion 4.1, we have the realizable f* FF and the discrete function class satisfies [F] < co.
Let 'D denote the data set and D' denote a tangent sequence {>/, v/] The tangent sequence defined as x (x V1 and yf ~ p(-|z))). Note here that x follows from the distribution 9r, and depends on the original sequence, hence the tangent sequence independent conditional on D.
For this martingale process, we first introduce a decoupling Lemma from Agarwal et al. (2020).
Lemma A.1. [Lemma 24 in Agarwal et al. (2020)] Let D be a dataset, and let DD' be tangent se- quence. Let ((SD)) En Φ(ʃ, (x, 3)) be any function which can be decomposed additively across samples in D. Here, & any function of f and sample (x,y). Let f F(D) be any estimator taking the dataset as input and with range F. Then we have
ED exp (T(F.D)- log Ep exp(T(f. log log [FI]] < 1.
Then present Lemma which upper bounds the TV distance via loss function closely related to KL divergence. Such bounds for probabilistic distributions are discussed extensively literature such Tsybakov (2009).
Lemma A.2. [Lemma 25 in Agarwal el al. (2020)) For any two conditional probability densities fi, and any state distribution 2 A(X) have
Ex (x, f2(x,, S -2 Eew exp (-1 log
f2(2, y) [1(,.
A.1 PROOF OF THBOREM 4.1
With these Lemmas in hand, we are now equipped to prove our main theorem (Theorem 4.1), which guarantees the solution RRBC of eq. (3) is close to the optimal policy mg in TV distance.
Theorem A.1 (Theorem 4.1). Suppose we have corrupted demonstration data set D with sample
size N from Definition 2.1, and there exists constant corruption ratio < 0.5. Under Assump-
14

---

Under review as a conference paper at ICLR 2022
tion 4.1, let T to be the output objective value with RBCC in the optimization eq. (3) with the batch
size b S 1. then with probability at least - c1ô, we have
( |ogg [10 +T)
E Propp
|RBC TE(-|S)[TTV =0
Proof of Theorem 4.1. En route to the proof of Theorem 4.1, keep using the notations in Lemma A.I and Lemma A.2, where the state observation is z, the action is y, and the discrete function class is F.
Similar Agarwal al. (2020), we first note that Lemma A.1 can be combined with a simple Chernoff bound to obtain an exponential tail bound. With probability at least 1 C we have
- log Ep exp(T -r( log [F] (16).
Our proof technique relies on lower bounding the LHS of eq. (9). and upper bounding the RHS eq. (9).
Let the batch size b S 3/ which is constant in Definition 3.1, then the number of batches M >
NeN such that there exists at least 66% batches without corruptions.
In the definition of RBC (Definition 3.1), we solve
RBC arg min max median r'ell I5J5M
(10)
Notice that since TE is feasible solution of the inner maximization step eq. (10), choose n' тв. Now we consider the objective function which is the difference of Negative Log-Likelihood between ff and f³, i... (f) (f*), defined in eq. (4) where
(T) b Σ log(T(a)s)).
(s,a)e
Hence, we choose ['f,, D) in Lemma A.1 as
N
f' V.)
D)(f
Σ
log
b
f(x,, ys)
iEB
N
(log fr,, vi) - log (x,, (x,, v)))
2b
B
which is the difference of Negative Log-Likelihood
evaluutee evaluated single batch By.j E [M]. This is actually the objective function on a single batch appeared eq. (3).
Lower bound for the LHS of eq. (9). We apply the concentration bound eq. (9) for such uncor- rupted batches, hence the majority of all batches satisfies eq. (9). For those batches, the LHS of
15

---

Under review as a conference paper at ICLR 2022
eq. (9) can be lower bounded by the TV distance according to Lemma A.2.
flot, v/). )
N Σ
log EDD
exp
log
(D
2
iEB,
(
N
- log (w,
log B Bezggr exp
Me, v)
BBB,
(
N
TV' "
E Ex - (2,
(11)
2h
BEB,
where (i) follows from the independence between f and D' due to the decoupling technique, and (ii) follows from Lemma A.2, which is an upper bound of the Total Variation distance.
Upper bound for the RHS of eq. (9). Note that the objective the median of means of each batches and f is one feasible solution of the inner maximization step eq. (10). Since r is the output objective value with $RBC in the optimization eq. (3), this implies that Med (T) (med S T for the median batch BMedd which is equivalent to -ea (f, D) s NT/2.
Hence for the median batch BMed, the RHS of eq. (9) be upper bounded by
-T D) log F (1gg111)) < log [F| log(1/6) NT/2.
(12)
Putting together the pieces eq. (11) and eq. (12) for BMed, we have
TE(-1>) -o with probability at least cj8.
((00((17) (Lo8(1F//0) +r)
E Ea-poy (RBC(-Is)
N
A.2 PROOF OF THEOREM 4.2
With the supervised learning guarantees Theorem 4.1 in hand, which provides an upper bound for Ex-pen || || =g(+|s) reward for BBC This bound directly corresponds to the reward performance a policy.
now able to present the suboptimality guarantee of the
Theorem A.2 (Theorem 4.2). Under the same setting as Theorem 4.1, we have
1 JAg JJRBC 5 (0 V N
Tog([Fl/8)
+
with probability at least c18.
Proof of Theorem 4.2. This part is similar to Agarwal et al. (2019), and we have
(1 (1mE -JRBCC) Exnpey Ba-TE(
A (s, a)
< ? V Eamping || (.Is) (=))))
v Barepr ||FBBC (
16

---

Under review as a conference paper at ICLR 2022
where we use the fact that sups,a,7 [A (s. always bounded between and
$ I-q for the advantage function and the reward is
Combining Theorem 4.1, we have
{
JAB JznBC so
1
log( F1/6)
+
(1-
N
with probability at least cjó.
17


Reviews:
[{"review_id": "uba9o3cCmM0", "reviewer": "Reviewer_tcU1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strength:\n\nThe authors provide theoretical and empirical analysis that the proposed algorithm is simple yet effective.\n\nWeakness:\n\nIn the theorems, the authors assume that a small enough $\\epsilon$ exists. However, with very small $\\epsilon$, BC also performs well. It will be a stronger statement when the $\\epsilon$ is included in the bounds, not assumption.\n\nI think the previous work [1] is very similar to this work. This paper also proposes a robust (offline) IL algorithm from the noisy expert demonstration. Because this work is applicable in the offline, some discussions or empirical comparisons should be provided.\n\n[1] Sasaki, Fumihiro, and Ryota Yamashina. \"Behavioral Cloning from Noisy Demonstrations.\" ICLR. 2021.\n", "summary_of_the_paper": "This paper proposes the definition of corrupted demonstrations and a new robust algorithm for offline imitation learning from corrupted demonstrations. The main idea to guarantee the robustness is median-of-means (MOM), which is used for high-dimensional robust regression. \nThe authors propose an optimization formula based on MOM. The proposed algorithm, named robust behavior cloning (RBC), solves the min-max-median optimization to train two policies $\\pi$ and $\\pi’$.\n\nUnder the assumption that the policy class is discrete, two meaningful theorems are provided. The first theorem shows that the policy obtained from RBC is close to the expert policy with high probability. The second theorem shows the degree of suboptimality measured by the difference between the expected return of the policy obtained from RBC and the expert policy.\n\nFinally, the authors provide empirical results on two continuous control benchmarks. In both domains, the proposed algorithm achieves competitive performance with BC on expert demos and outperforms BC on corrupted demonstrations by a large margin.\n", "summary_of_the_review": "At least one highly related work is missed and the statements of the theorem require small $\\epsilon$.\n\nHowever, I think the proposed algorithm based on MOM and theoretical analysis are interesting.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VRTd4wpL7R", "reviewer": "Reviewer_Sr3Z", "summary": "", "questions": "", "limitations": "", "rating": 5, "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:\n\n+ The paper considers a problem of relevance to the ICLR community, and proposes what appears to be a novel algorithm with both empirical and theoretical support.\n\n+ I found the paper very clear and easy to read\n\n+ The theoretical results are tight, in that they match the optimal statistical rates achievable in offline IL.\n\nWeaknesses:\n\n- Theorems 4.1 and 4.2 have no explicit dependence on the fraction of corrupted data points $\\varepsilon$ and/or the number of batches $M$ needed to ensure that at least 50% of the batches are not corrupted (which is assumed in the proof).  Presumably there is a tradeoff/dependence here.  In the extreme case where $\\varepsilon\\approx .5$, it would seem that each \"batch\" would be of size 1, at which point it isn't clear if/how the algorithm would work.  Some more explicit delineations of these constants would be very useful.\n\n- The empirical evaluation was somewhat underwhelming: I would have expected to see several more environments tested.  \n\n- No comparison to other robust imitation learning algorithms were provided, and so it is unclear if the algorithm is doing well, or if the tasks are easy enough that any sensible approach to limiting the effects of outliers would do well.  If the reason is that no other offline robust IL algorithms exist, then why not compare DAGGER w/ a MOM cost (which the authors repeatedly state is easy to implement) to some of the interactive robust IL methods outlined in the related work section.  At the very least, comparisons to more sophisticated offline IL methods should be done, e.g., the method proposed in Ho and Ermon 2016.  Statistical optimality and practical performance are not always the same, and so only comparing to BC is not as strong as suggested by the results as Agarwal et al.\n\n", "summary_of_the_paper": "This paper considers an offline imitation learning task wherein a constant $\\varepsilon$-fraction of demonstrations have been potentially arbitrarily corrupted.  This data corruption is motivated by sub-optimal experts and/or erroneous/adversarial sensors.  In order to address this, the paper proposes minimizing a Median-of-Means (MOM) objective.  Theoretically, it is shown that up to constant factors, the resulting learned policy achieves the same statistical rates as behavior cloning, which was shown to be optimal for the offline imitation learning setting in recent work by Agarwal et al.  This analysis is done under the assumption of a discrete policy class containing the expert policy.  Algorithmically, an approach based on alternating gradient descent/ascent is proposed, and it is shown on two continuous control benchmarks in PyBullet (LunarLanderContinuous-v2 and HalfCheetahBulletEnv0) that the proposed approach compares favorably to a behavior cloning as applied to uncorrupted data, whereas vanilla behavior cloning performs very poorly.", "summary_of_the_review": "This paper presents a novel and in my perspective interesting approach to tackling IL in the corrupted data setting.  However, I believe it would benefit from a refinement of the theoretical results to highlight the role that the fraction $\\varepsilon$ of corrputed data plays, as well as from more extensive empirical evaluation, as described above.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RoumQlgtM7d", "reviewer": "Reviewer_rs1D", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strength:\n\n1.\tThe proposed MOM objective for robust imitation learning is novel.\n2.\tTheoretical justifications are available showing the validity of the proposed RBC.\n3.\tThe paper is well-organized and clearly written.\n\nWeakness:\n\n1.\tIn the experiments, data corruption changes a sampled action to a boundary value which does not match exactly with the demonstration corruption definition in Def. 2.1. It would be better for the authors to corrupt the actions with an arbitrary value within the action value range. \n\n2.\tThe experiments focus on tasks with low-dimensional state spaces. Considering that BC also achieves good performance in tasks like Ant, it would be good for the authors to consider tasks with higher-dimensional state spaces. Moreover, there are only two tasks in the experiment section, which does not show a strong validation of the effectiveness of the proposed solution. \n\n3.\tThe performance of RBC is not convincing in the HalfCheetah task as only 1% of corruption is added. It would be better for the authors to show RBC’s performance on HalfCheetah when the corruption rate increases to 20%, to better show the advantage of the proposed RBC.\n\n4.\tOnly behavior cloning is compared in the experiment section. Baselines that assume expert demonstrations such as EDM[1] and DFSN[2] should also be compared to show the robustness to data corruption and better show the necessity of the proposed solution.\n\n[1] Jarrett, D., Bica, I., & van der Schaar, M. (2020). Strictly batch imitation learning by energy-based distribution matching. arXiv preprint arXiv:2006.14154.\n[2] DonghunLee,SrivatsanSrinivasan,andFinaleDoshi-Velez.Trulybatchapprenticeshiplearning with deep successor features. International Joint Conference on Artificial Intelligence (IJCAI), 2019. \n", "summary_of_the_paper": "In this paper, the authors aim to find an offline solution to the imitation learning problem with corrupted demonstration data. They propose a simple robust behavior cloning (RBC) approach based on the Median-of-Means (MOM) objective. The contributions of this work are as follows:\n\n1.\tA novel RBC algorithm is proposed with a MOM objective in policy estimation based on behavior cloning.\n2.\tThe authors provided theoretical justifications on the error scaling and sample complexity of the proposed RBC to show that RBC guarantees robustness to corrupted demonstrations at no cost of statistical error.\n3.\tExperiments on some low-dimensional tasks show the effectiveness of the proposed RBC. ", "summary_of_the_review": "In general, the authors propose a novel and interesting MOM objective for robust imitation learning from corrupted data. However, there are some weaknesses (listed above), including no sufficient experiment results supporting the effectiveness of the proposed solution, preventing me from giving an acceptance.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RIAx8jW4wLR", "reviewer": "Reviewer_9dLk", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "### Summary++:\n\nThis is quite a difficult paper to judge.  The conception of the scenario and execution within the parameters stated are just about fine.  A lot of imitation learning papers do assume that you can query the environment or an expert policy, which is not always feasible.  This paper uses strictly just demonstrations, which is interesting, and I don’t think gets enough attention.  The core of the learning method is essentially gradient descent on a dynamically selected subset of each minibatch, and so while there isn’t much wrong there, the innovation is limited. \n\nWhat I believe to be the “secret sauce” is basically uncommended on (see A), and the absolute contribution is low as it basically combines existing components in a somewhat contrived scenario that essentially fits that combination of components (see B).  I also have problems with the formal statements and math (see C, D, E).  I believe there is also a tension between the motivation for the method and the method itself (see F).  Finally, the empirical validation is chronically lacking for such a simple and broadly applicable method (see G).\n\n### Major Comments:\n\nA - The method itself is incredibly simple, which in a way is to be commended, I suppose.  However, the crux of the method, in my eyes, is that backpropogating through only the median loss term just discards the outliers (as intended), such that those samples are never used in a gradient computation.  This is quite a succinct method for “automated outlier detection,” akin to something like RANSAC for localization with outliers.  This is a nice intuition and application of this idea, but it is dressed up to be way more complex than this in the paper.  When the method is stripped back to this, it is a notably less significant advance.  I also think this perspective engenders analysis and discussion that is currently lacking from the paper.\n\nB - The corrupted samples are selected at random from the demonstrations, and, the ratio of corrupted to non-corrupted is quite low (<10%).  Therefore, it is perfectly reasonable that the MoM operation will discard these samples.  It is unclear to me what the effect would be with higher percentages of corrupted samples.  I expect that the gradient estimators would become *very* high-variance as the probability of each small minibatch having at least a single outlier tends to one.  (This relatively simple but hyper-instructive mathematical analysis is also absent from the paper).  The corrupted samples are drawn with uniform probability, and so there is correct supervision present in the corrupted dataset, it is just a case of filtering out the bad samples. In this sense, this whole paper is just defining a type of filter, which is less significant as a methodological innovation again.  I think something like a semi-supervised method learning attaching a Bernoulli distributed random mask on which samples are outliers, or any unsupervised outlier detection/clustering method, would be much more scalable, performant, and appropriate for higher corruption ratios.  \n\nB.1 - The corruptions are defined by driving the action to the extrema of the allowable range.  This is the worst-case scenario for the B.C. baseline, and the best-case scenario for the proposed method.  This is also quite a rare case, as the corruption would likely be biased, but not _extreme_.  I therefore believe that the comparison is unfair, to the point of being invalid.  \n\nC - I seriously question the structure of the objective in Eq. (3).  I cannot see how the introduction of a second policy $\\pi’$ affects this optimization.  As both $\\pi$ and $\\pi’$ are defined on the same space, I _think_ this expression reduces to simply:\n \n\\begin{equation}\n= argmin_{\\pi \\in \\Pi} 2 * l_j (\\pi) = argmin_{\\pi \\in \\Pi} l_j (\\pi)\n\\end{equation} \n\n(you can essentially change the max to a min and change the minus to a plus, or, (i think) the loss function for the difference is symmetric (up to a minus) in $\\pi$ and $\\pi’$ and so the solution must be at $\\pi = \\pi’$. )\n\nI also think there is an expectation over the minibatch partitions missing from the objective.  \n\nD - The “theory” sections add nothing to this paper, as far as i’m concerned.  I believe they serve no purpose other than making the paper seem more significant/complex than it is.  _Especially_ given that the only bit of theoretical analysis I see as required -- the probability that any given minibatch is uncorrupted, and hence provides unbiased gradient signal -- is not included.  \n\nE - The definition of a corrupted dataset is also not entirely consistent with the definition used later on.  You discuss an “adversary” getting to change the observed action for a chosen \\epsilon-subset of the data, but, later on, you then randomly sample the points to corrupt and set them to an extreme+random value.  This is quite far apart from the idea of a hypothetical adversary intentionally corrupting the dataset.  As I said in B, the correct supervision is in the data in your setup, whereas in the real world, samples may be consistently biased in regions of subspace.  This means that the expert policy could not be recovered, and hence I am deeply skeptical of your “guarantees” that the expert policy will be recovered.  \n\nF - In the introduction, the authors (in-part) motivate the problem of learning an agent as being hindered by the inability to conduct experiments in hazardous or dangerous regions of state space.  \n\nF.1 - Behavioural cloning requires samples in all parts of visited state space to ensure performance, and therefore having missing regions of state space or biased demonstrations in these regions of state space can lead to arbitrarily sub-optimal results.  Simulation-based methods are the _only_ way to ensure consistency.\n\nF.2 - The authors also comment on the difficulty of specifying a reward function.  However, IL still requires you to specify a loss function, which may or may not produce results that are optimal in terms of reward, and hence IL/BC does not alleviate this either. Minimizing a loss term does not imply optimality in reward space (i.e. [Warrington et al., 2020]).  \n\nF.3 - Limiting yourself to not use environment interactions is interesting, but I feel that this is a critical restriction that ultimately limits the utility of this method.  I struggle to see a scenario where demonstrations are too few and too corrupted for B.C. to be viable even with manual data cleaning, but where application of the proposed method would enable practitioners to be like “sure, let’s use these highly corrupted demonstrations anyway”...  That may be a personal thing, but I feel like this method may struggle to find impact anywhere, and certainly with the broad and safety-critical purview motivated in the introduction.  To be convinced of this, I would need to see this method crack a previously intractable and real-world task.  \n\nG - The empirical validation is far too thin in my opinion.  Testing on two (simple) gym environments is not especially challenging, and, as alluded to above, the rate of corruption is pretty low and corrupted samples are easily detectable.  The baselines compared to are pretty much the most simple thing one could have done, and while I am not overly familiar with B.C. methods, I struggle to believe that nothing more complex than L-2 regression has been done prior to this.  Again, as alluded to above, I think semi-supervised methods (or even historic methods such as Jackknife sampling) would easily outperform this method in more complex settings.  I understand that the highly restricted scenario limits the diversity of methods that can be use, but I do not believe that this method has been “battle tested” when it is compared against baselines that are either (a) infeasible or (b) known/designed to fail.  \n\nH - I do take issue with the use of “imitation learning” throughout -- you are explicitly doing the more restricted “behavioural cloning”, as opposed to the slightly more general family of imitation learning methods.  \n\n\n### Minor Comments:\n1 - Only proper nouns should be capitalized: i.e. “Robust Behavior Cloning” -> “robust behavior cloning”;  “Negative Log-Likelihood” -> “negative log-likelihood”.\n\n2 - Avoid colloquial language and contractions: i.e. “demos”.\n\n3 - The figures are massive for how much information is conveyed in them.  \n\n4 - The math is pretty impenetrable. \n\n\nWarrington, et al. \"Robust asymmetric learning in pomdps.\" International Conference on Machine Learning. PMLR, 2021.\n", "summary_of_the_paper": "This paper tackles behavioural cloning from expert demonstrations, where a fixed fraction of the demonstrations are corrupted.  This is a somewhat (see comments below) practical scenario where trajectories gathered are limited or biased in response to constraints on collection.  A crucial (again, see comments below) point is that _no_ further environment interactions are allowed -- only the possibly corrupted demonstrations can be used.  The paper provides a definition of a corrupted dataset, an objective for training using a corrupted dataset, and provides some convergence and error bounds.  The method is tested on two standard Gym environments, and some ablation studies are provided.", "summary_of_the_review": "The paper itself is not especially well written, having numerous typos and grammatical mistakes, and is evaluated on the barest minimum of tasks (two relatively simple gym environments), with no convincing baselines or alternative methods compared to.  I am also currently unconvinced by the core objective (eq. (3)), and the relevance of the math presented, although I invite the authors to justify these both to me.  Finally, I think the setup itself is both too restrictive to have significant practical impact, and is actually in conflict with the original motivation for the work.  \n\nOverall, I do not think this paper is of the requisite quality for acceptance at this point in time.  I encourage the authors to explore removing some of the inherent restrictions on the method, validating the method on a wider range of environments, seek out alternative methods to compare to, and to submit this work to a workshop to further develop the work and obtain feedback.  \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Meta-review: This submission addressed offline imitation learning problem with non-optimal demonstrations. The AC went through the draft, reviews, and replies. The AC agrees with all reviewers that the mathematical analysis, empirical evaluation, and general quality of writing haven't reached the bar of ICLR papers.
Decision: Reject