11affiliationtext: The Chinese University of Hong Kong,
Shenzhen22affiliationtext: Shenzhen Research Institute of Big
Data33affiliationtext: National Key Laboratory for Novel Software Technology,
Nanjing University

# Theoretical Analysis of Offline Imitation With Supplementary Dataset

Ziniu Li Equal contribution. Author ordering is determined by coin flip.
Email<EMAIL_ADDRESS>and<EMAIL_ADDRESS>Tian Xu∗ Yang Yu
Corresponding author. Email<EMAIL_ADDRESS>and<EMAIL_ADDRESS>Zhi-Quan
Luo†

###### Abstract

Behavioral cloning (BC) can recover a good policy from abundant expert data,
but may fail when expert data is insufficient. This paper considers a
situation where, besides the small amount of expert data, a supplementary
dataset is available, which can be collected cheaply from sub-optimal
policies. Imitation learning with a supplementary dataset is an emergent
practical framework, but its theoretical foundation remains under-developed.
To advance understanding, we first investigate a direct extension of BC,
called NBCU, that learns from the union of all available data. Our analysis
shows that, although NBCU suffers an imitation gap that is larger than BC in
the worst case, there exist special cases where NBCU performs better than or
equally well as BC. This discovery implies that noisy data can also be helpful
if utilized elaborately. Therefore, we further introduce a discriminator-based
importance sampling technique to re-weight the supplementary data, proposing
the WBCU method. With our newly developed _landscape-based analysis_ , we
prove that WBCU can outperform BC in mild conditions. Empirical studies show
that WBCU simultaneously achieves the best performance on two challenging
tasks where prior state-of-the-art methods fail.

##  1 Introduction

Imitation learning (IL) methods train a good policy from expert demonstrations
(Argall et al., 2009; Osa et al., 2018). One popular approach is behavioral
cloning (BC) (Pomerleau, 1991), which imitates the expert via supervised
learning. Specifically, in IL, samples usually refer to state-action
pairs/sequences from trajectories in the given dataset. Both the quality and
quantity of trajectories are crucial to achieving satisfying performance. For
instance, it is found that BC performs well when the dataset has a large
amount of expert-level trajectories; see, e.g., (Spencer et al., 2021).
Nevertheless, due to the compounding errors issue (Ross and Bagnell, 2010),
any offline IL algorithm, including BC, will fail when the number of expert
trajectories is small (Rajaraman et al., 2020; Xu et al., 2021a). To address
the compounding errors issue, a naive solution is to ask the expert to collect
more trajectories. However, querying the expert is expensive and intractable
in applications such as healthcare and industrial control.

To address the mentioned failure mode, we follow an alternative and emergent
framework proposed in (Kim et al., 2022b; Xu et al., 2022a), which assumes, in
addition to the expert dataset, a supplementary dataset is relatively cheap to
obtain. In particular, this supplementary dataset could be previously
collected by certain behavior policies; as such, it has lots of expert and
sub-optimal trajectories. The key challenge here is to figure out which
supplemental samples are helpful. We realize that a few advances have been
achieved in this direction (Kim et al., 2022b, a; Xu et al., 2022a; Ma et al.,
2022). To leverage the supplementary dataset, a majority of algorithms train a
discriminator to distinguish expert-style and sub-optimal samples, upon which
a weighted BC objective is optimized to learn a good policy. For instance, Kim
et al. (2022b) proposed the DemoDICE algorithm, which learns the discriminator
via a regularized state-action distribution matching objective. As for the
DWBC algorithm in (Xu et al., 2022a), the policy and discriminator are jointly
trained under a cooperation framework.

Though prior algorithms are empirically shown to perform well in some
scenarios, the theoretical foundation of this new imitation problem remains
under-developed. Specifically, researchers have a sketchy intuition that noisy
demonstrations in the supplementary dataset may hurt the performance when we
directly apply BC, and researchers hope to develop algorithms to overcome this
challenge. However, the following questions have not been carefully answered
yet: (Q1) precisely, what kind of noisy samples is harmful? (or what kind of
supplementary samples is helpful?) (Q2) how to design algorithms in a
principled way? Answers could deepen our understanding and provide insights
for future advances.

In this paper, we explore the above questions by investigating two
(independent) variants of BC. To learn a policy, both algorithms apply a BC
objective on the _union_ dataset (the concatenation of the expert and
supplementary dataset), but they differ in assigning weights of samples that
appear in the loss function. To qualify the benefits of the supplementary
dataset, we treat the BC _only_ with the expert dataset as a baseline to
compare.

The first algorithm, called NBCU (naive BC with union dataset), assigns
uniform weights for all samples. As a direct extension of BC, the theoretical
study of NBCU provides answers to (Q1). In particular, we show that NBCU
suffers an imitation gap that is larger than BC in the _worst_ case (Theorem 2
and Proposition 1), implying its inferior performance in the general case.
However, we discover _special_ cases where NBCU performs better than or
equally well as BC (Theorem 3 and Theorem 4). This discovery indicates that
noisy data can also be helpful if utilized elaborately. To our best knowledge,
such a message is new to the community. We provide the empirical evidence in
Figure 1 and discuss these results in depth later.

As NBCU (i.e., the direct extension of BC) may fail in the worst case, we
develop another algorithm called WBCU (weighted BC with union dataset) to
address this failure mode. In light of (Kim et al., 2022b; Xu et al., 2022a),
WBCU trains a discriminator to weigh samples. We use the importance sampling
technique (Shapiro, 2003, Chapter 9) to design the weighting rule. Unlike
prior works (Kim et al., 2022b; Xu et al., 2022a) that use a biased (or
regularized) weighting rule, WBCU is theoretically sound and principled in the
sense that the loss function is corrected as if samples from the supplementary
dataset were collected by the expert policy; see Remark 1 for detailed
discussion.

Theoretically, we justify WBCU via a new landscaped-based analysis (Theorem
5). We characterize the landscape properties (e.g., the Lipschitz continuity
and quadratic growth conditions) in Lemma 1 and Lemma 2. Interestingly, we
find that the “smooth” function approximation for the _discriminator_ plays a
vital role in WBCU; without it, WBCU cannot be better than BC (Proposition 2).
Our theory can provide actionable guidance for practitioners; see Section 5.2
for details. These results offer answers to (Q2).

Figure 1: Averaged normalized scores of learned policies (over 4 MuJoCo
environments) on two tasks with different supplementary datasets. A larger
score means a better performance. Experiments show that 1) NBCU is worse than
BC for the noisy expert task and better than BC for the full replay task; 2)
only our method WBCU can perform well on both two tasks.

Finally, we corroborate our claims with experiments on the MuJoCo locomotion
control. Given the same expert dataset (1 expert trajectory), we consider two
tasks with different supplementary datasets. The first task (called full
replay) follows the setting in (Kim et al., 2022b): supplementary trajectories
are from the replay buffer of an online SAC agent (Haarnoja et al., 2018). The
second task (called noisy expert) is a new test-bed: the supplementary dataset
contains clean expert-style trajectories, and the noisy counterparts111Noisy
counterparts cover expert states but are injected with action noise.. Please
refer to Section D.1 for experiment details. Please see Figure 1 for the
(averaged) normalized scores of learned policies over four representative
MuJoCo environments222Ant-v2, HalfCheetah-v2, Hopper-v2, and Walker2d-v2.
(performance on individual environments is reported in Table 2 and Table 3 in
Appendix). We find that WBCU _simultaneously_ achieves the best performance on
both two tasks, whereas prior state-of-the-art methods like DemoDICE (Kim et
al., 2022b) and DWBC (Xu et al., 2022a) only perform well on one of two tasks.
We will connect the experiment results with theoretical analysis in the main
text.

##  2 Related Work

Adversarial Imitation Learning. Unlike BC, adversarial imitation learning
(AIL) methods (e.g., GAIL (Ho and Ermon, 2016)) do not suffer the compounding
errors issue when the expert trajectories are limited; see the empirical
evidence in (Ho and Ermon, 2016; Ghasemipour et al., 2019; Kostrikov et al.,
2019) and theoretical support in (Xu et al., 2020, 2022b). In particular, AIL
methods train a discriminator to perform the state-action distribution
matching, which differs from BC. Nevertheless, AIL methods naturally work in
the online setting (i.e., the interaction is allowed). If the transition
function is not available, BC is minimax optimal (Rajaraman et al., 2020; Xu
et al., 2021b) and offline counterparts of AIL are not better than BC (Li et
al., 2022).

Perhaps surprisingly, we find that the discriminator used in our WBCU
algorithm plays a different role than AIL methods. We provide a detailed
explanation in Section 5.

Imitation Learning with Imperfect Demonstrations. The problem considered in
this paper is closely related to imitation learning (IL) with imperfect
demonstrations (Wu et al., 2019; Brown et al., 2019; Tangkaratt et al., 2020;
Wang et al., 2021; Sasaki and Yamashina, 2021; Liu et al., 2022) in the sense
that the supplementary dataset can also be viewed as imperfect demonstrations.
However, our problem setting differs from IL with imperfect demonstrations in
two key aspects. First, in IL with imperfect demonstrations, they either pose
strong assumptions (Tangkaratt et al., 2020; Sasaki and Yamashina, 2021; Liu
et al., 2022) or require auxiliary information (e.g., confidence scores on
imperfect trajectories) on the imperfect dataset (Wu et al., 2019; Brown et
al., 2019). In contrast, we assume access to a small number of expert
trajectories, which could be more practical. Second, most works (Wu et al.,
2019; Brown et al., 2019; Tangkaratt et al., 2020; Wang et al., 2021) in IL
with imperfect demonstrations require online environment interactions while we
focus on the offline setting.

Finally, we point out that the problem of offline imitation learning with a
supplementary dataset is first considered in (Kim et al., 2022b; Xu et al.,
2022a). Subsequently, Ma et al. (2022); Kim et al. (2022a) study a related
setting: learning from observation, where actions are missing and only states
are observed. Existing works mainly focus on empirical studies, and the
theoretical foundation remains under-developed.

##  3 Preliminary

Markov Decision Process. In this paper, we consider the episodic Markov
decision process333Our results can be translated to the discounted and
infinite-horizon MDP setting. We consider the episodic MDP because it allows a
simple way of dealing with the statistical estimation. (MDP)
${\mathcal{M}}=({\mathcal{S}},{\mathcal{A}},{\mathcal{P}},r,H,\rho)$
(Puterman, 2014). The first two elements ${\mathcal{S}}$ and ${\mathcal{A}}$
are the state and action space, respectively. $H$ is the maximum length of a
trajectory and $\rho$ is the initial state distribution.
${\mathcal{P}}=\\{P_{1},\cdots,P_{H}\\}$ specifies the non-stationary
transition function of this MDP; concretely, $P_{h}(s_{h+1}|s_{h},a_{h})$
determines the probability of transiting to state $s_{h+1}$ conditioned on
state $s_{h}$ and action $a_{h}$ in time step $h$, for $h\in[H]$, where the
symbol $[x]$ means the set of integers from $1$ to $x$. Similarly,
$r=\\{r_{1},\cdots,r_{H}\\}$ is the reward function, and we assume
$r_{h}:{\mathcal{S}}\times{\mathcal{A}}\rightarrow[0,1]$, for $h\in[H]$. A
time-dependent policy is
$\pi_{h}:{\mathcal{S}}\rightarrow\Delta({\mathcal{A}})$, where
$\Delta({\mathcal{A}})$ is the probability simplex. $\pi_{h}(a|s)$ gives the
probability of selecting action $a$ on state $s$ in time step $h$, for
$h\in[H]$. When the context is clear, we simply use $\pi$ to denote the
collection of time-dependent policies $\\{\pi_{h}\\}_{h=1}^{H}$.

We measure the quality of a policy $\pi$ by the policy value (i.e.,
environment-specific long-term return):
$V(\pi)=\mathbb{E}\big{[}\sum_{h=1}^{H}r(s_{h},a_{h})\mid
s_{1}\sim\rho;a_{h}\sim\pi_{h}(\cdot|s_{h}),s_{h+1}\sim
P_{h}(\cdot|s_{h},a_{h}),\forall h\in[H]\big{]}$. To facilitate later
analysis, we need to introduce the state-action distribution
$d^{\pi}_{h}(s,a)$:

$\displaystyle d^{\pi}_{h}(s,a)={\mathbb{P}}\big{(}$ $\displaystyle
s_{h}=s,a_{h}=a\mid
s_{1}\sim\rho;a_{\ell}\sim\pi(\cdot|s_{\ell}),s_{\ell+1}\sim
P_{\ell}(\cdot|s_{\ell},a_{\ell}),\forall\ell\in[h]\big{)}.$

Here, we use the convention that $d^{\pi}$ is the collection of all time-
dependent state-action distributions. Sometimes, we need to consider the state
distribution $d^{\pi}(s)$, which shares the same definition with
$d^{\pi}(s,a)$ except that we only compute the probability of visiting a
specific state $s$. It is easy to see that
$d^{\pi}_{h}(s)=\sum_{a}d^{\pi}_{h}(s,a)$, $\forall h\in[H]$.

Imitation Learning. The goal of imitation learning is to learn a high quality
policy directly from expert demonstrations. To this end, we often assume there
is a nearly optimal expert policy $\pi^{\operatorname{E}}$ that could interact
with the environment to generate a dataset (i.e., $N_{\operatorname{E}}$
trajectories of length $H$):

$\displaystyle{\mathcal{D}}^{\operatorname{E}}=\big{\\{}$
$\displaystyle\operatorname{tr}=\left(s_{1},a_{1},s_{2},a_{2},\cdots,s_{H},a_{H}\right);s_{1}\sim\rho,a_{h}\sim\pi^{\operatorname{E}}_{h}(\cdot|s_{h}),s_{h+1}\sim
P_{h}(\cdot|s_{h},a_{h}),\forall h\in[H]\big{\\}}.$

Then, the learner can use ${\mathcal{D}}^{\operatorname{E}}$ to mimic the
expert. From a theoretical perspective, the quality of imitation is measured
by the _imitation gap_ :
$\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi)\right]$, where $\pi$ is the
learned policy and the expectation is taken over the randomness of
${\mathcal{D}}^{\operatorname{E}}$. We hope that a good learner can mimic the
expert perfectly and thus the imitation gap is small. In this paper, we assume
that the expert policy is deterministic, which is common in the literature
(Rajaraman et al., 2020, 2021; Xu et al., 2020, 2021b). Note that this
assumption holds for tasks including MuJoCo locomotion control.

Behavioral Cloning. Given an _expert_ dataset
${\mathcal{D}}^{\operatorname{E}}$, the behavioral cloning (BC) algorithm
takes the maximum likelihood estimation:

$\displaystyle\pi^{\operatorname{BC}}\in\max_{\pi}\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{E}}_{h}}(s,a)\log\pi_{h}(a|s),$
(1)

where $\widehat{d^{\operatorname{E}}_{h}}(s,a)$ is the empirical state-action
distribution. By definition,
$\widehat{d^{\operatorname{E}}_{h}}(s,a)=n_{h}^{\operatorname{E}}(s,a)/N_{\operatorname{E}}$,
where $n_{h}^{\operatorname{E}}(s,a)$ refers to the number of expert
trajectories such that their state-action pairs are equal to $(s,a)$ in time
step $h$. In the tabular case, a closed-formed solution to Equation 1 is
available:

