summaries: The paper proposes behavioral repertoire imitation learning (BRIL) which aims to learn a collection of policy from diverse demonstrations. BRIL learns such a collection by learning a context-dependent policy, where the context variable represents behavior of each demonstration. To obtain a context variable, BRIL rely on user’s knowledge, where the user manually defines a feature space that describes behavior. This feature space is then reduced by using a dimensionality reduction method such as t-SNE. Lastly, the policy is learned by supervised learning (behavior cloning) with a state-context input variable and an action output variable. The method is experimentally evaluated on the StarCraft environment. The results show that BRIL performs better than two baselines: behavior cloning on diverse demonstrations and behavior cloning on clustered demonstrations.  This work examines the problem of using training a policy which can emulate a variety of different strategies based on a set of demonstrations representing this space of strategies.  The proposed method, BRIL, computes a feature vector for each demonstration, and then employs a dimensionality reduction technique to map the demonstrations to a latent space of strategies.  BRIL then preforms behavioral cloning on these demonstrations, with the reduced representation of the current strategy as an additional input to the policy model.  Empirical evaluation of BRIL is conducted in StarCraft II, where the agent is tasked with scheduling the construction of different units (other aspects of play are controlled by built-in AI).  Results show that when conditioned on good strategies, the BRIL model is superior to a base imitation learning model trained without strategy information. This paper presents Behavioral Repertoire Imitation Learning (BRIL) which is a way to learn a policy via imitation learning that can be modulated with different behavior inputs that adjust the policy's behavior.  Demonstrations used in training are labeled with differences in behavior across dimensions (which are then reduced to two dimensions using t-SNE), and then these behavior labels are provided as additional input when training a NN from demonstrations using behavior cloning.  Experimental results are shown for learning a BRIL policy from 7000+ demonstrations of humans playing StarCraft, and are compared to that of learning a single behavior cloned policy trained on all demonstrations as well as behavior cloned policies trained on subsets of demonstrations clustered by their behavior. 
abstractText: Imitation Learning (IL) is a machine learning approach to learn a policy from a set of demonstrations. IL can be useful to kick-start learning before applying reinforcement learning (RL) but it can also be useful on its own, e.g. to learn to imitate human players in video games. However, a major limitation of current IL approaches is that they learn only a single “average” policy based on a dataset that possibly contains demonstrations of numerous different types of behaviors. In this paper, we present a new approach called Behavioral Repertoire Imitation Learning (BRIL) that instead learns a repertoire of behaviors from a set of demonstrations by augmenting the state-action pairs with behavioral descriptions. The outcome of this approach is a single neural network policy conditioned on a behavior description that can be precisely modulated. We apply this approach to train a policy on 7,777 human demonstrations for the build-order planning task in StarCraft II. Dimensionality reduction techniques are applied to construct a lowdimensional behavioral space from the high-dimensional army unit composition of each demonstration. The results demonstrate that the learned policy can be effectively manipulated to express distinct behaviors. Additionally, by applying the UCB1 algorithm, the policy can adapt its behavior – in-between games – to reach a performance beyond that of the traditional IL baseline approach.
authors.name: BEHAVIORAL REPERTOIRE
references.authors: Brenna D Argall Sonia Chernova Manuela Veloso Brett Browning
references.title: A survey of robot learning from demonstration
references.venue: Robotics and autonomous systems,
references.authors: Christopher G Atkeson Stefan Schaal
references.title: Robot learning from demonstration
references.venue: In ICML,
references.authors: Peter Auer Nicolo Cesa-Bianchi Paul Fischer
references.title: Finite-time analysis of the multiarmed bandit problem
references.venue: Machine Learning,
references.authors: Paul Bakker Yasuo Kuniyoshi
references.title: Robot see, robot do: An overview of robot imitation
references.venue: In AISB96 Workshop on Learning in Robots and Animals,
references.authors: Yoshua Bengio Jérôme Louradour Ronan Collobert Jason Weston
references.title: Curriculum learning
references.venue: In Proceedings of the 26th annual international conference on machine learning,
references.authors: Michael Buro
references.title: Real-time strategy games: A new AI research challenge
references.venue: pp. 1534–1535,
references.authors: David Churchill Michael Buro
references.title: Build order optimization in Starcraft
references.venue: In Seventh Artificial Intelligence and Interactive Digital Entertainment Conference,
references.authors: Edoardo Conti Vashisht Madhavan Felipe Petroski Such Joel Lehman Kenneth Stanley Jeff Clune
references.title: Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Antoine Cully J-B Mouret
references.title: Evolving a behavioral repertoire for a walking robot
references.venue: Evolutionary computation,
references.authors: Antoine Cully Jeff Clune Danesh Tarapore Jean-Baptiste Mouret
references.title: Robots that can adapt like animals
references.authors: Benjamin Eysenbach Abhishek Gupta Julian Ibarz Sergey Levine
references.title: Diversity is all you need: Learning skills without a reward function
references.venue: arXiv preprint arXiv:1802.06070,
references.authors: Bernard Gorman Mark Humphrys
references.title: Imitative learning of combat behaviours in first-person computer games
references.venue: Proceedings of CGAMES,
references.authors: Alex Graves Greg Wayne Malcolm Reynolds Tim Harley Ivo Danihelka Agnieszka GrabskaBarwińska Sergio Gómez Colmenarejo Edward Grefenstette Tiago Ramalho John Agapiou
references.title: Hybrid computing using a neural network with dynamic external
references.venue: memory. Nature,
references.authors: Stefan Freyr Gudmundsson Philipp Eisen Erik Poromaa Alex Nodet Sami Purmonen Bartlomiej Kozakowski Richard Meurling Lele Cao
references.title: Human-like playtesting with deep learning
references.venue: IEEE Conference on Computational Intelligence and Games (CIG),
references.authors: Jack Harmer Linus Gisslén Jorge del Val Henrik Holst Joakim Bergdahl Tom Olsson Kristoffer Sjöö Magnus Nordin
references.title: Imitation learning with concurrent actions in 3D games
references.venue: IEEE Conference on Computational Intelligence and Games (CIG),
references.authors: Jonathan Ho Stefano Ermon
references.title: Generative adversarial imitation learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Niels Justesen Sebastian Risi
references.title: Learning macromanagement in StarCraft from replays using deep learning
references.venue: IEEE Conference on Computational Intelligence and Games (CIG),
references.authors: Niels Justesen Philip Bontrager Julian Togelius Sebastian Risi
references.title: Deep learning for video game playing
references.venue: IEEE Transactions on Games,
references.authors: Joel Lehman Kenneth O Stanley
references.title: Abandoning objectives: Evolution through the search for novelty alone
references.venue: Evolutionary computation,
references.authors: Joel Lehman Kenneth O Stanley
references.title: Evolving a diversity of virtual creatures through novelty search and local competition
references.venue: In Proceedings of the 13th annual conference on Genetic and evolutionary computation,
references.authors: Yunzhu Li Jiaming Song Stefano Ermon
references.title: InfoGAIL: Interpretable imitation learning from visual demonstrations
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Laurens van der Maaten Geoffrey Hinton
references.title: Visualizing data using t-SNE
references.venue: Journal of machine learning research,
references.authors: Tambet Matiisen Avital Oliver Taco Cohen John Schulman
references.title: Teacher-student curriculum learning
references.venue: arXiv preprint arXiv:1707.00183,
references.authors: Leland McInnes John Healy James Melville
references.title: Umap: Uniform manifold approximation and projection for dimension reduction
references.venue: arXiv preprint arXiv:1802.03426,
references.authors: Josh Merel Yuval Tassa Sriram Srinivasan Jay Lemmon Ziyu Wang Greg Wayne Nicolas Heess
references.title: Learning human behaviors from motion capture by adversarial imitation
references.venue: arXiv preprint arXiv:1707.02201,
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A Rusu Joel Veness Marc G Bellemare Alex Graves Martin Riedmiller Andreas K Fidjeland Georg Ostrovski
references.title: Human-level control through deep reinforcement learning
references.authors: Jean-Baptiste Mouret Jeff Clune
references.title: Illuminating search spaces by mapping elites
references.venue: arXiv preprint arXiv:1504.04909,
references.authors: Ashvin Nair Bob McGrew Marcin Andrychowicz Wojciech Zaremba Pieter Abbeel
references.title: Overcoming exploration in reinforcement learning with demonstrations
references.venue: IEEE International Conference on Robotics and Automation (ICRA),
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: Santiago Ontanón Gabriel Synnaeve Alberto Uriarte Florian Richoux David Churchill Mike Preuss
references.title: A survey of real-time strategy game ai research and competition in Starcraft
references.venue: IEEE Transactions on Computational Intelligence and AI in games,
references.authors: Deepak Pathak Pulkit Agrawal Alexei A Efros Trevor Darrell
references.title: Curiosity-driven exploration by self-supervised prediction
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops,
references.authors: Justin K Pugh Lisa B Soros Kenneth O Stanley
references.title: Quality diversity: A new frontier for evolutionary computation
references.venue: Frontiers in Robotics and AI,
references.authors: Lawrence Saul Sam Roweis
references.title: An introduction to locally linear embedding
references.venue: Journal of Machine Learning Research,
references.authors: Stefan Schaal
references.title: Is imitation learning the route to humanoid robots
references.venue: Trends in cognitive sciences,
references.authors: Tom Schaul Daniel Horgan Karol Gregor David Silver
references.title: Universal value function approximators
references.venue: In International conference on machine learning,
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
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
references.title: Mastering chess and shogi by self-play with a general reinforcement learning algorithm
references.venue: arXiv preprint arXiv:1712.01815,
references.authors: Peng Sun Xinghai Sun Lei Han Jiechao Xiong Qing Wang Bo Li Yang Zheng Ji Liu Yongsheng Liu Han Liu
references.title: TStarBots: Defeating the Cheating Level Built-in AI in StarCraft II in the Full Game
references.venue: arXiv preprint arXiv:1809.07193,
references.authors: Richard S. Sutton Andrew G. Barto
references.title: Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
references.venue: URL http://incompleteideas.net/book/the-book-2nd. html
references.authors: Zhentao Tang Dongbin Zhao Yuanheng Zhu Ping Guo
references.title: Reinforcement learning for buildorder production in StarCraft II
references.venue: Eighth International Conference on Information Science and Technology (ICIST),
references.authors: Joshua B. Tenenbaum Vin De Silva John C. Langford
references.title: A Global Geometric Framework for Nonlinear Dimensionality Reduction
references.venue: Science Reports,
references.authors: Christian Thurau Christian Bauckhage Gerhard Sagerer
references.title: Imitation learning at all levels of game-AI
references.venue: In Proceedings of the international conference on computer games, artificial intelligence, design and education,
references.authors: Oriol Vinyals Timo Ewalds Sergey Bartunov Petko Georgiev Alexander Sasha Vezhnevets Michelle Yeo Alireza Makhzani Heinrich Küttler John Agapiou Julian Schrittwieser
references.title: Starcraft II: A new challenge for reinforcement learning
references.venue: arXiv preprint arXiv:1708.04782,
references.authors: Wu Dani Yogatama Julia Cohen Katrina McKinney Oliver Smith Tom Schaul Timothy Lillicrap Chris Apps Koray Kavukcuoglu Demis Hassabis David Silver
references.title: AlphaStar: Mastering the Real-Time Strategy Game StarCraft II. https://deepmind.com/blog/ alphastar-mastering-real-time-strategy-game-starcraft-ii/, 2019
references.authors: Ziyu Wang Josh S Merel Scott E Reed Nando de Freitas Gregory Wayne Nicolas Heess
references.title: Robust imitation of diverse behaviors
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Huikai Wu Junge Zhang Kaiqi Huang
references.title: Msc: A dataset for macro-management in StarCraft II
references.venue: arXiv preprint arXiv:1710.03131,
sections.heading: 1 INTRODUCTION
sections.text: Deep Reinforcement learning has shown impressive results, especially for board games (Silver et al., 2017) and video games (Mnih et al., 2015). However, reinforcement learning (RL) has critical shortcomings when reward signals are sparse or interactions with the environment are expensive. There are several attempts to mitigate these shortcomings, including curriculum learning (Bengio et al., 2009; Graves et al., 2016; Matiisen et al., 2017), reward shaping (Ng et al., 1999), curiositydriven exploration (Pathak et al., 2017), diversification (Conti et al., 2018; Eysenbach et al., 2018), and Imitation Learning (Bakker & Kuniyoshi, 1996).
  In this paper, we focus on Imitation Learning (IL), wherein the goal is to learn a policy from a dataset of demonstrations, possibly coming from a human, another artificial system, or a collection of different entities. IL can be combined with RL, either to kick-start the learning process with IL and then improving the policy further with RL (Silver et al., 2016) or by running both methods in parallel (Harmer et al., 2018). Traditional IL techniques result in a single policy, which usually expresses an “averaged” behavior among all the behaviors present in the training data. We see this as a major limitation of IL. It would be more desirable to instead learn a diverse set of policies, expressing all the different types of behaviors present in the dataset. Additionally, having a repertoire of different behaviors allows a system to adapt to changes when it is deployed.
  Addressing the limitations of current IL methods, we present a new IL approach called Behavioral Repertoire Imitation Learning (BRIL), which is inspired by Quality-Diversity (QD) algorithms (Pugh et al., 2016; Mouret & Clune, 2015) and RL methods that learn multiple different behaviors. In contrast to traditional optimization techniques, QD-algorithms attempt to find a diverse set of high-quality solutions rather than a single optimal solution. When QD-algorithms search in policy space, they typically discover hundreds or thousands of different policies controlled by different neural networks. BRIL instead learns a behavioral repertoire using a single model that can be manipulated to express multiple behaviors, similarly to RL algorithms that learn a single policy for
  multiple goals (Schaul et al., 2015; Andrychowicz et al., 2017). BRIL consists of a multi-step process (see Figure 1) wherein the experimenter: (1) extracts state-action pairs (similarly to many IL approaches), (2) designs a set of behavioral dimensions to form a behavioral space (similarly to many QD algorithms) and determines the behavioral description (coordinates in the space) for each demonstration, (3) merges the data to form a dataset of state-action-behavior triplets, and (4) trains a model to predict actions from state-behavior pairs through supervised learning. When deployed, the model can act as a policy and the behavior of the model can be manipulated by changing its behavioral input features.
  BRIL is tested on the build-order planning problem in StarCraft, in which a high-level policy controls the build-order decisions for a bot that has otherwise scripted modules for low-level tasks, similarly to Churchill & Buro (2011); Justesen & Risi (2017). We show that the learned policy can be optimized online by modulating the behavioral features using the Upper Confidence Bounds (UCB1) algorithm, such that it outperforms the traditional IL approach against a fixed opponent. We believe this approach can be particularly useful when modeling human players in a game by expressing the entire range of distinct behaviors instead of the average of all. We hypothesize that this property can allow a system to be more robust to exploitation, which is a concern for AI systems in many games. Furthermore, BRIL could be useful in applications beyond games, such as adaptive and resilient robotics.
