# Model-based Offline Imitation Learning with Non-expert Data

Jeongwon Park
UCLA
Lin Yang
UCLA

###### Abstract

Although Behavioral Cloning (BC) in theory suffers compounding errors, its
scalability and simplicity still makes it an attractive imitation learning
algorithm. In contrast, imitation approaches with adversarial training
typically does not share the same problem, but necessitates interactions with
the environment. Meanwhile, most imitation learning methods only utilises
optimal datasets, which could be significantly more expensive to obtain than
its suboptimal counterpart. A question that arises is, can we utilise the
suboptimal dataset in a principled manner, which otherwise would have been
idle? We propose a scalable model-based offline imitation learning algorithmic
framework that leverages datasets collected by both suboptimal and optimal
policies, and show that its worst case suboptimality becomes linear in the
time horizon with respect to the expert samples. We empirically validate our
theoretical results and show that the proposed method always outperforms BC in
the low data regime on simulated continuous control domains.

##  1 Introduction

Imitation Learning(IL) refers to the setting where a policy does not have
access to the ground truth reward function but instead has expert
demonstrations. It has shown to be an efficient approach to policy
optimization that has been extensively tested on real world applications[14,
12]. Most previous works on IL focuses on settings where it has limited access
to expert demonstrations, where the general strategies include i) BC[26, 12]
when no environment interactions are allowed ii) Interactive IL with an
expert[39] iii) Adversarial IL[9, 5, 4], by minimizing some form of divergence
between the expert and learner’s state action distribution. In this paper, we
consider an entirely offline setting as in i).

In many practical real world cases, we make the realistic assumption that the
set of logged datasets is pyramidal[25]: there are an enormous number of bad
trajectories, many mediocre trajectories, a few good trajectories, etc. It
follows that when imitation learning algorithms only make usage of the optimal
trajectories, it disregards the information stored in the suboptimal
trajectories. How best is it then, to utilise those suboptimal trajectories?
While there were some works that attempts to learn from suboptimal
demonstrations[30, 3, 26, 27], there were limited works that focuses on the
complete offline setting.

As in i), offline reinforcement learning (RL)[22] is a setting where the agent
only has access to a fixed dataset of experience, and where interactions with
the environment are not permitted. It is a setting of great interest when
considering applications where deploying suboptimal policies might be costly,
for example in healthcare and self-driving[12]. Although it is fair to assume
that such settings has accumulated a vast amount of behavior dataset over the
years, be it optimal or suboptimal, offline RL entails the additional
assumption of the availability of a reward function, or that such experiences
are labeled with rewards. Here, we consider a slightly different setting,
where we replace the necessity of reward labels with that of a modest amount
of expert demonstrations. That is, the setting where the behavior dataset does
not include any reward labels, but instead is composed of both suboptimal and
(a lot less)optimal trajectories. Our motivations are akin to that of inverse
RL[16, 11, 4], and we consider its offline analogue where reward functions are
difficult to engineer[11] but it is relatively easier to provide expert
demonstrations instead.

We also formulate connections with imitation learning and offline RL and
present an imitation learning algorithm where, by utilising suboptimal
demonstrations, its performance is less dependent on the amount of optimal
demonstrations. We approach this problem by utilising a learned model trained
on the behavior dataset. Previously, imitation learning with offline model
estimation[40] has not been studied thoroughly, as in the infinite state
action space regime, a model trained with limited and narrow coverage
datasets, such as those that are exclusively comprised of expert
demonstrations, is almost guaranteed empirically to be too incorrect for
reliable usage[35, 18]. We then argue that, if we cannot do substantially
better with respect to the algorithm, why don’t we change the setting itself?
Namely, we change it to the one presented in the paragraph above, and utilise
suboptimal data that is potentially idle. From this stems our motivation; in
such instances, can we statistically and empirically demonstrate that, by
solely interacting with an estimated transition from such idle data, that we
can do better than BC?

Under whats hopefully a promising setting, our primary contribution is a
general algorithmic framework for offline imitation where a policy is trained
adversarially with a discriminator in an estimated model, which is trained a
priori. We first demonstrate its statistical benefits over behavioral cloning,
and its practical instantiation that outperforms BC on all our evaluations.
Indeed, offline estimation and usage of a model comes with its own set of
difficulties[23, 18, 24], as the model only has access to data with limited
support and cannot improve its accuracy using additional experience. It is
also well known that a policy optimizing in such a model could learn to
exploit where it is inaccurate, which degrades the evaluated performance[24,
23]. We provide justifiable remedies that are motivated by recent works in
model based offline RL[18, 23, 17], where our algorithm also estimates and
penalizes model uncertainty.

##  2 Preliminaries

We consider a $\gamma$ discounted infinite horizon Markov Decision Process
(MDP) $M=(\mathcal{S},\mathcal{A},T,r,d_{0},\gamma)$ where $\mathcal{S}$ and
$\mathcal{A}$ denotes the state and action space respectively,
$T(s^{\prime}|s,a)$ the transition dynamics, $r(s,a)$ the reward function,
$d_{0}(s)$ the initial state distribution, and $\gamma\in(0,1)$ the discount
factor. We denote the policy $\pi(a|s)$ as a state conditional action
distribution, and $d^{\pi}_{T}(s)$ as the state distribution induced by $\pi$
in the dynamics $T$, where $p^{\pi}_{T}$ as its state action analogue. We
denote $T_{t},T_{l}\in\mathbb{T}$, as the true dynamics and the learned
dynamics, respectively in the set of transitions $\mathbb{T}$

We denote the expert policy as $\pi^{*}$, the learner policy as $\hat{\pi}$,
and the behavior policy as $\pi^{\mu}$. In the imitation learning setting, the
goal is to find a policy $\hat{\pi}\in\Pi$ that minimizes the difference in
expected discounted sum of rewards with that of the expert policy
$V^{\pi^{*}}-V^{\hat{\pi}}$, where we consider $V^{\pi^{*}}$ to be fixed. In
our analysis, $\Pi$ and $\mathbb{T}$ are discrete sets of policies and
transitions respectively and we assume a realizable setting for the policy,
where $\Pi$ is rich enough for $\pi^{*}\in\Pi$.

We follow the conventions in [34], where for any two policies $\pi$,
$\tilde{\pi}$ and dynamics $T$, $\tilde{T}$ we define a discriminating
function $f_{\pi,\tilde{\pi}}^{T,\tilde{T}}$:

$f_{\pi,\tilde{\pi}}^{T,\tilde{T}}=\operatorname*{argmax}_{f:||f||_{\infty}\leq
1}\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T}}[f(s)]-\operatorname{\mathbb{E}}_{s\sim
d^{\tilde{\pi}}_{\tilde{T}}}[f(s)]$

and the set of discriminating functions:
$F=\\{f_{\pi,\tilde{\pi}}^{T,\tilde{T}}:\pi,\tilde{\pi}\in\Pi\
,T\in\mathbb{T},\pi\neq\tilde{\pi}\\}$

Note that each $f\in F$ defines an Integral Probability Metric (IPM) of the
Total Variation (TV) distance for the two distributions. We also define the
data coverage of $p^{\pi^{\mu}}_{T_{t}}(s,a)$, $C:=\sup_{\pi\in\Pi,s\in S,a\in
A}\frac{\nu^{\pi}_{T_{l}}(s,a)}{p^{\pi^{\mu}}_{T_{t}}(s,a)}$, where
$\nu^{\pi}_{T_{l}}(s,a)$ denotes an admissible state action density by any
$\pi\in\Pi$ in the transition $T_{l}$, and, $p^{\pi^{\mu}}_{T_{t}}(s,a)$
denotes the state action distribution of the behavior policy. Unless otherwise
stated, we assume $C$ is bounded. We define the model training loss taken with
respect to the behavior distribution,
$\epsilon_{T}=\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{\mu}}(s,a)}[||T_{t}(s^{\prime}|a,s)-T_{l}(s^{\prime}|a,s)||_{1}]$, and
the expected distance of any two policies $\pi$, $\pi^{^{\prime}}$ where the
expectation is taken with respect to the state vistation distribution of $\pi$
as $\epsilon_{\pi,\pi^{^{\prime}}}=\operatorname{\mathbb{E}}_{s\sim
d^{\pi}}[||\pi(a|s)-\pi^{^{\prime}}(a|s)||_{1}]$. For simplicity, we assume
the existence of an optimization oracle for all optimization problems that
follow. We also assume that $p^{\pi}_{T}(s,a)$ is computable when $\pi$ and
$T$ is given. Note that in general we can get arbitrarily close to the true
distribution by sacrificing more compute.
Data Assumption In our work we assume access to a finite collection of $M$
optimal state action pairs and $N$ suboptimal state action pairs that are
generated by the expert and the behavior policy respectively, when rolling out
their policy on the true dynamics, i.e
$\\{s_{i}^{*}\,a_{i}^{*}\\}_{i=1..M}\sim p^{\pi^{*}}_{T_{t}}$,
$\\{s_{i}^{\mu}\,a_{i}^{\mu}\\}_{i=1..N}\sim p^{\pi^{\mu}}_{T_{t}}$. Although
we focus on instances where $N>>M$, our work is not restricted on that
setting.

##  3 Existing Algorithms

#### BC

One of the more traditional approaches to imitation learning, behavioral
cloning[12] trains a function approximator to replicate the expert under the
state distribution induced by the expert. A well known result is that the
worst case expected suboptimality for any BC learner scales quadratically in
the time horizon with respect to the training error[19, 14]. We further
elucidate by presenting a general bound for the difference in expected returns
for any two policies $\pi$ and $\hat{\pi}$.

Lemma 1:

$V^{\pi}-V^{\hat{\pi}}\leq\frac{1}{(1-\gamma)^{2}}\epsilon_{\pi,\hat{\pi}}$

Proof and further details in Appendix. When $\pi$ and $\hat{\pi}$ are
$\pi^{*}$ and $\pi^{BC}$ respectively, the bound reduces to the well studied
error bounds of behavioral cloning under the infinite horizon setting[19]. The
difficulty here is that behavioral cloning does not directly minimize the
difference in state visitation densities,
$\epsilon_{d^{\pi,\hat{\pi}}}:=||d^{\pi}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{t}}(s)||_{1}$,
between the learner and the expert. As a result, the error from
$\epsilon_{\pi,\hat{\pi}}$ is summed over all timesteps when it propagates to
$\epsilon_{d^{\pi,\hat{\pi}}}$, which is also known as covariate shift in the
literature[14]. Furthermore, $\epsilon_{d^{\pi,\hat{\pi}}}$ is also summed
over all timesteps when it propagates to
$\epsilon_{V}:=V^{\pi}-V^{\hat{\pi}}$.