$\displaystyle\pi^{\operatorname{BC}}_{h}(a|s)=\left\\{\begin{array}[]{ll}\frac{n_{h}^{\operatorname{E}}(s,a)}{n_{h}^{\operatorname{E}}(s)}&\text{if
}n_{h}^{\operatorname{E}}(s)>0\\\
\frac{1}{|{\mathcal{A}}|}&\text{otherwise}\end{array}\right.$ (4)

where
$n_{h}^{\operatorname{E}}(s)\triangleq\sum_{a^{\prime}}n_{h}^{\operatorname{E}}(s,a^{\prime})$.
For visited states, BC can make good decisions by duplicating expert actions.
However, BC has limited knowledge about the expert actions on non-visited
states. As a result, it may suffer a large imitation gap when making a wrong
decision on a non-visited state, leading to compounding errors (Ross and
Bagnell, 2010).

Imitation with Supplementary Dataset. BC will fail when the number of expert
trajectories is small due to the mentioned compounding errors issue. A naive
solution is to collect more expert trajectories. In this paper, we follow an
alternative and emergent framework in (Kim et al., 2022b; Xu et al., 2022a),
where we assume that an offline _supplementary_ dataset
${\mathcal{D}}^{\operatorname{S}}$ (i.e., $N_{\operatorname{S}}$ trajectories
of length $H$) is relatively cheap to obtain:

$\displaystyle{\mathcal{D}}^{\operatorname{S}}=\big{\\{}$
$\displaystyle\operatorname{tr}=\left(s_{1},a_{1},s_{2},a_{2},\cdots,s_{H},a_{H}\right);s_{1}\sim\rho,a_{h}\sim\pi^{\beta}_{h}(\cdot|s_{h}),s_{h+1}\sim
P_{h}(\cdot|s_{h},a_{h}),\forall h\in[H]\big{\\}},$

where $\pi^{\beta}$ is a behavioral policy that could be a mixture of certain
base policies, i.e., $\pi^{\beta}=\sum_{i=1}^{K}\alpha_{i}\pi^{i}$ with
$\sum_{i=1}^{K}\alpha_{i}=1$ and $\alpha_{i}\geq 0$ for $i\in[K]$. Algorithms
can additionally leverage this supplementary dataset to mitigate the
compounding errors issue.

##  4 Analysis of Naive Behavior Cloning with Union Dataset

In this section, we consider a direct extension of BC for the problem of
offline imitation with a supplementary dataset. Specifically, this algorithm
called NBCU (naive BC with the union dataset) performs the maximum likelihood
estimation on the union of the expert and supplementary datasets:

$\displaystyle\pi^{\operatorname{NBCU}}\in\mathop{\rm
argmax}_{\pi}\sum_{h=1}^{H}\sum_{(s,a)}\widehat{d^{\operatorname{U}}_{h}}(s,a)\log\pi_{h}(a|s),$
(5)

where
${\mathcal{D}}^{\operatorname{U}}={\mathcal{D}}^{\operatorname{S}}\cup{\mathcal{D}}^{\operatorname{E}}$
and $\widehat{d^{\operatorname{U}}_{h}}(s,a)$ is the empirical state-action
distribution estimated from ${\mathcal{D}}^{\operatorname{U}}_{h}$ (i.e., the
subset of ${\mathcal{D}}^{\operatorname{U}}$ in step $h$). As an analogue to
Equation 4, we have

$\displaystyle\pi^{\operatorname{NBCU}}_{h}(a|s)=\left\\{\begin{array}[]{ll}\frac{n_{h}^{\operatorname{U}}(s,a)}{n_{h}^{\operatorname{U}}(s)}&\text{if
}n_{h}^{\operatorname{U}}(s)>0\\\
\frac{1}{|{\mathcal{A}}|}&\text{otherwise}\end{array}\right.$ (8)

where, just like before, $n_{h}^{\operatorname{U}}(s,a)$ refers to the number
of union trajectories such that their state-action pairs are equal to $(s,a)$
in time step $h$. To analyze NBCU, we pose an assumption about the dataset
collection.

Algorithm 1 NBCU

1:Expert dataset ${\mathcal{D}}^{\operatorname{E}}$ and supplementary dataset
${\mathcal{D}}^{\operatorname{S}}$.

2:${\mathcal{D}}^{\operatorname{U}}\leftarrow{\mathcal{D}}^{\operatorname{E}}\cup{\mathcal{D}}^{\operatorname{S}}$.

3:Apply BC to learn a policy $\pi$ by objective (5) with
${\mathcal{D}}^{\operatorname{U}}$.

######  Assumption 1.

The supplementary dataset ${\mathcal{D}}^{\operatorname{S}}$ and expert
dataset ${\mathcal{D}}^{\operatorname{E}}$ are collected in the following way:
each time, we roll-out a behavior policy $\pi^{\beta}$ with probability
$1-\eta$ and the expert policy with probability $\eta$, where $\eta\in[0,1]$
controls the fraction of expert trajectories. Such an experiment is
independent and identically conducted by $N_{\operatorname{tot}}$ times.

Under Assumption 1, we slightly overload our notations: let
$N_{\operatorname{E}}$ be the _expected_ number of expert trajectories, i.e.,
$N_{\operatorname{E}}=\eta N_{\operatorname{tot}}$, and $N_{\operatorname{S}}$
be the _expected_ number of supplementary trajectories, i.e.,
$N_{\operatorname{S}}=(1-\eta)N_{\operatorname{tot}}$.

###  4.1 Baseline: BC on the Expert Dataset

To measure whether the supplementary dataset is helpful, we consider the BC
_only_ with the expert dataset as a baseline. This approach has been analyzed
in (Rajaraman et al., 2020), and we transfer their results under our
assumption444The proof of Theorem 1 builds on (Rajaraman et al., 2020) and the
main difference is that the number of expert trajectories is a random variable
in our set-up. Technically, we handle this difficulty by Lemma 3 in Appendix.:

######  Theorem 1.

Under Assumption 1. In the tabular case, if we apply BC only on the expert
dataset, we have that555$a(n)\lesssim b(n)$ means that there exist $C,n_{0}>0$
such that $a(n)\leq Cb(n)$ for all $n\geq n_{0}$. In our context, $n$ usually
refers to the number of trajectories.

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})\right]\lesssim\min\left\\{H,\frac{|{\mathcal{S}}|H^{2}}{N_{\operatorname{E}}}\right\\},$

where the expectation is taken over the randomness in the dataset collection.

Proofs of all theoretical results are deferred to the Appendix.

###  4.2 Main Results of NBCU

Now, we present our main claim about NBCU.

######  Theorem 2.

Under Assumption 1. In the tabular case, for any $\eta\in(0,1]$, we have

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]\lesssim\min\bigg{\\{}H,(1-\eta)\left(V(\pi^{\operatorname{E}})-V(\pi^{\beta})\right)+\frac{|{\mathcal{S}}|H^{2}\log(N_{\operatorname{tot}})}{N_{\operatorname{tot}}}\bigg{\\}},$

where the expectation is taken over the randomness in the dataset collection.

We often have $V(\pi^{\operatorname{E}})-V(\pi^{\beta})>0$, as the behavior
policy is usually inferior to the expert policy. In this case, even if
$N_{\operatorname{tot}}$ is sufficiently large so that the second term is
negligible, there still exists a positive gap between
$V(\pi^{\operatorname{E}})$ and $V(\pi^{\operatorname{NBCU}})$. Fundamentally,
this is because the behavior policy may collect non-expert actions, so the
recovered policy may select a wrong action even on expert states, which
results in bad performance. The following theorem shows that the gap
$V(\pi^{\operatorname{E}})-V(\pi^{\beta})$ is inevitable in the worst case.

######  Proposition 1.

Under Assumption 1. In the tabular case, there exists an MDP ${\mathcal{M}}$,
an expert policy $\pi^{\operatorname{E}}$ and a behavior policy $\pi^{\beta}$,
for any $\eta\in(0,1]$, when $N_{\operatorname{tot}}\gtrsim|{\mathcal{S}}|$,
we have

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]\gtrsim(1-\eta)\left(V(\pi^{\operatorname{E}})-V(\pi^{\beta})\right),$

where the expectation is taken over the randomness in the dataset collection.

The construction of the hard instance in Proposition 1 is based on the
following intuition: NBCU does not distinguish the action labels in the union
dataset and treats them equally important; see Equation 8. Therefore, NBCU
will learn bad decisions and suffer a non-vanishing gap when the dataset has a
bad state-action coverage (i.e., primarily, action labels on the expert states
are sub-optimal).

###  4.3 Positive Results of NBCU

The previous results suggest that NBCU is not warranted to be better than BC.
For some special cases (depending on the dataset coverage), however, we can
bypass the hard instance in Proposition 1 and show that NBCU can perform well.
We state two representative results as follows.

######  Theorem 3.

Under the same assumption with Theorem 2, additionally assume that
$\pi^{\beta}=\pi^{\operatorname{E}}$. In the tabular case, for any
$\eta\in[0,1]$, we have

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]\lesssim\min\left\\{H,\frac{|{\mathcal{S}}|H^{2}}{N_{\operatorname{tot}}}\right\\},$

where the expectation is taken over the randomness in the dataset collection.

Theorem 3 is a direct extension of Theorem 1. The condition
$\pi^{\beta}=\pi^{\operatorname{E}}$ seems strong. Still, it may approximately
hold in the following case: the supplementary dataset
${\mathcal{D}}^{\operatorname{S}}$ is collected by an online agent that
improves its performance over iterations, in which $\pi^{\beta}$ is close to
$\pi^{\operatorname{E}}$ asymptotically.

######  Theorem 4.

Under the same assumption with Theorem 2, additionally assume that
$\pi^{\beta}$ never visits expert states, i.e.,
$\mathrm{supp}(d^{\pi^{\beta}}_{h}(\cdot))\cap\mathrm{supp}(d^{\pi^{\operatorname{E}}}_{h}(\cdot))=\emptyset$666For
a distribution $p$, $\mathrm{supp}(p)=\\{x:p(x)\neq 0\\}$. for all $h\in[H]$.
In the tabular case, for any $\eta\in(0,1]$, we have

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]\lesssim\min\left\\{H,\frac{|{\mathcal{S}}|H^{2}}{N_{\operatorname{E}}}\right\\},$
(9)

where the expectation is taken over the randomness in the dataset collection.

It is commonly believed that noisy demonstrations are harmful to performance
(Sasaki and Yamashina, 2021). Nevertheless, Theorem 4 provides a condition in
which BC is robust to noisy samples. Technically, this robustness property
stems from the theoretical analysis that only states along the expert
trajectory are significant for the imitation gap, and noisy actions on the
non-expert states do not contribute.

Summary. Our results demonstrate that without a special design, the naive
application of BC on the union dataset is not guaranteed to be better than BC.
However, good results may happen if the dataset coverage is nice, suggesting
that noisy demonstrations are not the monster in all cases. Please refer to
Table 1 for a summary.

Table 1: Effects of state-action attributes of samples for NBCU. “✓✓” indicates a helpful sample, “✗” indicates a harmful sample, and “✓” means something in between. | Expert state | Non-expert state
---|---|---
Expert action | ✓✓ | ✓
Non-expert action | ✗ | ✓

Connection with Experiments. From Figure 1, we already see two interesting
phenomena: 1) NBCU is worse than BC for the noisy expert task; 2) NBCU is much
better than BC for the full replay task. We use our theory to interpret these
results. First, for the noisy expert task, our experiment setting (refer to
Section D.1 for details) ensures that the supplementary dataset has noisy
demonstrations on expert states, following the idea in Proposition 1. In this
case, Theorem 2 predicts that NBCU is no better than BC. Second, for the full
replay task, we remark that the replay buffer contains lots of expert-level
trajectories (refer to Figure 5 in Appendix which shows that the online SAC
converges to the expert-level performance quickly). Therefore, the dataset
coverage is good in this scenario and Theorem 3 and Theorem 4 can explain the
good performance of NBCU.

##  5 Analysis of Weighted Behavioral Cloning with Union Dataset

In this section, we explore an alternative approach to leverage the expert and
supplementary datasets. In light of (Kim et al., 2022b; Xu et al., 2022a), a
discriminator is trained to score samples, upon which a weighted BC objective
is used for policy optimization:

$\displaystyle\pi^{\operatorname{WBCU}}\in\mathop{\rm
argmax}_{\pi}\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\bigg{\\{}\widehat{d^{\operatorname{U}}_{h}}(s,a)\times\left[w_{h}(s,a)\log\pi_{h}(a|s)\right]\times{\mathbb{I}}\left[w_{h}(s,a)\geq\delta\right]\bigg{\\}},$
(10)

where $\widehat{d^{\operatorname{U}}_{h}}(s,a)$ is the empirical state-action
distribution estimated from ${\mathcal{D}}^{\operatorname{U}}_{h}$,
$w_{h}(s,a)\in[0,\infty)$ is the weight decided by the discriminator, and
$\delta\in[0,\infty)$ is a hyper-parameter. We point out that $\delta$ is
introduced for theoretical analysis, and in practice we set $\delta=0$. We
call this approach WBCU (weighted BC with the union dataset).

Our key idea is the importance sampling technique (Shapiro, 2003, Chapter 9),
which can transfer samples in the union dataset under the expert policy
distribution. In this way, WBCU is expected to address the failure mode of
NBCU. We elaborate on this point as follows. In the population level (i.e.,
there are infinitely samples), we would have
$\widehat{d^{\operatorname{U}}_{h}}=d^{\operatorname{U}}_{h}$, which is
jointly determined by the expert policy and the behavioral policy. In this
case, if
$w_{h}(s,a)=d^{\operatorname{E}}_{h}(s,a)/d^{\operatorname{U}}_{h}(s,a)$, we
would have
$\widehat{d^{\operatorname{U}}_{h}}(s,a)w_{h}(s,a)=d^{\operatorname{E}}_{h}(s,a)$.
Accordingly, the objective (10) is to learn a policy as if samples were
collected by the expert policy. In practice, $d^{\operatorname{E}}_{h}(s,a)$
and $d^{\operatorname{U}}_{h}(s,a)$ are unknown; instead, we only have finite
samples from these two distributions. Therefore, we need to estimate the
grounded importance sampling ratio
$d^{\operatorname{E}}_{h}(s,a)/d^{\operatorname{U}}_{h}(s,a)$.

We emphasize that a simple two-step idea—first estimating
$d^{\operatorname{E}}_{h}(s,a)$ and $d^{\operatorname{U}}_{h}(s,a)$ separately
and then calculating their quotient—is intractable. This is because it is
difficult to accurately estimate the probability density of high-dimensional
distributions. Following the seminal idea in (Goodfellow et al., 2014), we
take a one-step approach: we directly train a discriminator to estimate
$d^{\operatorname{E}}_{h}(s,a)/d^{\operatorname{U}}_{h}(s,a)$. Concretely, we
consider time-dependent parameterized discriminators
$\\{c_{h}:{\mathcal{S}}\times{\mathcal{A}}\rightarrow(0,1)\\}_{h=1}^{H}$, each
of which has an objective

$\displaystyle\max_{c_{h}}$
$\displaystyle\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{E}}_{h}}(s,a)\left[\log\left(c_{h}(s,a)\right)\right]+\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{U}}_{h}}(s,a)\left[\log\left(1-c_{h}(s,a)\right)\right].$
(11)

The above problem amounts to training a binary classifier (i.e., the logistic
regression). In the population level, with the first-order optimality
condition, we have

$\displaystyle
c^{\star}_{h}(s,a)=\frac{{d^{\operatorname{E}}_{h}}(s,a)}{{d^{\operatorname{E}}_{h}}(s,a)+{d^{\operatorname{U}}_{h}}(s,a)}.$
(12)

Then, we can obtain the importance sampling ratio
$d^{\operatorname{E}}_{h}(s,a)/d^{\operatorname{U}}_{h}(s,a)$ in the following
way:

$\displaystyle w_{h}(s,a)=\frac{c^{\star}_{h}(s,a)}{1-c^{\star}_{h}(s,a)}.$
(13)

Based on the above discussion, we outline the implementation of the proposed
method WBCU in Algorithm 2.

Algorithm 2 WBCU

1:Expert dataset ${\mathcal{D}}^{\operatorname{E}}$ and supplementary dataset
${\mathcal{D}}^{\operatorname{S}}$.

2:${\mathcal{D}}^{\operatorname{U}}\leftarrow{\mathcal{D}}^{\operatorname{E}}\cup{\mathcal{D}}^{\operatorname{S}}$.

3:Train a binary classifier $c$ by objective (11) with
${\mathcal{D}}^{\operatorname{E}}$ and ${\mathcal{D}}^{\operatorname{U}}$.

4:Compute the importance sampling ratio $w$ by Equation 13.

5:Apply BC to learn a policy $\pi$ by objective (10) with
${\mathcal{D}}^{\operatorname{U}}$.

######  Remark 1.

The weighting rule of WBCU is unbiased in the sense that WBCU directly
estimates the importance sampling ratio, while prior methods in (Kim et al.,
2022b; Xu et al., 2022a) use biased/regularized weighting rules. As
byproducts, WBCU has fewer hyper-parameters to tune.

First, DemoDICE also implements the policy learning objective (10), but
DemoDICE uses the weighting rule $\widetilde{w}(s,a)\propto
d^{\star}(s,a)/d^{\operatorname{U}}(s,a)$ (refer to the formula between
Equations (19)-(20) in (Kim et al., 2022b)), where $d^{\star}$ is computed by
a regularized state-action distribution objective (refer to (Kim et al.,
2022b, Equations (5)-(7)))777For a moment, we use the notations in (Kim et
al., 2022b) and present their results under the stationary and infinite-
horizon MDPs. Same as the discussion of DWBC (Xu et al., 2022a).:

$\displaystyle d^{\star}$ $\displaystyle=\mathop{\rm
argmin}_{d}D_{\mathrm{KL}}(d\|d^{\operatorname{E}})+\alpha
D_{\mathrm{KL}}(d\|d^{\operatorname{U}})$ s.t. $\displaystyle d(s,a)\geq
0\quad\forall s,a.$
$\displaystyle\sum_{a}d(s,a)=(1-\gamma)\rho(s)+\gamma\sum_{s^{\prime},a^{\prime}}P(s|s^{\prime},a^{\prime})d(s^{\prime},a^{\prime})\quad\forall
s.$

where $\gamma\in[0,1)$ is the discount factor, $\alpha>0$ is a hyper-
parameter. Due to the regularized term in the objective and the Bellman flow
constraint, we have $d^{\star}\neq d^{\operatorname{E}}$.

Second, DWBC considers a different policy learning objective (refer to (Xu et
al., 2022a, Equation (17))):

$\displaystyle\min_{\pi}\quad$
$\displaystyle\alpha\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}}\left[-\log\pi(a|s)\right]-\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}}\left[-\log\pi(a|s)\cdot\frac{\lambda}{c(1-c)}\right]+\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}}\left[-\log\pi(a|s)\cdot\frac{1}{1-c}\right],$
(14)

where $\alpha>0,\lambda>0$ are hyper-parameters, and $c$ is the output of the
discriminator that is jointly trained with $\pi$ (refer to (Xu et al., 2022a,
Equation (8))):

