summaries: This paper presents a method for increasing the efficiency of sparse reward RL methods through a backward curriculum on expert demonstrations. The method in the paper is as follows: assuming access to expert demonstration and a resettable simulator, the start state of the agent in the beginning of training is sampled from end of demonstration (close to the rewarding state) where the task of achieving the goal is easy. Then gradually through a curriculum this is shifted backwards in the demonstration, making the task gradually harder.

summaries: The paper presents a strategy for solving sparse reward tasks with RL by sampling initial states from demonstrations. The method, Backplay, starts by sampling states near the end of a demonstration trajectory, so that the agent will be initialized to states near the goal. As training progresses, the initial state distribution is incrementally shifted towards earlier steps in the demonstration, until the agent is trained starting from the original initial state. The authors further provide an analysis of the sample complexity of this method on a simple MDP. The method is demonstrated on a maze navigation task and a challenging game Pommerman.

abstractText: Model-free reinforcement learning (RL) requires a large number of trials to learn a good policy, especially in environments with sparse rewards. We explore a method to improve the sample efficiency when we have access to demonstrations. Our approach, Backplay, uses a single demonstration to construct a curriculum for a given task. Rather than starting each training episode in the environment’s fixed initial state, we start the agent near the end of the demonstration and move the starting point backwards during the course of training until we reach the initial state. Our contributions are that we analytically characterize the types of environments where Backplay can improve training speed, demonstrate the effectiveness of Backplay both in large grid worlds and a complex four player zero-sum game (Pommerman), and show that Backplay compares favorably to other competitive methods known to improve sample efficiency. This includes reward shaping, behavioral cloning, and reverse curriculum generation.

authors:
Yusuf Aytar
Tobias Pfaff
David Budden
Tom Le Paine
Ziyu Wang
Nando de Freitas

title: Playing hard exploration games by watching youtube

venue: arXiv preprint arXiv:1805.11592,

authors:
Michael Bain
Claude Sommut

title: A framework for behavioural claning

venue: Machine intelligence,

authors:
Feryal Behbahani
Kyriacos Shiarlis
Xi Chen
Vitaly Kurin
Sudhanshu Kasewa
Ciprian Stirbu
João Gomes
Supratik Paul
Frans A Oliehoek
João Messias

title: Learning from demonstration in the wild

venue: arXiv preprint arXiv:1811.03516,

title: Cooperation under the shadow of the future: experimental evidence from infinitely repeated games

venue: American economic review,

authors:
Noam Brown
Tuomas Sandholm

title: Safe and nested subgame solving for imperfect-information games

venue: In Advances in Neural Information Processing Systems,

authors:
Cameron B Browne
Edward Powley
Daniel Whitehouse
Simon M Lucas
Peter I Cowling
Philipp Rohlfshagen
Stephen Tavener
Diego Perez
Spyridon Samothrakis
Simon Colton

title: A survey of monte carlo tree search methods

venue: IEEE Transactions on Computational Intelligence and AI in games,

authors:
Guan-Yu Chen
Laurent Saloff-Coste

title: On the mixing time and spectral gap for birth and death

venue: chains. arXiv preprint arXiv:1304.4346,

authors:
J. Clark
D. Amodei

title: Faulty reward functions in the wild

authors:
Abhishek Das
Satwik Kottur
José M.F. Moura
Stefan Lee
Dhruv Batra

title: Learning cooperative visual dialog agents with deep reinforcement learning

authors:
Hal Daumé
John Langford
Daniel Marcu

title: Search-based structured prediction

venue: Machine learning,

authors:
Ashley D Edwards
Laura Downs
James C Davidson

title: Forward-backward reinforcement learning

venue: arXiv preprint arXiv:1803.10227,

authors:
Carlos Florensa
David Held
Markus Wulfmeier
Pieter Abbeel

title: Reverse curriculum generation for reinforcement learning

venue: arXiv preprint arXiv:1707.05300,

authors:
Jakob N Foerster
Richard Y Chen
Maruan Al-Shedivat
Shimon Whiteson
Pieter Abbeel
Igor Mordatch

title: Learning with opponent-learning awareness

venue: arXiv preprint arXiv:1709.04326,

authors:
Yang Gao
Ji Lin
Fisher Yu
Sergey Levine
Trevor Darrell

title: Reinforcement learning from imperfect demonstrations

venue: arXiv preprint arXiv:1802.05313,

authors:
Anirudh Goyal
Philemon Brakel
William Fedus
Timothy Lillicrap
Sergey Levine
Hugo Larochelle
Yoshua Bengio

title: Recall traces: Backtracking models for efficient reinforcement learning

venue: arXiv preprint arXiv:1804.00379,

authors:
Todd Hester
Matej Vecerik
Olivier Pietquin
Marc Lanctot
Tom Schaul
Bilal Piot
Dan Horgan
John Quan
Andrew Sendonaris
Gabriel Dulac-Arnold

title: Deep q-learning from demonstrations

venue: arXiv preprint arXiv:1704.03732,

authors:
Jonathan Ho
Stefano Ermon

title: Generative adversarial imitation learning

authors:
Wenming Hong
Ke Zhou

title: A note on the passage time of finite-state markov chains

venue: Communications in Statistics-Theory and Methods,

authors:
Ionel-Alexandru Hosu
Traian Rebedea

title: Playing atari games with deep reinforcement learning and human checkpoint replay

venue: arXiv preprint arXiv:1607.05077,

authors:
Boris Ivanovic
James Harrison
Apoorva Sharma
Mo Chen
Marco Pavone

title: Barc: Backward reachability curriculum for robotic reinforcement learning

venue: arXiv preprint arXiv:1806.06161,

authors:
Sham Kakade
John Langford

title: Approximately optimal approximate reinforcement learning

authors:
Max Kleiman-Weiner
Mark K Ho
Joseph L Austerweil
Michael L Littman
Joshua B Tenenbaum

title: Coordinate to cooperate or compete: abstract goals and joint intentions in social interaction

venue: COGSCI,

authors:
Marc Lanctot
Vinicius Zambaldi
Audrunas Gruslys
Angeliki Lazaridou
Julien Perolat
David Silver
Thore Graepel

title: A unified game-theoretic approach to multiagent reinforcement learning

authors:
Michael Laskey
Sam Staszak
Wesley Yu-Shu Hsieh
Jeffrey Mahler
Florian T Pokorny
Anca D Dragan
Ken Goldberg. Shiv

title: Reducing supervisor burden in dagger using support vectors for efficient learning from demonstrations in high dimensional state spaces

venue: In Robotics and Automation (ICRA),

authors:
Joel Z Leibo
Vinicius Zambaldi
Marc Lanctot
Janusz Marecki
Thore Graepel

title: Multi-agent reinforcement learning in sequential social dilemmas

venue: In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems,

authors:
Adam Lerer
Alexander Peysakhovich

title: Maintaining cooperation in complex social dilemmas using deep reinforcement learning

venue: arXiv preprint arXiv:1707.01068,

title: Learning social conventions in markov games

venue: arXiv preprint arXiv:1806.10071,

authors:
Sergey Levine
Chelsea Finn
Trevor Darrell
Pieter Abbeel

title: End-to-end training of deep visuomotor policies

venue: Journal of Machine Learning Research,

authors:
Jiwei Li
Will Monroe
Alan Ritter
Michel Galley
Jianfeng Gao
Dan Jurafsky

title: Deep reinforcement learning for dialogue generation

authors:
Stephen McAleer
Forest Agostinelli
Alexander Shmakov
Pierre Baldi

title: Solving the rubik’s cube without human knowledge

venue: arXiv preprint arXiv:1805.07470,

authors:
Matej Moravcík
Martin Schmid
Neil Burch
Viliam Lisý
Dustin Morrill
Nolan Bard
Trevor Davis
Kevin Waugh
Michael Johanson
Michael H. Bowling

title: Deepstack: Expert-level artificial intelligence in no-limit

venue: poker. CoRR,

authors:
Ashvin Nair
Bob McGrew
Marcin Andrychowicz
Wojciech Zaremba
Pieter Abbeel

title: Overcoming exploration in reinforcement learning with demonstrations

venue: arXiv preprint arXiv:1709.10089,

authors:
Andrew Y Ng
Daishi Harada
Stuart Russell

title: Policy invariance under reward transformations: Theory and application to reward shaping

authors:
Xue Bin Peng
Pieter Abbeel
Sergey Levine
Michiel van de Panne

title: Deepmimic: Example-guided deep reinforcement learning of physics-based character skills

venue: arXiv preprint arXiv:1804.02717,

authors:
Alexander Peysakhovich
Adam Lerer

title: Consequentialist conditional cooperation in social dilemmas with imperfect information

venue: arXiv preprint arXiv:1710.06975,

title: Prosocial learning agents solve generalized stag hunts better than selfish ones

venue: Proceedings of the 17th Conference on Autonomous Agents and MultiAgent Systems,

authors:
Cinjon Resnick
Wes Eldridge
David Ha
Denny Britz
Jakob Foerster
Julian Togelius
Kyunghyun Cho
Joan Bruna

title: Pommerman: A multi-agent playground, 2018

authors:
Stéphane Ross
Geoffrey Gordon
Drew Bagnell

title: A reduction of imitation learning and structured prediction to no-regret online learning

venue: In Proceedings of the fourteenth international conference on artificial intelligence and statistics,

