summaries: 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. 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.  In this paper, the authors show that, for deterministic experts, imitation learning can be done by reduction to reinforcement learning with a stationary reward. 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. Experiments are given to confirm that the reduction works well in practice for continuous control tasks.  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.
abstractText: 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.
references.authors: Pieter Abbeel Andrew Y Ng
references.title: Apprenticeship learning via inverse reinforcement learning
references.venue: In Proceedings of the twenty-first international conference on Machine learning,
references.authors: Christopher G Atkeson Stefan Schaal
references.title: Robot learning from demonstration
references.venue: In ICML,
references.authors: Yuri Burda Harrison Edwards Amos Storkey Oleg Klimov
references.title: Exploration by random network distillation
references.venue: arXiv preprint arXiv:1810.12894,
references.authors: Benjamin Ellenberger
references.title: Pybullet gymperium. https://github.com/benelot/ pybullet-gym, 2018–2019
references.authors: Eugene A Feinberg Adam Shwartz
references.title: Handbook of Markov decision processes: methods and applications, volume 40
references.venue: Springer Science & Business Media,
references.authors: Chelsea Finn Sergey Levine Pieter Abbeel
references.title: Guided cost learning: Deep inverse optimal control via policy optimization
references.venue: In International Conference on Machine Learning,
references.authors: Seyed Kamyar Seyed Ghasemipour Richard Zemel Shixiang Gu
references.title: A divergence minimization perspective on imitation learning methods
references.venue: In Conference on Robot Learning,
references.authors: Tuomas Haarnoja Aurick Zhou Pieter Abbeel Sergey Levine
references.title: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor
references.venue: In International conference on machine learning,
references.authors: Jonathan Ho Stefano Ermon
references.title: Generative adversarial imitation learning
references.venue: In Advances in neural information processing systems,
references.authors: Borja Ibarz Jan Leike Tobias Pohlen Geoffrey Irving Shane Legg Dario Amodei
references.title: Reward learning from human preferences and demonstrations in atari
references.venue: In Advances in neural information processing systems,
references.authors: Kee-Eung Kim Hyun Soo Park
references.title: Imitation learning via kernel mean embedding
references.venue: In Thirty-Second AAAI Conference on Artificial Intelligence,
references.authors: Yunzhu Li Jiaming Song Stefano Ermon
references.title: Infogail: Interpretable imitation learning from visual demonstrations
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Andrew Y Ng Stuart J Russell
references.title: Algorithms for inverse reinforcement learning
references.venue: In Icml,
references.authors: Daniel Paulin
references.title: Concentration inequalities for markov chains by marton couplings and spectral methods
references.venue: Electronic Journal of Probability,
references.authors: Martin L Puterman
references.title: Markov decision processes: discrete stochastic dynamic programming
references.authors: Siddharth Reddy Anca D. Dragan Sergey Levine
references.title: SQIL: Imitation learning via reinforcement learning with sparse rewards
references.venue: In International Conference on Learning Representations,
references.authors: Stéphane Ross Drew Bagnell
references.title: Efficient reductions for imitation learning
references.venue: In Proceedings of the thirteenth international conference on artificial intelligence and statistics,
references.authors: Stéphane Ross Geoffrey Gordon Drew Bagnell
references.title: A reduction of imitation learning and structured prediction to no-regret online learning
references.venue: In Proceedings of the fourteenth international conference on artificial intelligence and statistics,
references.authors: Wen Sun Anirudh Vemula Byron Boots Drew Bagnell
references.title: Provably efficient imitation learning from observation alone
references.venue: In International Conference on Machine Learning,
references.authors: Ruohan Wang Carlo Ciliberto Pierluigi Vito Amadori Yiannis Demiris
references.title: Random expert distillation: Imitation learning via expert policy support estimation
references.venue: In International Conference on Machine Learning,
references.authors: Tianhao Zhang Zoe McCarthy Owen Jow Dennis Lee Xi Chen Ken Goldberg Pieter Abbeel
references.title: Deep imitation learning for complex manipulation tasks from virtual reality teleoperation
references.venue: IEEE International Conference on Robotics and Automation (ICRA),
references.authors: Paulin
references.title: 2015), where the constant 4.5 appears by plugging in equation
references.venue: ρS ‖TV. Proof of Lemma
sections.text: 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.
sections.heading: 1 INTRODUCTION
sections.text: 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.
sections.heading: 2 PRELIMINARIES
sections.text: 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π. In the theoretical part of the paper, we treat MDPs with finite state and action spaces. Given a starting state s1 of the MDP, and a policy π, the limiting distribution over states is defined as
  ρπS(s) = 1(s1) > lim N→∞
  1
  N N∑ i=0 P iπ, (1)
  where 1(s1) denotes the indicator vector. We adopt the convention that the subscript S indicates a distribution over states and a 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, we drop the dependence on the initial state from the notation. The expected per-step reward of π is defined as
  V π = lim N→∞ Eπ [JN/N | s1] = EρπR(s, a), (2)
  where JN = ∑N t=1R(st, at) 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 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), where we dropped the dependency on the initial state by ergodicity. Consider a finite trajectory s1, a1, s2, a2, . . . , sN , aN . Denote by ρ̂(s, a) = 1N ∑N t=1 1 ((s, a) = (st, at)) the histogram (empirical distribution) of data seen along this
  trajectory and denote by ρ̂S(s) = 1N ∑N t=1 1 (s = st) the corresponding histogram over the states. Denote by D the support of ρ̂, i.e. the set of state-action pairs visited by the expert.
  Total Variation Consider probability distributions defined on a discrete set X . The total variation distance between distributions is defined as
  ‖ρ1 − ρ2‖TV = sup M⊆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 for any vector v ∈ [0, 1]|X| it holds that Eρ1 [v] − Eρ2 [v] ≤ , then we have ‖ρ1 − ρ2‖TV ≤ . Lemma 2. If ‖ρ1 − ρ2‖TV ≤ , then we have |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)
  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, governed by constants, commonly called C and α. 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. There are constants C > 0 and α ∈ (0, 1) such that max′s ‖1(s′)>P tE − ρES ‖TV ≤ Cαt. Moreover, defining ρ̃s ′
  t (s, a) = (1(s ′)>P tE)(s)πE(a|s), we have maxs′ ‖ρ̃s
  ′
  t − ρE‖TV ≤ Cαt. The mixing time of the chain τmix, defined as the smallest t so that maxs′ ‖1(s′)>P tE − ρES ‖TV ≤ 14 is bounded as τmix ≤ logα C + logα(4).
  McDiarmid’s inequality is a tool for measuring how fast functions of several random variables approach their expected value. We now recall a version of the inequality used when the variables form a Markov chain. The proof is given in Appendix D.
  Lemma 4. Consider a Markov Chain s1, s2, . . . , sN . For any coefficients ci and a function f so that fs(s1, . . . , sN )− fs(s′1, . . . , s′N ) ≤ ∑N i=1 ci1(si 6= s′i) for all s1, . . . , sN , s′1, . . . , s′N , we have
  P (|f(s1, s2, . . . , sN )− Ef(s1, s2, . . . , sN )| ≤ ) ≥ 1− 2 exp { −
  2
  4.5τmix‖c‖22
  } ,
  where τmix is the mixing time of the chain.