$\displaystyle\min_{c}\quad$
$\displaystyle\lambda\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}}\left[-\log
c(s,a,\log\pi(a|s))\right]+\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}}\left[-\log(1-c(s,a,\log\pi(a|s)))\right]$
$\displaystyle-\lambda\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}}\left[-\log(1-c(s,a,\log\pi(a|s)))\right].$

Since its input additionally incorporates $\log\pi$, the discriminator is not
guaranteed to estimate the state-action distribution. Thus, the weighting in
Equation 14 loses a connection with the importance sampling ratio.

Experiments in Figure 1 show that WBCU simultaneously works well on the noisy
expert and full replay tasks, while prior methods like DemoDICE and DWBC
perform well only on one of them. We believe the discussion in Remark 1 can
partially explain the empirical observation. Next, we investigate the
theoretical foundation of WBCU.

###  5.1 Negative Result of WBCU With Tabular Representation

In this section, we consider parameterizing the discriminator $c$ by a huge
table (i.e., a vector with dimension $|{\mathcal{S}}||{\mathcal{A}}|$). We
present a surprising counter-intuitive result.

######  Proposition 2.

In the tabular case (with $\delta=0$), we have
$\pi^{\operatorname{WBCU}}=\pi^{\operatorname{BC}}$.

Proposition 2 shows that even if we have a large number of supplementary
samples and even if we use the importance sampling, WBCU is not guaranteed to
outperform BC, based on the tabular representation. We highlight that this
failure mode is because the discriminator has no extrapolation ability in this
case. Specifically, for an expert-style sample $(s,a)$ that _only_ appears in
the supplementary dataset, we have $\widehat{d^{\operatorname{E}}_{h}}(s,a)=0$
and $\widehat{d^{\operatorname{U}}_{h}}(s,a)>0$, so
$c^{\star}_{h}(s,a)=\widehat{d^{\operatorname{E}}_{h}}(s,a)/(\widehat{d^{\operatorname{E}}_{h}}(s,a)+\widehat{d^{\operatorname{U}}_{h}}(s,a))=0$.
That is, such a good sample does not contribute to the learning objective
(10). Intuitively, the tabular representation simply treats samples in a
discrete way, which ignores the correlation between samples.

Figure 2: Illustration for the learning scheme of WBCU under Assumption 2.

###  5.2 Positive Result of WBCU With Function Approximation

To bypass the hurdle in the previous section, we investigate WBCU with certain
function approximation in this section. To avoid the tabular/discrete
representation, we will consider “smooth” function approximators, which can
model the internal correlation between samples. Specifically, we consider the
discriminator to be parameterized by

$\displaystyle
c_{h}(s,a;\theta_{h})=\frac{1}{1+\exp(-\langle\phi_{h}(s,a),\theta_{h}\rangle)},$
(15)

where $\phi_{h}(s,a)\in{}^{d}$ is the feature vector (that can be learned by
neural networks), and $\theta_{h}\in{}^{d}$ is the parameter to train.
Accordingly, the optimization problem becomes:

$\displaystyle\min_{\theta_{h}}{\mathcal{L}}_{h}(\theta_{h})\triangleq\bigg{\\{}\sum_{(s,a)}\widehat{d^{\operatorname{E}}_{h}}(s,a)\left[\log\left(1+\exp\left(-\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)\right]+\sum_{(s,a)}\widehat{d^{\operatorname{U}}_{h}}(s,a)\left[\log\left(1+\exp\left(\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)\right]\bigg{\\}}.$
(16)

Let $\theta^{\star}=\\{\theta_{1}^{\star},\cdots,\theta_{H}^{\star}\\}$ be the
optimal solution obtained from Equation 16. Due to the side information in the
feature, samples are no longer treated independently, and the discriminator
can perform a structured estimation. We clarify that to be consistent with the
previous results, the policy is still based on the tabular representation. We
discuss the general function approximation of policy in Appendix C.

Since $c^{\star}$ is no longer analytic as in Equation 12, a natural question
is: what can we say about it? Our intuition is stated as follows. Let
${\mathcal{D}}^{\operatorname{S}}_{h}$ denote the set of samples in step $h$
in ${\mathcal{D}}^{\operatorname{S}}$. Since the behavior policy that collects
${\mathcal{D}}^{\operatorname{S}}_{h}$ is diverse, we can imagine
${\mathcal{D}}^{\operatorname{S}}_{h}$ contains two modes of samples: some of
them actually are also collected by the expert policy while others are not. In
the former case, we expect that $w_{h}(s,a)$ is large so that
$\widehat{d^{\operatorname{U}}_{h}}(s,a)w_{h}(s,a)\approx 1$, indicating such
a sample $(s,a)$ is likely collected by the expert. In the latter case, we
hope the discriminator can predict $w_{h}$ with a small value so that
$\widehat{d^{\operatorname{U}}_{h}}(s,a)w_{h}(s,a)\approx 0$, indicating it is
a non-expert sample. Notice that $w_{h}$ is monotone with respect to the inner
product $\langle\phi_{h}(s,a),\theta\rangle$; refer to Equations (13)(15).
Therefore, we conclude that a larger $\langle\phi_{h}(s,a),\theta\rangle$
means a significant contribution to the learning objective (10). Next, we
demonstrate that the above intuition can be achieved under mild assumptions.

######  Assumption 2 (Linear Separability).

Let
${\mathcal{D}}^{\operatorname{S}}={\mathcal{D}}^{\operatorname{S},1}\cup{\mathcal{D}}^{\operatorname{S},2}$
and
${\mathcal{D}}^{\operatorname{S},1}\cap{\mathcal{D}}^{\operatorname{S},2}=\emptyset$,
where ${\mathcal{D}}^{\operatorname{S},1}$ is collected by the expert policy
and ${\mathcal{D}}^{\operatorname{S},2}$ is collected by a sub-optimal policy
(but the algorithm does not know this split). For each time step $h\in[H]$,
there exists a ground truth parameter $\bar{\theta}_{h}\in{\mathbb{R}}^{d}$,
for any
$(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}$
and $(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}$, it
holds that

$\displaystyle\langle\bar{\theta}_{h},\phi_{h}(s,a)\rangle>0,\langle\bar{\theta}_{h},\phi_{h}(s^{\prime},a^{\prime})\rangle<0.$

Readers may realize that Assumption 2 is closely related to the notion of
“margin” in the classification problem. Define

$\displaystyle\Delta_{h}(\theta)\triangleq\bigg{\\{}$
$\displaystyle\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\langle\theta,\phi_{h}(s,a)\rangle-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\langle\theta,\phi_{h}(s^{\prime},a^{\prime})\rangle\bigg{\\}}.$

From Assumption 2, we have $\Delta_{h}(\bar{\theta}_{h})>0$. This means that
there _exists_ a classifier that recognizes samples from both
${\mathcal{D}}^{\operatorname{E}}_{h}$ and
${\mathcal{D}}^{\operatorname{S},1}_{h}$ as “good” samples, which contributes
to the objective (10). On the other hand, samples from
${\mathcal{D}}^{\operatorname{S},2}_{h}$ will be classified as “bad” samples,
which do not matter for the learned policy. Note that such a nice classifier
is assumed to exist, which is not identical to what is learned via Equation
16. Next, we theoretically control the (parameter) distance between two
classifiers.

Before further discussion, we note that $\bar{\theta}_{h}$ is not unique if it
exists. Without loss of generality, we define $\bar{\theta}_{h}$ as that can
achieve the maximum margin (among all unit vectors888Otherwise, the margin is
unbounded by multiplying $\bar{\theta}_{h}$ with a positive scalar.). To
theoretically characterize the movement of $\theta^{\star}$, we first
characterize the landscape properties (e.g., Lipschitz continuity and
quadratic growth conditions999These terminologies are from the optimization
literature (see, e.g., (Karimi et al., 2016; Drusvyatskiy and Lewis, 2018)).)
of $\Delta_{h}$ and ${\mathcal{L}}_{h}(\theta)$ in Lemma 1 and Lemma 2,
respectively.

######  Lemma 1 (Lipschitz Continuity).

For any $\theta\in{}^{d}$, the margin function is $L_{h}$-Lipschitz continuous
in the sense that

$\displaystyle\Delta_{h}(\bar{\theta}_{h})-\Delta_{h}(\theta)\leq
L_{h}\left\|\bar{\theta}_{h}-\theta\right\|,$

where $L_{h}=\left\|\phi_{h}(s^{1},a^{1})-\phi_{h}(s^{2},a^{2})\right\|$ with
$(s^{1},a^{1})\in\mathop{\rm
argmin}_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\langle\theta,\phi_{h}(s,a)\rangle$
and $(s^{2},a^{2})\in\\\ \mathop{\rm
argmax}_{(s,a)\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\langle\theta,\phi_{h}(s,a)\rangle$.

######  Lemma 2 (Quadratic Growth).

For any $h$, let $A_{h}\in{\mathbb{R}}^{N_{\operatorname{tot}}\times d}$ be
the matrix that aggregates the feature vectors of samples in
${\mathcal{D}}^{\operatorname{U}}_{h}$. Consider the under-parameterization
case that $\mathop{\bf rank}(A_{h})=d$. There exists $\tau_{h}>0$ such that

$\displaystyle{\mathcal{L}}_{h}(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h})\geq{\mathcal{L}}_{h}(\theta^{\star}_{h})+\frac{\tau_{h}}{2}\left\|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right\|^{2}$

######  Theorem 5.

Under Assumption 2, for any $h\in[H]$, if the following inequality holds

$\displaystyle\sqrt{\frac{2\left({\mathcal{L}}_{h}(\bar{\theta}_{h})-{\mathcal{L}}_{h}(\theta^{\star}_{h})\right)}{\tau_{h}}}<\frac{\Delta_{h}(\bar{\theta}_{h})}{L_{h}},$
(17)

then we have $\Delta_{h}(\theta^{\star}_{h})>0$.

To interpret Theorem 5, we note that $\Delta_{h}(\theta^{\star}_{h})>0$ means
that the learned discriminator can perfectly distinguish the good samples
(from ${\mathcal{D}}^{\operatorname{E}}_{h}$ and
${\mathcal{D}}^{\operatorname{S},1}_{h}$) and bad samples (from
${\mathcal{D}}^{\operatorname{S},2}_{h}$). In other words, if the feature
design is nice such that Inequality (17) holds, then the obtained classifier
can still maintain the decision results by $\bar{\theta}$; refer to Figure 2
for illustration. Consequently, all samples from
${\mathcal{D}}^{\operatorname{E}}_{h}$ and
${\mathcal{D}}^{\operatorname{S},1}_{h}$ are assigned large weights. In this
way, WBCU can leverage additional samples to outperform BC. Technically,
$\Delta_{h}(\theta_{h}^{\star})>0$ means that there exists a $\delta>0$ such
that we have $w_{h}(s,a)>\delta$ for
$(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}$
and $w_{h}(s,a)<\delta$ for $(s,a)\in{\mathcal{D}}^{\operatorname{S},2}_{h}$.
As such, WBCU can utilize the good samples
${\mathcal{D}}^{\operatorname{S},1}_{h}$ and eliminate the bad samples
${\mathcal{D}}^{\operatorname{S},2}_{h}$ in theory. The detailed imitation gap
bound depends on the number of trajectories in
${\mathcal{D}}^{\operatorname{E}}\cup{\mathcal{D}}^{\operatorname{S},1}$, and
this result is straightforward, so we omit details here.

Readers may ask whether inequality (17) can hold in practice. This question is
hard to answer because the coefficient $\tau_{h}$ and $L_{h}$ are data-
dependent. Nevertheless, we can provide a toy example to illustrate that
inequality (17) holds and give a sharp condition for $d=1$; please refer to
Appendix B for details. Further relaxation of the condition and assumption is
left for future work.

Figure 3: Averaged normalized scores of trained policies of WBCU with gradient
penalty (GP). Numbers in the legend indicate the scale of the GP
regularization.

Summary. Our theoretical analysis (Proposition 2 and Theorem 5) discloses that
the “smooth” function approximation is inevitable to achieve satisfying
performance. For practitioners, our results would suggest that regularization
techniques that control the smooth property of the function approximators may
improve the performance, which we empirically verify below.

Additional Experiments. We note that quite often, non-linear neural networks
rather than linear functions are used in practice. For neural networks, the
gradient penalty (GP) regularization101010This technique adds a squared loss
of the gradient norm to the original loss function; see Section D.1 for
details. is known to control the Lipschitz continuous property of the
discriminator (Gulrajani et al., 2017). In particular, a large gradient
penalty loss can push the discriminator to prefer 1-Lipschitz continuous
functions that are “smooth”. With the same set-up with experiments in Figure
1, we show that the gradient penalty is crucial for the practical performance
of WBCU; see Figure 3. A similar phenomenon is also observed for the related
algorithm DemoDICE; see Figure 6 in Appendix.

##  6 Conclusion

We theoretically explore imitation learning with a supplementary dataset, and
empirical results corroborate our findings. While our results have several
desirable features, they also have shortcomings. One limitation is that we
consider the tabular representation in policy learning. However, our
theoretical implications may remain unchanged if function approximation is
used. Please see Appendix C for discussion, which deserves further
investigation.

Exploring more applications of NBCU and WBCU is an interesting future work.
For example, for large language models (Radford et al., 2018), we may have
massive supplementary samples from the Web, while examples with human
annotations are limited. Compared with the existing reinforcement-learning-
based methods (see, e.g., (Stiennon et al., 2020)), training good policies may
be easier and more efficient by the developed imitation learning approaches.

## Acknowledgements

Ziniu Li would like to thank Yushun Zhang, Yingru Li, Jiancong Xiao, and
Dmitry Rybin for reading the manuscript and providing valuable comments. Tian
Xu would like to thank Fanming Luo, Zhilong Zhang, and Jingcheng Pang for
reading the manuscript and providing helpful comments. Ziniu Li appreciates
the helpful discussion with Congliang Chen about a technical lemma.

## References

  * Agarwal et al. [2020] A. Agarwal, S. Kakade, A. Krishnamurthy, and W. Sun.  Flambe: Structural complexity and representation learning of low rank mdps.  _Advances in Neural Information Processing Systems 33_ , pages 20095–20107, 2020.
  * Argall et al. [2009] B. D. Argall, S. Chernova, M. Veloso, and B. Browning.  A survey of robot learning from demonstration.  _Robotics and autonomous systems_ , 57(5):469–483, 2009.
  * Boyd et al. [2004] S. Boyd, S. P. Boyd, and L. Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Brown et al. [2019] D. Brown, W. Goo, P. Nagarajan, and S. Niekum.  Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations.  In _Proceedings of the 36th International Conference on Machine Learning_ , pages 783–792, 2019.
  * Diamond and Boyd [2016] S. Diamond and S. Boyd.  CVXPY: A Python-embedded modeling language for convex optimization.  _Journal of Machine Learning Research_ , 17(83):1–5, 2016.
  * Drusvyatskiy and Lewis [2018] D. Drusvyatskiy and A. S. Lewis.  Error bounds, quadratic growth, and linear convergence of proximal methods.  _Mathematics of Operations Research_ , 43(3):919–948, 2018.
  * Ghasemipour et al. [2019] S. K. S. Ghasemipour, R. S. Zemel, and S. Gu.  A divergence minimization perspective on imitation learning methods.  In _Proceedings of the 3rd Annual Conference on Robot Learning_ , pages 1259–1277, 2019.
  * Goodfellow et al. [2014] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. C. Courville, and Y. Bengio.  Generative adversarial nets.  In _Advances in Neural Information Processing Systems 27_ , pages 2672–2680, 2014.
  * Gulrajani et al. [2017] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville.  Improved training of wasserstein gans.  In _Advances in Neural Information Processing Systems 30_ , pages 5767–5777, 2017.
  * Haarnoja et al. [2018] T. Haarnoja, A. Zhou, P. Abbeel, and S. 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.
  * Ho and Ermon [2016] J. Ho and S. Ermon.  Generative adversarial imitation learning.  In _Advances in Neural Information Processing Systems 29_ , pages 4565–4573, 2016.
  * Kakade and Langford [2002] S. M. Kakade and J. Langford.  Approximately optimal approximate reinforcement learning.  In _Proceedings of the 17th International Conference on Machine Learning_ , pages 267–274, 2002.
  * Karimi et al. [2016] H. Karimi, J. Nutini, and M. Schmidt.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In _Proceeddings of The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases_ , pages 795–811, 2016.
  * Kim et al. [2022a] G.-H. Kim, J. Lee, Y. Jang, H. Yang, and K.-E. Kim.  Lobsdice: Offline imitation learning from observation via stationary distribution correction estimation.  _arXiv_ , 2202.13536, 2022a.
  * Kim et al. [2022b] G.-H. Kim, S. Seo, J. Lee, W. Jeon, H. Hwang, H. Yang, and K.-E. Kim.  DemoDICE: Offline imitation learning with supplementary imperfect demonstrations.  In _Proceedings of the 10th International Conference on Learning Representations_ , 2022b.
  * Kostrikov et al. [2019] I. Kostrikov, K. K. Agrawal, D. Dwibedi, S. Levine, and J. Tompson.  Discriminator-actor-critic: Addressing sample inefficiency and reward bias in adversarial imitation learning.  In _Proceedings of the 7th International Conference on Learning Representations_ , 2019.
  * Li et al. [2022] Z. Li, T. Xu, Y. Yu, and Z.-Q. Luo.  Rethinking valuedice: Does it really improve performance?  _arXiv_ , 2202.02468, 2022.
  * Liu et al. [2022] L. Liu, Z. Tang, L. Li, and D. Luo.  Robust imitation learning from corrupted demonstrations.  _arXiv_ , 2201.12594, 2022.
  * Ma et al. [2022] Y. J. Ma, A. Shen, D. Jayaraman, and O. Bastani.  Smodice: Versatile offline imitation learning via state occupancy matching.  In _Prooceedings of the 39th International Conference on Machine Learning_ , pages 14639–14663, 2022.
  * Osa et al. [2018] T. Osa, J. Pajarinen, G. Neumann, J. A. Bagnell, P. Abbeel, and J. Peters.  An algorithmic perspective on imitation learning.  _Foundations and Trends in Robotic_ , 7(1-2):1–179, 2018.
  * Pomerleau [1991] D. Pomerleau.  Efficient training of artificial neural networks for autonomous navigation.  _Neural Computation_ , 3(1):88–97, 1991.
  * Puterman [2014] M. L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, 2014.
  * Radford et al. [2018] A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al.  Improving language understanding by generative pre-training.  2018\.
  * Rajaraman et al. [2020] N. Rajaraman, L. F. Yang, J. Jiao, and K. Ramchandran.  Toward the fundamental limits of imitation learning.  In _Advances in Neural Information Processing Systems 33_ , pages 2914–2924, 2020.
  * Rajaraman et al. [2021] N. Rajaraman, Y. Han, L. Yang, J. Liu, J. Jiao, and K. Ramchandran.  On the value of interaction and function approximation in imitation learning.  In _Advances in Neural Information Processing Systems 34_ , pages 1325–1336, 2021.
  * Ross and Bagnell [2010] S. Ross and D. Bagnell.  Efficient reductions for imitation learning.  In _Proceedings of the 13rd International Conference on Artificial Intelligence and Statistics_ , pages 661–668, 2010.
  * Sasaki and Yamashina [2021] F. Sasaki and R. Yamashina.  Behavioral cloning from noisy demonstrations.  In _Proceedings of the 9th International Conference on Learning Representations_ , 2021.
  * Shapiro [2003] A. Shapiro.  Monte carlo sampling methods.  _Handbooks in operations research and management science_ , 10:353–425, 2003.
  * Spencer et al. [2021] J. Spencer, S. Choudhury, A. Venkatraman, B. Ziebart, and J. A. Bagnell.  Feedback in imitation learning: The three regimes of covariate shift.  _arXiv_ , 2102.02872, 2021.
  * Stiennon et al. [2020] N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems 33_ , pages 3008–3021, 2020.
  * Tangkaratt et al. [2020] V. Tangkaratt, B. Han, M. E. Khan, and M. Sugiyama.  Variational imitation learning with diverse-quality demonstrations.  In _Proceedings of the 37th International Conference on Machine Learning_ , pages 9407–9417, 2020.
  * Wang et al. [2021] Y. Wang, C. Xu, B. Du, and H. Lee.  Learning to weight imperfect demonstrations.  In _Proceedings of the 38th International Conference on Machine Learning_ , pages 10961–10970, 2021.
  * Wu et al. [2019] Y.-H. Wu, N. Charoenphakdee, H. Bao, V. Tangkaratt, and M. Sugiyama.  Imitation learning from imperfect demonstration.  In _Proceedings of the 36th International Conference on Machine Learning_ , pages 6818–6827, 2019.
  * Xu et al. [2022a] H. Xu, X. Zhan, H. Yin, and H. Qin.  Discriminator-weighted offline imitation learning from suboptimal demonstrations.  In _Prooceedings of the 39th International Conference on Machine Learning_ , pages 24725–24742, 2022a.
  * Xu et al. [2020] T. Xu, Z. Li, and Y. Yu.  Error bounds of imitating policies and environments.  In _Advances in Neural Information Processing Systems 33_ , pages 15737–15749, 2020.
  * Xu et al. [2021a] T. Xu, Z. Li, and Y. Yu.  Error bounds of imitating policies and environments for reinforcement learning.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021a.
  * Xu et al. [2021b] T. Xu, Z. Li, and Y. Yu.  More efficient adversarial imitation learning algorithms with known and unknown transitions.  _arXiv_ , 2106.10424, 2021b.
  * Xu et al. [2022b] T. Xu, Z. Li, Y. Yu, and Z.-Q. Luo.  Understanding adversarial imitation learning in small sample regime: A stage-coupled analysis.  _arXiv_ , 2208.01899, 2022b.

##  Appendix A Proof of Results in Section 4

######  Lemma 3.

For any $N\in\mathbb{N}_{+}$ and $p\in(0,1)$, if the random variable $X$
follows the binomial distribution, i.e., $X\sim\operatorname{Bin}(N,p)$, then
we have that

$\displaystyle\mathbb{E}\left[\frac{1}{X+1}\right]\leq\frac{1}{Np}.$

###### Proof.

$\displaystyle\mathbb{E}\left[\frac{1}{X+1}\right]$
$\displaystyle=\sum_{x=0}^{N}\left(\frac{1}{x+1}\right)\frac{N!}{x!(N-x)!}p^{x}(1-p)^{N-x}$
$\displaystyle=\frac{1}{(N+1)p}\sum_{x=1}^{N+1}\left(\frac{(N+1)!}{x!(N+1-x)!}\right)p^{x}(1-p)^{N+1-x}$
$\displaystyle=\frac{1}{(N+1)p}\left(1-(1-p)^{N+1}\right)\leq\frac{1}{Np}.$

∎

###  A.1 Proof of Theorem 1

When $|{\mathcal{D}}^{\operatorname{E}}|\geq 1$, by [Rajaraman et al., 2020,
Theorem 4.2], we have that

$\displaystyle
V(\pi^{\operatorname{E}})-\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{BC}})\right]\leq\frac{4|{\mathcal{S}}|H^{2}}{9|{\mathcal{D}}^{\operatorname{E}}|}.$

