Imitation Learning by Reinforcement Learning
Authors: Kamil Ciosek
Venue: ICLR 2022 Poster (2022)
Keywords: reinforcement learning
imitation learning
Markov Decision Process
continuous control

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.

Published as a conference paper at ICLR 2022
IMITATION LEARNING BY REINFORCEMENT LEARNING
Kamil Ciosek
Spotify kamiler cespotii
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 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 practice for continuous control tasks.
INTRODUCTION
Typically, reinforcement learning (RL) assumes access pre-specified reward and then learns 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 policy from expert demonstrations.
There are two major categories of Imitation Learning algorithmss behavioral cloning and inverse reinforcement learning. Behavioral cloning learns the policy by supervised learning on expert data, but is robust training errors, failing 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 maximize these rewards (Ng et al. 2000).
The most versatile IRL method is adversarial IL (Ho Ermon 2016 Li et al. 2017 Ghasemipour al. 2020), which minimizes divergence between the distribution of data produced by the agent and provided by the expert. Adversarial IL learns representation and a policy simultancously 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 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, Waag et al. (2019) proposed to reduce imitation learning to single instance of reinforcement learning problem, where reward is defined 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 Scction However, while empirical performance of these approaches has been good, they enjoy no performance guarantees all, even in the asymptotic setting where expert data is infinite.
Contributions We fill in this missing justification for this algorithm, providing the needed theoreti- cal analysis. Specifically, in Sections aad 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. Morcover, in Section 6 we empirically evaluate the performance of the reduction the amount of available expert data varies.

---