authors:
Simon Schmitt
Jonathan J Hudson
Augustin Zidek
Simon Osindero
Carl Doersch
Wojciech M Czarnecki
Joel Z Leibo
Heinrich Kuttler
Andrew Zisserman
Karen Simonyan

title: Kickstarting deep reinforcement learning

venue: arXiv preprint arXiv:1803.03835,

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
David Silver
Aja Huang
Chris J. Maddison
Arthur Guez
Laurent Sifre
George van den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot
Sander Dieleman
Dominik Grewe
John Nham
Nal Kalchbrenner
Ilya Sutskever
Timothy Lillicrap
Madeleine Leach
Koray Kavukcuoglu
Thore Graepel
Demis Hassabis

title: Mastering the game of Go with deep neural networks and tree

venue: search. Nature,

authors:
David Silver
Thomas Hubert
Julian Schrittwieser
Ioannis Antonoglou
Matthew Lai
Arthur Guez
Marc Lanctot
Laurent Sifre
Dharshan Kumaran
Thore Graepel
Timothy P. Lillicrap
Karen Simonyan
Demis Hassabis

title: Mastering chess and shogi by self-play with a general reinforcement learning

authors:
Tom Vodopivec
Spyridon Samothrakis
Branko Šter

title: On monte carlo tree search and reinforcement learning

venue: J. Artif. Int. Res.,

authors:
Jiakai Zhang
Kyunghyun Cho

title: Query-efficient imitation learning for end-to-end autonomous driving

venue: arXiv preprint arXiv:1605.06450,

authors:
Hongwei Zhou
Yichen Gong
Luvneesh Mugrai
Ahmed Khalifa
Andy Nealen
Julian Togelius

title: A hybrid search agent in pommerman

venue: In Proceedings of the 13th International Conference on the Foundations of Digital Games,

authors:
Yuke Zhu
Ziyu Wang
Josh Merel
Andrei A. Rusu
Tom Erez
Serkan Cabi
Saran Tunyasuvunakool
János Kramár
Raia Hadsell
Nando de Freitas
Nicolas Heess

title: Reinforcement and imitation learning for diverse visuomotor

venue: skills. CoRR,

heading: 1 INTRODUCTION

text:
An important goal of AI research is to construct agents that can learn well in new environments (Levine et al., 2016). An increasingly popular paradigm for this task is deep reinforcement learning (deep RL, Silver et al. (2016); Moravcík et al. (2017); Silver et al. (2017)). However, training an RL agent can take a very long time, particularly in environments with sparse rewards. In these settings, the agent typically requires a large number of episodes to stumble upon positive rewards and learn even a moderately effective policy that can then be refined. This is often resolved via hand-engineering a dense reward function. Such reward shaping, while effective, can also change the set of optimal policies and have unintended side effects (Ng et al., 1999; Clark & Amodei, 2016).
We consider an alternative technique for accelerating RL in sparse reward settings. The idea is to create a curriculum for the agent via reversing a single trajectory (i.e. state sequence) of reasonably good, but not necessarily optimal, behavior. We start our agent at the end of a demonstration and let it learn a policy in this easier setup. We then move the starting point backward until the agent is training only on the initial state of the task. We call this technique Backplay.
Our contributions are threefold:
1. We characterize analytically and qualitatively which environments Backplay will aid.
2. We demonstrate Backplay’s effectiveness on both a grid world task (to gain intuition) as well as the four player stochastic zero-sum game Pommerman (MultiAgentLearning, 2018).
3. We empirically show that Backplay compares favorably to other methods that improve sample complexity.
Besides requiring vastly fewer number of samples to learn a good policy, an agent trained with Backplay can outperform its demonstrator and even learn an optimal policy following a sub-optimal
∗These two authors contributed equally
demonstration. Our experiments further show Backplay’s strong performance relative to reward shaping (involves hand tuning reward functions), behavioral cloning (not intended for use with sub-optimal experts), and other forms of automatic curriculum generation (Florensa et al. (2017), requires a reversable environment).
2 RELATED WORK
The most related work to ours is a blog post describing a method similar to Backplay used to obtain state-of-theart performance on the challenging Atari game Montezuma’s Revenge (Salimans & Chen, 2018). This work was independent of and concurrent to our own. In addition to reporting results on a different, complex stochastic multi-agent environment, we provide an analytic characterization of the method as well as an in depth discussion of what kinds of environments a practitioner can expect Backplay to out or underperform other existing methods.
A popular method for improving RL with access to expert demonstrations is behavioral cloning/imitation learning. These methods explicitly encourage the learned policy to mimic an expert policy (Bain & Sommut, 1999; Ross et al., 2011; Daumé et al., 2009; Zhang & Cho, 2016; Laskey et al., 2016; Nair et al., 2017; Hester et al., 2017; Ho & Ermon, 2016; Aytar et al., 2018; Lerer & Peysakhovich, 2018; Peng et al., 2018). Imitation learning requires access to both state and expert actions (whereas Backplay only requires states) and is designed to copy an expert, thus it cannot, without further adjustments (e.g. as proposed by Gao et al. (2018)), surpass a suboptimal expert. We discuss the pros and cons of an imitation learning + adjustment vs. a Backplay-based approach in the main analysis section.
Other algorithms (Ranzato et al., 2015; Li et al., 2016; Das et al., 2017a;b), primarily in dialog, use a Backplay-like curriculum, albeit they utilize behavioral cloning for the first part of the trajectory. This is a major difference as we show that for many classes of problems, we only need to change the initial state distribution and do not see any gains from warm-starting with imitation learning. Backplay is more similar to Conservative Policy Iteration (Kakade & Langford, 2002), a theoretical paper which presents an algorithm designed to operate with an explicit restart distribution.
Also related to Backplay is the method of automatic reverse curriculum generation Florensa et al. (2017). These approaches assumes that the final goal state is known and that the environment is both resettable and reversible. The curricula are generated by taking random walks in the state space to generate starting states or by taking random actions starting at the goal state McAleer et al. (2018). These methods do not require an explicit ‘good enough’ demonstration as Backplay does. However, they require the environment to be reversible, an assumption that doesn’t hold in many realistic tasks such as a robot manipulating breakable objects or complex video games such as Starcraft. In addition, they may fare poorly when random walks reach parts of the state space that are not actually relevant for learning a good policy. Thus, whether a practitioner wants to generate curricula from a trajectory or a random walk depends on the environment’s properties. We discuss this in more detail in our analysis section and show empirical results suggesting that Backplay is superior.
Hosu & Rebedea (2016) use uniformly random states of an expert demonstration as starting states for a policy. Like Backplay, they show that using a single loss function to learn a policy from both demonstrations and rewards can outperform the demonstrator and is robust to sub-optimal demonstrations. However, they do not impose a curriculum over the demonstration and are equivalent to the Uniform baseline in our experiments.
Zhu et al. (2018) use a curriculum but manually tune it for each ‘stage’ of the environment. Within each stage, they use what we call Uniform training, which fails in our most challenging environments.
Goyal et al. (2018) and Edwards et al. (2018) simultaneously proposed the use of a learned backtracking model to generate traces that lead to high value states. Their methods rely on either having the agent visit high reward states or learning a model of the environment capable of generating the states. Both of these are challenging in environments in which the dynamics near starting states are very different from those near goal states.
Finally, Ivanovic et al. (2018) use a known (approximate) dynamics model to create a backwards curriculum for continuous control tasks. Their approach requires a physical prior which is not always available and often not applicable in multi-agent scenarios. In contrast, Backplay automatically creates a curriculum fit for any resettable environment with accompanying demonstrations.

heading: 3 BACKPLAY

text:
Consider the standard formalism of a single agent Markov Decision Process (MDP) defined by a set of states S, a set of actions A, and a transition function T : S × A → S which gives the probability distribution of the next state given a current state and action. If P(A) denotes the space of probability distributions over actions, the agent chooses actions by sampling from a stochastic policy π : S → P(A), and receives reward r : S × A → R at every time step. The agent’s goal is to construct a policy which minimizes its discounted expected return Rt = E [∑∞ k=0 γ krt+k+1 ] where rt is the reward at time t and γ ∈ [0, 1] is the discount factor, and the expectation is taken with respect to both the policy and the environment.
The final component of an MDP is the distribution of initial starting states s0. The key idea in Backplay is that we do not initialize the MDP in only a fixed s0. Instead, we assume access to a demonstration which reaches a sequence of states {sd0, sd1, . . . , sdT }. For each training episode, we uniformly sample starting states from the sub-sequence {sdT−k, sdT−k+1, . . . , sdT−j} for some window [j, k]. Note that this training regime requires the ability to reset the environment to any state. As training continues, we ‘advance’ the window according to a curriculum by increasing the values of j and k until we are training on the initial state in every episode (j = k = T ). In this manner, our hyperparameters for Backplay are the windows and the training epochs at which we advance them.

heading: 3.1 QUANTITATIVE ANALYSIS