When $|{\mathcal{D}}^{\operatorname{E}}|=0$, we simply have that

$\displaystyle
V(\pi^{\operatorname{E}})-\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{BC}})\right]\leq
H.$

Therefore, we have the following unified bound.

$\displaystyle
V(\pi^{\operatorname{E}})-\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{BC}})\right]\leq\frac{|{\mathcal{S}}|H^{2}}{\max\\{|{\mathcal{D}}^{\operatorname{E}}|,1\\}}\leq\frac{2|{\mathcal{S}}|H^{2}}{|{\mathcal{D}}^{\operatorname{E}}|+1}.$

The last inequality follows that $\max\\{x,1\\}\geq(x+1)/2,\;\forall x\geq 0$.
Finally, notice that
$|{\mathcal{D}}^{\operatorname{E}}|\sim\operatorname{Bin}(N_{\operatorname{tot}},\eta)$.
By Lemma 3, we have that

$\displaystyle
V(\pi^{\operatorname{E}})-\mathbb{E}\left[V(\pi^{\operatorname{BC}})\right]\leq\mathbb{E}\left[\frac{2|{\mathcal{S}}|H^{2}}{|{\mathcal{D}}^{\operatorname{E}}|+1}\right]\leq\frac{2|{\mathcal{S}}|H^{2}}{N_{\operatorname{tot}}\eta}=\frac{2|{\mathcal{S}}|H^{2}}{N_{\operatorname{E}}},$

which completes the proof.

###  A.2 Proof of Theorem 2

For analysis, we first define the mixture state-action distribution as
follows.

$\displaystyle d^{\operatorname{mix}}_{h}(s,a)\triangleq\eta
d^{\pi^{\operatorname{E}}}_{h}(s,a)+(1-\eta)d^{\pi^{\beta}}_{h}(s,a),d^{\operatorname{mix}}_{h}(s)\triangleq\sum_{a\in{\mathcal{A}}}d^{\operatorname{mix}}_{h}(s,a),\;\forall(s,a)\in{\mathcal{S}}\times{\mathcal{A}},\;\forall
h\in[H].$

Note that in the population level, the marginal state-action distribution of
union dataset ${\mathcal{D}}^{\operatorname{U}}$ in time step $h$ is exactly
$d^{\operatorname{mix}}_{h}$. That is,
$d^{\operatorname{U}}_{h}(s,a)=d^{\operatorname{mix}}_{h}(s,a),\;\forall(s,a,h)\in{\mathcal{S}}\times{\mathcal{A}}\times[H]$.
Then we define the mixture policy $\pi^{\operatorname{mix}}$ induced by
$d^{\operatorname{mix}}$ as follows.

$\displaystyle\pi^{\operatorname{mix}}_{h}(a|s)=\begin{cases}\frac{d^{\operatorname{mix}}_{h}(s,a)}{d^{\operatorname{mix}}_{h}(s)}&\text{if
}d^{\operatorname{mix}}_{h}(s)>0,\\\
\frac{1}{|{\mathcal{A}}|}&\text{otherwise}.\end{cases}\;\forall(s,a)\in{\mathcal{S}}\times{\mathcal{A}}\;,\forall
h\in[H].$

From the theory of Markov Decision Processes, we know that (see, e.g.,
[Puterman, 2014])

$\displaystyle\forall
h\in[H],\forall(s,a)\in{\mathcal{S}}\times{\mathcal{A}},d^{\pi^{\operatorname{mix}}}_{h}(s,a)=d^{\operatorname{mix}}_{h}(s,a).$

Therefore, we can obtain that the marginal state-action distribution of union
dataset ${\mathcal{D}}^{\operatorname{U}}$ in time step $h$ is exactly
$d^{\pi^{\operatorname{mix}}}_{h}$. Then we have the following decomposition.

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]$
$\displaystyle=\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{mix}})+V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]$
$\displaystyle=\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{mix}})\right]+\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]$
$\displaystyle=V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{mix}})+\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right].$

For $V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{mix}})$, we have that

$\displaystyle V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{mix}})$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\left(d^{\pi^{\operatorname{E}}}_{h}(s,a)-d^{\pi^{\operatorname{mix}}}_{h}(s,a)\right)r_{h}(s,a)$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\left(d^{\pi^{\operatorname{E}}}_{h}(s,a)-d^{\operatorname{mix}}_{h}(s,a)\right)r_{h}(s,a)$
$\displaystyle=(1-\eta)\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\left(d^{\pi^{\operatorname{E}}}_{h}(s,a)-d^{\pi^{\beta}}_{h}(s,a)\right)r_{h}(s,a)$
$\displaystyle=(1-\eta)\left(V(\pi^{\operatorname{E}})-V(\pi^{\beta})\right).$

The last equation follows the dual formulation of policy value [Puterman,
2014]. Besides, notice that
$\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]$
is exactly the imitation gap of BC when regarding $\pi^{\operatorname{mix}}$
and ${\mathcal{D}}^{\operatorname{U}}$ as the expert policy and expert
demonstrations, respectively. By [Rajaraman et al., 2020, Theorem 4.4], we
have that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]\lesssim\frac{|{\mathcal{S}}|H^{2}\log(N_{\operatorname{tot}})}{N_{\operatorname{tot}}}.$

Combining the above two equations yields that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]\lesssim(1-\eta)\left(V(\pi^{\operatorname{E}})-V(\pi^{\beta})\right)+\frac{|{\mathcal{S}}|H^{2}\log(N_{\operatorname{tot}})}{N_{\operatorname{tot}}}.$

###  A.3 Proof of Proposition 1

We consider the instance named Standard Imitation in [Xu et al., 2021a]; see
Figure 4. In Standard Imitation, each state is an absorbing state. In each
state, only by taking the action $a^{1}$, the agent can obtain the reward of
$1$. Otherwise, the agent obtains zero rewards. The initial state distribution
is a uniform distribution, i.e., $\rho(s)=1/|{\mathcal{S}}|,\forall
s\in{\mathcal{S}}$.

Figure 4: The Standard Imitation MDP in [Xu et al., 2021a].

We consider that the expert policy $\pi^{\operatorname{E}}$ always takes the
action $a^{1}$ while the behavioral policy $\pi^{\beta}$ always takes another
action $a^{2}$. Formally, $\pi^{\operatorname{E}}_{h}(a^{1}|s)=1,\forall
s\in{\mathcal{S}},h\in[H],\;\pi^{\beta}_{h}(a^{2}|s)=1,\forall
s\in{\mathcal{S}},h\in[H]$. It is direct to calculate that
$V(\pi^{\operatorname{E}})=H$ and $V(\pi^{\beta})=0$. The supplementary
dataset ${\mathcal{D}}^{\operatorname{S}}$ and the expert dataset
${\mathcal{D}}^{\operatorname{E}}$ are collected according to Assumption 1.
The mixture state-action distribution can be calculated as $\forall
s\in{\mathcal{S}},h\in[H]$,

$\displaystyle d^{\operatorname{mix}}_{h}(s,a^{1})=\eta
d^{\pi^{\operatorname{E}}}_{h}(s,a^{1})+(1-\eta)d^{\pi^{\beta}}_{h}(s,a^{1})=\eta
d^{\pi^{\operatorname{E}}}_{h}(s,a^{1})=\eta\rho(s),$ $\displaystyle
d^{\operatorname{mix}}_{h}(s,a^{2})=\eta
d^{\pi^{\operatorname{E}}}_{h}(s,a^{2})+(1-\eta)d^{\pi^{\beta}}_{h}(s,a^{2})=(1-\eta)d^{\pi^{\beta}}_{h}(s,a^{2})=(1-\eta)\rho(s).$

Note that in the population level, the marginal distribution of the union
dataset ${\mathcal{D}}^{\operatorname{U}}$ in time step $h$ is exactly
$d^{\operatorname{mix}}_{h}$. The mixture policy induced by
$d^{\operatorname{mix}}$ can be formulated as

$\displaystyle\pi^{\operatorname{mix}}_{h}(a^{1}|s)=\eta,\pi^{\operatorname{mix}}_{h}(a^{2}|s)=1-\eta,\forall
s\in{\mathcal{S}},h\in[H].$

Just like before, we have
$d^{\pi^{\operatorname{mix}}}_{h}(s,a)=d^{\operatorname{mix}}_{h}(s,a)$. The
policy value of $\pi^{\operatorname{mix}}$ can be calculated as

$\displaystyle
V(\pi^{\operatorname{mix}})=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}d^{\operatorname{mix}}_{h}(s,a)r_{h}(s,a)=\sum_{h=1}^{H}\sum_{s\in{\mathcal{S}}}d^{\operatorname{mix}}_{h}(s,a^{1})=\eta
H.$

The policy $\pi^{\operatorname{NBCU}}$ can be formulated as

$\displaystyle\forall
h\in[H],\quad\pi^{\operatorname{NBCU}}_{h}(a|s)=\left\\{\begin{array}[]{ll}\frac{n^{\operatorname{U}}_{h}(s,a)}{\sum_{a^{\prime}}n^{\operatorname{U}}_{h}(s,a^{\prime})}&\text{if}\sum_{a^{\prime}}n^{\operatorname{U}}_{h}(s,a^{\prime})>0\\\
\frac{1}{|{\mathcal{A}}|}&\text{otherwise}\end{array}\right.$ (20)

We can view that the BC’s policy learned on the union dataset mimics the
mixture policy $\pi^{\operatorname{mix}}$. In the following part, we analyze
the lower bound on the imitation gap of $\pi^{\operatorname{NBCU}}$.

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]$
$\displaystyle=V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{mix}})+\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]$
$\displaystyle=H-\eta
H+\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]$
$\displaystyle=(1-\eta)(V(\pi^{\operatorname{E}})-V(\pi^{\beta}))+\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right].$

Then we consider the term
$\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]$.

$\displaystyle V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\left(d^{\pi^{\operatorname{mix}}}_{h}(s,a)-d^{\pi^{\operatorname{NBCU}}}_{h}(s,a)\right)r_{h}(s,a)$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)r_{h}(s,a)$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)r_{h}(s,a)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)>0\\}$
$\displaystyle\quad+\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)r_{h}(s,a)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)=0\\}.$

We take expectation over the randomness in ${\mathcal{D}}^{\operatorname{U}}$
on both sides and obtain that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]$
$\displaystyle=\mathbb{E}\left[\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)r_{h}(s,a)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)>0\\}\right]$
$\displaystyle\quad+\mathbb{E}\left[\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)r_{h}(s,a)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)=0\\}\right].$
(21)

For the first term in RHS, we have that

$\displaystyle\quad\mathbb{E}\left[\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)r_{h}(s,a)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)>0\\}\right]$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)r_{h}(s,a)\mathbb{E}\left[\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)>0\\}\right]$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)r_{h}(s,a){\mathbb{P}}\left(n^{\operatorname{U}}_{h}(s)>0\right)\mathbb{E}\left[\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)\bigg{|}n^{\operatorname{U}}_{h}(s)>0\right]$
$\displaystyle=0.$

The last equation follows the fact that when $n^{\operatorname{U}}_{h}(s)>0$,
$\pi^{\operatorname{NBCU}}_{h}(a|s)$ is an unbiased maximum likelihood
estimation of $\pi^{\operatorname{mix}}_{h}(a|s)$. For the remaining term, we
have that

