review_iclr_bench/iclr_parsed/1zwleytEpYx.txt

# IMITATION LEARNING
## BY REINFORCEMENT LEARNING

**Kamil Ciosek**
Spotify
kamilc@spotify.com

ABSTRACT

Imitation learning algorithms learn a policy from demonstrations of expert behavior.
We show that, for deterministic experts, imitation learning can be done by reduction
to reinforcement learning with a stationary reward. Our theoretical analysis both
certifies the recovery of expert reward and bounds the total variation distance
between the expert and the imitation learner, showing a link to adversarial imitation
learning. We conduct experiments which confirm that our reduction works well in
practice for continuous control tasks.

1 INTRODUCTION

Typically, reinforcement learning (RL) assumes access to a pre-specified reward and then learns
a policy maximizing the expected average of this reward along a trajectory. However, specifying
rewards is difficult for many practical tasks (Atkeson & Schaal, 1997; Zhang et al., 2018; Ibarz et al.,
2018). In such cases, it is convenient to instead perform Imitation Learning (IL), learning a policy
from expert demonstrations.

There are two major categories of Imitation Learning algorithms: behavioral cloning and inverse
reinforcement learning. Behavioral cloning learns the policy by supervised learning on expert data,
but is not robust to training errors, failing in settings where expert data is limited (Ross & Bagnell,
2010). Inverse reinforcement learning (IRL) achieves improved performance on limited data by
constructing reward signals and calling an RL oracle to maximize these rewards (Ng et al., 2000).

The most versatile IRL method is adversarial IL (Ho & Ermon, 2016; Li et al., 2017; Ghasemipour
et al., 2020), which minimizes a divergence between the distribution of data produced by the agent
and provided by the expert. Adversarial IL learns a representation and a policy simultaneously by
using a non-stationary reward obtained from a discriminator network. However, training adversarial
IL combines two components which are hard to stabilize: a discriminator network, akin to the one
used in GANs, as well as a policy, typically learned with an RL algorithm with actor and critic
networks. This complexity makes the training process very brittle.

There is a clear need for imitation learning algorithms that are simpler and easier to deploy. To
address this need, Wang et al. (2019) proposed to reduce imitation learning to a single instance of
reinforcement learning problem, where reward is defined to be one for state-action pairs from the
expert trajectory and zero for other state-action pairs. A closely related, but not identical, algorithm
has been proposed by Reddy et al. (2020) (we describe the differences in Section 5). However, while
empirical performance of these approaches has been good, they enjoy no performance guarantees at
all, even in the asymptotic setting where expert data is infinite.

**Contributions** We fill in this missing justification for this algorithm, providing the needed theoretical analysis. Specifically, in Sections 3 and 4, we show a total variation bound between the expert
policy and the imitation policy, providing a high-probability performance guarantee for a finite dataset
of expert data and linking the reduction to adversarial imitation learning algorithms. For stochastic
experts, we describe how the reduction fails, completing the analysis. Moreover, in Section 6, we
empirically evaluate the performance of the reduction as the amount of available expert data varies.


-----

2 PRELIMINARIES

**Markov Decision Process** An average-reward Markov Decision Process (Puterman, 2014; Feinberg & Shwartz, 2012) is a tuple (S, A, T, R, s1), where S is a state space, A is the action space,
_T : S_ _A_ _P_ (S) is the transition model, R : S _A_ [0, 1] is a bounded reward function and s1
_×_ _→_ _×_ _→_
is the initial state. Here, we write P (X) to denote probability distributions over a set X. A stationary
policy π : S → _P_ (A) maps environment states to distributions over actions. A policy π induces a
Markov chain Pπ over the states. In the theoretical part of the paper, we treat MDPs with finite state
and action spaces. Given the starting state s1 of the MDP, and a policy π, the limiting distribution
over states is defined as


_ρ[π]S_ [=][ 1][(][s][1][)][⊤] [lim]
_N_ _→∞_


_Pπ[i]_ _[,]_ (1)
_i=0_

X


where 1(s1) denotes the indicator vector. We adopt the convention that the subscript S indicates a
distribution over states and no subscript indicates a distribution over state-action pairs. We denote
_ρ[π](s, a) = ρ[π]S[(][s][)][π][(][a][|][s][)][. While the limit in equation 1 is guaranteed to exist for all finite MDPs]_
(Puterman, 2014), without requiring ergodicity, in this paper we consider policies that induce ergodic
chains. Correspondingly, our notation for ρ[π]S [and][ ρ][π][ does not include the dependence on the initial]
state. The expected per-step reward of π is defined as

_V_ _[π]_ = lim (2)
_N_ _→∞_ [E][π][ [][J][N] _[/N][ |][ s][1][] =][ E][ρ][π]_ [[][R][(][s, a][)]][,]

where JN = _t=1_ _[R][(][s][t][, a][t][)][ is the total return. In this paper we consider undiscounted MDPs]_
because they are enough to model the essential properties of the imitation learning problem while
being conceptually simpler than discounted MDPs. However, we believe that similar results could be

[P][N]
obtained for discounted MDPs.

**Expert Dataset** Assume that the expert follows an ergodic policy πE. Denote the corresponding
distribution over expert state-action pairs as ρ[E](s, a) = ρ[π][E] (s, a), which does not depend on
the initial state by ergodicity. Consider a finite trajectory s1, a1, s2, a2, . . ., sN _, aN_ . Denote by
_ρˆ(s, a) =_ _N1_ _Nt=1_ [1][ {][(][s, a][) = (][s][t][, a][t][)][}][ the histogram (empirical distribution) of data seen along]

this trajectory and denote byP ˆρS(s) = _N1_ _Nt=1_ [1][ {][s][ =][ s][t][}][ the corresponding histogram over the]

states. Denote by D the support of ˆρ, i.e. the set of state-action pairs visited by the expert.
P

**Total Variation** Consider probability distributions defined on a discrete set X. The total variation
distance between distributions is defined as

_∥ρ1 −_ _ρ2∥TV = supM_ _X_ _|ρ1(M_ ) − _ρ2(M_ )|. (3)
_⊆_

In our application, the set X is either the set of MDP states S or the set of state state-action pairs
_S × A. Below, we restate in our notation standard results about the total variation distance. See_
Appendix D for proofs.

**Lemma 1. If Eρ1** [v] − Eρ2 [v] ≤ _ϵ for any vector v ∈_ [0, 1][|][X][|], then ∥ρ1 − _ρ2∥TV ≤_ _ϵ._