$\epsilon_{d^{\pi,\hat{\pi}}}\leq\mathcal{O}(\frac{1}{1-\gamma}\epsilon_{\pi,\hat{\pi}})\;\;\;\;\;\;\;\epsilon_{V}\leq\mathcal{O}(\frac{1}{1-\gamma}\epsilon_{d^{\pi,\hat{\pi}}})$

In other words, the error’s compounding nature can be attributed to the
inability to minimize $\epsilon_{d^{\pi,\hat{\pi}}}$ directly. We can then
deduce that if there were indeed a measure of minimizing
$\epsilon_{d^{\pi,\hat{\pi}}}$, we would obtain a
$\mathcal{O}(\frac{1}{1-\gamma})$ factor improvement in $\epsilon_{V}$.

#### Adversarial Imitation

As shown previously, one gets an unfavorable guarantee on BC when
$\epsilon_{\pi,\hat{\pi}}$ is large, which generally occurs when $M$ is small.
We also showed that one can reduce the expected worst case error by a factor
of $\frac{1}{1-\gamma}$ when the difference in the state marginals are
directly minimized. In this section we point out the successes in recent
adversarial IL methods[9, 5, 4, 33, 32] and remind that its success over
behavioral cloning, particularly in the low-data regime, can simply be
attributed to its access to more information. While seemingly an obvious
statement, the imitation learning literature seems to have overlooked this
notion[6, 19]. Precisely, this additional information comes by the form of
$T_{t}$, which grants them the ability to minimize
$\epsilon_{d^{\pi,\hat{\pi}}}$ directly. This is in contrast to the hypothesis
presented in [6], where they assign credit to particular differences in
formulations of loss functions.

Information theoretically, when the algorithm has access to a true model of
its MDP, i.e knowledge of $T_{t}$, it can compute $d^{\hat{\pi}}_{T_{t}}(s)$.
Subsequently, a rather straightforward routine to compute and minimize
$\epsilon_{d^{\pi,\hat{\pi}}}$ is a min-max optimization procedure.

Theorem 2: Let

$\hat{\pi}=\operatorname*{argmin}_{\pi\in\Pi}\max_{f\in
F}\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi}_{T_{t}}(s,a)}[f(s,a)]$

Then with probability at least $1-\delta$,

$V^{\pi^{*}}-V^{\hat{\pi}}\leq\frac{2}{1-\gamma}\epsilon_{s}$

where $\epsilon_{s}=\sqrt{\frac{ln(\frac{|F|}{\delta})}{M}}$. Proof and
further details in Appendix.[34]

Quite simplistically, $\hat{\pi}$ in the algorithm above is directly
minimizing $||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\pi}_{T_{t}}(s,a)||_{TV}$, albeit in
its approximated form. As a result, there is only one stage of error
propagation from the policy’s objective to $\epsilon_{V}$. Note that the
algorithm shares the same essential qualities of most adversarial IL
methods[9, 5, 4], in that additional data are generated via interactions,
after which min-max optimization procedure follows. Essentially, the reduction
of dependency on $M$ comes at the cost of the assumption of a known $T_{t}$,
as opposed to the BC setting, where the algorithm only has access to a
limited, and usually expensive, samples of expert data. We can then deduce
that BC without any new information is a fundamentally limited setting,
especially in the low data regime. The recently constructed lower bound on BC
constitutes confirmatory evidence of this statement, where the lower bound
also scales quadratic in the horizon[20]. However note that such online
samples are typically considered expensive and even the most sophisticated
algorithms specified for sample efficiency[38, 29] generally requires orders
of magnitude more number of interactions than $M$.

##  4 Model-based Offline Imitation Learning

In previous sections we briefly analysed the properties of BC and adversarial
IL methods. We concluded that the latter comes with better theoretical
guarantees, albeit at the cost of interacting with the environment, or access
to a true model. However, BC is still widely used due to its simplicity and
scalability[41]. An immediate question that arises is whether existing and
tested methods as the ones discussed can be repurposed for sample efficient
learning in a complete offline setting, while conserving the generality and
scalability of BC.

###  4.1 Algorithm 1

We first begin with a simple extension of Theorem 2, namely how its bound
differs when the rollouts from the learner is generated from a learned model
$T_{l}$ instead of $T_{t}$. In both Algorithm 1 and Algorithm 2, a model
$T_{l}$ is trained at initialization from samples $s,a\sim
p^{\pi^{\mu}}_{T_{t}}$. Observing that the expectation in the objective of
$\pi$ is taken over $p^{\pi}_{T_{l}}(s,a)$ instead of $p^{\pi}_{T_{t}}(s,a)$,
we then obtain the following sample complexity of this modified algorithm.

Theorem 3: Let

$\hat{\pi}=\operatorname*{argmin}_{\pi\in\Pi}\max_{f\in
F}\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi}_{T_{l}}(s,a)}[f(s,a)]$

Then with probability at least $1-\delta$,

$V^{\pi^{*}}-V^{\hat{\pi}}\leq\frac{1}{1-\gamma}(2\epsilon_{s}+\frac{1}{1-\gamma}2C\epsilon_{T})$

where $\epsilon_{s}=\sqrt{\frac{ln(\frac{|F|}{\delta})}{M}}$. Proof and
further details in Appendix.
As in section 3, $\epsilon_{s}$ is the sampling error that has a $\sqrt{1/M}$
dependency on the number of expert samples. It is precisely the term that we
aim to reduce the suboptimality’s dependence on. $\epsilon_{T}$ denotes the
training loss of the model. $C$ is the importance weight which serves as a
bias correction term. Given a model $T_{l}$, it accounts for the
distributional shift that occurs between the training and evaluation stage,
since the distribution in which $T_{l}$ was trained on,
$p^{\pi^{\mu}}_{T_{t}}(s,a)$, differs from the distributions on which it is
evaluated. If our assumption on the bounded $C$ holds, both of the error terms
are guaranteed to converge to 0 in the limit of infinite samples. However its
scaling factor $O(\frac{1}{(1-\gamma)^{2}})$ implies the coverage of the
behavior dataset plays an essential role in algorithm 1’s performance, more so
than the expert dataset size.

Note that Algorithm 1’s error, unlike that of BC, incur no dependence on
$\epsilon_{\pi^{*},\hat{\pi}}$, and only has a $O(\frac{1}{1-\gamma})$
dependency on $M$, albeit at the cost of introducing a model error term
$C\epsilon_{T}$. Intuitively, we ’shift’ the quadratic dependency on $M$
obtained in behavioral cloning to the model training loss $\epsilon_{T}$ in
Algorithm 1. Why would this be favorable? Consider the definition of the error
term. As an empirical risk minimization (ERM) objective, standard learning
theoretical bounds shows that $\epsilon_{T}$ is inversely related to the
number of $s,a$ pairs from $p^{\pi^{\mu}}_{T_{t}}(s,a)$, However, note that
the algorithm is agnostic as to what policy $\pi^{\mu}(a|s)$ is. In other
words, $p^{\pi^{\mu}}_{T_{t}}(s,a)$ is the distribution that is obtained by
any behavior policy, including suboptimal policies. When considering instances
where it is much more easier to obtain suboptimal data, our analysis implies
that provided sufficient coverage of $p^{\pi^{\mu}}_{T_{t}}(s,a)$, such cases
do not need as much samples from the expert, since we are ’reallocating’ the
data dependence from that of the expert to that of any policy.

###  4.2 Algorithm 2

Perhaps in a more practical setting, we might want a scalable alternative loss
function that can easily be added to the BC framework along with the
statistical benefits. In other words, we search for an algorithm that has
similar properties to Algorithm 1, in the sense that the dependency on $M$ is
reduced, but can be easily integrated with a BC loss, in the following form:

$\text{loss}(\pi)=\epsilon_{\pi^{*},\pi}+\text{loss}_{auxillary}$

This is motivated by the fact that relying solely on $f$ for policy
optimization might not be ideal when given a finite dataset, where it is easy
to overfit to the discriminator[5, 4]. We are able to achieve this by
modifying the discriminator function. Algorithm 1 focuses on the setting where
$f$ takes in both states and actions as inputs. In this subsection, we study
its variant, Algorithm 2, where $f$ instead only discriminates on the state
space, while the learner $\hat{\pi}$ also directly minimizes a behavioral
cloning loss
$\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\pi(a|s^{*})||_{1}$, such that
its final objective becomes a two-way trade off problem

$\text{loss}(\pi)=\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\pi(a|s^{*})||_{1}-\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T_{l}}}[\hat{f}(s)]\ $

where $\hat{f}=\operatorname*{argmax}_{f\in
F}\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T_{l}}}[f(s)]$. We then again bound the algorithm’s suboptimality
using terms of interest.

Theorem 4: Let

$\hat{\pi}=\operatorname*{argmin}_{\pi\in\Pi}\max_{f\in
F}\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T_{l}}}[f(s)]+\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\pi(a|s^{*})||_{1}$

Then with probability at least $1-\delta$,

$V^{\pi^{*}}-V^{\hat{\pi}}\leq\frac{1}{1-\gamma}(2\epsilon_{s}+\frac{1}{1-\gamma}2C\epsilon_{T}+\epsilon_{\pi})$

where $\epsilon_{s}=\sqrt{\frac{ln(\frac{|F|}{\delta})}{M}}$ and
$\epsilon_{\pi}=\sqrt{\frac{ln(\frac{1}{\delta})}{M}}$. Proof and further
details in Appendix.
As in Algorithm 1, both $\epsilon_{T}$ and $\epsilon_{s}$ approaches 0 in the
limit of infinite samples from the behavior distribution
$p^{\pi^{\mu}}_{T_{t}}$ with high probability. The third term is the sampling
error of $\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\pi(a|s^{*})||_{1}$
from the true expectation $\epsilon_{\pi^{*},\pi}$, which also approaches 0 as
$M\rightarrow{\infty}$. Thus the derived bound indeed becomes a valid sample
complexity of Algorithm 2. As in Algorithm 1, the dependence on $M$ is linear
in the time horizon, at the cost of introducing the model error
$C\epsilon_{T}$.

