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. An important goal of AI research is to construct agents that can learn well in new environments BID28 ). An increasingly popular paradigm for this task is deep reinforcement learning (deep RL, BID40 ; BID31 ; ). 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 BID34 BID7 .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 BID32 .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 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 BID12 , requires a reversable environment).2 RELATED WORK Figure 1 . Backplay : We first collect a demonstration, from which we build a curriculum over the states. We then sample a state according to that curriculum and initialize our agent accordingly.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 BID1 Ross et al., 2011; BID10 BID44 BID24 BID33 BID16 BID17 BID0 BID35 . 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 BID14 ), 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 BID38 BID29 BID8 , 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 BID21 , 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 BID12 . 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 BID30 . 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. BID46 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, BID5 BID42 ). 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 and thus to make sure that learned strategies are safe and not exploitable BID4 .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 BID25 BID13 or risky coordination games BID43 . In contrast, humans are much better at finding these coordinating and cooperating equilibria BID3 BID22 . 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?Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627-635, 2011. A APPENDIX
Learn by working backwards from a single demonstration, even an inefficient one, and progressively have the agent do more of the solving itself. This paper presents a method for increasing the efficiency of sparse reward RL methods through a backward curriculum on expert demonstrations.  The paper presents a strategy for solving sparse reward tasks with RL by sampling initial states from demonstrations.