**Lemma 2. If ∥ρ1 −** _ρ2∥TV ≤_ _ϵ, then Eρ1_ [v] − Eρ2 [v] ≤ 2ϵ for any vector v ∈ [0, 1][|][X][|].

**Imitation Learning** Learning to imitate means obtaining a policy that mimics expert behavior.
This can be formalized in two ways. First, we can seek an imitation policy πI which obtains a
expected per-step reward that is ϵ-close to the expert on any reward signal bounded in the interval

[0, 1]. Denote the limiting distribution of state-action tuples generated by the imitation learner with
_ρ[I]_ (s, a). Formally, we want to satisfy

_∀R : S × A →_ [0, 1], EρE [R] − EρI [R] ≤ _ϵ,_ (4)

where ϵ is a small constant. Second, we can seek to ensure that the distributions of state-action pairs
generated by the expert and the imitation learner are similar (Ho & Ermon, 2016; Finn et al., 2016).
In particular, if we measure the divergence between distributions with total variation, we want to
ensure

_∥ρ[E]_ _−_ _ρ[I]_ _∥TV ≤_ _ϵ._ (5)


-----

**Algorithm 1 Imitation Learning by Reinforcement Learning (ILR)**

**Require: expert dataset D, ENVIRONMENT (without access to extrinsic reward)**

_Rint(s, a) ←_ 1 {(s, a) ∈ _D}_
_πI ←_ RL-SOLVER(ENVIRONMENT, Rint)

Lemmas 1 and 2 show that the equations 4 and 5 are closely related. In other words, attaining expected
per-step reward close to the expert’s is the same (up to a multiplicative constant) as closeness in total
variation between the state-action distribution of the expert and the imitation learner. We provide
further background on adversarial imitation learning and other divergences in Section 5.

**Markov Chains** When coupled with the dynamics of the MDP, a policy induces a Markov chain,
In this paper, we focus our attention on chains which are irreducible and aperiodic. Crucially, such
chains approach the stationary distribution at an exponential rate. In the following Lemma, we
formalize this insight. The proof is given in Appendix D.
**Lemma 3. Denote with PE the Markov chain induced by an irreducible and aperiodic expert policy.**
_The mixing time of the chain τmix, defined as the smallest t so that maxs[′]_ 1(s[′])[⊤]PE[t] _S_ 4
_∥_ _[−]_ _[ρ][E][∥][TV][ ≤]_ [1]

_is bounded. Moreover, for any probability distribution p1, we have_ _t=0_ _[∥][p]1[⊤][P]E[ t]_ _[−]_ _[ρ]S[E][∥][TV][ ≤]_ [2][τ][mix][.]

3 IMITATION LEARNING BY REINFORCEMENT LEARNING[P][∞]

**Algorithm** To perform imitation learning, we first obtain an expert dataset D and construct an
intrinsic reward

_Rint(s, a) = 1 {(s, a) ∈_ _D} ._ (6)

We can then use any RL algorithm to solve for this reward. We note that for finite MDPs equation 6
exactly matches the algorithm proposed by Wang et al. (2019) as a heuristic. The reward defined in
equation 6 is intrinsic, meaning we construct it artificially in order to elicit a certain behavior from
the agent. This is in contrast to an extrinsic reward, which is what the agent gathers in the real world
and what we want to recover. We will learn in Proposition 1 that the two are in fact closely related
and solving for the intrinsic reward guarantees recovery of the extrinsic reward.

**Guarantee on Imitation Policy** The main focus of the paper lies on showing theoretical properties
of the imitation policy obtained when solving for the reward signal defined in equation 6. Our formal
guarantees hold under three assumptions.
**Assumption 1. The expert policy is deterministic.**
**Assumption 2. The expert policy induces an irreducible and aperiodic Markov chain.**
**Assumption 3. The imitation learner policy induces an irreducible and aperiodic Markov chain.**

Assumption 1 is critical for our proof to go through and cannot be relaxed. It is also essential to
rationalize the approach of Wang et al. (2019). In fact, no reduction involving a single call to an RL
solver with stationary reward can exist for stochastic experts since for any MDP there is always an
optimal policy which is deterministic. Assumptions 2 and 3 could in principle be relaxed, to allow
for periodic chains, but it would complicate the reasoning, which we wanted to avoid. We note that
we only interact with the expert policy via a finite dataset of N samples.

Our main contribution is Proposition 1, in which we quantify the performance of our imitation learner.
We state it below and prove it in Section 4.
**Proposition 1. Consider an imitation learner trained on a dataset of size N** _, which attains the_
_limiting distribution of state-action pairs ρ[I]_ _. Under Assumptions 1, 2 and 3, given that we have_
2
_N_ max 800 _S_ _, 450 log_ _δ_ _τmix[3]_ _[η][−][2][ expert demonstrations, with probability at least][ 1][ −]_ _[δ][,]_
_≥_ _|_ _|_

_the imitation learner attains total variation distance from the expert of at most_

  


_∥ρ[E]_ _−_ _ρ[I]_ _∥TV ≤_ _η._ (7)

_The constant τmix is the mixing time of the expert policy and has been defined in Section 2. Moreover,_
_with the same probability, for any bounded extrinsic reward function R, the imitation learner achieves_


-----

_expected per-step extrinsic reward of at least_
EρI [R] ≥ EρE [R] − _η._ (8)

Proposition 1 shows that the policy learned by imitation learner satisfies two important desiderata: we
can guarantee both the closeness of the generated state-action distribution to the expert distribution
as well as recovery of expert reward. Moreover, the total variation bound in equation 7 links the
obtained policy to adversarial imitation learning algorithms. We describe this link in more detail in
Section 5.

4 PROOF

**Structure of Results** We begin by showing a result about mixing in Markov chains in Section 4.1.
We then give our proof, which has two main parts. In the first part, in Section 4.2, we show that it
is possible to achieve a high expected per-step intrinsic reward defined in equation 6. In the second
part, in Section 4.3, we show that, achieving a large expected per-step intrinsic reward guarantees a
large expected per-step extrinsic reward for any extrinsic reward bounded in [0, 1]. In Section 4.4, we
combine these results and prove Proposition 1.

4.1 MIXING IN MARKOV CHAINS

We now show a lemma that quantifies how fast the histogram approaches the stationary distribution. The proof of the lemma relies on standard results about the Total Variation distance between
probability distributions as well as generic results about mixing in MDPs, developed by Paulin (2015).
**Lemma 4. The total variation distance between the expert distribution and the expert histogram ˆρ**
_based on N samples can be bounded as_

8 _S_ _τmix_