$\displaystyle\quad\mathbb{E}\left[\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)r_{h}(s,a)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)=0\\}\right]$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)r_{h}(s,a)\mathbb{E}\left[\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)=0\\}\right]$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)r_{h}(s,a){\mathbb{P}}\left(n^{\operatorname{U}}_{h}(s)=0\right)\mathbb{E}\left[\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)\bigg{|}n^{\operatorname{U}}_{h}(s)=0\right]$
$\displaystyle=\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)r_{h}(s,a){\mathbb{P}}\left(n^{\operatorname{U}}_{h}(s)=0\right)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\frac{1}{|{\mathcal{A}}|}\right)$
$\displaystyle\overset{(a)}{=}\sum_{h=1}^{H}\sum_{s\in{\mathcal{S}}}\rho(s){\mathbb{P}}\left(n^{\operatorname{U}}_{h}(s)=0\right)\left(\eta-\frac{1}{|{\mathcal{A}}|}\right)$
$\displaystyle\overset{(b)}{=}H\left(\eta-\frac{1}{|{\mathcal{A}}|}\right)\sum_{s\in{\mathcal{S}}}\rho(s){\mathbb{P}}\left(n^{\operatorname{U}}_{1}(s)=0\right).$

In the equation $(a)$, we use the fact that
$r_{h}(s,a^{1})=1,r_{h}(s,a)=0,\forall a\in{\mathcal{A}}\setminus\\{a^{1}\\}$.
In the equation $(b)$, since each state is an absorbing state, we have that
${\mathbb{P}}\left(n^{\operatorname{U}}_{h}(s)=0\right)={\mathbb{P}}\left(n^{\operatorname{U}}_{1}(s)=0\right),\forall
h\in[H]$.

We consider two cases. In the first case of $\eta\geq 1/|{\mathcal{A}}|$, we
directly have that

$\displaystyle\mathbb{E}\left[\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\rho(s)\left(\pi^{\operatorname{mix}}_{h}(a|s)-\pi^{\operatorname{NBCU}}_{h}(a|s)\right)r_{h}(s,a)\mathbb{I}\\{n^{\operatorname{U}}_{h}(s)=0\\}\right]\geq
0.$

By Equation 21, we have that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]\geq
0,$

which implies that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]\geq(1-\eta)(V(\pi^{\operatorname{E}})-V(\pi^{\beta})).$

In the second case of $\eta<1/|{\mathcal{A}}|$, we have that

$\displaystyle
H\left(\eta-\frac{1}{|{\mathcal{A}}|}\right)\sum_{s\in{\mathcal{S}}}\rho(s){\mathbb{P}}\left(n^{\operatorname{U}}_{1}(s)=0\right)$
$\displaystyle\overset{(a)}{\geq}-\left(\frac{1}{|{\mathcal{A}}|}-\eta\right)H\exp\left(-\frac{N_{\operatorname{tot}}}{|{\mathcal{S}}|}\right)$
$\displaystyle\geq-(1-\eta)H\exp\left(-\frac{N_{\operatorname{tot}}}{|{\mathcal{S}}|}\right)$
$\displaystyle\overset{(b)}{\geq}-\frac{(1-\eta)H}{2}.$

In the inequality $(a)$, we use that

$\displaystyle\sum_{s\in{\mathcal{S}}}\rho(s){\mathbb{P}}\left(n^{\operatorname{U}}_{1}(s)=0\right)=\sum_{s\in{\mathcal{S}}}\rho(s)(1-\rho(s))^{N_{\operatorname{tot}}}=\left(1-\frac{1}{|{\mathcal{S}}|}\right)^{N_{\operatorname{tot}}}\leq\exp\left(-\frac{N_{\operatorname{tot}}}{|{\mathcal{S}}|}\right).$

The inequality $(b)$ holds since we consider the range where
$N_{\operatorname{tot}}\geq|{\mathcal{S}}|\log(2)$. By Equation 21, we have
that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{mix}})-V(\pi^{\operatorname{NBCU}})\right]\geq-\frac{(1-\eta)H}{2}.$

This implies that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]$
$\displaystyle\geq(1-\eta)(V(\pi^{\operatorname{E}})-V(\pi^{\beta}))-\frac{(1-\eta)H}{2}$
$\displaystyle=\frac{(1-\eta)}{2}(V(\pi^{\operatorname{E}})-V(\pi^{\beta})).$

In both cases, we prove that
$\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]\gtrsim(1-\eta)(V(\pi^{\operatorname{E}})-V(\pi^{\beta}))$
and thus complete the proof.

###  A.4 Proof of Theorem 3

When $\pi^{\beta}=\pi^{\operatorname{E}}$,
$\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\right]$
is exactly the imitation gap of BC on ${\mathcal{D}}^{\operatorname{U}}$ with
expert policy $\pi^{\operatorname{E}}$. By [Rajaraman et al., 2020, Theorem
4.2], we finish the proof.

###  A.5 Proof of Theorem 4

According to the policy difference lemma in [Kakade and Langford, 2002], we
have that

$\displaystyle V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})$
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{s_{h}\sim
d^{\pi^{\operatorname{E}}}_{h}(\cdot)}\left[Q^{\pi^{\operatorname{NBCU}}}_{h}(s_{h},\pi^{\operatorname{E}}_{h}(s_{h}))-\sum_{a\in{\mathcal{A}}}\pi^{\operatorname{NBCU}}_{h}(\cdot|s_{h})Q^{\pi^{\operatorname{NBCU}}}_{h}(s_{h},a)\right]$
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{s_{h}\sim
d^{\pi^{\operatorname{E}}}_{h}(\cdot)}\left[Q^{\pi^{\operatorname{NBCU}}}_{h}(s_{h},\pi^{\operatorname{E}}_{h}(s_{h}))(1-\pi^{\operatorname{NBCU}}_{h}(\pi^{\operatorname{E}}_{h}(s_{h})|s_{h}))\right]$
$\displaystyle\leq H\sum_{h=1}^{H}\mathbb{E}_{s\sim
d^{\pi^{\operatorname{E}}}_{h}(\cdot)}\left[\mathbb{E}_{a\sim\pi^{\operatorname{NBCU}}_{h}(\cdot|s)}\left[\mathbb{I}\left\\{a\not=\pi^{\operatorname{E}}_{h}(s)\right\\}\right]\right],$

where
$Q^{\pi}_{h}(s,a)=\mathbb{E}[\sum_{t=h}^{H}r(s_{t},a_{t})|(s_{h},a_{h})=(s,a)]$
is the state-action value function for a policy $\pi$ and
$\pi^{\operatorname{E}}_{h}(s_{h})$ denotes the expert action. By assumption,
we have $\forall h\in[H]$,
$\mathrm{supp}(d^{\pi^{\operatorname{E}}}_{h}(\cdot))\cap\mathrm{supp}(d^{\pi^{\beta}}_{h}(\cdot))=\emptyset$.
Therefore, we know that the union state-action pairs in
${\mathcal{D}}^{\operatorname{U}}$ does not affect $\pi^{\operatorname{NBCU}}$
on expert states. As a result, $\pi^{\operatorname{NBCU}}$ exactly takes
expert actions on states visited in ${\mathcal{D}}^{\operatorname{E}}$. Then
we have that

$\displaystyle V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{NBCU}})\leq
H\sum_{h=1}^{H}\mathbb{E}_{s\sim
d^{\pi^{\operatorname{E}}}_{h}(\cdot)}\left[\mathbb{I}\left\\{s\notin{\mathcal{S}}_{h}({\mathcal{D}}^{\operatorname{E}})\right\\}\right],$

where ${\mathcal{S}}_{h}({\mathcal{D}}^{\operatorname{E}})$ is the set of
states in time step $h$ in ${\mathcal{D}}^{\operatorname{E}}$. Taking
expectation over the randomness within ${\mathcal{D}}^{\operatorname{E}}$ on
both sides yields that

$\displaystyle
V(\pi^{\operatorname{E}})-\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{NBCU}})\right]\leq
H\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[\sum_{h=1}^{H}\mathbb{E}_{s\sim
d^{\pi^{\operatorname{E}}}_{h}(\cdot)}\left[\mathbb{I}\left\\{s\notin{\mathcal{S}}_{h}({\mathcal{D}}^{\operatorname{E}})\right\\}\right]\right].$

By [Rajaraman et al., 2020, Lemma A.1], we further derive that

$\displaystyle
V(\pi^{\operatorname{E}})-\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{NBCU}})\right]\leq\frac{|{\mathcal{S}}|H^{2}}{\max\\{|{\mathcal{D}}^{\operatorname{E}}|,1\\}}\leq\frac{2|{\mathcal{S}}|H^{2}}{|{\mathcal{D}}^{\operatorname{E}}|+1}.$

We take expectation over the binomial variable
$|{\mathcal{D}}^{\operatorname{E}}|$ and have that

$\displaystyle
V(\pi^{\operatorname{E}})-\mathbb{E}\left[V(\pi^{\operatorname{NBCU}})\right]\leq\mathbb{E}\left[\frac{2|{\mathcal{S}}|H^{2}}{|{\mathcal{D}}^{\operatorname{E}}|+1}\right]\leq\frac{2|{\mathcal{S}}|H^{2}}{N_{\operatorname{tot}}\eta}=\frac{2|{\mathcal{S}}|H^{2}}{N_{\operatorname{E}}},$

which completes the proof.

##  Appendix B Proof of Results in Section 5

###  B.1 Proof of Proposition 2

In the tabular case, with the first-order optimality condition, we have
$c^{\star}_{h}(s,a)=\widehat{d^{\operatorname{E}}_{h}}(s,a)/(\widehat{d^{\operatorname{E}}_{h}}(s,a)+\widehat{d^{\operatorname{U}}_{h}}(s,a))$.
By Equation 13, we have

$\displaystyle\widehat{d^{\operatorname{U}}_{h}}(s,a)w_{h}(s,a)=\widehat{d^{\operatorname{U}}_{h}}(s,a)\times\frac{\widehat{d^{\operatorname{E}}_{h}}(s,a)}{\widehat{d^{\operatorname{U}}_{h}}(s,a)}=\widehat{d^{\operatorname{E}}_{h}}(s,a).$

Hence, the learning objective (10) reduces to (1).

###  B.2 Proof of Lemma 1

Recall that

$\displaystyle\Delta_{h}(\theta)=\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\langle\theta,\phi_{h}(s,a)\rangle-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\langle\theta,\phi_{h}(s^{\prime},a^{\prime})\rangle.$

Then we have that

$\displaystyle\Delta_{h}(\bar{\theta}_{h})-\Delta_{h}(\theta)$
$\displaystyle=\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\langle\bar{\theta}_{h},\phi_{h}(s,a)\rangle-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\langle\bar{\theta}_{h},\phi_{h}(s^{\prime},a^{\prime})\rangle$
$\displaystyle\quad-\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\langle\theta,\phi_{h}(s,a)\rangle+\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\langle\theta,\phi_{h}(s^{\prime},a^{\prime})\rangle$
$\displaystyle\overset{(a)}{\leq}\langle\bar{\theta}_{h},\phi_{h}(s^{1},a^{1})\rangle-\langle\bar{\theta}_{h},\phi_{h}(s^{2},a^{2})\rangle-\langle\theta,\phi_{h}(s^{1},a^{1})\rangle+\langle\theta,\phi_{h}(s^{2},a^{2})\rangle$
$\displaystyle=\langle\bar{\theta}_{h}-\theta,\phi_{h}(s^{1},a^{1})-\phi_{h}(s^{2},a^{2})\rangle$
$\displaystyle\overset{(b)}{\leq}\left\|\bar{\theta}_{h}-\theta\right\|\left\|\phi_{h}(s^{1},a^{1})-\phi_{h}(s^{2},a^{2})\right\|.$

In inequality $(a)$, we utilize the facts that $(s^{1},a^{1})\in\mathop{\rm
argmin}_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\langle\theta_{h},\phi_{h}(s,a)\rangle$
and
$(s^{2},a^{2})\in\mathop{\rm
argmax}_{(s,a)\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\langle\theta_{h},\phi_{h}(s,a)\rangle$.
Inequality $(b)$ follows the Cauchy–Schwarz inequality. Let
$L_{h}=\left\|\phi_{h}(s^{1},a^{1})-\phi_{h}(s^{2},a^{2})\right\|$ and we
finish the proof.

###  B.3 Proof of Lemma 2

First, by Taylor’s Theorem, there exists
$\theta_{h}^{\prime}\in\\{\theta\in{\mathbb{R}}^{d}:\theta^{t}=\theta^{\star}_{h}+t(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}),\;\forall t\in[0,1]\\}$ such that

$\displaystyle{\mathcal{L}}_{h}(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h})$
$\displaystyle={\mathcal{L}}_{h}(\theta^{\star}_{h})+\langle\nabla{\mathcal{L}}_{h}(\theta^{\star}_{h}),\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\rangle+\frac{1}{2}\left(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right)^{\top}\nabla^{2}{\mathcal{L}}_{h}(\theta_{h}^{\prime})\left(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right)$
$\displaystyle={\mathcal{L}}_{h}(\theta^{\star}_{h})+\frac{1}{2}\left(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right)^{\top}\nabla^{2}{\mathcal{L}}_{h}(\theta_{h}^{\prime})\left(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right).$ (22)

The last equality follows the optimality condition that
$\nabla{\mathcal{L}}_{h}(\theta^{\star}_{h})=0$. Then, our strategy is to
prove that the smallest eigenvalue of the Hessian matrix
$\nabla^{2}{\mathcal{L}}_{h}(\theta_{h}^{\prime})$ is positive, i.e.,
$\lambda_{\min}(\nabla^{2}{\mathcal{L}}_{h}(\theta_{h}^{\prime}))>0$. We first
calculate the Hessian matrix
$\nabla^{2}{\mathcal{L}}_{h}(\theta_{h}^{\prime})$. Given
${\mathcal{D}}^{\operatorname{E}}$ and ${\mathcal{D}}^{\operatorname{U}}$, we
define the function
$G:{\mathbb{R}}^{(|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|)}\rightarrow{\mathbb{R}}$
as

$\displaystyle
G(v)\triangleq\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{i=1}^{|{\mathcal{D}}^{\operatorname{E}}|}g(v_{i})+\frac{1}{|{\mathcal{D}}^{\operatorname{U}}|}\sum_{j=1}^{|{\mathcal{D}}^{\operatorname{U}}|}g(v_{j}),$

where $v_{i}$ is the $i$-th element in the vector
$v\in{\mathbb{R}}^{(|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|)}$
and $g(x)=\log\left(1+\exp(x)\right)$ is a real-valued function. Besides, we
use
$B_{h}\in{\mathbb{R}}^{(|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|)\times
d}$ to denote the matrix whose $i$-th row
$B_{h,i}=-y_{i}\phi_{h}(s^{i},a^{i})^{\top}$, and $y_{i}=1$ if
$(s^{i},a^{i})\in{\mathcal{D}}^{\operatorname{E}}_{h}$, $y_{i}=-1$ if
$(s^{i},a^{i})\notin{\mathcal{D}}^{\operatorname{E}}_{h}$. Then the objective
function can be reformulated as

$\displaystyle{\mathcal{L}}_{h}(\theta_{h})$
$\displaystyle=\sum_{(s,a)}\widehat{d^{\operatorname{E}}_{h}}(s,a)\left[\log\left(1+\exp\left(-\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)\right]+\sum_{(s,a)}\widehat{d^{\operatorname{U}}_{h}}(s,a)\left[\log\left(1+\exp\left(\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)\right]$
$\displaystyle=\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}}\log\left(1+\exp\left(-\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)+\frac{1}{|{\mathcal{D}}^{\operatorname{U}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{U}}}\log\left(1+\exp\left(\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)$
$\displaystyle=G(B_{h}\theta_{h}).$

Then we have that
$\nabla^{2}{\mathcal{L}}_{h}(\theta_{h})=B_{h}^{\top}\nabla^{2}G(B_{h}\theta_{h})B_{h}$,
where

$\displaystyle\nabla^{2}G(B_{h}\theta_{h})=\mathop{\bf
diag}\left(\frac{g^{\prime\prime}((B_{h}\theta_{h})_{1})}{|{\mathcal{D}}^{\operatorname{E}}|},\ldots,\frac{g^{\prime\prime}((B_{h}\theta_{h})_{|{\mathcal{D}}^{\operatorname{E}}|})}{|{\mathcal{D}}^{\operatorname{E}}|},\frac{g^{\prime\prime}((B_{h}\theta_{h})_{|{\mathcal{D}}^{\operatorname{E}}|+1})}{|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|},\ldots,\frac{g^{\prime\prime}((B_{h}\theta_{h})_{|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|})}{|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|}\right).$

Here $g^{\prime\prime}(x)=\sigma(x)(1-\sigma(x))$, where
$\sigma(x)=1/(1+\exp(-x))$ is the sigmoid function. The eigenvalues of
$\nabla^{2}G(B_{h}\theta_{h})$ are

$\displaystyle\left\\{\frac{g^{\prime\prime}((B_{h}\theta_{h})_{1})}{|{\mathcal{D}}^{\operatorname{E}}|},\ldots,\frac{g^{\prime\prime}((B_{h}\theta_{h})_{|{\mathcal{D}}^{\operatorname{E}}|})}{|{\mathcal{D}}^{\operatorname{E}}|},\frac{g^{\prime\prime}((B_{h}\theta_{h})_{|{\mathcal{D}}^{\operatorname{E}}|+1})}{|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|},\ldots,\frac{g^{\prime\prime}((B_{h}\theta_{h})_{|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|})}{|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|}\right\\}.$

Notice that
$\theta_{h}^{\prime}\in\\{\theta\in{\mathbb{R}}^{d}:\theta^{t}=\theta^{\star}_{h}+t(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}),\;\forall t\in[0,1]\\}$. For a matrix $A$, we
use $\lambda_{\min}(A)$ to denote the minimal eigenvalue of $A$. Here we claim
that the minimum of the minimal eigenvalues of $\nabla^{2}G(B_{h}\theta^{t})$
over $t\in[0,1]$ is achieved at $t=0$ or $t=1$. That is,

$\displaystyle\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{t})):\forall
t\in[0,1]\\}=\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{0})),\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{1}))\\}.$

