Imitation Learning from Imperfection: Theoretical Justifications and Algorithms
Authors: Ziniu Li
Tian Xu
Zeyu Qin
Yang Yu
Zhi-Quan Luo
Venue: NeurIPS 2023 spotlight (2023)
Keywords: imitation learning
distribution shift
policy optimization
data selection
TL;DR: We show the potential of improving imitation learning by leveraging diverse data sources through effective data selection.

Abstract: Imitation learning (IL) algorithms excel in acquiring high-quality policies from expert data for sequential decision-making tasks. But, their effectiveness is hampered when faced with limited expert data. To tackle this challenge, a novel framework called (offline) IL with supplementary data has been proposed, which enhances learning by incorporating an additional yet imperfect dataset obtained inexpensively from sub-optimal policies. Nonetheless, learning becomes challenging due to the potential inclusion of out-of-expert-distribution samples. In this work, we propose a mathematical formalization of this framework, uncovering its limitations. Our theoretical analysis reveals that a naive approach—applying the behavioral cloning (BC) algorithm concept to the combined set of expert and supplementary data—may fall short of vanilla BC, which solely relies on expert data. This deficiency arises due to the distribution shift between the two data sources. To address this issue, we propose a new importance-sampling-based technique for selecting data within the expert distribution. We prove that the proposed method eliminates the gap of the naive approach, highlighting its efficacy when handling imperfect data. Empirical studies demonstrate that our method outperforms previous state-of-the-art methods in tasks including robotic locomotion control, Atari video games, and image classification. Overall, our work underscores the potential of improving IL by leveraging diverse data sources through effective data selection.