_ρ[E]_ _ρˆ_ TV _ϵ +_ _|_ _|_ (9)
_∥_ _−_ _∥_ _≤_ r _N_

_with probability at least 1_ 2 exp 4.5τmix _(where the probability space is defined by the process_
_−_ _−_ _[ϵ][2][N]_

_generating the expert histogram)._ n o

_Proof. We first prove the statement for histograms over the states. Recall the notation ˆρS =_

_N1_ _Nt=1_ [1][ {][s][t][ =][ s][}][. Recall that we denote the stationary distribution (over states) of the Markov]
chain induced by the expert with ρ[E]S [.]
P

First, instantiating Proposition 3.16 of Paulin (2015), we obtain

4ρ[E]S [(][s][)]

EρˆS [[][∥][ρ][E]S _[−]_ _ρ[ˆ]S∥TV] ≤_ [P]s [min] _Nγps_ _[, ρ]S[E][(][s][)]_ _,_

q 

where γps is pseudo spectral gap of the chain. Re-write the right-hand side as

_s_ [min] 4Nγρ[E]S [(]ps[s][)] _[, ρ]S[E][(][s][)]_ _≤_ [P]s 4Nγρ[E]S [(]ps[s][)] _≤_ _Nγ4|Sps|_ _[,]_
q  q q

where the last inequality follows from the Cauchy-Schwartz inequality. Using equation 3.9 of PaulinP
(2015), we have γps ≥ 2τ1mix [. Taken together, this gives]

EρˆS [[][∥][ρ][E]S _ρS_ TV] 8|SN|τmix _._ (10)

_[−]_ [ˆ] _∥_ _≤_
q

Instantiating Proposition 2.18 of Paulin (2015), we obtain

_P_ (|∥ρ[E]S _[−]_ _ρ[ˆ]S∥TV −_ EρˆS [[][∥][ρ][E]S _[−]_ _ρ[ˆ]S∥TV]| ≥_ _ϵ) ≤_ 2 exp _−_ 4.[ϵ]5[2]τ[N]mix _._ (11)
 

Combining equations 10 and 11, we obtain


2 exp
_≤_ _−_ 4.[ϵ]5[2]τ[N]mix



8|S|τmix


_ρ[E]S_ _ρS_ TV _ϵ +_
_|∥_ _[−]_ [ˆ] _∥_ _≥_


Since the expert policy is deterministic, the total variation distance between the distributions of
state-action tuples and states is the same, i.e. _ρ[E]S_ _ρS_ TV = _ρ[E]_ _ρˆ_ TV.
_∥_ _[−]_ [ˆ] _∥_ _∥_ _−_ _∥_


-----

4.2 HIGH EXPECTED INTRINSIC PER-STEP REWARD IS ACHIEVABLE

We now want to show that it is possible for the imitation learner to attain a large intrinsic reward.
Informally, the proof asks what intrinsic reward the expert would have achieved. We then conclude
that a learner specifically optimizing the intrinsic reward will obtain at least as much.
**Lemma 5. Generating an expert histogram with N points, with probability at least 1 −**
2 exp 4.5τmix _, we obtain a dataset such that a policy πI maximizing the intrinsic reward_
_−_ _[ϵ][2][N]_

_Rint(s, an_ ) = 1((os, a) _D) satisfies EρI_ [Rint] 1 _ϵ_ 8|SN|τmix _, where we used the shorthand_
_∈_ _≥_ _−_ _−_

_notation ρ[I]_ = ρ[π][I] _to denote the state-action distribution ofq πI_ _._


_Proof. We invoke Lemma 4 obtaining_ _ρ[E]_ _ρˆ_ TV _ϵ +_ 8|SN|τmix with probability as in the
_∥_ _−_ _∥_ _≤_

statement of the lemma. First, we prove q
_s,a_ _[ρ][E][(][s, a][)][1][ {]ρ[ˆ](s, a) = 0} ≤_ _ϵ +_ 8|SN|τmix _,_ (12)
q

by setting ρ1 = ρ[E], ρ2 = ˆPρ and M = {(s, a) : ˆρ(s, a) = 0} in equation 3.

Combining

1 = _s,a_ _[ρ][E][(][s, a][) =][ P]s,a_ _[ρ][E][(][s, a][)][1][ {]ρ[ˆ](s, a) = 0} +_ _s,a_ _[ρ][E][(][s, a][)][1][ {]ρ[ˆ](s, a) > 0}_ (13)

and equation 12, we obtain

[P] [P]

_s,a_ _[ρ][E][(][s, a][)][1][ {]ρ[ˆ](s, a) > 0} ≥_ 1 − _ϵ −_ 8|SN|τmix _,_ (14)
q

which means that the expert policy achieves expected per-step intrinsic reward of at leastP 1 _ϵ_
_−_ _−_

8|SN|τmix . This lower bounds the expected per-step reward obtained by the optimal policy.

q

4.3 MAXIMIZING INTRINSIC REWARD LEADS TO HIGH PER-STEP EXTRINSIC REWARD


We now aim to prove that the intrinsic and extrinsic rewards are connected, i.e. maximizing the
intrinsic reward leads to a large expected per-step extrinsic reward. The proofs in this section are
based on the insight that, by construction of intrinsic reward in equation 6, attaining intrinsic reward
of one in a given state implies agreement with the expert. In the following Lemma, we quantify the
outcome of achieving such agreement for ℓ consecutive steps.
**Lemma 6. Assume an agent traverses a sequence of ℓ** _state-action pairs, in a way consistent with_
_the expert policy. Denote the expert’s expected extrinsic per-step reward with EρE_ [R]. Denote
_by ˜ρt[p][1]_ [(][s, a][) = (][p]1[⊤][P]E[ t] [)(][s][)][π][E][(][a][|][s][)][ the expected state-action occupancy at time][ t][, starting in state]
_distribution p1. The per-step extrinsic reward_ _V[˜]p[ℓ]1_ _[of the agent in expectation over realizations of the]_
_sequence satisfies_

_V˜p[ℓ]1_ [=][ P]s,a _ℓt=0−1_ 1ℓ _ρ[˜][p]t_ [1] [(][s, a][)] _R(s, a)_ EρE [R] _ℓ_ _[.]_ (15)

_≥_ _−_ [4][τ][mix]
P  

_Proof. Invoking Lemma 2, we have that EρE_ [R] − Eρ˜[p]t [1] [[][R][]][ ≤] [2][∥]ρ[˜][p]t [1] _−_ _ρ[E]∥TV for any timestep_
_t. In other words, the expected per-step reward obtained in step t of the sequence is at least_
EρE [R] 2 _ρ˜[p]t_ [1]
_−_ _∥_ _[−]_ _[ρ][E][∥][TV][. The per-step reward in the sequence is at least]_

