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.  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.name: BACKPLAY: ‘MAN
authors.name: MUSS IMMER UMKEHREN
authors.name: Cinjon Resnick
authors.name: Roberta Raileanu
authors.name: Sanyam Kapoor
authors.name: Kyunghyun Cho
references.authors: Yusuf Aytar Tobias Pfaff David Budden Tom Le Paine Ziyu Wang Nando de Freitas
references.title: Playing hard exploration games by watching youtube
references.venue: arXiv preprint arXiv:1805.11592,
references.authors: Michael Bain Claude Sommut
references.title: A framework for behavioural claning
references.venue: Machine intelligence,
references.authors: Feryal Behbahani Kyriacos Shiarlis Xi Chen Vitaly Kurin Sudhanshu Kasewa Ciprian Stirbu João Gomes Supratik Paul Frans A Oliehoek João Messias
references.title: Learning from demonstration in the wild
references.venue: arXiv preprint arXiv:1811.03516,
references.authors: Pedro Dal Bó
references.title: Cooperation under the shadow of the future: experimental evidence from infinitely repeated games
references.venue: American economic review,
references.authors: Noam Brown Tuomas Sandholm
references.title: Safe and nested subgame solving for imperfect-information games
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Cameron B Browne Edward Powley Daniel Whitehouse Simon M Lucas Peter I Cowling Philipp Rohlfshagen Stephen Tavener Diego Perez Spyridon Samothrakis Simon Colton
references.title: A survey of monte carlo tree search methods
references.venue: IEEE Transactions on Computational Intelligence and AI in games,
references.authors: Guan-Yu Chen Laurent Saloff-Coste
references.title: On the mixing time and spectral gap for birth and death
references.venue: chains. arXiv preprint arXiv:1304.4346,
references.authors: J. Clark D. Amodei
references.title: Faulty reward functions in the wild
references.venue: https://blog.openai.com/ faulty-reward-functions/,
references.authors: Abhishek Das Satwik Kottur José M.F. Moura Stefan Lee Dhruv Batra
references.title: Learning cooperative visual dialog agents with deep reinforcement learning
references.venue: CoRR, abs/1703.06585,
references.authors: Hal Daumé John Langford Daniel Marcu
references.title: Search-based structured prediction
references.venue: Machine learning,
references.authors: Ashley D Edwards Laura Downs James C Davidson
references.title: Forward-backward reinforcement learning
references.venue: arXiv preprint arXiv:1803.10227,
references.authors: Carlos Florensa David Held Markus Wulfmeier Pieter Abbeel
references.title: Reverse curriculum generation for reinforcement learning
references.venue: arXiv preprint arXiv:1707.05300,
references.authors: Jakob N Foerster Richard Y Chen Maruan Al-Shedivat Shimon Whiteson Pieter Abbeel Igor Mordatch
references.title: Learning with opponent-learning awareness
references.venue: arXiv preprint arXiv:1709.04326,
references.authors: Yang Gao Ji Lin Fisher Yu Sergey Levine Trevor Darrell
references.title: Reinforcement learning from imperfect demonstrations
references.venue: arXiv preprint arXiv:1802.05313,
references.authors: Anirudh Goyal Philemon Brakel William Fedus Timothy Lillicrap Sergey Levine Hugo Larochelle Yoshua Bengio
references.title: Recall traces: Backtracking models for efficient reinforcement learning
references.venue: arXiv preprint arXiv:1804.00379,
references.authors: Todd Hester Matej Vecerik Olivier Pietquin Marc Lanctot Tom Schaul Bilal Piot Dan Horgan John Quan Andrew Sendonaris Gabriel Dulac-Arnold
references.title: Deep q-learning from demonstrations
references.venue: arXiv preprint arXiv:1704.03732,
references.authors: Jonathan Ho Stefano Ermon
references.title: Generative adversarial imitation learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Wenming Hong Ke Zhou
references.title: A note on the passage time of finite-state markov chains
references.venue: Communications in Statistics-Theory and Methods,
references.authors: Ionel-Alexandru Hosu Traian Rebedea
references.title: Playing atari games with deep reinforcement learning and human checkpoint replay
references.venue: arXiv preprint arXiv:1607.05077,
references.authors: Boris Ivanovic James Harrison Apoorva Sharma Mo Chen Marco Pavone
references.title: Barc: Backward reachability curriculum for robotic reinforcement learning
references.venue: arXiv preprint arXiv:1806.06161,
references.authors: Sham Kakade John Langford
references.title: Approximately optimal approximate reinforcement learning
references.venue: URL http://dblp.uni-trier.de/db/conf/icml/ icml2002.html#KakadeL02
references.authors: Max Kleiman-Weiner Mark K Ho Joseph L Austerweil Michael L Littman Joshua B Tenenbaum
references.title: Coordinate to cooperate or compete: abstract goals and joint intentions in social interaction
references.venue: COGSCI,
references.authors: Marc Lanctot Vinicius Zambaldi Audrunas Gruslys Angeliki Lazaridou Julien Perolat David Silver Thore Graepel
references.title: A unified game-theoretic approach to multiagent reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Michael Laskey Sam Staszak Wesley Yu-Shu Hsieh Jeffrey Mahler Florian T Pokorny Anca D Dragan Ken Goldberg. Shiv
references.title: Reducing supervisor burden in dagger using support vectors for efficient learning from demonstrations in high dimensional state spaces
references.venue: In Robotics and Automation (ICRA),
references.authors: Joel Z Leibo Vinicius Zambaldi Marc Lanctot Janusz Marecki Thore Graepel
references.title: Multi-agent reinforcement learning in sequential social dilemmas
references.venue: In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems,
references.authors: Adam Lerer Alexander Peysakhovich
references.title: Maintaining cooperation in complex social dilemmas using deep reinforcement learning
references.venue: arXiv preprint arXiv:1707.01068,
references.authors: Adam Lerer Alexander Peysakhovich
references.title: Learning social conventions in markov games
references.venue: arXiv preprint arXiv:1806.10071,
references.authors: Sergey Levine Chelsea Finn Trevor Darrell Pieter Abbeel
references.title: End-to-end training of deep visuomotor policies
references.venue: Journal of Machine Learning Research,
references.authors: Jiwei Li Will Monroe Alan Ritter Michel Galley Jianfeng Gao Dan Jurafsky
references.title: Deep reinforcement learning for dialogue generation
references.authors: Stephen McAleer Forest Agostinelli Alexander Shmakov Pierre Baldi
references.title: Solving the rubik’s cube without human knowledge
references.venue: arXiv preprint arXiv:1805.07470,
references.authors: Matej Moravcík Martin Schmid Neil Burch Viliam Lisý Dustin Morrill Nolan Bard Trevor Davis Kevin Waugh Michael Johanson Michael H. Bowling
references.title: Deepstack: Expert-level artificial intelligence in no-limit
references.venue: poker. CoRR,
references.authors: Ashvin Nair Bob McGrew Marcin Andrychowicz Wojciech Zaremba Pieter Abbeel
references.title: Overcoming exploration in reinforcement learning with demonstrations
references.venue: arXiv preprint arXiv:1709.10089,
references.authors: Andrew Y Ng Daishi Harada Stuart Russell
references.title: Policy invariance under reward transformations: Theory and application to reward shaping
references.venue: In ICML,
references.authors: Xue Bin Peng Pieter Abbeel Sergey Levine Michiel van de Panne
references.title: Deepmimic: Example-guided deep reinforcement learning of physics-based character skills
references.venue: arXiv preprint arXiv:1804.02717,
references.authors: Alexander Peysakhovich Adam Lerer
references.title: Consequentialist conditional cooperation in social dilemmas with imperfect information
references.venue: arXiv preprint arXiv:1710.06975,
references.authors: Alexander Peysakhovich Adam Lerer
references.title: Prosocial learning agents solve generalized stag hunts better than selfish ones
references.venue: Proceedings of the 17th Conference on Autonomous Agents and MultiAgent Systems,
references.authors: Marc’Aurelio Ranzato Sumit Chopra Michael Auli Wojciech Zaremba
references.title: Sequence level training with recurrent neural networks
references.venue: CoRR, abs/1511.06732,
references.authors: Cinjon Resnick Wes Eldridge David Ha Denny Britz Jakob Foerster Julian Togelius Kyunghyun Cho Joan Bruna
references.title: Pommerman: A multi-agent playground, 2018
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: Simon Schmitt Jonathan J Hudson Augustin Zidek Simon Osindero Carl Doersch Wojciech M Czarnecki Joel Z Leibo Heinrich Kuttler Andrew Zisserman Karen Simonyan
references.title: Kickstarting deep reinforcement learning
references.venue: arXiv preprint arXiv:1803.03835,
references.authors: John Schulman Filip Wolski Prafulla Dhariwal Alec Radford Oleg Klimov
references.title: Proximal policy optimization algorithms
references.venue: arXiv preprint arXiv:1707.06347,
references.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
references.title: Mastering the game of Go with deep neural networks and tree
references.venue: search. Nature,
references.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
references.title: Mastering chess and shogi by self-play with a general reinforcement learning
references.authors: Tom Vodopivec Spyridon Samothrakis Branko Šter
references.title: On monte carlo tree search and reinforcement learning
references.venue: J. Artif. Int. Res.,
references.authors: Jiakai Zhang Kyunghyun Cho
references.title: Query-efficient imitation learning for end-to-end autonomous driving
references.venue: arXiv preprint arXiv:1605.06450,
references.authors: Hongwei Zhou Yichen Gong Luvneesh Mugrai Ahmed Khalifa Andy Nealen Julian Togelius
references.title: A hybrid search agent in pommerman
references.venue: In Proceedings of the 13th International Conference on the Foundations of Digital Games,
references.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
references.title: Reinforcement and imitation learning for diverse visuomotor
references.venue: skills. CoRR,
sections.heading: 1 INTRODUCTION
sections.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.
sections.heading: 3 BACKPLAY
sections.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.
sections.heading: 3.1 QUANTITATIVE ANALYSIS
sections.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.
sections.heading: 3.2 QUALITATIVE ANALYSIS
sections.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.
sections.heading: 4 EXPERIMENTS
sections.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?
sections.heading: 4.1 TRAINING DETAILS
sections.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.
sections.heading: 4.2 MAZE
sections.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.
sections.heading: Algorithm Map Set % Optimal % 0-5 Optimal Avg Suboptimality Std Suboptimality
sections.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.
sections.heading: 4.3 POMMERMAN
sections.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.
sections.heading: 5 CONCLUSION
sections.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?
sections.heading: A APPENDIX
sections.heading: A.1 BACKPLAY HYPERPARAMETERS
sections.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.
sections.heading: A.2 MAZE: DEMONSTRATION DETAILS
sections.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).
sections.heading: A.3 MAZE: NETWORK ARCHITECTURE AND TRAINING PARAMETERS
sections.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].
sections.heading: A.4 MAZE: LEARNING CURVES
sections.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.
sections.heading: A.5 POMMERMAN: OBSERVATION STATE
sections.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.
sections.heading: A.6 POMMERMAN: NETWORK ARCHITECTURE AND TRAINING PARAMETERS
sections.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.
sections.heading: A.7 POMMERMAN: ACTION DISTRIBUTION ANALYSIS
sections.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.
sections.heading: A.8 POMMERMAN: WIN RATES
sections.text: Here we show the per-map win rates obtained by the agent trained with Backlpay on the 100 Pommerman maps.
sections.heading: A.9 PRACTICAL FINDINGS
sections.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).