Imitation Learning from Imperfection: Theoretical Justifications and Algorithms
Ziniu Li Tian Xu Zeyu Qints, Yang Yut3,, and Zhi-Quan Luot1. 1.2
The Chinese University of Hong Kong, Shenzhen
"Shenzhen Research Institute of Big Data
National Key Laboratory for Novel Software Technology. Nanjing University 'Polixir.ai
$ Hong Kong University of Science and Technology
Abstract
Imitation learning (IL) algorithms excel in acquiring high-quality policies from expert data for sequential decision-making tasks. But, their effectiveness is hampered when faced with limited expert data. To tackle this challenge. novel framework called (offline) IL with supplementary data has been proposed [25, 61], which enhances learning by incorporating an additional yet imperfect dataset obtained inexpensively from sub-optimal policies. Nonetheless, learning becomes challenging due the potential inclusion of -eeeexxeetdiiitrbuutioo samples. In this work, we propose a mathematical formalization of this framework, uncovering its limitations. Our theoretical analysis reveals that naive approach applying the behavioral cloning (BC) algorithm concept to the combined set of expert and supplementary data-may fall short vanilla BC, which solely relies on expert data. This deficiency arises due the distribution shift between the two data sources. To address this issue, we propose a new saw.taaneeeallinngg-gg..
technique for selecting data within the expert distribution. We prove that the proposed method eliminates the gap of the naive approach, highlighting its efficacy when handling imperfect data. Empirical studies demonstrate that our method outperforms previous state-of-the- thee------h-rrrttt methods in tasks including robotic locomotion control, Atari video games, and image classification. Overall, our work underscores the potential improving IL by leveraging diverse data sources through effective data selection.
1 Introduction
Imitation learning (IL) [3, 34] is essential technique in artificial intelligence, allowing machines to enhance their performance by imitating expert behaviors. This technique has showcased remarkable achievements across various domains such robotics [27], self-driving cars [35], and language models [55, 8J. Among the IL approaches, behavioral cloning (BC) [40] stands out as a popular method. In particular, BC leverages cemporall--corellaee demonstrations, employing them as training samples to learn a mapping from states to actions via maximum likelihood estimation. In this manner, IL expands upon the traditional supervised learning framework, enabling the acquisition of sequential decision-maln makiing capabilities.
state-action pairs extracted from expert
The quantity of expert trajectories plays crucial role in achieving satisfactory performance. Previous studies have shown that BC works well when the dataset contains a large number of expert-level
*: Equal contribution. Author ordering is determined by coin flip. Emails: ziniul illnnkk cuhk, edu cn and xut@l amda. .nju. edu.
Email: zeyu.q wer.a.gincconnnn gin&connect. ust.hk.
I: Corresponding authors. Emails: yuy@nju. edu. en and luozq@cuhk.. edu. en. www/liiiiiu/ISW/B...
'The code is available at https:
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

trajectories [48]. However, the well-known compounding errors issue [44] renders any offline IL algorithm, including BC, ineffective when the number of expert trajectories small [42. 60]. Furthermore, collecting more trajectories from the expert is costly and impractical in many domains, such as robotics and healthcare.
To overeome the challenge of scarce expert data, we propose to use an additional yet imperfect dataset to supplement the expert data; see Figure I for illustration, In particular, this additional dataset can be cheaply obtained by executing sub-optimal policies. However, the incorporation of supplementary dataset introduces distribution shift issue due to the presence of out-of -f-expert- distribution trajectories." 3 The distribution shift issue may hamper the model's performance in utilizing the supplementary data, as we will argue later.
We realize that a number of empirical successes have been reported in this direction [25, 24, 61, 32]. Most algorithms rely discriminator to distinguish between expert-style and sub-optimal samples, followed by optimization of a weighted BC objective to learn good policy. For example, DeMoDICE [25] uses a regularized state-action distribution matching objective to train the discriminator, while DWBC [61] employs a cooperative training framework for the policy and discriminator. Despite the empirical successes in certain scenarios, there remains notable absence of systematic theoretical studies, particularly in terms of imitation gap (i.e., performance difference between the expert and learner., which may hinder deep understanding and impede future algorithmic advances.
Table 1: The theoretical guarantees of three methods: (1) BC, which relies solely on expert data; (2) NBCU, which directly uses the union of expert data and sup- plementary data without selection; and (3) ISW-BC, a new method that employs importance sampling for data selection. Compared with BC, NBCU suffers a non- vanishing error due the distribution shift between two datasets while ISW-BC does not.
expert
model traising
data
data selction
sugueal
16c0 supplementary data but 00D
Figure 1: Compared with the conventional IL framework (shown in cyan), the supple- mentary data helps address the expert data scarcity issue, and the data selection tech- nique helps address the distribution shift. issue in model training.
Imitation Gap O |S| NR Õ Õ((1-) (v - V(T + No+No
BC NBCU ISW-BC
I
O 1
NoNN
We aim to bridge the gap between theory and practice in the (offline) IL with supplementary data framework by developing effective algorithms and providing rigorous theoretical guarantees. To the best of our knowledge, only [9] provided imitation gap bounds for a model-based adversarial imitation learning approach in similar problem. However, our focus lies the widely used and simpler BC and its variants, which are model-free in nature. Our contributions are summarized below.
We develop formal mathematical framework of the IL with supplementary data framework and conduct corresponding theoretical analysis. Our findings highlight the impact of the distribution shift between expert and supplementary data. Our results
summarized in Table 1.*
In particular, our analysis shows that naively applying BC on the union of expert and supplemen- tary data (referred to as the NBCU method in this paper) has a non-vanishing error term in the imitation gap bound (see the second row of Table 1). This means that the direct use of additional data might yield inferior performance compared with solely using the expert data with BC. This necessitates the development of more advanced algorithms.
Forr instance, web texts and images are easily available for language and vision models, respectively: robotics benefit from previously collected datasets.
'This issue is separate from the intrinsic distribution shift problem that IL already faces, where the training and evaluation distributions differ [44]. It is important to note that these are distinct issues.
*We briefly explain notations in Table 1: [S] indicates the state space size, H is the horizon length, Ne means the expert data size, and Ns refers to the supplementary data size. In addition, we define r = NE/(NE + Ns). and ((x B) V(T") as the performance gap between expert policy = and supplementary data collection policy 9 For ISW-BC's bound. > 0 represents the state-action distribution density ratio bound between these two policies (to be detailed in Theorem 3).
2

---

To address the distribution shift issue, we propose a new approach called ISW-BC, which uses the importance sampling technique select data within the expert distribution. In contrast to prior methods [25, 61J, ISW-BC re-weights data in an unbiased way. We develop new imitation gap bound for ISW-BC (see the last row of Table 1), revealing that it not only eliminates the gap exhibited by the naive approach but also offers superior guarantee over BC.
Our theoretical analysis has been validated through extensive experiments, including robotic locomotion control, Atari video games, and image classification. The results affirm the superiority of ISW-BC over existing methods, thus demonstrating the potential of our method in addressing the distribution shift issue in IL with supplementary data.
2 Related Work
We review briefly relevant studies in the main text and provide detailed discussion in Appendix B.
Behavioral Cloning. Behavioral cloning (BC) a popular algorithm in the offline setting, where the learner cannot interact with the environment. According to the learning theory in [42], only using an expert dataset, BC has an imitation gap of O[ /Ne), where |S| is the state space size, H is the planning horizon, and NE is the number of expert trajectories. Our work investigates the use of supplementary dataset to enhance the dependence on the data size.
Adversarial Imitation Learning. In contrast to BC, adversarial imitation learning (AIL) methods, such as GAIL [21], perform imitation through atate-action distribution matching. It has been demonstrated both empirically and theoretically that AlL methods do not suffer from the compounding errors issue when the expert data limited [21, 16, 26, 59, 60, 28, 633. Under mild conditions, [62] provided horizon-fres bound of (minn / )) which is much better than BC in terms of dependence on H. However, AIL methods work naturally in the online setting (i.e., the interaction is allowed), which is not directly applicable in the offline setting that we study in this paper. Although the proposed method has a discriminator and policy like AIL, our discriminator and policy are not designed to compete with each other adversarially, as we will explain in detail later.
Imitation Learning with Supplementary Data. Our theoretical study is motivated by recent empirical successes in IL with supplementary data [25, 61. 32, 24]. Compared with [25, 61], a related setting, learning from observation, is studied in [32, 24]. In this setting, expert actions are absent, and only expert states are observed. The importance sampling technique used in our method for addressing distribution shift is also studied in (semi-)supervisee learning [49, 11, 30, 15]. Our contribution is to show this technique is also effective in the imitation learning, where data has a Markovian structure.
3 Preliminaries
Markoy Decision Process. In this paper, we consider the episodic Markov decision process (MDP) framework [41]. An MDP is defined by the tuple M = AS p,,, H,p)) where S and A the state and action space, respectively. H is the maximum length of trajectory, and p is the initial state distribution. The non-stationary transition function is specified by = (P...... PH }, where Ph (s 19h, ax) determines the probability of transiting to state sh-1 given the current state sp and action 0Ą in time step h, for h E [H]. Here the symbol [ar] means the set of integers from 1 to x. Similarly, the reward function r = {r1,
.TH) specifies the reward received at each time step, where Th. S x A- j0, 1] for E [H] A policy in an MDP is function that maps each state to a probability distribution over actions. We consider dependepn policies Tr, : + A(A), where ((A) is the probability simplex. The policy at each time step h is denoted as Th, and we use a to denote the collection of time-dependent policies J when the context is clear.
We measure the quality of a policy π by the policy value (i.e., environment-
long-term return:: ((x) E - Th (sh, on) | 81 P; ~ TT, (-1s)), 8h-1 Px Sp. ax). Yh E [A]] To facilitate later analysis, we need to introduce the state-action distribution df (s, a) = P(s = s,
!!
alT). We use the convention that d" is the collection of -eeendepnndnnt state-action distributions.
Imitation Learning. Imitation learning (II.) aims to learn a policy that mimics an expert policy based on expert demonstrations. In this paper, we assume that there exists a good expert policy E that generates dataset DE consisting of Ng trajectories of length H.
DE tr (#1, (11 82, 02. :8 ag) ) 88 D2 an = 8h-1 Pa(-1s,, an), Vh E [M]].
3

---

The learner aims to imitate the expert using the expert dataset DE, The quality of the imitation is measured by the imitation gap, defined as E [v [(T)]. where the expectation is taken over the randomness of data collection. It is worth noting that in the training phase, the II. learner does not have access to reward information. good learner should closely mimic the expert, resulting in a small imitation gap. We assume that the expert policy is deterministic, a common assumption in the literature [42, 43, 60], and applicable to tasks such as MuJoCo locomotion control.
Behavioral Cloning, Behavioral cloning (BC) is a popular imitation learning algorithm that aims to learn a policy from an expert dataset D via supervised learning. Specifically, BC seeks to find policy π RC that maximizes the log-likelihood of the expert actions in the dataset:
π BC E argmaax
E (s.a)ESXA
(ogT
where (s, a) is the empirical state-action distribution in the expert dataset. By the maximum likeli- hood estimation (MLE), BC can make good decisions by duplicating expert actions on states visited in DE, However, BC may take sub-optimal actions non-visited states, resulting in compounding errors and a large imitation gap. This issue is significant when the expert data is limited.
4 Imitation Learning with Supplementary Data
To address the challenge of limited availability of expert data, we consider an IL with supple- mentary dataset framework. We assume that a supplementary yet imperfect dataset D = { tr
(81,a), a1 82, '2, 8H, ) is collected by behavior policy T.. A naive approach is to perform MLE on the union of the expert and supplementary dataset D = DE DD:
H
π NBCU E argmmax
Σ ((
(=.
where di (s. a) is the empirical state-action distribution in DV, We refer to this approach as NBCU (naive BC with the union dataset). NBCU treats these two datasets equally and is brittle to distribution shift, as we will demonstrate later. For theoretical analysis purpose, we assume expert data represents a a E [0, 1] fraction of the total union data.
Assumption 1. The expert dataset D and supplementary dataset DE are collected in the following way: each time, we roll-out a behavior policy R with probability 1 -1 1] and the expert policy with probubility Such experiment is independent and identically conducted Noot times.
Under Assumption 1, we slightly overload our notations: use Ng denote the expected number of expert trajectories, which is given by NE = vi,Nent. and Ng to denote the expected number of supplementary trajectories, which is given by Ns- (1 - 17) Noot- Note that the probabilistic sampling procedure does not change the nature of our theoretical insights. In practice, one may collect a fixed number of expert and supplementary trajectories, respectively.
To establish a common ground, we begin by specifying the policy representations. Here, we adopt tabular representations, which assume that the parameterized value functions can take any possible form. Specifically, we define x (a]s; f) = (ø(s, a), 8), where ő(s, a) E Idd is the feature representa- tion and e Rd is the parameter to optimize. In tabular representations, we use one-hot features for 0(s.0 a). For discussion on general function approximation schemes, please refer to Appendix E.
Imitation Gap of BC. In order to evaluate the usefulness of the supplementary dataset, we use BC with only the expert dataset as baseline. The analysis of this approach has been done in the conventional IL set-up in [42], and we re-state their results in our setting.
Theorem 1. Under Assumption 1, if we apply BC only on the expert dataset, we have that ((S)E))
E (T) V(TBO)) dataset collection (same as other expectations).
Ng ), where the expectation is taken over the randomness in the
Proofs of Theorem 1 and other theoretical results are deferred to the Appendix. The proof of Theorem builds on [42], with the main difference being that the number of expert trajectories is
random variable in our set-up. We handle this difficulty by using Lemma in the Appendix. The quadratic dependence on the planning horizon H indicates the compounding errors issue of BC.

---

If the expert data is limited (i.e., NE is small), the performance gap can be large, suggesting poor performance of BC in this scenario.
Imitation Gap of NBCU. Guarantees of naively using the supplementary data are presented below. Theorem 2. Under Assumption 1, if we apply BC on the union dataset, we have (v [(TTBCC))] = ((11 (0((1-n))) (V V(( + |S| log(Noo))).
Nest
Remark 1. In case when the behavior policy is inferior to the expert policy, we have ((T²) V(=0) > In this case, even if Noot large enough to make the second term negligible, there is still non-vanishing gap of V (= V (T²) due to the behavior policy's 's potential to collect non-expert actions. In other words, the recovered policy may select wrong actions even on expert states, leading to the sub-optimal performance of NBCU.
is worthy to note that this non-vanishing error term can also be interpreted from the viewpoint of the distribution shift. Specifically, using the analysis in [62], we can show that
((=B)-V(TT)) O(HE))
O(Hea) = O(H2 Ex),
where Ed- max; Tdd di. the state-action distribution total variation (TV) distance and E = max, max, (.)ss, (-(s) is the policy distribution TV distance. Hence, we can also view Theorem 2 in the context of catt-acciion policy distribution shifts.
Note also that we do not claim that NBCU is always worse than BC. Instead, Theorem 2 implies that if the distribution shift between two data datasets is small, NBCU could be better than BC by leveraging more data, which we will also show in experiments later.
The next proposition establishes the inevitability of the gap V(T - V(=)) in the worst case. Proposition Under Assumption I, there exists an MDP M, an expert policy T and a behavior
policy n², such that have E (V ((
[2(11 (V V(r")))
The hard instance in Proposition builds on the following idea: NBCU considers all action labels in the union dataset equally important. Therefore, we can build an instance where the expert π selects a good action with an one-step reward of 1, while the behavior policy xO chooses bad action with one-step reward of O. The noise introduced by T results in incorrect learning goals, causing NBCU make a mistake with probability 1 y7. which the fraction of the noise in the union dataset. By carefully designed transition probability, we can obtain the expected bound in Proposition 1.
5 Addressing Distribution Shift with Importance Sampling
In this section, we propose data selection approach to alleviate the distribution shift issue between expert data and supplementary data. Our approach is inspired by recent works [25, 61], where diseriminator is trained re-weight samples, and weighted BC objective is used for policy optimization. Specifically, we define the weighted BC objective as follows:
"1
π JSW-BC E argmmax
Σ
a (s. x [wn a) log TA (a|s)] x [wn 2 01 (3)
IT
A=1
(A
where di (s. a) is the empirical state-action distribution of the union dataset, and (n a) [0, 20) is the weight decided by the discriminator. We introduce a arper-parameter 6 E [0, oo) to better select samples.
We propose using the importance sampling technique [46, Chapter 9] to transfer samples the union dataset to the expert policy distribution, which is the key idea behind our method. This technique helps address the failure mode of NBCU. In an ideal scenario where there are infinite samples (i.e., at the population level), dH would equal dy. By setting (s, a) = (s, a) / (s, a), obtain al (s, a)wx a) df[ss, a), and the objective (3) enables the learning of policy if samples were collected by the expert policy. However, in practice, (s, a) and (s, a) are unknown, and only have a finite number samples from each of these distributions. Therefore, we must estimate the grounded importance sampling ratio d (s, a)/d/ (s, a) from the expert data and union data.
We emphasize that estimating the probability densities of high-dimensional distributions separately for expert and union data and then calculating their quotient can be a challenging task. We take different
5

---

approach. Inspired by [17]. we directly train discriminator to estimate the importance sampling ratio d a)/d% (s, a). To this end, we introduce time-dependent parameterized discriminators {cr : x A [0, 1]
H h= each of which is optimized according the objective function
max
Σ (8,0)E8xA
(F{(s,)) a) [log (cn (s,
+
Σ (a,0)E8XA
(ss a) [log (1 c cs))))))
(4)
Ch
Solving the optimization problem in (4) is equivalent training binary classifier that assigns positive labels to expert data and negative labels to union data. We can obtain the optimal discriminator at the population level, from which we can derive the importance sampling ratio formula:
(s, a)
wn(s, a) = c% (8, a)
(8, a) (s, + (
(5)
0% a)
Based on the previous discussion, we present the implementation of our proposed method, named ISW-BC (importance-sampling sampling-weighted weighted BC), in Algorithm 1. It is worth noting that ISW-BC employs an unbiased weighting rule since it directly estimates the importance sampling ratio. In contrast, previous approaches such as [25, 61] use regularized weighting rules that may fail to recover the expert policy even with infinite samples. For further details on the differences between our method and previous ones, please refer to Appendix B.
5.1 Negative Result of ISW-BC with Tabular Representations of Discriminator
We have not yet specified the representations of the discriminator. One natural choice is use tabular representations, which correspond to linear function approximation with one-hot features. Tabular representations have a strong representation power since they can span all possible functions. However, surprisingly, we show that tabular representations can fail when considering generalization. Proposition 2. If the discriminator uses the one-hot feature with 8 O, we have π ISW-BC =C
Proposition suggests that even if we have a large number of supplementary samples and use importance sampling, ISW-BC is not guaranteed to outperform BC based on tabular representations. To illustrate, suppose we have a sample (s, a) that is an expert-style sample but only appears in the supplementary dataset, meaning that (f, a) > 0, ds a) 0 and d a) > 0. Using
tabular representations, we can compute the closed-form solution (7, a) dF a) (d
dy (s. a)) = O. This implies that the importance sampling ratio (v, a) cj (s. a) (1-11 (s, 0, so this good sample does not contribute to the learning objective (3). The failure of tabular
representations due to their discrete treatment of data, ignoring internal correlations. Consequently, although they work well in minimizing the empirical loss, they are not good at generalization. This kind of failure mode also mentioned in the GAN literature [4].
Algorithm 1 ISW-BC
in-distribution
out-of-distribation
Input: Expert data DE and supplementary data DS, 1: DV + DE D
2: Train binary classifier with positive labels
for D and negative labels for D
3: w +- Compute importance sampling ratio by
Eq. (5).
4: π ISW-BC <- Apply weighted BC learn policy
Figure 2: Illustration for ISW-BC. Please refer to the text below Assumption 2 for a detailed explanation.
by Eq. (3) with DU and w.
Output: Policy n ISW-BC
5.2 Positive Result of ISW-BC with Function Approximation of Discriminator
In this section, we address the issue raised in the previous section by investigating ISW-BC with a specific function approximation. To avoid the limitations of tabular representations, consider that the discriminator is parameterized by Ca a; 0%) = I+exp(- (5.. where Φ) S x - R2 is a fixed feature mapping and 0g E IRd the parameter to be trained. Note that we require d < || to avoid the tabular representations. Let g(x) log(1 [1 + exp(x)). Then, the optimization problem of

---

the discriminator becomes:
min (0,) A Σ -o On
Eth ())((((()) On))
(6)
(x,0)
(s,a)
Let 0 [07 f be the optimal solution obtained from Eq. (6). With the feature vector,
samples are no longer treated independently. and the discriminator can perform structured estimation.
To be consistent with the previous results, the policy is still based on tabular representations.
In the context of general linear function approximation, it is no longer possible to obtain a closed-form solution for e* as in Eq. (5). This raises the question: what can we infer about ct? Our intuition can described as follows. We can envision the supplementary dataset containing two types of samples: some that were in-expert distribution, and others that were out-of-exper -epprrreeettttteooo distribution. We expect that wp (s, a) is large in the former case and small in the latter case. Note that wy (8, a) is monotonic with respect to the inner product (oh, (s, a), 0). Therefore, we conclude that a larger value of (0n(s, a), 0) implics a more significant contribution to the learning objective (3). In the following part, we demonstrate that the aforementioned intuition can be achieved under mild assumptions.
Assumption 2. Let Di denote the set of state-action pairs in DS in h. Define D
{(s,a)
Dj. : di (s) > 0, a = (s) as the mn-expert-distribttin dataset in D and D., = =D D as the out-of-exeer-ddistrbbbtt
dataset. There exists a ground truth parameter 02 E Rd, for any $.1 and (s',a') E 5,2, it holds that (0), (n (s) > 0 and (0), (s',',, a')) < 0.
(s, a) E DR. UDD
Readers may realize that Assumption 2 is closely related to the notion of "margin" in the classification problem. Define An (0) & min (sa)) (0, (s, a)) max (a) (0, Φn a')). From Assumption 2, we have (0,) > O. This means that there exists a classifier that recognizes samples fi-expertt-distiibunee
from both DE and 5 distribution samples. Note that such a nice classifier is assumed to exist, which is not identical to what is learned via Eq. (6). Before further discussion, note that 0, is not unique if it exists. Without loss of generality, we define 0, as that can achieve the maximum margin (among all unit vectors).
samples and samples from D
out-of-expert-
Let us delve into the technical challenge that arises from Assumption 2. Although we assume two modes in the supplementary dataset, the learner is not aware of them beforehand. To gain better understanding, refer to Figure 2. where the "star" corresponds to the expert data and the "triangle" corresponds to the supplementary data. The green and red parts of the triangle represent DS.1 and D8.2, respectively. While training the discriminator, we assign positive labels (shown in "+") to the expert data and negative labels (shown in "-") to the union data. Consequently, it becomes challenging determine the learned decision boundary theoretically. To address this challenge, develop the landscape properties, Lipschitz continuity and quadratic growth conditions, in Lemma I and Lemma 2, respectively. These terminologies are from the optimization literature; see [23, 13). Incorporating these properties will enable us to infer the learned decision boundary.
Lemma 1. For any 0 E Rd, the margin function is L, -iisschtt continuous in the sense that (O,) - (0) < Ln 0 - -O], where Ln = (8 , - on(s², ",2,,0 a²'ll with (s* ,a))) E argmin (3.0)EDEUp (0, on (s, a)) and (s² aa²) E argmax (sa))D (0, (s,(s))
Lemma 2. For any h, let A E R. Non xd be the matrix that aggregates the feature vectors of samples in DV- Assume that rank( An) d, then Lu. (defined in Eq. (6)) has (one-sided) quadratic growth
condition. That is, there exists > O such that L (rx( 2 (o)) + = 0 -0%ll
Using Lemma and Lemma 2, we are ready to obtain the imitation gap bound of ISW-BC
Theorem 3. Under Assumptions I and 2, let μ = max d% (s, . (s)) /r (s. (F()))
<
0o, if the feature is designed such that 2(C,,0.)--
An( holds, then we have (n())) >
Th
Ln
O. Furthermore, we have the imitation gap bound (T - VSTISWBC)) = O Ng+Ns/
In order to interpret Theorem 3, it is important to note that (O;) > 0 means that there exists a 8 > 0 such that wn,ss, a; 08)) > 5 for a) E D u D and wn, (s, a; 0%) < 5 for (s,a) E 52 As a result, all samples from DE and D'S,) are assigned with large weights, which allows ISW-BC to make use of additional samples and outperform BC.
7

---

We remark that the imitation gap bound of ISW-BC is dependent on the number of expert-style state-action pairs presented in the union of D and D. This number is represented as NE + N μ, where μ is a state-action coverage parameter. It is important to mention that similar notation is used in the literature of offline RL, seen in [33, 10]. Additionally, ISW-BC has the ability to eliminate the gap of NBCU, meaning there no non-vanishing error in Theorem 3. Moreover, ISW-BC can perform well even when Di," has noisy action lahels, a scenario where NBCU may fail.
Although Theorem 3 produces desirable outcomes, it does have some limitations. First, the theoret- ical analysis necessitates knowledge of 6, which typically challenging to determine beforehand. However, our empirical findings in Section 6 demonstrate that setting å = 0 is effective in practice. Second, Theorem mandates the use good smooth features to ensure the required inequality holds, thereby avoiding the undesirable case presented in Proposition 2. Our paper does not offer solution for finding such feature representations. Nevertheless, our experiments indicate that neural networks can usually learn suitable features. We present simple mathematical example corresponding to Theorem in Appendix D.5. We leave more general results of ISW-BC to future work.
Experiments
To validate the theoretical claims, perform numerical experiments. We provide brief overview of the experiment set-up below, and the details can be found in Appendix H.
6.1 Robotic Locomotion Control
In this section, we present our experiment on locomotion control, where we train a robot to run like a human in four environments from the Gym MuJoCo suite [14]: Ant, Hopper, Half cheetah, and Walker. We adopt online SAC [19] to train an agent for each environment with 1M steps, and consider the resultant policy as the expert. For each environment, the expert data contains I trajectory collected by the expert policy. We consider two types of supplementary datasets:
Full Replay (small distribution shift): the supplementary dataset (1 million samples) is directly sampled from the experience replay buffer of the online SAC agent, which is suggested by [25]. This setting has a small distribution shift as the online agent quickly converges to the expert policy (see Figure 5 in the Appendix), resulting in abundant expert trajectories in the replay buffer.
Noisy Expert (large distribution shift): the supplementary dataset consists of 10 clean expert trajectories and 5 noisy expert trajectories where the action labels are corrupted (i.c., replaced by random actions). This introduces large state-action distribution shift, as discussed in Remark 1. For further discussion on dataset corruption and distribution shift, please refer to Appendix F.2.
Table 2:
Environment return of algorithms on 4 robotic locomotion control tasks. Digits correspond the mean performance over 5 random seeds and the subscript +: indicates the standard deviation. "Avg" computes the normalized score over environments. Same as the other tables.
Ant
HalfCheetah
Hopper
Walker
Avg
Random
-326
-280
20
0%
Expert
5229
11115
3589
5082
100%
BC
1759_ss7
931 2373
2468
1738
38%
NBCU
4932_148
10566126
3241
4462-10s
92%
DemoDICE
5000
10781 107
33941s3
4537 11125
94
Full Replay
DWBC
2951-138
1485
2567
1572=225
44%
ISW-BC
4933
10786
3434
4475=164
94%
NBCU
3259-150
5561
558
518
35%
DeMoDICE
2523-244
6020 #340
1990+s0
1685=160
49%
Noisy Expert
DWBC
3270
5688 2057
3317158
1985
62%
ISW-BC
3075m00
928413er
2624
2859 2077
69
Besides our proposed methods, we also evaluate two state-of-the-ar methods in the locomotion control domain: DemoDICE [25] and DWBC [61]. We report the experiment results in Table 2.
We observe that BC suffers since the amount of expert data is limited. In the full replay task, NBCU performs well due to the small distribution shift. However, in the noisy expert task, NBCU's average

---

performance is inferior to that of BC while ISW-BC outperforms NBCU in average significantly, demonstrating the robustness of ISW-BC distribution shift. is worth noting that among all evaluated methods, only our proposed method ISW-BC performs well in both settings. Prior methods such DemoDICE and DWBC only perform well in one of the two settings.
6.2 Atari Video Games
In this section, we evaluate algorithms on Atari games [5], which involve video frames as inputs and discrete controls as outputs. Furthermore, environment transitions are stochastic for these games. We consider 5 games, namely Alien, MsPacman, Phoenix, Qbert, and Space Invaders. We obtain the offline expert data and supplementary data from the replay buffer of an online DQN agent, as released by [2]. We use the expert data from the buffer with the last index, which only contains 50k frames, to create a challenging learning setting. To augment this data, we use earlier replay buffer data to obtain supplementary data with approximately 200k frames. We consider the same baselines as in Section 6. I. All methods build on the classical convolutional neural networks used in DQN.
Similar to Section 6.1, we consider two types of supplementary data. The full replay setting involves supplementary data that is close the expert data, exhibiting small distribution shift. The noisy expert setting has noisy action labels, leading to large distribution shift. Experiment details can be found in Appendix H.I.2 report the game scores of trained policies Table
Table 3: Environment return of algorithms on Atari video games.
Alien
MsPacman
Phoenix
Qbert
SpaceInvaders
Avg
Random
228
307
0%
Expert
2143
3601
4869
10955
1783
100%
BC
1051+t:
1799+27
1520+se
4769-11:
472+10
32%
NBCU
1405
2089
2431
8065
600
50%
DemoDICE
1401
2146115
2192
7820_ao0
558
48%
Full Replay
DWBC
122+4
1251+sa
583+aa
1078-s0
287+a
7%
ISW-BC
1452
2162+a6
2299+re
7848-as
613+10
50%
NBCU
944
1378
1491 155
4366_
418414
27%
DeMODICE
1054+as
1604+50
1448+112
5354+290
395+10
31%
Noisy Expert
DWBC
643+ss
656+16
1165+a7
3860-104
296+a
16%
ISW-BC
1122
1980
1618
5247
497
36 %
Our observations consistent with those of the previous experiments. NBCU performs well when the distribution shift is small, while only ISW-BC is robust when the distribution shift large.
6.3 Image Classification
(a) Clipart
(b) Infograph
(c) Painting
(d) Quickdraw
(c) Real
(f) Sketch
Figure 3: Samples of tiger class from 6 sub-datasets of the DomainNet [36] dataset. Infograph and quickdraw have quite different patterns (i.e., distribution shift) compared with the others.
In our final experiment, we tackle an image classification task. This task is a special type of imitation learning where the planning horizon is I and there are environment transitions. The reward is classification accuracy. Please note that our main purpose here is to use this degraded one-step task to verify the thcoretical results.
We use a famous dataset, DomainNet [36], which comprises 6 sub-datasets (clipart, infograph, painting ing. qui ckdraw, real, and sketch) that have different feature patterns and hence distribution shifts; see Figure 3 for an illustration. Following [22], our task to perform 10-class classification (bird, feather, headphones, ice_cream teapot, ti tiger, whale, windmill, wine wine_glass, and We provide explanation of why NBCU is better than BC Ant and Walker in this scenario in Appendix.

---

zebra) using 80% of the images for training and 20% for test. Each sub-dataset has roughly 2000-5000 images.
We build the classifier on the pretrained ResNet-18 [20], as directly training ResNet-18 on the DomainNet dataset failed. We then optimize 2-hidden-layer neural network, where inputs from the feature representations extracted by the pretrained and fixed ResNet-18. We create 6 sub-tasks, where one of the 6 sub-datasets used as the expert data while the other sub-datasets are used the supplementary datasets. We evaluate the classification accuracy on the expert test data. Note that there no natural extension of DemoDICE for this task. More details can be found in Appendix H.1.3.
The results of our experiment are presented in Table 4. We observe that due to the presence of distribution shifts, NBCU performs even worse than BC, even though NBCU use more data than BC. On the other hand, ISW-BC can improve the performance over BC on out of 6 tasks by re-weighting the supplementary data. At the same time, ISW-BC is more effective than DWBC.
Table 4: Test classification accuracy (%) of algorithms 6 types of expert and supplementary data.
Clipart
Infograph
Painting
Quickdraw
Real
Sketch
Avg
BC
89.31 10.01
15.801o.o:
90.141o.
85.61
96.191u.o
87.5810.
84.10
NBCU
89. 16
56.32+0.02
+8.2990.oz
84.78+0.08
95.31+0.00
80.57+0.00
83.57
DWBC
90.001o.es
57.4410.00
90.891o.or
85.091o.ce
96.351o.o1
88.8610.0r
84.77
ISW-BC
90.86
57.52_o
91.78
84.97
96.56_..o
89.63 os
85.22
Discussion and Conclusion
This paper introduces formal mathematical framework for imitation learning with supplementary yet imperfect dataset, which is designed to address the scarcity of expert data. Within this framework, we present new theoretical insights that illuminate the distribution shift challenge between expert and supplementary data. To deal with this challenge, we devise a new method named ISW-BC, employing the importance sampling technique to select data within the expert distribution. Through both theoretical analysis and empirical evaluations, we show the superiority of the proposed approach.
Our research is closely connected with data-centric artificial intelligence (AI) [39, 54, 64]. Here, the emphasis lies in the quality, availability, and management of data as foundational elements for constructing effective Al models and applications. The importance sampling technique developed in this paper proves valuable for processing imperfect data.
Furthermore, our methods can extend beyond the scope of consideration in this paper. To illustrate, the core concept of data re-weighting and selection can find utility in the realm of large language models. In specific downstream tasks with limited expert data, can judiciously select set of pre-training tasks to construct supplementary data and to enhance overall performance of language models; for additional insights, please refer to recent progress in [58, 18]. Other potential avenues for eeileeeepppttiio
future exploration include the extension to multi-task imitation learning, as well as the unsupervised case where the expert data is not available."
Overall, our findings demonstrate the potential of improving imitation learning performance by leveraging diverse data sources through effective data selection. We aspire for this work to serve as inspiration for future advancements in the field.
Acknowledgment
We thank Congliang Chen for discussing a technical lemma. The work of Yang Yu is supported by National Key Research and Development Program of China (2020AA00107200) NSFC (61876077), and Collaborative Innovation Center of Novel Software Technology and Industrialization. The work of Luo is supported in part by the National Key Research and Development Project under grant 2022YFA1003900 and in part by the Guangdong Provincial Key Laboratory of Big Data Computing.
'In this scenario, we can consider using a small fraction of imperfect data to reconstruct a surrogate expert policy and expert data (e.g., via majority voting). Subsequently, we can regard the remaining imperfect data as supplementary and apply the proposed framework.
10

---

References
[1] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in Neural Information Processing Systems 33, pages 20095-20107, 2020.
[2] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, pages 104-114, 2020.
[3] Brenna D Argall, Sonia Chernova, Manuela Veloso, and Brett Browning. A survey of robot learning from demonstration. Robotics and Autonomous Systems, 57(5):469 483,, 2009.
[4] Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilib- rium in generative adversarial nets (gans). In Proceedings of the 34th International Conference on Machine Leurning, pages 224-232, 2017.
[5] Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 17:253-279, 2013.
[6] Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In Proceedings of the 36th International Conference on Machine Learning, pages 783 2019.
[7] Daniel S Brown, Wonjoon Goo, and Scott Niekum. Better-than-demonssaatr imitation learning via automatically-rankee demonstrations. In Conference on robot learning, pages 330-359. PMLR, 2020.
[8] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In Advances Neural Information Processing Systems 33, pages 1877-1901, 2020.
[9] Jonathan Chang, Masatoshi Uehara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. In Advances in Neural Information Processing Systems 34, pages 965-979, 2021.
[10] Jinglin Chen and Nan Jiang. Information-theorrtie considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, pages 1042-1051, 2019.
[11] Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances in Neural Information Processing Systems 23, pages
2010.
[12] Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[13] Dmitriy Drusvyatsky and Adrian S Lewis. Error bounds, quadratic growth, and linear conver- gence of proximal methods. Mathematics of Operations Research, 43(3)9919-948, 2018.
[14] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In Proceedings of the 33rd International Conference on Machine Learning. pages 1329-1338, 2016.
[15] Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. In Advances in Neural Information Processing Systems 33, pages 1 11996-12007 2020.
[16] Seyed Kamyar Seyed Ghasemipour, Richard S. Zemel, and Shixiang Gu. A divergence mini- mization perspective on imitation learning methods. Proceedings of the 3rd Annual Conference on Robot Learning, pages 1259-1277, 2019.

---

[17] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems 27, pages 2672-2680, 2014.
[18) Suriya Gunasekar, Yi Zhang, Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi. Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, et al. Textbooks are all you need. arXiv preprint arXiv:2306. /644, 2023.
[19] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, pages 1856-1865, 2018.
[20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[21] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems 29, pages 4565-4573, 2016.
[22] Junyuan Hong, Lingjuan Lyu, Jiayu Zhou, and Michael Spranger. Outsourcing training without uploading data via efficient collaborative open-source sampling. In Advances in Neural Information Processing Systems 35, pages 20133-20146 2022.
[23] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak- jojakk-ojjsiiwiczz condition. In Proceeddings of The European Con- ference on Machine Learning and Principles and Practice of Knowledge Diseovery Databases, pages 195-811,22 2016.
[24] Geon- HyeonH Kim, Jongmin Lee, Youngsoo Jang, Hongseok Yang, and Kee-Eung Kim. Lob- sdice: Offline learning from observation via stationary distribution correction estimation. In Advances in Neural Information Processing Systems 35, pages 8252-8264, 2022.
[25] Geon-Hyeony Kim, Seokin Seo, Jongmin Lee, Wonseok Jeon, HyeongJoo Hwang, Hongseok Yang, and Kee-Eung Kim. DemoDICE: Offline imitation learning with supplementary imperfect demonstrations. Proceedings of the 10th International Conference on Learning Representations, 2022.
[26] Ilya Kostrikov, Kumar Krishna Agrawal, Debidatta Dwibedi, Sergey Levine, and Jonathan Tompson. crriimiinttor-ator-rriii Addressing sample inefficiency and reward bias in ad- versarial imitation learning. In Proceedings of the 7th International Conference on Learning Representations, 2019.
[27] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. Journal of Machine Learning Research, 17(39):1-40, 2016.
[28] Ziniu Li, Tian Xu, Yang Yu, and Zhi-Quan Luo. Rethinking valuedice: Does it really improve performance? arXiv preprint arXiv:2202. 02468, 2022.
[29] Anqi Li, Byron Boots, and Ching-An Cheng. Mahalo: Unifying offline reinforcement learning and imitation learning from observations. arXiv preprint arXiv:233../7156, 2023.
[30] Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(3):447-461, 2015.
[31] Liu Liu, Ziyang Tang. Lanqing Li, and Dijun Luo. Robust imitation learning from corrupted demonstrations. arXiv preprint arXiv:2201. 2..iv:220011/5944 /2594, 2022.
[32] Yecheng Jason Ma, Andrew Shen, Dinesh Jayaraman, and Osbert Bastani. Smodice: Versatile offline imitation learning via state occupancy matching. In Prooceedings of the 39th International Conference on Machine Learming, pages 14639- 14663, 2022.
[33] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
12

---

[34] Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J. Andrew Bagnell, Pieter Abbeel, and Jan Peters. An algorithmic perspective on imitation learning. Foundations and Trends Robotic, 7(1-2):1-179, 2018.
[35] Yunpeng Pan, Ching-An Cheng, Kamil Saigol, Keuntaek Lee, Xinyan Yan, Evangelos Theodorou, and Byron Boots. Agile autonomous driving using end-to-end deep imitation learning. arXiv preprint MiXiv1709.07774 2017.
[36] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1406-1415, 2019.
[37] Xue Bin Peng. Aviral Kumar, Grace Zhang, and Sergey Levine. weightg Simple and scalable off- off-policy reinforcement learning, arXiv preprint arXiv:1910000117,, 2019.
[38] Jan Peters and Stefan Schaal. Reinforcement learning by reward-weighter regression for operational space control. In Machine Learning, Proceedings of the 24th International Conference on Machine Learning, pages 745-750, 2007.
[39] Neoklis Polyzotis and Matei Zaharia. What data-centric ai learn from data and ml engineer- ing? arXiv preprint (.xxv:2//2.064::: 2021.
[40] Dean Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3(1):88-99)) 1991.
[41] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
[42] Nived Rajaraman, Lin F. Yang, Jiantao Jiao, and Kannan Ramchandran. Toward the fundamental limits of imitation learning. In Advances in Neural Information Processing Systems 33, pages 2924, 2020.
[43] Nived Rajaraman, Yanjun Han, Lin Yang. Jingho Liu, Jiantao Jiao, and Kannan Ramchandran. On the value of interaction and function approximation in imitation learning. In Advances in Neural Information Processing Systems 34, pages 1325-1336, 2021.
[44] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the 13rd International Conference on Artificial Intelligence and Statistics, pages 661-668, 2010.
[45] Fumihiro Sasaki and Ryota Yamashina. Behavioral cloning from noisy demonstrations. In Proceedings of the 9th International Conference on Learning Representations, 2021.
[46] Alexander Shapiro. Monte carlo sampling methods. Handbooks in operations research and management science, 10:353-425, 2003.
[47] Harshit Sikchi, Qinqing Zheng, Amy Zhang, and Scott Nickum. Dual rl: Unification and new methods for reinforcement and imitation learning. In Sixteenth European Workshop on Reinforcement Learning, 2023.
[48] Jonathan Spencer, Sanjiban Choudhury, Arun Venkatraman, Brian Ziebart, and J Andrew Bagnell. Feedback in imitation learning: The three regimes of covariate shift. arXiv preprint arXiv:2102.0282 2021.
[49] Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul von Bünau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application covariate shift adaptation. In Advances in Neural Information Processing Systems 20, pages 1433-1440, 2007.
[50] Umar Syed. Michael H. Bowling, and Robert E. Schapire. Apprenticeship learning using linear programming. In William W. Cohen, Andrew McCallum, and Sam T. Roweis, editors, Proceedings of the 25th International Conference on Machine Learning, pages 1032-1039, 2008.
[51] Voot Tangkaratt, Bo Han, Mohammad Emtiyaz Khan, and Masashi Sugiyama. Variational imitation learning with diverse-quality demonstrations. In Proceedings of the 37th International Conference on Machine Learning, pages 9407-9417, 2020.
13

---

[52] Yunke Wang, Chang Xu, Bo Du, and Honglak Lee. Learning to weight imperfect demonstrations. In Proceedings of the 38th International Conference on Machine Learning. pages 10961-10970, 2021.
[53] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the deviation of the empirical distribution. Hewlent- Packard Labs, Techical Report, 2003.
[54] Steven Euijong Whang, Yuji Roh, Hwanjun Song, and Jae-Gil Lee. Data collection and quality challenges in deep learning: A data-centric ai perspective. The VLDB Journal, pages 1-23, 2023.
[55] Grover J Whitehurst and Ross Vasta. Is language acquired through imitation? Journal of Psycholinguistic Research, 4:37-59, 1975.
[56] Yueh-Hua Wu, Nontawat Charoenphakdee, Han Bao, Voot Tangkaratt, and Masashi Sugiyama. Imitation learning from imperfect demonstration. In Proceedings of the 36th International Conference on Machine Learning, pages 6818-6827 2019.
[57] Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-cfficient offline and online reinforcement learning. Advances in Neural Information Processing Systems 34, pages 27395-27407 2021.
[58] Sang Michael Xie, Shibani Santurkar, Tengyu Ma, and Percy Liang. Data selection for language models via importance resampling. arXiv preprint arXiv:2302.03169, 2023.
[59] Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments. In Advances in Neural Information Processing Systems 33, pages 15737-15749, 2020.
[60] Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments for reinforcement learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[61] Haoran Xu, Xianyuan Zhan, Honglei Yin, and Huiling Qin. ceeriminaato-weeighee offline imitation learning from suboptimal demonstrations. In Prooceedings of the 39th International Conference on Machine Learning, pages 14725-24742. 2022.
[62] Tian Xu, Ziniu Li, Yang Yu, and Zhi Zhi-Quan Luo. Understanding adversarial imitation learning in small sample regime: A stage-coupled analysis. arXiv preprint arXiv:2208.0189) 2022.
[63] Tian Xu, Ziniu Li, Yang Yu, and Zhi Qui-Quan Luo. Provably efficient adversarial imitation learning with unknown transitions. In Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence, pages 2367-2378. 2023.
[64] Daochen Zha, Zaid Pervaiz Bhat, Kwei-Herng Lai, Fan Yang. Zhimeng Jiang, Shaochen Zhong, and Xia Hu. Data-centric artificial intelligence: A survey, arXiv preprint arXiv:2303. 10158, 2023.
14

---

A Broader Impacts
This study delves into the theoretical aspects of offline imitation learning with supplementary data, and we verify our findings through experiments on established benchmarks. While this paper does not present any immediate, direct social impacts, the potential practical applications of our research could bring about positíve change. By expanding the reach of imitation learning algorithms, our work may facilitate the development of more efficient and effective solutions fields such as roboties, autonomous vehicles, and healthcare. However, we must also acknowledge that the misuse of such technology could have negative consequences, such as the manipulation of information to influence people's behavior. Therefore, it is crucial to remain vigilant in ensuring that the benefits of imitation learning are harnessed in a responsible and ethical manner.
B Additional Related Work
B.1 Imitation Learning from Imperfection
The problem considered in this paper is related to IL with single imperfect dataset [56, 6, 51, 52, 45, 31]. In particular, the supplementary dataset in our set-up can also be viewed imperfect demonstrations. However, our problem setting differs from IL with imperfect demonstrations in two key aspects. First, IL with imperfect demonstrations, they either pose strong assumptions [51, 45, 31] or require auxiliary information (e.g., confidence scores on imperfect trajectories) on the imperfect dataset [56, 6]. In contrast, we assume access to a small number of expert trajectories to identify -eexert-ddisrrbutiie
data. Second, most works [56, 6, 51, 52] in IL with imperfect demonstrations require online environment interactions while we focus on the offline setting. Additionally, a related study, [7] employed imperfect data to infer reward function. Under the assumption of the expert being strietly sub-optimal, [7] demonstrated that it is possible to learn a policy that surpasses the performance of the demonstrator by utilizing the recovered reward function.
Our research also bears relevance to the recent works by [29, 47], which aimed unify offline Reinforcement Learning (RL) and IL. Different from our approach, these studies adopt a principle akin adversarial imitation learning [50]. For a more detailed discussion, we refer readers to [29, 47]. We also observe a connection between the objective of importance sampling weighted behavior cloning (ISW-BC) and the reward-weighh weighted regression (RWR) framework introduced in [38, 37). Specifically, the training objective of ISW-BC can be likened to reward-weighted regression
d=.0).)
(RWR) with y = 0 and a reward function denoted as r(s, a) = log (s.a) Nevertheless, there exist two distinctions between the two approaches. First, RWR primarily focuses on the online setting, while our work centers around the offline setting. Second, RWR finds its application in the context of RL, where rewards are readily available. Conversely, in our imitation learning setup, the reward (or the importance sampling ratio) needs to be inferred.
B.2 Difference with DemoDICE and DWBC
Our work builds upon previous research in IL with supplementary data, specifically the algorithms DemoDICE [25] and DWBC [61]. significant distinction arises between ISW-BC and these two methods in terms of the weighting rule design. While DemoDICE and DWBC employ regularized weighting rules, our method directly estimates the importance sampling ratio. This fundamental difference can be critical as regularized weighting rules may struggle to recover the expert policy exactly even with infinite samples. We provide further elaboration on this point below.
First, DeCODICE also uses the weighted BC objective in Eq. (3). But, DemoDICE uses the weighting rule of i((s, a) xx d' (s, a)/d (s, a) (refer to the formula between Equations (19)-(20) in [25]), where d' (s, a) is computed by the expert's state-action distribution matching objective regularized by a divergence the union data distribution (refer to [25, Equations (5)-(7)):?
d= = argmin DKI((d + aDka(dlla")
s.t. d(s,a)
Ys, a.
FFor a moment, we use the notations in [25] and present their results under the stationary and -oriten MDPs. Same as the discussion of DWBC [61].
15

---

= (1- +7 P d((ss, ,d) vs. s',a'
where 7 E [0, 1) is the discount factor, > is a hyper-parameter. Due to the regularization term in the objective, it holds that d' (s, + d= (s, a), resulting in a biased weighting rule w(s a).
Second, DWBC considers different policy learning objective (refer to [61, Equation (17))):
X
min a Σ
log 7 (a|s)]
Σ
log (als))
c(1 c)
(s.a)EDR
(s,a)EDR
Σ
log ((as)
(s
where >> O, >> 0 are hyper-parameters, and is the output of the discriminator that is jointly trained with æ (refer to [61, Equation (8)):
min A Σ
[- [olog c(s, a, log [alss))]
Σ
| c(s, a, ((as(()))))
(DE
(8,0)EDS
Σ
[- c(8, a, log (als)))
(s.a)EDR
Since its input additionally incorporates log ग, the discriminator is not guaranteed to estimate the state-action distribution. Thus, the weighting in Eq. (7) loses connection with the importance sampling ratio.
C Proof of Results in Section
Recall the objective of BC Eq. (1):
π BC
E argmax
Σ
(s.4)ESxA
where di (s. a) = n a/ Nent is the empirical state-action distribution in the expert dataset, and (s, a) is the number of expert trajectories such that their state-action pairs are equal to (s, a) in time step With the tabular representations, we can obtain closed-formed solution the above optimization problem.
(e.a) if (f) > 0
BC nA
(als)
(8)
otherwise
where (s) 2 E.. n (s, a') Analogously, we also have closed-form solution for NBCU in the tabular setting:
(s.a)
if
NBCU T
(als)
( (e)
otherwise
LAT
will discuss the generalization performance NBCU later.
In the proof, we frequently use the notation S and Z. In particular, a(n) S b(n) means that there exist C. no such that ann) S Cb(n) for all 2 ng. our context, n usually refers to the number of trajectories. For any two distributions P and Q over finite set X. we define the total variation distance as
TV(P.Q) Σ -())) - Ql1
16

---

C.1 Proof of Theorem 1
When DDE 2 1, by [42, Theorem 4.2], we have the following imitation gap bound for BC:
V(= B) Epe [V = 4|S H
9
When [DE simply have that
v(=') - Ed [v BC) < H.
Therefore, we have the following unified bound.
|S V(n²) - Epe [( BO) max (IDE),1)
2 H
IDE +1
The last incquality follows that max æz, 1 2 (x + 1 for any x 2 O. Finally, notice that [DB] follows binomial distribution by Assumption 1, i.e. [DE] Bin(NVot 17). By Lemma 3, we have that E[1/(DD) E + 1)1 I Noot7, so
2
2 2|S Noo
E
[DB] +
NE
which completes the proof.
C.2 Proof of Theorem 2
For analysis, we first define the mixture state-action distribution as follows.
amix (s, a) A mdh (s, + (1 -n)djh" a). (m. V(s,a) e S S 4k [H].
m (s)
By Assumption 1, in the population level, the marginal state-action distribution of union dataset DU in time step is exactly di That is, (s, = (s, a), a(s,a,h) e x [M]. Then define the mixture policy mix induced by dmix follows.
(a,a) (s)
if dgii(ss) > ((s,a)ESxx 4h E [M]. otherwise.
mix (als)=
=
(10)
A
From the theory of Markov Decision Processes, we know that (see, e.g., [41])
Yh E [H]. V(s, a) E ES A, di mix
(s, a)
dn piix (s, a).
Therefore, we can obtain that the marginal state-action distribution of union dataset DU in time step h is exactly dr mix Then we have the following decomposition.
E [V (i NBCJ]]
[V B) V(a mix) + V(n:iix) V(n NBCU]
E [V - V( + E [[(mmix) [TTNN) V(T mix + E [( NB.U))
For (( m(T we have that
(TT - V(z Σ
(s,a) di. (s, ra (s)
h= (s.0)ESXA
H
Σ
(IW (dR"(s, (s, -dm (s, rn (n(
h= (s,0)ESxA
(1 m)
(o (s, - -5" (s,a)) (s
h=1 ESxA
(1 1) (V(TD) V(T
(11)
17

---

The last equation follows the dual formulation of policy value (see, e.g., [41]), ie., V(T) = Σ E(s.a) is exactly the imitation gap of BC when regarding = and DU as the expert policy and expert dataset, respectively. Note that mii may be stochastic policy. By [42, Theorem 4.4], we have the following imtiation gap bound
for any policy æ. Besides, notice that E [V(m=ix) V(T
|S |S log(
E mi
V(T V(TNECU) 2
(12)
Noot
Combining Eq. (11) and Eq. (12) yields that
SS] 112 log
E - - $ (1-1) (V -V(T)))V(()) +
Ntot
C.3 Proof of Proposition 1
The hard instance in Proposition 1 builds on the Standard Imitation MDP proposed in [60]] see Figure for illustration. For this MDP, each state an absorbing state, i... Pr. (s|s, a) for any and This property is mainly used to facilitate probability calculation and does not change the nature of our analysis. Furthermore, by only taking the action a² (shown in green), the agent can obtain reward of +1. Otherwise, the agent obtains reward of 0 for the other action # a! The initial state distribution is a uniform distribution, i.e., p(s) = 1/ S| for any s E S.
0
0
Green arrow: expert action
Blue arrow: non-expert action
Figure 4: The Standard Imitation MDP in [60] corresponding to prove Proposition 1.
We consider that the expert policy T always takes the action at (shown in green) while the behavioral
policy 7 always takes another action a² (shown in blue). Formally, T (a [s) 1 and ア (a²ls) =
for any s S and h [H]. It is direct calculate that ((*²) H and V(=²) = 0. The supplementary dataset D and the expert dataset D are collected according to Assumption 1. The
mixture state-action distribution (introduced in Appendix C.2) can calculated for any s E S and h E [
dn (s, aa) "plji (s,a") (5,aa)+(1) (1-1) (s,a') )= = ndd (s, aa) = np(s),
d Mmix a²) = ndd," (s, (5, (1- (s, (1-)))) (s, a²) = - n)
Note that in the population level, the marginal distribution of the union dataset DU in time step h is exactly amix The mixture policy induced by amix (introduced in Appendix C.2) can be formulated as
mix (a' [s) Th mix (a²ls) = 1 - n, Vs E S, E [H].
Th
Just like before, we have di. (s, a) = dmiix (s, a). The policy value of mix can be calculated as
mix Σ
(s))()))))s
Σ
(s. n/H.
h=1 (x.a)eSxA
h=1 SES
Recall from Eq. (9) that ग NBCU be formulated
n (s.a) N (s.a')
ir 1H
vh [H],
NBCU Th
(als) -
(13)
otherwise
We can view that the BC's policy learned on the union dataset mimics the mixture policy x mix In the following part, we analyze the lower bound on the imitation gap of N NICCU
(T V( N] = ((=B) )- V(r + E [V - ( [[NNCC)]
H HH + E (V mixx V (TT
18

---

(1 - ( + E [V(T - v(TNBCU)]]
Then we consider the term [V (TTTix)=
((TNBCU)).
V(m - V(TNBCUU)
ch (s, dz
NBCU (s, (s(
h= (s.a)ESxA
Σ
E
pls) (ahii((ls)) Th
NBCU (als)) (n)
(s.a)ESxA
H
E
pls) (als) Th (alo) 0}
(5.
p(s) (IT n
N (s, ()) 0}.
(s.a)ExxA
We take expectation over the randomness DU on both sides and obtain that
E
[V (T
mix - NBTU]]
(14)
H
=
E
p(s) (mh mix (als) - Th (als)) (x (xx 0)
NBCU
A=1
(s,a)E8xA
H
+
E
Σ
Σ
p(s) (I. (als) - Th
NBCU (als)) (2s 0}
(15)
Aml
(A,0)ESxA
For the first term in RHS, we have that
H
E
Σ
pls) (mm (ali)(a)s)) NBCU (alu(()ls)) (s, ()) 0}
h=1
(a.0)ESxA
Σ
Σ
p(s)ra(s.a)B) [ (mnnii((ss) 2h (BCU)) Hi 0]]
h=l
(s.0)ESxA
Σ
Σ
(P) 0) Th (als) -
NBCU (a|s) m 0)
1=
(s.0)ESxA
0.
The last equation follows the fact that F
NBCU (a|s) is an unbiased estimation of πī (als), so NBCU (als) (s) O). For the second term in Eq. (15), have that
E firmix (als)
"h
E
p(s) (M (mixx (als) Th
rn Nncu
NBCU (als))
(s) 0}
(s.0)ESxA
H
Σ
Σ
( (())r m (als) mi
NBCU (als)) THn (s) = 0]]
h=1
(8.0)
Σ
(s)) (s) = 0) T mix (als) - =
NBCU (a|s) n (s) = 0)
h=
(8.0)ESXA
H
Σ
Σ
(P) = =0) (<x)
[A) (A1)
h=
(8.0)E8XA
19

---

H
p(s)F (n)()) = =0) (1- [A]
sES
(s) = 0). ) ((s) E(s))P (s)
H
(AI)
SES
In the equation (a), we use the fact that ra (s. aa) but rh (s. a) for any a a' In the
equation (b), since each state is an absorbing state, we have that P( (8) 0) P( any h E [H]. We consider two cases to address RHS of equation (b). In the first case of ry 2 1/ AA), we directly have that
(s) (s) = 0) for
E
Σ
p(s) (mhh(((s))) Th NNN
NBCU (als)) rn(s, (als)) [I = 0} 2 0.
A=1 (x,a)ESxA
By Eq. (15), we have that
E [(T - -V(=NCCU) 20,
which implies that
E (V V(T (TTNCC))) ) (1- - V))
In the second case of 1 < 1/I we have that
H
1
Σ
p(s) (s) =) - ((11 |A| -1) exp
(a)
Niot
A
|S|
SES
Noot |S]
8 IV -(1 11) H exp
(1 ))H
2
In the inequality (a), we use that
Σ ((ss) 0) Σ - (1 SES
1
Noi
Nust
Mos)
exp
[
SES
The inequality (b) holds since we consider the range where Neot 2 |S] log(2). By Eq. (15), we have that
E mix (TT NBNU)] (1 -1-w) 7)H
2
This implies that
E [ - Vin NBCU) 2 (1- (V V(T*)) (1 - H)
2
= - (V - V(=9)).
In both cases, we prove that E -V(TT)-V((7BBBB)) the proof.
- V(TNBBOJ)] 2 (1 (1= -V (mT²)
and thus complete
D Proof of Results in Section 5
D.1 Proof of Propasition 2
In the tabular case, with the first-order optimality condition, we have (8, (dd,)))((((ss))) dy (s).)). By Eq. (5), we have
(s),)) = -d (s) x (s, = (s,
(s,a)
Hence, the learning objective (3) reduces to (1).
20

---

D.2
Proof of Lemma
Recall that
(+)
min (o.a)ED)uD))
(0. (s,
max (d'
(8.0n(s',
Then we have that
A,(0,) - (0) = min
(On, (8,
max (d),"))
(O,, On (s',
(u.D)
min
(0, on (8, a))
max (s',a')ED
(0, (s' (s', ,d')
(s.a)EDfuDd.
(4) (0n. dn (s) )} (0n, 2n ,,,,))) (0, dh (s', aa)) + (0, (0,0n()?,u?)
(0n - 0, (s a²) - 6n (s",a"))
$ 0 0|| 1s a 6 a² 2
In inequality (a), we utilize the facts that (st,at) E (s.) (0n, (s, a)) and
(s², argmax (s.)ED (9n: (s, a))- Inequality (b) follows the Cauchy-Sehwee Schwarz inequality. Let La (s ( a²) (s a²)]| and we finish the proof.
D.3
Proof of Lemma
First, by Taylor's Theorem, there exists 8y E {0 E Rd 0r 0% t(O, - -8)), Vt E [0, 1]} such that
LA (0,) = (0)) + (VLx On 0%) + 2 (0n -0, (0,) (0n - 0%)
1 0, - 0% T L. (8%) (0, 0%)
= ((,) +
(16)
The last equality follows the optimality condition that L., (0;) = 0. Then, our strategy is to prove that the smallest eigenvalue of the Hessian matrix V ()) is positive, i.., Amin (V (0)) > We first calculate the Hessian matrix V L²L, Given DE and DV, we define the function [((DF|+|DD)) - IR as
DE Σ g(v)
DV
G(o)
A
+
DU Σ g(0;),
DE
where U; is the i-th element in the vector E R(DD=H1DD real-valued function. Besides, we use Bn R(ID" | to denote the matrix whose i-th row BR, = -3,0% ((sssa')))))))))))) and yı = 1 if (s*, DE. yi -1 (s', ",") & DJ. Then the objective function can be reformulated as
H|D"D and g(z) = log (1 + exp(x)) a
((,)
(s, a) [log (1 + exx (x) 0x)))] + Σ (s,a)
dy (s. a) flog (1 exp (1n(ss a), 0x)))
(x,a)
Σ
log (1 + exp (=) +
Σ
log (1 exp ((d)(s, a), R,)))
|DEl
DD
(D.
(8.0)EDU
G((BOr).
Then we have that B. Br, where
V²G(BAO))
= diag (g"((BOO)z)
d(((BoOn)
g"((BnOn) +1)
g"((BnOn) (
D
F
[DF)
DU
[D
DDU
21

---

Here (z) = o(x)(1- a(r)), where o(x) = 1/(1 + exp(-2)) is the sigmoid function. The
eigenvalues of (B, are
g"((BROn))) IDRL
J"((BOO))DOO) g"((BnOn) (B1+1) [DR]
("((BoO)) IDRI + IDU
[D + [DU|
Notice that 0g E 0r = 1(On - 02), 1I [0, 1J}. For matrix A, we use Amin (A) to denote the minimal eigenvalue of A. Here we claim that the minimum of the minimal eigenvalues of V²G(B,0" over E [0,1] is achieved at or
That is,
min (Amin (V)G(B,O*)) VI [0, 1]} min (mii (V2G(B Amin (V2G(B(0)) ))}
We prove this claim as follows. For any [0. 1]. we use ..t)................ A D (t)} denote
the eigenvalues of V²G(B,,'). For each E [| + [DL]]. we consider (t) [0, 1] - IR as function of t. Specifically,
5 ((((AA)) .).1). DEI
if [|DF]]
x²(1)
8 ("(( (B,
otherwise.
|DE|+ID41
We observe that (x) (x)(1 - (z))(( (x)))) which satisfies that Vx S 0, gz) 2 0, and
Vr 2 0, g²)(x) I O. Therefore, we have that the minimum of (t) over & E [0, 1] must be achieved at t = Or t 1. That is,
min xx(t) = min (O)) 1E
(17)
For any / E [0. 1]. we define 1' [[D + as the index of the minimal eigenvalue of GB,(
ie., Age = Amin (V))(,,)'),, Then we have that
Main(>min
Vt E [0, 1]} = min(A, (1) 4 E [0, 1]}
(a)
min Aa (0), A, :
min (0) (1)}
min (Amin , (V
Equality (a) follows (17) and equality (b) follows that X and Aç (1) are the minimal eigenvalues of V²G(B,0") and V²G(B,0"), respectively.
In summary, we derive that min (V'G( Vt E [0, 1]} = min Amiin (V'G(BAO)),, Amin (V'G(((B,) (18) which proves the previous claim.
Further, we consider Amin (n,)))
Amia (a))))Bn)
inf =ER*:[<= 1=1
T 22 Cn
inf =ER<:||>
|=1 (Bax) V²G(BBOn) (Brr)
inf =EIm(Br)
T VVDG(BBh))z
(ea)((B)) |1 inf
Amin (V²G(BAOA)
2 inf
|| min( Amin (V2G(B,0)), Amin Amin (V'G((BO'))
=TTm Bx)
Here Tm(Br) {a Rd :2 B, ||a||| 1). The last inequality follows Eq. (18).
Recall we assume that rank(An) = d, so we have that rank = Thus, Im Ba) is a set of vectors with positive norms, i.c., inf inf=elu(B.)) |||||| > O. Besides, since (z) (=) o(x) > 0. we also have that
minfAmiu (V²G(B,)') Ami (V'G
0.
22

---

In summary, we obtain that
2 min(Amin minnAmin(V"'G((BB (V2G(B,0))) Amin (V > 0.
Amin (v2C((0)) 2
[|=1]] inf (B,)
Then, with Eq. (16), there exists
||zl| The (sciint(e) (Ell(BB)
inf
min (iina (V Amia Amia((
such that
2 (0%) 2 110 0%,1
which completes the proof.
D.4
Proof of Theorem 3
First, invoking Lemma with = 0% yields that
An (0%) An Ln 00, - 071l
(f% Φn (s, a)) and (s', a') E argmax, (s.0)ED) (rg)) (0% on (s, a)). Then, by Lemma 2, there exists Tn > 0 such that
Here L, (l a) - (5 | with (s,a)
(O,) 2 La T 1|02-0212
This directly implies an upper bound of the distance between 0/ and 9%
(On( - (0)))
0, -0 =
Th
If the feature is designed such that 2(Ca(0N)-Cn(0:) An(ds) Ix
holds, we further have that
Th
0 0ill (On)/ Ln. Then we get that
(x())) 2 (0,) - Ln 110, 0% > 0,
which completes the proof of the first statement.
Then we proceed to prove the imitation gap bound. We first identify the property of n ISW-BC Recall the objective of WBCU.
H
π ISW-BC E aargmax
Σ
Σ
2 (x x [wn(s, a) log Tn (a]s)] x T (wn(s, a) 2 o1
1=1 (sA))SXA
For any state with EaEA di condition, we have
2 20 > o, with the first-order optimality
(s 2
ISW-BC
(als)
TA
EnEd dy a), (s, 2 8) For an expert state s with d (s) > 0f (s, (s)) E DD U D we have that (0h (s Th (s))) > (0) on (n a)), V(s,a) D This is due the first statement that (07) > 0 in this theorem. Recall that
1
en (n(8, 02)
cn az 0%) 1 exp(( (8, as,a).))))))) 07))
and wP (s, 1 Cn (s, a: 05)
wp (s, a) for any (s) D This implies that we can find a 8 such that I [wn Th {s)) 2 8] = for any (s, t (s() DE D and I [wn (s, a) 5] 0 for any (s,a) D 3.2 Based the above analytical form of ISW-BC
We can further obtain that "
23

---

we have that π BSW-BC (T (s)]s) = 1 for any (s, (s)) E D UD In summary, for any state with (s, (+)) E DR. UD we have that Th.
JSW-BC (Th ( =.
With the above property of π ISW-BC we proceed to analyze the policy value gap. According to [42, Lemma 4.3]. we have
H
V(Th) - V( BCI
S H
(TV (T)()))) Th
JSW-RC (-1s))]
(1)
Pum1
Since T. is assumed to be deterministic, we have
V(TB)- V (1 (SW S
H
E snudh
E Bawrksw.Bocin [L{a + (+())
(.)
I (T & D u DDD.
E
seudg
R
H
ll ((ss $ D }. (()
H
E
1=1
Inequality (a) follows the property of IC derived above. In particular, for any state s with (8, (x)) E DR. U D. we have that ni ISW-BCCTT ())))) = 1. Equation (b) holds due to the
Assumption 2. In particular, for expert state that dz (s) 0, the events of (s, (s)) $ DE. U U and (s, (s)) & Dj are equivalent.
Moreover, take the expectation over DV on both sides and obtain that
E (1 V [SW-BC)
H
d
E (-)
P ((s [()) $ DH)
h=1
H
H
dh (s) ((s, [s)) $ DDD))
h=1 8ES
According to Assumption 1, we have that
dg (s)) = ndl (s, (s)) + (1 n)dk (8, (s))
(a)
(s, n (s)) + (1 17) di (s,
2 ndh
(1
n)
di (s, (R)).
Inequality (a) follows the definition of μ in Theorem 3: for any hs E x [H], we have d=
dy (s, T (T)) (s, (x S μ. Then we obtain that
(V - V (SW-BC)) H
dh (s) - (s) (s)))
H H h=1 SES
((s, (s)) & D.).
(1- m)pp
For each (s, h) S x
[H]. we observe that
+f ((s, T (s)) $ D = (s, R (s)) (1 di (s, m (s))) Nest <
9.N
Here the last inequality follows Lemma 5. Consequently, we can derive that
H
4H S
ΣΣ
d ())) ((s, o ((s) $ DD) S
9Nett
A=1
24

---

which further implies that
I [V(mT) V(x S 17
1
4H2|S|
4H2|S1 9 (NE + Ns/u)
(1 n)/u/
9Noo
We complete the proof.
D.5
An Example Corresponding to Theorem 3
In this section, we provide an example that illustrates the required feature design in Theorem can hold.
Example To illustrate Theorem 3, we consider an example in the feature space RR. particular, for time step h E [H], we have the expert dataset and supplementary dataset as follows.
D { a01))
a())) } D { {((t))att)) (s(3)) .a(3)
D {(510) .a()) } Di. { (5(()) (a(o))
The corresponding features
@h (1) , _a(1) = =00,1)T, on (1(2) .(()) - 1 --))
1 T
(3) (3) Φ
= 0, 00-2
Φh (s(4) (((1))(()) = (-1,0)
Notice that the set of appert-style samples D U {(s(), ()))), ), a and the set of non-expert-style samples is D = ((x(3), a(3)) It is direct to calculate that the ground- truth parameter that achieves the maximum margin among unit vectors is 6 = (-v2/22 v 2 and the maximum margin is (O())) = 22/2. According to Eq. (6), for On (fp.11 0n.2) the optimization objective is
(0))
=Σ (s,a)
dii a) [log exp (=(( 0n)))|+ Σ
(s flog (1 exp ((on(s 0,)))
(s.a)
1
(log (1 + exp (-0,,)) + log (1 + exp (0h,1)))
2
1
log (1 + exp (0n.2)) + log
1 exx
-
1
+
4
2
1
log 1 + exp
1 (-00m.))
+ log (1 exp (- (0h))))
4
We apply CVXPY [12] to calculate the optimal solution 0% (-0.310, 0.993)T and the objective values L.. (0,) 1.287, (0,) 1.309. Furthermore, we calculate the Lipschitz coefficient T.,, appears in Lemma 1.
(2) (2)
argmin (0, (n(s,))), (5(3) ()) E argmax (0% dn (s, a)), (B.D)EDFuDS1
(s,a)ED))
V2
=,= On (n= (2) (s (3)
Then we calculate the parameter of strong convexity Th appears in Lemma 2. Based on the proof of Lemma 2, our strategy is to calculate the minimal eigenvalue of the Hessian matrix.
First, for 0,, = -(...10 T, the gradient of (n(0)) is
(Op)
=- Σ
((0,,))(-((063.))...)) +
N (s, (1)n(8, (a.))SSAA
Σ
(s,))E8XA
25

---

= (220(0..) _ - 8 50( - 4 (0h.2) 2
1
-
1
1
(-01.2)
1
-
0h.2)
Here (xx) = 1/(1 + (xxp(=x)) for R. is the sigmoid function. Then the Hessian matrix at fn is
(On) (0,,)) + fo (2)
(0, + to (60ma))
0
where f(x) (1) o(x)) and f(x) f(-z)) For any t [0, 1). the eigenvalues of the Hessian
matrix at 0% On + t00 0n) are
1 T (2%).) 7 10%22) Too (3%)))
- ((0
Now, we calculate the minimal eigenvalues of V2 Ln (0))). We consider the function
3 7 (z) + g(z)
1
Va E |a, b).
2
The gradient is
1 32
2²) (1 1
1
_リt (1-
) (-)))
g((x) (())=)()))- 20(x)) + o
We observe that Vx 0, (z) 2 0, and Vx 2 0. (x) 5 0. Thus, we have that the minimum of g(x) must be achieved arguments, we know that the minimal eigenvalue is 9(0.993) ss 0.163 and Tn zs 0.163. Then we can calculate that
a or b. Besides, we have that g(z) g(-x). With the above
2 (Cn(On) - Ln(())) so 0.520,
(O,) 1.
Lb
The inequality in Theorem 3 holds.
E Discussion
In the main text, focus the tabular representations for policies. Furthermore, consider trajectory sampling procedure for behavior policy in collecting the supplementary dataset. We present two possible extensions in this section.
E.1 Function Approximation of Policies
In the main text, the theoretical analysis for BC-based algorithms considers the tabular setting in policy learning where a table function represents the policy. Here we provide an analysis of BC with general function approximation in policy learning. Notice that the algorithms considered in this paper (i.e., BC, NBCU and ISW-BC) can be unified under the framework of maximum likelihood estimation (MLE)*. Therefore, the theoretical results in the main text can also be extended to the setting of general function approximation by similar analysis.
Assume that the learner is access to finite function class II { = (T1 T2. TT)). where TA - A (.A) could be any function (e.g., neural networks). For simplicity of analysis, we assume that IT is finite class. Notice that the algorithms considered in this paper are BC and its variants, which all take the principle of maximum likelihood estimation (MLE). The theoretical analysis of these algorithms based on the following inequality:
H
- V(m) S
Σ E h=1
TV (T (1)), (1))
())
Therefore, the key is to upper bound the TV distance. Take BC as example (i.e., π = π BC). By using the concentration inequality in [1, Theorem 21], we obtain that for any (0, 1), when
Among these algorithms, the main difference is the weight function in the MLE objective; see Equations (1), (2) and (7).
26

---

[D 2 1, with probability at least - 8 over the randomness within D
[V2 (-1s), BC (-[s)] < log 1og(1100)) S B
(19)
[DE
With additional efforts (by using union bound and Jensen's inequality), we have the following result. Theorem 4 (BC with Function Approximation). Under Assumption In the general function approximation setting, additionally assume that x E II If we apply BC on the expert data, we have
O H log( (T))
- V -
NE
where the expectation taken over the randomness in the dataset collection.
The detailed proof is deferred to Appendix F. Compared with Theorem I, we notice that the change in theoretical bound is that ([S))/g) is replaced by O[ H Ng)/NE). Such change is expected for other algorithms (e.g.. NBCU and WBCU), so our theoretical implications still hold. We leave the detailed analysis for future works.
E.2 Supplementary Data with Corruption
In the main text, consider the trajectory sampling procedure in Assumption 1. However, in some cases, the supplementary data can poisoned and corrupted by an adversary. For example, although the human expert demonstrates optimal trajectory, the recorder the recording system possibly corrupts the data by accident or on purpose. Data corruption is one of the main security threats to imitation learning methods [31]. Therefore, it valuable to investigate the robustness of the presented algorithms in this poison setting. Supplementary data with corruption is partially investigated in our experiments under the noisy expert setting, which we argue have large state-action distribution shift.
Assumption 3 (Poison Setting). The supplementary dataset D and expert dataset DE are collected in the following way: each time, with probability τ), we rollout the expert policy collect trajectory. With probability 1 - TJ, we still rollout the expert policy to collect a trajectory but with probability - rÍ', the actions along the sampled trajectory are replaced with actions uniformly sampled from the action space. Such an experiment is independent and identically conducted by Noot times.
Theorem 5 (NBCU the Poison Setting). Under Assumption
the tabular case, for any
77 E (0, 1], we have
E (((NB))(((BCCU)))) - - 1/12
(1
1) A +
S|AA Nint
+
H12
where the expectation is taken over the randonness in the dataset collection. Theorem (ISW-BC in the Poison Setting). Under Assumptions and 3, if the feature is designed
such that / 2( (2(u(()))) (k(()))
An(On)) holds, we have the imitation gap bound
Ta
12|
B[V(* VST.SW-BC)) = NE + N
Proofs of Theorem and Theorem be found in Appendix Compared with the imitation gap of NBCU, there is no non non-vanishing gap due to the corrupted actions in the imitation gap of ISW-BC. This means that ISW-BC still robust in this setting.
F Proof of Results in Section E
F1 Proof of Theorem 4
According to [42, Lemma 4.3), have
(T*=) V V(
B [V (TT)) T (-1s))
h=1
27

---

With [1, Theorem 211, when [DF] 2 1, for any 8 E (0, 1), with probability at least 8 over the
randommess within D we have that
BC (-1s)) 2 log( [6] [TV2 (T (-1s), Th
B B ())
[DE]
With union bound, with probability at least 6, for all h [H], it holds that
BC (-1s)) 2 log [T H1/)
E () (.) [TV2 (m Th
DD
which implies that
V(T - VTx
S H
E
[TV (+)), (+1s)
shudh ())
h=1
(a)
H
()
BC (-1s)) TV (m)())s), Th
lo H/6)
S V2H2
[DE
Inequality (a) follows Jensen's 's inequality. Taking expectation the randomness within DE yields that
logí (0)(()))/0)
Ede [(TT)) (( s 811 + + 8)V2H2
DE
(a)
D
H
+
1 (1-
D
V2H²
log(2 IT| DB
De
(V2+1) H²
DE
[D
$ 4H22 log(4 (
[DE
Equation (a) holds due to the choice that = L/ ). For [DE = 0, we directly have that
EDE [V (CT < H.
Therefore, for any [D 2 O, we have that
1og(4[11]/ max [DEI,1) 13)
Eps V (T7 - (T) S 4HH
m
We consider real-valued function f(x) log(cx)) ) for x 2 where e [T] H 4. Its gradient function is f'(x)) (1 log(cx))/=** < 0 when > 1. Then we know that f(x) is decreasing as
z increases. Furthermore, we have that max[/DE 11 Z (IDE) 1)/2 when [D 2 Then we
obtain
Log(4/[I]H) max([DD 1})
EpE [V(=B) BC] < 4H²
max[[DE).11 1]
2 log( 4 [| + 1))
< 4H²
DD +
Taking expectation over the random variable |
Bin (Not 7) yields that
+ 1)) 2 log( 4 II| ([DE
E [ - V s 4H'E
[
+
28

---

2 loog(41)) ((DE) + 1))
411²
[DE]
Inequality (a) follows Jensen's inequality. E (0, 1], where 411/
We consider the function g(x) = - - log(s/c) for
(z) = - (loo(2//o) + 2 0, (0(x)= 0. Ve E (0, 1]. g' g'(x)
Thus, g(x) is a concave function. By Jensen's 's inequality, we have that [[g - (([[a)) can derive that
Then we
2 4
IT H(DEE)
+ 1))
E [( -V(x I 4H²
E
[DE +
4V2H²
E
9
|DE] +
1
S 4V2HH²
E
| +1
(4)
$ 4V
NE
[og(4[I[|HNBB
S <V22H2
NE
In inequality (a), we use the facts that g((x) 2 0 and E [1/([DE) + 1)] S 1/Ne from Lemma 3. We complete the proof.
F.2 Proof of Theorem
We first analyze the data distribution in DU_ According to Assumption 3, we summarize the sampling procedure of trajectories in DU follows. Each time, we rollout the expert policy collect trajectory. Furthermore, with the probability of (1 7) r/)), the actions along the sampled expert trajectory are replaced with actions uniformly sampled from the action space. Then put this
poisoned expert trajectory into DU, Otherwise, with the probability of 1 1 - (1) (1)=-))),, we directly put the original expert trajectory into DU Therefore, we can formulate the marginal distribution of the state-action pairs in time step h in DU For each (s, a, h) E S x A x [H].
1
(H a) = (1 - 7)(1 - x/)) d (s, + 1) of d
A
dy Σ d (s) di (s).
aEA
Then we proceed analyze the imitation gap. Similar to the proof of Theorem 2, according [42, Lemma 4.3], we have
H
V(T²) - (( S
H
E
TV (TB(.))), n
NBCU (-1s))
h=1
Again, we introduce the definition of the policy mix
d (s.0)
if (s) = dh (s) > O,
V(s, E x A, Vh E [H) x mix (als) =
(e)
otherwise.
T
In particular, if df O, we have that
mix (a|s) = d. (s.aa a)
(s) = (1 - (1 - (1 -7')) (
+ (1- 7)(1 - v/') A
Th
29

---

Then we decompose the imitation gap into two parts.
V(x")
V(T )
H
TV (+))),), NBCU (-1s)) (-C((-))))
Fh
H
H
H
TTh B TV (1s), Th mix (-1s)) + Σ
s (.) [V (*x mix (-1s), NBCU (-1s))
Famm
We first analyze the first term in RHS. For certain (s, hb) such (x) = dh (8) > 0, we have that
TV (-1s), nh (-1s) (+s)) =
Σ mix (als)
ah (1)
Σ xx)
(1- (1 - --7)(1 1/)) (als)) (1- n) - n |
= (1 - 1) - 1/') (1- -111)
Therefore, we can derive that
H
TV (T mix (-1s)) S (1 n)(1 -)(1-1))H² H/2 (1 1
A
h=1
Now we analyze the second term of
B p()
TV (Th
mix (-18), (-1)) x
NBCU (-1s))
h=1
Recall the formula of n NBCU
(s.a)
if n >
Th
NBCU
(a|s)
=
nx (e)
otherwise
[
Notice that n NBCU is the maximum likelihood estimation of miix According to the concentration
inequality of total variation [53], for each hs E S x [H), for any fixed 5 E (0, 1), when n (s) > 0,
with probability at least 8, we have
TV (m mix (118), (11)) Th
NBCU (-18)) S
n (s(ss)
When n (8) = 0, we have that
TV (ixi (+Is), nh NBCU (-1s)) < 1 S log(38). By combining the above two inequalities, for each (s, we have
[f]] with probability at least
A log(3/5)
NBCU (BCU)))s) < TV (m Th
max(n! (s),
Applying union bound yields that with probability at least 5/2, for all (s, S x [M].
A (og
TV (m)t mix (-Is),
NBCU (-1s)) -
max (ax), (s),
Then we have that
H
H
E s (+)
(TV (.1s), Th
NBCU [)))s-)ss
30

---

H
Al log H
<
sndd (1)
max max(n) n [s),1}
h=1
[V max ( (9),
= Hv V
B (n () h=1
H
= H Lo
(s)
max (naxff/(s))
k=1 SES
dh (s)
-
max (m (s)
#ES
Here the last inequality follows Cauchy-Swarta inequality. Notice that n (s) is the number of times that the state appears in D in time step h and thus follows the Binomial distribution of Bin( Noot d% (s)). By applying Lemma 4, for each h), with probability least 5, we have
d E (s)
8log(1/8)
max I (m (s).
Nio
By union bound, with probability at least 1 - 8/2, for all (s,h) E x [A]
dr R (s)
8 logg (log(2) (18))/8))
max(n (s),
Noo
Then, with probability at least we have
8|8 |A| log 16g)(6]/) (8/5)
H Σ a (-) TV (TTi Th
NBCU (-1s)) S 12
Noot
Finally, we upper bound the imitation gap. With probability at least
5, we have
1/) (1
1
8|S|||| log" (G|S H/0)
V(xB)- ((T < <1 (1- (1--)(1-1)))
+ H²2
|A|
Noot
We set H/Noo and obtain that E [v(T") [B
(1-n)(1-1)) (11) (1-
1 [A]
8|S||A log 2 H/))
88 + (1- - 6) (1-nn(1=
+ H22
Nen
< H² Noo
+ (1 11 -n/) (1-
1
8|S |||| 1ogg(6)444)))))
+ H2
A
Niot
(1 (1 7/) (1 LAI ) + 4H²
2/5 A log (6).))
Noo:
On the other hand, we directly have BV( NBCN) & H. We complete the proof.
F.3 Proof of Theorem
In the poison setting, we can conduct the same analysis as in the proof of Theorem 3 and demonstrate that म. ISW-BC (*)(s) ( = 1, V(s, ((s)) [s)) E DE U S where DE is the set of state-action pairs in
DE in time step h and DSS {(, DJ : di (s) 0,a (+)), According [42, Lemma
4.3]. we have
H Σ
(TT - -1 ISW-BC) < H
a (() (-) TV (11s),) Th
JSW-BC (-1s))]
A=
31

---

Since the expert policy is assumed to be deterministic, we can obtain
V(Th) VV
H
E
E Bawrksw.Boiin
[I (
(+)
hm
F [s (s)) & DR uD }}
H
())
h=1
Let DS,clean denote the non-corrupted dataset in DS. Then can obtain that
V(rB)-V(rt - V(-
(a)
H
Σ
E
[ (((s,TE(s) DE U D.D. cleeau)
}
soudh
(
M
Σ
oh (s)1 ( (R)) & D D S.clean
A=1sES
where DScllean denotes the set of state-action pairs in DS,clean in time step h. Inequality (a) follows h S.clean DDd. since DS,eleun is collected by the expert policy, Taking expectation over the
that D D randomness in DE and DS,clean on both sides yields that
Epe DS cleom [V V(T [SW-BC)] H ΣE
dr (s)IP (0s (6)) & D D )
k=
Notice that both D and DS,elean are collected by the expert policy. Then if |DF + [DS,cloan| 2 1. we can calculate that for each (s, h) E [H],
1D |D*)+|DS
di (s) (s, (s)) $ DR U DR. s...lea)) = dr (s) (1 dr (s)
4 9 + [DS,clean|)
where the last inequality follows Lemma 5. If [D + SScleaan = 0, we directly have that ch. (s) (s, (s)) & D U.D. cllaan We unify the above two inequalities and get that d (s) P (s, (F()s) & D U UDD
max D + D chernn 1]
max | + DSS.leau 1}
Now we proceed to upper bound the imitation gap.
EE Dilio [V - 1SW-BB))
< H Σ
Σ
R di. (s)IP ((s, [()) & DD U UDS S.clean
h= 1 sES
S
max{/DE + [DS,clean|
Note that F + [SS.len Bin(Neot 7 + (1 - n)/r)) Taking expectation with respect to
[DE| + [DS.clean| yields that
HS
E [[ V(T [SW-BB]]] E
max ( EDE + [DS, 1}
2|S]H2
< E
[DE + DDS,cleau
(a)
2/S
Nos (7 (1 7)-)))
2|S(H
Ng + 1/'Ns
32

---

Inequality (a) follows Lemma 3. We finish the proof.
G Technical Lemmas
Lemma For any N E N+ and E (0, 1), if the random variable X follows the binomial distribution, i.e. X Bin(N, p), then have that
E
X
++ 1
Np
Proof.
N
N!
z!(N - z)! p0 p)
I +
a=0
x!(N +1 z:) ) 1² -p)
(N + 1]!
(N 1)p
(1- (1 -l-p) N) v Np
(N 1)p
Lemma 4 (Binomial concentration (Lemma A.I in [57])). For any N E N4 and (0, 1). suppose
X Bin(Bn (p,p. Then with probability least 6, we have
8 1log(1/))
N
Lemma 5. For any N E M4 and [0, 1], consider the function f(x) == x(1 - x) then we have
Vz (0, 1]. f(x) s 9N
Proof. We calculate that (z(x) = (1 (1-z)~-1(1 (N + 1)x). is direct to have that f(x) achieves its maximum at xx 1/(NN + 1). Furthermore, have
1 (1 1
N+1
1
N+1 N
eN
9.
Inequality (a) follows that (1 + Z/N)N < exp(x), VN
2 1,
N. We complete the proof.
H Experiments Details and Additional Results
H.1 Experiment Details
In this section, we present the experiment details to facilitate the replication our results. The experiments conducted machine comprising 48 CPU cores and 4 V100 GPU cores. We repeat each experiment 5 times using different random seeds (2021, 2022, 2023, 2024, and 2025).
H.1.1 Robotic Locomotion Control
In this study, we evaluate the performance of various imitation learning algorithms on four locomotion control tasks from the MuJoCo suite: Ant-v2, HalfCheetah-v2 sooperrv2,, and Walker2d-v2. These tasks are widely used in the literature and are considered challenging benchmarks.
To train the expert policy, we use the online Soft Actor-Critic (SAC) algorithm [19] with million training steps. We implement the algorithm using the rlkit codebase, which is available at https: //github. com/rail- sesiil-berkeeee werrkeeey/rliii in Figure 5. We treat the resulting policy as the expert policy and use it to generate expert trajectories.
The training curves of the online SAC agent are shown
33

---

12500
5000
5000
10000
4003-
3000
2000
5860
2008-
2310
2000
1000
020
800
0.75
230g
0.50
0.50
1.00
0.00
Intrsstion
Inlradtion
intrrdiio Step
Figure 5: Training curves of online SAC 4 locomotion control environments.
In our experimental setup, we utilize an expert dataset comprising of expert trajectory collected by the trained SAC agent. Additionally, all algorithms are provided with supplementary dataset. There are two setting of the supplementary data.
Full Replay. The supplementary dataset is obtained from the replay buffer of the online SAC agent, which has over one million samples, equivalent to 1000+ trajectories. The rapid convergence of online SAC, as illustrated in Figure 5, implies that the replay buffer is enriched with substantial number of expert-level trajectories. As a result, we expect that utilizing the supplementary data without any modification may lead to desirable results.
Noisy Expert. The supplementary dataset comprises of 10 clean expert trajectories and 5 noisy expert trajectories. In this case, replace the action labels in the noisy trajectories with random actions drawn from [-1, 1J. This replacement creates noisy action labels for the expert states, leading to significant distribution shift at the state-action level, as noted in Remark 1. The high degree of distribution shift makes it challenging for using the supplementary data.
We use hidden-llaee multi-layer perceptron (MLP) with hidden size 256 and ReLU activation for all algorithms, as the state information in locomotion control tasks is informative by design. The codebase of DemoDICE is based on the original authors' work, which can be accessed at https://gi thub. com/KAIST AILab/ imi taatttatiinneee dice. For DWBC, we also use the authors' codebase, which is available at ht //gi thub. com/ Coom//yanhr////e /DWBC. We experimented with different hyper-parametes for both algorithms but found that the default parameters provided by the authors work well. We normalize state observations in the dataset before training all algorithms, following [25]. This is crucial for achieving satisfactory performance.
In training the discriminator of ISW-BC, we use the gradient penalty (GP) regularization, as recom- mended by [25]. We add the following loss to the original loss (4) to enforce 1-Lipschitz continuity:
min Σ (1lg(s, a; 0) 1)²
(s.a)EB
where g is the gradient of the discriminator c(s, a; 0). and B is mini-batch. This promotes the learning of smooth features and can improve generalization performance.
In our implementation of ISW-BC, we employ 2-hidden-layer MLPs ReLU activation for both the discriminator and policy networks. We use batch size of 256 and Adam optimizer with learning rate of 0.0003 for training both networks. The training objective is to maximize the likeliiod.ood. We set 0 and use gradient penalty coefficient of by default, unless otherwise stated. The training process is carried out for million iterations. We evaluate the performance every 10k iterations with 10 episodes. The normalized score in the last column of Table 2 is computed in the following way:
with 256 hidden units and
Expert performance - Agent performance
Normalized score
(20)
Expert performance - Random policy performance
H.1.2 Atari Video Games
We evaluate algorithms on a set of 5 Atari video games from the standard benchmark: Alien, MsPacman, Phoenix, Qbert, and SpaceInvaders, We preprocess the game environments using a standard set of procedures. including sticky actions with a probability of 0.25, grayscaling, downsam- pling to an image size of [84, 84], and stacking frames of 4. These procedures follow the instruc- tions provided by the dopamine codebase, which is available at https: //gps:///ttta //github. com/ google/ dopamine/ aolobmmastan puts are of shape (84, 84, 4).
dopamine/disccete /wwee/dssseeeeeeeeeeeeeeeeeeeeee wttpre/ddddceeeeedddddieaoe domains/ /atari baaarrllbb____ Lib.py. py. The final image in-
34

---

We use the replay buffer data from an online DQN agent, which is publicly available at https: datasets, // /cconolle. e. cloud. google. cww/coo///s/oo htt.///trag//eeee harge//bowwee/acee /atarittari-iii httr//aaarrrrrppple repaaa-daattssss thanks to the work of [2]. The dataset consists of 200 million frames, divided into 50 indexed buckets (ranging from to 49). However, using the entire dataset is computationally infeasible" and unnecessary for our task. Therefore, we select specific buffer buckets for imitation learning.
We choose the expert data from bucket index 49, using only the first 400K frames for training. This makes the task challenging (we find that BC performs well with 1M frames of expert data). For the full replay setting, we select supplementary data from buffer indices 45 to 48, using the first 400K frames from each bucket. This yields supplementary dataset that is 4 times larger than the expert data. In the noisy task setting, we follow the same procedure for selecting supplementary data, but replace the action labels with random labels on buffer index 45.
All agents employ the same convolutional neural network (CNN) architecture the DQN agent, consisting of three convolutional blocks. The first block applies a filter size of 8, a stride of 4, and has channel size of 32. The second block uses a filter size of 4, stride of 4, and a channel size of 64, while the third block applies a filter size of 3, stride of 4, and has a channel size of 64. All blocks use the ReLU activation function. The feature representations are flattened to a vector, on which 1 --iddeen-layer MLP with a hidden size of 512 and ReLU activation function is applied. Finally, the outputs are passed through softmax function to obtain probability distribution.
Atari games are not considered in [25, 61] and public implementations of DemoDICE and DWBC for Atari games are not available. To use these methods in the Atari environment, we extend their original implementation by replacing the MI.P used in locomotion control with the CNN described earlier. Implementing ISW-BC is a little more complicated. We use the same CNN policy network as in the other methods, but find that directly training the discriminator from scratch is less effective. This is because the discriminator tends focus on irrelevant background information instead of the decision-centric part. To overcome this issue, we build the discriminator upon the feature extractor of the policy network, leveraging its ability to extract useful information. The discriminator is MLP with ReLU activation and a hidden size of 1024: the image feature representation has dimension 512 and the action feature representation also has a dimension 512 (we randomly project one-hot discrete actions to a 5 122dimennsoon space). We find that the depth of the MLP is crucial for performance, using a depth of for the full replay setting and 3 for the noisy expert setting. We clip the importance sampling ratio for numerical stability, using minimum value of O and a maximum value of 5 for the full replay setting. and a minimum value of 0.2 and a maximum value of for the noisy expert setting. We provide ablation studies of these hyperparameters in Appendix H.2.2.
All methods were optimized using the Adam optimizer with a learning rate of 0.00025 and a batch size of 256. The training objective is to maximize the log-likelihood. The training process consisted of 200K gradient steps. Every 2K gradient steps, the algorithms were evaluated by running 10 episodes and computing the raw game scores. The normalized score in the last column of Table 3 is computed by Eq. (20).
H.1.3 Image Classification
We utilize the publicly available DomainNet dataset [36] for our experiments, which can be accessed at http://csx bu clipart, infograph, painting, quickdraw, real, and sketch, with 2103, 2626. 2472, 4000, 4864, and 2213 images, respectively. Our task involves recognizing objects from 10 different classes: bird, feather, headphones, ice_cream teapot, tiger, whale, windmill, wine _aane_sssss.. and zebra. We divided the images into training and test sets, with 80% for training and 20% for testing.
http:/vis//////// tturrc.......teeeeooo/ooooo This dataset comprises six sub-datasets:
We employ a 2-hidden-layer neural network with hidden size of 512 and ReLU activation as the classifier. To extract features from images, we utilize the pretrained ResNet-18 model (trained on ImageNet), which has a feature dimension of 512. The ResNet-18 model can be ac- cessed at https://pytors:
ht/ggeeeaaeettorcciiiieeeeeeeeee wtwpciiiiiooooodelll.l.o...mm models.
resnet18. html. We opted for this approach as training such a large convolutional neural net- work directly on the DomainNet dataset proved to be ineffective. The training objective is to minimize the cross-entrope loss. To optimize the network parameters, we use the stochastic gradient descent (SGD) optimizer with learning rate of 0.01 and momentum of 0.9. Additionally, we apply
Loadiig 200M frames requires over 500GB memory.
35

---

weight decay with a coefficient of 0.0005. The models are trained for 100 epochs with a batch size of 100, following the standard practice.
The discriminators used in ISW-BC and DWBC are implemented as 2-hidden-layer neural networks with ReLU activation. It's important as inputs. The image input is processed by the pre-trained and fixed ResNet-18, while the label input projected to the same dimension (512) by random projection matrix. The hidden size for the discriminator is set to 1024 for ISW-BC and 1025 for DWBC, as the discriminator in DWBC also takes the log- likelihood as an input. For ISW-BC, the discriminator trained independently for 100 epochs with the same optimization configuration as the classifier. Afterward, the discriminator is fixed, and its output used to compute the importance sampling ratio, which is then used to train the classifier.
that these discriminators take both the image and label
H.2
Additional Results
H.2.1
Training Curves
The training curves on the robotic locomotion control tasks are displayed in Figure 6, Figure 7 and Figure 8. The training curves on Atari video games are displayed in Figure 9 and Figure 10. The training curves on the image classification task are displayed Figure 11.
BC
NBGU
DWBC
DonuDICE
IBW
Arr-22
HaiCCheeth-12
4600
7500
8000
6000
Happer-12
6000
Walkerd-222
4000
3000
2400
2000
1000
800
8.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
beeaton
100
Dlndtoon
105
Figure 6: Training curves of algorithms on the locomotion control task in the full replay setting. Solid lines correspond to the mean performance and shaded regions correspond to the 95% confidence interval. Same as other figures.
H.2.2 Ablation Study
In this section, we present ablation studies conducted on Atari games, aiming to provide insights into the underlying working scheme our method. We specifically emphasize Atari games due to their high-dimensionall image inputs, making these tasks particularly challenging. In contrast, the other two tasks, locomotion control and image classification, involve informative vector inputs, setting them apart from the unique characteristics of Atari games.
Ablation Study on Feature Representations of Discriminator Network. Our study reveals that employing separate CNN for the discriminator yields inferior results compared to utilizing the feature extractor of the policy network. Please refer to Figure 12. Our conjecture is that training the discriminator independently may cause it to fit noise information (e.g., background). In contrast, the policy CNN network capable of learning decision-centric information, enabling an effective approach to building the discriminator network through the feature extractor of the policy network.
36

---

8C
NBCU
DWBC
DeTODICE
BNBC
4500
10000
3200
7630
1500
1000
-1500
-3200
3200
4000
2000
500
8.50
-1003
twb
Figure 7: Training curves algorithms on the locomotion control task the noisy expert setting.
BC
NBCU
DARC
DanoDICE
ISA-BC
HarChhossh-2
4500
7500
3000
5200
2500
Hepper
Walkord
3200
4:00
2400
2000
1000
800
heeatin
Hlemtto
1e5
Figure 8: Training curves of algorithms on the locomotion control task in the expert&random setting.
37

---

1930
3022
2000
2030
1930
10000 twarte
750
1330
2300
50000
103003
15:0000
200000
50000
190303
15000
200000
Figure Training curves of algorithms on the Atari games in the full replay setting.
BC
DWSSC
Demutrte Martsonen
MBCUU
Akan
1990
2520
200
1230
1998
030
1232
332
430
50000
(00003
15000
200000
10300
Ober:
Saacsiwadera
0330
4300
2930
152
10/06
200000
6300
99990
Reatton
Figure 10: Training curves of algorithms on the Atari games in the noisy expert setting.
Painting
56
40
26
52
96.0
$4.2
Tec
$3.0-
63
Figure 11: Training curves of algorithms on the image classification task using the DomainNet dataset.
38

---

MeProra
Prowni
1.000
29.00
2570
2000
1930
1992
1532
400
1932
Sakeeworrrs
752
7900
0330
432
332
3030
152
109000
200000
102003
Figure 12: Training curves of ISW-BC on the Atari games in the full replay setting. We test the performance with different feature extractors of the discriminator.
Ablation Study on Depth of Discriminator Network. We have discovered that the number of discriminator layers plays crucial role in the performance of Atari games. The training curves, depicted in both Figure 13 and Figure 14, illustrate the performance variation based on the number of layers in the discriminator network. Notably, 1-hidden-layer neural network yields the best results for the full replay setting, while a 3-hidden-layer neural network performs optimally in the noisy expert setting. It important note that this phenomenon is specific Atari games. We do not have a good explanation yet. We believe this deserves further investigation in the future work.
I5W S2N-B//umm.o...o (omrr-))))))
ISW 500-B/ymm.. Marworee
ISW B00.00mmmMM Jeyrra--
Akann
3032
Pheanx
1900
2003
2003
1000
2008
300
502
52000
189003 Parmton
159000
200000
0200
0300
532
4900
430
2320
Reation
Figure 13: Training curves of ISW-BC the Atari games in the full replay setting. We test the performance with different number of layers for the discriminator network.
H.2.3 Results on the Mix of Expert and Random Data
In the main text, we consider two types of supplementary datasets: full replay and noisy expert. Here we consider another type of supplementary datasets which consists of expert trajectories and trajectories generated by a random policy [25, 47). evaluate all methods on this new type of supplementary datasets on the robotic locomotion control tasks. In particular, the supplementary dataset contains expert trajectories and 10 random trajectories. We report the experimental results Table 5. The results show that ISW-BC outperforms NBCU significantly, demonstrating
39

---

3030
Pronir
1500
2070
2532
1200
2032
1932
+00
1990
1230
1922
932
432
Sakeewwarrs
twatte
4390
9330
432
332
2030
230
109000
100003
Figure 14: Training curves of ISW-BC on the Atari games with the noisy expert setting. We the performance with different number of layers for the discriminator network.
the robustness of ISW-BC to distribution shift. Furthermore, ISW-BC also performs better than DemoDICE and DWBC.
Table 5: Environment return of algorithms on the mixture of expert and random dataset on
locomotion control tasks
Ant
HalfCheetah
Hopper
Walker
Avg
Random
326
-280
-20
0%
Expert
5229
11115
3589
5082
100%
BC
1 1759
237
24681164
1738
38%
NBCU
4316=216
14+0
3401
1189=100
51%
DemoDICE
4097
7401
3556227
4451
83%
DWBC
3447 2220
5307 2319
32862s2
1451=14
59%
ISW-BC
4467 135
8697=so
3584:t
4528::22
88%
40


Reviews:
[{"review_id": "0pDniojoU9", "reviewer": "Reviewer_Yb9D", "summary": "In the paper, the authors focus on imitation learning (IL) when working with supplementary imperfect data. They conduct a thorough theoretical analysis to understand the limitations of IL under various dataset compositions. The authors' theoretical analysis provides insights into the bounds and constraints of IL when dealing with different types of datasets.\n\nTo address this problem, they propose a novel method called importance-sampling behavior cloning ISW-BC. The proposed method is designed to mitigate the issues associated with imperfect data in IL. This technique leverages importance sampling to assign appropriate weights to different samples, thereby effectively reducing the impact of imperfections in the training data.\n\nTo validate the effectiveness of their approach, the authors conduct extensive evaluations on a diverse set of tasks. The results indicate that the proposed method outperforms the current state-of-the-art techniques in most cases. This suggests that the importance-sampling behavior cloning method is a promising solution for tackling the problem of imitation learning with supplementary imperfect data.", "questions": "In line 310, authors claim that NBCU performs worse than BC. This would be the expected results, however in Table 2 for Ant and HalfCheetah NBCU with Noisy Expert data performs significantly better than BC. Can the authors explain this in more detail?", "limitations": "See Weaknesses", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "One strength of the paper is the authors' meticulous exploration of the various theoretical bounds that arise when working with imperfect data within the framework of BC. By dissecting these limitations, they provide a deep understanding of the challenges faced in practice, enabling researchers and practitioners to make more informed decisions when applying BC to real-world datasets.\n\nFurthermore, the authors introduce a novel method based on importance sampling, which offers a clear and intuitive approach for addressing the imperfections in the data. \n\nIn addition to their theoretical contributions, the authors demonstrate the practical relevance of their proposed method by conducting a thorough analysis on diverse tasks. This empirical evaluation validates the effectiveness of their approach across various application domains, further strengthening the paper's findings.", "weaknesses": "The authors' analysis lacks consideration of alternative methods that can effectively learn from imperfect data. [1]\n\nIn order for the method to be applied, a dataset of labeled expert demonstrations is required. In many practical applications, we do not have access to this information.\n\n[1]Better-than-Demonstrator Imitation Learning via Automatically-Ranked Demonstrations,Daniel S. Brown, Wonjoon Goo and Scott Niekum, CoRL 2019", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review and check our paper, and for your insightful comments. \n\n**Comment 1:** The authors' analysis lacks consideration of alternative methods that can effectively learn from imperfect data. [1]\n\n**Response 1:** Thank you for bringing up the work [1], which utilizes automatically generated ranked demonstrations to learn a reward function for imitation. However, unlike our analysis, [1] primarily focuses on the online setting, and its main theorem contributes significantly by enabling the learning of a policy better than the demonstrator using the recovered reward function. It is worth noting that [1] requires a different assumption, namely that the expert policy is sufficiently sub-optimal.\n\nWe will address this point in the revised paper by including the above discussion.\n\n**Comment 2:** In order for the method to be applied, a dataset of labeled expert demonstrations is required. In many practical applications, we do not have access to this information.\n\n**Response 2:** We appreciate your concern and would like to address it with two potential solutions. First, while obtaining a *complete* dataset of labeled expert demonstrations may be challenging in some practical scenarios, we believe it can be feasible and cost-effective to acquire *a few* labeled expert demonstrations (e.g., at least one expert trajectory in the locomotion control tasks considered in our experiments).\n\nAlternatively, if obtaining labeled expert demonstrations proves truly unfeasible, we propose a two-stage solution. Let us consider a mixed dataset containing both expert trajectories and non-expert trajectories. We can divide this dataset into two equal parts, denoted as $D_1$ and $D_2$. In the first stage, we infer a representative policy $\\widehat{\\pi}^{\\operatorname{E}}$ from $D_1$ and use this policy to generate labels for the corresponding trajectories in $D_1$. Subsequently, in the second stage, we apply our framework, considering $D_2$ as supplementary data. Our intuition here is that expert trajectories likely constitute the majority of the entire dataset, so the policy $\\widehat{\\pi}^{\\operatorname{E}}$ recovered from the noisy data $D_1$ can effectively act as a proxy for the expert policy.\n\n**Question 3:** In line 310, authors claim that NBCU performs worse than BC. This would be the expected results, however in Table 2 for Ant and HalfCheetah NBCU with Noisy Expert data performs significantly better than BC. Can the authors explain this in more detail?\n\n**Response 3:** Thanks for the nice observation and we have carefully examined this case. Through visualization (via PCA), we found that the state coverage (between the expert data and noisy non-expert data) is relatively nice for Ant and HalfCheetah tasks (compared with the other two tasks). Therefore, NBCU performs relatively well on these two tasks. For your reference, we have included the visualization plots in Figure 1 of a separate PDF file.\n\n---\n\nWe hope that the above answers can address your concerns satisfactorily. We would be grateful if you could re-evaluate our paper based on the above responses. We look forward to receiving your further feedback."}, {"review_id": "WpHmbgeTd3", "reviewer": "Reviewer_LjZi", "summary": "This paper studies the problem of offline imitation learning (IL) with a supplementary dataset, which can address the scarce expert data issue in pure IL. In this setting, the challenge is that the supplementary dataset may have out-of-distribution samples. This paper considers the classical method Behavioral Cloning (BC) and its variants, and proves their imitation gap bounds in offline IL with a supplementary dataset. The theoretical results show that the naïve BC on union dataset (NBCU) method suffers a non-vanishing gap, and thus may be worse than BC which only learns from the expert dataset. To address this issue, the authors propose the method Importance-sampling weighted BC (ISW-BC), which can select in-distribution samples in supplementary dataset. They prove that ISW-BC can eliminate the gap in NBCU. The experimental results also show that ISW-BC outperforms existing methods on a variety of tasks.", "questions": "The theoretical results for ISW-BC in lines 260-270 are quite complicated and difficult to understand. Can the authors give more explanations and proof sketch for these results?", "limitations": "The authors have discussed the limitations and broader impacts of this paper in the conclusion part and appendix.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper conducts a systematic theoretical study of offline IL with a supplementary dataset. The developed theory closes the gap between theory and practice and lays a foundation for further studies of this problem.\n\n2. This paper proposes a simple and effective method ISW-BC. The authors validate that ISW-BC can address the distribution shift issue in both theory and practice, which makes advances over existing methods.", "weaknesses": "1. This paper is a bit dense to read. I believe that this paper would benefit from providing more intuitions and proof sketch for the theoretical results. Besides, the authors should give more analysis of the experimental results, which can give the reader an intuitive idea about how and where the proposed algorithm improves upon existing methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time to review and provide positive feedback for our work.\n\n**Comment 1:** This paper is a bit dense to read. I believe that this paper would benefit from providing more intuitions and proof sketch for the theoretical results. Besides, the authors should give more analysis of the experimental results, which can give the reader an intuitive idea about how and where the proposed algorithm improves upon existing methods.\n\n**Response 1:** Thanks for your helpful suggestions. We will revise our paper based on your comments.\n\n**Question 2:** The theoretical results for ISW-BC in lines 260-270 are quite complicated and difficult to understand. Can the authors give more explanations and proof sketch for these results?\n\n**Response 2:** Thanks for your helpful comments. We provide a proof sketch below for your reference and we will put it in the revised paper.\n\nFirst, based on a classical reduction lemma, we can upper bound the imitation gap by the divergence between the expert policy and the learned policy distributions. \n$$\nV\\left(\\pi^{\\mathrm{E}}\\right) - V\\left(\\pi^{\\mathrm{ISW}-\\mathrm{BC}}\\right) \\leq H \\sum\\_{h=1}^H \\mathbb{E}\\_{s \\sim d\\_h^{\\mathrm{E}}(\\cdot)}\\left[\\mathrm{TV}\\left(\\pi\\_h^{\\mathrm{E}}(\\cdot \\mid s), \\pi\\_h^{\\mathrm{ISW}-\\mathrm{BC}}(\\cdot \\mid s)\\right)\\right]\n$$\nThen our target is to analyze the properties of the learned policy distribution. To achieve this goal, we derive the closed-form solution for the learned policy, on which the learned weights of samples play a crucial role. \n$$\n\\pi\\_h^{\\mathrm{ISW}-\\mathrm{BC}}(a \\mid s)=\\frac{\\widehat{d\\_h^{\\mathrm{U}}}(s, a) w\\_h(s, a) \\mathbb{I}\\left[w\\_h(s, a) \\geq \\delta\\right]}{\\sum\\_{a \\in \\mathcal{A}} \\widehat{d\\_h^{\\mathrm{U}}}(s, a) w\\_h(s, a) \\mathbb{I}\\left[w\\_h(s, a) \\geq \\delta\\right]}\n$$\nThen we continue to analyze the properties of the learned classifier which induces the weights of samples. Through a landscape-based analysis (Lemma 1 and Lemma 2), we prove that the learned classifier induces the consistent margin with the ground-truth classifier ($\\Delta\\_h (\\theta^\\star\\_h) > 0$) and thus can distinguish between in-expert-distribution samples $\\mathcal{D}^{\\text{E}}\\_h \\cup \\mathcal{D}^{\\text{S}, 1}\\_h$ and out-expert-distribution samples $\\mathcal{D}^{\\text{S}, 2}\\_h$. With this result, we further show that the learned policy matches the expert policy on states within in-expert-distribution samples $\\mathcal{D}^{\\text{E}}\\_h \\cup \\mathcal{D}^{\\text{S}, 1}\\_h$. Finally, we can obtain the improved imitation gap bound.   \n\nPlease let us know if you have further concerns about this point."}, {"review_id": "kBHzyXvmSI", "reviewer": "Reviewer_Y1mx", "summary": "The paper provides derivations of the imitation gap, the gap in performance between the trained agent and expert who provided the data, when traditional behavioural cloning (BC) is used. The specific setting assumes there is plentiful of supplementary data to train the BC agent on, but since this supplementary data may (and probably is) of poor quality (i.e., not as good as expert demonstrations), traditional BC produces less than optimal agents. The paper proposes a importance-sampling correction by training a discriminator on the dataset (to distinguish the high quality and low quality demonstrations), and then train BC using the importance-sampling correction. The results indicate the proposed method improves over BC and existing methods, while not reducing original BC performance in settings with high amount of expert data.", "questions": "1) What is the \"BC\" method shown in Tables 2, 3 and 4? Is this just \"BC\" row trained on the expert dataset only? If so, please clarify in main paper text.\n2) The \"one expert trajectory in expert dataset\" setup throughout experiments seems overly restrictive. Have you experiment with other settings, like with 5 or 10 expert trajectories in the expert dataset? Was it ensured that the \"one expert trajectory\" in the expert dataset was indeed a good demonstration? Even with a good policy, some trajectories may end up being bad.\n3)  In the object recognition task, the supplementary data is data with valid labels but with a different style. However, the focus is on \"sub-optimal policy\" data, and in other environments the supplementary data consists of different policies (\"full dataset\" setting) and outright wrong labels (\"noisy expert\"), where some actions are replaced with random ones. Following this, it seems like a more natural setup for object recognition task would be to do everything in single domain (e.g., \"Real\"), but randomly replace the sample label with a wrong label in the supplementary dataset. What is the reason behind using different sub-sets as supplementary data?\n\n### Comments\n\nNote: I do not have the expertise to comment on the mathematical derivations. I work on the assumption these are correct/throughout, and comment on the experimental setup and results.\n\n- Footnotes come after commas\n- Term \"imitation gap\" is used early on (e.g., lines 39 and 66), but not formally or informally defined. A quick definition after first use of the term would help readability.\n- Not required, but in future, please use same colors consistently between figures (e.g., same method always gets the same color). This improves paper readability quite considerably.\n- Section 3 header sounds like it is missing something (e.g., should it be \"Preliminaries\" or \"Problem setup\"?)\nNumbers in the tables are in bit different format; some (Random, Expert) seem to be in normal text mode, while rest are in math mode. Formatting should be consistent.", "limitations": "Authors have broader impact section, and correctly report the limited societal impact. Authors list some of the limitations of the method in Appendix, e.g., difficulties regarding training discriminator in the Atari domain.\n\n## Rebuttal acknowledgement\n\nI have read authors' rebuttal and new results which did address my concerns, and I updated my score from 6 to 7 (before discussion period closed).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Theoretical backing and derivation of the method.\n- Both theoretical and empirical improvements over baselines, and proposed method is more applicable than baselines (e.g., no natural extension of DemoDICE to image recognition task, as it lacks rewards).\n- Empirical results in three different settings (MuJoCo, Atari and object recognition).\n- Method is simple to implement. With a good baseline code base shared, I could see other people adapting this method and trying it out.", "weaknesses": "- Proposed method has rather small/noisy improvements in terms of metrics in the experiments.\n\t- In \"noisy expert\" setting, the proposed method is clearly better than the baselines. However this setting seems rather unrealistic (proper trajectories from a policy but actions are random). A more realistic scenario would be rollouts from a poorly trained policy, or a random agent.\n- Not a very novel setting (as evident by the number of baselines) and the solution, while well executed, is a combination of existing works in somewhat simple way.\n- Training discriminators may be problematic (which is a shared difficulty with baselines). Authors note this in the Appendix for the Atari experiments.\n- (Minor) No code available, but paper lists references to libraries and datasets used. Nevertheless, replicating the results as presented in the paper will be near-impossible, given the earlier works in ML field. I urge authors to share the code, even if it is \"messy\", so that others can build on the contributions of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and providing us with your valuable feedback. \n\n**Comment 1:** In \"noisy expert\" setting, the proposed method is clearly better than the baselines. However this setting seems rather unrealistic (proper trajectories from a policy but actions are random). A more realistic scenario would be rollouts from a poorly trained policy, or a random agent.\n\n**Response 1:**  We appreciate your concern and would like to provide two solutions to address it. On the one hand, we believe that the considered noisy expert setting is practical in some applications with potential data corruption. For example, although the human expert demonstrates an optimal trajectory, the recorder or the recording system possibly corrupts the data by accident or on purpose. Motivated by such applications, the study on the robustness to data corruption has drawn much research interest in imitation learning [R1, R2].\n\nTo further address your concern about the rollouts from non-expert policy, we have experimented the case where the supplementary dataset contains expert trajectories and trajectories collected by a random agent in the locomotion control benchmark. The experimental results show that ISW-BC outperforms NBCU significantly, implying the robustness of ISW-BC to distribution shift. Besides, ISW-BC also performs better than other baselines DemoDICE and DWBC. The detailed results are available in Table 1 in a separated pdf file. We are also planning to conduct more experiments in Atari games and include these results in the future version. \n\nReferences:\n\n[R1] Liu Liu, et al. “Robust Imitation Learning from Corrupted Demonstrations.” arXiv: 2201.12594\n\n[R2] Fumihiro Sasaki, Ryota Yamashina. “Behavioral Cloning from Noisy Demonstrations.\" ICLR 2021.\n\n**Comment 2:** No code available.\n\n**Response 2:** As promised in the Appendix, we will make our code and datasets available for public access upon acceptance. Currently, in accordance with the NeurIPS instructions, we have provided the code to the area chair via an anonymized link.\n\n**Question 3:** What is the \"BC\" method shown in Tables 2, 3 and 4? Is this just \"BC\" row trained on the expert dataset only?\n\n**Response 3:** Yes, you are correct. The \"BC\" method shown in Tables 2, 3, and 4 refers to the row labeled \"BC,\" which is trained solely on the expert dataset. We apologize for any confusion, and we will make sure to clarify this point in the later revision of the paper.\n\n**Question 4:** The \"one expert trajectory in expert dataset\" setup throughout experiments seems overly restrictive. Have you experiment with other settings, like with 5 or 10 expert trajectories in the expert dataset? Was it ensured that the \"one expert trajectory\" in the expert dataset was indeed a good demonstration? Even with a good policy, some trajectories may end up being bad.\n\n**Response 4:**  We appreciate your concern. Indeed, for the locomotion control tasks, we have conducted experiments with 5 expert trajectories and observed that BC (Behavioral Cloning) trained solely on the expert dataset performs exceptionally well. Consequently, in this case, there appears to be no significant advantage in using supplementary data. Note that one expert trajectory is a common choice in the existing literature. As for your concern that some trajectories may end up being bad, we notice that the collected expert trajectories are all in high quality for this benchmark. For the other tasks (e.g., Atari games and object recognization), we do consider the set-up of more than single demonstration. \n\n**Question 5:** In the object recognition task, the supplementary data is data with valid labels but with a different style. However, the focus is on \"sub-optimal policy\" data, and in other environments the supplementary data consists of different policies (\"full dataset\" setting) and outright wrong labels (\"noisy expert\"), where some actions are replaced with random ones. Following this, it seems like a more natural setup for object recognition task would be to do everything in single domain (e.g., \"Real\"), but randomly replace the sample label with a wrong label in the supplementary dataset. What is the reason behind using different sub-sets as supplementary data?\n\n**Response 5:** We utilize distinct subsets as supplementary data, as this approach is a common practice within this benchmark for examining the robustness of the learning method against distribution shifts. To establish a connection between this setup and our formulation, one might consider that each domain corresponds to a unique sub-state space.\n\nNonetheless, in line with your insights, we have conducted a new experiment. In this experiment, each supplementary dataset is situated within the same domain as the expert dataset, and certain labels within the supplementary dataset have been deliberately subjected to noise injection. For comprehensive details, please refer to Table 2 in the separate PDF file. Empirical results demonstrate that ISW-BC outperforms baseline methods and maintains its robustness even within this particular scenario.\n\n**Comment 6:** Footnotes come after commas. Term \"imitation gap\" is used early on (e.g., lines 39 and 66), but not formally or informally defined.  Please use same colors consistently between figures.  Section 3 header sounds like it is missing something (e.g., should it be \"Preliminaries\" or \"Problem setup\"?) Numbers in the tables are in bit different format. \n\n**Response 6:** Thank you for bringing these issues to our attention. We will make the corresponding corrections and improvements based on your suggestions.\n\n---\n\nWe hope that the above answers can address your concerns satisfactorily and improve the clarity of our contribution. We would be grateful if you could re-evaluate our work based on the above responses."}, {"review_id": "0fXQc6IQhq", "reviewer": "Reviewer_FJAh", "summary": "This paper considers the problem of offline imitation learning with supplementary data with optimality not guaranteed. The paper gives theoretical analysis on the performance gap bound between expert policy and learner's policy for behavior cloning (BC) on expert data only and naively using BC over the union of expert and supplementary data. Based on the analysis, the paper proposes a provably better method than BC, which is ISW-BC. ISW-BC uses importance sampling (with a lower threshold) between state-action pairs to \"correct\" the learning from non-expert state-action occupancy onto expert state-action occupancy. In several mujoco and Atari environments, ISW-BC works comparably well or better than the SOTA methods, DemoDICE and DWBC. ", "questions": "I have one question: can we actually comprehend ISW-BC as reward-weighted regression [1, 2] with $\\gamma=0$ and reward $r(s,a)=\\log\\frac{d^E(s,a)}{d^U(s,a)}$? If so, then I think more discussion is needed on the relationship between ISW-BC and RWR [1] / AWR [2].\n\nThe suggestions for the authors are listed as follows. I am open to increase my score if the authors can improve their paper as suggested:\n\n1. Modify the paper as suggested in the weaknesses (discussion of point 1, modification with point 2, 3) and limitation section;\n\n2. It would be great for the authors to try the supplementary data consists of some expert trajectories and many random trajectories or medium-level trajectories, like those tested in [3]. The component of the supplementary data can largely affect the performance of the algorithm [3];\n\n3. I strongly recommend the authors to open-source their code upon acceptance (or next submission).\n\n**References:**\n\n[1] Jan Peters and Stefan Schaal. Reinforcement learning by reward-weighted regression for operational space control. In ICML, 2007.\n\n[2] Advantage-Weighted Regression: Simple and Scalable Off-Policy Reinforcement Learning. X. Peng et al. in ArXiv, 2019.\n\n[3] H. S. Sikchi et al. Imitation from Arbitrary Experience: A Dual Unification of Reinforcement and Imitation Learning Methods. In ArXiv, 2023.", "limitations": "**Limitations:** The authors have discussed the theoretical limitations in line 280 and line 746-750. I think, however, there are more limitations that the authors could consider to add, and concentrated in a single limitation section:\n\n1) non-robustness to stochasticity (elaborated in point 1 of the weakness section);\n\n2) the assumption that $d^U$ covers $d^E$, which is also a weakness that DICE possesses but still a concern in practical use.\n\nNote these limitations do not necessarily mean that the work is not valuable enough for the conference; however, they do pose concern for readers who want to apply ISW-BC in the future.\n\n**Potential Negative Societal Impact:** The paper does a good job in discussing the broader impact at the beginning of the supplementary material.\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**1. Good writing that is easy to follow and clearly conveys the idea.** The paper is a math-heavy one with many pages of theoretical proofs; however, the core result is well-summarized by Tab. 1, the theorems, and Eq. 3-5. Besides, for readers that are interested in theoretical results with function approximators, the theorems are kindly summarized in Sec. E in the appendix, leaving the long proof details in the next section. The limitations, broader impact and computational resource are all well-discussed. \n\n**2. Simple but effective idea.** The idea of ISW-BC proposed by the paper is very simple; it only requires separate training of a discriminator and an actor, which is quite easy to implement. However, such method is theoretically guaranteed to be better than BC and is indeed better than many baselines in multiple environments.\n\n**3. Solid theoretical and practical results.** The theoretical results clearly shows that how bad could it be when we are treating non-expert data as expert data in behavior cloning (BC), and how the quality (value function) of the non-expert data affects the result. Based on this, the author proposes ISW-BC, a method that is theoretically proved to be better, and indeed achieves superior performance over multiple baselines (DWBC, DemoDICE) on multiple environments (Atari, mujoco, and even non-RL tasks).\n\n\n\n\n\n\n\n", "weaknesses": "**1. The proposed method, ISW-BC, might be non-robust to stochastic environment.** Consider a simple tabular MDP with five states $s_{begin}, s_1, s_2, s_{success}, s_{fail}$; \n\nthe agent always begin at $s_{begin}$, and there is only one action for $s_{begin}$, which has 50% probability of leading to $s_1$ and 50% probability of leading to $s_2$; \n\nthere is only one action for $s_1$ that 100% leads to $s_{success}$, and two actions for $s_2$ that 100% leads to $s_{success}$ and $s_{fail}$ respectively;\n\n $s_{success}$ is the success state that terminates the episode with $+1$ reward; $s_{fail}$ terminates the episode with $-1$ reward.\n\nNow, consider the scenario where we only have one expert trajectory (1-shot is a common case) that goes from $s_{begin}$ to $s_1$ and finally $s_{success}$. The supplementary data acts uniformly random. By definition, the discriminator now gives a close-to-zero ratio for $d_h^E/d_h^U$ with any history that involves $s_2$ (let us ignore the numerical stability issue for now because there are engineering solutions). DICE methods have an equivalence of value function (which is the Lagrange dual function), which can guide the agent back from $s_2$ to $s_{success}$. ISW-BC, however, append no or very little weight to supplementary data on $s_2$, and, because expert has never experienced $s_2$, does not know what to do on $s_2$.\n\n**2. It strikes me as a little strange how we \"justify\" the use of weight in imitation with imperfect data from theoretical analysis**, because the story of the paper seems to be improve over NBCU (later proved to be empirically better than DICE/DWBC), but the NBCU analyzed in the paper is too unintuitive to ever work; it is natural, rather than with theoretical analysis for one to know that (s)he cannot treat non-expert data that is arbitrarily bad as expert ones. **(Despite of this, I am still convinced that the theoretical analysis on NBCU is a notable contribution.)**\n\n**3. Other minor problems:**\n\na) Besides the empirical advance on offline IL mentioned in the paper, there are more theoretical advances in offline IL (more specifically, the unification of offline IL and RL), which are MAHALO [1] and ReCOIL [2]. I encourage the author to briefly discuss them in the related work section.   \n\nb) The color of the curve for each method should be unified throughout the paper. For example, the color of ISW-BC in Fig.9 and Fig.10 in the appendix are not unified and might mislead the readers.\n\n  \n\n**References:**\n\n[1] A. Li et al. MAHALO: Unifying Offline Reinforcement Learning and Imitation Learning from Observations. In ICML, 2023.\n\n[2] H. S. Sikchi et al. Imitation from Arbitrary Experience: A Dual Unification of Reinforcement and Imitation Learning Methods. In ArXiv, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper, and for your constructive comments.\n\n**Comment 1:** The proposed method, ISW-BC, might be non-robust to stochastic environment.\n\n**Response 1:** Thank you for providing the example and initiating the discussion. However, we would like to clarify that in theory, ISW-BC can work in stochastic environments (we do not pose a deterministic transition assumption). Moreover, in practice, we have considered non-deterministic tasks and showed that ISW-BC works well. \n\nRegarding your concern with the provided example, we clarify that this failure mode is associated with Proposition 2, where the main issue lies in the tabular representations rather than the stochasticity itself. However, we have shown that when feature design is well-crafted, ISW-BC can effectively avoid this failure mode, as demonstrated in our Theorem 3.\n\nRegarding your mention of DICE methods, we would appreciate further clarification on which specific DICE method you are referring to and how it manages to work with just one expert trajectory. If you are referring to the DemoDICE method, we would like to emphasize that it cannot recover the expert policy even in the population level (see Appendix B for more details).\n\n**Comment 2:** It strikes me as a little strange how we \"justify\" the use of weight in imitation with imperfect data from theoretical analysis.\n\n**Response 2:** We appreciate your feedback, and we would like to provide further clarification to address your concern. Our theoretical analysis indeed sheds new light on the justification for using weights in imitation with imperfect data. While it is intuitive to believe that treating non-expert data, which can be arbitrarily bad, as expert data would not work in the worst-case scenario, our theory reveals that this naive idea may still perform well in certain cases. Our theory introduces the concept of state-action/policy distribution shifts, as discussed in Remark 1, and provides a characterization of when the naive approach fails and when it can be effective. We use experiments to illustrate both the good and bad cases for NBCU. Then our paper attempts to introduce the use of importance sampling to improve NBCU in both cases. \n\n**Comment 3:** Besides the empirical advance on offline IL mentioned in the paper, there are more theoretical advances in offline IL, which are MAHALO [1] and ReCOIL [2]. \n\n**Response 3:** Thanks for pointing out these references. We provide a short discussion below, which will be involved in the revised paper. Similar to MILO (citied as [7] in our paper), MAHALO [1] analyzes the suboptimality of MAHALO which follows the pessimism principle in offline RL, while we study BC and its variants. ReCOIL[2] optimizes the state-action distribution matching objective with new duality techniques and presents a new energy-based model viewpoint. In contrast, ISW-BC leverages the importance sampling technique, and we provide a new analysis for it.\n\n**Comment 4:** The color of the curve for each method should be unified throughout the paper. \n\n**Response 4:** We will ensure that the color format is unified to avoid any confusion in the revised version.\n\n**Comment 5:** I have one question: can we actually comprehend ISW-BC as reward-weighted regression [1, 2] with $\\gamma=0$ and reward $r(s, a) = \\log \\frac{d^{\\operatorname{E}}(s, a)}{ d^{\\operatorname{U}}(s, a)}$.\n\n**Response 5**: Yes, the training objective of ISW-BC can be comprehended as reward-weighted regression (RWR) with $\\gamma=0$ and reward $r(s, a) = \\log \\frac{d^{\\operatorname{E}}(s, a)}{ d^{\\operatorname{U}}(s, a)}$. This viewpoint is intriguing, but we would like to highlight the following differences:\n\n- Papers on RWR mainly consider the online setting, while we focus on the offline setting.\n- Papers on RWR are applicable in the RL setting where the reward is readily available, whereas in our imitation learning setting, we need to infer the reward (or the importance sampling ratio).\n\n**Comment 6:** Modify the paper as suggested in the weaknesses and limitation section.\n\n**Response 6:** Your suggestions are very helpful and we will revise the paper as suggested. \n\n**Comment 7:** It would be great for the authors to try the supplementary data consists of some expert trajectories and many random trajectories or medium-level trajectories, like those tested in [3]. \n\n**Response 7:**  Thanks for pointing out that supplementary data distribution is important for algorithm performance, which is consistent with our claim in discussing NBCU. We have experimented that supplementary data consists of 10 expert trajectories and 10 random trajectories in the locomotion control benchmark. The results show that ISW-BC outperforms BC by a wide margin, demonstrating the robustness of ISW-BC to distribution shift. Furthermore, ISW-BC also performs better than other baselines DemoDICE and DWBC. The detailed results are available in Table 1 in a separated pdf file. We are also planning to conduct more experiments with medium-level trajectories or in Atari games and replenish these results in the future revision. \n\n**Comment 8:** I strongly recommend the authors to open-source their code upon acceptance (or next submission).\n\n**Response 8:** As promised in the Appendix, we will make our code and datasets available for public access upon acceptance. Currently, in accordance with the NeurIPS instructions, we have provided the code to the area chair via an anonymized link.\n\n**Comment 9:** The assumption that $d^{\\operatorname{U}}$ covers $d^{\\operatorname{E}}$, which is also a weakness that DICE posses but still a concern in practical use. \n\n**Response 9:** We appreciate your feedback, but we would like to clarify that this assumption directly holds because the union data includes the expert data.\n\n---\n\nWe hope that the above response can address your concerns adequately. We would greatly appreciate it if you could re-evaluate our paper based on the above responses."}]

Author rebuttal:
We thank all reviewers for their expertise and efforts in reviewing our paper. We have responsed to each review seperately. We hope that our response can address the concerns well. Furthermore, we look forward to any additional comments or suggestions for improvement.

Please take note that we have attached a separate PDF file containing new experimental results aimed at addressing the concerns from Reviewers Yb9D, Y1mx, and FJAh.

Best,

The Authors

Meta-review: All reviewers agree that this is a submission above the bar for acceptance. I have gone through the reviews and paper myself, and I find the paper to overall be a strong submission all-around, combining strong theoretical results with extensive experiments and clear writing/presentation.
Decision: Accept (spotlight)