In the previous section we discussed that the error in the conditional action
distribution $\epsilon_{\pi^{*},\hat{\pi}}$ of two policies $\pi^{*}$ and
$\hat{\pi}$ adds linearly each consecutive timestep over the time horizon when
it propagates to $||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{t}}(s)||_{1}$,
and a tighter bound over $V^{\pi^{*}}-V^{\hat{\pi}}$ necessitates the direct
minimization of the error in state densities. A rather simplistic view of
Algorithm 2 is that it is minimizing its upper bound (approximated by samples)
under its IPM form,
$\epsilon_{\pi^{*},\hat{\pi}}=||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{t}}(s)||_{1}\leq||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{l}}(s)||_{1}+\frac{1}{1-\gamma}C\epsilon_{T}\cong\frac{1}{M}\sum_{m=1}^{{M}}\hat{f}(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}}[\hat{f}(s)]+\frac{1}{1-\gamma}C\epsilon_{T}$ (further
details in Appendix), where the bound all consists of terms of minimization.
From this perspective we can attribute Algorithm 2’s sample efficiency over BC
by its ability to minimize $\epsilon_{d^{\pi,\hat{\pi}}}$ (almost) directly,
which mitigates covariate shift. We also argue that despite the fact that our
analysis focuses on a linear loss function for the discriminator $\hat{f}$, a
practical algorithm we propose is quite general. We do not injure its essence
by say, using a different loss function. Rather quite simplistically, its crux
is as follows; first train a model, after which, at each iteration, a
discriminator and a policy is trained adversarially with
$\\{s_{i}^{*}\\}_{i=1..M}\sim d^{\pi^{*}}_{T_{t}}$ and
$\\{\hat{s_{i}}\\}_{i=1..\hat{M}}\sim d^{\hat{\pi}}_{T_{l}}$, where $\hat{M}$
could be arbitrarily large since we have access to $T_{l}$. In addition,
$\hat{\pi}$ has an additional behavioral cloning loss term to minimize. Full
algorithm is detailed in Algorithm 2 in Appendix.

###  4.3 The C term and its repercussions

Recall the second term from Theorem 4, $\frac{1}{1-\gamma}2C\epsilon_{T}$.
When training $T_{l}$ with ERM, the training loss minimized is
$\epsilon_{T}=\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{\mu}}_{T_{t}}(s,a)}[||T_{t}(s^{\prime}|a,s)-T_{l}(s^{\prime}|a,s)||_{1}]$.
where the training distribution is limited only to
$p^{\pi^{\mu}}_{T_{t}}(s,a)$. However when we bound the difference of the
witness functions $f$ induced by the the model error(detail in Appendix)

$\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{t}}(s)}[\hat{f}(s)]-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}(s)}[\hat{f}(s)]\leq
f_{max}\frac{1}{1-\gamma}\operatorname{\mathbb{E}}_{s,a\sim
p^{\hat{\pi}}_{T_{l}}(s,a)}[||T_{t}(s^{\prime}|a,s)-T_{l}(s^{\prime}|a,s)||_{1}]$

we observe a different distribution $p^{\hat{\pi}}_{T_{l}}(s,a)$ at the
expectation instead of $p^{\pi^{\mu}}_{T_{t}}(s,a)$, i.e a different train and
test set for $T_{l}$. A conventional approach to such case is introducing a
concentration coefficient $C$ that is assumed to be bounded uniformly for all
$\pi\in\Pi$, $s,a\in S,A$, such that $\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi}_{T_{l}}(s,a)}[||T_{t}(s^{\prime}|a,s)-T_{l}(s^{\prime}|a,s)||_{1}]\leq
C\epsilon_{T}$, ensuring the convergence properties during finite sample
analysis, a form of insurance against any distribution shift if you will. Such
simple algebraic trick, however, neglects what potentially is a ’make or
break’ in an offline learning algorithm in a practical setting[22, 18, 23]. It
has been empirically observed[22] that a combination of infinite state-action
space and function approximation likely causes divergence while training, due
to the policy exploiting the errors in the model, which is expected to be
large with such bias in the distributions.

As alluded before, our analysis elucidates this notion, as $C$ compounds at a
quadratic rate, which means for very large $C$, the second error term from
Theorem 4 will dominate the other terms and the bound will become very loose
in the worst case. By its definition, this occurs when any $\pi\in\Pi$ admits
$s,a$ such that $p^{\pi}_{T_{l}}(s,a)$ is large but
$p^{\pi^{\mu}}_{T_{t}}(s,a)$ is small, for all $s,a\in S,A$. As a result, the
worst case bound becomes uncontrollably large when any rollouts from $T_{l}$
diverges too much from the behavior dataset.

What happens then if our assumption on $C$ doesn’t hold? This implies that the
previous worst case error becomes unbounded. A simple algebraic modification
in the proof, however resolves this issue, albeit at a cost of losing our
convergence guarantees. But first we define a new term $U$, that attempts to
capture an intuitive notion of uncertainty[25] induced by the error in the
learned model. We define $U(\pi):=|\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi}_{T_{l}}(s,a)}[||T_{t}(s^{\prime}|a,s)-T_{l}(s^{\prime}|a,s)||_{1}]-\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{\mu}}_{T_{t}}(s,a)}[||T_{t}(s^{\prime}|a,s)-T_{l}(s^{\prime}|a,s)||_{1}]|$,
the difference in the model error induced by $\pi$ when evaluated at
$p^{\pi}_{T_{l}}(s,a)$ and $p^{\pi^{\mu}}_{T_{t}}(s,a)$. From its definition,
we can observe that $\sup_{\pi\in\Pi}U(\pi)$ determines a property related to
the global accuracy of $T_{l}$. We then utilize this term to bypass the
unboundedness of $C$ in Theorem 2.

Corollary 2: Algorithm 2 returns a policy $\hat{\pi}$ such that

$V^{\pi^{*}}\leq
V^{\hat{\pi}}+\frac{1}{1-\gamma}2\epsilon_{s}+\frac{1}{(1-\gamma)^{2}}(2\epsilon_{T}+U(\hat{\pi})+U(\pi^{*}))+\frac{1}{1-\gamma}\epsilon_{\pi^{*},\hat{\pi}}$

In words, the suboptimality increases when either $\hat{\pi}$ or $\pi^{*}$
visits states that incur larger model error than $\epsilon_{T}$. Given that
$T_{l}$ attempts to minimize $\epsilon_{T}$, we can expect that it is
relatively more accurate on $s,a\sim p^{\pi^{\mu}}_{T_{t}}(s,a)$.
Consequently, $U(\hat{\pi})$ and $U(\pi^{*})$ is small when $\hat{\pi}$ and
$\pi^{*}$ doesn’t erroneously lead to states that incur large model error.
However, note that $U(\pi^{*})$ is an uncontrollable term, and signifies a
fundamental property of the provided dataset. Therefore any attempt to ensure
the error is bounded should be realized by controlling $U(\hat{\pi})$.

In practical settings, to avoid degenerate solutions caused by the potentially
unbounded model bias, we instead want to solve the optimization problem of the
following form,

$\underset{\pi\in\Pi}{\text{minimize}}\max_{f\in
F}\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T_{l}}}[f(s)]+\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\pi(a|s^{*})||_{1}$
$s.t.U(\hat{\pi})\leq c$

where $c$ is some sufficiently small constant. An immediate question is then
how best do we ensure a sufficiently small $U(\hat{\pi})$? By its definition,
we know $U(\hat{\pi})$ will be small when the learner $\hat{\pi}$ visits
states that the model is relatively more accurate in. Certainly, we cannot
formulate this as a Lagrangian to directly minimize $U(\hat{\pi})$, as no such
oracle exists. In section 5, we provide some practical remedies which proves
to be essential to Algorithm 2’s practical performance.

##  5 Practical Implementation and Experiments

Up to this point our theoretical results indicates that in the offline
imitation learning setting, using a learned model from suboptimal datasets
reduces the dependence on the number of expert samples, provided that the
algorithm can control its degree of distributional shift(bounded $C$). Given
that the results were based on certain idealizations and assumptions, can we
still empirically validate this claim?

#### Uncertainty Penalization

In section 4 we discussed how the sample complexity of Algorithm 1 and 2
crucially depends on the uncertainty of $T_{l}$ in the states induced by
$\hat{\pi}$ and $\pi^{*}$. Instead of relying on the assumption on $C$, we
decompose the model’s uncertainty into $U(\hat{\pi})$ and $U(\pi^{*})$, and
argue that while $U(\pi^{*})$ is a fundamental property of the dataset, we can
attempt to control the value of $U(\hat{\pi})$. In our experiments, we utilise
uncertainty quantification techniques[18, 23, 17, 22] to estimate and control
$U(\hat{\pi})$. Following works in the model based offline reinforcement
learning literature[24], we train $T_{l}$ as an ensemble of $K$ probabilistic
neural networks that each outputs a mean and a covariance matrix $\Sigma$ to
estimate the transition from the behavior dataset, and use the discrepancies
in their predictions to estimate uncertainty. While there are a myriad of
possible techniques for this endeavor, for our main evaluations we use the one
presented in [18] and observe that it is sufficient to obtain good results.
Specifically, we define the state-action wise estimated uncertainty
$\hat{U}(s,a):=\max_{i=1}^{K}||\Sigma_{i}(s,a)||$ and the uncertainty
penalized discriminator $f_{u}(s,a)=f(s,a)-\lambda\hat{U}(s,a)$ where the
objective of the policy then becomes(with our previously defined $\hat{f}$)

$\text{loss}(\hat{\pi})=\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}}[\hat{f_{u}}(s)]\ $

In our experiments we attempt to answer the following questions: i) In the
offline setting, does Algorithm 2 outperform BC in the low data regime? ii) Is
Algorithm 2 competitive with Adversarial IL methods that are trained online?
iii) To what extent does $U(\hat{\pi})$ affect the algorithm’s performance and
can we validate that we can indeed control $U(\hat{\pi})$ with the proposed
methods? We answer the above questions with standard benchmark tasks from
OpenAi gym[2] with the Mujoco[28] simulator. We collect both expert and
behavior datasets using SAC[8]. All behavior datasets are collected for 1M
time steps, after which the collection terminates. We then evaluate our
algorithm along with BC and Adversarial IL from section 3. We implement our
own Adversarial IL algorithm and practice fair comparison by training it on an
identical codebase and hyperparameters(where they apply) as on Algorithm 2,
except that it uses a true model $T_{t}$ to sample rollouts instead. BC also
shares the same policy architecture with Adversarial IL and Algorithm 2.

We first highlight several factors that are expected to affect the magnitude
of $U(\hat{\pi})$. They include:
1) Dataset Size: The number of state action pairs used to train the model
2) Dataset Coverage: The degree of exploration or the number of policies used
to collect the data.
3) Uncertainty Penalization: This requires uncertainty quantification
techniques.
4) Starting State: As alluded before, the starting state of rollouts directly
affects the model’s uncertainty.

Note that 1) and 2) are both determined prior running the algorithm. Assuming
that 1) and 2) are known, we can use this prior to determine the degree of 3).
In order to evaluate the severity of 2), we collect two different behavior
datasets to train the model. Dataset $p^{\pi^{\mu}}_{w}$ is collected by a
slow learning policy that upon termination, obtains medium level performance,
or approximately half the returns of the $\pi^{*}$. We deliberately induce
slow learning so that the best performing policy in $p^{\pi^{\mu}}_{w}$ is
still suboptimal. Dataset $p^{\pi^{\mu}}_{n}$ is collected entirely by a
random policy. Note that in the evaluated Mujoco Tasks, a random policy admits
a much narrower dataset than a learning policy. Main experimental evaluations
are shown in Table 1. Performance for Algororithm 2 was evaluated on the
$T_{l}$ trained with the $p^{\pi^{\mu}}_{w}$(Algorithm2_w on Table 1) and
$p^{\pi^{\mu}}_{n}$(Algorithm2_n on Table 1) dataset. For all tasks, we
experiment with varying number of expert trajectories, namely 1,3,10 and 30.
When training the model, we utilise only the prescribed expert dataset(s) in
addition to the behavior dataset.