sections.heading: 2 BACKGROUND
sections.heading: 2.1 IMITATION LEARNING
sections.text: While Reinforcement Learning (RL) deals with learning a mapping (a policy) between states and actions by interacting with an environment, in Imitation Learning (IL) a policy is learned from demonstrations. Methods based on IL, also known as Learning from Demonstration (LfD), have shown promise in the field of robotics (Bakker & Kuniyoshi, 1996; Atkeson & Schaal, 1997; Schaal, 1999; Argall et al., 2009; Nair et al., 2018) and games (Silver et al., 2016; Justesen & Risi, 2017; Gudmundsson et al., 2018; Thurau et al., 2004; Gorman & Humphrys, 2007; Vinyals et al., 2019; Harmer et al., 2018).
  IL is a form of supervised learning, in which the goal is to learn a policy π(s), mapping a state s ∈ S to a probability distribution over possible actions. In contrast to an RL task, the agent cannot interact with the environment during training but is instead presented with a dataset D of demonstrations. A demonstration dj ∈ D consists of kj sequential state-action pairs, where the action was taken in the state by some policy. While not a general requirement, in this paper a demonstration corresponds to an episode, i.e. starting from an initial state and ending in a terminal state.
  Generative Adversarial Imitation Learning (GAIL) uses a Generative Adversarial Network (GAN) architecture wherein the generator is a policy that produces trajectories (without access to rewards) and the discriminator has to distinguish between the generated trajectories and trajectories from a
  set of demonstrations (Ho & Ermon, 2016). Two extensions of GAIL learn a latent space of the demonstrations (Wang et al., 2017; Li et al., 2017), which results in a conditioned policy similarly to our approach. While our approach requires manually designed behavioral dimensions, this can give the user more control over the learned policy; different behavioral spaces can be beneficial for different purposes. A latent space also does not explicitly bare meaning, in contrast to a manually defined behavioral space. Additionally, our approach learns a low-dimensional behavioral space that is suitable for fast adaptation.