text:
Next, we consider a simple environment in which we can analytically show that Backplay will improve the sample-efficiency of RL training.
Consider a connected, undirected graph G = (V,E). An agent is placed at a fixed node v0 ∈ V and moves to neighboring nodes at a negative reward of −1 for each step. Its goal is to reach a target node v∗ ∈ V , terminating the episode. This corresponds to an MDPM = (S,A, P,R) with state space S ∼ V , action space A ∼ E, deterministic transition kernel corresponding to
P (st+1 = j | st = i, at = (l, k)) = δ(j = k)δ(l = i) + δ(j = i)δ(l 6= i)
and uniform reward R(st, at) = −1 for st+1 6= v∗. Assume that π is a fixed policy onM, such that the underlying Markov chain is irreducible and aperiodic:
Kπ(s ′, s) = ∑ a∈A P (st+1 = s ′ | st = s, at = a)π(a | s)
Kπ has a single absorbing state at s = s∗ := v∗. Our goal is to estimate the value function of this policy, equivalent to the expected first-passage time of the Markov chain Kπ from s0 = s to s∗:
Vπ(s) = Eτ(s, s∗) = Emin{j ≥ 0 ; s.t. sj = s∗, s0 = s, si+1 ∼ Kπ(·, si)} .
We consider a special tractable case where the value function can be well approximated by looking at the distance of a state from the goal state. Formally:
Assumption 1. For all θ, Vθ(s) = Vθ(s′) whenever distG(s′, s∗) = distG(s, s∗).
We wish to analyze the process which is the projection of our Markov policy π only in terms of the distance zt. However, now the transition probabilities will not only be a function of only zt and so
this projection will be non-Markovian. Its Markov approximation z̄t is defined as the Markov chain K given by the expected transition probabilities
Pr(z̄t+1 = l − 1|z̄t = l) = αl := Prµ(zt+1 = l − 1 | zt = l) , (1) Pr(z̄t+1 = l|z̄t = l) = βl := Prµ(zt+1 = l | zt = l) , l = 0 . . .M (2)
and thus Pr(z̄t+1 = l + 1|z̄t = l) = 1− αl − βl = Prµ(zt+1 = l + 1 | zt = l) under the stationary distribution µ of Kπ . Assumption 2. The projected process is well described by its Markovian approximation.
Though these assumptions are relatively strong, they makes the analysis of Backplay in this graph complex but analytically tractable. Given a demonstration d = (d0 = s0, . . . , dL = s∗), dl ∈ S we will perform Backplay Theorem 1. When assumptions 1 and 2 hold, the sample complexity gains from using Backplay rather than standard RL are exponential in the diameter of the graph. O(M 2
m α −m) vs Ω(Mα−M/2).
Proof. we sample it using a step size m > 0 (such that j = 0 mod m, where j is defined in Section 3) to obtain d̄l := distG(dL−ml, s∗), l = 0, 1, . . . , Lm , which satisfies d̄l ≤ lm for all l.
For fixed l, we initialize the chain K at d̄l: z̄0 = d̄l. Since Pr(z̄m = 0) ≥ ∏m−1 j=0 αj := γ0,m, after O(γ−10,m) trials of length ≤M , we will reach the absorbing state and finally have a signal-carrying update for the Q-function at the originating state.
We can consequently merge that state into the absorbing state and reduce the length of the chain by one. Repeat the argument m times so that after O( ∑m j=0 γ −1 j,m) = O(mγ −1 0,m) trials, the Q-function is updated at z̄0. Repeat at Backplay steps lm, l = 1, . . . Mm , and we reach a sample complexity of
Tm = M m−1∑ k=0 O M m∑ j=0 γ−1km,(k+1)m−j  . In the case where αl = α for all l, we obtain γ−1km,(k+1)m−j = γ0,m−j = α −m+j and therefore
Tm = O ( M2(1−αm+1) m(1−α) α −m ) , where the important term is the rate M 2 m α −m.
On the other hand, Hong & Zhou (2017) shows that the first-passage time τ(0,M) in a skip-free finite Markov chain of M states with a single absorbing state is a random variable whose momentgenerating function ϕ(s) = Esτ(s,s∗) is given by
ϕ(s) = M∏ j=1 (1− λj)s 1− λjs , (3)
where λ1, . . . , λM are the non-unit eigenvalues of the transition probability matrix. It follows that Eτ(0,M) = ϕ′(1) = ∑M j=1 1 1−λj ≈ (1− λ1) −1, which corresponds to the reciprocal spectral gap.1 Chen & Saloff-Coste (2013) further shows that this reciprocal spectral gap is Ω(α−M/2) in our case, and therefore the model without Backplay will on average take TM = Ω(α−M/2) trials to reach the absorbing state and receive information.
We can analyze the uniform strategy similarly. The probability that a trajectory initialized at one of the uniform samples will reach the absorbing state is lower bounded by
M∑ j=1 αjP (z̄0 = j) = 1 M M∑ j=1 αj = α− αM+1 M(1− α) , (4)
which is approximately αM when α is small, leading to a sample complexity of O(M 2α−1) to update the value function at the originating state, and O(M3α−1) at the starting state. Comparing this rate
1The spectral gap of a Markov Chain is the difference between the first and second largest eigenvalue magnitudes of its transition probability matrix. It controls its mixing time among many other properties.
to Backplay with m = 1, observe that the uniform strategy is slower by a factor of M (and one can verify that the same is true for generic step size m by imagining that we first sampled a window of size m and then sub-sampled our state from that window), suggesting that it loses efficiency on environments with large diameter.
The preceding analysis suggests that a full characterization of Backplay is a fruitful direction for reinforcement and imitation learning theory, albeit beyond the scope of this paper.

heading: 3.2 QUALITATIVE ANALYSIS

text:
We now provide intuition regarding the conditions under which Backplay can improve sampleefficiency or lead to a better policy than that of the demonstrator. In addition, we discuss the differences between Backplay and other methods of reducing sample complexity for deep RL as well as when practitioners would choose to use one or the other.
Figure 2 contains three grid worlds. In each, the agent begins at s0, receives +1 when it reaches s∗, and otherwise incurs a per step cost. They each pose a challenge to model free RL and highlight advantages and disadvantages of Backplay compared to other approaches like behavioral cloning (BC, Bain & Sommut (1999)), generative adversarial imitation learning (GAIL, Ho & Ermon (2016)), and reverse curriculum generation (RCG, Florensa et al. (2017)). See Table 1 for a direct comparison of these algorithms.
Demonstration s∗
s0
(a) Backplay Helps
Demonstration s∗
s0
(b) Backplay Helps
Demonstration s∗
s0
(c) Backplay Hinders
Figure 2. Three environments illustrating when Backplay can help or hinder learning an optimal policy. Backplay is expected to learn faster than standard RL on the first and second mazes, but perform worse on the third maze.
The left grid world shows a sparse reward environment in which Backplay can decrease the requisite training time compared to standard RL. Using the sub-optimal demonstration will position the Backplay agent close to high value states. In addition, the agent will likely surpass the expert policy because, unlike in BC approaches, Backplay does not encourage the agent to imitate expert actions. Rather, the curriculum forces the agent to first explore states with large associated value and, consequently, estimating the value function suffers less from the curse of dimensionality. And finally, we expect it to also surpass results from RCG because random movements from the goal state will progress very haphazardly in such an open world.
The middle grid illustrates a maze with bottlenecks. Backplay will vastly decrease the exploration time relative to standard RL, because the agent will be less prone to exploring the errant right side chamber where it can get lost if it traverses to the right instead of going up to the goal. If we used BC, then the agent will sufficiently learn the optimal policy, however it will suffer when placed in nearby spots on the grid as they will be out of distribution; Backplay-trained agents will not have this problem as they also explore nearby states. When an RCG agent reaches the first fork, it has an even chance of exploring the right side of the grid and wasting lots of sample time.
On the rightmost grid world, while Backplay is still likely to surpass its demonstrator, it will have trouble doing better than standard RL because the latter always starts at s0 and consequently is more likely to stumble upon the optimal solution of going up and right. In contrast, Backplay will spend the dominant amount of its early training starting in states in the sub-optimal demonstration. Note that BC will be worse off than Backplay because by learning the demonstration, it will follow the trajectory into the basin instead of going up the right side. Finally, observe that RCG will likely outperform here given that it has a high chance of discovering the left side shortcut and, if not, it would more likely discover the right side shortcut than be trapped in the basin.
In summary, Backplay is not a universal strategy to improve sample complexity. Even in the navigation setting, if the task randomizes the initial state s0, a single demonstration trajectory does not generally improve the coverage of the state-space outside an exponentially small region around said trajectory. For example, imagine a binary tree and a navigation task that starts at a random leaf and needs to reach the root. A single expert trajectory will be disjoint from half of the state space (because the root is absorbing), thus providing no sample complexity gains on average.

heading: 4 EXPERIMENTS

text:
We now move to evaluating Backplay empirically in two environments: a grid world maze and a four-player free-for-all game. The questions we study across both environments are the following:
• Is Backplay more efficient than training an RL agent from scratch? • How does the quality of the given demonstration affect the effectiveness of Backplay? • Can Backplay agents surpass the demonstrator when it is non-optimal? • Can Backplay agents generalize?

heading: 4.1 TRAINING DETAILS