We prove this claim as follows. For any $t\in[0,1]$, we use
$\\{\lambda_{1}(t),\ldots,\lambda_{|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|}(t)\\}$
to denote the eigenvalues of $\nabla^{2}G(B_{h}\theta^{t})$. For each
$i\in[|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|]$,
we consider $\lambda_{i}(t):[0,1]\rightarrow{\mathbb{R}}$ as a function of
$t$. Specifically,

$\displaystyle\lambda_{i}(t)=\begin{cases}\frac{g^{\prime\prime}((B_{h}\theta^{\star}_{h})_{i}+t(B_{h}(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}))_{i})}{|{\mathcal{D}}^{\operatorname{E}}|},&\quad\text{if
}i\in[|{\mathcal{D}}^{\operatorname{E}}|]\\\
\frac{g^{\prime\prime}((B_{h}\theta^{\star}_{h})_{i}+t(B_{h}(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}))_{i})}{|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|},&\quad\text{otherwise}.\end{cases}$

We observe that
$g^{\prime\prime\prime}(x)=\sigma(x)(1-\sigma(x))(1-2\sigma(x))$ which
satisfies that $\forall x\leq 0,\;g^{\prime\prime\prime}(x)\geq 0,$ and
$\forall x\geq 0,\;g^{\prime\prime\prime}(x)\leq 0$. Therefore, we have that
the minimum of $\lambda_{i}(t)$ over $t\in[0,1]$ must be achieved at $t=0$ or
$t=1$. That is,

$\displaystyle\min_{t\in[0,1]}\lambda_{i}(t)=\min\\{\lambda_{i}(0),\lambda_{i}(1)\\}.$
(23)

For any $t\in[0,1]$, we define
$i^{t}\in[|{\mathcal{D}}^{\operatorname{E}}|+|{\mathcal{D}}^{\operatorname{U}}|]$
as the index of the minimal eigenvalue of $\nabla^{2}G(B_{h}\theta^{t})$,
i.e., $\lambda_{i^{t}}(t)=\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{t}))$. Then
we have that

$\displaystyle\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{t})):\forall
t\in[0,1]\\}$ $\displaystyle=\min\\{\lambda_{i^{t}}(t):\forall t\in[0,1]\\}$
$\displaystyle\overset{(a)}{=}\min\\{\min\\{\lambda_{i^{t}}(0),\lambda_{i^{t}}(1)\\}:\forall
t\in[0,1]\\}$ $\displaystyle=\min\\{\lambda_{i^{0}}(0),\lambda_{i^{1}}(1)\\}$
$\displaystyle\overset{(b)}{=}\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{0})),\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{1}))\\}$

Equality $(a)$ follows (23) and equality $(b)$ follows that
$\lambda_{i^{0}}(0)$ and $\lambda_{i^{1}}(1)$ are the minimal eigenvalues of
$\nabla^{2}G(B_{h}\theta^{0})$ and $\nabla^{2}G(B_{h}\theta^{1})$,
respectively.

In summary, we derive that

$\displaystyle\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{t})):\forall
t\in[0,1]\\}=\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{0})),\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{1}))\\},$
(24)

which proves the previous claim.

Further, we consider
$\lambda_{\min}\left(\nabla^{2}{\mathcal{L}}_{h}(\theta_{h})\right)$.

$\displaystyle\lambda_{\min}\left(\nabla^{2}{\mathcal{L}}_{h}(\theta_{h})\right)$
$\displaystyle=\inf_{x\in{\mathbb{R}}^{d}:\left\|x\right\|=1}x^{\top}\nabla^{2}{\mathcal{L}}_{h}(\theta_{h})x$
$\displaystyle=\inf_{x\in{\mathbb{R}}^{d}:\left\|x\right\|=1}\left(B_{h}x\right)^{\top}\nabla^{2}G(B_{h}\theta_{h})\left(B_{h}x\right)$
$\displaystyle=\inf_{z\in\operatorname{Im}(B_{h})}z^{\top}\nabla^{2}G(B_{h}\theta_{h})z$
$\displaystyle=\left(\inf_{z\in\operatorname{Im}(B_{h})}\left\|z\right\|\right)^{2}\lambda_{\min}(\nabla^{2}G(B_{h}\theta_{h}))$
$\displaystyle\geq\left(\inf_{z\in\operatorname{Im}(B_{h})}\left\|z\right\|\right)^{2}\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{0})),\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{1}))\\}.$

Here
$\operatorname{Im}(B_{h})=\\{z\in{\mathbb{R}}^{d}:z=B_{h}x,\left\|x\right\|=1\\}$.
The last inequality follows Equation 24.

In the under-parameterization case where $\mathop{\bf rank}(A_{h})=d$, we have
that $\mathop{\bf rank}(B_{h})=d$. Thus, $\operatorname{Im}(B_{h})$ is a set
of vectors with positive norms, i.e.,
$\inf_{z\in\operatorname{Im}(B_{h})}\left\|z\right\|>0$. Besides, since
$g^{\prime\prime}(x)=\sigma(x)(1-\sigma(x))>0$, we also have that

$\displaystyle\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{0})),\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{1}))\\}>0.$

In summary, we obtain that

$\displaystyle\lambda_{\min}\left(\nabla^{2}{\mathcal{L}}_{h}(\theta_{h})\right)\geq\left(\inf_{z\in\operatorname{Im}(B_{h})}\left\|z\right\|\right)^{2}\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{0})),\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{1}))\\}>0.$

Then, with Equation 22, there exists
$\tau_{h}=\left(\inf_{z\in\operatorname{Im}(B_{h})}\left\|z\right\|\right)^{2}\min\\{\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{0})),\lambda_{\min}(\nabla^{2}G(B_{h}\theta^{1}))\\}>0$
such that

$\displaystyle{\mathcal{L}}_{h}(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h})\geq{\mathcal{L}}_{h}(\theta^{\star}_{h})+\frac{\tau_{h}}{2}\left\|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right\|^{2},$

which completes the proof.

###  B.4 Proof of Theorem 5

First, invoking Lemma 1 with $\theta=\theta^{\star}_{h}$ yields that

$\displaystyle\Delta_{h}(\theta^{\star}_{h})\geq\Delta_{h}(\bar{\theta}_{h})-L_{h}\left\|\bar{\theta}_{h}-\theta^{\star}_{h}\right\|.$

Here $L_{h}=\left\|\phi_{h}(s,a)-\phi_{h}(s^{\prime},a^{\prime})\right\|$ with
$(s,a)\in\mathop{\rm
argmin}_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\langle\theta^{\star}_{h},\phi_{h}(s,a)\rangle$
and
$(s^{\prime},a^{\prime})\in\mathop{\rm
argmax}_{(s,a)\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\langle\theta^{\star}_{h},\phi_{h}(s,a)\rangle$.
Then, by Lemma 2, there exists $\tau_{h}>0$ such that

$\displaystyle{\mathcal{L}}_{h}(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h})\geq{\mathcal{L}}_{h}(\theta^{\star}_{h})+\frac{\tau_{h}}{2}\left\|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right\|^{2}.$

This directly implies an upper bound of the distance between $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}$ and $\theta^{\star}_{h}$.

$\displaystyle\left\|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right\|\leq\sqrt{\frac{2\left({\mathcal{L}}_{h}(\bar{\theta}_{h})-{\mathcal{L}}_{h}(\theta^{\star}_{h})\right)}{\tau_{h}}}.$

When inequality $(\ref{eq:condition})$ holds, we further have that
$\left\|\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}-\theta^{\star}_{h}\right\|<\Delta_{h}(\bar{\theta}_{h})/L_{h}$. Then
we get that

$\displaystyle\Delta_{h}(\theta^{\star}_{h})\geq\Delta_{h}(\bar{\theta}_{h})-L_{h}\left\|\bar{\theta}_{h}-\theta^{\star}_{h}\right\|>0,$

which completes the proof.

###  B.5 An Example Corresponding to Theorem 5

######  Example 1.

To illustrate Theorem 5, we consider an example in the feature space
${\mathbb{R}}^{2}$. In particular, for time step $h\in[H]$, we have the expert
dataset and supplementary dataset as follows.

$\displaystyle{\mathcal{D}}^{\operatorname{E}}_{h}=\left\\{\left(s^{(1)},a^{(1)}\right),\left(s^{(4)},a^{(4)}\right)\right\\},\;{\mathcal{D}}^{\operatorname{S}}_{h}=\left\\{\left(s^{(2)},a^{(2)}\right),\left(s^{(3)},a^{(3)}\right)\right\\},\;$
$\displaystyle{\mathcal{D}}^{\operatorname{S},1}_{h}=\left\\{\left(s^{(2)},a^{(2)}\right)\right\\},\;{\mathcal{D}}^{\operatorname{S},2}_{h}=\left\\{\left(s^{(3)},a^{(3)}\right)\right\\}.$

The corresponding features are

$\displaystyle\phi_{h}\left(s^{(1)},a^{(1)}\right)=(0,1)^{\top},\;\phi_{h}\left(s^{(2)},a^{(2)}\right)=\left(-\frac{1}{2},0\right)^{\top},$
$\displaystyle\phi_{h}\left(s^{(3)},a^{(3)}\right)=\left(0,-\frac{1}{2}\right)^{\top},\;\phi_{h}\left(s^{(4)},a^{(4)}\right)=(-1,0)^{\top}.$

Notice that the set of expert-style samples is
${\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}=\\{(s^{(1)},a^{(1)}),(s^{(2)},a^{(2)}),(s^{(4)},a^{(4)})\\}$
and the set of non-expert-style samples is
${\mathcal{D}}^{\operatorname{S},2}_{h}=\\{(s^{(3)},a^{(3)})\\}$. It is direct
to calculate that the ground-truth parameter that achieves the maximum margin
among unit vectors is $\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}=(-\sqrt{2}/2,\sqrt{2}/2)^{\top}$ and the maximum margin is
$\Delta_{h}(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h})=\sqrt{2}/2$. According to Equation 16, for
$\theta_{h}=(\theta_{h,1},\theta_{h,2})^{\top}$, the optimization objective is

$\displaystyle{\mathcal{L}}_{h}(\theta_{h})$
$\displaystyle=\sum_{(s,a)}\widehat{d^{\operatorname{E}}_{h}}(s,a)\left[\log\left(1+\exp\left(-\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)\right]+\sum_{(s,a)}\widehat{d^{\operatorname{U}}_{h}}(s,a)\left[\log\left(1+\exp\left(\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)\right]$
$\displaystyle=\frac{1}{2}\left(\log\left(1+\exp\left(-\theta_{h,2}\right)\right)+\log\left(1+\exp\left(\theta_{h,1}\right)\right)\right)$
$\displaystyle\quad+\frac{1}{4}\left(\log\left(1+\exp\left(\theta_{h,2}\right)\right)+\log\left(1+\exp\left(-\frac{1}{2}\theta_{h,1}\right)\right)\right)$
$\displaystyle\quad+\frac{1}{4}\left(\log\left(1+\exp\left(-\frac{1}{2}\theta_{h,2}\right)\right)+\log\left(1+\exp\left(-\theta_{h,1}\right)\right)\right).$

We apply CVXPY [Diamond and Boyd, 2016] to calculate the optimal solution
$\theta^{\star}_{h}\approx(-0.310,0.993)^{\top}$ and the objective values
${\mathcal{L}}_{h}(\theta^{\star}_{h})\approx
1.287,\;{\mathcal{L}}_{h}(\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h})\approx 1.309$. Furthermore, we calculate the Lipschitz coefficient
$L_{h}$ appears in Lemma 1.

$\displaystyle(s^{(2)},a^{(2)})=\mathop{\rm
argmin}_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\langle\theta^{\star}_{h},\phi_{h}(s,a)\rangle,\;(s^{(3)},a^{(3)})\in\mathop{\rm
argmax}_{(s,a)\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\langle\theta^{\star}_{h},\phi_{h}(s,a)\rangle,$
$\displaystyle
L_{h}=\left\|\phi_{h}(s^{(2)},a^{(2)})-\phi_{h}(s^{(3)},a^{(3)})\right\|=\frac{\sqrt{2}}{2}.$

Then we calculate the parameter of strong convexity $\tau_{h}$ 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 $\theta_{h}=(\theta_{h,1},\theta_{h,2})^{\top}$, the gradient of
${\mathcal{L}}_{h}(\theta_{h})$ is

$\displaystyle\nabla{\mathcal{L}}_{h}(\theta_{h})$
$\displaystyle=-\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{E}}_{h}}(s,a)\sigma(-\langle\phi_{h}(s,a),\theta_{h}\rangle)+\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{U}}_{h}}(s,a)\sigma\left(\langle\phi_{h}(s,a),\theta_{h}\rangle\right)$
$\displaystyle=\left(\frac{1}{2}\sigma(\theta_{h,1})-\frac{1}{4}\sigma(-\theta_{h,1})-\frac{1}{8}\sigma(-\frac{1}{2}\theta_{h,1}),\frac{1}{4}\sigma\left(\theta_{h,2}\right)-\frac{1}{2}\sigma\left(-\theta_{h,2}\right)-\frac{1}{8}\sigma(-\frac{1}{2}\theta_{h,2})\right)^{\top}.$

Here $\sigma(x)=1/(1+\exp(-x))$ for $x\in{\mathbb{R}}$ is the sigmoid
function. Then the Hessian matrix at $\theta_{h}$ is

$\displaystyle\nabla^{2}{\mathcal{L}}_{h}(\theta_{h})=\begin{pmatrix}\frac{3}{4}f(\theta_{h,1})+\frac{1}{16}f\left(\frac{1}{2}\theta_{h,1}\right)&0\\\
0&\frac{3}{4}f(\theta_{h,2})+\frac{1}{16}f\left(\frac{1}{2}\theta_{h,2}\right)\end{pmatrix},$

where $f(x)=\sigma(x)(1-\sigma(x))$ and $f(x)=f(-x)$. For any $t\in[0,1]$, the
eigenvalues of the Hessian matrix at $\theta^{t}_{h}=\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h}+t(\theta^{\star}_{h}-\macc@depth\char
1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a
111{}_{h})$ are

$\displaystyle\frac{3}{4}f(\theta^{t}_{h,1})+\frac{1}{16}f\left(\frac{1}{2}\theta^{t}_{h,1}\right),\;\frac{3}{4}f(\theta^{t}_{h,2})+\frac{1}{16}f\left(\frac{1}{2}\theta^{t}_{h,2}\right).$

Now, we calculate the minimal eigenvalues of
$\nabla^{2}{\mathcal{L}}_{h}(\theta^{t}_{h})$. We consider the function

$\displaystyle
g(x)=\frac{3}{4}f(x)+\frac{1}{16}f\left(\frac{1}{2}x\right),\;\forall
x\in[a,b].$

The gradient is

$\displaystyle
g^{\prime}(x)=\frac{3}{4}\sigma(x)(1-\sigma(x))(1-2\sigma(x))+\frac{1}{32}\sigma\left(\frac{1}{2}x\right)\left(1-\sigma\left(\frac{1}{2}x\right)\right)\left(1-2\sigma\left(\frac{1}{2}x\right)\right).$

We observe that $\forall x\leq 0,\;g^{\prime}(x)\geq 0,$ and $\forall x\geq
0,\;g^{\prime}(x)\leq 0$. Thus, we have that the minimum of $g(x)$ must be
achieved at $x=a$ or $x=b$. Besides, we have that $g(x)=g(-x)$. With the above
arguments, we know that the minimal eigenvalue is $g(0.993)\approx 0.163$ and
$\tau_{h}\approx 0.163$. Then we can calculate that

$\displaystyle\sqrt{\frac{2\left({\mathcal{L}}_{h}(\bar{\theta}_{h})-{\mathcal{L}}_{h}(\theta^{\star}_{h})\right)}{\tau_{h}}}\approx
0.520,\;\frac{\Delta_{h}(\bar{\theta}_{h})}{L_{h}}=1.$

The inequality (17) holds.

###  B.6 Additional Analysis of WBCU With Function Approximation

Here we provide an additional theoretical result for WBCU with function
approximation when $d=1$.

######  Theorem 6.

Consider $d=1$. For any $h\in[H]$, if the following inequality holds

$\displaystyle\frac{1}{|{\mathcal{D}}^{\operatorname{S}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\langle\phi_{h}(s,a),\bar{\theta}_{h}\rangle<\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{E}}_{h}}\langle\phi_{h}(s^{\prime},a^{\prime}),\bar{\theta}_{h}\rangle.$
(25)

then we have that $\Delta_{h}(\theta^{\star}_{h})>0$. Furthermore, the
inequality (25) is also a necessary condition.