sections.heading: 2.2 QUALITY DIVERSITY & BEHAVIORAL REPERTOIRES
sections.text: Traditional optimization algorithms aim at finding the optimal solution to a problem. Quality Diversity (QD) algorithms, on the other hand, attempt to find a set of high-performing solutions that each behave as differently as possible (Pugh et al., 2016). QD-algorithms usually rely on evolutionary algorithms, such as Novelty Search with Local Competition (NSLC) (Lehman & Stanley, 2011b) or MAP-Elites (Mouret & Clune, 2015). NSLC is a population-based multi-objective evolutionary algorithm with a novelty objective that encourages diversity and a local competition objective that measures an individual’s ability to outperform similar individuals in the population. Individuals are added to an archive throughout the optimization process if they are significantly more novel than previously explored behaviors. MAP-Elites does not maintain a population throughout the evolutionary run, only an archive divided into cells that reflect the concept of behavioral niches in a pre-defined behavioral space. For example, in Cully & Mouret (2016) different cells in the map correspond to different walking gaits for a hexapod robot. Both NSLC and MAP-Elites results in an archive of diverse and high-performing solutions. The pressure toward diversity in QD-algorithms can help the optimization process escape local optima (Lehman & Stanley, 2011a), while the diverse set of solutions also allows for online adaption by switching intelligently between these (Cully et al., 2015). We will describe variations of such an adaption procedure in the next section.
  QD is related to the general idea of learning behavioral repertoires. Where QD-algorithms optimize towards a single quality objective by simultaneously searching for diversity, a behavioral repertoire can consist of solutions optimized towards different objectives as in the Transferability-based Behavioral Repertoire Evolution algorithm (TBR-Evolution) by Cully & Mouret (2016).