text:
We compare several training regimes. The first is Backplay, which uses the Backplay algorithm corresponding to a particular sequence of windows and epochs as specified in A.1. The second, Standard is vanilla model-free RL with the agent always starting at the initial state s0. The last, Uniform, is an ablation that considers how important is the curriculum aspect of Backplay by sampling initial states randomly from the entire demonstration. In all these regimes, we use Proximal Policy Optimization (PPO, Schulman et al. (2017)) to train an agent with policy and value functions parameterized by convolutional neural networks.
On the Maze environment (detailed below), we also ran comparisons against Behavioral Cloning and Reverse Curriculum Generation. We chose BC over GAIL (Ho & Ermon, 2016) for three reasons. First, GAIL requires careful hyperparameter tuning and is thus difficult to train. Second, GAIL requires more environment interactions. And third, GAIL has recently been shown to perform significantly worse than BC (Behbahani et al., 2018).
Training details and network architectures for all the environments can be found in A.3 and A.6, while A.9 contains empirical observations for using Backplay in practice.

heading: 4.2 MAZE

text: We generated mazes of size 24× 24 with 120 randomly placed walls, a random start position, and a random goal position. We then used A* to generate trajectories. These included both Optimal demonstrations (true shortest path) and N-Optimal demonstrations (N steps longer than the shortest path). More details on this setup are given in A.2.

heading: Algorithm Map Set % Optimal % 0-5 Optimal Avg Suboptimality Std Suboptimality

text:
Our model receives as input four 24 × 24 binary maps. They contain ones at the positions of, respectively, the agent, the goal, passages, and walls. It outputs one of five options: Pass, Up, Down, Left, or Right. The game ends when the agent has reached its goal or after a maximum of 200 steps, whereupon the agent receives reward of +1 if it reaches the goal and a per step penalty of -0.03.
Backplay, Uniform, Standard. Table 2 shows that Standard has immense trouble learning in this sparse reward environment while both Backplay and Uniform find an optimal path approximately 30- 50% of the time and a path within five of the optimal path almost always. Thus, in this environment, demonstrations of even sub-optimal experts are extremely useful, while the curriculum created by Backplay is not necessary. That curriculum does, however, aid convergence speed (A.4). We will see in 4.3 that the curriculum becomes vital as the environment increases in complexity.
Behavioral Cloning. We trained an agent using behavioral cloning from the same trajectories as the ones used for Backplay. While the agent learns to perfectly imitate those trajectories, we had immense difficult doing better than the expert. All of our attempts to use reward signal to improve the agent’s performance (over that of the behaviorally cloned agent) were unsuccessful, even after incorporating tricks in the literature such as those found in Schmitt et al. (2018). One possible reason is that the agent has no information about states outside of the demonstration trajectory.
Reverse Curriculum Generation. We also compared Backplay to the method proposed by Florensa et al. (2017). As illustrated in Table 2 and Section A.4, Florensa agents perform significantly worse with higher sample complexity variance compared to Backplay (or Uniform). This suggests that having demonstrations helps inordinately. Further details can be found in A.3.

heading: 4.3 POMMERMAN

text:
Pommerman is a stochastic environment (Resnick et al., 2018) based on the classic console game Bomberman and will be a competition at NeurIPS 2018. It is played on an 11x11 grid where on every turn, each of four agents either move in a cardinal direction, pass, or lay a bomb. The agents begin fenced in their own area by two different types of walls - rigid and wooden. The former are indestructible while bombs destroy the latter. Upon blowing up wooden walls, there is a uniform chance at yielding one of three power-ups: an extra bomb, an extra unit of range in the agent’s bombs, or the ability to kick bombs. The maps are designed randomly, albeit there is always a guaranteed path between any two agents. For a visual aid of the start state, see Figure 8 in A.5.
In our experiments, we use the purely adversarial Free-For-All (FFA) environment. This environment is introduced in (MultiAgentLearning, 2018; Resnick et al., 2018) and we point the reader there for more details. The winner of the game is the last agent standing. It is played from the perspective of one agent whose starting position is uniformly picked among the four. The three opponents are
copies of the winner of the June 3rd 2018 FFA competition, a stochastic agent using a Finite State Machine Tree-Search approach (FSMTS, Zhou et al. (2018)). We also make use of the FSMTS agent as the ‘expert’ in the Backplay demonstrations.
The observation state is represented by 19 11x11 maps, and we feed the concatenated last two states to our agent as input. A detailed description of this mapping is given in A.5. The game ends either when the learning agent wins or dies, or when 800 steps have passed. Upon game end, the agent receives +1 for winning and −1 otherwise (Sparse). We also run experiments where the agent additionally receives +0.1 whenever it collects an item (Dense).
Our first three scenarios follow the Sparse setup. We independently consider three Backplay trajectories, one following the winner over 100 maps, one following the winner over four maps, and one following the runner up over four maps, with the latter two set of maps being the same. Figure 3 shows that Backplay can soundly defeat the FSMTS agents in sparse settings when following the winner, even when there are 100 maps to consider, while other methods struggle in this setup. Modulo higher variance in Backplay’s result, we see a similar comparison in the runner-up case. Visit this link for an example gif of our trained Backplay agent (top left - red). Note that our agent learned to ‘throw’ bombs, a unique playing style that no prior Pommerman competitor had exhibited, including the FSMTS demonstrator.
Moreover, by training on 100 maps, Backplay generalizes (to some extent) on unseen boards. Backplay wins 416 / 1000 games on a held out set of ten maps, with the following success rates on each: 85.3%, 84.1%, 81.6%, 79.5%, 52.4%, 47.4%, 38.1%, 22.6%, 20%, and 18.3%. This was in contrast to our Maze experiments where no approach generalized. Given this discrepancy, we believe that the lack of generalization was a consequence of not including enough mazes during training.

heading: 5 CONCLUSION

text:
We have introduced and analyzed Backplay, a technique which improves the sample efficiency of model-free RL by constructing a curriculum around a demonstration. We showed that Backplay agents can learn in complex environments where standard model-free RL fails, that they can outperform the ‘expert’ whose trajectories they use while training, and that they compare very favorably to related methods such as reversible curriculum generation. We also presented a theoretical analysis of its sample complexity gains in a simplified setting.
An important future direction is combining Backplay with more complex and complementary methods such as Monte Carlo Tree Search (MCTS, (Browne et al., 2012; Vodopivec et al., 2017)). There are many potential ways to do so, for example by using Backplay to warm-start MCTS.
Another direction is to use Backplay to accelerate self-play learning in zero-sum games. However, special care needs to be taken to avoid policy correlation during training (Lanctot et al., 2017) and thus to make sure that learned strategies are safe and not exploitable (Brown & Sandholm, 2017).
A third direction is towards non-zero sum games. It is well known that standard independent multiagent learning does not produce agents that are able to cooperate in social dilemmas (Leibo et al., 2017; Lerer & Peysakhovich, 2017; Peysakhovich & Lerer, 2017; Foerster et al., 2017) or risky coordination games (Yoshida et al., 2008; Peysakhovich & Lerer, 2018). In contrast, humans are much better at finding these coordinating and cooperating equilibria (Bó, 2005; Kleiman-Weiner et al., 2016). Thus, we conjecture that human demonstrations can be combined with Backplay to construct agents that perform well in such situations.
Other future priorities are to gain further understanding into when Backplay works well, when it fails, and how we can make the procedure more efficient. Could we speed up Backplay by ascertaining confidence estimates of state values? Do the gains in sample complexity come from value estimation like our analysis suggests, from policy iteration, or from both? Is there an ideal rate for advancing the curriculum window and is there a better approach than a hand-tuned schedule?

heading: A APPENDIX

heading: A.1 BACKPLAY HYPERPARAMETERS

text:
As mentioned in Section 3, the Backplay hyperparameters are the window bounds and the frequency with which they are shifted. When we get to a training epoch represented in the sequence of epochs, we advance to the corresponding value in the sequence of windows. For example, consider training an agent with Backplay in the Maze environment (Table 3) and assume we are at epoch 1000. We will select a maze at random, an N ∈ [16, 32), and start the agent in that game N steps from the end. Whenever a pair is chosen such that the game’s length is smaller than N , we use the initial state.
There isn’t any downside to having the model continue training in a window for too long, albeit the ideal is that this method increases the speed of training. There is however a downside to advancing the window too quickly. A scenario common to effective training is improving success curves punctured by step drops whenever the window advances.

heading: A.2 MAZE: DEMONSTRATION DETAILS

text: For N-Optimal demonstrations, we used a noisy A* where at each step, we follow A* with probability p or choose a random action otherwise. We considered N ∈ {5, 10}. In all scenarios, we only selected maps in which there exists at least a path from the the initial state to the goal state, we filtered any path that was less than 35 in length and stopped when we found a hundred valid training games. Note that we held the demonstration length invariant rather than the optimal length (i.e. all N-optimal paths have the same length regardless of N, which means that the length of the optimal path of a N-optimal demonstration decreases with N). This could explain why the results in Table 2 (column 1) show that Backplay’s performance increases with N (since the larger the N, the smaller the true optimal path, so the easier it is to learn an optimal policy for that maze configuration).

heading: A.3 MAZE: NETWORK ARCHITECTURE AND TRAINING PARAMETERS

