# Tight Performance Guarantees of Imitator Policies with Continuous Actions

Davide Maran, Alberto Maria Metelli, Marcello Restelli

###### Abstract

Behavioral Cloning (BC) aims at learning a policy that mimics the behavior
demonstrated by an expert. The current theoretical understanding of BC is
limited to the case of finite actions. In this paper, we study BC with the
goal of providing theoretical guarantees on the performance of the imitator
policy in the case of continuous actions. We start by deriving a novel bound
on the performance gap based on Wasserstein distance, applicable for
continuous-action experts, holding under the assumption that the value
function is Lipschitz continuous. Since this latter condition is hardy
fulfilled in practice, even for Lipschitz Markov Decision Processes and
policies, we propose a relaxed setting, proving that value function is always
Hölder continuous. This result is of independent interest and allows obtaining
in BC a general bound for the performance of the imitator policy. Finally, we
analyze noise injection, a common practice in which the expert’s action is
executed in the environment after the application of a noise kernel. We show
that this practice allows deriving stronger performance guarantees, at the
price of a bias due to the noise addition.

##  1 Introduction

The degree of interaction of the human in the ecosystem of artificial
intelligence is progressively becoming more and more prominent (Zanzotto
2019). In this setting, the human plays the role of an expert that, with
different tools, interacts with the artificial agents and allows the agent to
leverage their knowledge to improve, quicken, and make the learning process
more effective (Jeon, Milli, and Dragan 2020).

Imitation Learning (IL, Osa et al. 2018) can be considered one of the simplest
forms of interaction between a human and an artificial agent. This kind of
interaction is unidirectional since the human expert provides the agent with a
set of demonstrations of behavior that is optimal w.r.t. an unknown objective.
The agent, on its part, aims to learn a behavior as close as possible to the
demonstrated one. Classically, we distinguish between two realizations of IL:
Behavioral Cloning (BC, Bain and Sammut 1995) and Inverse Reinforcement
Learning (IRL, Arora and Doshi 2021). BC aims at mimicking the _behavior_ of
the agent by recovering a policy that matches as much as possible the expert’s
demonstrated behavior. Instead, IRL has the more ambitious goal of
reconstructing a _reward_ function that justifies the expert’s behavior. Thus,
it aims at representing the expert’s _intent_ rather than their behavior. In
this sense, IRL is more challenging than BC, as its output, the reward
function, is a more powerful tool that succeeds in being deployed even in the
presence of a modification of the environment.

Although IL techniques have been successfully applied to a large variety of
real-world applications (e.g., Asfour et al. 2008; Geng, Lee, and Hülse 2011;
Rozo, Jiménez, and Torras 2013; Likmeta et al. 2021), their theoretical
understanding in terms of performance of the imitation policy is currently
limited. Recently, in (Xu, Li, and Yu 2020), a first analysis of the error
bounds has been provided for BC and Generative Adversarial Imitation Learning
(Ho and Ermon 2016). However, these results involve the presence of an
$f$-divergence (Rényi et al. 1961), usually total variation (TV) or KL-
divergence, between the expert’s policy and the imitator one. Consequently,
they are significant only when the action space is finite, while becoming
vacuous for experts with continuous actions. To further argue on the
limitation of this analysis, consider the case in which BC is reduced to
minimize the _mean squared error_ (MSE) between the expert’s action and the
imitator one. Even in this simple scenario, as we shall see, the current
analysis based on TV cannot relate MSE with the performance of the imitator
policy. This represents a relevant limitation since many of the applications
of IL are naturally defined with continuous-actions context.

#### Original Contributions

In this paper, we aim to take a step forward to a more comprehensive
theoretical understanding of BC. Specifically, we devise error bounds that
relate the performance difference $J^{\pi_{E}}-J^{\pi_{I}}$ between the
expert’s policy $\pi_{E}$ and the imitator one $\pi_{I}$ to their divergence.
Our bounds are based on the Wasserstein distance (Villani 2009) and, for this
reason, are meaningful even in the presence of continuous-action spaces
(Section 3). Our work contains the following contributions:

  1. 1.

We will prove a performance bound for standard BC in case of Lipschitz reward-
transition for the MDP (see (Rachelson and Lagoudakis 2010)) and Lipschitz
continuity of the value function.

  2. 2.

Since the latter assumption is often violated in practice111It is well-known
that the value function is Lipschitz continuous under the demanding assumption
that $\gamma L_{p}(1+L_{\pi})<1$ (Rachelson and Lagoudakis 2010), requiring
the Lipschitz constants of the transition model $L_{p}$ and of the policy
$L_{\pi}$ to be very small., we extend the result by only requiring
Lipschitzness of the MDP, even if it requires a weaker performance bound. It
is also shown that, the less regularity we lose on the value function, the
slower the convergence of BC (Section 4).

  3. 3.

Finally, we focus on a popular practice employed in imitation learning, i.e.,
_noise injection_ (Laskey et al. 2017a). In this setting, the expert’s action,
before being executed in the environment, is corrupted with noise to make the
imitation process more robust. We show that noise injection allows achieving
stronger theoretical guarantees at the price of competing against a noisy
expert, which could have a lower performance (Section 5).

In particular, in the second point, we show that the value function of a
Lipschitz MDP is always Hölder continuous, with a suitable choice of the
exponent depending on the properties of the MDP and policy. This represents a
result of independent interest that overcomes a well-known limitation of the
Lipschitz continuity of the value function (Rachelson and Lagoudakis 2010;
Pirotta, Restelli, and Bascetta 2015), with possible applications outside BC.

##  2 Preliminaries

In this section, we provide the necessary mathematical background (Section
2.1) and the foundations of Markov Decision Processes (Section 2.2).

###  2.1 Mathematical Background

#### Notation

Let $\mathcal{X}$ be a set and $\mathfrak{F}$ be a $\sigma$-algebra over
$\mathcal{X}$, we denote with $\mathcal{P}{(\mathcal{X})}$ the set of
probability measures over the measurable space $(\mathcal{X},\mathfrak{F})$.
Let $x\in\mathcal{X}$, we denote the Dirac delta measure centered in $x$ as
$\delta_{x}$. Let $f:\mathcal{X}\rightarrow\mathbb{R}$ be a function, we
denote the $L_{\infty}$-norm as $\|f\|_{\infty}=\sup_{x\in\mathcal{X}}f(x)$
and with $\|f\|_{i}$ the $L_{i}$-norm for $i\in\\{1,2\\}$.

#### Lipschitz Continuity

Let $(\mathcal{X},d_{\mathcal{X}})$ and $(\mathcal{Y},d_{\mathcal{Y}})$ be two
metric spaces and $L>0$. A function $f:\mathcal{X}\rightarrow\mathcal{Y}$ is
said to be $L$-_Lipschitz continuous_ ($L$-LC) if:

$\displaystyle d_{\mathcal{Y}}(f(x),f(x^{\prime}))\leq
Ld_{\mathcal{X}}(x,x^{\prime}),\quad\forall x,x^{\prime}\in\mathcal{X}.$

We denote the Lipschitz semi-norm of function $f$ as
$\left\|f\right\|_{L}=\sup_{x,x^{\prime}\in\mathcal{X},x\neq
x^{\prime}}{d_{\mathcal{Y}}(f(x),f(x^{\prime}))}/{d_{\mathcal{X}}(x,x^{\prime})}$.
In the real space ($X\subseteq\mathbb{R}^{n}$), we use the Euclidean distance,
i.e., $d_{\mathcal{X}}(x,x^{\prime})=\|x-x^{\prime}\|_{2}$. For probability
measures ($\mathcal{X}=\mathcal{P}{(\Omega)}$), the most intuitive distance is
the _total variation_ (TV), defined as:

$\displaystyle\mathrm{TV}(\mu,\nu)=\sup_{\|f\|_{\infty}\leq
1}\left|\int_{\Omega}f(\omega)\left(\mu-\nu\right)(\mathrm{d}\omega)\right|\;\forall\mu,\nu\in\mathcal{P}{(\Omega)}$

However, with continuous deterministic distributions, the TV takes its maximum
value $1$ (Figure 1). Thus, we introduce $L_{1}$-_Wasserstein_ distance
(Villani 2009), defined as:

$\displaystyle\mathcal{W}(\mu,\nu)=\sup_{\left\|f\right\|_{L}\leq
1}\left|\int_{\Omega}f(\omega)(\mu-\nu)(\mathrm{d}\omega)\right|\quad\forall\mu,\nu\in\mathcal{P}{(\Omega)}$

It is worth noting that, for deterministic distributions, we have
$\mathcal{W}(\delta_{x},\delta_{x^{\prime}})=d_{\mathcal{X}}(x,x^{\prime})$.

#### Hölder Continuity

The notion of Lipschitz continuity is generalized by Hölder continuity. Let
$(\mathcal{X},d_{\mathcal{X}})$ and $(\mathcal{Y},d_{\mathcal{Y}})$ be two
metric spaces and $L,\alpha>0$. A function
$f:\mathcal{X}\rightarrow\mathcal{Y}$ is said to be $(\alpha,L)$-_Hölder
continuous_ ($(\alpha,L)$-HC) if:

$\displaystyle d_{\mathcal{Y}}(f(x),f(x^{\prime}))\leq
Ld_{\mathcal{X}}(x,x^{\prime})^{\alpha},\quad\forall
x,x^{\prime}\in\mathcal{X}.$

It is worth noting that: (i) Lipschitz continuity is obtained by Hölder
continuity for $\alpha=1$; (ii) only constant functions are $(\alpha,L)-$HC
for $\alpha>1$; (iii) in bounded domains, the higher the value of $\alpha$ the
more restrictive the condition.

#### Convolution

Let $f,g:\mathbb{R}^{n}\to\mathbb{R}$ be two functions, their _convolution_ is
defined for all $x\in\mathbb{R}^{n}$ as:

$(f*g)(x)\coloneqq\int_{\mathbb{R}^{n}}f(x-y)g(y)\mathrm{d}y=\int_{\mathbb{R}^{n}}f(y)g(x-y)\mathrm{d}y.$

We introduce the following regularity assumption regarding the probability
measures.

######  Definition 1.

A probability measure $\mathcal{L}\in\mathcal{P}{(\mathbb{R}^{n})}$ is $L$-TV-
Lipschitz continuous ($L$-TV-LC) if:

$\mathrm{TV}(\mathcal{L}(\cdot+h),\mathcal{L}(\cdot))\leq
L\|h\|_{2},\qquad\forall h\in\mathbb{R}^{n}.$

Under this assumption, we can prove that the convolution regularizes bounded
and possibly irregular functions.

######  Proposition 1.

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a function such that
$\|f\|_{\infty}\leq M$, and let $\mathcal{L}\in\mathcal{P}{(\mathbb{R}^{n})}$
be an $L$-TV-LC probability measure that admits density function
$\ell:\mathbb{R}^{n}\rightarrow\mathbb{R}_{\geq 0}$. Then, the convolution
$f*\ell$ is $2LM$-LC continuous.

###  2.2 Markov Decision Processes

A discrete-time discounted Markov Decision Process (MDP, Puterman 2014) is a
6-tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},p,r,\gamma,\mu)$ where
$\mathcal{S}$ and $\mathcal{A}$ are the measurable sets of states and actions,
$p:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}{(\mathcal{S})}$ is the
transition model that defines the probability measure $p(\cdot|s,a)$ of the
next state when playing action $a\in\mathcal{A}$ in state $s\in\mathcal{S}$,
$r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is the reward function
defining the reward $r(s,a)$ upon playing action $a\in\mathcal{A}$ in state
$s\in\mathcal{S}$, $\gamma\in[0,1)$ is the discount factor, and
$\mu\in\mathcal{P}{(\mathcal{S})}$ is the initial-state distribution. The
agent’s behavior is modeled by a (Markovian stationary) policy
$\pi:\mathcal{S}\rightarrow\mathcal{P}{(\mathcal{A})}$, which assigns a
probability measure $\pi(\cdot|s)$ of the action to be taken in state
$s\in\mathcal{S}$. With little abuse of notation, when the policy is
deterministic, we denote with $\pi(s)$ the action played in state
$s\in\mathcal{S}$. The execution of a policy determines a _$\gamma$
-discounted visitation distribution_, defined as:

$\displaystyle
d^{\pi}(s)\coloneqq(1-\gamma)\sum_{t=0}^{+\infty}\gamma^{t}\operatorname*{\mathbb{P}}(s_{t}=s|\pi,\mu),\quad\forall
s\in\mathcal{S}.$

#### Value Functions

The state-action value function (or _Q-function_) which quantifies the
expected discounted sum of the rewards obtained under a policy $\pi$, starting
from a state $s\in\mathcal{S}$ and fixing the first action $a\in\mathcal{A}$:

$\displaystyle
Q^{\pi}(s,a)\coloneqq\mathbb{E}_{\pi}\left[\sum_{t=0}^{+\infty}\gamma^{t}r(s_{t},a_{t})\bigg{|}s_{0}=s,a_{0}=a\right],$
(1)

where $\mathop{\mathbb{E}}_{\pi}$ denotes the expectation w.r.t. to the
stochastic process $a_{t}\sim\pi(\cdot|s_{t})$ and $s_{t+1}\sim
p(\cdot|s_{t},a_{t})$ for all $t\in\mathbb{N}$. The state value function (or
_V-function_) is defined as
$V^{\pi}(s)\coloneqq\mathop{\mathbb{E}}_{a\sim\pi(\cdot|s)}[Q^{\pi}(s,a)]$,
for all $s\in\mathcal{S}$. Given an initial state distribution $\mu$, the
_expected return_ is defined as:

$J^{\pi}\coloneqq\mathop{\mathbb{E}}_{s\sim\mu}[V^{\pi}(s)]=\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi},a\sim\pi(\cdot|s)}[r(s,a)].$

#### Lipschitz MDPs

We now introduce notions that will allow us to characterize the smoothness of
an MDP (Rachelson and Lagoudakis 2010). To this end, we assume that the state
space $\mathcal{S}$ and action space $\mathcal{A}$ are metric spaces endowed
with the corresponding distance functions $d_{\mathcal{S}}$ and
$d_{\mathcal{A}}$.

######  Assumption 1 (Lipschitz MDP).

An MDP $\mathcal{M}$ is $(L_{p},L_{r})$-LC if, for all
$(s,a),(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}$ it holds that:

$\displaystyle\mathcal{W}(p(\cdot|s,a),p(\cdot|s^{\prime},a^{\prime}))\leq
L_{p}\left(d_{\mathcal{S}}(s,s^{\prime})+d_{\mathcal{A}}(a,a^{\prime})\right),$
$\displaystyle\left|r(s,a)-r(s^{\prime},a^{\prime})\right|\leq
L_{r}\left(d_{\mathcal{S}}(s,s^{\prime})+d_{\mathcal{A}}(a,a^{\prime})\right).$

######  Assumption 2 (Lipschitz Policy).

A (Markovian stationary) policy $\pi$ is $L_{\pi}$-LC if, for all
$s,s^{\prime}\in\mathcal{S}$ it holds that:

$\displaystyle\mathcal{W}(\pi(\cdot|s),\pi(\cdot|s^{\prime}))\leq
L_{\pi}d_{\mathcal{S}}(s,s^{\prime}).$

Figure 1: Comparison between TV and Wasserstein distances for two Gaussian
distributions $\mu$ and $\nu$. Left: $\mathrm{TV}(\mu,\nu)\approx 0.38$,
$\mathcal{W}(\mu,\nu)=1$, Center: $\mathrm{TV}(\mu,\nu)\approx 1$,
$\mathcal{W}(\mu,\nu)=1$, Right: $\mathrm{TV}(\mu,\nu)\approx 1$,
$\mathcal{W}(\mu,\nu)=0.4$

Note, if instead of the Wasserstein metric, we had used the TV, these
assumptions would be way more restrictive, not holding for deterministic
environment/policies with continuous state-action spaces (Munos and Szepesvári
2008). Under Assumptions 1 and 2, provided that $\gamma L_{p}(1+L_{\pi})<1$,
the Q-function $Q^{\pi}$ is $L_{Q}$-LC with $L_{Q}\leq\frac{L_{r}}{1-\gamma
L_{p}(1+L_{\pi})}$ (Rachelson and Lagoudakis 2010, Theorem 1).

##  3 Bound for Imitating Policies based on Wasserstein Distance

The high-level goal of this work is to find a theoretical guarantee for the
imitator policies learned with BC. Specifically, we want to bound the
difference in expected return $J^{\pi_{E}}-J^{\pi_{I}}$ between the _imitator_
policy $\pi_{I}$ learned with BC and the _expert_ policy $\pi_{E}$ in terms of
a distributional divergence between the corresponding action distributions.

The best-known results for this kind of analysis, in the case of _discrete_
action spaces, are proved in (Xu, Li, and Yu 2020) and we report it below for
completeness.222The result reported in (Xu, Li, and Yu 2020) involves the KL-
divergence and is obtained, via Pinsker’s inequality, from the one we report
that is tighter (Appendix A.2 of Xu, Li, and Yu (2020)).

######  Theorem 2 (Xu, Li, and Yu (2020), Theorem 1).

Let $\pi_{E}$ be the expert policy and $\pi_{I}$ be the imitator policy. If
$|r(s,a)|\leq R_{\max}$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$, it
holds that:

$J^{\pi_{E}}-J^{\pi_{I}}\leq\frac{2R_{\max}}{(1-\gamma)^{2}}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\mathrm{TV}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))].$

As anticipated, this result is not suitable for continuous action spaces,
since the TV between different policies would take its maximum value $1$
whenever one of the two policies is deterministic. The following example
clarifies the issue.

######  Example 1 (label=exa:1).

Suppose that the action space is a real space
$\mathcal{A}\subseteq\mathbb{R}^{n}$ and that both expert $\pi_{E}$ and the
imitator $\pi_{I}$ policies are deterministic. A common way to perform BC is
to minimize the _mean squared error_ (MSE) between the expert’s action and the
imitator one. Suppose we are able to provide the following guarantee on the
MSE, for some $\varepsilon>0$:

$\displaystyle\mathop{\mathbb{E}}_{s\sim
d^{E}}\left[\left\|\pi_{E}(s)-\pi_{I}(s)\right\|^{2}_{2}\right]\leq\varepsilon^{2}.$
(2)

However, this condition provides no guarantee in TV. Indeed, by taking
$\pi_{I}(s)=\pi_{E}(s)+\frac{\varepsilon}{\sqrt{n}}\mathbf{1}_{n}$, being
$\mathbf{1}_{n}$ the vector of all $1$s, Equation (2) is fulfilled, but we
obtain: $\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\mathrm{TV}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))]=\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\mathds{1}\\{\pi_{E}(s)\neq\pi_{I}(s)\\}]=1$, where $\mathds{1}$
is the indicator function.

###  3.1 A Bound based on Wasserstein Distance

Even if the existing analysis of Xu, Li, and Yu (2020) cannot be applied in
continuous action spaces, as shown in Example LABEL:exa:1, it is not hard to
leverage the regularity of the MDP to effectively bound the performance
difference $J^{\pi_{E}}-J^{\pi_{I}}$.

######  Theorem 3.

Let $\pi_{E}$ be the expert policy and $\pi_{I}$ be the imitator policy. If
that state-action value function $Q^{\pi_{I}}$ of the imitator policy
$\pi_{I}$ is $L_{Q^{\pi_{I}}}$-LC, then it holds that:

$J^{\pi_{E}}-J^{\pi_{I}}\leq\frac{L_{Q^{\pi_{I}}}}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\mathcal{W}(\pi_{I}(\cdot|s),\pi_{E}(\cdot|s))].$

###### Proof.

Using the _performance difference lemma_ (Kakade and Langford 2002), we have:

$\displaystyle J^{\pi_{E}}-J^{\pi_{I}}=$
$\displaystyle\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}\left[\mathop{\mathbb{E}}_{a\sim\pi_{E}(\cdot|s)}[A^{\pi_{I}}(s,a)]\right],$

where $A^{\pi_{I}}(s,a)=Q^{\pi_{I}}(s,a)-V^{\pi_{I}}(s)$ is the advantage
function. The inner expectation can be written as:

$\displaystyle\mathop{\mathbb{E}}_{a\sim\pi_{E}(\cdot|s)}[A^{\pi_{I}}(s,a)]$
$\displaystyle=\int_{A}Q^{\pi_{I}}(s,a)(\pi_{E}(\mathrm{d}a|s)-\pi_{I}(\mathrm{d}a|s))$
$\displaystyle\leq\sup_{s\in\mathcal{S}}\left\|Q^{\pi_{I}}(s,\cdot)\right\|_{L}\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s)),$

where the inequality follows from the definition of Wasserstein metric. The
result is obtained by observing that
$\sup_{s\in\mathcal{S}}\left\|Q^{\pi_{I}}(s,\cdot)\right\|_{L}\leq\left\|Q^{\pi_{I}}\right\|_{L}\leq
L_{Q^{\pi_{I}}}$. ∎

A similar bound was previously derived by (Pirotta, Restelli, and Bascetta
2015, Theorem 1) and (Asadi, Misra, and Littman 2018, Theorem 2). However,
(Pirotta, Restelli, and Bascetta 2015) assume that the policy is LC w.r.t. a
policy parametrization. Instead, the result of (Asadi, Misra, and Littman
2018) involves the transition model instead of the policy and requires a bound
uniform over $\mathcal{S}\times\mathcal{A}$ on the Wasserstein distance
between the true and the estimated models. Let us now revisit Example
LABEL:exa:1 in light of Theorem 3.

######  Example 2 (continues=exa:1).

Under Equation (2) , we can provide an effective guarantee on the Wasserstein
distance:

$\displaystyle\mathop{\mathbb{E}}_{s\sim d^{\pi_{E}}}$
$\displaystyle[\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))]=\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\left\|\pi_{E}(s)-\pi_{I}(s)\right\|_{1}]$
$\displaystyle\quad\leq{\mathbb{E}_{s\sim
d^{\pi_{E}}}[\|\pi_{E}(s)-\pi_{I}(s)\|^{2}_{2}]}^{\frac{1}{2}}\leq\varepsilon,$

where in the first inequality, we used Jensen’s inequality.

Comparing Theorem 3 with Theorem 2, we no longer require the uniform bound
$R_{\max}$ on the reward function, but we introduce an additional assumption
on the regularity of the imitator Q-function $Q^{\pi_{I}}$. Clearly, we should
find suitable assumptions under which $L_{Q^{\pi_{I}}}$ is finite. As we
anticipated in Section 2.2, the only known result that provides such an
estimate under the assumption of Lipschitz MDP and Lipschitz policy with
Wasserstein metric is (Rachelson and Lagoudakis 2010), where the authors
proved that, if $\gamma L_{p}(1+L_{\pi})<1$ is satisfied, $L_{Q^{\pi}}$ can be
chosen as:

$\displaystyle L_{Q^{\pi}}\coloneqq\frac{L_{r}}{1-\gamma L_{p}(1+L_{\pi})}.$
(3)