sections.heading: 3 IMITATION LEARNING BY REINFORCEMENT LEARNING
sections.text: Algorithm To perform imitation learning, we first obtain an expert dataset D and construct an intrinsic reward
  RI(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 we have N ≥ max { D η , log ( 2|S| δ ) |S|2 Bη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)
  For brevity, we introduced D = 2C(1 + 2C1−α )(1 − α) −1 and B = 4.5τmix(1 + 2C1−α ) 2, where the constants C, α and τmix reflect the mixing time of the expert policy and are defined in Section 2. Moreover, with the same probability, for any extrinsic reward function, the imitation learner achieves expected per-step extrinsic reward of at least
  EρIRE ≥ EρERE − η. (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.
sections.heading: 4 PROOF
sections.text: 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.
sections.heading: 4.1 MIXING IN MARKOV CHAINS
sections.text: 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 McDiarmid’s inequality for Markov chains, which we introduce in Section 2. Lemma 5. The total variation distance between the expert distribution and the expert histogram ρ̂ based on N samples can be bounded as
  ‖ρE − ρ̂‖TV ≤ + C/N 1− αN
  1− α (9)
  with probability at least 1− 2|S| exp { − 4
  2N 4.5|S|2τmix
  } (where the probability space is defined by the
  process generating the expert histogram).
  Proof. We first prove the statement for histograms over the states. Recall the notation ρ̂S = 1 N ∑N t=1 1 (st = s). Recall that we denote the stationary distribution (over states) of the Markov chain induced by the expert with ρES .
  Define fs(s1, . . . , sN ) = 1N ∑N i=1 1(si = s). For two state sequences s1, . . . , sN and s ′ 1, . . . , s ′ N
  we have fs(s1, . . . , sN ) − fs(s′1, . . . , s′N ) ≤ 1N ∑N i=1 1(si 6= s′i). Using this property, instantiate Lemma 4 with ci = 1/N for each state separately with fs as above. Using the fact that
  fs(s1, . . . , sN ) = ρ̂S(s), this gives us P (|ρ̂S(s) − Eρ̂S(s)| ≤ ′) ≥ 1 − 2 exp { − ′2N 4.5τmix } , where
  we introduced the notation Eρ̂S(s) = 1/N ∑N−1 i=0 (1(s1) >P iE)(s). Applying the union bound
  over all states, we have P (∀s. |ρ̂S(s) − Eρ̂S(s)| ≤ ′) ≥ 1 − 2|S| exp { − ′2N 4.5τmix } . This implies
  P (‖ρ̂S − Eρ̂S‖1 ≤ |S| ′) ≥ 1− 2|S| exp { − ′2N 4.5τmix } . Introducing ′′ = |S| ′, this is equivalent to
  P (‖ρ̂S − Eρ̂S‖1 ≤ ′′) ≥ 1− 2|S| exp { −
  ′′2N
  4.5|S|2τmix
  } . (10)
  We now quantify the distance between Eρ̂ and the stationary distribution. ‖Eρ̂S − ρES ‖1 = ∥∥∥(1/N∑N−1i=0 1(s1)>P iE)− ρES ∥∥∥
  1 = (1/N) ∥∥∥∑N−1i=0 (1(s1)>P iE − ρES )∥∥∥ 1
  ≤ (1/N) ∑N−1 i=0 ∥∥(1(s1)>P iE − ρES )∥∥1 ≤ (1/N)∑N−1i=0 2Cαi = (2C/N) 1− αN
  1− α . (11)
  Here, the last inequality follows from Lemma 3 and the identity ‖ρ1 − ρ2‖TV = 12‖ρ1 − ρ2‖1. We combine equation 10 and equation 11 using the triangle inequality. Using the property ‖ρ1−ρ2‖TV = 1 2‖ρ1 − ρ2‖1 again and setting = ′′/2, we obtain
  ‖ρES − ρ̂S‖TV ≤ + C/N 1− αN
  1− α (12)
  with probability at least 1 − 2|S| exp { − 4
  2N 4.5|S|2τmix
  } . Since the expert policy is deterministic, the
  total variation distance between the distributions of state-action tuples and states is the same, i.e. ‖ρES − ρ̂S‖TV = ‖ρE − ρ̂‖TV.
sections.heading: 4.2 HIGH EXPECTED INTRINSIC PER-STEP REWARD IS ACHIEVABLE
sections.text: 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 6. Generating an expert histogram with N points, with probability at least 1 − 2|S| exp { − 4
  2N 4.5|S|2τmix
  } , we obtain a dataset such that a policy πI maximizing the intrinsic reward
  RI(s, a) = 1((s, a) ∈ D) satisfies EρI [RI ] ≥ 1 − − C/N 1−α N
  1−α , where we used the shorthand notation ρI = ρπI to denote the state-action distribution of πI .
  Proof. We invoke Lemma 5 obtaining ‖ρE − ρ̂‖TV ≤ + C/N 1−α N
  1−α with probability as in the statement of the lemma. First, we prove∑
  s,a ρ E(s, a)1[ρ̂(s, a) = 0] ≤ + C/N 1−α
  N
  1−α , (13)
  by setting ρ1 = ρE , ρ2 = ρ̂ and M = {(s, a) : ρ̂(s, a) = 0} in equation 3. Combining
  1 = ∑ s,a ρ E(s, a) = ∑ s,a ρ E(s, a)1[ρ̂(s, a) = 0] + ∑ s,a ρ E(s, a)1[ρ̂(s, a) > 0] (14)
  and equation 13, we obtain∑ s,a ρ E(s, a)1[ρ̂(s, a) > 0] ≥ 1− − C/N 1−α N 1−α , (15)
  which means that the expert policy achieves expected per-step intrinsic reward of at least 1 − − C/N 1−α N
  1−α . This lower bounds the expected per-step reward obtained by the optimal policy.
sections.heading: 4.3 MAXIMIZING INTRINSIC REWARD LEADS TO HIGH PER-STEP EXTRINSIC REWARD
sections.text: 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 l consecutive steps. Lemma 7. Assume an agent traverses a sequence of l state-action pairs, in a way consistent with the expert policy. Denote the expert’s expected extrinsic per-step reward with EρERE . Denote by ρ̃p1t (s, a) = (p > 1 P t E)(s)πE(a|s) the expected state-action occupancy at time t, starting in state distribution p1. The per-step extrinsic reward Ṽ lp1 of the agent in expectation over realizations of the sequence satisfies
  Ṽ lp1 = ∑ s,a ((∑l−1 t=0 1 l ρ̃ p1 t (s, a) ) RE(s, a) ) ≥ EρERE − 1l 2C 1−α . (16)
  Proof. Invoking Lemma 3, we have that ‖ρ̃p1t − ρE‖TV ≤ Cαt. Invoking Lemma 2, we have that EρERE−Eρ̃p1t RE ≤ 2Cα
  t for any timestep t. In other words, the expected per-step reward obtained in step t of the sequence is at least EρERE − 2Cαt. The per-step reward in the sequence is at least
  Ṽ lp1 ≥ 1 l ∑l−1 i=0(EρERE − 2Cαi) = EρERE − 2 lC ∑l−1 i=0 α i
  = EρERE − 2lC 1−αl 1−α ≥ EρERE − 2 lC 1 1−α .
  In Lemma 7, 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 8. For any extrinsic reward signal RE bounded in [0, 1], an imitation learner which attains expected per-step intrinsic reward of EρIRI also attains extrinsic per-step reward of at least
  EρIRE ≥ (EρIRI)(EρERE)− 2C
  1− α (1− EρIRI),
  with probability one, where EρERE is the expected per-step extrinsic reward of the expert.
  We provide the proof in Appendix D.
sections.heading: 4.4 BRINGING THE PIECES TOGETHER
sections.text: We now show how Lemma 6 and Lemma 8 can be combined to obtain Proposition 1 (stated in Section 3).
  Proof of Proposition 1. We use the assumption that N ≥ max { 2C(1 + 2C
  1− α )(1− α)−1 1 η , log ( 2|S| δ ) 4.5|S|2τmixη−2(1 + 2C 1− α )2 } . (17)
  We will instantiate Lemma 6 with
  = η
  2(1 + 2C1−α ) . (18)
  Equations 17 and 18 imply that N ≥ log (
  2|S| δ ) 4.5|S|2τmixη−2(1 + 2C1−α ) 2 =
  log (
  2|S| δ ) 4.5|S|2τmix(2 )−2. We can rewrite this as 4 2N 4.5|S|2τmix ≥ log 2|S| δ , which implies
  − 4 2N
  4.5|S|2τmix ≤ log δ 2|S| . This implies that δ ≥ 2|S| exp { − 4 2N
  4.5|S|2τmix
  } . (19)
  Moreover, using equation 17 again, we have that N ≥ 2C(1 + 2C1−α )(1− α) −1 1
  η . This is equivalent to CN 1 1−α ≤ 1 2
  η 1+ 2C1−α . Using equation 18, we obtain + CN 1 1−α ≤ η 1+ 2C1−α , equivalent to ( +
  C N 1 1−α )(1 + 2C 1−α ) ≤ η, which implies ( + C N 1−αN 1−α )(1 + 2C 1−α ) ≤ η. Rewriting this gives
  κ ( 1 + 2C
  1− α
  ) ≤ η, (20)
  where we use the notation κ = + C/N 1−α N
  1−α .
  We first show equation 8, which states that we are able to recover expected per-step expert reward. Invoking Lemma 6 and using equation 19, 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 8, this implies achieving extrinsic reward of at least
  EρIRE ≥ EρERE(1− κ)− 2Cκ
  1− α .
  This implies
  EρERE − EρIRE ≤ EρERE − EρERE(1− κ) + 2Cκ
  1− α = κEρERE +
  2Cκ 1− α ≤ κ+ 2Cκ 1− α ≤ η,
  where the last inequality follows from equation 20. Since this statement holds for any extrinsic reward signal RE , we obtain the total variation bound by invoking Lemma 1, getting ‖ρE − ρI‖TV ≤ η.
sections.heading: 5 RELATED WORK
sections.text: 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 have ‖ρE − ρI‖TV ≥ DJS(ρE , ρI). 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 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 12 (ρ
  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.
sections.heading: 6 EXPERIMENTS
sections.text: In this section, we empirically 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 here. Instead, we focus on two aspects: the amount of expert data needed to achieve good imitation quality 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 R′I(s, a) = 1−min(s′,a′)∈D dL2((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. While we can no longer theoretically claim that optimizing this upper bound guarantees the recovery of expert reward (as in Lemma 8), this property still holds in practice, as verified below. In other settings, 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 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.
sections.heading: 7 CONCLUSIONS
sections.text: 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.
sections.heading: 8 ETHICS STATEMENT
sections.text: 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.
sections.heading: 9 REPRODUCIBILITY STATEMENT
sections.text: Our main contribution is Proposition 1, for which we provided a complete proof. The only results we rely on are generic properties of the Total Variation distance and of Markov chain mixing, which we recall in our notation in Section 2. We provide citations of references where they are derived in Appendix D. Our experimental setup is described in detail in appendix A. Moreover, we make the source code available to reviewers.
sections.heading: A DETAILS OF EXPERIMENTAL SETUP
sections.text: 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 repository1. 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 of 0.01 was used for exploration.
  1https://github.com/takuseno/d4rl-pybullet
  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
  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.
sections.heading: B PLOTS MEASURING SAMPLE EFFICIENCY
sections.text: 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
  16 ep
  is od
  es
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  0.00K 250.00K 500.00K
  1000
  500
  0
  500
  1000
  1500
  2000
  8 ep
  is od
  es
  0.00K 250.00K 500.00K
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  0.00K 250.00K 500.00K 1000
  500
  0
  500
  1000
  1500
  2000
  4 ep
  is od
  es
  0.00K 250.00K 500.00K
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  0.00K 250.00K 500.00K 1500 1000 500
  0 500
  1000 1500 2000
  1 ep
  is od
  e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  0.00K 250.00K 500.00K 1500 1000 500
  0 500
  1000 1500 2000
  1/ 2
  ep is
  od e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  0.00K 250.00K 500.00K
  1000
  500
  0
  500
  1000
  1500
  2000
  1/ 4
  ep is
  od e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  0.00K 250.00K 500.00K
  1000 500
  0 500
  1000 1500 2000
  1/ 8
  ep is
  od e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  0.00K 250.00K 500.00K
  1000
  500
  0
  500
  1000
  1500
  2000
  1/ 16
  ep is
  od e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  0.00K 250.00K 500.00K
  1000
  0
  1000
  2000
  1/ 32
  ep is
  od e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  0.00K 250.00K 500.00K
  1000
  0
  1000
  2000
  1/ 64
  ep is
  od e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  0.00K 250.00K 500.00K
  1000
  0
  1000
  2000
  1/ 12
  8 ep
  is od
  e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  0.00K 250.00K 500.00K
  1000
  0
  1000
  2000
  1/ 25
  6 ep
  is od
  e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  0.00K 250.00K 500.00K
  1000
  0
  1000
  2000
  1/ 51
  2 ep
  is od
  e
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  2000
  2500
  0.00K 250.00K 500.00K 0
  500
  1000
  1500
  0.00K 250.00K 500.00K
  1000
  0
  1000
  2000
sections.heading: C RUNTIME COMPARISON OF DIFFERENT ALGORITHMS
sections.text: We have run all algorithms from the paper in a controlled computational environment (no other processes running on the machine). We ran the imitation learning algorithms 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.
sections.heading: D ADDITIONAL PROOFS
sections.text: Proof of Lemma 1. By setting v′ = 1− v, it follows that Eρ2 [v]− Eρ1 [v] ≤ for all v. Therefore |Eρ1 [v] − Eρ2 [v]| ≤ for all v. For any M ⊆ X on the right-hand side of equation 3, we can instantiate v(x) = 1(x ∈M), completing the proof.
  Proof of Lemma 2. We have |Eρ1 [v]− Eρ2 [v]| = | ∑ x(ρ1(x)− ρ2(x))v(x)| ≤ | ∑ x(ρ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 = 12‖ρ1 − ρ2‖1.
  Proof of Lemma 3. For the statement about distributions over states, see Theorem 4.9 in the book by Levin et al. (2017). For the statement about distributions over state-action pairs, we use the fact that the expert policy is deterministic so that ‖ρ̃s′t − ρE‖TV = ‖1(s′)>P tE − ρES ‖TV.
  Proof of Lemma 4. Instantiate Corollary 2.11 of Paulin et al. (2015), where the constant 4.5 appears by plugging in equation (2.9) of Paulin et al. (2015).
  Proof of Lemma 8. Consider the imitation learner’s trajectory of length T . We will now consider sub-sequences where the agent agrees with the expert. Denote by Ml the number of such sequences of length l. Denote by V̂ i,l the per-step extrinsic reward obtained by the agent in the ith sequence of length l.
  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∑ l l ∑Ml i=1 V̂ i,l = ∑ l lMl 1 Ml ∑Ml i=1 V̂
  i,l. Dividing by the sequence length, the per-step extrinsic reward is at least
  JT T ≥ ∑ l lMl T 1 Ml ∑Ml i=1 V̂ i,l. (21)
  Denote by ∆l = ∣∣∣ 1Ml ∑Mli=1 V̂ i,l − 1Ml ∑Mli=1 Ṽ lp(sl1)∣∣∣ the difference between the average extrinsic reward obtained in sequences of length l and its expected value, where we denoted by p(sl1) the initial state distribution among sequences of length l. We can now re-write equation 21 as:
  JT T ≥ ∑ l lMl T 1 Ml ∑Ml i=1 Ṽ l p(sl1) − ∑ l lMl T ∆l. (22)
  Using Lemma 7, we can re-write this further
  JT T ≥ ∑ l lMl T ( EρERE − 1l 2C 1−α ) − ∑ l lMl T ∆l (23)
  = ∑ l lMl T EρERE − ∑ l Ml T 2C 1−α − ∑ l lMl T ∆l. (24)
  Denote by B the number of timesteps the imitation learner disagrees with the expert. Observe that we have ∑ l Ml T ≤ B+1 T since B bad timesteps can partition the trajectory into at most B + 1
  sub-sequences and ∑ lMl is the total number of sub-sequences. This gives
  JT T ≥ ∑ l lMl T EρERE − B+1 T 2C 1−α − ∑ l lMl T ∆l. (25)
  Now, using the fact that the imitation learner policy is ergodic, we can take limits as T →∞. The left hand side converges to EρIRE with probability one. On the right-hand side, ∑ l lMl T (the fraction of time the imitation learner agrees with the expert) converges to EρIRI with probability one. Using ergodicity again, B+1T converges to 1− EρIRI with probability one.
  It remains to prove that the error term ∑ l lMl T ∆l converges to zero with probability one. First, we will show that, for every l, either Ml is always zero, i.e. the streak length l does not occur in sub-sequences of any length or Ml →∞ as T →∞. Indeed, the chain is ergodic, which means that, if we traversed a streak of length l, we have non-zero probability of returning to where the streak begun and then retracing it. Let us call the of set of all ls where Ml = 0 by N− L∞. Moreover, let us call the set of ls with Ml →∞ as T →∞ with L∞. We have:∑
  l∈L∞ lMl T ∆l + ∑ l∈N−L∞ lMl T ∆l ≤ supl∈L∞ ∆l. (26)
  The second term in the sum equals zero with because of the definition of L∞. The term supl∈L∞ ∆l converges to zero with probability one by the law of large numbers, where we use the fact that Ml →∞ as T →∞ for Ml ∈ L∞.