sections.heading: 2.3 BANDIT ALGORITHMS & BAYESIAN OPTIMIZATION
sections.text: Given either a discrete set or a continuous distribution of options, we can intelligently decide which options to select to maximize the expected total return over several trials. To do this, we consider the discrete case as a k-armed bandit problem and the continuous case as a Bayesian optimization problem. In the continuous case, the problem can also be simplified to a k-armed bandit problem, simply by picking k options from the continuous space of options.
  The goal of a k-armed bandit problem is to maximize the total expected return after some number of trials by iteratively selecting one of k arms/options, each representing a fixed distribution of returns (Sutton & Barto, 2018). To solve this problem, one must balance exploitation (leveraging an option that has rendered high returns in the past) and exploration (trying options to gain a better estimation of their expected value). A bandit algorithm is a general solution to k-armed bandit problems. One of the most popular of these is the Upper Confidence Bound 1 (UCB1) algorithm (Auer et al., 2002) that first tries each arm once and then always selects the option that at each step maximizes:
  Xj + C
  √ 2 ln t
  nj , (1)
  where Xj is the mean return when selecting option j after t steps, nj is the number of times option j has been selected, and C is a constant that determines the level of exploration.
  This k-armed bandit approach can be considered as the discrete case of the more general approach of Bayesian optimization (BO), in which a continuous black-box objective function is optimized. BO starts with a prior distribution over objective functions, which is then updated based on queries to the black-box function using Bayes’ theorem. The Intelligent Trial and Error algorithm (IT&E) uses BO for robot adaptation to deal with changes in the environment by intelligently searching in the continuous behavioral space of policies found by MAP-Elites (Cully et al., 2015). In their approach,
  the fitness of all solutions in the behavioral space is used to construct a prior distribution of the fitness, which is also called a behavior-performance map. A Bayesian optimizer is then used to sample a point in the map, record the observed performance, and compute a posterior distribution of the fitness. This process is continued until a satisfying solution is found. IT&E could also be applied as an adaptation procedure to the policy found by BRIL, by creating a prior distribution based on some quality information of the demonstrations, e.g. player rating or win-rate. A Bayesian optimizer is then used to optimize the behavioral feature input. In this paper we will, however, simplify the adaption process to a discrete k-armed bandit problem with k manually selected behavioral features and leave the use of Bayesian optimization techniques for future work.