text:
We use a standard deep RL setup for our agents. The agent’s policy and value functions are parameterized by a convolutional neural network with 2 layers each of 32 output channels, followed by two linear layers with 128 dimensions. Each of the layers are followed by ReLU activations. This body then feeds two heads, a scalar value function and a softmax policy function over the five actions. All of the CNN kernels are 3x3 with stride and padding of one.
We train our agent using Proximal Policy Optimization (PPO, Schulman et al. (2017)) with γ = 0.99, learning rate 1× 10−3, batch size 102400, 60 parallel workers, clipping parameter 0.2, generalized advantage estimation with τ = 0.95, entropy coefficient 0.01, value loss coefficient 0.5, mini-batch size 5120, horizon 1707, and 4 PPO updates at each iteration. The number of interactions per epoch is equal to the batch size (102400).
The hyperparameters used for training the agent with Reverse Curriculum Generation (Florensa et al., 2017) are: 104 rollout states for nearby sampling, 50 Brownian steps, 200 samples from new starts, 100 samples from old starts, interval for the expected return [0.1, 0.9].

heading: A.4 MAZE: LEARNING CURVES

text: Below are our learning curves for the Maze challenge over five seeds. Note that we do not show any results for Standard as it failed to learn much of anything in the time allotted (3500 epochs). Also note that Backplay occasionally sees the actual grid starting position from epoch 1400, but it becomes the default starting state at epoch 1750. To align with this, our Florensa baseline switches to training from the actual start position at epoch 1750, and we show results for Uniform only over the initial starting state. Correspondingly, we show the graphs from epoch 1000 as all of the methods have commensurately poor results before that time.

heading: A.5 POMMERMAN: OBSERVATION STATE

text:
There are 19 feature maps that encompass each observation. They consist of the following: the agents’ identities and locations, the locations of the walls, power-ups, and bombs, the bombs’ blast strengths and remaining life counts, and the current time step.
The first map contains the integer values of each bomb’s blast strength at the location of that bomb. The second map is similar but the integer value is the bomb’s remaining life. At all other positions, the first two maps are zero. The next map is binary and contains a single one at the agent’s location. If the agent is dead, this map is zero everywhere. The following two maps are similar. One is full with the agent’s integer current bomb count, the other with its blast radius. We then have a full binary map that is one if the agent can kick and zero otherwise.
The next maps deal with the other agents. The first contains only ones if the agent has a teammate and zeros otherwise. This is useful for building agents that can play both team and solo matches. If the agent has a teammate, the next map is binary with a one at the teammate’s location (and zero if she is not alive). Otherwise, the agent has three enemies, so the next map contains the position of the enemy that started in the diagonally opposed corner from the agent. The following two maps contain the positions of the other two enemies, which are present in both solo and team games.
We then include eight feature maps representing the respective locations of passages, rigid walls, wooden walls, flames, extra-bomb power-ups, increase-blast-strength power-ups, and kicking-ability power-ups. All are binary with ones at the corresponding locations.
Finally, we include a full map with the float ratio of the current step to the total number of steps. This information is useful for distinguishing among observation states that are seemingly very similar, but in reality are very different because the game has a fixed ending step where the agent receives negative reward for not winning.

heading: A.6 POMMERMAN: NETWORK ARCHITECTURE AND TRAINING PARAMETERS

text:
We use a similar setup to that used in the Maze game. The architecture differences are that we have an additional two convolutional layers at the beginning, use 256 output channels, and have output dimensions of 1024 and 512, respectively, for the linear layers. This architecture was not tuned at all during the course of our experiments. Further hyperparameter differences are that we used a learning rate of 3× 10−4 and a gamma of 1.0. These models trained for 72 hours, which is ∼50M frames. 2
2In our early experiments, we also used a batch-size of 5120, which meant that the sampled transitions were much more correlated. While Backplay would train without any issues in this setup, Standard would only marginally learn. In an effort to improve our baselines, we did not explore this further.

heading: A.7 POMMERMAN: ACTION DISTRIBUTION ANALYSIS

text: Pommerman can be difficult for reinforcement learning agents. The agent must learn to effectively wield the bomb action in order to win against competent opponents. However, bombs destroy agents indiscriminately, so placing one without knowing how to retreat often results in negative reward for that agent. Since agents begin in an isolated area, they are prone to converging to policies which do not use the bomb action (as seen in the histograms in Figure 9), which leads them to sub-optimal policies in the long-term.

heading: A.8 POMMERMAN: WIN RATES

text: Here we show the per-map win rates obtained by the agent trained with Backlpay on the 100 Pommerman maps.

heading: A.9 PRACTICAL FINDINGS

text:
We trained a large number of models through our research into Backplay. Though these findings are tangential to our main points (and are mainly qualitative), we list some observations here that may be helpful for other researchers working with Backplay.
First, we found that Backplay does not perform well when the curriculum is advanced too quickly, however it does not fail when the curriculum is advanced ‘too slowly.’ Thus, researchers interested in using Backplay should err on the side of advancing the window too slowly rather than too quickly.
Second, we found that Backplay does not need to hit a high success rate before advancing the starting state window. Initially, we tried using adaptive approaches that advanced the window when the agent reached a certain success threshold. This worked but was too slow. Our hypothesis is that what is more important is that the agent gets sufficiently exposed to enough states to attain a reasonable barometer of their value rather than that the agent learns a perfectly optimal policy for a particular set of starting states.
Third, Backplay can still recover if success goes to zero. This surprising and infrequent result occurred at the juncture where the window moved back to the initial state and even if the policy’s
entropy over actions became maximal. We are unsure what differentiates these models from the ones that did not recover.
We also explored using DAgger (Ross et al. (2011)) for training our agent, but found that it achieved approximately the same win rate (∼ 20%) as what we would expect when four FSMTS agents played each other (given that there are also ties).


summaries: The paper proposes a multi-layer pruning method called MLPrune for neural networks, which can automatically decide appropriate compression ratios for all the layers. It firstly pre-trains a network. Then it utilizes K-FAC to approximate the Fisher matrix, which in turn approximates the exact Hessian matrix of training loss w.r.t model weights. The approximated Hessian matrix is then used to estimate the increment of loss after pruning a connection. The connections from all layers with the smallest loss increments are pruned and the network is re-trained to the final model.

summaries: This paper introduces an approach to pruning the parameters of a trained neural network. The idea is inspired by the Optimal Brain Surgeon method, which relies on second derivatives of the loss w.r.t. the network parameters. Here, the corresponding Hessian matrix is approximated using the Fisher information to make the algorithm scalable to very deep networks.

abstractText: Model compression can significantly reduce the computation and memory footprint of large neural networks. To achieve a good trade-off between model size and accuracy, popular compression techniques usually rely on hand-crafted heuristics and require manually setting the compression ratio of each layer. This process is typically costly and suboptimal. In this paper, we propose a Multi-Layer Pruning method (MLPrune), which is theoretically sound, and can automatically decide appropriate compression ratios for all layers. Towards this goal, we use an efficient approximation of the Hessian as our pruning criterion, based on a Kroneckerfactored Approximate Curvature method. We demonstrate the effectiveness of our method on several datasets and architectures, outperforming previous state-of-theart by a large margin. Our experiments show that we can compress AlexNet and VGG16 by 25x without loss in accuracy on ImageNet. Furthermore, our method has much fewer hyper-parameters and requires no expert knowledge.

authors:
Jimmy Ba
Roger Grosse
James Martens

title: Distributed second-order optimization using kroneckerfactored approximations

authors:
Matthieu Courbariaux
Itay Hubara
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1

venue: arXiv preprint arXiv:1602.02830,

authors:
Emily L Denton
Wojciech Zaremba
Joan Bruna
Yann LeCun
Rob Fergus

title: Exploiting linear structure within convolutional networks for efficient evaluation

venue: In Advances in neural information processing systems,

authors:
Xin Dong
Shangyu Chen
Sinno Pan

title: Learning to prune deep neural networks via layer-wise optimal brain surgeon

venue: In Advances in Neural Information Processing Systems,

authors:
Yunchao Gong
Liu Liu
Ming Yang
Lubomir Bourdev

title: Compressing deep convolutional networks using vector quantization

venue: arXiv preprint arXiv:1412.6115,

authors:
Roger Grosse
James Martens

title: A kronecker-factored approximate fisher matrix for convolution layers

venue: In International Conference on Machine Learning,

authors:
Yiwen Guo
Anbang Yao
Yurong Chen

title: Dynamic network surgery for efficient dnns

venue: In Advances In Neural Information Processing Systems,

authors:
Song Han
Huizi Mao
William J Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

venue: arXiv preprint arXiv:1510.00149,

authors:
Song Han
Jeff Pool
John Tran
William Dally

title: Learning both weights and connections for efficient neural network

authors:
Babak Hassibi
David G Stork

title: Second order derivatives for network pruning: Optimal brain surgeon

authors:
Max Jaderberg
Andrea Vedaldi
Andrew Zisserman

title: Speeding up convolutional neural networks with low rank expansions

venue: arXiv preprint arXiv:1405.3866,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Vadim Lebedev
Yaroslav Ganin
Maksim Rakhuba
Ivan Oseledets
Victor Lempitsky

title: Speeding-up convolutional neural networks using fine-tuned cp-decomposition

venue: arXiv preprint arXiv:1412.6553,

authors:
Yann LeCun
John S Denker
Sara A Solla

title: Optimal brain damage

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Hao Li
Asim Kadav
Igor Durdanovic
Hanan Samet
Hans Peter Graf

title: Pruning filters for efficient convnets

venue: arXiv preprint arXiv:1608.08710,

authors:
James Martens
Roger Grosse

title: Optimizing neural networks with kronecker-factored approximate curvature

venue: In International conference on machine learning,