However, we argue that condition $\gamma L_{p}(1+L_{\pi})<1$ is very demanding
and often unrealistic. Indeed, to fulfill it we need at least one of these
conditions to be satisfied:

  1. (i)

$\gamma\ll 1$: in practice, it is almost always false, since the discount
factor is often chosen to be close to $1$;

  2. (ii)

$L_{p}<1$: this is a very unrealistic assumption, since it would make all the
states shrink exponentially when the same actions are performed;

  3. (iii)

$L_{\pi}\approx 0$: the action depends very little on the state so that there
is a very limited possibility of controlling the environment (this condition
alone is not even sufficient).

Figure 2: State value functions of Example LABEL:ese1. Left: the bound of
(Rachelson and Lagoudakis 2010) hold and it is tight. Right: the bound of
(Rachelson and Lagoudakis 2010) does not hold, but our bound based on Hölder
continuity holds, for different values of $\alpha\in(0,1)$.

###  3.2 The Tightness of the Value Function Lipschitz Constant

It is legitimate to question whether the value $L_{Q^{\pi}}$ of Equation (3),
widely employed in the literature (e.g., Rachelson and Lagoudakis 2010;
Pirotta, Restelli, and Bascetta 2015; Asadi, Misra, and Littman 2018), is a
tight approximation of the Lipschitz semi-norm $\|Q^{\pi}\|_{L}$. In this
section, we prove that the result cannot be improved, at least when requiring
the Lipschitz continuity of the value function. Example LABEL:ese1 shows that
the value function $Q^{\pi}$ can be made non-LC even when the MDP and the
policy are LC, while Theorem 4 proves that a bound like the one of Theorem 3
cannot be obtained for a generic Lipschitz MDP and Lipschitz policies.

######  Example 3 (label=ese1).

Let $\mathcal{M}$ be an MDP and $\pi$ be a policy defined as follows, given
the constants $L_{p},L_{r}>0$:

  * •

$\mathcal{S}=[-1,1]$;

  * •

$\mathcal{A}=\\{0\\}$;

  * •

The dynamic is deterministic. From every state $s\in\mathcal{S}$, performing
action $0$, the only possible, the environment moves to the state
$s^{\prime}=\mathrm{clip}(L_{p}s,-1,1)$.333$\mathrm{clip}(x,a,b)$ is the
_clipping_ function, i.e., $\max\\{\min\\{x,b\\},a\\}$. This means that
$p(\mathrm{d}s^{\prime}|s,a)=\delta_{\mathrm{clip}(L_{p}s,-1,1)}(\mathrm{d}s^{\prime})$;

  * •

$r(s,a)=L_{r}s$;

  * •

The initial state distribution is $\mu=\mathrm{Uni}([0,1])$ (not influential
for the derivation that follows).

This MDP is $(L_{p},L_{r})$-LC and the policy has Lipschitz constant equal to
$L_{\pi}=0$, since there is one action only. Equation (3) ensures that the
state value function $V^{\pi}$ (that is equal to the state-action value
function $Q^{\pi}$ since there is one action only) is LC with constant:

$L_{V^{\pi}}=\frac{L_{r}}{1-\gamma L_{p}}.$

Since the state space is one dimensional, we can compute the state value
function $V^{\pi}$ exactly:

$V^{\pi}(s)=L_{r}\sum_{k=0}^{+\infty}\gamma^{k}\
\mathrm{clip}{\left(L_{p}^{k}s,-1,1\right)},\qquad\forall s\in\mathcal{S}.$

As shown in Figure 2 left, the point of maximal slope $s=0$. Even if we have
employed the specific values $L_{p}=1.15$, $L_{r}=1$, and $\gamma=0.75$, it is
simple to see that this property is valid in general. Moreover, we have
plotted in orange the line which passes through the origin, having slope equal
to:

$L_{V^{\pi}}=\frac{L_{r}}{1-\gamma L_{p}}=\frac{1}{1-0.75\cdot 1.15}\approx
7.27,$

which is the tangent line to the state value function in $s=0$, as it also can
be found analytically:

$\frac{\partial V^{\pi}}{\partial
s}(0)=L_{r}\sum_{k=0}^{+\infty}\gamma^{k}L_{p}^{k}=\frac{L_{r}}{1-\gamma
L_{p}}.$

This means that, in this case, the choice of the Lipschitz constant provided
by the theory (Equation 3) is actually tight.

What happens if we reach the hard edge of $\gamma L_{p}(1+L_{\pi})=\gamma
L_{p}>1$, where Equation (3) does not guarantee any property? For instance, by
taking $L_{p}=1.15$, $L_{r}=1$, and $\gamma=0.9$, we lose any Lipschitz
property, finding a derivative which is unbounded, as shown in Figure 2 right.

Note that, in this example, we are able to find a non-LC state value function
even in the apparently simple case of $\mathcal{A}=\\{0\\}$, where
$L_{\pi}=0$. Therefore, this example also shows that the dynamics of the
system alone is enough to make the state value function irregular.
Furthermore, the same example can be adapted to prove that, for a generic
Lipschitz MDP and a pair of Lipschitz policies, a bound like the one of
Theorem 3 cannot be obtained in general.

######  Theorem 4.

There exist an $(L_{p},L_{r})$-LC MDP and an $L_{\pi}$-LC policy $\pi$ such
that for every finite constant $C>0$, (even depending on $L_{p}$, $L_{\pi}$,
and $L_{r}$), there exists an $L_{\pi}$-LC policy $\pi^{\prime}$ such that:

$J^{\pi}-J^{\pi^{\prime}}\geq C\mathop{\mathbb{E}}_{s\sim
d^{\pi}}[\mathcal{W}(\pi(\cdot|s),\pi^{\prime}(\cdot|s))].$

The proof is reported in Appendix B. If we set $\pi=\pi_{E}$ as the expert
policy and $\pi^{\prime}=\pi_{I}$ as an imitator policy, Theorem 4 shows that,
even if the MDP and the policies are LC, we cannot, in general, upper bound
the performance difference $J^{\pi_{E}}-J^{\pi_{I}}$ with the expected
Wasserstein distance $\mathop{\mathbb{E}}_{s\sim
d^{\pi}}[\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))]$. This is in line
with the fact that, without additional assumptions, e.g., when $\gamma
L_{p}(L_{\pi}+1)<1$ does not hold, Theorem 4 is vacuous. Therefore, these
bounds cannot be improved in the framework of Lipschitz continuity, however, a
weaker notion of regularity can be used to generalize the previous theorems.

##  4 Hölder Continuity is All We Need

In this section, we propose an approach for overcoming the limitations of the
Lipschitz continuity, discussed in the previous section. In Section 4.1, we
show that the state-action value function $Q^{\pi}$ is always Hölder
continuous, provided that the MDP and the policy are LC. Then, in Section 4.2,
we apply these findings to BC, deriving a bound on the performance difference
$J^{\pi_{E}}-J^{\pi_{I}}$ in terms of the Wasserstein distance that holds for
_every_ LC MDP and policy.

###  4.1 The Hölder Continuity of the Value Function

The first step to improve the result of (Rachelson and Lagoudakis 2010) is to
observe that, like in Example LABEL:ese1, even when the value function is not
Lipschitz continuous, it keeps being continuous. This observation is not, in
principle, accounted for by the previous analysis, which provides no result
when $\gamma L_{p}(1+L_{\pi})>1$. This suggests that employing a notion of
regularity that is stronger than continuity but weaker than Lipschitz
continuity, as Hölder continuity, might lead to an improvement of the
analysis. Indeed, we are able to prove the following generalization.

######  Theorem 5 (Hölder-continuity of the Q-function).

Let $\mathcal{M}$ be an $(L_{p},L_{r})$-LC MDP, let $\pi$ be an $L_{\pi}$-LC
policy, and let

$0<\alpha<\overline{\alpha}\coloneqq\min\left\\{1,\frac{-\log\gamma}{\log(L_{p}(1+L_{\pi}))}\right\\}.$

If the state space $\mathcal{S}$ and the action space $\mathcal{A}$ admit
finite diameter444The _diameter_ of a metric space
$(\mathcal{X},d_{\mathcal{X}})$ is defined as:
$\mathrm{diam}{(\mathcal{X})}=\sup_{x,x^{\prime}\in\mathcal{X}}d_{\mathcal{X}}(x,x^{\prime})$.
$\mathrm{diam}{(\mathcal{S})}$ and $\mathrm{diam}{(\mathcal{A})}$,
respectively, then the state-action value function $Q^{\pi}$ is
$(\alpha,L_{Q^{\pi},\alpha})-$HC with a Hölder constant bounded by:

$L_{Q^{\pi},\alpha}\coloneqq\frac{L_{r}\left(\mathrm{diam}{(\mathcal{S})}+\mathrm{diam}{(\mathcal{A})}\right)^{1-\alpha}}{1-\gamma(L_{p}(1+L_{\pi}))^{\alpha}}.$

The proof is reported in Appendix C. The requirement on the finiteness of the
diameter of the state and action spaces is a mild condition. Indeed, it is
common to assume that these spaces are bounded (or even compact), which
implies a finite diameter. Furthermore, as commonly done in practice, one can
easily re-scale the states and actions, modifying the diameter and not
altering the nature of the problem.555As an alternative, one could assume that
the reward function $r(s,a)$ is $(\alpha,L_{r})$-HC, removing the need for the
diameters. Furthermore, we can easily obtain the Hölder constant of the state
value function $V^{\pi}$.

######  Proposition 6 (Hölder-continuity of the V-function).

Let $\pi$ be an $L_{\pi}$-LC policy. If the state-action value function
$Q^{\pi}$ is $(\alpha,L_{Q^{\pi},\alpha})$-HC, then the corresponding state
value function $V^{\pi}$ is $(\alpha,L_{V^{\pi},\alpha})$-HC with:

$\displaystyle L_{V^{\pi},\alpha}\coloneqq
L_{Q^{\pi},\alpha}(L_{\pi}+1)^{\alpha}.$

These result represent a generalization of those of (Rachelson and Lagoudakis
2010), which are obtained by setting $\alpha=1$.

Moreover, this Theorem 5 implies that the value functions of an LC MDP and
policy is always continuous, since any HC function is also continuous,
regardless of its constants, as it seemed from the previous example. Coming
back to Example LABEL:ese1, we can perform further analyses.

######  Example 4 (continues=ese1).

We can use Theorem 5 to provide an upper bound on the value function even if
the Lipschitz continuity does not hold. The critical exponent is given by:

$\overline{\alpha}=-\frac{\log\gamma}{\log(L_{p}(1+L_{\pi}))}\approx 0.72.$

For every value of $\alpha<\overline{\alpha}$, the state value function
$V^{\pi}$ is $(\alpha,L_{V^{\pi},\alpha})-$HC. As we can see in Figure 2
right, for small $\alpha$, the bound provided by
$L_{V^{\pi},\alpha}|s|^{\alpha}$ is tight for $s\to 1$.

###  4.2 A More General Bound based on Wasserstein Distance

Similarly to what we have done in Section 3, to a result of regularity, we are
able to associate a result about the loss of BC, bounding the difference in
performance between two policies with their Wasserstein distance. Indeed,
thank to Theorem 5, we can prove the following bound.

######  Theorem 7 (Optimal Error Rate for BC).

Let $\pi_{E}$ be the expert policy and $\pi_{I}$ be the imitator policy. If
that state-action value function $Q^{\pi_{I}}$ of the imitator policy
$\pi_{I}$ is $(\alpha,L_{Q^{\pi_{I}},\alpha})$-HC, then it holds that:

$J^{\pi_{E}}-J^{\pi_{I}}\leq\frac{L_{Q^{\pi_{I}},\alpha}}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}\left[\mathcal{W}\left(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s)\right)^{\alpha}\right].$