sections.heading: 2.4 DIMENSIONALITY REDUCTION
sections.text: In this paper, the dimensionality of the behavior space is reduced using the t-distributed Stochastic Neighbor Embedding (t-SNE) by Maaten & Hinton (2008). In Stochastic Neighbor Embedding (SNE, a precursor to t-SNE), a graph is embedded by minimizing the distance between two probability distributions measured with the Kullback-Leibler divergence. The first of these probability distributions reflect the similarity between the high-dimensional points, and the second one measures the similarity between the embedded, low dimensional points. The high-dimensional probability is fixed, while the embedding is iteratively updated to minimize the distance between its probability distribution and the fixed one. t-SNE uses a Student t-distribution kernel for the embedding’s probability, solving previously known flukes of SNE such as the crowding problem.
  Even though t-SNE is considered state-of-the-art in dimension reduction, several other techniques could be explored. For instance, certain datasets’ structure can be recovered in low dimensional space using simpler algorithms such as Principal Component Analysis (PCA). Otherwise, other methods such as Isometric Feature Mapping (Isomap) by Tenenbaum et al. (2000), Locally Linear Embedding (LLE) by Saul & Roweis (2001) and Uniform Manifold Approximation and Projection (UMAP) by McInnes et al. (2018) could be used.
sections.heading: 2.5 UNIVERSAL POLICIES
sections.text: In value-based RL, one typically learns a state value function Vπ(s) or a state-action value function Qπ(s, a) for a policy π. Universal Value Function Approximators (UVFA) instead learn a joint distribution Vπ(s, g) or Qπ(s, a, g) over all goals G (Schaul et al., 2015). UVFA can be learned using supervised learning from a training set of optimal values such as V ∗g (s) or Q ∗ g(s, a), or it can be learned through RL by switching between goals both when generating trajectories and when computing gradients. Hindsight Experience Replay is an extension to UVFAs, which performs an additional gradient update with the goal being replaced by the terminal state; this modification can give further improvements when it is infeasible to reach the goals (Andrychowicz et al., 2017). An extension to Generative Adversarial Imitation Learning (GAIL) augments each trajectory with a context (Merel et al., 2017), which specifies the agent’s sub-goals that can be modulated at test-time.
  In our approach, we are not considering goals, but rather behaviors, intending to learn a universal policy π(s, b) over states s ∈ S and behaviors b ∈ B in a particular behavioral space. We are thus combining the QD approach of designing a behavioral space with the idea of learning a universal policy to express behaviors in this space.