authors:
Alexander Novikov
Dmitrii Podoprikhin
Anton Osokin
Dmitry P Vetrov

title: Tensorizing neural networks

authors:
Mohammad Rastegari
Vicente Ordonez
Joseph Redmon
Ali Farhadi

title: Xnor-net: Imagenet classification using binary convolutional neural networks

venue: In European Conference on Computer Vision,

title: Modeling by shortest data

venue: description. Automatica,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Wei Wen
Chunpeng Wu
Yandan Wang
Yiran Chen
Hai Li

title: Learning structured sparsity in deep neural networks

authors:
Jiaxiang Wu
Cong Leng
Yuhang Wang
Qinghao Hu
Jian Cheng

title: Quantized convolutional neural networks for mobile devices

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Yuhuai Wu
Elman Mansimov
Roger B Grosse
Shun Liao
Jimmy Ba

title: Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation

authors:
Guodong Zhang
Shengyang Sun
David Duvenaud
Roger Grosse

title: Noisy natural gradient as variational inference

venue: arXiv preprint arXiv:1712.02390,

authors:
Chenzhuo Zhu
Song Han
Huizi Mao
William J Dally

title: Trained ternary quantization

venue: arXiv preprint arXiv:1612.01064,

heading: 1 INTRODUCTION

text:
Deep neural networks have proven very successful in many artificial intelligence tasks such as computer vision, natural language processing, and robotic control. In exchange for such success, modern architectures are usually composed of many stacked layers parameterized with a large number of learnable weights. This contrasts classical networks which have hundreds or even thousands times fewer parameters. As a consequence, modern architectures require considerable memory storage and intensive computation. This is problematic in applications that need to run on small embedded systems or that require low-latency to make safety-critical decisions.
Fortunately, we can compress these large networks with little to no loss of accuracy, by exploiting the fact that many redundancies exist within their parameters. A popular approach is to quantize the parameters using lower precision, thus encoding the network with fewer bits (Courbariaux et al., 2016; Gong et al., 2014; Rastegari et al., 2016; Wu et al., 2016; Zhu et al., 2016). On the other hand, pruning techniques (Dong et al., 2017; Guo et al., 2016; Han et al., 2015a;b; Li et al., 2016; Wen et al., 2016) aim at removing redundant connections. It has been widely exploited due to its simplicity and efficacy. In this paper, we follow this line of work and propose a new pruning approach.
Pruning algorithms differ on the pruning criteria employed. Popular pruning methods typically rely on heuristics, such as weight magnitudes. However, a small magnitude does not necessarily mean unimportance (Hassibi & Stork, 1993; LeCun et al., 1990); if the input neuron has a large expected value, a small weight could still have a large effect on its output neuron. As a consequence, magnitudebased pruning might delete important parameters, or preserve unimportant ones. Furthermore, magnitude-based pruning requires manually setting the compression ratio of each layer. These ratios are not easy to tune, as different layers (and architectures) typically have different sensitivities for compression. Directly comparing the parameters’ magnitudes from all layers and pruning the smallest one would not solve the problem, since magnitudes are not calibrated across layers. Because of this, existing approaches usually involve time-consuming trial and error processes that require domain expertise.
In this paper we employ the Hessian matrix as a principled pruning criterion, as it characterizes the local curvature of the training loss. The Hessian was exploited in the past, but was either assumed to be computable (Hassibi & Stork, 1993), which is not possible in practice for modern neural networks with millions of parameters, or simplistic approximations (e.g., diagonal (LeCun et al., 1990)) were
utilized resulting in poor performance. Here we first note that the Fisher Information matrix is close to the Hessian under certain conditions. We then use a Kronecker-factored Approximate Curvature (K-FAC) (Martens & Grosse, 2015) method to efficiently estimate the Fisher matrix. In our experiments, the overhead of estimating the Hessian approximation is very small compared with the pre-train and re-train time. Therefore, our method is efficient to use, while exhibiting better compression performance compared with previous second-order pruning. Importantly, this criterion is also calibrated across layers, allowing us to directly compare parameters from different layers and set one global compression ratio for the whole network, rather than one ratio per layer. This makes our method significantly easier to use when compared to magnitude-based pruning. Our method achieves state-of-the-art results on several benchmark datasets and model architectures. Furthermore, it can be easily applied to new customized network architectures, without costly tuning many compression hyper-parameters.

heading: 2 BACKGROUND

text: In this section, we first introduce the notation used in the paper. Since our work is inspired by the Optimal Brain Surgeon (Hassibi & Stork, 1993), we also briefly review the idea and its limitations.

heading: 2.1 NOTATION

text:
Suppose we have a neural network with L fully-connected layers1. Let p(y|x,Θ) be the output distribution and L be the loss function. y denotes the target outputs, x the inputs, and Θ the network’s weights. Each layer l is associated with its input al−1 ∈ Rdl−1 , a weight matrix Wl ∈ Rdl−1×dl , a binary mask matrix Γl ∈ Rdl−1×dl and its output sl ∈ Rdl . The elements γ(i,j)l ∈ {0, 1} in the binary matrix Γl indicate whether the corresponding weight is retained or pruned away. We use subscript to denote the layer index, and superscript to denote the element index in a matrix. We also distinguish a matrix (vector) from a scalar by capital boldface2. The weights in a layer l can be computed as θ(i,j)l = w (i,j) l γ (i,j) l , and thus the forward-pass can be written as,
sl = (Wl Γl) al−1, al = h (sl) , (1)
where denotes element-wise product, and h is the Relu activation in our experiments. We also use W to denote the concatenation of [vec{W1}, vec{W2}, · · · , vec{WL}], which is a column vector with the same size as the total number of parameters in this neural network, similarly for Γ and Θ. Index q denotes the index number of a parameter in W(or Γ, Θ) that is associated with w(i,j)l (or γ (i,j) l , θ (i,j) l ). Parameters, weights and connections are used interchangeably.

heading: 2.2 A REVIEW ON OPTIMAL BRAIN SURGEON (OBS)

text:
Given a neural network with parameters Θ, the local surface of the training loss can be characterized by its Taylor expansion:
δL = ∂L ∂Θ δΘ + 1 2 δΘTHδΘ +O(||δΘ||3), (2)
where δΘ is a small change of the parameter values (e.g., setting some parameters to zero) and H is the Hessian matrix defined as ∂2L/∂Θ2. Note that at convergence the first-order term vanishes and the higher-order term can be neglected. OBS aims to find an index q, such that when changing θq from its original value to zero, the change in training loss δL is minimized:
min q ( min δΘ ( 1 2 δΘTHδΘ )) , s.t. eTq δΘ + δΘ = 0, (3)
where eTq is the unit vector in the weight space corresponding to θq . The inner minimization problem can be solved by the method of Lagrangian multipliers. Hassibi & Stork (1993) applied OBS on a small network with 18,000 weights and showed good results. However, since the exact solution involves the inverse of the Hessian matrix, original OBS is intractable for modern neural networks that contain millions of parameters.
1Convolutional layers can be transformed into fully-connected layers if we vectorize filters within each channel and expand the input feature map with repeated patches
2with minor abuse of notation for al−1 and sl

heading: 3 MULTI-LAYER PRUNING

text: Our method follows a similar pipeline when compared to conventional pruning methods. We first pre-train a neural network until converged, and then apply Multi-Layer Pruning (including surgeon) upon it. This will give us a compressed network with slightly worse performance. Finally, the network is re-trained to recover the model performance. In the following paragraph, we first introduce the problem formulation and its ideal solution in Section 3.1. We then show how to make approximations in Section 3.2.

heading: 3.1 MULTI-LAYER PRUNING AND SURGEON

text:
Our objective is to prune as much as possible while maintaining good model performance, e.g. high accuracy in classification. This is similar to the objective of Minimum Description Length (MDL, (Rissanen, 1978))
min Θ D(data|Θ) +D(Θ). (4)
In our case, the first term in Eq. (4) is equivalent to the training loss, and the second term is the description length denoting how many bits we need to encode the model. Here, we use the number of parameters as an indicator of such description length. We also introduce a relative importance λ, which characterizes the trade-off between sparsity and model performance, and controls the final size of a compressed model. Our objective can then be written as
Ψ = min W,Γ L (y|x,W Γ) + λ L∑ l=1 ∑ (i,j) γ (i,j) l  , (5) where Γ is the binary mask matrix defined in Section 2.1. This objective cannot be directly optimized with SGD as γ(i,j)l is contrained to be binary. Instead, we consider an easier case where we first pre-train the model to the local minimum of L, then update one γ(i,j)l from 1 to 0 if such change will decrease Ψ, or equivalently, if such change will not increase L more than λ. Since the parameter for forward-pass is θ(i,j)l = γ (i,j) l w (i,j) l , updating γ (i,j) l is equivalent to prune a parameter θ (i,j) l . Similar to Hassibi & Stork (1993), we also consider a surgeon operation after pruning. This will change other preserved parameters accordingly, so as to minimize the loss increment caused by the pruning. More specifically, after pruning one parameter θ(i,j)l and applying the surgeon, the increment of L will be,
min δΘ
( 1
2 δΘTHδΘ
) , s.t. δθ
(i,j) l + w (i,j) l = 0. (6)
δθ (i,j) l is the corresponding scalar value in δΘ, and H is the Hessian matrix of L w.r.t (W Γ). Solving such a minimization problem with Lagrangian multipliers results in the following update
∆Lq = 1
2
( w
(i,j) l )2 [H−1] (q,q) , δΘ∗ = [ − w (i,j) l [H−1] (q,q) H−1 ](.,q) . (7)
Here, δΘ∗ is the surgeon applied on the remaining Θ (and W accordingly). ∆Lq is the increment of loss after pruning and the surgeon operation. Again, superscript (q, q) denotes the element at the qth row and qth column, (., q) denotes the qth column in that matrix, and q is the index of the parameter in H that associates with w(i,j)l . The estimation of H −1 will be introduced in section 3.2.
Theoretically, we can calculate ∆Lq for each parameter and prune the one with the smallest ∆L, but this will become impractically time-consuming. Therefore, at each pruning step, we calculate ∆Lq for each remaining parameter, and prune all parameters with ∆Lq < λ. This is fine as long as such assumption holds, that H does not change significantly when we prune those unimportant parameters one by one. In our experiments, we simply set λ to be the pth percentile of all ∆Lq from all layers. Therefore, our method can jointly determine the importance of parameters from all layers and prune multiple layers simultaneously.
After pruning and doing surgeon, we apply SGD to those retained parameters to re-train the network,
W←W − α∂L (W Γ) ∂ (W Γ) Γ. (8)