We observe that Algorithm2_w always outperforms BC with large margin on the
1,3,10 Expert Traj settings, while they both become near optimal when provided
30 expert trajectories. We notice that BC is more susceptible to $M$ in both
directions, and its performance admits a steeper slope as a function of $M$.
This is confirmatory evidence to our analysis in that the dependency on $M$ is
much lower for Algorithm 2. For $Algorithm2_{n}$, we obtain much lower
performance than $Algorithm2_{w}$, which is expected due to lower coverage of
$p^{\pi^{\mu}}_{n}$. However, it still outperforms BC on most settings. We
also note that BC is significantly more susceptible to high variance among
trials, which could be detrimental for real world settings[41]. We also point
out that our implementation of Adversarial IL aligns with the literature[19,
7, 6, 9, 5, 4] with respect to its performance, and also our analysis in that
it is robust to low data regimes. Despite having to use a learned model
instead, Algorithm 2 trained on $p^{\pi^{\mu}}_{w}$ is almost as good as
Adversarial IL.

We also empirically study the effect of different starting states from section
5. Results are presented in Table 2. We find that the performance heavily
relies on where $\hat{\pi}$ begin its rollouts on $T_{l}$. During experiments,
we find that $T_{l}$’s low accuracy on states other than from
$d^{\pi^{\mu}}_{T_{t}}(s)$ leads to unstable policy learning. This result
aligns with our theoretical findings, and it suggests that different starting
states could potentially lead to stronger model-based offline RL results.
Additional implementation details/evaluations are provided in the Appendix.

| BC | Adversarial IL | Algorithm2_w | Algorithm2_n
---|---|---|---|---
Hopper-v2 | 1 Expert Traj | 0.15 $\pm$ 0.16 | 0.83 $\pm$ 0.13 | 0.83 $\pm$ 0.11 | 0.52 $\pm$ 0.13
| 3 Expert Traj | 0.14 $\pm$ 0.18 | 0.95 $\pm$ 0.03 | 0.78 $\pm$ 0.11 | 0.55 $\pm$ 0.21
| 10 Expert Traj | 0.56 $\pm$ 0.25 | 1.02 $\pm$ 0.06 | 0.95 $\pm$ 0.13 | 0.61 $\pm$ 0.10
| 30 Expert Traj | 0.91 $\pm$ 0.06 | 0.94 $\pm$ 0.09 | 0.95 $\pm$ 0.02 | 0.84 $\pm$ 0.04
HalfCheetah-v2 | 1 Expert Traj | 0.21 $\pm$ 0.33 | 0.72 $\pm$ 0.23 | 0.42 $\pm$ 0.08 | 0.33 $\pm$ 0.04
| 3 Expert Traj | 0.55 $\pm$ 0.21 | 0.93 $\pm$ 0.04 | 0.72 $\pm$ 0.11 | 0.31 $\pm$ 0.12
| 10 Expert Traj | 0.57 $\pm$ 0.12 | 1.13 $\pm$ 0.04 | 0.78 $\pm$ 0.18 | 0.52 $\pm$ 0.04
| 30 Expert Traj | 0.83 $\pm$ 0.10 | 0.95 $\pm$ 0.02 | 0.93 $\pm$ 0.11 | 0.78 $\pm$ 0.11
Walker2d-v2 | 1 Expert Traj | 0.09 $\pm$ 0.12 | 0.74 $\pm$ 0.22 | 0.66 $\pm$ 0.20 | 0.32 $\pm$ 0.14
| 3 Expert Traj | 0.10 $\pm$ 0.16 | 0.82 $\pm$ 0.09 | 0.73 $\pm$ 0.22 | 0.78 $\pm$ 0.11
| 10 Expert Traj | 0.37 $\pm$ 0.42 | 0.91 $\pm$ 0.12 | 0.98 $\pm$ 0.03 | 0.89 $\pm$ 0.05
| 30 Expert Traj | 0.92 $\pm$ 0.34 | 0.97 $\pm$ 0.13 | 0.98 $\pm$ 0.09 | 0.94 $\pm$ 0.05

  * •

Table 1: Mean and Std for performance of Algorithm 2 compared to BC and
Adversarial IL evaluated on the last iteration, with varying number of
provided expert trajectories. Scores are normalized such that a random policy
scores 0.00 and the expert scores 1.00. All trials were averaged over
different random seeds. For BC, the numbers presented are averaged over 20
different seeds due to a much shorter run time. Adversarial IL and Algorithm 2
were averaged over 3 seeds. For all 1 Expert Traj experiments, different
trajectory was used each trial.

Starting States | $d_{0}(s)$ | $d^{\pi^{*}}_{T_{t}}(s)$ | $d^{\pi^{\mu}}_{T_{t}}(s)$ | $d(s)$
---|---|---|---|---
Hopper-v2 | 0.21 $\pm$ 0.07 | 0.36 $\pm$ 0.05 | 0.78 $\pm$ 0.11 | 0.13 $\pm$ 0.05
HalfCheetah-v2 | 0.32 $\pm$ 0.08 | 0.41 $\pm$ 0.05 | 0.72 $\pm$ 0.11 | 0.02 $\pm$ 0.01
Walker2d-v2 | 0.18 $\pm$ 0.09 | 0.48 $\pm$ 0.21 | 0.73 $\pm$ 0.22 | 0.12 $\pm$ 0.04

  * •

Table 2: Algorithm2_w evaluated on different rollout starting states, all on
the 3 Expert Traj settings. Scores are evaluated using the same procedure as
in Table 1.

##  6 Related Works

We now briefly discuss prior works that motivated this work. Traditionally, IL
focuses on learning with fixed expert demonstrations[12, 41], while [39, 14]
formalized the compounding error bound of BC. Subsequently they introduce
Dagger, which necessitates interactions with the expert and the environment,
and shows that it breaks the quadratic bound. [10, 15] present methods that
address the distribution shift of IL by attempting to match the state
visitation density of the expert. [36, 35] recently proposed algorithms for
offline imitation learning, but they are only restricted to discrete action
spaces. [9, 5, 4] first derived adversarial IL from the principle of maximum
entropy [16] in the deep RL setting, and demonstrated that it significantly
outperforms BC.

Here we highlight works that attempts IL with suboptimal demonstrations[3, 27,
30, 26]. [26] presents an alternative BC algorithm that learns from noisy
logged demonstrations, by filtering out data with low modes.[3] showed that,
given performance rankings of the suboptimal demonstrations, their algorithm
obtains better performance than the demonstration. However, their algorithm
relies on the assumption that the reward in the MDP of interest is easily
’extrapolatable’, which is not a fair assumption to make on all MDPs, such as
ones that require a fair amount of exploration.

We also highlight some theoretical contributions that motivated our work,
namely[20, 31, 19].[31] presents a provably efficient imitation learning
algorithm on settings where the actions are not provided in the expert
dataset. In the tabular setting [20] showed that with knowledge of the true
dynamics one can obtain an subquadratic error bound with respect to the
horizon. [19] illustrates a unified view on error bound analysis for imitation
learning. While [19, 20] does not present any practical algorithms, our
theoretical results were greatly inspired by their works. In that sense, our
work can be considered an extension of their works.

In its essence, our empirical work most resembles the recent works in model
based offline learning[17, 23, 18], which have shown promising results.
Therefore, any further developments in this area could potentially benefit our
work. To combat the issue of distribution shift, [18, 23] has relied on
uncertainty penalization using the discrepancies in the ensemble predictions,
while [17] has relied on penalizing the Q function for state action pairs that
are generated by the model. In particular, [18, 17] builds on the work of [24]
that uses an ensemble of model to estimate epistemic uncertainty. Outside
offline RL, [1] also utilises ensemble disagreement of policies to penalize
visiting uncertain regions.

##  7 Conclusion

Addressing sample efficiency and covariate shift has been a long standing
challenge in IL. In our work, we present principled remedies by finding usage
of suboptimal demonstrations. We show that training a model from a suboptimal
dataset and adversarial training in the estimated MDP yields an algorithm that
requires much lower amount of expert samples. As the algorithms we present are
general and backed with theory, it could potentially have real world use
cases. It shares the same promise with offline RL, but without requiring
reward labels.

It is also worthy to share some limitations in our work. Notably, our
algorithm relies on the sufficient coverage assumption of the behavior dataset
along with less principled approaches to estimate uncertainty. In that
perspective, our work shares the same obstacles as model based offline RL
algorithms, and future works on these limitations could benefit them both.