Furthermore, if the MDP $\mathcal{M}$ is $(L_{p},L_{r})$-LC and the imitator
policy $\pi_{I}$ is $L_{\pi_{I}}$-LC, the bound is tight for what concerns the
exponent $\alpha$ that cannot be improved above the critical value
$\overline{\alpha}$ of Theorem 5.

The proof is reported in Appendix C. This is a remarkable result, since it is
valid for every LC MDP and policy. As expected, a low value of $\alpha$ leads
to a looser bound. Unfortunately, this bound, despite being tight in the
exponent, is difficult to manage in practice. Indeed, in order to minimize the
right-hand side, $\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))^{\alpha}]$, one
should know the value $\alpha$ in advance. However,
$\alpha\leq\overline{\alpha}$ depends on the Lipschitz constants of the
environment and of the policy, which are usually unknown. Therefore, no
imitation learning algorithm can be trained to minimize this error explicitly.
Fortunately, we can see that, weakening this result, we can obtain a more
practical guarantee. Since $0<\alpha<1$, we can apply Jensen’s inequality to
obtain:

$\displaystyle\\!\\!\\!J^{\pi_{E}}-J^{\pi_{I}}\leq\frac{L_{Q^{\pi_{I}},\alpha}}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}\left[\mathcal{W}\left(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s)\right)\right]^{\alpha}.\\!\\!\\!$
(4)

In this formulation, we minimize the expected Wasserstein distance only, and
the knowledge of $\alpha$ is not needed, but its value impacts the kind of
guarantee we can provide.

######  Remark 1.

If we perform BC in a $(L_{p},L_{r})$-LC MDP and with a $L_{\pi_{I}}$-LC
imitator policy $\pi_{I}$, the best possible performance guarantee (from
Equation 4) is given by:

$J^{\pi_{E}}-J^{\pi_{I}}\leq\mathcal{O}(\varepsilon^{\alpha}),$

where $\varepsilon$ is the square root of the imitation MSE, i.e.,
$\varepsilon^{2}=\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\|\pi_{E}(s)-\pi_{I}(s)\|^{2}_{2}]$ as defined in Example
LABEL:exa:1, and
$\alpha<\overline{\alpha}=-\frac{\log\gamma}{\log(L_{p}(1+L_{\pi_{I}}))}$, the
critical exponent.

Therefore, a very low value of $\alpha$, corresponding to lack of regularity,
can badly influence the possibility of learning a good imitator policy.

##  5 Noise Injection

BC may struggle when the regularity assumptions are lacking. However, in
practice, using a _noisy_ expert policy may significantly help the learning
process (Laskey et al. 2017b). This empirical benefit is justified by the
intuition that noise helps in exploring the neighborhood of the expert
trajectories. In this section, we formulate this empirical evidence in a
mathematically rigorous way. Indeed, we show how to break the barrier enforced
by Theorem 7, whose result is obtained by a deterministic expert. Clearly,
these advantages come with the price that a noisy expert might experience a
loss in expected return compared to the deterministic one.

Figure 3: The performance of the expert $J^{\pi}$ as a function of the
standard deviation of the noise $\sigma$. The performance is measured on 40
episodes int environment repeated for 20 different random seeds (nuance
represents the $95\%$ non-parametric c.i.).

###  5.1 Noise Injection: a Mathematical Formulation

The simplest form of noise injection is realized by adding to the expert’s
action $a_{E,t}$ a noise component $\eta_{t}$. In particular, assuming that
the action space is real, i.e., $\mathcal{A}\subseteq\mathbb{R}^{n}$, we have:

$\displaystyle\forall
t\in\mathbb{N}:\qquad\begin{cases}a_{t,E}\sim\pi_{E}(\cdot|s_{t})\\\
\eta_{t}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathcal{L}\\\
a_{t}=a_{t,E}+\eta_{t}\\\ \end{cases},$ (5)

where $\\{\eta_{t}\\}_{t\in\mathbb{N}}$ is a noise sequence whose components
are independent between each other and from the sequences of states and
actions, and identically distributed by law
$\mathcal{L}\in\mathcal{P}{(\mathcal{A})}$. If $\mathcal{L}$ admits a density
function, we can express the density function of the played action $a_{t}$ as
the convolution of the expert policy density function $\pi_{E}$ and the
density function $\ell$ of the noise law $\mathcal{L}$. Note that the
formalization in Equation (5) encompasses distributions that do not correspond
to the intuitive idea of _noise_ (e.g., when $\mathcal{L}$ is a discrete law).
To obtain a meaningful result, we enforce the following assumption.

######  Assumption 3.

The law of the noise $\mathcal{L}$ admits a density function w.r.t. a
reference measure $\ell:\mathbb{R}^{n}\rightarrow\mathbb{R}_{\geq 0}$ and is
TV-LC (see Definition 1) with constant $L_{\ell}$.

Under this assumption, denoting with $\pi_{E,\ell}$ the policy with noise
injection, i.e., $a_{t}\sim\pi_{E,\ell}(\cdot|s_{t})$, we have that:

$\pi_{E,\ell}(a|s)=\int_{\mathbb{R}^{n}}\pi_{E}(a^{\prime}|s)\ell(a-a^{\prime})\mathrm{d}a^{\prime},\;\;\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$

This represents the convolution of the policy density function $\pi_{E}$ and
the noise density function $\ell$. In other words, this shows that the action
taken by the expert policy $a_{E,t}$ is averaged over the noise probability
distribution.

Assumption 3 covers the most common types of noise, like the Gaussian or the
uniform ones. In fact, we can prove that every univariate unimodal
distribution satisfies Definition 1 (see Proposition 9 in the Appendix A).
Considering multivariate Gaussian noise, we directly derive the $L_{\ell}$
constant.

######  Example 5.

Suppose the noise is sampled from a zero-mean Gaussian distribution
$\mathcal{N}(0,\Sigma)$ with covariance matrix ${\Sigma}$, the previous
integral writes, for all $(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\pi_{E,\ell}(a|s)=\int_{\mathbb{R}^{n}}\pi_{E}(a^{\prime}|s)\underbrace{\frac{e^{-\frac{1}{2}(a-a^{\prime})^{T}\Sigma^{-1}(a-a^{\prime})}}{(2\pi)^{n/2}\mathrm{det}({\Sigma})^{1/2}}}_{\ell(a-a^{\prime})}\mathrm{d}a^{\prime},$

where we recognise the Gaussian $n$-variate density $\ell$. Assumption 3 is
verified since, for $h\in\mathbb{R}^{n}$:

$\displaystyle\mathrm{TV}{\left(\mathcal{N}(h,\Sigma),\mathcal{N}(0,\Sigma)\right)}$
$\displaystyle\leq\sqrt{\frac{1}{2}\mathrm{KL}{\left(\mathcal{N}(h,\Sigma),\mathcal{N}(0,\Sigma)\right)}}$
$\displaystyle=\frac{1}{2}\left\|h\right\|_{\Sigma^{-1}}\leq\frac{1}{2\sqrt{s_{\min}(\Sigma)}}\|h\|_{2},$

where we used Pinsker’s inequality and $s_{\min}(\cdot)$ denoted the minimum
singular value of a matrix. In particular, if $\Sigma$ is diagonal as
$\sigma^{2}I$, we have that $L_{\ell}=1/(2\sigma)$.

It is worth noting that, in the diagonal covariance case, $L_{\ell}$ is
proportional to $\sigma^{-1}$. This suggests that, the smaller the impact of
the noise $\mathcal{L}$, i.e., the smaller the standard deviation $\sigma$,
the higher the constant $L_{\ell}$. Indeed, as $\sigma$ decreases, the
regularization effect of the noise becomes less relevant (in the limit
$\sigma\rightarrow 0$, noise injection vanishes).

###  5.2 A Bound based on Wasserstein Distance for Noise Injection

We are now able to prove a performance guarantee for BC with noise injection.
The idea is based on a simple yet interesting fact. We can use the noise to
smooth a bounded function, as in Proposition 1. Applying this approach to the
state-action value function, leads to the following result.

######  Theorem 8.

Let $\pi_{E}$ be the expert policy and $\pi_{I}$ be the imitator policy. Let
us suppose that we have injected a noise of density function $\ell$,
satisfying Assumption 3 to obtain a noisy expert $\pi_{E,\ell}$ and a noisy
imitator $\pi_{I,\ell}$. If $|Q^{\pi_{I}}(s,a)|\leq Q_{\max}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$, it holds that:

$J^{\pi_{E,\ell}}-J^{\pi_{I,\ell}}\leq\frac{2L_{\ell}Q_{\max}}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E,\ell}}}[\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))].$

The proof is reported in Appendix D. Some observations are in order. First,
note the similarity with Theorem 3, with the only difference being the
substitution of $L_{Q^{\pi}}$ with $2L_{\ell}Q_{\max}$. Second, we require no
smoothness assumption (e.g., Lipschitz continuity) on the environment or on
the policy. Yet, if in the previous result of Theorem 3 the constant
$L_{Q^{\pi}}$ could easily become infinite, now, the constant
$2L_{\ell}Q_{\max}$ can be easily bounded by
$\frac{2L_{\ell}R_{\max}}{(1-\gamma)^{2}}$, since
$Q_{\max}\leq\frac{R_{\max}}{1-\gamma}$. From an intuitive perspective, the
need for smoothness in the environment is replaced with an assumption on the
density function of the noise. Lastly, we can see that, in the right-hand side
of the formula, the error is measured by the Wasserstein distance of the non-
noisy policies. This is advisable, since it implies that the intrinsic error
due to the noise does not affect the bound besides on the $\gamma$-discounted
visitation distribution. We show in Appendix that this quantity is always
smaller than its counterpart involving the noisy policies.

######  Remark 2.

If we perform BC injecting a noise $\eta_{t}$ of density function $\ell$ and
satisfying Assumption 3, we have the following performance guarantee:

$J^{\pi_{E,\ell}}-J^{\pi_{I,\ell}}\leq\mathcal{O}(\varepsilon),$

where $\varepsilon$ is the MSE of the imitation policy as in Remark 1.

In comparison with Remark 1 for standard BC, we can appreciate that, here, the
exponent $\alpha$ disappeared. Indeed, we have a performance bound that
decreases linearly in the MSE. In many cases, when the environment is not
intrinsically very smooth, or the expert policy is irregular, the $\alpha$
parameter can be very small, slowing down the convergence significantly.
Instead, a liner decay is a relevant improvement of the v speed. Furthermore,
as already noted, no assumption of regularity is required in Theorem 8, so
that the last result has a much wider range of applications.

##  6 Practical Considerations

In the previous sections, we have seen that the use of noise injection allows
having a much better performance guarantee than standard BC (see Remarks 1 and
2). Still, in practice, what matters is to have an imitator policy that is
good itself rather than an imitator that is simply good in mimicking a given
policy. Therefore, if with the noise injection we negatively affect the
performance of the expert, i.e., if $J^{\pi_{E,\ell}}\ll J^{\pi_{E}}$, the
results given about noise injection could become useless. On the contrary, we
argue that adding noise to the expert’s action to a certain extent, does not
particularly affect performance. In Figure 3, we show the results of testing
this statement on some of the most common continuous-actions environments of
the OpenAI gym (Brockman et al. 2016) library. In this simulation,666Details
can be found in Appendix. we first train an expert policy with the well-known
DDPG (Lillicrap et al. 2015), TD3 (Fujimoto, Hoof, and Meger 2018) and PPO
(Schulman et al. 2017) in the following OpenAI gym environments:

  * •