heading: 3.2 APPROXIMATING HESSIAN USING FISHER

text:
Performing the pruning and surgeon operations as in Eq. (7) involves estimating and inverting the Hessian matrix, which is intractable for modern neural networks that contain millions of parameters. To efficiently calculate Eq. (7), we approximate the Hessian. Towards this goal, we first employ the Fisher Information matrix to approximate the Hessian and further use a Kronecker-factored Approximate Curvature (K-FAC) method to approximate the Fisher matrix. The first approximation comes from the fact that if the training objective is the negative log-likelihood, the Hessian matrix consists of expected second-order derivatives under the data distribution, while the Fisher matrix consists of expected second-order derivatives under the model distribution. Since modern neural networks usually have strong model capacities, we expect those two distributions are close for a well-trained model. The second approximation is demonstrated to be reasonable in optimization tasks (Grosse & Martens, 2016; Martens & Grosse, 2015), and will further help us to calculate Eq. (7) efficiently.
The K-FAC method approximates the Fisher matrix as a block-diagonal matrix and estimates each block by the Kronecker-product of two much smaller matrices, which are the second-order statistics of inputs and derivatives. Given a neural network with stacked fully-connected layers3, the Fisher Information matrix is defined as
F = E [ (∇WL) (∇WL)T ] . (9)
Unless specified otherwise, the expectation is taken with respect to the model distribution. We can re-write the Fisher in a block-wise manner by partitioning rows and columns of F if they correspond to parameters within the same layer. The (i, j) block is then4
Fij = E [ vec {∇WiL} vec { ∇WjL }T ] , (10)
which is the covariance of the gradients from i and j layers5. As noted by Martens & Grosse (2015), the elements of the covariance of derivatives from different layers are generally smaller than the ones within the same layer. Therefore, F can be approximated by a block-diagonal matrix where the lth block is simply Fll.
Using back-propagation, the gradients of layer l can be calculated as∇WlL = (∇slL) (al−1) T . The lth diagonal block Fll can then be written as
Fll = E [ vec { (∇slL) (al−1) T } vec { (∇slL) (al−1) T }T] = E [ al−1a T l−1 ⊗ (∇slL)(∇slL)T ] (11)
≈ E [ al−1a T l−1 ] ⊗ E [ (∇slL)(∇slL)T ] , (12)
where ⊗ denotes Kronecker-product. The second equality comes from the property of the Kroneckerproduct6. The last approximation is supposed to maintain the "coarse structure" of the Fisher matrix (Martens & Grosse, 2015), and such "coarse structure" is sufficient for our method to achieve a good compression ratio as empirically demonstrated in our experiments. Therefore, F (and thus H) can be approximated by several much smaller matrices
Al−1 = E [ al−1a T l−1 ] , DSl = E [ (∇slL)(∇slL)T ] , Fll = Al−1 ⊗DSl. (13)
For a typical modern neural network such as AlexNet, the original Hessian matrix is a 61M× 61M matrix, while Al−1 and DSl of the largest fully-connected layer have sizes of only 9126 × 9126 and 4096 × 4096 respectively. We use exponential moving average to estimate the expectation in Al−1 and DSl, with a decay factor of 0.95 and a horizon of 1000 steps in all experiments. This adds only a small overhead to the normal forward-backward pass. Furthermore, the inverse F−1 and matrix-vector product F−1h can be efficiently calculated by leveraging the block diagnoal structure and property of Kronecker-product7.
3Details for convolutional layers are discussed in Grosse & Martens (2016). 4Note that vec{} denotes vectorization, as Wi is a matrix, while previously W is a vector. See section2.1 5E [∇WL] = 0, since the expectation is taken over the model distribution 6vec { uvT } = v ⊗ u, (A⊗B)(C⊗D) = (A⊗C)(B⊗D). 7(A⊗B)−1 = A−1 ⊗B−1, (A⊗B)vec{X} = vec{BXAT }
Algorithm 1 Multi-Layer Pruning Initialization: W, Γ, Pruning fraction p. Pre-training Stage:
1: Pre-train the network Pruning Stage:
2: for t = 0, · · · , 1000 do 3: Update Al−1 ← 0.95×Al−1 + 0.05× al−1aTl−1 4: Update DSl ← 0.95×DSl + 0.05× (∇slL)(∇slL)T 5: end for 6: Compute Fisher matrix F by Eq. (13). 7: Compute importance measure ∆Lq for each parameter by Eq. (7). 8: Normalize ∆Lq within each layer by Eq. (14). 9: Compute pth percentile of ˜∆Lq from all layers as λ.
10: Update mask γ(i,j)l to 0 if its corresponding ˜∆Lq is smaller than λ. 11: Compute δΘ∗ by Eq. (7) and update Θ,W← Θ + δΘ∗. 12: Re-train the network by Eq. (8).
However, such a block diagonal approximation decorrelates the gradients from different layers, and might lead to different scales for different layers. This will become problematic when we jointly prune all layers, i.e. sorting ∆Lq from all layers. We empirically find that ∆Lq from different layers will sometimes differ by several orders of magnitudes, which makes it impossible to perform the multi-layer pruning. Therefore, we propose a simple yet effective modification for this problem. After calculating ∆Lq , we normalize it within the same layer:
˜∆Lq = ∆Lq∑
q∈layer l ∆Lq (14)
Then, we use ˜∆Lq as an importance measure to prune parameters. Surgeon and other parts remain unchanged. We show our algorithm as Algorithm 1. During pruning, we only need to set an overall compression ratio, and the MLPrune method will automatically decide the compression ratio for each layer. This free us from tuning hyper-parameters, and thus it is easier and more efficient to apply.

heading: 4 RELATED WORK

text:
Model compression task aims to compress a large model into a smaller one while maintaining good performance. There are several popular families of approaches, including pruning, quantization, and low-rank approximation. Quantization (Courbariaux et al., 2016; Gong et al., 2014; Rastegari et al., 2016; Wu et al., 2016; Zhu et al., 2016) aims to use fewer bits to encode each parameter, e.g. binary neural network. Low-rank approximation (Denton et al., 2014; Jaderberg et al., 2014; Lebedev et al., 2014; Novikov et al., 2015) approximates layer weights by low-rank representations, and thus saves the storage and makes speedup. Pruning, being one of the most popular methods due to its simplicity and effectiveness, aims to delete unimportant parameters from a large network. These techniques could be further integrated together and result in better compression ratio (Han et al., 2015a).
The pruning operation involves finding and deleting unimportant parameters, and thus needs a criterion for deciding importance. Magnitude-based methods (Guo et al., 2016; Han et al., 2015b; Li et al., 2016; Wen et al., 2016) use the absolute value of a parameter as an indicator, assuming smaller weights generally have smaller importance upon a network’s output, but there is no theoretical evidence to support this criterion. On the other hand, some other work (Hassibi & Stork, 1993; LeCun et al., 1990) use the second-order Hessian matrix to calculate the importance of each parameter, and show significant improvements when applied to toy neural networks. However, these methods cannot be easily adapted to modern neural networks due to the large size of the Hessian matrix. Recently, Dong et al. (2017) use the layer-wise reconstruction as an indicator, which provides a theoretical upper bound for the pruning error, while avoiding the intractable large Hessian matrix. However, all these methods require specifying one compression ratio for each layer, and searching such ratios are time-consuming for very deep neural networks.
In our work, we utilize K-FAC to approximate the Fisher matrix, which in turn approximates the exact Hessian matrix. K-FAC(Grosse & Martens, 2016; Martens & Grosse, 2015) provides an efficient way to estimate and invert an approximation of the Fisher matrix of a neural network. It first approximates the Fisher by a block diagonal matrix, and then decomposes each block by two much smaller matrix via Kronecker-product. Such approximation and its variants(Ba et al., 2016; Wu et al., 2017; Zhang et al., 2017) have shown success in the field of optimization.

heading: 5 EXPERIMENTS