_V˜p[ℓ]1_ _ℓ_ _ℓi=0−1[(][E][ρ][E]_ [[][R][]][ −] [2][∥]ρ[˜][p]i [1] _ℓ_ _ℓi=0−1_ _ρ[p]i_ [1]

_[≥]_ [1] _[−]_ _[ρ][E][∥][TV][) =][ E][ρ][E]_ [[][R][]][ −] [2] _[∥][˜]_ _[−]_ _[ρ][E][∥][TV]_

P EρE [R] _ℓ_ P∞i=0 _ρ[p]i_ [1]

_≥_ _−_ [2] _[∥][˜]_ _[−]_ _[ρ][E][∥][TV]_

P

Invoking Lemma 3, we have thatdeterministic, distances between distributions of states and state-action pairs are the same. We thust=0 _[∥][p]1[⊤][P][ t]E_ _[−]_ _[ρ]S[E][∥][TV][ ≤]_ [2][τ][mix][. Since the expert policy is]
get _V[˜]p[ℓ]1_ _ρ[E]_ [[][R][]][ −] [4][τ]ℓ[mix] [.] [P][∞]

_[≥]_ [E]


-----

In Lemma 6, we have shown that, on average, agreeing with the expert for a number of steps
guarantees a certain level of extrinsic reward. We will now use this result to guarantee extrinsic
reward obtained over a long trajectory.

**Lemma 7. For any extrinsic reward signal R bounded in [0, 1], an imitation learner which attains**
_expected per-step intrinsic reward of EρI_ [Rint] = 1 − _κ also attains extrinsic per-step reward of at_
_least_
EρI [R] ≥ (1 − _κ)(EρE_ [R]) − 4τmixκ,

_with probability one, where EρE_ [R] is the expected per-step extrinsic reward of the expert.

We provide the proof in Appendix D.

4.4 BRINGING THE PIECES TOGETHER

We now show how Lemma 5 and Lemma 7 can be combined to obtain Proposition 1 (stated in Section
3).

2
_Proof of Proposition 1. We use the assumption that N_ max 800 _S_ _, 450 log_ _δ_ _τmix[3]_ _[η][−][2][.]_
_≥_ _|_ _|_

Since τmix is either zero or τmix 1, this implies
_≥_   


2
_N_ max 32 _S_ _τmix (1 + 4τmix)[2]_ _η[−][2], log_ 18τmix (1 + 4τmix)[2] _η[−][2]_ _._ (16)
_≥_ _|_ _|_ _δ_
   

We will instantiate Lemma 5 with


_η_

_._ (17)
2 + 8τmix


_ϵ =_


2 2
Equations 16 and 17 imply that N log _δ_ 18τmix (1 + 4τmix)[2] _η[−][2]_ = log _δ_ 4.5τmixϵ[−][2]. We can

2 _Nϵ[2]_ _≥_
rewrite this as log _δ_ _≤_ 4.5τmix [, which implies] 
 _[ −]_ 4.[ϵ]5[2]τ[N]mix _[≤]_ [log][ δ]2 [. This implies that] 

 


_δ_ 2 exp _._ (18)
_≥_ _−_ 4.[ϵ]5[2]τ[N]mix
 

Moreover, using equation 16 again, we have that N ≥ 32|S|τmix (1 + 4τmix)[2] _η[−][2]. This is equivalent_

to [8][|][S]N[|][τ][mix] _≤_ [1]4 (1+4ητ[2]mix)[2][, or] 8|SN|τmix _≤_ 2[1] 1+4ητmix [. Using equation 17, we obtain][ ϵ][ +] 8|SN|τmix _≤_

q q


8|S|τmix


1+4ητmix [, equivalent to] _ϵ +_



(1 + 4τmix) ≤ _η. Rewriting this gives_


_κ (1 + 4τmix) ≤_ _η,_ (19)

8|S|τmix .


where we use the notation κ = ϵ +


We first show equation 8, which states that we are able to recover expected per-step expert reward.
Invoking Lemma 5 and using equation 18, we have that it is possible for the imitation learner to
achieve per-step expected intrinsic reward of at least 1 − _κ with probability 1 −_ _δ. Invoking Lemma_
7, this implies achieving extrinsic reward of at least

EρI [R] ≥ EρE [R](1 − _κ) −_ 4τmixκ.

This implies

EρE [R] − EρI [R] ≤ EρE [R] − EρE [R](1 − _κ) + 4τmixκ_

= κEρE [R] + 4τmixκ ≤ _κ + 4τmixκ ≤_ _η,_

where the last inequality follows from equation 19. Since this statement holds for any extrinsic reward
signal R, we obtain the total variation bound by invoking Lemma 1, getting ∥ρ[E] _−_ _ρ[I]_ _∥TV ≤_ _η._


-----

5 RELATED WORK

**Behavioral Cloning** The simplest way of performing imitation learning is to learn a policy by
fitting a Maximum Likelihood model on the expert dataset. While such ‘behavioral cloning’ is easy
to implement, it does not take into account the sequential nature of the Markov Decision Process,
leading to catastrophic compounding of errors (Ross & Bagnell, 2010). In practice, the performance
of policies obtained with behavioral cloning is highly dependent on the amount of available data.
In contrast, our reduction avoids the problem faced by behavioral cloning and provably works with
limited expert data.

**Apprenticeship Learning** Apprenticeship Learning (Abbeel & Ng, 2004) assumes the existence
of a pre-learned linear representation for rewards and then proceeds in multiple iterations. In each
iteration, the algorithm first computes an intrinsic reward signal and then calls an RL solver to obtain
a policy. Our algorithm also uses an RL solver, but unlike Apprenticeship Learning, we only call it
once.

**Adversarial IL** Modern adversarial IL algorithms (Ho & Ermon, 2016; Finn et al., 2016; Li et al.,
2017; Sun et al., 2019) remove the requirement to provide a representation by learning it online.
They work by minimizing a divergence between the expert state-action distribution and the one
generated by the RL agent. For example, the GAIL algorithm (Ho & Ermon, 2016) minimizes the
Jensen-Shannon divergence. It can be related to the total variation objective of equation 5 in two ways.
First, the TV and JS divergences obey 2 _DJS(ρ[E], ρ[I]_ ) ≥∥ρ[E] _−_ _ρ[I]_ _∥TV, so that DJS(ρ[E], ρ[I]_ ) ≤ _ϵ[′]_