Pendulum-v0: this environment has a continuous action space $[-2,2]$. The
objective is to apply torque on a pendulum to swing it into an upright
position. The whole system is very regular, as it is governed by simple
differential equations, and is also deterministic, except for the initial
position of the pendulum, which is random.

  * •

LunarLanderContinuous-v2: this environment has a continuous action space
$[-1,1]^{2}$. Here, we have to make a rocket land safely in a landing pad. The
dynamics is quite complex, and stochasticity is present to simulate the effect
of the wind.

  * •

BipedalWalker-v3: this environment has a continuous action space $[-1,1]^{4}$.
Here we have to make a bipedal robot walk. The dynamics is even more complex,
but the whole system is deterministic.

Then, we evaluated the performance of these experts with noise injection with
Gaussian noise with different standard deviations. As we can see in figure 3,
even when the noise increases until it is close to the radius of the action
space, at least in seven cases out of nine, the performance does not suffer
significant drops. Intuitively, this can be explained by the fact that we
applied an i.i.d. zero-mean noise sequence that is independent of the state
and the action. Thus, its effect does not accumulate over the horizon.

##  7 Conclusions

In this paper, we have addressed BC in the case of continuous-action
environments from a theoretical perspective. We have shown that the existing
theoretical guarantees on BC are not suitable when dealing with continuous
actions. Thus, we have derived a first bound for the performance guarantees,
under the assumption that the imitator value function is Lipschitz continuous.
Since this latter assumption is demanding (i.e., it is not guaranteed even
when the underlying MDP and policy are LC), we have relaxed it by studying the
continuity properties of the value function. As a result of independent
interest, we have proved that the value function is always Hölder continuous,
under the milder assumption that the underlying MDP and policy are LC. Then,
we have applied these findings to obtain a general bound for the performance
gap of BC, which we have proved to be tight. Finally, we have formalized noise
injection and we have shown the advantages of this practice when applied to
BC.

## References

  * Arora and Doshi (2021) Arora, S.; and Doshi, P. 2021.  A survey of inverse reinforcement learning: Challenges, methods and progress.  _Artif. Intell._ , 297: 103500.
  * Asadi, Misra, and Littman (2018) Asadi, K.; Misra, D.; and Littman, M. L. 2018.  Lipschitz Continuity in Model-based Reinforcement Learning.  In _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , 264–273.
  * Asfour et al. (2008) Asfour, T.; Azad, P.; Gyarfas, F.; and Dillmann, R. 2008.  Imitation Learning of Dual-Arm Manipulation Tasks in Humanoid Robots.  _Int. J. Humanoid Robotics_ , 5(2): 183–202.
  * Bain and Sammut (1995) Bain, M.; and Sammut, C. 1995.  A Framework for Behavioural Cloning.  In _Machine Intelligence 15, Intelligent Agents_ , 103–129.
  * Brockman et al. (2016) Brockman, G.; Cheung, V.; Pettersson, L.; Schneider, J.; Schulman, J.; Tang, J.; and Zaremba, W. 2016.  OpenAI Gym.  gym:arXiv:1606.01540.
  * Fujimoto, Hoof, and Meger (2018) Fujimoto, S.; Hoof, H.; and Meger, D. 2018.  Addressing function approximation error in actor-critic methods.  In _International conference on machine learning_ , 1587–1596. PMLR.
  * Geng, Lee, and Hülse (2011) Geng, T.; Lee, M.; and Hülse, M. 2011.  Transferring human grasping synergies to a robot.  _Mechatronics_ , 21(1): 272–284.
  * Ho and Ermon (2016) Ho, J.; and Ermon, S. 2016.  Generative Adversarial Imitation Learning.  In _Advances in Neural Information Processing Systems 29 (NIPS)_ , 4565–4573.
  * Jeon, Milli, and Dragan (2020) Jeon, H. J.; Milli, S.; and Dragan, A. D. 2020.  Reward-rational (implicit) choice: A unifying formalism for reward learning.  In _Advances in Neural Information Processing Systems 33 (NeurIPS)_.
  * Kakade and Langford (2002) Kakade, S. M.; and Langford, J. 2002.  Approximately Optimal Approximate Reinforcement Learning.  In _Proceedings of the Nineteenth International Conference on Machine Learning (ICML)_ , 267–274.
  * Laskey et al. (2017a) Laskey, M.; Lee, J.; Fox, R.; Dragan, A. D.; and Goldberg, K. 2017a.  DART: Noise Injection for Robust Imitation Learning.  In _1st Annual Conference on Robot Learning (CoRL)_ , 143–156.
  * Laskey et al. (2017b) Laskey, M.; Lee, J.; Fox, R.; Dragan, A. D.; and Goldberg, K. 2017b.  DART: Noise Injection for Robust Imitation Learning.  In _1st Annual Conference on Robot Learning (CoRL)_ , 143–156.
  * Likmeta et al. (2021) Likmeta, A.; Metelli, A. M.; Ramponi, G.; Tirinzoni, A.; Giuliani, M.; and Restelli, M. 2021.  Dealing with multiple experts and non-stationarity in inverse reinforcement learning: an application to real-life problems.  _Mach. Learn._ , 110(9): 2541–2576.
  * Lillicrap et al. (2015) Lillicrap, T. P.; Hunt, J. J.; Pritzel, A.; Heess, N.; Erez, T.; Tassa, Y.; Silver, D.; and Wierstra, D. 2015.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_.
  * Munos and Szepesvári (2008) Munos, R.; and Szepesvári, C. 2008.  Finite-Time Bounds for Fitted Value Iteration.  _Journal of Machine Learning Research_ , 9(5).
  * Osa et al. (2018) Osa, T.; Pajarinen, J.; Neumann, G.; Bagnell, J. A.; Abbeel, P.; and Peters, J. 2018\.  An Algorithmic Perspective on Imitation Learning.  _Found. Trends Robotics_ , 7(1-2): 1–179.
  * Pirotta, Restelli, and Bascetta (2015) Pirotta, M.; Restelli, M.; and Bascetta, L. 2015.  Policy gradient in Lipschitz Markov Decision Processes.  _Mach. Learn._ , 100(2-3): 255–283.
  * Puterman (2014) Puterman, M. L. 2014.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons.
  * Rachelson and Lagoudakis (2010) Rachelson, E.; and Lagoudakis, M. G. 2010.  On the locality of action domination in sequential decision making.
  * Rényi et al. (1961) Rényi, A.; et al. 1961.  On measures of entropy and information.  In _Proceedings of the fourth Berkeley symposium on mathematical statistics and probability_ , volume 1. Berkeley, California, USA.
  * Rozo, Jiménez, and Torras (2013) Rozo, L. D.; Jiménez, P.; and Torras, C. 2013.  A robot learning from demonstration framework to perform force-based manipulation tasks.  _Intell. Serv. Robotics_ , 6(1): 33–51.
  * Schulman et al. (2017) Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O. 2017.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_.
  * Villani (2009) Villani, C. 2009.  _Optimal transport: old and new_ , volume 338.  Springer.
  * Xu, Li, and Yu (2020) Xu, T.; Li, Z.; and Yu, Y. 2020.  Error Bounds of Imitating Policies and Environments.
  * Yuval (2022) Yuval, P. 2022.  Wasserstein metric vs Holder continuity.  Mathematics Stack Exchange.  URL:https://math.stackexchange.com/q/4448627 (version: 2022-05-12).
  * Zanzotto (2019) Zanzotto, F. M. 2019.  Viewpoint: Human-in-the-loop Artificial Intelligence.  _J. Artif. Intell. Res._ , 64: 243–252.

##  Appendix A General Math

See 1

###### Proof.

For every $x,y\in\mathcal{X}$, we have:

$\displaystyle|(f*\ell)(x)-(f*\ell)(y)|$
$\displaystyle=\bigg{|}\int_{\mathbb{R}^{n}}f(z)g(x-z)\mathrm{d}z-\int_{\mathbb{R}^{n}}f(z)g(y-z)\
\mathrm{d}z\bigg{|}$
$\displaystyle=\bigg{|}\int_{\mathbb{R}^{n}}f(z)(\ell(x-z)-\ell(y-z))\
\mathrm{d}z\bigg{|},$

since $\|f\|_{\infty}\leq M$, by assumption, we have that the result is
bounded by:

$M\int_{\mathbb{R}^{n}}\left|\ell(x-z)-\ell(y-z)\right|\mathrm{d}z=2M\mathrm{TV}(\mathcal{L}(x-\cdot)-\mathcal{L}(y-\cdot))\leq
2LM\|x-y\|_{2},$

where the last passage follows from the definition of $L$-TV-LC. ∎

######  Proposition 9.

Let $f$ be any univariate density function. Then, if $f$ is unimodal (i.e.
there is $x_{0}$ such that $f(x)$ is nondecreasing in $(-\infty,x_{0}]$ and
nonincreasing in $[x_{0},+\infty)$), $f$ is TV-LC with
$L=2\sup_{x\in\mathbb{R}}f(x)$.

###### Proof.

We first prove the result for functions $f$ that are Lipschitz with constant
$L_{f}$:

$\displaystyle\mathrm{TV}(f(\cdot+h),f(\cdot))$
$\displaystyle=\int_{\mathbb{R}}|f(x+h)-f(x)|\ \mathrm{d}x$
$\displaystyle=\int_{-\infty}^{x_{0}-h}|f(x+h)-f(x)|\
\mathrm{d}x+\int_{x_{0}-h}^{x_{0}}|f(x)-f(x+h)|\
\mathrm{d}x+\int_{x_{0}}^{\infty}|f(x)-f(x+h)|\ \mathrm{d}x.$

At this point, we know that being $f$ continuous there is one point in
$x\in[{x_{0}-h},{x_{0}})$ such that $f(x)=f(x+h)$. Therefore, by
Lipschitzness, in the whole interval $[{x_{0}-h},{x_{0}})$ we have
$|f(x)-f(x+h)|\leq 2L_{f}h$. Substituting in the previous formula, we have:

$\leq\int_{-\infty}^{x_{0}-h}|f(x+h)-f(x)|\
\mathrm{d}x+2L_{f}h^{2}+\int_{x_{0}}^{\infty}|f(x)-f(x+h)|\ \mathrm{d}x.$

Now, note that:

  * •

in the interval $(-\infty,x_{0}-h]$ the function $f(x+h)-f(x)$ is nonnegative;

  * •

in the interval $[x_{0},+\infty)$ the function $f(x+h)-f(x)$ is nonpositive.

Therefore, the previous integral writes:

$\displaystyle\int_{-\infty}^{x_{0}-h}f(x+h)-f(x)\
\mathrm{d}x+\varepsilon+\int_{x_{0}}^{\infty}f(x)-f(x+h)\ \mathrm{d}x$
$\displaystyle\leq 2L_{f}h^{2}+\int_{x_{0}}^{x_{0}-h}f(x)\
\mathrm{d}x+\int_{x_{0}+h}^{x_{0}}f(x)\ \mathrm{d}x\leq 2\sup fh+2L_{f}h^{2}.$

This being valid for every $h$, we can also write, by triangular inequality,
for every $K\in\mathbb{N}$:

$\displaystyle\mathrm{TV}(f(\cdot+h),f(\cdot))$
$\displaystyle\leq\sum_{k=0}^{K-1}\mathrm{TV}\bigg{(}f\Big{(}\cdot+h\frac{k}{K}\Big{)},f\Big{(}\cdot+h\frac{k+1}{K}\Big{)}\bigg{)}$
$\displaystyle\leq\sum_{k=0}^{K-1}2\sup
f\frac{h}{K}+2L_{f}\frac{h^{2}}{K^{2}}=2h\sup f+2L_{f}\frac{h^{2}}{K}.$