sections.heading: 3 BEHAVIORAL REPERTOIRE IMITATION LEARNING (BRIL)
sections.text: This section describes two approaches to learning behavioral repertoires using IL. We first describe how a behavioral space can be formed from demonstrations. Then we introduce a naive IL approach that first clusters demonstrations based on their coordinates in the behavioral space, and then applies traditional IL on each cluster. Finally, BRIL is introduced, which learns a single policy augmented with a behavioral feature input rather than learning multiple policies for each behavioral cluster.
sections.heading: 3.1 BEHAVIORAL SPACES FROM DEMONSTRATIONS
sections.text: A behavioral space consists of some behavioral dimensions that are typically determined by the experimenter. For example, in StarCraft, behavioral dimensions can correspond to the ratio of each
  army unit produced throughout the game to express the strategic characteristics of the player. A behavioral space can require numerous dimensions to be able to express meaningful behavioral relationships between interesting solutions for a problem. Intuitively, if the problem is complex, more dimensions can give a finer granularity in the diversity of solutions. However, there is a trade-off between granularity and adaptation, as low-dimensional spaces are easier to search in. We thus propose the idea of first designing a high-dimensional behavioral space and then reducing the number of dimensions through dimensionality reduction techniques. In our preliminary experiments, it has shown beneficial to reduce the space to two dimensions, as it allows for easy visualization of the data distribution and it also seems to be a good trade-off between granularity and adaptation speed. In preliminary experiments with one-dimensional behavioral spaces, we noticed that nearby solutions could be wildly different.
sections.heading: 3.2 IMITATION LEARNING ON BEHAVIORAL CLUSTERS
sections.text: The naive IL approach for learning behavioral repertories trains n policies on n behaviorally diverse subsets of the demonstrations. This idea is similar to the state-space clustering in Thurau et al. (2004), but here we cluster data points in a behavioral space instead. When a behavioral space is defined, each demonstration can be specified by a particular behavioral description (a coordinate in the Rn dimensional space), where afterward a clustering algorithm can split the dataset into several subsets. Hereafter, traditional IL can be applied to each subset to learn one policy for each behavioral cluster. This approach creates a discrete set of policies similar to current QD algorithms. However, it introduces a dilemma: if the clusters are small, there is a risk of overfitting to these reduced training sets. On the other hand, if the clusters are large but few, the granularity of behaviors is lost.
sections.heading: 3.3 LEARNING BEHAVIORAL REPERTOIRES
sections.text: QD algorithms typically fill an archive with diverse and high-quality solutions, sometimes resulting in thousands of policies stored in a single run, which increases the storage requirements in training as well as in deployment. To reduce the storage requirement, one can decrease the size of the archive, with the trade-off of losing granularity in the behavioral space. The main approach introduced in this paper, called Behavioral Repertoire Imitation Learning (BRIL), solves these issues and reduces overfitting by employing a universal policy instead, in which a single policy is conditioned on a behavioral description. In contrast to QD algorithms, the goal of BRIL is neither to optimize quality nor diversity directly. Instead, BRIL attempts to imitate and express the diverse range of behaviors and the quality that exists in a given set of demonstrations. Additionally, BRIL produces a continuous space of policies which is potentially more expressive than a discrete set.
  BRIL extends the traditional imitation learning setting through the following approach. First, the behavioral characteristics of each demonstration are determined. If the dimensionality of these descriptions is large, it can be useful to reduce the space as described in the earlier section. A training set of state-action-behavior triplets is then constructed, such that the behavior is equal to the behavioral description of the corresponding demonstration. Then, a policy π(s, b) is trained in a supervised way on this dataset to map states and behaviors to actions. Following this approach, the training set is not reduced to small behavioral clusters.
  When the trained policy is deployed, the behavioral feature input can be modulated to manipulate its behavior. The simplest approach is to fix the behavioral features throughout an episode, evaluate the episodic return, and then consider new behavioral features for the next episode. This approach should allow for episodic, or inter-game, adaptivity, which will be explored in our experiments. One could also manipulate the behavioral features during an episode e.g. by learning a meta-policy.
sections.heading: 4 EXPERIMENTS
sections.text: This section presents the experimental results of applying BRIL to the game of StarCraft. Policies are trained to control the build-order planning module of a relatively simple scripted StarCraft bot1 that plays the Terran race. While the policy is trained off-line, our experiments attempt to optimize the playing strength of this bot online, in-between episodes/games, by manipulating its behavior.
  1[REDACTED for anonymity]
sections.heading: 4.1 BEHAVIORAL FEATURE SPACE
sections.text: The behavioral space for a StarCraft build-order policy can be designed in many ways. Inspired by the AlphaStar League Strategy Map (Vinyals et al., 2019), the behavioral features are constructed from the army composition, such that the dimensions represent the ratios of each unit type. We achieve this by traversing all demonstrations in the data set, counting all the army unit creation events, and computing the relative ratios. Each demonstration thus has an n-dimensional behavioral feature description, where n = 15 is the number of army unit types for Terran.
  To form a 2D behavioral space, which allows for easier online search and analysis, we apply tDistributed Stochastic Neighbor Embedding (t-SNE). Fig. 2 visualizes the points of all the demonstrations in this 2D space and Fig. 2a shows four plots where the points are colored to show the ratios of Marines, Marauders, Hellions, and Siege Tanks that were produced during these games.