implies _ρ[E]_ _ρ[I]_ TV 2√ϵ[′]. This means that GAIL indirectly minimizes the total variation distance.

Second, we havesufficiently large sizes of the expert dataset, this means that it also minimizes the GAIL objective. ∥ _−_ _∥ ∥ρ[E] ≤−_ _ρ[I]_ _∥TV ≥_ _DJS(ρ[E]p, ρ[I]_ ). Since our algorithm minimizes Total Variation for
Both of these properties imply that our reduction converges to a fixpoint with similar properties
as GAIL’s. This has huge practical significance because our algorithm does not need to train a
discriminator.

Another adversarial algorithm, InfoGAIL (Li et al., 2017) minimizes the 1-Wasserstein divergence,
which obeys EρE [RL] − EρI [RL] ≤ _DW1_ (ρ[E], ρ[I] ) for any reward function RL Lipschitz in the L1
norm. This is similar to the property defined by equation 4, implied by our Proposition 1, except
we guarantee closeness of expected per-step reward for any bounded reward function as opposed to
Lipschitz-continuous functions.

**Random Expert Distillation** Wang et al. (2019) propose an algorithm which, for finite MDPs,
is the same as ours. However, they do not justify the properties of the imitation policy formally.
Our work can be thought of as complementary. While Wang et al. (2019) conducted an empirical
evaluation using sophisticated support estimators, we fill in the missing theory. Moreover, while our
empirical evaluation is smaller in scope, we attempt to be more complete, demonstrating convergence
in cases where only partial trajectories are given.


**The SQIL heuristic** SQIL (Reddy et al., 2020) is close to our work in that it proposes a similar
algorithm. At any given time, SQIL performs off-policy reinforcement learning on a dataset sampled
from the mixture distribution [1]2 [(][ρ][E][(][s, a][) +][ ρ][RL][(][s, a][))][, where][ ρ][E][(][s, a][)][ is the distribution of data]

under the expert. Since the rewards are one for the data sampled from ρ[E] and zero for stateaction pairs sampled from ρRL, the expected reward obtained at a state-action pair (s, a) is given by
_ρ[E]_ (s,a)

_ρ[E]_ (s,a)+ρRL(s,a) [, which is non-stationary and varies between zero and one. The benefit of SQIL is]
that it does not require a support estimate. However, while SQIL has demonstrated good empirical
performance, it does not come with a theoretical guarantee of any kind, making it hard to deploy in
settings where we need a theoretical certificate of policy quality.

**Expert Feedback Loop** IL algorithms such as SMILe (Ross & Bagnell, 2010) and DAGGER
(Ross et al., 2011) assume the ability to query the expert for more data. While this makes it easier to
reproduce expert behavior, the ability to execute queries is not always available in realistic scenarios.
Our reduction is one-off, and does not need to execute expert queries to obtain more data.


-----

) expert ( ) ILR ( ) BC ( ) GAIL ( ) GMMIL ( ) SQIL


2500

2000

1500

1000

500

0

2 9 2 7 2 5 2 3 2 1 2[1] 2[3] 2[5]


2500

2000

1500

1000

500

0

2 9 2 7 2 5 2 3 2 1 2[1] 2[3] 2[5]


2000

1500

1000

500

0

2 9 2 7 2 5 2 3 2 1 2[1] 2[3] 2[5]


2000

1000

0

1000

2 9 2 7 2 5 2 3 2 1 2[1] 2[3] 2[5]


(a) Hopper


(b) Ant


(c) Walker


(d) HalfCheetah


Figure 1: Extrinsic return of imitation learners as a function of the number of episodes of demonstration data. For comparison, we also show expert performance. Confidence bars denote one standard
error.

6 EXPERIMENTS

We investigate the performance of our reduction on continuous control tasks. Because Wang et al.
(2019) have already conducted an extensive evaluation of various ways of estimating the support for
the expert distribution, we do not attempt this. Instead, we focus on two aspects: the amount of expert
data needed to achieve good imitation and the relationship between intrinsic and extrinsic return.

**Continuous Relaxation** In order to adapt the discrete reduction to a continuous state-action space,
we define the reward as RI[′] [(][s, a][) = 1][ −] [min][(][s][′][,a][′][)][∈][D] _[d][L]2_ [((][s, a][)][,][ (][s][′][, a][′][))][2][. To see how this is related]
to the reward in equation 6, consider a scaled version of the binary reward used in the theoretical
analysis which ranges from 1 _L to 1 instead of from 0 to 1, where L is the L2-diameter of the_
_−_
state-action space. Then the relaxed reward is an upper bound on the scaled theoretical reward. Since
optimizing this upper bound is different from optimizing the reward in equation 6 directly, we can no
longer theoretically claim the recovery of expert reward (as in Lemma 7). However, this property
still holds in practice, as verified below. In settings where such reduction is not feasible, the random
expert distillation approach can be used, which Wang et al. (2019) have demonstrated can work quite
well and Burda et al. (2018) have shown can work with pixel observations.

**Experimental Setup** We use the Hopper, Ant, Walker and HalfCheetah continuous control environments from the PyBullet gym suite (Ellenberger, 2018–2019). The expert policy is obtained
by training a SAC agent for 2 million steps. We compare 5 methods. ILR denotes our imitation
learning reduction. BC denotes a behavioral cloning policy, obtained after training on the expert
dataset for 500000 steps. GAIL (Ho & Ermon, 2016) denotes the Generative Adversarial Imitation
Learning algorithm. GMMIL (Kim & Park, 2018) denotes a variant of adversarial IL minimizing the
MMD divergence. SQIL (Reddy et al., 2020) denotes the SQIL heuristic. In order to ensure a fair
comparison among algorithms, we re-implemented all of them using the same basis RL algorithm,
SAC (Haarnoja et al., 2018). All imitation learning agents were run for 500000 environment interactions. We repeated our experiments using 5 different random seeds. The remaining details about the
implementation and hyperparameters are provided in Appendix A.

**Performance as Function of Quantity of Expert Data** The plot in Figure 1 shows the performance
of various imitation learners as a function of how much expert data is available. The amount of data
is measured in episodes, where fractional numbers mean that state-action tuples are taken from the
beginning of the episode. Confidence bars represent one standard error. All of the methods except BC
work well when given a large quantity of expert data (16 episodes, on the right hand side of the plot).
However, for smaller sizes of the expert dataset, the performance of various methods deteriorates
at different rates. In particular, GMMIL needs more expert data than other methods on Hopper and
Walker, while on Ant ILR achieves top performance with less data than other methods. Across all the
environments, ILR is competitive with the best of the other methods. We claim that our method is
preferable since it is the simplest one to implement, is computationally cheap and does not introduce
new hyperparameters beyond those of the RL solver.