This entails, taking $K\to\infty$, that

$\mathrm{TV}(f(\cdot+h),f(\cdot))\leq 2h\sup f.$

Let us come to the general case. Let $N\in\mathbb{N}$. As Lipschitz functions
are dense in $L^{1}(\mathbb{R})$, taking $\varepsilon=\frac{h}{N}$, we know
that there is a Lipschitz function $f_{\varepsilon}$ satisfying the
unimodality and such that $\sup f=\sup f_{\varepsilon}$ such that

$\mathrm{TV}(f,f_{\varepsilon})<\varepsilon.$

Therefore,

$\mathrm{TV}(f(\cdot+h),f(\cdot))\leq
2\varepsilon+\mathrm{TV}(f_{\varepsilon}(\cdot+h),f_{\varepsilon}(\cdot))\leq
2\varepsilon+2h\sup f\leq 2h(\sup f+1/N).$

Taking $N\to\infty$, we get the result. ∎

##  Appendix B Negative Result

See 4

###### Proof.

In order to show the result we will use a similar MDP as the one defined in
Example LABEL:ese1 of the main paper. Then, we will take $\pi=\pi^{*}$, the
optimal policy, which is constant equal to zero (so $L_{\pi}=0$), and, as
$\pi^{\prime}$ a sequence of policies $\pi_{n}$ such that:

$\lim_{n\rightarrow+\infty}\frac{J^{*}-J^{\pi_{n}}}{\mathop{\mathbb{E}}_{s\sim
d^{\pi_{n}}}[\mathcal{W}(\pi^{*}(\cdot|s),\pi_{n}(\cdot|s))]}=+\infty.$

In this way, for any finite constant $C>0$, there will be an $n>0$ such that,
choosing $\pi^{\prime}=\pi_{n}$, we have the result. Let $\mathcal{M}$ an MDP
defined as follows:

  * •

$\mathcal{S}=[0,1]$;

  * •

$\mathcal{A}=[0,1]$;

  * •

The dynamic is deterministic: from every state $s\in\mathcal{S}$, performing
action $a\in\mathcal{A}$, we go to the state
$s^{\prime}=\mathrm{clip}(L_{p}(s+a),0,1)$. This means that
$p(\mathrm{d}s^{\prime}|s,a)=\delta_{\mathrm{clip}(L_{p}(s+a),0,1)}(\mathrm{d}s^{\prime})$;

  * •

$r(s,a)=-L_{r}s$ with $L_{r}>0$;

  * •

The initial state is $0$ (i.e., $\mu=\delta_{0}$);

  * •

The discount factor is $\gamma$.

Since the reward is always negative, the optimal policy $\pi^{*}$ is
identically zero, since is the only one allowing to remain in the origin.
Consider instead the sequence of policies for $n\in\mathbb{N}$, defined as:
$\pi_{n}(\cdot|s)=\delta_{1/n}(\cdot)$. Both $\pi^{*}$ and $\pi_{n}$ are
Lipschitz with $L_{\pi}=0$, and we have
$\mathcal{W}(\pi^{*}(\cdot|s),\pi_{n}(\cdot|s))=1/n$ in every state
$s\in\mathcal{S}$. Nonetheless, we can see that:

$V^{*}(0)=0\qquad V^{\pi_{n}}(0)\leq-L_{r}\sum_{k=0}^{+\infty}\gamma^{k}\
\mathrm{clip}\Big{(}\frac{L_{p}^{k}}{n},0,1\Big{)}.$

When $n\to\infty$, we have:

$\lim_{n\rightarrow+\infty}\frac{J^{*}-J^{\pi_{n}}}{\mathop{\mathbb{E}}_{s\sim
d^{\pi_{n}}}[\mathcal{W}(\pi^{*}(\cdot|s),\pi_{n}(\cdot|s))]}=-\lim_{n\rightarrow+\infty}\frac{V^{\pi_{n}}(0)}{1/n}\geq\lim_{n\rightarrow+\infty}nL_{r}\sum_{k=0}^{+\infty}\gamma^{k}\
\mathrm{clip}\Big{(}\frac{L_{p}^{k}}{n},0,1\Big{)}.$

Here, we can substitute $\delta\coloneqq 1/n$, finding

$\lim_{n\rightarrow+\infty}\frac{J^{*}-J^{\pi_{n}}}{\mathop{\mathbb{E}}_{s\sim
d^{\pi_{n}}}[\mathcal{W}(\pi^{*}(\cdot|s),\pi_{n}(\cdot|s))]}\geq\lim_{\delta\to
0^{+}}\frac{L_{r}\sum_{k=0}^{\infty}\gamma^{k}\ \mathrm{clip}\Big{(}\delta
L_{p}^{k},0,1\Big{)}}{\delta}=L_{r}\sum_{k=0}^{+\infty}\gamma^{k}L_{p}^{k}=\frac{L_{r}}{1-\gamma
L_{p}},$

which gives $+\infty$ for $L_{p}\geq 1/\gamma$. ∎

##  Appendix C Proofs with Hölder continuity

Before proving the main result, we need two technical lemmas.

######  Lemma 1.

Let $(\mathcal{X},d_{\mathcal{X}}),(\mathcal{Y},d_{\mathcal{Y}})$ be two
metric spaces, and $\\{f_{n}\\}_{n\in\mathbb{N}}$ be a sequence of functions
$\mathcal{X}\to\mathcal{Y}$ that are $(\alpha,L)-$HC such that
$\lim_{n\rightarrow+\infty}f_{n}=f$. Then, $f$ is $(\alpha,L)-$HC.

###### Proof.

Let $x,x^{\prime}\in\mathcal{X}$. Fix $\varepsilon>0$. Let:

$n_{0}\coloneqq\inf\\{n:\|f_{n}-f\|_{\infty}\coloneqq\sup_{x^{\prime\prime}\in\mathcal{X}}d_{\mathcal{Y}}(f_{n}(x^{\prime\prime}),f(x^{\prime\prime}))\leq\varepsilon
Ld_{\mathcal{X}}(x,x^{\prime})^{\alpha}\\}.$

Note that $n_{0}$ exists by definition. Then, we have:

$\displaystyle d_{\mathcal{Y}}(f(x),f(x^{\prime}))$ $\displaystyle\leq
d_{\mathcal{Y}}(f(x),f_{n_{0}}(x))+d_{\mathcal{Y}}(f_{n_{0}}(x),f_{n_{0}}(x^{\prime}))+d_{\mathcal{Y}}(f(x^{\prime}),f_{n_{0}}(x^{\prime}))$
$\displaystyle\leq
d_{\mathcal{Y}}(f_{n_{0}}(x),f_{n_{0}}(x^{\prime}))+2\varepsilon
Ld_{\mathcal{X}}(x,x^{\prime})^{\alpha}$
$\displaystyle\leq(2\varepsilon+1)Ld_{\mathcal{X}}(x,x^{\prime})^{\alpha}.$

Since this is valid for every $\varepsilon>0$, we have also
$d_{\mathcal{Y}}(f(x),f(x^{\prime}))\leq
Ld_{\mathcal{X}}(x,x^{\prime})^{\alpha}$, which is the thesis. ∎

######  Proposition 10.

Let $\mu,\nu\in\mathcal{P}{(\mathcal{X})}$ be two probability measures on a
metric space $(\mathcal{X},d_{\mathcal{X}})$. Then, for any $(\alpha,L)$-HC
function $f$, it holds that:

$\int_{\mathcal{X}}(\mu(\mathrm{d}x)-\nu(\mathrm{d}x))f(x)\leq L\
\mathcal{W}(\mu,\nu)^{\alpha}.$

For this proof, we thank an interesting Stack Exchange discussion (Yuval
2022).

###### Proof.

Let $K(\mu,\nu)$ denote the space of couplings of $\mu$ and $\nu$, i.e. Borel
probability measures on $\mathcal{X}\times\mathcal{X}$ that project to $\mu$
in the first coordinate and to $\nu$ in the second coordinate. Recall that:

$\mathcal{W}(\mu,\nu)=\inf_{\lambda\in
K(\mu,\nu)}\,\,\left\\{\int_{\mathcal{X}\times\mathcal{X}}d_{X}(x,y)\,\lambda(\mathrm{d}x,\mathrm{d}y)\right\\}\,.$

Suppose that $\forall x,y\in\mathcal{X}$ we have that $|f(x)-f(y)|\leq
Ld_{\mathcal{X}}(x,y)^{\alpha}$, where $0<\alpha<1$. Then for any $\lambda\in
K(\mu,\nu)$, we have:

$\displaystyle\left|\int_{\mathcal{X}}(\mu(\mathrm{d}x)-\nu(\mathrm{d}x))f(x)\right|$
$\displaystyle\leq\int_{\mathcal{X}\times\mathcal{X}}|f(x)-f(y)|\,\lambda(\mathrm{d}x,\mathrm{d}y)$
$\displaystyle\leq
L\int_{\mathcal{X}\times\mathcal{X}}d_{\mathcal{X}}(x,y)^{\alpha}\,\lambda(\mathrm{d}x,\mathrm{d}y)$
$\displaystyle\leq
L\left(\int_{\mathcal{X}\times\mathcal{X}}d_{X}(x,y)\,\lambda(\mathrm{d}x,\mathrm{d}y)\right)^{\alpha},$

where the last inequality is an application of Hölder’s inequality for the
functions $(x,y)\mapsto d_{X}(x,y)^{\alpha}$ and the constant $1$, with
exponents $p=1/\alpha$ and $q=1/(1-\alpha)$. Alternatively, the last
inequality in can be obtained from an application of Jensen’s inequality for
the convex function $t\mapsto t^{1/\alpha}$ on $[0,\infty)$. Taking infimum
over $\lambda\in K(\mu,\nu)$ gives:

$\left|\int_{\mathcal{X}}(\mu(\mathrm{d}x)-\nu(\mathrm{d}x))f(x)\right|\leq
LW(\mu,\nu)^{\alpha}\,,$

as required. ∎

See 6

###### Proof.

By definition, for every $s\in\mathcal{S}$:

$V^{\pi}(s)=\int_{\mathcal{A}}Q^{\pi}(s,a)\pi(\mathrm{d}a|s).$

Therefore, by introducing suitable Dirac deltas, we have for
$s,s^{\prime}\in\mathcal{S}$:

$\displaystyle\left|V^{\pi}(s)-V^{\pi}(s^{\prime})\right|$
$\displaystyle=\left|\int_{\mathcal{A}}Q^{\pi}(s,a)\pi(\mathrm{d}a|s)-\int_{\mathcal{A}}Q^{\pi}(s^{\prime},a)\pi(\mathrm{d}a|s^{\prime})\right|$
$\displaystyle=\bigg{|}\int_{\mathcal{A}}\int_{\mathcal{S}}Q^{\pi}(z,a)\delta_{s}(\mathrm{d}z)\pi(\mathrm{d}a|s)-\int_{\mathcal{A}}\int_{\mathcal{S}}Q^{\pi}(z,a)\delta_{s^{\prime}}(\mathrm{d}z)\pi(\mathrm{d}a|s^{\prime})\bigg{|}$
$\displaystyle=\bigg{|}\int_{\mathcal{A}}\int_{\mathcal{S}}\left(\delta_{s}(\mathrm{d}z)\pi(\mathrm{d}a|s)-\delta_{s^{\prime}}(\mathrm{d}z)\pi(\mathrm{d}a|s^{\prime})\right)Q^{\pi}(z,a)\bigg{|}.$

Now, thanks to Proposition 10, we have for $s,s^{\prime}\in\mathcal{S}$:

$\displaystyle\left|V^{\pi}(s)-V^{\pi}(s^{\prime})\right|\leq
L_{Q^{\pi},\alpha}\mathcal{W}\left(\delta_{s}(\cdot)\pi(\cdot|s),\delta_{s^{\prime}}(\cdot)\pi(\cdot|s^{\prime})\right)^{\alpha}\leq
L_{\alpha}(1+L_{\pi})^{\alpha}d_{\mathcal{S}}\left(s,s^{\prime}\right)^{\alpha},$

where the last passage follows from the following manipulation of the
Wasserstein distance:

$\displaystyle\mathcal{W}(\delta_{s}(\cdot)\pi(\cdot|s),\delta_{s^{\prime}}(\cdot)\pi(\cdot|s^{\prime}))\leq\mathcal{W}(\delta_{s}(\cdot)\pi(\cdot|s),\delta_{s}(\cdot)\pi(\cdot|s^{\prime}))+\mathcal{W}(\delta_{s}(\cdot)\pi(\cdot|s^{\prime}),\delta_{s^{\prime}}(\cdot)\pi(\cdot|s^{\prime})).$

Concerning the first term, we have:

$\displaystyle\mathcal{W}(\delta_{s}(\cdot)\pi(\cdot|s),\delta_{s}(\cdot)\pi(\cdot|s^{\prime}))$
$\displaystyle=\sup_{\|f\|_{L}\leq
1}\left|\int_{\mathcal{S}\times\mathcal{A}}\left(\delta_{s}(\mathrm{d}z)\pi(\mathrm{d}a|s)-\delta_{s}(\mathrm{d}z)\pi(\mathrm{d}a|s^{\prime})\right)f(z,a)\right|$
$\displaystyle=\sup_{\|f\|_{L}\leq
1}\left|\int_{\mathcal{A}}\left(\pi(\mathrm{d}a|s)-\pi(\mathrm{d}a|s^{\prime})\right)f(s,a)\right|$
$\displaystyle\leq\sup_{\|f\|_{L}\leq
1}\|f(s,\cdot)\|_{L}\cdot\mathcal{W}\left(\pi(\cdot|s),\pi(\cdot|s^{\prime})\right)$
$\displaystyle\leq\mathcal{W}\left(\pi(\cdot|s),\pi(\cdot|s^{\prime})\right)\leq
L_{\pi}d_{\mathcal{S}}\left(s,s^{\prime}\right),$

having observed that $\|f(s,\cdot)\|_{L}\leq\|f\|_{L}\leq 1$. Concerning the
second term, we have:

$\displaystyle\mathcal{W}(\delta_{s}(\cdot)\pi(\cdot|s^{\prime}),\delta_{s^{\prime}}(\cdot)\pi(\cdot|s^{\prime}))$
$\displaystyle=\sup_{\|f\|_{L}\leq
1}\left|\int_{\mathcal{S}\times\mathcal{A}}\left(\delta_{s}(\mathrm{d}z)\pi(\mathrm{d}a|s^{\prime})-\delta_{s^{\prime}}(\mathrm{d}z)\pi(\mathrm{d}a|s^{\prime})\right)f(z,a)\right|$
$\displaystyle=\sup_{\|f\|_{L}\leq
1}\left|\int_{\mathcal{S}}\left(\delta_{s}(\mathrm{d}z)-\delta_{s^{\prime}}(\mathrm{d}z)\right)\int_{\mathcal{A}}\pi(\mathrm{d}a|s^{\prime})f(z,a)\right|$
$\displaystyle\leq\sup_{\|f\|_{L}\leq
1}\left\|\int_{\mathcal{A}}\pi(\mathrm{d}a|s^{\prime})f(\cdot,a)\right\|_{L}\mathcal{W}\left(\delta_{s}(\cdot),\delta_{s^{\prime}}(\cdot)\right)$
$\displaystyle\leq d_{\mathcal{S}}\left(s,s^{\prime}\right),$

where we observed that the Lipschitz semi-norm is bounded by $1$ since for
$z,z^{\prime}\in\mathcal{S}$:

$\displaystyle\left|\int_{\mathcal{A}}\pi(\mathrm{d}a|s^{\prime})f(z,a)-\int_{\mathcal{A}}\pi(\mathrm{d}a|s^{\prime})f(z^{\prime},a)\right|\leq\int_{\mathcal{A}}\pi(\mathrm{d}a|s^{\prime})\left|f(z,a)-f(z^{\prime},a)\right|\leq
d_{\mathcal{S}}(z,z^{\prime}).$ (6)

∎

See 5

###### Proof.

Consider the following sequences of functions for $n\in\mathbb{N}$:

$\begin{cases}Q_{0}(s,a)=0\\\
Q_{n+1}(s,a)=r(s,a)+\gamma\int_{\mathcal{S}}V_{n}(s^{\prime})p(\mathrm{d}s^{\prime}|s,a)\end{cases},\qquad\begin{cases}V_{0}(s)=0\\\
V_{n+1}(s)=\int_{\mathcal{A}}Q_{n+1}(s,a)\pi(\mathrm{d}a|s)\end{cases}.$

We want to prove, by induction, that $Q_{n}$ is always
$(\alpha,L_{Q^{\pi},\alpha})-$HC. The base case $n=0$ is trivial, since a
constant function is Hölder continuous for every couple of parameters. Now,
let us suppose that $Q_{n}$ is $(\alpha,L_{Q^{\pi},\alpha})-$HC. Then, for
$s_{1},s_{2}\in\mathcal{S}$ and $a_{1},a_{2}\in\mathcal{A}$, we have:

$\displaystyle\left|Q_{n+1}(s_{1},a_{1})-Q_{n+1}(s_{2},a_{2})\right|$
$\displaystyle=\bigg{|}r(s_{1},a_{1})+\gamma\int_{\mathcal{S}}V_{n}(s^{\prime})p(\mathrm{d}s^{\prime}|s_{1},a_{1})-r(s_{2},a_{2})-\gamma\int_{\mathcal{S}}V_{n}(s^{\prime})p(\mathrm{d}s^{\prime}|s_{2},a_{2})\bigg{|}$
$\displaystyle=\bigg{|}r(s_{1},a_{1})-r(s_{2},a_{2})+\gamma\int_{\mathcal{S}}V_{n}(s^{\prime})\Big{(}p(\mathrm{d}s^{\prime}|s_{1},a_{1})-p(\mathrm{d}s^{\prime}|s_{2},a_{2})\Big{)}\bigg{|}$
$\displaystyle\leq|r(s_{1},a_{1})-r(s_{2},a_{2})|+\gamma\bigg{|}\int_{\mathcal{S}}V_{n}(s^{\prime})\Big{(}p(\mathrm{d}s^{\prime}|s_{1},a_{1})-p(\mathrm{d}s^{\prime}|s_{2},a_{2})\Big{)}\bigg{|}.$

Now, we consider one term at a time. Concerning the first term, recalling that
$0<\alpha\leq 1$ and that the reward function is $L_{r}$-LC, we have:

$\displaystyle|r(s_{1},a_{1})-r(s_{2},a_{2})|$ $\displaystyle\leq
L_{r}\left(d_{\mathcal{S}}(s_{1},s_{2})+d_{\mathcal{A}}(a_{1},a_{2})\right)$
$\displaystyle=L_{r}\left(d_{\mathcal{S}}(s_{1},s_{2})+d_{\mathcal{A}}(a_{1},a_{2})\right)^{\alpha}\left(d_{\mathcal{S}}(s_{1},s_{2})+d_{\mathcal{A}}(a_{1},a_{2})\right)^{1-\alpha}$
$\displaystyle\leq
L_{r}\left(\mathrm{diam}{(\mathcal{S})}+\mathrm{diam}{(\mathcal{A})}\right)^{1-\alpha}\left(d_{\mathcal{S}}(s_{1},s_{2})+d_{\mathcal{A}}(a_{1},a_{2})\right)^{\alpha},$

having observed that the distance between any pair of points is smaller than
the diameter of the corresponding set. Concerning the second term, we make use
of Proposition 6, this entails that $V_{n}$ is
$(\alpha,L_{Q^{\pi},\alpha}(L_{\pi}+1)^{\alpha})-$HC, Proposition 10, and
exploit that the transition model is $L_{p}$-LC:

$\displaystyle\bigg{|}\int_{\mathcal{S}}V_{n}(s^{\prime})\Big{(}p(\mathrm{d}s^{\prime}|s_{1},a_{1})-p(\mathrm{d}s^{\prime}|s_{2},a_{2})\Big{)}\bigg{|}$
$\displaystyle\leq
L_{V^{\pi},\alpha}\mathcal{W}\left(p(\cdot|s_{1},a_{1}),p(\cdot|s_{2},a_{2})\right)^{\alpha}$
(7) $\displaystyle\leq
L_{Q^{\pi}_{n},\alpha}\left(L_{p}(L_{\pi}+1)\right)^{\alpha}\left(d_{\mathcal{S}}(s_{1},s_{2})+d_{\mathcal{A}}(a_{1},a_{2})\right)^{\alpha}.$
(8)

Thus, we have the recurrence involving the Hölder constants:

$\displaystyle L_{Q^{\pi}_{0},\alpha}=0$ $\displaystyle
L_{Q^{\pi}_{n+1},\alpha}=L_{r}\left(\mathrm{diam}{(\mathcal{S})}+\mathrm{diam}{(\mathcal{A})}\right)^{1-\alpha}+\gamma
L_{Q^{\pi}_{n},\alpha}\left(L_{p}(L_{\pi}+1)\right)^{\alpha}.$

The sequence is convergent for $\left(L_{p}(L_{\pi}+1)\right)^{\alpha}<1$,
which leads to the condition:

$\displaystyle\alpha<\frac{-\log\gamma}{\log(L_{p}(L_{\pi}+1))}.$

Under such a condition, the limit $L_{Q^{\pi},\alpha}$ can be easily found as:

$\displaystyle
L_{Q^{\pi},\alpha}=L_{r}\left(\mathrm{diam}{(\mathcal{S})}+\mathrm{diam}{(\mathcal{A})}\right)^{1-\alpha}+\gamma
L_{Q^{\pi},\alpha}\left(L_{p}(L_{\pi}+1)\right)^{\alpha}\implies
L_{Q^{\pi},\alpha}=\frac{L_{r}\left(\mathrm{diam}{(\mathcal{S})}+\mathrm{diam}{(\mathcal{A})}\right)^{1-\alpha}}{1-\gamma\left(L_{p}(L_{\pi}+1)\right)^{\alpha}}.$

∎

See 7

###### Proof.

The first part of the theorem is obtained from the _performance difference
lemma_ (Kakade and Langford 2002), we have:

$\displaystyle J^{\pi_{E}}-J^{\pi_{I}}=$
$\displaystyle\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}\left[\mathop{\mathbb{E}}_{a\sim\pi_{E}(\cdot|s)}[A^{\pi_{I}}(s,a)]\right],$

where $A^{\pi_{I}}(s,a)=Q^{\pi_{I}}(s,a)-V^{\pi_{I}}(s)$ is the advantage
function. The inner expectation can be written as:

$\displaystyle\mathop{\mathbb{E}}_{a\sim\pi_{E}(\cdot|s)}[A^{\pi_{I}}(s,a)]$
$\displaystyle=\int_{A}Q^{\pi_{I}}(s,a)(\pi_{E}(\mathrm{d}a|s)-\pi_{I}(\mathrm{d}a|s))$
$\displaystyle\leq\sup_{s\in\mathcal{S}}L_{Q^{\pi_{I}}(s,\cdot),\alpha}\cdot\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))^{\alpha},$