## References

  * [1] Kianté Brantley, Wen Sun, and Mikael Henaff. Disagreement-regularized imitation learning. In International Conference on Learning Representations, 2020.
  * [2] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
  * [3] Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observation. In International Conference on Machine Learning, 2019
  * [4] Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International Conference on Machine Learning, 2016.
  * [5] Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse reinforce- ment learning. International Conference on Learning Representations, 2018
  * [6] Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimization perspective on imitation learning methods. Conference on Robot Learning, 2019
  * [7] Liyiming Ke, Sanjiban Choudhury, Matt Barnes, Wen Sun, Gilwoo Lee, and Siddhartha Srinivasa. Imitation Learning as f-Divergence Minimization In arXiv:1905.12888, 2019
  * [8] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, 2018a.
  * [9] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, 2016.
  * [10] Fangchen Liu, Zhan Ling, Tongzhou Mu, and Hao Su. State alignment-based imitation learning. International Conference on Learning Representations, 2020.
  * [11] Andrew Y Ng, Stuart J Russell, et al. Algorithms for inverse reinforcement learning. In International Conference on Machine Learning, 2000.
  * [12] Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural computation, 1991.
  * [13] Siddharth Reddy, Anca D Dragan, and Sergey Levine. Sqil: imitation learning via regularized behavioral cloning. International Conference on Learning Representations, 2020.
  * [14] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In International Conference on Artificial Intelligence and Statistics, 2010.
  * [15] Yannick Schroecker and Charles L Isbell. State aware imitation learning. In Advances in Neural Information Processing Systems, 2017
  * [16] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In AAAI Conference on Artificial Intelligence, 2008.
  * [17] Tianhe Yu, Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. COMBO: Conservative offline model-based policy optimization. arXiv preprint arXiv:2102.08363, 2021.
  * [18] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPO: Model-based offline policy optimization. arXiv preprint arXiv:2005.13239, 2020
  * [19] Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments. Advances in Neural Information Processing Systems, 33, 2020.
  * [20] Nived Rajaraman, Lin F Yang, Jiantao Jiao, and Kannan Ramachandran. Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems, 2020
  * [21] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202, 2020.
  * [22] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.
  * [23] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. MOReL: Model- based offline reinforcement learning. arXiv preprint arXiv:2005.05951, 2020.
  * [24] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. In Advances in Neural Information Processing Systems, pages 12498–12509, 2019\.
  * [25] Jacob Buckman, Carles Gelada, and Marc G Bellemare. The importance of pessimism in fixed- dataset policy optimization. arXiv preprint arXiv:2009.06799, 2020.
  * [26] Fumihiro Sasaki, Ryota Yamashina. Behavioral Cloning from Noisy Demonstrations. In International Conference on Learning Representations, 2021
  * [27] Yueh-Hua Wu, Nontawat Charoenphakdee, Han Bao, Voot Tangkaratt, and Masashi Sugiyama. Im- itation learning from imperfect demonstration. arXiv preprint arXiv:1901.09387, 2019.
  * [28] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026–5033. IEEE, 2012.
  * [29] Fumihiro Sasaki, Tetsuya Yohira, and Atsuo Kawaguchi. Sample efficient imitation learning for continuous control. In International Conference on Learning Representations, 2018.
  * [30] Daniel H Grollman and Aude G Billard. Robot learning from failed demonstrations. International Journal of Social Robotics, 4(4):331–342, 2012.
  * [31] WenSun, AnirudhVemula, ByronBoots,and JAndrewBagnell. Provablyefficient imitation learning from observation alone. In International Conference of Machine Learning, 2019\.
  * [32] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems,pages 2672–2680, 2014.
  * [33] Umar Syed and Robert E Schapire. A game-theoretic approach to apprenticeship learning. In Advances in neural information processing systems, 2008.
  * [34] Alekh Agarwal Nan Jiang Sham M. Kakade Wen Sun. Reinforcement Learning: Theory and Algorithms, 2020
  * [35] Daniel Jarrett, Ioana Bica, Mihaela van der Schaar. Strictly Batch Imitation Learning by Energy-based Distribution Matching, In Advances in neural information processing systems, 2020
  * [36] Alex J. Chan and Mihaela van der Schaar. Scalable Bayesian Inverse Reinforcement Learning, International Conference of Learning Representations 2021
  * [37] Ilya Kostrikov, Ofir Nachum, Jonathan Tompson. Imitation Learning Via Off-Policy Distribution Matching. International Conference of Learning Representations 2020
  * [38] Robert Dadashi, Léonard Hussenot, Matthieu Geist, Olivier Pietquin. Primal Wassertein Imitation Learning. International Conference of Learning Representations 2021
  * [39] Stéphane Ross Geoffrey J. Gordon J. Andrew Bagnell. A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning. In AISTATS, 2011
  * [40] Peter Englert; Alexandros Paraschos; Jan Peters; Marc Peter Deisenroth. Model-based imitation learning by probabilistic trajectory matching. 2013 IEEE International Conference on Robotics and Automation
  * [41] Felipe Codevilla, Eder Santana, Antonio M. López, Adrien Gaidon. Exploring the Limitations of Behavior Cloning for Autonomous Driving. In  arXiv:1904.08980
  * [42] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
  * [43] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representa- tion learning of low rank mdps. NeurIPS, 2020b.

## Checklist

The checklist follows the references. Please read the checklist guidelines
carefully for information on how to answer these questions. For each question,
change the default [TODO] to [Yes] , [No] , or [N/A] . You are strongly
encouraged to include a justification to your answer, either by referencing
the appropriate section of your paper or providing a brief inline description.
For example:

  * •

Did you include the license to the code and datasets? [Yes] See Section 2.

  * •

Did you include the license to the code and datasets? [No] The code and the
data are proprietary.

  * •

Did you include the license to the code and datasets? [N/A]

Please do not modify the questions and only use the provided macros for your
answers. Note that the Checklist section does not count towards the page
limit. In your paper, please delete this instructions block and only keep the
Checklist section heading above along with the questions/answers below.

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] see conclusion

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A] no
forseeable negative impact

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
See preliminaries

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] in appendix

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [No]
code will soon be released after cleanup

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] in appendix

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes] see Table 1, Table 2 in section 5

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [No] all
experiments were run on cpus, as it doesn’t need heavy compute

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [N/A]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

Input: Optimal trajectories $D(\pi^{*})=\\{s^{*}_{i},a^{*}_{i}\\}_{i=1..M}$,
Suboptimal trajectories
$D(\tilde{\pi})=\\{\tilde{s}_{i},\tilde{a}_{i}\\}_{i=1..N}$;

Result: $\hat{\pi}$,$T_{l}$, and $f$ parameters

Train model $T_{l}$ with $D:=D(\pi^{*})\cup D(\tilde{\pi})$;

for  _epoch =1,2,…,T_ do

Collect Data: Run current policy(in parallel) $\hat{\pi}$ in $T_{l}$ for $H$
horizon length and obtain dataset
$D(\hat{\pi})=\\{\hat{s}_{i},\hat{a}_{i},\hat{r}_{i}\\}_{i=1..B}$ with batch
size B and scores $\hat{r}$ from $f$;

Discriminator: Update $f$ with $D(\hat{\pi})$ and $D(\pi^{*})$;

Policy: Take policy gradient step to maximise $\hat{r}$ from $f$ and minimize
BC loss from $D(\pi^{*})$;

end for

Algorithm 1 Algorithm 2

##  Appendix A Additional Implementation Details

#### Rollout Length

For sake of simplicity our analysis relied on the assumption that
$d^{\hat{\pi}}_{T_{l}}$ is computable for a given policy $\hat{\pi}$. However,
with infinite state action spaces, naively rolling out the entire trajectory
for $\frac{1}{1-\gamma}$ steps in $T_{l}$ might not be desirable[24] as the
model’s error compounds as shown in section 4[34]. Meanwhile too short of a
rollout from $T_{l}$ such as in[18, 24] increases the sampling bias from not
sampling from $d^{\hat{\pi}}_{T_{l}}$, and the resulting algorithm strays too
much from our analysis. In our experiments, we find that a certain range of
rollout lengths $H$ works well, namely $5\leq H\leq 15$. However we perform
all our experiments with $H$ fixed with 10, which is typically longer than
most model based RL experiments. As opposed to standard model based RL[24], in
the imitation learning setting we provide some additional justifications as to
why a longer $H$ (up to a certain point) might be desirable in section B.1.

#### Starting State

As discussed before, the policy performs $H$ step rollouts in $T_{l}$ where we
then estimate $d^{\hat{\pi}}_{T_{l}}$. However, from what state distribution
do we actually begin the rollout? This stems a fairly important discussion, as
our experiments showed that it is a large controlling factor on the
algorithm’s performance. We first discuss several available options: i)
$d_{0}(s)$; Initial States: we assume samples from $d_{0}(s)$ are available as
initial states in the provided dataset, ii) $d^{\pi^{*}}_{T_{t}}(s)$; Expert
States, iii) $d^{\pi^{\mu}}_{T_{t}}(s)$; Behavior States, iiii) $d(s)$;
Arbitary States: these refers to any states that are sampled from the
observation space.

We first state that we chose iii) for our evaluations, motivated from our
theoretical results. We also experimentally confirm that iii) is indeed the
best option. In section 4, we showed that the algorithm’s performance relies
crucially on the magnitudes of the term $C$ or $U(\hat{\pi})$. While $C$ is a
property of the dataset, $U(\hat{\pi})$ is a term that we can control. Now
recall the definition of $U(\hat{\pi})$. Since we expect $T_{l}$ to be
relatively more accurate on $d^{\pi^{\mu}}_{T_{t}}(s)$ than others, a policy
that begins from $d^{\pi^{\mu}}_{T_{t}}(s)$ will also likely end up in states
that $T_{l}$ is more accurate in, which results in a lower $U(\hat{\pi})$.
Explained differently, the algorithm’s performance depends on the accuracy of
$T_{l}$ during rollouts, which is expected to be higher when rollouts start
from iii). In a sense, choosing the starting state iii) is an additional
strategy that controls $U(\hat{\pi})$, as is uncertainty penalization. We
corroborate this hypothesis in our experiments in section 5.

###  A.1 Additional Training Details

#### Discriminator

We train the function $f$ with 2 layers and 64 units. To mitigate overfitting,
we regularize it by enforcing a lipschitz constant of 0.05 on the network
parameters. We find this to be significantly more beneficial than gradient
penalty based regularizations.

#### Model

We train the model as similar to [18, 24], where we train an ensemble of 7
neural networks and predict with a random sample from the ensemble
predictions.

#### Policy

We optimize the policy with PPO[42]. Although we can in principle
backpropagate through time in $T_{l}$, we believed policy gradients would be a
better choice since we can get a gradient arbitarily close to the true
gradient by simply sacrificing more compute. For all our experiments, we
collect 5000 samples in parallel for a horizon length of 10, which results in
50000 total samples per epoch.

##  Appendix B Proofs

Proof of Lemma 1(Performance Difference of Two Policies): This is a simple
application of the performance difference lemma[34] of any two policies $\pi$,
$\hat{\pi}$. Let $R_{max}\leq 1/2$, then it follows that
$Q_{max}\leq\frac{1}{2(1-\gamma)}$, where
$Q^{\pi}(s,a):=\operatorname{\mathbb{E}}_{\pi,T_{t}}[\sum_{t=0}^{\infty}\gamma^{t}r(s,a)]$
and
$Q^{\pi}(s,\hat{\pi}):=\operatorname{\mathbb{E}}_{a\sim\hat{\pi},\pi,T_{t}}[\sum_{t=0}^{\infty}\gamma^{t}r(s,a)]$,
where only the first action is averaged over $\hat{\pi}$. Then it follows that

$V^{\pi}-V^{\hat{\pi}}$ $=\frac{1}{1-\gamma}\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T_{t}}}[-Q^{\hat{\pi}}(s,\hat{\pi}(s))+Q^{\hat{\pi}}(s,\pi(s))]$

$\leq Q_{max}\frac{1}{1-\gamma}\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T_{t}}}[||\pi-\hat{\pi}||_{1}]$
$\leq\frac{1}{(1-\gamma)^{2}}\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T_{t}}}[||\pi-\hat{\pi}||_{1}]$

We refer readers to Section E, Theorem 21 in [43] for detailed proofs on
maximum likelihood(MLE) guarantees on $\operatorname{\mathbb{E}}_{s\sim
d^{\pi}_{T_{t}}}[||\pi-\hat{\pi}||_{1}]$, such that the bound becomes a valid
sample complexity after a MLE training procedure.