Theorem 6 provides a clean and sharp condition to guarantee that the learned
discriminator can perfectly classify the high-quality samples from
${\mathcal{D}}^{\operatorname{E}}_{h}$ and
${\mathcal{D}}^{\operatorname{S},1}_{h}$, and low-quality samples from
${\mathcal{D}}^{\operatorname{S},2}_{h}$. In particular, inequality (25) means
that by the ground truth parameter $\bar{\theta}_{h}$, the average score of
samples in supplementary dataset is lower than that of samples in expert
dataset. This condition is easy to satisfy because the supplementary dataset
contains bad samples from ${\mathcal{D}}^{\operatorname{S},2}_{h}$ whose
scores are much lower. In contrast, ${\mathcal{D}}^{\operatorname{E}}$ only
contains expert-type samples with high scores.

###### Proof.

Recall the objective function

$\displaystyle\min_{\theta_{h}}{\mathcal{L}}_{h}(\theta_{h})=\sum_{(s,a)}\widehat{d^{\operatorname{E}}_{h}}(s,a)\log\left(1+\exp\left(-\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right)+\sum_{(s,a)}\widehat{d^{\operatorname{U}}_{h}}(s,a)\log\left(1+\exp\left(\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\right).$

Consider the function $f(x)=\log(1+\exp(x))$. We have that
$f^{\prime\prime}(x)=\sigma(x)(1-\sigma(x))\geq 0$, where
$\sigma(x)=1/(1+\exp(-x))$. As such, $f^{\prime\prime}(x)$ is a convex
function. Notice that the operations of composition with affine function and
non-negative weighted sum preserve convexity [Boyd et al., 2004]. Therefore,
${\mathcal{L}}_{h}(\theta_{h})$ is a convex function with respect to
$\theta_{h}$. Then for any $\widetilde{\theta}\in{\mathbb{R}}$, it holds that

$\displaystyle{\mathcal{L}}_{h}(\theta_{h})\geq{\mathcal{L}}_{h}(\widetilde{\theta})+\nabla{\mathcal{L}}_{h}(\widetilde{\theta})\left(\theta_{h}-\widetilde{\theta}\right).$

Setting $\theta_{h}=\theta^{\star}_{h}$ and $\widetilde{\theta}=0$ yields that

$\displaystyle\nabla{\mathcal{L}}_{h}(0)\theta^{\star}_{h}\leq{\mathcal{L}}_{h}(\theta^{\star}_{h})-{\mathcal{L}}_{h}(0).$
(26)

The gradient of ${\mathcal{L}}_{h}(\theta_{h})$ is of the form

$\displaystyle\nabla{\mathcal{L}}_{h}(\theta_{h})=-\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{E}}_{h}}(s,a)\sigma(-\langle\phi_{h}(s,a),\theta_{h}\rangle)\phi_{h}(s,a)+\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{U}}_{h}}(s,a)\sigma\left(\langle\phi_{h}(s,a),\theta_{h}\rangle\right)\phi_{h}(s,a).$

Here $\sigma(x)=1/(1+\exp(-x))$ is the sigmoid function. Then we calculate the
gradient at $\widetilde{\theta}=0$.

$\displaystyle\nabla{\mathcal{L}}_{h}(0)$
$\displaystyle=-\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{E}}_{h}}(s,a)\sigma(0)\phi_{h}(s,a)+\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{U}}_{h}}(s,a)\sigma\left(0\right)\phi_{h}(s,a)$
$\displaystyle=\frac{1}{2}\left(\frac{\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{U}}_{h}}\phi_{h}(s,a)}{|{\mathcal{D}}^{\operatorname{U}}|}-\frac{\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)}{|{\mathcal{D}}^{\operatorname{E}}|}\right)$
$\displaystyle=\frac{1}{2|{\mathcal{D}}^{\operatorname{U}}|}\left(\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{U}}_{h}}\phi_{h}(s,a)-\frac{|{\mathcal{D}}^{\operatorname{U}}|}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\right)$
$\displaystyle=\frac{1}{2|{\mathcal{D}}^{\operatorname{U}}|}\left(\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\phi_{h}(s,a)+\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)-\frac{|{\mathcal{D}}^{\operatorname{U}}|}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\right)$
$\displaystyle=\frac{1}{2|{\mathcal{D}}^{\operatorname{U}}|}\left(\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\phi_{h}(s,a)-\frac{|{\mathcal{D}}^{\operatorname{S}}|}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\right)$
$\displaystyle=\frac{|{\mathcal{D}}^{\operatorname{S}}|}{2|{\mathcal{D}}^{\operatorname{U}}|}\left(\frac{1}{|{\mathcal{D}}^{\operatorname{S}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\phi_{h}(s,a)-\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\right).$

Furthermore, with inequality (25), we know that

$\displaystyle\frac{1}{|{\mathcal{D}}^{\operatorname{S}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\phi_{h}(s,a)-\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\not=0.$

Therefore, $\nabla{\mathcal{L}}_{h}(0)\not=0$. With the first-order optimality
condition, we know that $0$ is not the optimal solution and
${\mathcal{L}}_{h}(0)>{\mathcal{L}}_{h}(\theta^{\star}_{h})$. Combined with
inequality (26), we have that

$\displaystyle\nabla{\mathcal{L}}_{h}(0)\theta^{\star}_{h}\leq{\mathcal{L}}_{h}(\theta^{\star}_{h})-{\mathcal{L}}_{h}(0)<0.$

This directly implies that

$\displaystyle\left(\frac{1}{|{\mathcal{D}}^{\operatorname{S}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\phi_{h}(s,a)-\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\right)\theta^{\star}_{h}<0.$

Besides, inequality (25) implies that

$\displaystyle\left(\frac{1}{|{\mathcal{D}}^{\operatorname{S}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\phi_{h}(s,a)-\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\right)\bar{\theta}_{h}<0.$

With the above two inequalities, we can derive that
$\theta^{\star}_{h}\bar{\theta}_{h}>0$. Then we have that

$\displaystyle\Delta_{h}(\theta^{\star}_{h})$
$\displaystyle=\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\theta^{\star}_{h}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\theta^{\star}_{h}\phi_{h}(s^{\prime},a^{\prime})$
$\displaystyle=\frac{\theta^{\star}_{h}}{\bar{\theta}_{h}}\left(\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\bar{\theta}_{h}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\bar{\theta}_{h}\phi_{h}(s^{\prime},a^{\prime})\right)$
$\displaystyle=\frac{\theta^{\star}_{h}}{\bar{\theta}_{h}}\Delta_{h}(\bar{\theta}_{h})$
$\displaystyle>0.$

Thus, the sufficiency of condition (25) is proved. Next, we prove the
necessity of condition (25). That is, if $\Delta_{h}(\theta^{\star}_{h})>0$,
then

$\displaystyle\frac{1}{|{\mathcal{D}}^{\operatorname{S}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\langle\phi_{h}(s,a),\bar{\theta}_{h}\rangle<\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S}}_{h}}\langle\phi_{h}(s^{\prime},a^{\prime}),\bar{\theta}_{h}\rangle.$

Then we aim to prove that $\theta^{\star}_{h}\bar{\theta}_{h}>0$. It is easy
to obtain that $\theta^{\star}_{h}\not=0$ and $\bar{\theta}_{h}\not=0$ since
$\Delta_{h}(\theta^{\star}_{h})>0$ and $\Delta_{h}(\bar{\theta}_{h})>0$. Then
we consider two cases where $\bar{\theta}_{h}>0$ and $\bar{\theta}_{h}<0$.

  * •

Case I ($\bar{\theta}_{h}>0$). In this case, we have that

$\displaystyle\Delta_{h}(\bar{\theta}_{h})$
$\displaystyle=\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\bar{\theta}_{h}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\bar{\theta}_{h}\phi_{h}(s^{\prime},a^{\prime})$
$\displaystyle=\bar{\theta}_{h}\left(\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\phi_{h}(s^{\prime},a^{\prime})\right).$

Then $\Delta_{h}(\bar{\theta}_{h})>0$ implies that

$\displaystyle\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\phi_{h}(s,a)>\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\phi_{h}(s^{\prime},a^{\prime}).$
(27)

Then we claim that $\theta^{\star}_{h}>0$. Otherwise, it holds that

$\displaystyle\Delta_{h}(\theta^{\star}_{h})$
$\displaystyle=\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\theta^{\star}_{h}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\theta^{\star}_{h}\phi_{h}(s^{\prime},a^{\prime})$
$\displaystyle=\theta^{\star}_{h}\left(\max_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\phi_{h}(s,a)-\min_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\phi_{h}(s^{\prime},a^{\prime})\right)$
$\displaystyle<0.$

The last inequality follows $\theta^{\star}_{h}<0$ and
$\max_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\phi_{h}(s,a)-\min_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\phi_{h}(s^{\prime},a^{\prime})>0$
due to inequality (27). Thus, the above inequality conflicts with
$\Delta_{h}(\theta^{\star}_{h})>0$. The claim that $\theta^{\star}_{h}>0$ is
proved and $\bar{\theta}_{h}\theta^{\star}_{h}>0$.

  * •

Case II ($\bar{\theta}_{h}<0$). Similarly, we get that

$\displaystyle\Delta_{h}(\bar{\theta}_{h})$
$\displaystyle=\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\bar{\theta}_{h}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\bar{\theta}_{h}\phi_{h}(s^{\prime},a^{\prime})$
$\displaystyle=\bar{\theta}_{h}\left(\max_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\phi_{h}(s,a)-\min_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\phi_{h}(s^{\prime},a^{\prime})\right).$

Then $\Delta_{h}(\bar{\theta}_{h})>0$ implies that

$\displaystyle\max_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\phi_{h}(s,a)<\min_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\phi_{h}(s^{\prime},a^{\prime}).$
(28)

Similar to the analysis in case I, we claim that $\theta^{\star}_{h}<0$.
Otherwise, it holds that

$\displaystyle\Delta_{h}(\theta^{\star}_{h})$
$\displaystyle=\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\theta^{\star}_{h}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\theta^{\star}_{h}\phi_{h}(s^{\prime},a^{\prime})$
$\displaystyle=\theta^{\star}_{h}\left(\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\phi_{h}(s^{\prime},a^{\prime})\right)$
$\displaystyle<0.$

The last inequality follows $\theta^{\star}_{h}>0$ and
$\min_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}\cup{\mathcal{D}}^{\operatorname{S},1}_{h}}\phi_{h}(s,a)-\max_{(s^{\prime},a^{\prime})\in{\mathcal{D}}^{\operatorname{S},2}_{h}}\phi_{h}(s^{\prime},a^{\prime})<0$
due to inequality (28). Thus, the above inequality conflicts with
$\Delta_{h}(\theta^{\star}_{h})>0$. The claim that $\theta^{\star}_{h}<0$ is
proved and $\bar{\theta}_{h}\theta^{\star}_{h}>0$.

To summarize, we have proved that $\bar{\theta}_{h}\theta^{\star}_{h}>0$.
Similar to the proof of the sufficient condition, by the convexity of
${\mathcal{L}}_{h}(\theta_{h})$ and optimality of $\theta^{\star}_{h}$, we can
obtain that

$\displaystyle\left(\frac{1}{|{\mathcal{D}}^{\operatorname{S}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\phi_{h}(s,a)-\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\right)\theta^{\star}_{h}<0.$

This directly implies that

$\displaystyle\left(\frac{1}{|{\mathcal{D}}^{\operatorname{S}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{S}}_{h}}\phi_{h}(s,a)-\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|}\sum_{(s,a)\in{\mathcal{D}}^{\operatorname{E}}_{h}}\phi_{h}(s,a)\right)\bar{\theta}_{h}<0,$

which completes the proof of necessity.

∎

##  Appendix C Behavioral Cloning with General Function Approximation

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 WBCU) can be unified under the framework of
maximum likelihood estimation (MLE)111111Among these algorithms, the main
difference is the weight function in the MLE objective; see Equations (1), (5)
and (14).. Therefore, the theoretical results in the main text can also be
extended to the setting of general function approximation by a similar
analysis.

We consider BC with general function approximation, which is the foundation of
analyzing NBCU and WBCU. In particular, we assume access to a policy class
$\Pi=\\{\pi=(\pi_{1},\pi_{2},\ldots,\pi_{h}):\;\pi_{h}\in\Pi_{h},\;\forall
h\in[H]\\}$ and
$\Pi_{h}=\\{\pi_{h}:{\mathcal{S}}\rightarrow\Delta({\mathcal{A}})\\}$, where
$\pi_{h}$ could be any function (e.g., neural networks). For simplicity of
analysis, we assume that $\Pi$ is a finite policy class. The objective of BC
is still

$\displaystyle\pi^{\operatorname{BC}}\in\max_{\pi\in\Pi}\sum_{h=1}^{H}\sum_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\widehat{d^{\operatorname{E}}_{h}}(s,a)\log\pi_{h}(a|s),$

but we do not have the analytic solution as in Equation 4.

######  Theorem 7.

Under Assumption 1. In the general function approximation, additionally assume
that $\pi^{\operatorname{E}}\in\Pi$, we have

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})\right]\lesssim\min\left\\{H,H^{2}\sqrt{\frac{\log(|\Pi|HN_{\operatorname{E}})}{N_{\operatorname{E}}}}\right\\}$

Compared with Theorem 1, we find that the only change in theoretical bound is
that ${\mathcal{O}}(|{\mathcal{S}}|/N_{\operatorname{E}})$ is replaced with
${\mathcal{O}}(\sqrt{\log(|\Pi|)/N_{\operatorname{E}}})$. We note that such a
change also holds for other algorithms (e.g., NBCU and WBCU). Therefore, our
theoretical implications remains unchanged.

###### Proof of Theorem 7.

We apply the policy difference lemma in [Kakade and Langford, 2002] and obtain
that

$\displaystyle V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})$
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{s_{h}\sim
d^{\pi^{\operatorname{E}}}_{h}(\cdot)}\left[Q^{\pi^{\operatorname{BC}}}_{h}(s_{h},\pi^{\operatorname{E}}_{h}(s_{h}))-\sum_{a\in{\mathcal{A}}}\pi^{\operatorname{BC}}_{h}(\cdot|s_{h})Q^{\pi^{\operatorname{BC}}}_{h}(s_{h},a)\right]$
$\displaystyle\leq\sum_{h=1}^{H}\mathbb{E}_{s_{h}\sim
d^{\pi^{\operatorname{E}}}_{h}(\cdot)}\left[Q^{\pi^{\operatorname{BC}}}_{h}(s_{h},\pi^{\operatorname{E}}_{h}(s_{h}))(1-\pi^{\operatorname{BC}}_{h}(\pi^{\operatorname{E}}_{h}(s_{h})|s_{h}))\right]$
$\displaystyle\leq H\sum_{h=1}^{H}\mathbb{E}_{s\sim
d^{\pi^{\operatorname{E}}}_{h}(\cdot)}\left[\mathbb{E}_{a\sim\pi^{\operatorname{BC}}_{h}(\cdot|s)}\left[\mathbb{I}\left\\{a\not=\pi^{\operatorname{E}}_{h}(s)\right\\}\right]\right]$
$\displaystyle=H\sum_{h=1}^{H}\mathbb{E}_{s_{h}\sim
d^{\operatorname{E}}_{h}(\cdot)}\left[\mathrm{TV}\left(\pi^{\operatorname{E}}_{h}(\cdot|s_{h}),\pi^{\operatorname{BC}}_{h}(\cdot|s_{h})\right)\right].$

With Theorem 21 in [Agarwal et al., 2020], when
$|{\mathcal{D}}^{\operatorname{E}}|\geq 1$, for any $\delta\in(0,1)$, with
probability at least $1-\delta$ over the randomness within
${\mathcal{D}}^{\operatorname{E}}$, we have that

$\displaystyle\mathbb{E}_{s_{h}\sim
d^{\operatorname{E}}_{h}(\cdot)}\left[\mathrm{TV}^{2}\left(\pi^{\operatorname{E}}_{h}(\cdot|s_{h}),\pi^{\operatorname{BC}}_{h}(\cdot|s_{h})\right)\right]\leq
2\frac{\log(|\Pi|/\delta)}{|{\mathcal{D}}^{\operatorname{E}}|}.$

With union bound, with probability at least $1-\delta$, for all $h\in[H]$, it
holds that

$\displaystyle\mathbb{E}_{s_{h}\sim
d^{\operatorname{E}}_{h}(\cdot)}\left[\mathrm{TV}^{2}\left(\pi^{\operatorname{E}}_{h}(\cdot|s_{h}),\pi^{\operatorname{BC}}_{h}(\cdot|s_{h})\right)\right]\leq
2\frac{\log(|\Pi|H/\delta)}{|{\mathcal{D}}^{\operatorname{E}}|},$

which implies that

$\displaystyle V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})$
$\displaystyle\leq H\sum_{h=1}^{H}\mathbb{E}_{s_{h}\sim
d^{\operatorname{E}}_{h}(\cdot)}\left[\mathrm{TV}\left(\pi^{\operatorname{E}}_{h}(\cdot|s_{h}),\pi^{\operatorname{BC}}_{h}(\cdot|s_{h})\right)\right]$
$\displaystyle\overset{(a)}{\leq}H\sum_{h=1}^{H}\sqrt{\mathbb{E}_{s_{h}\sim
d^{\operatorname{E}}_{h}(\cdot)}\left[\mathrm{TV}^{2}\left(\pi^{\operatorname{E}}_{h}(\cdot|s_{h}),\pi^{\operatorname{BC}}_{h}(\cdot|s_{h})\right)\right]}$
$\displaystyle\leq\sqrt{2}H^{2}\sqrt{\frac{\log(|\Pi|H/\delta)}{|{\mathcal{D}}^{\operatorname{E}}|}}.$