where the inequality follows from Proposition 10. The result is obtained by
observing that $\sup_{s\in\mathcal{S}}L_{Q^{\pi_{I}}(s,\cdot),\alpha}\leq
L_{Q^{\pi_{I}},\alpha}$.

For what concerns the second part of the theorem, we build a counterexample.
Moreover, we will not focus on the constant, since it is very difficult to
estimate it correctly, and we will limit to verify that the bound on the
exponent $\alpha$ is tight.

As in the previous results, in order to show that the lower bound is tight, we
rely on the process defined in the examples of the main paper. Let
$\mathcal{M}$ an MDP defined as follows:

  * •

$\mathcal{S}=[0,1]$;

  * •

$\mathcal{A}=[0,1]$;

  * •

The dynamic is deterministic: from every state $s\in\mathcal{S}$, performing
action $a\in\mathcal{A}$, we go to the state
$s^{\prime}=\mathrm{clip}(L_{p}(s+a),0,1)$. This means that
$p(\mathrm{d}s^{\prime}|s,a)=\delta_{\mathrm{clip}(L_{p}(s+a),0,1)}(\mathrm{d}s^{\prime})$;

  * •

$r(s,a)=-L_{r}s$ with $L_{r}>0$;

  * •

The initial state is $0$ (i.e., $\mu=\delta_{0}$);

  * •

The discount factor is $\gamma$.

As before, the optimal policy $\pi^{*}$ is identically zero, since is the only
one allowing to stay in the origin. Consider instead the sequence of policies
$\pi_{n}(\cdot|s)=\delta_{1/n}(\cdot)$. Both $\pi^{*}$ and $\pi_{n}$ are
Lipschitz with $L_{\pi}=0$, and we have
$\mathcal{W}(\pi^{*}(\cdot|s),\pi_{n}(\cdot|s))=1/n$ in every state
$s\in[0,1]$. Nonetheless, we can see that:

$V^{*}(0)=0\qquad V^{\pi_{n}}(0)\leq-L_{r}\sum_{k=0}^{+\infty}\gamma^{k}\
\mathrm{clip}\left(\frac{L_{p}^{k}}{n},0,1\right).$

At this point, we want to evaluate the difference $J^{*}-J^{\pi_{n}}$ as $n$
increases:

$J^{*}-J^{\pi_{n}}\leq L_{r}\sum_{k=0}^{+\infty}\gamma^{k}\
\mathrm{clip}\Big{(}\frac{L_{p}^{k}}{n},0,1\Big{)}\overset{\delta=1/n}{=}L_{r}\sum_{k=0}^{+\infty}\gamma^{k}\
\mathrm{clip}\Big{(}\delta L_{p}^{k},0,1\Big{)}.$

At this point, we can see that:

$\mathrm{clip}\Big{(}\delta L_{p}^{k},0,1\Big{)}=\begin{cases}\delta
L_{p}^{k}&\text{if }k\leq-\frac{\log\delta}{\log L_{p}}\\\ 1&\text{if
}k>-\frac{\log\delta}{\log L_{p}}\end{cases}.$

Therefore, the previous sum can be rewritten as:

$\sum_{k=0}^{+\infty}\gamma^{k}\ \mathrm{clip}\Big{(}\delta
L_{p}^{k},0,1\Big{)}=\delta\sum_{k=0}^{\big{\lfloor}-\frac{\log\delta}{\log
L_{p}}\big{\rfloor}}\gamma^{k}L_{p}^{k}+\sum_{k=\big{\lfloor}-\frac{\log\delta}{\log
L_{p}}\big{\rfloor}+1}^{\infty}\gamma^{k}.$

Here, using the formula for geometric sums, we have:

$\displaystyle\sum_{k=0}^{+\infty}\gamma^{k}\ \mathrm{clip}\Big{(}\delta
L_{p}^{k},0,1\Big{)}$ $\displaystyle\leq\delta\frac{(\gamma
L_{p})^{-\frac{\log\delta}{\log L_{p}}}-1}{\gamma
L_{p}-1}+\frac{\gamma^{-\frac{\log\delta}{\log L_{p}}}}{1-\gamma}$
$\displaystyle=\delta\frac{\delta^{-1}\delta^{\frac{-\log\gamma}{\log
L_{p}}}-1}{\gamma L_{p}-1}+\frac{\delta^{\frac{\log\gamma}{\log
L_{p}}}}{1-\gamma}=\frac{\delta^{\frac{-\log\gamma}{\log L_{p}}}-1}{-\gamma
L_{p}-1}+\frac{\delta^{\frac{-\log\gamma}{\log L_{p}}}}{1-\gamma}.$

Since $\gamma^{-\frac{\log\delta}{\log
L_{p}}}=e^{-\log(\gamma)\frac{\log\delta}{\log
L_{p}}}=\delta^{\frac{-\log\gamma}{\log L_{p}}}$. This means that, as we have
$\mathcal{W}(\pi^{*}(\cdot|s),\pi_{n}(\cdot|s))=1/n=\delta$ in every state,
$\delta$ also corresponds to the Wasserstein error over the trajectory.
Therefore, Theorem 7 provides

$J^{*}-J^{\pi_{n}}\leq
C\delta^{\alpha}\qquad\text{with}\qquad\alpha\leq\overline{\alpha}\coloneqq\frac{-\log\gamma}{\log(L_{p}(1+L_{\pi}))}=\frac{-\log\gamma}{\log(L_{p})},$

while we have just found

$J^{*}-J^{\pi_{n}}\geq c\ \delta^{\frac{-\log\gamma}{\log L_{p}}},$

which makes the value of $\overline{\alpha}$ tight. ∎

##  Appendix D Results with Noise Injection

See 8

###### Proof.

By the performance difference lemma, we have

$J^{\pi_{E,\ell}}-J^{\pi_{I,\ell}}=\frac{1}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E,\ell}}}\Big{[}\mathop{\mathbb{E}}_{a\sim\pi_{E,\ell}(\cdot|s)}[Q^{\pi_{I,\ell}}(s,a)]-\mathop{\mathbb{E}}_{a\sim\pi_{I,\ell}(\cdot|s)}[Q^{\pi_{I,\ell}}(s,a)]\Big{]}.$

The inner part can be written as:

$\int_{A}Q^{\pi_{I,\ell}}(s,a)(\pi_{E,\ell}(a|s)-\pi_{I,\ell}(a|s))\ da.$

Here, by definition we have
$\pi_{E,\ell}(a|s)=\int_{A}\pi_{E}(a^{\prime}|s)\ell(a-a^{\prime})\
da^{\prime}$, and the same for $\pi_{I,\ell}$. Therefore, we find

$\displaystyle\int_{A}$ $\displaystyle
Q^{\pi_{I,\ell}}(s,a)(s,a)\bigg{(}\int_{A}\ell(a-a^{\prime})(\pi_{E}(a^{\prime}|s)-\pi_{I}(a^{\prime}|s))\
da^{\prime}\bigg{)}\ da$
$\displaystyle\qquad\quad=\int_{A}(\pi_{E}(a^{\prime}|s)-\pi_{I}(a^{\prime}|s))\bigg{(}\int_{A}Q^{\pi_{I,\ell}}(s,a)\ell(a-a^{\prime})\
da\bigg{)}\ da^{\prime}.$

Now, note that the inner term
$\int_{A}Q^{\pi_{I,\ell}}(s,a)\ell(a-a^{\prime})\ da$ is the convolution of a
function $Q^{\pi_{I,\ell}}(s,a)$ of $a$ which is bounded by $Q_{\max}$, and
the probability density of the noise, which satisfies Assumption 3 and is
therefore $L_{\ell}$ TV-Lipschitz. This allows us to apply Proposition 1,
having that the integral, as a function of $a$, is $L_{\ell}Q_{\max}-$LC. This
entails that

$\int_{A}(\pi_{E}(a^{\prime}|s)-\pi_{I}(a^{\prime}|s))\bigg{(}\int_{A}Q^{\pi_{I,\ell}}(s,a)\ell(a-a^{\prime})\
da\bigg{)}\ da^{\prime}\leq
2L_{\ell}Q_{\max}\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s)).$

Therefore, we get:

$J^{\pi_{E,\ell}}-J^{\pi_{I,\ell}}\leq\frac{2L_{\ell}Q_{\max}}{1-\gamma}\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E,\ell}}}[\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))],$

as required. ∎

##  Appendix E Miscellaneous results

######  Proposition 11.

Let $\mu,\nu$ two probability distributions over $\mathbb{R}^{n}$. Then,

$\mathbb{E}[\mu]-\mathbb{E}[\nu]\leq\mathcal{W}(\mu,\nu)$

###### Proof.

It is sufficient to consider that

$\mathbb{E}[\mu]-\mathbb{E}[\nu]=\int_{\mathbb{R}^{n}}x\mathrm{d}\mu(x)-\int_{\mathbb{R}^{n}}x\mathrm{d}\nu(x)=\int_{\mathbb{R}^{n}}x(\mathrm{d}\mu(x)-\mathrm{d}\nu(x))\leq\sup_{\|f\|_{L}\leq
1}\int_{\mathbb{R}^{n}}f(x)(\mathrm{d}\mu(x)-\mathrm{d}\nu(x))$

where the last term is precisely the definition of Wasserstein metric. ∎

This result is useful to see that the bound that we are able to obtain with
noise injection, that contains $\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))]$, is even better
than its ”noisy” counterpart $\mathop{\mathbb{E}}_{s\sim
d^{\pi_{E}}}[\mathcal{W}(\pi_{E,\ell}(\cdot|s),\pi_{I,\ell}(\cdot|s))]$ which
measures the difference between the noisy policies. This is because, if the
non noisy expert/imitator are deterministic, at fixed $s$,
$\pi_{E}(\cdot|s),\pi_{I}(\cdot|s)$ are Dirac’s delta, and so coincide with
their mean, while $\pi_{E,\ell}(\cdot|s),\pi_{I,\ell}(\cdot|s)$ are
distribution with mean $\pi_{E}(\cdot|s),\pi_{I}(\cdot|s)$ respectively.
Therefore, we have:

$\forall
s\in\mathcal{S}:\qquad\mathcal{W}(\pi_{E}(\cdot|s),\pi_{I}(\cdot|s))\leq\mathcal{W}(\pi_{E,\ell}(\cdot|s),\pi_{I,\ell}(\cdot|s)).$

##  Appendix F Details of the simulation

In the numerical simulation, we first trained some expert policy on the OpenAI
gym environments described in the main paper, and then we measured their
performance applying an i.i.d. Gaussian noise to the actions chosen by the
policies. Precisely, we used an $\mathbb{N}(0,\sigma I)$ noise with

$\sigma=0.0,\ 0.033,\ \dots,0.266,\ 0.3.$

for a total of ten equispaced values in $[0,0.3]$.

In order to evaluate the performance of the policies, we made the mean over
$40$ episodes for each value of $\sigma$, and then repeated for $20$ different
random seeds. Once collected the data, to generate the plot 3 we reported the
sample mean over the $20$ seeds and a $95\%$ confidence interval obtained with
the bootstrapping method.

###  F.1 Expert policy training

In order to use expert policies that are as standard as possible, we used
pretrained agents from the gihub repository https://github.com/DLR-RM/rl-
baselines3-zoo.

There, it is possible to find all the details about the hyperparameters.

###  F.2 Random number generation

The two possible source of randomness are given by the random generation of
the noise and by the intrinsic noise in the environments. When doing the
simulations, we simply set both the random seed of numpy and the one of gym to
$i=0,1,2,...19$ for each of the twenty experiments.

###  F.3 Device and computational power required

We ran the simulation on Python 3.7.9 on a device with CPU $1.80$ GHz and
$8.0$ GB of RAM.