Proof of Theorem 2: The proof can be found in [34], but we also present here
for completeness. It is a direct application of a uniform convergence argument
for all $f\in F$. For Theorem 2 and 3, we define $f$ slightly differently from
its definition presented in section 2, namely $f$ takes both $s,a$ as inputs.
We then define $\hat{f}:=\operatorname*{argmax}_{f\in
F}\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s\sim
p^{\hat{\pi}}_{T_{t}}}[f(s,a)]$ and $\tilde{f}:=\operatorname*{argmax}_{f\in
F}\operatorname{\mathbb{E}}_{s\sim
p^{\pi^{*}}_{T_{t}}}[f(s,a)]-\operatorname{\mathbb{E}}_{s\sim
p^{\hat{\pi}}_{T_{t}}}[f(s,a)]$.

Then it follows that for all $\pi\in\Pi$, $\max_{f\in
F}(\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{*}}_{T_{t}}}[f(s,a)]-\operatorname{\mathbb{E}}_{s,a\sim
p^{\hat{\pi}}_{T_{t}}}[f(s,a)])=\max_{f:||f||_{\infty}\leq
1}(\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{*}}_{T_{t}}}[f(s,a)]-\operatorname{\mathbb{E}}_{s\sim
p^{\hat{\pi}}_{T_{t}}}[f(s,a)])=||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\hat{\pi}}_{T_{t}}(s,a)||_{1}$

Also, let $R_{max}\leq 1$. It is then straightforward to see that

$V^{\pi^{*}}-V^{\hat{\pi}}$
$\leq\frac{1}{1-\gamma}|||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\hat{\pi}}_{T_{t}}(s,a)||_{1}$

We now bound the distance of the state-action visitation densities,

$||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\hat{\pi}}_{T_{t}}(s,a)||_{1}$
$=\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{*}}_{T_{t}}}[\tilde{f}(s,a)]-\operatorname{\mathbb{E}}_{s\sim
p^{\hat{\pi}}_{T_{t}}}[\tilde{f}(s,a)]$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\hat{\pi}}_{T_{t}}}[\tilde{f}(s,a)]+\epsilon_{s}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\hat{f}(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\hat{\pi}}_{T_{t}}}[\hat{f}(s,a)]+\epsilon_{s}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\hat{f}(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{*}}_{T_{t}}}[\hat{f}(s,a)]+\epsilon_{s}$ $\leq 2\epsilon_{s}$

Utilising

$V^{\pi^{*}}-V^{\hat{\pi}}$
$\leq\frac{1}{1-\gamma}||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\hat{\pi}}_{T_{t}}(s,a)||_{1}$

we conclude our proof. The first and last inequality is from Hoeffding’s
inequality taken union bound for all $f\in F$, where with probability at least
$1-\delta$ , $|\operatorname{\mathbb{E}}_{s\sim
p^{\pi^{*}}_{T_{t}}(s,a)}[f(s,a)]-\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*},a^{*})|\leq
2\sqrt{\frac{ln(\frac{|F|}{\delta})}{M}},\forall f\in F$,
$\epsilon_{s}:=2\sqrt{\frac{ln(\frac{|F|}{\delta})}{M}}$, and the third
inequality is from the optimality of $\hat{\pi}$.

Proof of Theorem 3: The proof is an adaptation of Theorem 2 in the case where
the expectation over $p^{\pi^{*}}_{T_{t}}$ is replaced with
$p^{\pi^{*}}_{T_{l}}$, then with the same definitions as in the proof of
Theorem 2,

$||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\hat{\pi}}_{T_{t}}(s,a)||_{1}$
$=\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{*}}_{T_{t}}}[\tilde{f}(s,a)]-\operatorname{\mathbb{E}}_{s,a\sim
p^{\hat{\pi}}_{T_{t}}}[\tilde{f}(s,a)]$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\hat{\pi}}_{T_{t}}}[\tilde{f}(s,a)]+\epsilon_{s}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\hat{\pi}}_{T_{l}}}[\tilde{f}(s,a)]+\epsilon_{s}+\frac{C}{1-\gamma}\epsilon_{T}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{*}}_{T_{l}}}[\tilde{f}(s,a)]+\epsilon_{s}+\frac{C}{1-\gamma}\epsilon_{T}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{*}}_{T_{t}}}[\tilde{f}(s,a)]+\epsilon_{s}+\frac{2C}{1-\gamma}\epsilon_{T}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*},a^{*})-\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{*}}_{T_{t}}}[\tilde{f}(s,a)]+\epsilon_{s}$ $\leq
2\epsilon_{s}+\frac{2C}{1-\gamma}\epsilon_{T}$

The third inequality is from the optimality of $\hat{\pi}$. For the second and
fourth inequality we use lemma 6 presented below to bound
$||d^{\hat{\pi}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{l}}(s)||_{1}\leq\frac{1}{1-\gamma}\epsilon_{T}$.
Consequently, using

$V^{\pi^{*}}-V^{\hat{\pi}}$
$\leq\frac{1}{1-\gamma}||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\hat{\pi}}_{T_{t}}(s,a)||_{1}$

we conclude our proof

Proof of Theorem 4:

We can decompose the state action distribution distance by the following,

$||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\hat{\pi}}_{T_{t}}(s,a)||_{1}$
$\leq||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{t}}(s)||_{1}+\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{t}}(s)}[||\pi^{*}(a|s)-\hat{\pi}(a|s)||_{1}]$

Define

$\hat{f}=\operatorname*{argmax}_{f\in F}\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{t}}(s)}[f(s)]-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{t}}(s)}[f(s)]$ $\tilde{f}=\operatorname*{argmax}_{f\in
F}\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}(s)}[f(s)]$

Using Hoeffding’s inequality and taking the union bound for all discriminator
functions $f\in F$(where we have defined in section 2), we have that with
probability at least $1-\delta$,

$|\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{t}}(s)}[f(s)]-\frac{1}{M}\sum_{m=1}^{{M}}f(s^{*})|\leq
2\sqrt{\frac{ln(\frac{|F|}{\delta})}{M}},\forall f\in F$

Now, bounding the difference in the two state distributions,

$||d^{\pi^{*}}_{T_{t}}-d^{\hat{\pi}}_{T_{t}}||_{1}$
$=\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{t}}(s)}[\hat{f}(s)]-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{t}}(s)}[\hat{f}(s)]$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\hat{f}(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{t}}(s)}[\hat{f}(s)]+\epsilon_{s}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\hat{f}(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}(s)}[\hat{f}(s)]+\epsilon_{s}+\frac{C\epsilon_{T}}{1-\gamma}$
$=\frac{1}{M}\sum_{m=1}^{{M}}\hat{f}(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}(s)}[\hat{f}(s)]+\epsilon_{s}+\frac{C\epsilon_{T}}{1-\gamma}+\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}-\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}(s)}[\tilde{f}(s)]+\epsilon_{s}+\frac{C\epsilon_{T}}{1-\gamma}+\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}-\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{l}}(s)}[\tilde{f}(s)]+\epsilon_{s}+\frac{C\epsilon_{T}}{1-\gamma}-\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\tilde{f}(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{t}}(s)}[\tilde{f}(s)]+\epsilon_{s}+\frac{2C\epsilon_{T}}{1-\gamma}-\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}$
$\leq
2\epsilon_{s}+\frac{2C\epsilon_{T}}{1-\gamma}-\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}$

Where the first equality holds from our definition of the set of
discriminators $F$. For the second and sixth inequality we again use lemma 6.
The fifth inequality holds due to the optimality of $\hat{\pi}$. Returning to
our original bound on expected returns,

$V^{\pi^{*}}-V^{\hat{\pi}}$
$\leq\frac{1}{1-\gamma}||p^{\pi^{*}}_{T_{t}}(s,a)-p^{\hat{\pi}}_{T_{t}}(s,a)||_{1}$
$\leq\frac{1}{1-\gamma}(||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{t}}(s)||_{1}+\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{t}}(s)}[||\pi^{*}(a|s)-\hat{\pi}(a|s)||_{1}])$
$\leq\frac{1}{1-\gamma}(2\epsilon_{s}+\frac{2C\epsilon_{T}}{1-\gamma}+\epsilon_{\pi})$

where we have $|\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{t}}(s)}[||\pi^{*}(a|s)-\hat{\pi}(a|s)||_{1}]-\frac{1}{M}\sum_{m=1}^{{M}}||\pi^{*}(a|s^{*})-\hat{\pi}(a|s^{*})||_{1}|\leq
2\sqrt{\frac{ln(\frac{1}{\delta})}{M}}:=\epsilon_{\pi}$ with probability at
least $1-\delta$.

Proof of Corollary 2 This follows from a slight modification in the proof of
Theorem 4, where we bound

$|\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}(s)}[\hat{f}(s)]-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{t}}(s)}[\hat{f}(s)]|$
$\leq\frac{1}{1-\gamma}\operatorname{\mathbb{E}}_{d^{\hat{\pi}}_{T_{l}}}[||T_{t}(s^{\prime}|s,a)-T_{l}(s^{\prime}|s,a)||_{1}]\leq\frac{1}{1-\gamma}(\epsilon_{T}+U(\hat{\pi}))$

and equivalently for $\pi^{*}$

Lemma 6 (Error Propagations of difference in transitions and policies): [19]
has presented the state distribution error propagation bound for two differing
policies. The bound for two differing transitions is trivially similar, and we
present it here. We denote the transition operator
$P^{\pi}_{T}:=\sum_{a}T(s^{\prime}|s,a)\pi(a|s)$ and
$G^{\pi}_{T}:=(\mathcal{I}-\gamma P^{\pi}_{T})^{-1}$, where we then have
$(1-\gamma)G^{\pi}_{T_{t}}d_{0}=d^{\pi}_{T_{t}}$

Then it follows that, for two transitions $T_{l}$ and $T_{t}$,

$d^{\pi}_{T_{t}}(s)-d^{\pi}_{T_{l}}(s)$ $(1-\gamma)((\mathcal{I}-\gamma
P^{\pi}_{T_{t}})^{-1}-(\mathcal{I}-\gamma P^{\pi}_{T_{l}})^{-1})d_{0}$
$=(1-\gamma)\gamma
G^{\pi}_{T_{l}}(P^{\pi}_{T_{l}}-P^{\pi}_{T_{t}})G^{\pi}_{T_{t}}d_{0}$ $=\gamma
G^{\pi}_{T_{l}}(P^{\pi}_{T_{l}}-P^{\pi}_{T_{t}})d^{\pi}_{T_{t}}$

Where we then have

$||d^{\pi}_{T_{t}}(s)-d^{\pi}_{T_{l}}(s)||_{1}=||\gamma
G^{\pi}_{T_{l}}(P^{\pi}_{T_{l}}-P^{\pi}_{T_{t}})d^{\pi}_{T_{t}}||_{1}$
$\leq\gamma||G^{\pi}_{T_{t}}||_{1}||(P^{\pi}_{T_{l}}-P^{\pi}_{T_{t}})d^{\pi}_{T_{t}}||_{1}$