**Performance as Function of Quantity of Environment Interactions** In Figure 2, we examine the
progress of the various agents as a function of environment interactions for a dataset containing 16
expert episodes. ILR shows improved sample efficiency on Ant, while behaving similarly to other


-----

) expert ( ) ILR ( ) GAIL ( ) GMMIL ( ) SQIL


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

500

1000

0.00K 250.00K 500.00K


(a) Hopper


(b) Ant


(c) Walker


(d) HalfCheetah


Figure 2: Extrinsic return of imitation learner as a function of the number of environment interactions.
Imitation learners were trained on 16 expert trajectories. Shaded area denotes one standard error.

algorithms on Hopper, Walker and HalfCheetah. Again, we are led to conclude that ILR is preferable
to to the other algorithms because of its simplicity. We provide analogous plots for different sizes of
the expert dataset in Appendix B.


**Intrinsic and Extrinsic Returns are Related in Practice** Our
reasoning in Section 4.3 shows that achieving a large intrinsic return
serves as a performance certificate, guaranteeing a certain level of
extrinsic return. We conducted an experiment to determine if this
property still holds for our continuous-state relaxation. Figure 3
shows the relationship between the intrinsic return (on the horizontal
axis) and the extrinsic return (on the vertical axis), during the first
50K steps of training using the Hopper environment. Each point on
the plot corresponds to evaluating the policy 100 times and averaging
the results. The plot confirms that there is a clear, close-to-linear,
relationship between the intrinsic and extrinsic return.

7 CONCLUSIONS


2000

1500

1000

Extrinsic Return 500

0

0 200 400 600 800

Intrinsic Return


Figure 3: Intrinsic vs Extrinsic
returns


We have shown that, for deterministic experts, imitation learning can be performed with a single
invocation of an RL solver. We have derived a bound guaranteeing the performance of the obtained
policy and relating the reduction to adversarial imitation learning algorithms. Finally, we have
evaluated the proposed reduction on a family of continuous control tasks, showing that it achieves
competitive performance while being comparatively simple to implement.

8 ACKNOWLEDGMENTS

The author thanks Lucas Maystre and Daniel Russo for proofreading the draft and making helpful
suggestions. Any mistakes are my own.

9 ETHICS STATEMENT

Since our most important contribution is a bound stating that the imitation learner closely mimics the
expert, the ethical implications of actions taken by our algorithm crucially depend on the provided
demonstrations. The most direct avenue for misuse is for malicious actors to intentionally demonstrate
unethical behavior. Second, assuming the demonstrations are provided in good faith, there is a risk
of excessive reliance on the provided bound. Specifically, it is still possible that our algorithm fails
to recover expert behavior in situations where assumptions needed by our proof are not met, for
example if the expert policy is stochastic. In certain settings, the bounds can also turn out to be very
loose, for example when the expert policy takes long to mix. This means that one should not deploy
our reduction in safety-critical environments without validating the assumptions first. However, the
proposed reduction also has positive effects. Specifically, we provide the benefits of adversarial
imitation learning, but without having to train the discriminator. This means that training is cheaper,
making imitation learning more affordable and research on imitation learning more democratic.


-----

10 REPRODUCIBILITY STATEMENT

Our main contribution is Proposition 1, for which we provided a complete proof. The external results
we rely on are generic properties of the Total Variation distance and of Markov chain mixing[1], for all
of which we have provided references. Our experimental setup is described in detail in Appendix A.
Moreover, we make the source code available.

REFERENCES

Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In
_Proceedings of the twenty-first international conference on Machine learning, pp. 1, 2004._

Christopher G Atkeson and Stefan Schaal. Robot learning from demonstration. In ICML, volume 97,
pp. 12–20. Citeseer, 1997.

Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network
distillation. arXiv preprint arXiv:1810.12894, 2018.

Benjamin Ellenberger. Pybullet gymperium. https://github.com/benelot/
pybullet-gym, 2018–2019.

Eugene A Feinberg and Adam Shwartz. Handbook of Markov decision processes: methods and
_applications, volume 40. Springer Science & Business Media, 2012._

Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control
via policy optimization. In International Conference on Machine Learning, pp. 49–58, 2016.

Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence minimization
perspective on imitation learning methods. In Conference on Robot Learning, pp. 1259–1277.
PMLR, 2020.

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, pp. 1861–1870. PMLR, 2018._

Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in neural
_information processing systems, pp. 4565–4573, 2016._

Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward
learning from human preferences and demonstrations in atari. In Advances in neural information
_processing systems, pp. 8011–8023, 2018._

Kee-Eung Kim and Hyun Soo Park. Imitation learning via kernel mean embedding. In Thirty-Second
_AAAI Conference on Artificial Intelligence, 2018._

David A Levin, Yuval Peres, and EL Wilmer. Markov chains and mixing times, vol. 107. American
_Mathematical Soc, 799, 2017._

Yunzhu Li, Jiaming Song, and Stefano Ermon. Infogail: Interpretable imitation learning from visual
demonstrations. In Advances in Neural Information Processing Systems, pp. 3812–3822, 2017.

Andrew Y Ng, Stuart J Russell, et al. Algorithms for inverse reinforcement learning. In Icml,
volume 1, pp. 2, 2000.

Daniel Paulin. Concentration inequalities for markov chains by marton couplings and spectral
methods. Electronic Journal of Probability, 20, 2015.

Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.

1In particular, we use a corollary of McDiarmid’s inequality for Markov chains by Paulin (2015).


-----