Inequality $(a)$ follows Jensen’s inequality. Taking expectation over the
randomness within ${\mathcal{D}}^{\operatorname{E}}$ yields that

$\displaystyle\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})\right]$
$\displaystyle\leq\delta
H+(1-\delta)\sqrt{2}H^{2}\sqrt{\frac{\log(|\Pi|H/\delta)}{|{\mathcal{D}}^{\operatorname{E}}|}}$
$\displaystyle\overset{(a)}{=}\frac{H}{2|{\mathcal{D}}^{\operatorname{E}}|}+\left(1-\frac{1}{2|{\mathcal{D}}^{\operatorname{E}}|}\right)\sqrt{2}H^{2}\sqrt{\frac{\log(2|\Pi|H|{\mathcal{D}}^{\operatorname{E}}|)}{|{\mathcal{D}}^{\operatorname{E}}|}}$
$\displaystyle\leq\left(\sqrt{2}+1\right)H^{2}\sqrt{\frac{\log(2|\Pi|H|{\mathcal{D}}^{\operatorname{E}}|)}{|{\mathcal{D}}^{\operatorname{E}}|}}$
$\displaystyle\leq
4H^{2}\sqrt{\frac{\log(4|\Pi|H|{\mathcal{D}}^{\operatorname{E}}|)}{|{\mathcal{D}}^{\operatorname{E}}|}}.$

Equation $(a)$ holds due to the choice that
$\delta=1/(2|{\mathcal{D}}^{\operatorname{E}}|)$. For
$|{\mathcal{D}}^{\operatorname{E}}|=0$, we directly have that

$\displaystyle\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})\right]\leq
H.$

Therefore, for any $|{\mathcal{D}}^{\operatorname{E}}|\geq 0$, we have that

$\displaystyle\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})\right]\leq
4H^{2}\sqrt{\frac{\log(4|\Pi|H\max\\{|{\mathcal{D}}^{\operatorname{E}}|,1\\})}{\max\\{|{\mathcal{D}}^{\operatorname{E}}|,1\\}}}.$

We consider a real-valued function $f(x)=\log(cx)/x,\;\forall x\geq 1$, where
$c=4|\Pi|H$. Its gradient function is $f^{\prime}(x)=(1-\log(cx))/x^{2}\leq
0,\;\forall x\geq 1$. Then we know that $f(x)$ is decreasing as $x$ increases.
Furthermore, we have that
$\max\\{|{\mathcal{D}}^{\operatorname{E}}|,1\\}\geq(|{\mathcal{D}}^{\operatorname{E}}|+1)/2,\;\forall|{\mathcal{D}}^{\operatorname{E}}|\geq
0$. Then we obtain

$\displaystyle\mathbb{E}_{{\mathcal{D}}^{\operatorname{E}}}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})\right]$
$\displaystyle\leq
4H^{2}\sqrt{\frac{\log(4|\Pi|H\max\\{|{\mathcal{D}}^{\operatorname{E}}|,1\\})}{\max\\{|{\mathcal{D}}^{\operatorname{E}}|,1\\}}}$
$\displaystyle\leq
4H^{2}\sqrt{\frac{2\log(4|\Pi|H(|{\mathcal{D}}^{\operatorname{E}}|+1))}{|{\mathcal{D}}^{\operatorname{E}}|+1}}.$

Taking expectation over the random variable
$|{\mathcal{D}}^{\operatorname{E}}|\sim\text{Bin}(N_{\operatorname{tot}},\eta)$
yields that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})\right]$
$\displaystyle\leq
4H^{2}\mathbb{E}\left[\sqrt{\frac{2\log(4|\Pi|H(|{\mathcal{D}}^{\operatorname{E}}|+1))}{|{\mathcal{D}}^{\operatorname{E}}|+1}}\right]$
$\displaystyle\overset{(a)}{\leq}4H^{2}\sqrt{\mathbb{E}\left[\frac{2\log(4|\Pi|H(|{\mathcal{D}}^{\operatorname{E}}|+1))}{|{\mathcal{D}}^{\operatorname{E}}|+1}\right]}.$

Inequality $(a)$ follows Jensen’s inequality. We consider the function
$g(x)=-x\log(x/c),\;\forall x\in(0,1]$, where $c=4|\Pi|H$.

$\displaystyle g^{\prime}(x)=-(\log(x/c)+1)\geq
0,\;g^{\prime\prime}(x)=-\frac{1}{x}\leq 0,\;\forall x\in(0,1].$

Thus, $g(x)$ is a concave function. By Jensen’s inequality, we have that
$\mathbb{E}[g(x)]\leq g(\mathbb{E}[x])$. Then we can derive that

$\displaystyle\mathbb{E}\left[V(\pi^{\operatorname{E}})-V(\pi^{\operatorname{BC}})\right]$
$\displaystyle\leq
4H^{2}\sqrt{\mathbb{E}\left[\frac{2\log(4|\Pi|H(|{\mathcal{D}}^{\operatorname{E}}|+1))}{|{\mathcal{D}}^{\operatorname{E}}|+1}\right]}$
$\displaystyle=4\sqrt{2}H^{2}\sqrt{\mathbb{E}\left[g\left(\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|+1}\right)\right]}$
$\displaystyle\leq
4\sqrt{2}H^{2}\sqrt{g\left(\mathbb{E}\left[\frac{1}{|{\mathcal{D}}^{\operatorname{E}}|+1}\right]\right)}$
$\displaystyle\overset{(a)}{\leq}4\sqrt{2}H^{2}\sqrt{g\left(\frac{1}{N_{\operatorname{E}}}\right)}$
$\displaystyle\leq
4\sqrt{2}H^{2}\sqrt{\frac{\log(4|\Pi|HN_{\operatorname{E}})}{N_{\operatorname{E}}}}.$

In inequality $(a)$, we use the facts that $g^{\prime}(x)\geq 0$ and
$\mathbb{E}\left[1/(|{\mathcal{D}}^{\operatorname{E}}|+1)\right]\leq
1/N_{\operatorname{E}}$ from Lemma 3. We complete the proof. ∎

##  Appendix D Experiments

###  D.1 Experiment Details

Dataset Collection. We train an online SAC agent [Haarnoja et al., 2018] with
1 million steps using the rlkit codebase121212https://github.com/rail-
berkeley/rlkit, which is the same as benchmark dataset
D4RL131313https://github.com/Farama-Foundation/D4RL. We use the deterministic
policy as the expert policy, which is common in the literature [Ho and Ermon,
2016] since the deterministic policy usually gives a better performance than
the stochastic policy; see Figure 5 for the training curves of online SAC.

Figure 5: Training curves of online SAC.

In our experiments, the expert dataset has 1 expert trajectory that is
collected by the trained SAC agent. Two tasks differ in the supplementary
dataset.

Noisy Expert Task. The supplementary dataset has 10 clean expert trajectories
and 5 noisy expert trajectories. For noisy trajectories, the action labels are
replaced with random actions (drawn from $[-1,1]$).

Full Replay Task. The supplementary dataset is from the replay buffer of the
online SAC agent, which has 1 million samples (roughly 1000+ trajectories).

Algorithm Implementation. The implementation of DemoDICE is based on the
original authors’ codebase141414https://github.com/KAIST-AILab/imitation-dice.
Same as DWBC151515https://github.com/ryanxhr/DWBC. We have fine-tuned the
hyper-parameters of DemoDICE and DWBC in our experiments but find that the
default parameters given by these authors work well. Following [Kim et al.,
2022b], we normalize state observations in the dataset before training for all
algorithms.

We use gradient penalty (GP) regularization in training the discriminator of
WBCU. Specifically, we add the following loss to the original loss (11):

$\displaystyle\min_{\theta}\left(\left\|g(s,a;\theta)\right\|-1\right)^{2},$

where $g$ is the gradient of the discriminator $c(s,a;\theta)$.

The implementation of NBCU and WBCU is adapted from DemoDICE’s. In particular,
both the discriminator and policy networks use the 2-layers MLP with 256
hidden units and ReLU activation. The batch size is 256 and learning rate
(using the Adam optimizer) is $0.0003$ for both the discriminator and policy.
The number of training iterations is 1 million. We use $\delta=0$ and GP=1,
unless mentioned. Please refer to our
codebase161616https://github.com/liziniu/ILwSD for details.

All experiments are run with 5 random seeds.

###  D.2 Additional Results

In this section, we report the exact performance of trained policies for each
MuJoCo locomotion control task. Training curves are displayed in Figure 8 and
Figure 9. The evaluation performance of the last 10 iterations is reported in
Table 2 and Table 3. The normalized score on a particular environment is
calculated by the following formula.

$\displaystyle\text{Normalized Score}=\frac{\text{Algorithm
Performance}-\text{Random Policy Performance}}{\text{Expert Policy
Performance}-\text{Random Policy Performance}}.$

In Table 2 and Table 3, the normalized score is averaged over 4 environments.

Training curves of WBCU and DemoDICE with gradient penalty are displayed in
Figure 10, Figure 11, Figure 12, and Figure 13.

Figure 6: Averaged normalized scores of trained policies of DemoDICE with gradient penalty. Experiments show that the gradient penalty regularization also matters for DemoDICE. Table 2: Performance of the trained policies by BC, DemoDICE [Kim et al., 2022b], DWBC [Xu et al., 2022a], NBCU (Algorithm 1), and WBCU (Algorithm 2) on the noisy-expert task. Numbers correspond to the averaged evaluation return over 5 random seeds ($\pm$ indicate the standard deviation); a lager return means better performance (same as other tables).  | Ant-v2 | HalfCheetah-v2 | Hopper-v2 | Walker2d-v2 | Normalized Score
---|---|---|---|---|---
Random | -325.6 | -280 | -20 | 2 | 0%
Expert | 5229 | 11115 | 3589 | 5082 | 100%
BC | $1759{\scriptscriptstyle\pm 287}$ | $931{\scriptscriptstyle\pm 273}$ | $2468{\scriptscriptstyle\pm 164}$ | $1738{\scriptscriptstyle\pm 311}$ | 38%
DemoDICE(GP=0) | $1893{\scriptscriptstyle\pm 181}$ | $2139{\scriptscriptstyle\pm 277}$ | $1823{\scriptscriptstyle\pm 169}$ | $563{\scriptscriptstyle\pm 34}$ | 31%
DemoDICE(GP=1) | $2492{\scriptscriptstyle\pm 235}$ | $5553{\scriptscriptstyle\pm 501}$ | $1320{\scriptscriptstyle\pm 319}$ | $1153{\scriptscriptstyle\pm 220}$ | 40%
DemoDICE(GP=10) | $2523{\scriptscriptstyle\pm 244}$ | $6020{\scriptscriptstyle\pm 346}$ | $1990{\scriptscriptstyle\pm 90}$ | $1685{\scriptscriptstyle\pm 160}$ | 49%
DWBC | $3270{\scriptscriptstyle\pm 238}$ | $5688{\scriptscriptstyle\pm 557}$ | $3317{\scriptscriptstyle\pm 59}$ | $1985{\scriptscriptstyle\pm 175}$ | 62%
NBCU | $3259{\scriptscriptstyle\pm 159}$ | $5561{\scriptscriptstyle\pm 539}$ | $558{\scriptscriptstyle\pm 23}$ | $518{\scriptscriptstyle\pm 56}$ | 35%
WBCU(GP=0) | $738{\scriptscriptstyle\pm 179}$ | $3828{\scriptscriptstyle\pm 333}$ | $2044{\scriptscriptstyle\pm 111}$ | $477{\scriptscriptstyle\pm 81}$ | 30%
WBCU(GP=1) | $2580{\scriptscriptstyle\pm 224}$ | $8274{\scriptscriptstyle\pm 488}$ | $3217{\scriptscriptstyle\pm 203}$ | $1932{\scriptscriptstyle\pm 329}$ | 64%
WBCU(GP=10) | $2130{\scriptscriptstyle\pm 259}$ | $7813{\scriptscriptstyle\pm 472}$ | $2930{\scriptscriptstyle\pm 229}$ | $1510{\scriptscriptstyle\pm 476}$ | 57%
Table 3: Performance of the trained policies by BC, DemoDICE [Kim et al., 2022b], DWBC [Xu et al., 2022a], NBCU (Algorithm 1), and WBCU (Algorithm 2) on the full-replay task.  | Ant-v2 | HalfCheetah-v2 | Hopper-v2 | Walker2d-v2 | Normalized Score
---|---|---|---|---|---
Random | -325.6 | -280 | -20 | 2 | 0%
Expert | 5229 | 11115 | 3589 | 5082 | 100%
BC | $1759{\scriptscriptstyle\pm 287}$ | $931{\scriptscriptstyle\pm 273}$ | $2468{\scriptscriptstyle\pm 164}$ | $1738{\scriptscriptstyle\pm 311}$ | 38%
DemoDICE(GP=0) | $4650{\scriptscriptstyle\pm 216}$ | $9882{\scriptscriptstyle\pm 270}$ | $39{\scriptscriptstyle\pm 0}$ | $4149{\scriptscriptstyle\pm 288}$ | 66%
DemoDICE(GP=1) | $5009{\scriptscriptstyle\pm 98}$ | $10701{\scriptscriptstyle\pm 70}$ | $3427{\scriptscriptstyle\pm 104}$ | $4560{\scriptscriptstyle\pm 146}$ | 94%
DemoDICE(GP=10) | $5000{\scriptscriptstyle\pm 124}$ | $10781{\scriptscriptstyle\pm 67}$ | $3394{\scriptscriptstyle\pm 93}$ | $4537{\scriptscriptstyle\pm 125}$ | 94%
DWBC | $2951{\scriptscriptstyle\pm 155}$ | $1485{\scriptscriptstyle\pm 377}$ | $2567{\scriptscriptstyle\pm 88}$ | $1572{\scriptscriptstyle\pm 225}$ | 44%
NBCU | $4932{\scriptscriptstyle\pm 148}$ | $10566{\scriptscriptstyle\pm 86}$ | $3241{\scriptscriptstyle\pm 276}$ | $4462{\scriptscriptstyle\pm 105}$ | 92%
WBCU(GP=0) | $483{\scriptscriptstyle\pm 79}$ | $-242{\scriptscriptstyle\pm 101}$ | $346{\scriptscriptstyle\pm 93}$ | $15{\scriptscriptstyle\pm 15}$ | 6%
WBCU(GP=1) | $4935{\scriptscriptstyle\pm 108}$ | $10729{\scriptscriptstyle\pm 74}$ | $3390{\scriptscriptstyle\pm 132}$ | $4509{\scriptscriptstyle\pm 142}$ | 94%
WBCU(GP=10) | $4858{\scriptscriptstyle\pm 95}$ | $10751{\scriptscriptstyle\pm 41}$ | $3436{\scriptscriptstyle\pm 37}$ | $4403{\scriptscriptstyle\pm 88}$ | 93%

######  Remark 2.

Readers may realize that NBCU actually is better than BC on the Ant-v2 and
HalfCheetah-v2 environments for the noisy-expert task, which seems to
contradict our theory. We clarify there is no contradiction. In fact, our
theory implies that in the worst case, NBCU is worse than BC. As we have
discussed in the main text, state coverage matters for NBCU’s performance. For
the noisy expert task, we visualize the state coverage in Figure 7, where we
use Kernel PCA171717https://scikit-
learn.org/stable/modules/generated/sklearn.decomposition.KernelPCA.html. We
use the “poly” kernel. to project states. In particular, we see that the state
coverage is relatively nice on Ant-v2 and HalfCheetah-v2, and somewhat bad on
Hopper-v2 and Walker2d-v2. This can help explain the performance difference
among these environments in Table 2.

(a) Ant-v2.

(b) Halfcheetah-v2.

(c) Hopper-v2.

(d) Walker2d-v2.

Figure 7: Visualization of the state coverage for the noisy expert task.
According to the experiment set-up, red points correspond to good samples and
blue points correspond to noisy and bad samples. Plots show that the state
overlap between two modes of samples is large for Hopper-v2 and Walker2d-v2
and is limited for Ant-v2 and HalfCheetah-v2. Therefore, we can expect NBCU
performs well on Ant-v2 and HalfCheetah-v2. Figure 8: Training curves of BC,
DemoDICE [Kim et al., 2022b], DWBC [Xu et al., 2022a], NBCU (Algorithm 1), and
WBCU (Algorithm 2) on the noisy expert task. Solid lines correspond to the
mean performance and shaded regions correspond to the 95% confidence interval.
Same as other figures.  Figure 9: Training curves of BC, DemoDICE [Kim et al.,
2022b], DWBC [Xu et al., 2022a], NBCU (Algorithm 1), and WBCU (Algorithm 2) on
the full replay task. Figure 10: Training curves of WBCU with gradient penalty
on the noisy expert task. Figure 11: Training curves of WBCU with gradient
penalty on the noisy expert task. Figure 12: Training curves of DemoDICE with
gradient penalty on the full replay task. Figure 13: Training curves of
DemoDICE with gradient penalty on the full replay task.