where we can further bound the two terms individually,

$||G^{\pi}_{T_{t}}||_{1}\leq\frac{1}{1-\gamma}$

and

$||(P^{\pi}_{T_{l}}-P^{\pi}_{T_{t}})d^{\pi}_{T_{t}}||_{1}$
$=\sum_{s^{^{\prime}}}\sum_{s}(|P^{\pi}_{T_{l}}(s^{\prime}|s)-P^{\pi}_{T_{t}}(s^{\prime}|s)|)d^{\pi}_{T_{t}}(s)$
$=\sum_{s^{^{\prime}}}\sum_{s}d^{\pi}_{T_{t}}(s)|\sum_{a}(T_{t}(s^{\prime}|s,a)-T_{l}(s^{\prime}|s,a))\pi(a|s)|$
$\leq\sum_{s^{^{\prime}}}\sum_{s}\sum_{a}p^{\pi}_{T_{t}}(s,a)|T_{t}(s^{\prime}|s,a)-T_{l}(s^{\prime}|s,a)|$
$=\operatorname{\mathbb{E}}_{p^{\pi}_{T_{t}}}[||T_{t}(s^{\prime}|s,a)-T_{l}(s^{\prime}|s,a)||_{1}]$

Then it follows that

$||d^{\pi}_{T_{t}}(s)-d^{\pi}_{T_{l}}(s)||_{1}\leq\frac{1}{1-\gamma}\operatorname{\mathbb{E}}_{p^{\pi}_{T_{t}}}[||T_{t}(s^{\prime}|s,a)-T_{l}(s^{\prime}|s,a)||_{1}]$

#### State Visitation difference minimization

We previously mentioned that $\hat{\pi}$ is minimizing the approximated state
visitation difference, we clarify this notion here.

$||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{t}}(s)||_{1}$
$\leq||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{l}}(s)||_{1}+||d^{\hat{\pi}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{l}}(s)||_{1}$
$\leq||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{l}}(s)||_{1}+\frac{1}{1-\gamma}C\epsilon_{T}$
$\leq\frac{1}{M}\sum_{m=1}^{{M}}\hat{f}(s^{*})-\operatorname{\mathbb{E}}_{s\sim
d^{\hat{\pi}}_{T_{l}}}[\hat{f}(s)]+\frac{1}{1-\gamma}C\epsilon_{T}+\epsilon_{s}$

The last inequality follows from our definition of $\hat{f}$ in Theorem 4.
Intuitively, the distributional information of states is encoded in $\hat{f}$,
which $\hat{\pi}$ can exploit by maximising $\hat{f}$. Maximising $\hat{f}$
becomes identical to minimizing
$||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{t}}(s)||_{1}$ when the model
training error $\epsilon_{T}$ is 0, or equivalently when there is an infinite
number of behavior state action pairs.

###  B.1 Recovery

In this subsection we comment on a direct consequence of our choice in the
starting state, namely the recovery behavior of our algorithm, which
solidifies our intuition on its empirical success over behavioral cloning.
Imitation Learning also concerns the problem of mitigating covariate shift,
which occurs when the learner deviates from the expert’s state distribution
$d^{\pi^{*}}_{T_{t}}$ during the evaluation stage. Naive BC methods does not
prepare the policy to recover to $d^{\pi^{*}}_{T_{t}}$ in such instances. We
argue that our model based approach acts to resolve this issue.

We define $v_{\pi}^{k}$ as an unique recovery variable for every policy $\pi$
in an MDP of interest.

$v_{\pi}^{k}:=||d^{\pi^{*}}_{T_{t}}-(P^{\pi}_{T_{t}})^{k}\nu||$

where $P^{\pi}_{T}$ is the transposed transition matrix $\sum_{a\in
A}T(s^{\prime}|a,s)\pi(a|s)$ induced by $\pi$ in the dynamics $T$, and
$\nu(s)$ denotes the density of any admissible states by $\pi\in\Pi$. Under
the assumption of irreducibility and aperiodicity of of $P^{\pi}_{T_{t}}$,
$(P^{\pi}_{T_{t}})^{k}\nu(s)$ will converge to its stationary distribution
$d^{\pi}_{T_{t}}(s)$ as $k\rightarrow{\infty}$. Intuitively, the finiteness of
$k$ allows $v_{\pi}^{k}$ to represent the ability of $\pi$ to ’direct’ itself
to $d^{\pi^{*}}_{T_{t}}(s)$ in under $k$ transitions, starting from any
admissible state $s\sim\nu(s)$. A policy that is sufficiently trained to
minimize this objective could endow $\pi$ the ability to recover from any
arbitrary admissible state back to the expert distribution in finitely many
steps. It then follows that we can bound $v_{\pi}^{k}$ with certain terms of
interest.

Proposition 1

$v_{\pi}^{k}\leq||d^{\pi^{*}}_{T_{t}}(s)-(P^{\pi}_{T_{l}})^{k}d^{\pi^{\mu}}(s)||+k\hat{\epsilon_{T}}+\sqrt{2\log
C}$

Where $\hat{\epsilon_{T}}=\max_{i=1..k}\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{\mu}}(s,a)}[||T_{t}(s_{i+1}|a_{i},s_{i})-T_{l}(s_{i+1}|a_{i},s_{i})||_{1}]$.
The first two terms of this bound are approximately the minimization variables
in Algorithm 2. While we do not directly minimize $C$, we attempt to control a
related variable $U(\hat{\pi})$ to ensure $C$ does not get too large.

Proof of Proposition 1:

$||d^{\pi^{*}}_{T_{t}}-(P^{\pi}_{T_{t}})^{k}\nu||_{1}$
$=||d^{\pi^{*}}_{T_{t}}-(P^{\pi}_{T_{l}})^{k}d^{\pi^{\mu}}+(P^{\pi}_{T_{l}})^{k}d^{\pi^{\mu}}-(P^{\pi}_{T_{t}})^{k}d^{\pi^{\mu}}+(P^{\pi}_{T_{t}})^{k}d^{\pi^{\mu}}-(P^{\pi}_{T_{t}})^{k}\nu||_{1}$
$\leq||d^{\pi^{*}}_{T_{t}}-(P^{\pi}_{T_{l}})^{k}d^{\pi^{\mu}}||_{1}+||(P^{\pi}_{T_{l}})^{k}d^{\pi^{\mu}}-(P^{\pi}_{T_{t}})^{k}d^{\pi^{\mu}}||_{1}+||(P^{\pi}_{T_{t}})^{k}d^{\pi^{\mu}}-(P^{\pi}_{T_{t}})^{k}\nu||_{1}$
$\leq||d^{\pi^{*}}_{T_{t}}-(P^{\pi}_{T_{l}})^{k}d^{\pi^{\mu}}||_{1}+k\hat{\epsilon_{T}}+||(P^{\pi}_{T_{t}})^{k}||_{1}||d^{\pi^{\mu}}-\nu||_{1}$
$\leq||d^{\pi^{*}}_{T_{t}}-(P^{\pi}_{T_{l}})^{k}d^{\pi^{\mu}}||_{1}+k\hat{\epsilon_{T}}+\sqrt{2\log
C}$

In the second inequality, we bound the $k$ step induced state divergence from
two different transition $T_{l}$ and $T_{t}$
$||(P^{\pi}_{T_{l}})^{k}d^{\pi^{\mu}}-(P^{\pi}_{T_{t}})^{k}d^{\pi^{\mu}}||$
using the second inequality follows from applying lemma B.2 from [24]. Also
note that $||(P^{\pi}_{T_{t}})^{k}||_{1}=1$ as $P^{\pi}_{T_{t}}$ is a left-
stochastic matrix. The last inequality follows from Pinsker’s inequality and
the definition of $C$. We also point out a trade-off between $k$ and
$\hat{\pi}$’s recovery property. As $k$ decreases it is quite possible that
$\hat{\pi}$ fails to learn to direct itself to $d^{\pi^{*}}_{T_{t}}$ from any
$s\sim\nu(s)$, especially if the MDP of interest has a large state space.
However, increasing $k$ loosens the bound for any non-zero $\epsilon_{T}$.
This may explain the range of horizon $H$ that we found works well, as
explained in section A.

Recall from section A that $\hat{\pi}$ begin its rollouts from
$d^{\pi^{\mu}}_{T_{t}}(s)$. We then provide a consequential argument that
arises from proposition 1; if $d^{\pi^{\mu}}_{T_{t}}(s)$ sufficiently
represents the state space that is generated by a learner $\hat{\pi}$ from
making a mistake, or equivalently when $C$ is bounded, then given a
sufficiently accurate $T_{l}$, our practical instatiation of Algorithm 2
trains $\hat{\pi}$ to direct itself back to $d^{\pi^{*}}_{T_{t}}(s)$ in $k$
transitions.

###  B.2 Reduction to offline RL

In this section we study the setting where we are given additional
information, namely i) when the true reward function is given and ii) when its
empirical samples are given corresponding to the behavior dataset. Given the
true reward function or labels, the problem then reduces to offline RL. In i,
the policy $\pi$ generates rollouts in the learned dynamics $T_{l}$ with the
true reward function $r:S\times A\mapsto\mathbb{R}$, after which $\pi$
maximises its collected reward in this fake environment. In ii, the setting is
identical to i except that its reward function $\hat{r}:S\times
A\mapsto\mathbb{R}$ is an empirical risk minimizing function of reward labels
obtained from the behavior dataset
$\\{s_{i},a_{i},r_{s_{i},a_{i}}\\}_{i=1..N}\sim p^{\pi^{\mu}}_{T_{t}}$. This
is in contrast to the imitation learning setting where we don’t have access to
either $r_{s_{i},a_{i}}$ or $r$. Despite the simple analysis, it is insightful
to compare how the bound compares to the previous setting under the same
assumptions, since we can observe what differs when the true reward is
replaced with a discriminator function $f$.

Theorem 5(When True Reward Function is Given(i)): Let

$\hat{\pi}=\operatorname*{argmax}_{\pi\in\Pi}\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi}_{T_{l}}(s,a)}[r(s,a)]$

Then

$V^{\pi^{*}}\leq V^{\hat{\pi}}+\frac{2C\epsilon_{T}}{(1-\gamma)^{2}}$

An almost identical proof is used for ii, where we take into account the
approximation error for the reward function,
$\epsilon_{r}:=\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi^{\mu}}_{T_{t}}}[|\hat{r}(s,a)-r(s,a)|]$, so we just state the proof for
ii.

Corollary 4(When Only Reward Labels are Given(ii)): Let

$\hat{\pi}=\operatorname*{argmax}_{\pi\in\Pi}\operatorname{\mathbb{E}}_{s,a\sim
p^{\pi}_{T_{l}}(s,a)}[\hat{r}(s,a)]$

Then