Siddharth Reddy, Anca D. Dragan, and Sergey Levine. SQIL: Imitation learning via reinforcement
learning with sparse rewards. In International Conference on Learning Representations, 2020.
[URL https://openreview.net/forum?id=S1xKd24twB.](https://openreview.net/forum?id=S1xKd24twB)

Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the
_thirteenth international conference on artificial intelligence and statistics, pp. 661–668, 2010._

Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured
prediction to no-regret online learning. In Proceedings of the fourteenth international conference
_on artificial intelligence and statistics, pp. 627–635, 2011._

Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning
from observation alone. In International Conference on Machine Learning, pp. 6036–6045, 2019.

Ruohan Wang, Carlo Ciliberto, Pierluigi Vito Amadori, and Yiannis Demiris. Random expert
distillation: Imitation learning via expert policy support estimation. In International Conference
_on Machine Learning, pp. 6536–6544. PMLR, 2019._

Tianhao Zhang, Zoe McCarthy, Owen Jow, Dennis Lee, Xi Chen, Ken Goldberg, and Pieter Abbeel.
Deep imitation learning for complex manipulation tasks from virtual reality teleoperation. In 2018
_IEEE International Conference on Robotics and Automation (ICRA), pp. 1–8. IEEE, 2018._

A DETAILS OF EXPERIMENTAL SETUP

To ensure a fair comparison, we implemented all imitation learners (ILR, GAIL, GMMIL and SQIL)
using the same base reinforcement learning solver (SAC). The implementation of SAC we used as a
basis came from the d4rl-pybullet repository[2]. The hyperparameters of SAC are given in the
table below.

**hyperparameter** **value**
actor optimizer Adam
actor learning rate 3e-4
critic optimizer Adam
critic learning rate 3e-4
batch size 100
update rate for target network (tau) 0.005
_γ_ 0.99

The policy network and the critic network have two fully connected middle layers with 256 neurons
each followed by ReLU non-linearities. The entropy term was not used when performing the actor
update after we found that including it had no effect on performance. Instead, a fixed Gaussian noise
with standard deviation of 0.01 was used for exploration.

For our behavioral cloning baseline, we performed supervised learning for 500K steps, using the
Adam optimizer with learning rate 3e-4. We used the same policy network architecture as the SAC
policy network.

ILR does not introduce any additional hyperparameters.

GAIL has the following additional hyperparameters.

**hyperparameter** **value**
discriminator optimizer Adam
discriminator learning rate 3e-4
discriminator batch size 100
discriminator update frequency 32
discriminator training iterations 500

2https://github.com/takuseno/d4rl-pybullet


-----

The last two hyperparameters mean that the discriminator network in GAIL is updated every 32
simulation steps, using 500 batches of data.

A direct implementation of GMMIL requires looping over the whole replay buffer each time a reward
is computed, which makes the algorithm very slow for longer runs. To make it tractable, we we only
computed the kernel for 8 points closest to the given state-action pair in the replay buffer and for 8
points in the expert dataset. The data structure used to find the nearest 8 points was updated every
32 steps. Kernel hyper-parameters were automatically estimated using the median heuristic (Kim &
Park, 2018) each time the algorithm was run.

SQIL uses a batch size of 200 (100 for state-action pairs from the expert and 100 for state-action
pairs coming from the replay buffer). It does not have additional hyperparameters.

B PLOTS MEASURING SAMPLE EFFICIENCY


In this section, we include plots showing the efficiency of all algorithms measured in terms of
environment interactions, for different quantities of available expert data. The plots can be thought as
an extension of Figure 1 in the main paper to what is happening during learning, not just at the end.

( ) expert ( ) ILR ( ) GAIL ( ) GMMIL ( ) SQIL


Hopper Ant Walker HalfCheetah


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

500

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

500

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

500

1000

1500

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

500

1000

1500

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

500

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

500

1000

0.00K 250.00K 500.00K


-----

2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

0.00K 250.00K 500.00K


2000

1500

1000

500

0

500

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


1500

1000

500

0

0.00K 250.00K 500.00K


2000

1000

0

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


1500

1000

500

0

0.00K 250.00K 500.00K


2000

1000

0

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


1500

1000

500

0

0.00K 250.00K 500.00K


2000

1000

0

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


1500

1000

500

0

0.00K 250.00K 500.00K


2000

1000

0

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


1500

1000

500

0

0.00K 250.00K 500.00K


2000

1000

0

1000

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


2500

2000

1500

1000

500

0

0.00K 250.00K 500.00K


1500

1000

500

0

0.00K 250.00K 500.00K


2000

1000

0

1000

0.00K 250.00K 500.00K


RUNTIME COMPARISON OF DIFFERENT ALGORITHMS


We ran all algorithms from the paper in a controlled computational setting (no other processes running
on the machine) in the hopper environment for 500K iterations. An expert dataset containing 16
episodes was used. Results are given below.

**Algorithm** **Runtime**
BC 0m 17s
SQIL 94m 39s
ILR 99m 16s
GAIL 213m 56s
GMMIL 448m 42s


Behavioral Cloning (BC) is the fastest, because it does not have to do any interaction with the
environment (it does, however, produce a policy with the worst performance). SQIL and ILR have a


-----

comparable runtime, dominated by the complexity of simulating the environment. GAIL is slower
because it has to train the discriminator network. GMMIL is the slowest algorithm due to the high
cost of computing the MMD divergences.

Overall, the conclusion from this benchmark is that our algorithm (ILR) is highly competitive in
terms of runtime.

D ADDITIONAL PROOFS

_Proof of Lemma 1. By setting v[′]_ = 1 − _v, it follows that Eρ2_ [v] − Eρ1 [v] ≤ _ϵ for all v. Therefore_
_|instantiateEρ1_ [v] − _vE(ρx2_ [) =v]| ≤ 1 {ϵx for all ∈ _M_ _} v, completing the proof.. For any M ⊆_ _X on the right-hand side of equation 3, we can_

_Proof of Lemma 2. We have_

Eρ1 [v] Eρ2 [v] = _x[(][ρ][1][(][x][)][ −]_ _[ρ][2][(][x][))][v][(][x][)][| ≤]_ [P]x
_|_ _−_ _|_ _|[P]_ _[|][ρ][1][(][x][)][ −]_ _[ρ][2][(][x][)][|][ =][ ∥][ρ][1][ −]_ _[ρ][2][∥][1][.]_

Here, the first inequality follows because elements of v are in the interval [0, 1]. The statement of the
lemma follows from the property ∥ρ1 − _ρ2∥TV =_ [1]2 _[∥][ρ][1][ −]_ _[ρ][2][∥][1][.]_

_Proof of Lemma 3. By Theorem 4.9 in the book by Levin et al. (2017), there are constants_
(C >1(s[′]) 0[⊤]P andE[t] [)(] α[s][)][π] ∈[E][(][a](0[|][s],[)] 1)[, we have] such that[ max] max[s][′][ ∥][′]sρ[˜][∥][s]t[1][′] [(][−][s][′][ρ][)][⊤][E][P][∥][TV]E[ t] _[−][≤][ρ]S[E][Cα][∥][TV][t][, where we used the fact that the][ ≤]_ _[Cα][t][.]_ Defining ˜ρ[s]t _[′]_ [(][s, a][) =]
expert policy is deterministic so that _ρ˜[s]t_ _[′]_ [=][ ∥][1][(][s][′][)][⊤][P][ t]E _S_
the chainτmix ≤− τlogmixα, defined as the smallest C − logα(4). _∥ t so that[−]_ _[ρ] max[E][∥][TV]s′ ∥1(s[′])[⊤]PE[t]_ _[−]_ _[−][ρ]S[E][ρ][∥][E][TV][∥][ ≤][TV][. The mixing time of]4[1]_ [is then bounded as]

It remains to show that, for any probability distribution p1, we have _t=0_ _[∥][p]1[⊤][P]E[ t]_ _[−]_ _[ρ]S[E][∥≤]_ [2][τ][mix][.]

Define d(t) = supp _p[⊤]PE[t]_ _S_
_∥_ _[−]_ _[ρ][E][∥][TV][. By equation 4.35 in the book by Levin et al. (2017), we have][P][∞]_

_d(ℓτmix) ≤_ 2[−][ℓ]. (20)

We can now write

_∞_ _∞_ _∞_ _∞_

_t=0_ _∥p[⊤]1_ _[P]E[ t]_ _[−]_ _[ρ]S[E][∥≤]_ _t=0_ _d(t) ≤_ _t=0_ _d(τmix⌊t/τmix⌋) ≤_ _t=0_ 2[−⌊][t/τ][mix][⌋],

X X X X

where the first inequality follows from the definition of d(t), the second one from the fact that
_d(t[′]) ≤_ _d(t) for t[′]_ _≥_ _t and the last one from equation 20. We can rewrite the right-hand side further,_
giving


_∞_

2[−][t] = 2τmix.
_t=0_

X


2[−⌊][t/τ][mix][⌋] = τmix
_t=0_

X


_Proof of Lemma 7. Consider the imitation learner’s trajectory of length T_ . We will now consider
sub-sequences where the agent agrees with the expert. Denote by Mℓ the number of such sequences
of length ℓ. Denote by _V[ˆ]_ _[i,ℓ]_ the per-step extrinsic reward obtained by the agent in the ith sequence of
length ℓ.

Assuming the worst case reward on states which are not in any of the sequences (i.e. where
the agent disagrees with the expert), the total extrinsic return JT along the trajectory is at least

reward is at leastℓ _[ℓ]_ [P][M]i=1[ℓ] _V[ˆ]_ _[i,ℓ]_ = _ℓ_ _[ℓM][ℓ]_ _M[1]ℓ_ _Mi=1ℓ_ _V[ˆ]_ _[i,ℓ]. Dividing by the sequence length, the per-step extrinsic_

P [P] P _JTT_ _ℓ_ _ℓMT_ _ℓ_ _M1ℓ_ _Mi=1ℓ_ _V[ˆ]_ _[i,ℓ]._ (21)

_[≥]_ [P] P


-----

Denote by ∆ℓ = _M[1]ℓ_ _Mi=1ℓ_ _V[ˆ]_ _[i,ℓ]_ _−_ _M1ℓ_ _Mi=1ℓ_ _V[˜]p[ℓ](s[ℓ]1[)]_ the difference between the average extrinsic

reward obtained in sequences of lengthP P ℓ and its expected value, where we denoted by p(s[ℓ]1[)][ the]
initial state distribution among sequences of length ℓ. We can now re-write equation 21 as:


_JTT_ _ℓ_ _ℓMT_ _ℓ_ _M1ℓ_ _Mi=1ℓ_ _V[˜]p[ℓ](s[ℓ]1[)][ −]_ [P]

_[≥]_ [P] P

Using Lemma 6, we can re-write this further


_ℓMT_ _ℓ_ [∆][ℓ][.] (22)


_JT_ _ℓMℓ_ _ℓMℓ_

_ℓ_ _T_ EρE [R] _ℓ_ [4][τ][mix] _ℓ_ _T_ [∆][ℓ] (23)

_T_ _−_ [1] _−_ [P]

_[≥]_ [P] _ℓMℓ_ _Mℓ_ _ℓMl_

= _ℓ_ _T_ [E][ρ][E] [[][R][]][ −] [P]ℓ _T_ [4]
[τ][mix][ −] [P]ℓ _T_ [∆][ℓ][.] (24)

Denote by B the number of timesteps the imitation learner disagrees with the expert. Observe
that we have _ℓ_ _MTℓ_ _T_ since[P] _B bad timesteps can partition the trajectory into at most B + 1_

sub-sequences and _[≤]ℓ_ _[M][B][ℓ][+1][is the total number of sub-sequences. This gives]_

[P] [P] _JTT_ _ℓ_ _ℓMT_ _ℓ_ [E][ρ][E] [[][R][]][ −] _[B]T[+1]_ [4][τ][mix][ −] [P]l _ℓMT_ _ℓ_ [∆][ℓ][.] (25)

_[≥]_ [P]

Now, using the fact that the imitation learner policy is ergodic, we can take limits asℓM Tℓ _→∞. The_
left hand side converges to EρI [R] with probability one. On the right-hand side, _ℓ_ _T_ (the fraction

of time the imitation learner agrees with the expert) converges to EρI [Rint] = 1 − _κ with probability_
one. Using ergodicity again, _[B]T[+1]_ converges to 1 EρI [Rint] with probability one.[P]

_−_

It remains to prove that the error term _ℓ_ _ℓMT_ _ℓ_ [∆][ℓ] [converges to zero with probability one. First,]

we will show that, for every ℓ, either Mℓ is always zero, i.e. the streak length ℓ does not occur in
sub-sequences of any length or Mℓ as T . Indeed, the chain is ergodic, which means that,
_→∞[P]_ _→∞_
if we traversed a streak of length ℓ, we have non-zero probability of returning to where the streak
begun and then retracing it. Let us call the of set of all ℓs where Mℓ = 0 by N _L_ . Moreover, let
_−_ _∞_
us call the set of ℓs with Mℓ _→∞_ as T →∞ with L∞. We have:

_ℓ∈L∞_ _ℓMT_ _ℓ_ [∆][ℓ] [+][ P]ℓ∈N−L∞ _ℓMT_ _ℓ_ [∆][ℓ] _[≤]_ [sup][ℓ][∈][L]∞ [∆][ℓ][.] (26)

The second term in the sum equals zero with because of the definition ofP _L∞. The term supℓ∈L∞_ ∆ℓ
converges to zero with probability one by the law of large numbers, where we use the fact that
_Mℓ_ _→∞_ as T →∞ for Mℓ _∈_ _L∞._


-----