text: Following previous work, we use compression ratio as our evaluation metric, which is defined as the ratio of the number of parameters that remaining active after pruning to the number of original parameters. To show the generality of our method, we perform experiments using three different datasets and five different deep network architectures, from shallow to deep. This includes LeNet300-100 and LeNet-5 (LeCun et al., 1998) on MNIST, CifarNet (Krizhevsky & Hinton, 2009) on Cifar-10, and AlexNet (Krizhevsky et al., 2012) and VGG16(Simonyan & Zisserman, 2014) on Imagenet ILSVRC-2012. The aforementioned architectures contain both fully-connected layers and convolution layers, and have different sizes from 267K to 138M parameters. We compare our results with some strong pruning baselines, including: 1) Randomly Pruning (Dong et al., 2017), 2) OBD (LeCun et al., 1990), 3) LWC (Han et al., 2015b), 4) DNS (Guo et al., 2016), 5) L-OBS (Dong et al., 2017). Following these work, we also apply pruning in an iterative manner and report the results in Table 1. Due to minor differences in implementation, different papers report different performance of pre-trained models. Therefore, we also report the original error and ∆error before and after pruning for each method. More implementation details could be found in Appendix A.

heading: 5.1 DOES MLPRUNE ACHIEVES BETTER COMPRESSION RESULTS?

text:
MNIST: We first conduct experiments on the MNIST dataset with LeNet-300-100 and LeNet-5. LeNet-300-100 has 2 fully-connected layers, with 300 and 100 hidden units respectively. LeNet-5 is a CNN with 2 convolutional layers, followed by 2 fully-connected layers. Table 1 shows that we can compress LeNet-300-100 to 1.3% of original size with almost no loss in performance. Similarly for LeNet-5, we can compress to 0.5%, which is much smaller than previous best result.
8Original DNS paper doesn’t provide result on VGG16. Therefore we adopt numbers from the reimplementation in Dong et al. (2017)
Cifar-10: We conduct experiments on Cifar-10 image classification benchmark with Cifar-Net architecture. Cifar-Net is a variant of AlexNet, containing 3 convolutional layers and 2 fullyconnected layers. Following previous work (Dong et al., 2017), we first pre-train the network to achieve 18.43% error rate on the testing set. We then iteratively prune the network to [50%, 25%, 12.5%, 10%, 8%, 6.4%] of its original size. This gives us a better compression ratio than our baselines while maintaining similar performance.
ImageNet: To demonstrate our method’s effectiveness on larger models and datasets, we prune AlexNet on ImageNet ILSVRC-2012. AlexNet has 5 convolutional layers, 3 fully-connected layers, and 61M parameters in total. We first pre-train the network, and achieve similar top-1 accuracy with other implementations. We then iteratively prune the network to [50%, 25%, 12.5%, 6.25%, 5%, 4%] of its original size. To the best of our knowledge, this is the best pruning result so far. Also notice that Han et al. (2015b) and Guo et al. (2016) find out it is necessary to fix the convolutional layers when pruning and retraining the fully-connected layer (and vice versa), otherwise the model cannot recover the pruning error. However, we don’t observe such difficulty in our experiments, as we simply prune and retrain all layers simultaneously. This also indicates that our pruning operation only brings small error and still preserves the model capacity.
We further apply our method to a modern neural network architecture, VGG16. VGG16 is a deep network with 13 convolutional layers, 3 fully-connected layers and 138M parameters in total. Due to its large number of layers, the search space of per-layer compression ratio is exponentially larger than that of AlexNet. Therefore, conventional methods would have difficulties to tune and set the compression ratio for each of those 16 layers. On the contrary, our method can be used in a pushbutton-to-start manner, and automatically finds out appropriate ratios. We use the same pruning set-up as in AlexNet experiment, and achieve the state-of-the-art result as shown in Table 1.

heading: 5.2 DOES MLPRUNE FIND REASONABLE PER-LAYER COMPRESSION RATIOS?

text: We compare the compression ratios, layer by layer, between our method and the baselines, as shown in Table 2. The compression ratios of Han et al. (2015b) and Guo et al. (2016) are manually tuned to achieve good results. In contrast, our method automatically determines the compression ratio for each layer during the pruning process. It involves no time-consuming procedure for tuning hyper-parameters yet achieves better results. We also notice that our compression ratios are not the same as previous manually-tuned ratios, but share some similarities; layers with smaller compression ratios in our method also have smaller ratios in the baselines. Also, fully-connected layers are generally be pruned more severe than convolutional layers, which is in accord with the observation that fully-connected layers usually have more redundancies. These suggest that our method can find reasonable per-layer compression ratios according to the sensitivities of each layer. Detailed compression ratios for other architectures could be found in Appendix B.

heading: 5.3 DOES MLPRUNE PRUNE SIMILAR PARAMETERS AS MAGNITUDE-BASED PRUNING?

text:
In section 5.2, we’ve seen MLPrune can automatically adjust how much to prune from different layers. In this section, we’ll investigate what parameters does MLPrune prune within one layer. Since both MLPrune and magnitude-based pruning can achieve good compression results, it’s intriguing
to explore if MLPrune prune similar parameters as magnitude-based pruning, or they prune totally different parameters.
Figure 1 shows the distribution of parameters’ magnitudes, coming from the first fully-connected layer of AlexNet. Before pruning, weight distribution is peaked at 0, and drops quickly as the absolute value increasing. This is very much like a gaussian distribution as what the weights were initialized from. Figure 1b shows the distribution after pruning using our method. It is obvious to see that parameters with magnitudes close to 0 (center region) are pruned away, indicating that the parameters regarded as having small impacts upon the loss by our method also usually have small magnitudes.
We further explore the correlation between a parameter’s magnitude and its importance measured by our method. From figure 2, we can observe that: 1) A parameter’s absolute value indeed has a strong correlation with its importance computed by MLPrune. This explains why magnitude-based methods also achieve fairly good performance. Despite this strong correlation, directly compare the magnitudes from all layer will give different pruning result than our method: setting the pruning threshold as the median of parameters’ magnitudes in Figure 2a will prune 14% of conv5, while the median of our importance will prune 7%. This explains why magnitude-based pruning cannot do multi-layer pruning. 2) FC layer initially has smaller importance(larger redundancies) than convolutional layer measured by MLPrune, and thus are pruned more severely. As more and more parameters are pruned away(from Figure 2a to Figure 2b), the importance of FC layer becomes closer to that of convolutional layer, and both layers will be pruned with similar ratios. This shows that our method can dynamically adjust the compression ratio of each layer, as the pruning going on.

heading: 6 CONCLUSION

text: In this paper we have proposed an automated Multi-Layer Pruning (MLPrune) method to compress deep neural networks. Our approach exploits an efficient approximation of the Hessian based on the K-FAC method as our pruning criterion. It has much fewer hyper-parameters and can be used in an automated manner without costly test and trial processes. We have demonstrated the effectiveness of our method on several datasets and architectures and achieved state-of-the-art results. In the future, we plan to extend our method to prune coarser components such as filters, rather than individual weights, so as to speed up the network and save memory furthermore.

heading: A PRUNING SETUP

text:
In this section, we provide the implementation details for experiments of AlexNet and VGG16.
The AlexNet is first pre-trained using similar settings as in Caffe model zoo. A training image is first rescale so that the shorter edge is 256 with aspect ratio unchanged. Then a 227x227 image is randomly croped, followed by randomly flip horizontally or not. We do not apply color augmentation as in original paper (Krizhevsky et al., 2012). During testing, a center cropped image is fed into the network. SGD with momentum is applied for training. The batch-size is 256 and momentum is 0.9 for pre-training and all retraining stages.
Table 3 shows the hyper-parameters used for retraining stages (We do not apply retraining when prune from 100% to 50% since the model performance doesn’t decrease before and after pruning). The learning rate schedule is exactly the same as pre-training, and doesn’t require any tuning. The weight decay is slightly decreased to regularize the model less, since a pruned model has smaller representation capacity. The only hyper-parameters need to tune during the pruning is the dropout rate. As more and more parameters are pruned away, the model will become under-fit rather than over-fit. Therefore, reduce the dropout rate accordingly will be helpful to get better model performance. (Han et al., 2015b) propose a heuristic formula to determine the appropriate dropout rate for magnitudebased pruning methods. However, applying their dropout rate on our model lead to severe over-fitting. For example, when compressed to 12.5%, their formula suggest dropout rate of 0.18%, while our model adopts 0.4%. One possible explanation is that magnitude-based pruning methods sometimes mistakenly prune away important connections. This will significantly harm the model capacity and need much smaller dropout rate.
We adopt similar strategy for VGG16, namely using the same learning rate schedule, decrease and fix the weigh decay, and fine tune the dropout rate during pruning. The batch-size is 128 and momentum is 0.9 for all experiments. Again, we achieve state-of-the-art pruning result. Also notice that the dropout rate for VGG16 is larger than that of AlexNet, which might due to the fact that VGG16 has larger fully-connected layer, and thus pruning a fraction of it won’t affect the model capacity that much.

heading: B PER-LAYER COMPRESSION RATIOS

text: We compare the compression ratio, layer by layer, between our method and the baselines, as shown in Table 4. The compression ratios of Han et al. (2015b) and Guo et al. (2016) are manually tuned to achieve good results. In contrast, our method automatically determines the compression ratio for each layer during the pruning process. It involves no time-consuming procedure for tuning hyper-parameters yet achieves better results.