sections.heading: 4.2 CLUSTERING
sections.text: For the baseline approach that applies IL to behavioral clusters, we use density-based spatial clustering of applications with noise (DBSCAN) with = 0.02 and a minimum number of samples per cluster of 30. We performed a grid-search on these two parameters to find the most meaningful data separation; however, the clustering is not perfect due to the many outliers. The clusters are visualized in Fig. 2b, with outliers shown in black.
sections.heading: 4.3 PERFORMANCE IN STARCRAFT
sections.text: We trained three groups of neural networks, all with three hidden layers and 256 hidden nodes per layer: (1) One baseline model trained on the whole dataset with no augmentation of behavioral features, (2) a BRIL model on the whole dataset with two extra input nodes for the behavioral features (i.e. the coordinates in Fig. 2b), and (3) several cluster baseline models trained only on demonstrations from their respective clusters without the augmented behavioral features.
  We applied these trained policy models as build-order modules in the scripted StarCraft II Terran bot sc2bot. It is important to note that this is a very simplistic bot with several flaws and limitations. Therefore the main goal in this paper is not to achieve human-level performance in StarCraft, but rather to test if BRIL allows us to do manipulate its behavior and enables online adaptation. The build-order module, here controlled by one of our policies, is queried with a state description and returns a build-order action, i.e. which building, research, or unit to produce next. The worker and building modules of the bot perform these actions accordingly, while assault, scout, and army modules control the army units. Importantly, policies we test act in a system that consists of both the bot, the opponent bot, and the game world. When we want to utilize our method for adaptation, we are thus not only adapting to the opponent but also the peculiarities of the bot itself.
  We will first focus on the results of the traditional IL approach. Table 1 shows the number of wins in 100 games on the two-player map CatalystLE as well as the corresponding average behaviors (i.e. the army unit ratios). Our bot played as Terran against the built-in Easy Zerg bot. The traditional IL approach won 41/100 games. IL on behavioral clusters showed very poor performance with a maximum of 18/100 wins by the model trained on C30. Besides the number of wins, we compute the nearest demonstration in the entire data set from the average behavior and use it as an estimate of the policy’s position in the 2D behavioral space. From the estimated point, we calculate the distance to each of the four cluster centroids. This analysis revealed that the policies trained on behavioral clusters express behaviors close to the clusters they were trained on (see the distances to the cluster centroids in Table 1). We hypothesize that the poor win rates of this naive approach are due to their training sets being too small such that the policies do not generalize to many of the states explored in the test environment.
  Table 1 also shows the results for BRIL with the coordinates of the four cluster centroids as behavioral features. BRIL (C11) achieves a win rate of 76/100, thus outperforming traditional IL. These results demonstrate that, for some particular environment, the model can be tuned to achieve a higher performance than traditional IL. Analyzing the behavior of the bot with the behavioral features of C11 reveals that it performs an all-in Marine push, similarly to the behavior of the demonstrations
  in C11 (notice the position of C11 on Fig. 2.b and the illumination of Marines on Fig. 2.a). With the behavioral features of C30, the approach reached a higher win rate than traditional IL; however, this difference was not significant. We also notice that for both BRIL and IL on behavioral clusters, the average expressed behavior is closest to the cluster centroid that it was modulated to behave as, among the four clusters we selected. The results show that the behavior of the learned BRIL policy can be successfully controlled. However, the distances are on average larger than for IL on behavioral clusters.
sections.heading: 4.4 ONLINE ADAPTATION
sections.text: The final test aims to verify that we can indeed use BRIL for online adaptation. We apply the UCB1 algorithm to select behavioral features from the discrete set of four options: {C10, C11, C30, C32} (i.e. the two-dimensional feature descriptions of these cluster centroids). This approach enables the algorithm to switch between behavioral features in-between games based on the return of the previous one, which is 1 for a win and 0 otherwise. The adaptive approach achieves 61/100 wins by identifying the behavior of C11 as the best option. Not surprisingly, the win rate is lower than when having the behavioral features of C11 fixed, while it outperforms traditional IL.
sections.heading: 5 DISCUSSION
sections.text: We proposed two new IL methods in this paper, one which learns a policy that is trained on only one behavioral cluster of data points and one which learns a single modifiable policy on the whole dataset. Our results suggest that policies trained on small behavioral clusters overfit and are thus unable to generalize beyond the states available in the cluster. This drawback might be solved with fewer and larger clusters at the cost of losing granularity in the repertoire of policies. If data is abundant, this approach may also work better while we still suspect the same overfitting would occur. BRIL, on the other hand, is simple to implement and results in a continuous distribution of policies by adjusting the behavioral features. Additionally, the results suggest that BRIL generalizes better, most likely because it learns from the whole training set. However, that generality potentially comes with the cost of higher divergence between the expected behavior (corresponding to the behavioral input features) and the resulting behavior when tested. While an important concern, a divergence is somewhat expected since the test environment is very different from that of the training set (different maps and opponents).
  Previous work showed how IL can kick-start learning before applying RL (Silver et al., 2016; Vinyals et al., 2019). With BRIL, one can easily form a population of diverse solutions instead of just one, which may be a promising approach for domains with a plethora of strategic choices like StarCraft. Promising future work could thus combine BRIL with ideas from AlphaStar to automatically form the initial population of policies used in the AlphaStar League.