$V^{\pi^{*}}\leq
V^{\hat{\pi}}+\frac{2C\epsilon_{T}}{(1-\gamma)^{2}}+\frac{2C\epsilon_{r}}{1-\gamma}$

Proof of Theorem 5/Corollary 4

$(1-\gamma)(V^{\pi^{*}}-V^{\hat{\pi}})=\operatorname{\mathbb{E}}_{p^{\pi^{*}}_{T_{t}}(s,a)}[r(s,a)]-\operatorname{\mathbb{E}}_{p^{\hat{\pi}}_{T_{t}}(s,a)}[r(s,a)]$
$\leq\operatorname{\mathbb{E}}_{p^{\pi^{*}}_{T_{t}}(s,a)}[r(s,a)]-\operatorname{\mathbb{E}}_{p^{\hat{\pi}}_{T_{l}}(s,a)}[\hat{r}(s,a)]+\frac{C\epsilon_{T}}{1-\gamma}+C\epsilon_{r}$
$\leq\operatorname{\mathbb{E}}_{p^{\pi^{*}}_{T_{t}}(s,a)}[r(s,a)]-\operatorname{\mathbb{E}}_{p^{\pi^{*}}_{T_{l}}(s,a)}[\hat{r}(s,a)]+\frac{C\epsilon_{T}}{1-\gamma}+C\epsilon_{r}$
$\leq\operatorname{\mathbb{E}}_{p^{\pi^{*}}_{T_{t}}(s,a)}[r(s,a)]-\operatorname{\mathbb{E}}_{p^{\pi^{*}}_{T_{t}}(s,a)}[r(s,a)]+\frac{2C\epsilon_{T}}{1-\gamma}+2C\epsilon_{r}=\frac{2C\epsilon_{T}}{1-\gamma}+2C\epsilon_{r}$

Compared to Theorem 3, given a true reward function, we are able to purge the
high probability error term $\epsilon_{s}$. As in the imitation learning
setting, Note that for both i and ii the suboptimality is still dependent on
the concentrability coefficient. Analogous to Theorem 3 and 4, for ii the
dependence on $\epsilon_{T}$ significantly outweighs that of the reward
function approximation error $\epsilon_{r}$, which signifies the importance of
an accurate model and data coverage over the reward function.

##  Appendix C Additional Experiments

In section 5 we saw that Algorithm 2 outperforms BC on all domains. In this
section we provide some additional empirical analysis that serves to answer
the following questions;

i) Compared to BC, does Algorithm 2 mitigate compounding errors?
ii) Compared to BC, does the policy trained with Algorithm 2 admit the
recovery behavior outlined in section B.1?
iii) How does Algorithm 2 perform when the model is trained solely from expert
demonstrations?

In order to evaluate i), we use a separate model $\hat{T_{l}}$ that is trained
solely from expert demonstrations $d^{\pi^{*}}_{T_{t}}(s)$, and estimate its
uncertainty when both $\hat{\pi}$ and $\pi^{BC}$ perform rollouts in $T_{l}$.
$\hat{\pi}$ and $\pi^{BC}$ is the output policy of Algorithm 2 and behavioral
cloning, respectively. Both $\hat{\pi}$ and $\pi^{BC}$ begin their rollouts in
$T_{l}$ from the same sampled state $s^{*}\sim d^{\pi^{*}}_{T_{t}}(s)$(where
$\hat{T_{l}}$ admits low uncertainty), and by quantifying its rise throughout
the rollout, we estimate which policy becomes more divergent from
$d^{\pi^{*}}_{T_{t}}(s)$. (recall $\hat{T_{l}}$ only encountered
$d^{\pi^{*}}_{T_{t}}(s)$ while training). In particular, we estimate both
$\hat{T_{l}}$’s aleatoric and epistemic uncertainty by measuring

$\tilde{U}_{t}(s_{t},a_{t};T_{l}):=\alpha\max_{i=1..k}||\tilde{\Sigma}_{i}(s,a)||-\beta\log
P(s^{\prime}_{pred}|s_{t},a_{t})$

$\log P(s^{\prime}_{pred}|s,a)$ is $\hat{T_{l}}$’s estimated log-probability
of the next state generated by $T_{l}$, $\tilde{\Sigma}_{i}(s,a)$ is the
covariance matrix predicted by each member of the ensemble $\hat{T_{l}}$, and
$\alpha$ and $\beta$ are appropriate scaling terms. $t$ indexes the timesteps
elapsed after beginning the rollouts.

Similarly, we evaluate ii) by letting both both $\hat{\pi}$ and $\pi^{BC}$
begin their rollouts from the same sampled state from
$d^{\pi^{\mu}}_{T_{t}}(s)$, i.e $\tilde{s}\sim d^{\pi^{\mu}}_{T_{t}}(s)$.
Indeed, $\hat{T_{l}}$ was not trained on $d^{\pi^{\mu}}_{T_{t}}(s)$ so it will
admit high $\tilde{U}_{t}$ on $\tilde{s}$ at $t=1$. However we predict that a
policy that admits recovery behavior will learn to direct itself back towards
$d^{\pi^{*}}_{T_{t}}(s)$ regardless of the starting state, which would in turn
correlate with a decreasing $\tilde{U_{t}}$ along $t$.

We provide confirmatory evidence of this hypothesis in figure 1 where we’ve
outlined results for evaluating i) and ii). Recall that $\hat{\pi}$ and
$\pi^{BC}$ generates rollouts in $T_{l}$. For each chart the x-axis represents
the elapsed timestep $t$ during the rollout after initial sampling, and the
y-axis represents the uncertainty $\tilde{U}_{t}$ as measured by
$\hat{T_{l}}$. The lines for $\hat{\pi}$ and $\pi^{BC}$ are denoted by
Algorithm2 and BC respectively. As the lines deviate more from the x-axis, the
evaluated policy is visiting more uncertain states, which implies increased
divergence from $d^{\pi^{*}}_{T_{t}}(s)$, and vice versa.

For i), the results are presented in the first two charts. Note that the BC
agent admits a much more divergent behavior than Algorithm 2 when they both
begin $s\sim d^{\pi^{*}}_{T_{t}}(s)$. The third and fourth charts outline the
evaluation results for ii). As opposed to i), both BC and Algorithm 2 begins
its rollouts from a state sampled from $d^{\pi^{\mu}}_{T_{t}}(s)$. As a
result, the initial uncertainty measured by $T_{l}$ is greater than in i). We
observe that in ii) $\pi^{BC}$ diverges even more so than in i) but
$\hat{\pi}$ succeeds in visiting states that obtain gradually lower
uncertainty. This result provides evidence to $\hat{\pi}$’s recovery behavior.
We also remind the readers that as $T_{l}$ becomes more accurate, this
comparison would correlate greater with the true divergence behavior in
$T_{t}$.

#### Expert Only

So far, we’ve only discussed circumstances where we assume access to a
behavior dataset sampled from $d^{\pi^{\mu}}_{T_{t}}(s)$, while being agnostic
to its optimality. While it is indeed a practical setting, we also want to
evaluate Algorithm 2 when we are provided only expert demonstrations. In such
setting, we can still apply results Theorem 4 without loss of its generality,
but as a result some of its terms will depend on different distributions and
we cannot guarantee a linear dependence on the $M$. Namely, $\epsilon_{T}$
would instead depend on the number of expert demonstrations, and
$C:=\sup_{\pi\in\Pi,s\in S,a\in
A}\frac{\nu^{\pi}_{T_{l}}(s,a)}{p^{\pi^{*}}_{T_{t}}(s,a)}$, where they both
scale in $O(\frac{1}{(1-\gamma)^{2}})$.

Observing the newly defined $C$, we suspect the algorithm’s performance would
depend on the learner’s ability to generate states that is covered by
$p^{\pi^{*}}_{T_{t}}(s,a)$. However, recall that Algorithm 2 minimizes the
estimated uncertainty of $T_{l}$, which is trained with samples
$s^{*},a^{*}\sim p^{\pi^{*}}_{T_{t}}(s,a)$. In other words, $T_{l}$ admits
less uncertainty on $p^{\pi^{*}}_{T_{t}}(s,a)$. One could then argue that in
such case, by minimizing $T_{l}$’s uncertainty, $\hat{\pi}$ could learn to
match its visitation density with $p^{\pi^{*}}_{T_{t}}(s,a)$. Additionally, as
alluded in section A, the function $f$ could capture distributional
information of states that $\hat{\pi}$ can utilise.

We evaluate this intuition and present its results on Table 3, where the
scores are presented in the column labeled $Algorithm2_{expert}$. Indeed, we
see that even if $T_{l}$ is trained solely with expert samples, Algorithm 2
outperforms BC. In the paragraph above, we attibute this to providing the
learner with more information that naive BC algorithms fails to utilise. This
implies that usage of a estimated model in imitation learning in general could
be beneficial.

Figure 1:  Average uncertainty measurements as a function of timesteps rolled
out in the model. where the shaded area represents the std of 5 random seed
trials. Uncertainty values are scaled such that states from expert
demonstrations obtains 0.

Algorithms | $BC$ | Algorithm 2_expert | Algorithm 2_w
---|---|---|---
Hopper-v2 | 0.14 $\pm$ 0.18 | 0.68 $\pm$ 0.05 | 0.78 $\pm$ 0.11
HalfCheetah-v2 | 0.55 $\pm$ 0.21 | 0.60 $\pm$ 0.05 | 0.72 $\pm$ 0.11
Walker2d-v2 | 0.10 $\pm$ 0.16 | 0.71 $\pm$ 0.14 | 0.73 $\pm$ 0.22

  * •

Table 3: Performance evaluations of Algorithm2_expert compared to BC, where
for all experiments 3 expert trajectories are provided.

Todos: experiment, imp details, state visition dif, read and more
supplementary We then state its consequence in the following corollary;
Corollary 1: Denote the policy from the naive BC algorithm $\pi^{BC}$ and
assume $\pi^{BC}\in\Pi$, then it follows that with probability $1-\delta$,

$||d^{\pi^{*}}_{T_{t}}(s)-d^{\hat{\pi}}_{T_{t}}(s)||_{1}\leq||d^{\pi^{*}}_{T_{t}}(s)-d^{\pi^{BC}}_{T_{t}}(s)||_{1}+\operatorname{\mathbb{E}}_{s\sim
d^{\pi^{*}}_{T_{t}}(s)}[||\pi^{BC}(a|s)-\hat{\pi}(a|s)||_{1}]+2\epsilon_{s}+\frac{1}{1-\gamma}2C\epsilon_{T}$

In words, $\hat{\pi}$ from Algorithm 2 is a better imitator than $\pi^{BC}$,
in the sense that it obtains a closer state visitation density to that of the
expert, provided there are enough data points and the two policies
$\hat{\pi},\pi_{BC}$ agrees with each other on the expert states.