Published as a conference paper at ICLR 2022
2 PRELIMINARIES
Markov Decision Process An avcrage-reward Markov Decision Process (Puterman 2014: Fein- berg & Shwartz, 2012) is tuple (S, A, R, s1), where S is state space, A is the action space, T: x A - P(S) is the transition model, R 5 x A - [0, 1] is a bounded reward function and $1 the initial state. Here, we write P(X) to denote probability distributions over set X, A stationary policy т : S - P(A) maps environment states to distributions over actions. A policy π induces Markov chain Pz over the states. In the theoretical part of the paper, treat MDPs with finite state and action spaces. Given the starting state $1 of the MDP, and a policy ग,, the limiting distribution
over states is defined
N
1 N
D 1
lim N
P
1=0
where 1 (5) denotes the indicator vector. We adopt the convention that the subscript S indicates a distribution over states and subscript indicates distribution over state-action pairs. We denote p" [8, a) (*))) (.) While the limit in equation [ 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 p3 and p" does not include the dependence on the initial state. The expected per-step reward of is defined as
V lim Ex [JN/N | [s]== = Epp [[[(s.)]. -20
where JN = - R(st, 0x)) is the total return. In this paper we consider undiscounted MDPs because they are enough to model the essential properties of the imitation Iearning problem while being conceptually simpler than discounted MDPs. However, we believe that similar results could be obtained for discounted MDPs.
Expert Dataset Assume that the expert follows ergodic policy gg. Denote the corresponding distribution over expert state-action pairs as nf (s, = -T (s, a), which does not depend on the initial state by ergodicity. Consider finite trajectory 81; 01, 82, (22....,8)) aN- Denote by p(s. a) = A En 1 {(s, a) (s), the histogram (empirical distribution) of data seen along this trajectory and denote by (s) + Ei= {s 8²) the corresponding histogram over the states. Denote by D the support of p. i.c. the set state-action pairs visited by the expert.
Total Variation Consider probability distributions defined on discrete set X. The total variation distance between distributions is defined as
|l P2/1TV = sup (P: - P2(M)
MCX
In our application, the X is either the set of MDP states or the set of state state-action pairs S x A. Below, we restate in our notation standard results about the total variation distance. See Appendix D for proofs.
Lemma 1. Bf [v] - Epg [v] e for any vector E [0, 1| then llei P2||TV S e. Lemma 2. Ifl: P2llTV S then E,, [v] E,2 [u] s 2e for any vector v E [0, 1
Imitation Learning Learning to imitate means obtaining policy that mimics expert behavior. This can be formalized two ways. First, we can seek an imitation policy कy which obtains a expected per-step reward that is e-close to the expert any reward signal bounded in the interval [0, 1]. Denote the limiting distribution of state-action tuples generated by the imitation learner with p (s) Formally, want satisfy
VR: S A - [0,
E,, [R]
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, we measure the divergence between distributions with total variation, we want to ensure
| -ppp p² 1Ivv Sc
(5)
2

---

Published as a conference paper at ICLR 2022
Algorithm 1 Imitation Learning by Reinforcement Learning (ILR)
Require: expert dataset D, ENVIRONMENT (without access to extrinsic reward)
Rimt (s, a) < {(,, a) E D}
T RLL-SOLVER(ENVIRONENN Ryms)
Lemmas I [nd that the gand closely related. In other words, attaining expected per-step reward close to the expert's 's is the same (up to a multiplicative constant) 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
When coupled with the dynamics of the MDP, a policy induces Markov chain, In this paper, we focus our attention 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
Markov Chains
Lemma 3. Denote with PF, the Markov chuin induced by irreducible and aperiodic expert policy. The mixing time of the chain Tmix, defined as the smallest t so that max.'
[s ( P P ITv S à is bounded. Moreover, for any probability distribution pt, we have 000 [Ppi P - P IV S 2Tmix.
3 IMITATION LEARNING BY REINFORCEMENT LEARNING
Algorithm To perform imitation learning, we first obtain an expert dataset D and construct an intrinsic reward
(sm a) = ((,,a) E D}.
(6)
We can then use any RL algorithm to solve for this reward. We note that for finite MDPs equation exactly matches the algorithm proposed by Wang et al. 2019) as heuristic. The reward defined in equation is intrinsic, meaning we construct artificially order 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| [ that the two are fact closely related and solving for the intrinsic reward guarantees recovery of the extrinsic reward.
Guarantee on Imitation Policy The main focus 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.
The expert policy is deterministic. Assumption 2. The expert policy induces an irreducible and aperiodic Markov chain.
Assumption 1.
Assumption 3. The imitation learner policy induces an irreducible and aperiodic Markov chain.
Assumption D is critical for our proof to go through and cannot be relaxed. It also essential to rationalize the approach of Wang et al. (2019). In fact, reduction involving single call an RL solver with stationary reward can exist for stochastic experts since for any MDP there 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 finite dataset of N samples.
Our main contribution is Proposition [ in which we quantify the performance our imitation learner. We state it below and prove it in Section
Proposition 1. Consider imitation learner trained on dataset of size N, which attains the limiting distribution of state-action pairs p²_ Under Assumptions / and 3 given that we have
N > max {800] 450 log (3) Tmnx""" -2 expert demonstrations, with probability least 1 8, the imitation learner attains total variation distance from the expert of at most
1|p -pp
p' 11av Sn
The constant Tmix 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
3

---

Published as a conference paper at ICLR 2022
expected per-step extrinsic reward of at least
3 [R] 2 1 77
(8)
Proposition Iaciiionnshaee shows that the policy learned by imitation learner satisfies two important desiderata: we can guarantee both the closeness of the generated state-action distribution the expert distribution as well as recovery of expert reward. Moreover, the total variation bound in equation 7 links the obtained policy adversarial imitation learning algorithms. We describe this link in more detail in Section
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 possible to achieve high expected per-step intrinsic reward defined equation part, in Section 4.3 we show that, achieving large expected per-step intrinsic reward guarantees 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 [
the second
4.1 MIXING IN MARKOV CHAINS
We now show lemma that quantifies how fast the histogram approaches the stationary distribu- tion. 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 Paullnn (2015).
Lemma 4. The total variation distance between the expert distribution and the expert histogram ò based N samplex can be bounded
| Tmix
l1pe plITV S V
N
with probability at least 2 exp generating the expert histogram).
{
NN 1.5Tmer
(where the probability space defined by the process
Proof. We first prove the statement for histograms over the states. Recall the notation òs & Em {s, = s}. Recall that we denote the stationary distribution (over states) of the Markoy chain induced by the expert with pg.
First, instantiating Proposition of Paulin (2015), we obtain
Epp Pl Ps lrv] < Σ. min (V
(p
PS(())
PS
No
where Yps is pseudo spectral gap of the chain. Re-write the right-hand side as ( A
Σ. min
p5(())
Σ.
(o
4 Nyy
Now
N
where the last inequality follows from the Cauchy-Schie Schwartz inequality. Using equation 3.9 of Paulin (2015), we have "/ps 2 2 Taken together, this gives
Eps [lpe PSSlTv] S
8
(10)
N
Instantiating Proposition 2.18 of Paulin 2015) we obtain
{
2
P(Il - PsllTV - Eps (lles
Ps pslltv]l 2 2exp
(11)
4.5
Combining equations TO and 11
we obtain
2
[1le5
ÅS||TV 2 6
8|51 N
2exp
4.5Tmix
Since the expert policy is deterministic, the total variation distance between the distributions of state-action tuples and states is the same, i.e. l|rg -S|lTV l
éll
4

---

Published as a conference paper at ICLR 2022
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 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 2 exp 1 4.5 Jr obtain dataset such that policy ny maximizing the intrinsic reward
Z2
where we used the shorthand notation p² = p=1 to denote the state-action distribution of T..
(s, a) = a(s,a) E D) satisfies B [Rm]] 21 S
Proof. We invoke Lemma obtaining l1e" - pllTv S c V statement of the lemma. First, we prove
S Taus with probability as in the
2 (p(s,a) = 00 s 8.S1 Farx
(12)
by setting - p=, ,2 - and M = (ss,a) ((8 a) = 0} in equation
Combining
1= E. (8, a) = D (s, (Ā(s.a) = 0) + Σs of (8, (p(8,a) > 0}
(13)
and equation
[2] we obtain
E. p" a) as fp(s, a) > 2 1 1 c-
8|S1
Fanx
(14)
which means that the expert policy achieves expected per-step intrinsic reward of at least 1
81
Fisx
This lower bounds the expected per-step reward obtained by the optimal policy.
N
4.3 MAXIMIZING INTRINSIC REWARD LEADS TO HIGH PER-STEP EXTRINSIC REWARD
We now aim prove that the intrinsic and extrinsic rewards are connected, i.c. 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 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 agent traverses sequence of state-action pairs, in a way consistent with the expert policy. Denote the expert's expected extrinsic per-step reward with E,][R]. Denote by P. (s, a) = (p] gs) ) the expected state-action occupancy at time t, starting in state distribution p1. The per-step extrinsic reward ps of the agent in expectation over realizations of the
sequence satisfies
Vel = Essa (EEno 1P (s,a) R(s.a)) 2 E (R)
Arms
(15)
Proof. Invoking Lemma we have that R, [R]
2 [R] < 21
-f ll for any timestep
t. In other words, the expected per-step reward obtained in step t of the sequence is at least E - 21 - = ||v. The per-step reward in the sequence at least
V M E 2|1 lTv)
E [R]
D 10 p 1|TV
ž Ep [R]
2 D 1 1TT
Invoking Lemma have that 120lPp 1Tv < 2Tmix- Since the expert policy is deterministic, distances between distributions of states and state-action pairs are the same. We thus
p1 get Vee 2 E,5 [ 4rais
5

---

Published as a conference paper at ICLR 2022
In Lemma have shown that, average, agreeing with the expert for number of steps guarantees a certain level 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), imitation learner which attains expected per-step intrinsic reward of R.pp' [im = K. also attains extrinsic per-step reward of at least
E [ 2
EE RR)
mimixh.
with probability one, where E [ is the expected per-slep extrinsic reward of the expert.
We provide the proof in Appendix
4.4 BRINGING THE PIECES TOGETHER
We now show how Lemma and Lemma can be combined to obtain Proposition (stated in Section
Proof of Proposition !
We use the assumption that N
max {800]S), 450 (3)) mix" m?
Since Tmix is either zero or Tmix 2 1, this implies
2
N 2 max 32 /2/SS/mmix (1 4Tmix) ) 2 log
18ix (1 + 4Tmix) )21
(16)
We will instantiate LemmaB with
(17)
2 + 8Tmix
Equations and 17 iiply that N 2 log (2) 18Tmix (1 + 4fmix)* 2 log (3) 4.5Tmix We can
rewrite this as log (2) < Nea 4.57mm
which implies 22 log é This implies that
4.57ml
{
2
8 2 2cxp
(18)
4.5Tmix
Moreover, using equation
16 again, we have that N
32|SS Tmix (1 4Tmix )2 12 This equivalent
to
S Tuis
or
N
<
1444mm
11
Using equation 17
we obtain e + v 8 7lm
N
<
7 1+
equivalent to ++1 8).5 Tima N
(1 + 4Tmix)
S Rewriting this gives
(1 4rmix) 17,
(19)
where we use the notation Æ c
81. Tais
We first show equation g which states that we are able to recover expected per-step expert reward. Invoking Lemma 5 and using equation [8] we have that it is possible for the imitation learner to achieve per-step expected intrinsic reward of at least 1 x with probability 8. Invoking Lemma this implies achieving extrinsic reward of at least
Ep [
E,E [R] x:) -4Tmix
This implies
E E
R
Ep
R
<
E
R
E [R] 1:) + 4rmix
R.lE,,
R + 4 S. + 4Tmix S 7)
where the last incquality follows from equation 19 Since this statement holds for any extrinsic reward signal R, we obtain the total variation bound by invoking Lemma getting || - p² || & n. 1T

---

Published as a conference paper at ICLR 2022
5 RELATED WORK
Behavioral Cloning The simplest way of performing imitation learning to learn policy by fitting a Maximum Likelihood model on the expert dataset. While such 'behavioral cloning' is easy to implement, 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 pre-leamned 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 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 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 divergence. It can be related to the total variation objective of equation in two ways. First, the TV and JS divergences obey 2 1 (p .p) 2 l|p o² [[v. that Dis(p ,p) S
implies Ilp= 1|ıv S 2/e'. This means that GAIL indirectly minimizes the total variation distance. Second, we have l|p 1 II 2 Dis(p",,')) Since our algorithm minimizes Total Variation for sufficiently large sizes of the expert dataset, this means that it also minimizes the GAIL. objective. Both of these properties imply that our reduction converges 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 eLi al. 2017) minimizes the I-Wasserstein divergence, which obeys E,, [Rr] Ep [ Dw (p" p') for any reward function RL Lipschitz in the L1 norm. This is similar to the property defined by equation 4 implied by our Proposition [ except we guarantee closeness of expected per-step reward for any bounded reward function as opposed to Lipschitz-contimuuus functions.
Random Expert Distillation Wang et al. (2019) propose an algorithm which, for finite MDPs, is the same 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 work in that it proposes similar algorithm. At any given time, SQIL performs pol-cy reinforcement learning on a dataset sampled from the mixture distribution (p (s, a) (s))), where ( a) is the distribution of data under the expert. Since the rewards are one for the data sampled from D and zero for state- action pairs sampled from PRL, the expected reward obtained at state-action pair (s, a) is given by (f(s,,)
p(stttttaa(ssa 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, does not come with a theoretical guarantee any kind, making it hard 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 al.] (2011) assume the ability 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 execute expert queries to obtain more data.
7

---

Published as a conference paper at ICLR 2022
expert
(-ILR ILR
(+)BC
(+II (+-GMMILL (-+) SQIL
300
200-
1530
190
(a) Hopper
(b) Ant
(c) Walker
(d) HalfCheetah
Figure I: Extrinsic return of imitation learners function of the number of episodes of demonstra- tion data. For comparison, we also show expert performance. Confidence bars denote one standard eπror.
6 EXPERIMENTS
We investigate the performance of our reduction on continuous control tasks. Because Wang et al. (2019) have already conducted an extensive evaluation various ways 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 a continuous state-action space, we define the reward as [s, a) = 1 minl ED) dr, ((s, a), (s', d'))². To see how this is related to the reward in equation 6 consider scaled version of the binary reward used in the theoretical analysis which ranges from 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 [ directly, we can no longer theoretically claim the recovery of expert reward (as in Lemma 7 However, this property still holds in practice, verified below. In settings where such reduction 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 work with pixel observations.
L to 1 instead of from 0 to 1, where L is the Le-diameter of the
Experimental Setup We use the Hopper, Ant, Walker and HalfCheetah continuous control envi- ronments from the PyBulle let gym suite (Ellenberger 2018 2019). The expert policy is obtained by training 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 adversarial IL minimizing the MMD divergence. SQIL (Reddy et al. 2000)) denotes the SQIL heuristic. In order to ensure fair comparison among algorithms, we re- immllmentedd all of them using the same basis RL algorithm, for 500000 environment interac-
SAC (Haarnoja et al., 2018). All imitation learning agents tions. 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 I 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, the right hand side of the plot). However, for smaller sizes of the expert dataset, the performance of various methods deteriorates 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 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 other
8

---

Published as a conference paper at ICLR 2022
expert
ILR
GAIL
GMMIL
SQIL
2000
2000
1590
1906
530
1200
JAAKE
500.00
0.8Cc
J5ADCK
(a) Hopper
(b) Ant
(c) Walker
(d) HalfCheetah
Figure 2: Extrinsic return of imitation learner function of the number of environment interactions. Imitation learners were trained on expert trajectories. Shaded area denotes one standard error.
algorithms Hopper, Walker and HalfCheetah. Again, 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
Intrinsic and Extrinsic Returns are Related Practice Our reasoning in Section 4.3 shows that achieving 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-stin relaxation. Figure 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-lineas relationship between the intrinsic and extrinsic return.
1500
1000
500
260
100
000
100
Intitide
Figure 3: Intrinsic vs Extrinsic returns
7 CONCLUSIONS
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 guarantecing the performance of the obtained policy and relating the reduction adversarial imitation learning algorithms. Finally, we have evaluated the proposed reduction on family of continuous control tasks, showing that achieves competitive performance while being comparatively simple to implement.
ACKNOWLEDGMENTS
The author thanks Lucas Maystre and Daniel Russo for proofreading the draft and making helpful suggestions. Any mistakes my own.
ETHICS STATEMENT
Since important contribution 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 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 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 very loose, for example when the expert policy takes long to mix. This means that one should not deploy our reduction in safety-crin critical environments without validating the assumptions first. However, the proposed reduction also has positive effects. Specifically, imitation learning, but without having to train the discriminator. This means that training is cheaper, making imitation learning more affordable and research imitation learning more democratic.
provide the benefits of adversarial

---

Published as a conference paper at ICLR 2022
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 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. 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 / 12894, 2018.
Benjamin Ellenberger. Pybullet gymperium.
ht:tss///gthabb.com//eee ot
pybullet gym 2018-2019.
Eugene 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 atari. Advances in neural information processing systems, pp. 801 1-8023, 2018.
Kee-Eung Kim and Hyun Soo Park. Imitation learning via kernel mean embedding. In Thirty-Secome AAAI Conference 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.
In particular, we corollary of McDiarmid's incquality for Markov chains by Paulin 2015
10

---

Published as a conference paper at ICLR 2022
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 http:ss////peeeeeeeee/
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 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. 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 telcoperation. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 1-8. IEFE, 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 basis came from the d4 -pybul repository The hyperparameters of SAC are given in the table below.
hyperparameter actor optimizer actor learning rate
value Adam
3e-4
critic optimizer critic learning rate batch size update rate for target network (tau) ?
Adam
3e-4
100
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 performance. Instead, fixed Gaussian noise with standard deviation of 0.01 was used for exploration.
For our behavioral cloning baseline, 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.
hy perpparaeeeerr discriminator optimizer discriminator learning rate discriminator batch size discriminator update frequency discriminator training iterations
value
Adam
3e-4
100
32
500

---

Published as a conference paper at ICLR 2022
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 reward computed, which makes the algorithm very slow for longer runs. To make tractable, we we only computed the kernel for 8 points closest the given state-action pair in the replay buffer and for points the expert dataset. The data structure used to find the nearest 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 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 I in the main paper to what is happening during learning, not just at the end.
expert
ILR
GAIL
GMMIL
SQIL
Hopper
Ant
Walker
HalfCheetah
16 episodes
2000
.000
2000
150
1300
7500
1000
2.00
8 episodes
2000
20:22
300
300
-020
0.000
500.00
400.04
episodes
1300
19V9
2000K4
2.001-
episode
1500
3.00
1/2 episode
70:0
1800
2.00
0.200
1/4 episode
2000
1300
1506
330
800
20000
300000
8200
6.00
20.000
20000
12

---

Published as a conference paper at ICLR 2022
1/8 episode
2103
2003
-207
1/16 episode
2140
2004
2000
1100
2.40
6.00
200.00
20000W
500,00
0.000
300000
20000
540000
1/32 episode
2120
2:00
1900
-107
1000
500
1/64 episode
1/128 episode
2450
2500
0.00
12:5
20008
300G
0.505
J.0000
200000
1/512 episode 1/256 episode
2.00
2000
2000
1300
1100
1230
1800
1.00
500
-080
C 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
Om 17s
SQIL
94m 39s
ILR
99m 16s
GAIL
213m 56s
GMMIL
448m 42s
Behavioral Cloning (BC) is the fastest, because does not have to do any interaction with the
environment (it does, however, produce policy with the worst performance). SQIL and ILR have
13

---

Published as a conference paper at ICLR 2022
comparable runtime, dominated by the complexity of simulating the environment. GAIL is slower because 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 Lemmal 7 By setting d' = v, follows that [t] Ep, [o] S for all u. Therefore
p [o] px [v]] I for all For any M C X on the right-hand side of equation 3 we can instantiate v(xr) = { E MJ. completing the proof.
Proof of Lemma
2
We have
Ep [b] - pp | =
= - = ll - p2ll1-
Here, the first inequality follows because elements of are in the interval [0, 1]. The statement the lemma follows from the property || P2llTV le P2ll1-
Proof of Lemma 3 By Theorem 4.9 in the book by Levin al. (017)). there constants C O and 10 such that max, [s() PE P3 ll I Ca Defining o (s, a) (I(5") (())))) we have max, 1188 p ||TV S Ca', where we used the fact that the expert policy is deterministic so that || -p I = [| P - - ITv. The mixing time of the chain Tmix defined as the smallest so that max, (1() PE P ITV S
is then bounded as
Tmix loga C loga (4).
remains to show that, for any probability distribution Pr, we have Ee 1pp1 PE - 2 < 27mix-
Define d(t) = supp 1l P/- - P5llyv. By equation 4.35 in the book by Levin et al. 2017 we have
d(LTmix) S -
(20)
We can now write
0
00
Σ llr t=
PE
S
d(t)
d(Tmix [l/Tmix)
Tmkk
t=0
where the first inequality follows from the definition of d((), the second one from the fact that
d(l') & d(l) for L' 2 and the last from equation 20 We can rewrite the right-hand side further, giving
8
2 [/ax
Tmix Σ 2- 2T
t=0
Proof of Lemmal Consider the imitation learner's trajectory of length T. We will now consider sub-sequee sequences where the agent agrees with the expert. Denote by Mr the number of such sequences of length f. Denote by Vri the per-step extrinsic reward obtained by the agent in the ith sequence of length f.
Assuming the worst reward states which not in any of the sequences (i.e. where the agent disagrees with the expert), the total extrinsic return Jr along the trajectory is at least Ms PiL Dividing by the sequence length, the per-step extrinsic
Σ. EM fri,é = Ee LM Me Ed reward is at least
JT T
Me V.s.
(21)
14

---

Published as a conference paper at ICLR 2022
Denote by A
1 Mr
E
pice
M2 E EM V p(af) the difference between the average extrinsic
reward obtained in sequences of length l and its expected value, where we denoted by p(s{) the initial state distribution among sequences of length f. We can now re-write equation 21 as:
JT T
EM M
Me
VE p(sf)
Ee
LM Ae.
(22)
Using Lemma 6, we can re-write this further
JT
2 E Liie E [R] 7 4mix)
LiMe -e
D
(23)
T
Σ N E [R]]
[1] Ee Mr 4Tmix
Ee
LM,
DE-
(24)
Denote by B the number of timesteps the imitation learner disagrees with the expert. Observe that we have Ee Mr T
T < B+1 since bad timesteps can partition the trajectory into at most B + 1 sub-sequences and 2nd2, Mr is the total number of sub-sequences. This gives
JI T
2
EM
E 8 [
B+1 4Tii
EMz A
(25)
Now, using the fact that the imitation learner policy is ergodic, we can take limits as T - cc. The left hand side converges to E,' [R] with probability one. On the right-band side. Σe EM, T (the fraction with probability
of time the imitation learner agrees with the expert) converges to Ep, [Rmd]] converges to - E [Rind] with probability one.
one. Using ergodicity again, B+1 T
It remains to prove that the eтror term E, LMr A. converges to zero with probability one. First, T
we will show that, for every L, either Mt is always zero, i.e. the streak length & does not occur in sub-sequences of any length or Mt - oo as T - cc. Indeed, the chain is ergodic, which means that, we traversed 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 Mr by N Lox. Moreover, let
us call the set of with Mj > 00 as T + DC with Loo. We have:
E1EL_
EM A. ESEN-Lo
EM MM S supreL.. De. T
(26)
The second term in the equals zero with because of the definition of Loc. The term supte A converges to zero with probability one by the law of large numbers, where we use the fact that Mj as T for M₂ Toc.
15


Reviews:
[{"review_id": "aJikmfMu8lR", "reviewer": "Reviewer_VY5r", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. The paper shows that imitation learning (IL) may be reduced to RL with stationary reward for deterministic experts. The analysis provides the theoretical grounding for several existing IL methods. The paper also contributes the connection between the stationary reward to minimizing f-divergence typically seen in adversarial IL, proving that the stationary reward minimizes total variation distance.\n\n2. The proof is clear, well motivated and easy to follow.\n\n3. The experiment studies an important aspect of IL, which is the relationship between the amount of expert data and the IL's performance.\n\nWeakness:\n1. Similar to previous works, the practical algorithm uses soft reward (1 - min L_2 distance) to avoid reward sparsity. While a very reasonable choice, the soft reward violates the critical assumption of deterministic expert. Could the authors explain the implications of the soft reward on the theoretical results?\n\n2. The empirical evaluation is limited, with several related questions unaddressed. For instance, the SAC expert appears to be rather weak (in terms of its performance) across different environments. It is unclear whether similar patterns would be observed if the expert matches the level of the performance observed in previous works (e.g. https://github.com/berkeleydeeprlcourse/homework/tree/master/hw1/experts). Another question is how the expert is trained has any impact on the IL performance. For instance, SAC implementation typically directly constraint the range of the action, while a Gaussian expert only clips the action as a post-processing step. In my experiences, these details have quite significant impacts on IL's performance and I hope the authors could expand on the experiments to further validate their theoretical results.\n\nQuestions:\n1. Comparison between Wang et al. 2019 vs the 1-min L_2 distance reward. Could the authors motivate why the latter reward is used and how it compares to Wang et al. 2019?\n\n2. Could the authors further elaborate on the assumption of the deterministic expert? E.g. How much does it matter in the practical algorithm? Is it even possible to differentiate between stochastic vs deterministic one from limited training data?", "summary_of_the_paper": "The paper contributes a theoretical analysis of imitation learning (IL) under deterministic experts. The paper shows that IL in this setting can be reduced to RL with a stationary reward, and the stationary reward minimizes the total variation distance between the expert and the learner. Several empirical experiments were presented to validate the theoretical analysis.", "summary_of_the_review": "The paper shows that, for deterministic experts, imitation learning (IL) could be reduced to RL with a stationary reward. The paper thus provides theoretical grounding for several existing works. In addition, the paper also draws connection with f-divergence minimization commonly found in adversarial IL. On the other hand, the empirical results are consistent with those from existing works, but are limited in its scope. Despite the flaws, I think the work is still interesting to the community. It would be nice if the paper could include more experiments to further support the theoretical analysis.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XzzUZZKEnbT", "reviewer": "Reviewer_XK3g", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of using reinforcement learning to imitate expert behavior is simple to execute compared to other imitation learning methods. I have a concern regarding the sparse reward function used in this paper. When training a reinforcement learning model, the sparse reward becomes problematic when you apply RL algorithm to solve it. Although the better intrinsic reward leads to better extrinsic reward, it is still troublesome to get a good policy by any reinforcement learning algorithm with this sparse reward function. This makes the result less useful than just applying other comparison methods. Could you give more explanation on this?\nIn term of computation time, the sparse reward can cause problem of bad convergence rate. It is much clearer if you can provide comparison of computation time of different algorithms in the experiment section. \nOverall, this paper is well written and very clear to readers. The result is promising and interesting from a theoretical point of view.\n", "summary_of_the_paper": "This paper considers imitation learning problem which aims at obtaining a policy that imitate expert behavior. Authors considers using reinforcement learning with a stationary reward constructed by expert datasets. Through theoretical analysis, the corresponding imitation policy is proved to achieve high expected per-step intrinsic reward and extrinsic reward. The difference between the expert policy and the imitation policy is bounded with a high probability. Some empirical experiments are performed on continuous control tasks. The results show this method is comparable with other algorithms while the algorithm is simpler. ", "summary_of_the_review": "This paper provides rigorous analysis for using reinforcement learning in imitation learning. The result is novel and shows the potential to accomplish imitation learning in a straightforward way. The intrinsic reward function reduced by the expert dataset is simple to construct. By setting a constant one reward for matching the demonstrated action in a demonstrated state, any reinforcement learning algorithm can provide policy for such a MDP problem. The result in this paper gives intuition of how this method performs in terms of expected return. And sufficient experimental results are shown to verify their theoretical results.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FcpFHthuyHe", "reviewer": "Reviewer_TFjU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is generally well written and easy to follow; however, the structure is sometimes unusual. The proofs would be easier to follow if the authors moved Lemmas from Appendix C & D into the main body while moving some of the detailed proofs from the main body into the Appendix.\n\nThe derived bound is non-trivial, but it is unclear how significant it is. The main issue lies in the assumption on the amount of data that is required which is linear (with a factor > 1) in the squared size of the state-space (note that the bound remains large even if \\delta is set to 1). Such a large amount of expert data is required since rewarding agreement is not a valid strategy when expert data is sparse: imagine a sub-sampled expert trajectory where the agent has the capability to return to previously seen states. In a more typical distribution-matching objective, the agent has to visit all the demonstration states and thus still has to complete the trajectory. In the objective proposed by the authors, the agent can maximize reward by returning to the same demonstration-state repeatedly. Naturally, if demonstrations are available in all states and the agent’s representational capacity is unlimited, then maximizing agreement is trivially optimal. The author’s bound does not require demonstrations to be available in all states and may thus be useful; however, the required amount of expert data is extremely large and no statement can be made if less data is available.\n\nIn the related works section, the authors claim that the method is minimizing the GAIL-objective. This is misleading; the GAIL objective is equivalent to minimizing the JS divergence to the expert histogram for all choices of N while the proposed method only minimizes TV distance and thus JS divergence if N is large enough. \n\nFor the empirical evaluation, the authors use an L2-distance as a stand-in for the reward used in the analysis. This is necessary as the reward is undefined in continuous state-action spaces (similarly, it will be too sparse in large discrete state-action spaces), but the implications of that heuristic are not explored in the paper. It would be good if the authors could add motivation and discussion for this form of the reward. The results are very positive, but it is unclear whether they are due to the theoretical properties of the algorithm or due to the particular nature of the mujoco walkers. Since the reward is a part of the observation-space in these domains, using simple heuristics like squared distance can plausibly lead to high performance; however, this would not generalize to other domains. It is furthermore problematic that the hardest benchmark task, humanoid, is missing as the given baseline algorithms have no problem solving it. Finally, the reported numbers for behavioral cloning are significantly worse than what has previously been reported in the literature.\n", "summary_of_the_paper": "The authors propose an algorithm for imitation learning which rewards the agent for observing state-action pairs that are part of the demonstration-set. The main contribution of the paper is the theoretical analysis which shows that the algorithm, given sufficient expert data, matches the expert’s occupancy distribution and expected reward. The proof comes in three parts: first, the authors relate expert rollouts to the limiting distribution of the expert’s policy. Second, the authors put a probabilistic bound on the expected agreement with expert-data based on the mixing time of the agent. Finally, the authors use this bound on expected agreement to bound the difference in expected extrinsic reward. The authors also provide an empirical evaluation in standard control benchmarks.", "summary_of_the_review": "The proposed bound is non-trivial and potentially useful; however, it would benefit from additional context to show whether it is truly significant. The empirical results are interesting, but rely on a heuristic that is not well-motivated and may be domain specific.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5xAss3Drgzf", "reviewer": "Reviewer_7ezW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper includes potentially interesting results. Some comments that can improve the paper are given below. \n1) In this paper, average rewards are considered. Is there any reason to consider the average reward MDP instead of discounted MDP, which is more widely used?\n2) It is not clear what the norm || ||_{TV} means.\n3) It would be better to discuss what kinds of RLs can be used in Proposition 1. It is not clear in the current paper. \n4) It would be better if the definition of intrinsic reward and extrinsic reward is explained in this paper. \n5) It is not clear how the imitation learner can learn the expert policy from the intrinsic reward in section 3. \nIt would be better if the process is explained in more details.\n6) In the experiment, it is not clear how the comaprative analysis is done. Because the authors did not develop new algorithms, \nit would be better to explain details of the comparative analysis. \n 7) Overall, the organization of the paper can be improved further to more clearly deliver the ideas by adding more detailed backgrounds. ", "summary_of_the_paper": "In this paper, the authors show that, for deterministic experts, imitation learning can be done by reduction\nto reinforcement learning with a stationary reward. theoretical analysis both\ncertifies the recovery of expert reward and bounds the total variation distance\nbetween the expert and the imitation learner, showing a link to adversarial imitation\nlearning. Experiments are given to confirm that the reduction works well in\npractice for continuous control tasks.\n", "summary_of_the_review": "In sum, the paper seems to contain potentially interesting results. \nThe overall organization and presentation can be further improved to improve the readability of the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides theoretical bounds for imitation learning with rewards (algorithm from Wang et al. (2019)). The bounds/proofs are highly novel and a very interesting contribution to the community, even though they are a lot more conservative than what is observed in practice. All reviewers agree on this point.
It is laudable that the authors also additionally provide an experimental evaluation. After the revision and the discussion, quite a few of the reviewers are still not 100% convinced about them, on the one hand as they would have liked to see more tasks, and on the other hand due to concerns about the reward relaxation (i.e., doesn't match the assumptions in the theorems any longer) which is required for experiments on standard benchmarks.
In the final answer the authors provide evidence that there is no big discrepancy, which is good enough (given that there don't seem to be any alternatives to get around this issue, except removing the experimental section altogether, which would be undesirable). Please clearly point out those limitations of the experiments in the paper and also incorporate this evidence.
Decision: Accept (Poster)