sections.heading: 6 CONCLUSIONS
sections.text: We introduced a new method called Behavioral Repertoire Imitation Learning (BRIL). By labeling each demonstration d ∈ D with a behavior descriptor confined within a pre-defined behavioral space, BRIL can learn a policy π(s, b) over states s ∈ S and behaviors b ∈ B. In our experiments, a low-dimensional representation of the behavioral space was obtained through dimensionality reduction. The results in this paper demonstrate that BRIL can learn a policy that, when deployed, can be manipulated by conditioning it with a behavioral feature input b, to express a wide variety of behaviors. Additionally, the observed behavior of the policy resembles the behavior characterized by b. Furthermore, a BRIL trained policy can be optimized online by searching for optimal behavioral features in a given setting. In our experiments, a policy trained with BRIL was optimized online beyond the performance reached by traditional IL, using UCB1 to select among a set of discrete behavioral features.
sections.heading: A APPENDIX
sections.text: A.1 PREDICTION ACCURACY
  Data from StarCraft 2 replays are extracted with sc2reaper2, a tool built using the StarCraft II Learning Environment inspired by the MSC Database (Wu et al., 2017). 7,777 replays of Terran vs. Zerg were processed, extracting state-action pairs every half a second resulting in a dataset of 1,625,671 state-action pairs.
  These states contain an abstraction of the game state similar to the one found in Justesen & Risi (2017). This abstraction includes: (1) the agent’s resources, supply, units and technologies, (2) a tally of the enemy’s units that have been observed, and (3) the agent’s units and technologies in production, including how far they are from being completed.
  2[REDACTED for anonymity]
  Once the replays were post-processed for clustering, the dataset was split into training/test/validation following a 60% / 30% / 10% split per cluster. With this splitting, the three groups of models that were discussed in subsection 4.3 were trained.
  These experiments were carried out ten times per model. Table 2 shows the mean test accuracy and mean test loss over these ten models for the baseline (IL) approach, the novel BRIL approach, and four different cluster baselines (Clusters 10, 11, 30 and 32), which were selected for their wildly different behaviors. The results show that augmenting by behavioral features has no significant effect on the test accuracy or loss. However, the next section shows how our new approach is able to express different behaviors with a single neural network.
  A.2 STARCRAFT
  Video games are popular testbeds for the development and testing of AI algorithms (Justesen et al., 2019). Real-Time Strategy (RTS) games, such as StarCraft, are among the hardest games for algorithms to learn as they contain a myriad of problems, such as dealing with imperfect information, adversarial real-time planning, sparse rewards, or huge state and action spaces (Buro, 2003). Several algorithms and bots have been built by the AI community (Ontanón et al., 2013; Churchill et al., 2016) to compete in tournaments such as the AIIDE StarCraft AI Competition3, the CIG StarCraft RTS AI Competition4 and the Student StarCraft AI Competition5.
  This paper deals with the problem of learning a policy for build-order planning in StarCraft. Similarly to the work by Justesen & Risi (2017), a neural network-based policy is trained using IL from state-action pairs, and the policy is then combined with a bot with scripted procedures for low-level tasks. However, the network in the work by Justesen & Risi (2017) learns an “average” policy, while the approach introduced in this paper is able to learn a behavioral repertoire from demonstrations. The build-order planning problem has also been approached with RL, optimizing a build-order policy for a specific bot (Tang et al., 2018; Sun et al., 2018).
  The StarCraft II Learning Environment (SC2LE) is an API that allows scripted bots and RL algorithms to interact with the game (Vinyals et al., 2017). SC2LE also allows data extraction thereby enabling IL from human demonstrations (Wu et al., 2017). AlphaStar is a recent approach that learns a human-level AI policy for StarCraft II using a combination of IL and RL (Vinyals et al., 2019). First, a neural network was trained from supervised demonstrations. The IL model was then used to seed a tournament with several RL agents (called the AlphaStar League), in which the agents competed. This approach resulted in a series of competitive and diverse behaviors. Despite the skill level of AlphaStar, it does not offer a solution for inter-game adaptation and the diversity of the AlphaStar League has to be managed carefully.
  A.3 ARMY COMPOSITIONS IN-GAME
  Replays in each of the clusters we examined in the bandit problem (that is, C10, C11, C30 and C32) exhibit a particular army composition in the game. Cluster 11, for example, shows a strategy com-
  3http://www.cs.mun.ca/˜dchurchill/starcraftaicomp/ 4http://cilab.sejong.ac.kr/sc_competition/ 5http://sscaitournament.com/
  posed almost purely of Marines (see Fig. 2). Fig. 3 shows screenshots of typical army compositions produced by the BRIL policy with the four different behavioral features.