summaries: The paper presents two methods to learn word embedding matrices that can be stored in much less space compared to traditional d x p embedding matrices, where d is the vocabulary size and p is the embedding size. Two methods are proposed: the first method estimates a p-dimensional embedding for a word as a sum of r tensor products of order n (tensor product of n q-dimensional embeddings).  This representation takes rnq parameters which can be much less than p, since p = q^n. The second method factorizes a full d x p embedding matrix jointly as a tensor product of much smaller t x q matrices and can obtain even larger space savings. Algorithms for efficiently computing full p-dimensional representations are also included. When only dot products are needed, the p-dimensional representations do not need to be explicitly constructed.

summaries: This paper proposes word2ket - a space-efficient form of storing word embeddings through tensor products. The idea is to factorize each d-dimensional vector into a tensor product of much smaller vectors (either with or without linear operators). While this results in a time cost for each word lookup, the space savings are enormous and can potentially impact several applications where the vocabulary size is too large to fit into processor memory (CPU or GPU). The experimental evaluation is done on several tasks like summarization, machine translation and question answering and convincingly demonstrates that one can achieve close to original model performance with very few parameters!

summaries: This paper explores two related methods to reduce the number of parameters required (and hence the memory footprint) of neural NLP models that would otherwise use a large word embedding matrix. Their method, inspired by quantum entanglement, involves computing word embeddings on-the-fly (or by directly computing the output of the "word embedding" with the first linear layer of network). They demonstrate their method can save an impressive amount of memory and does not exhibit big performance losses on three nlp tasks that they explore.

abstractText: Deep learning natural language processing models often use vector word embeddings, such as word2vec or GloVe, to represent words. A discrete sequence of words can be much more easily integrated with downstream neural layers if it is represented as a sequence of continuous vectors. Also, semantic relationships between words, learned from a text corpus, can be encoded in the relative configurations of the embedding vectors. However, storing and accessing embedding vectors for all words in a dictionary requires large amount of space, and may strain systems with limited GPU memory. Here, we used approaches inspired by quantum computing to propose two related methods1, word2ket and word2ketXS, for storing word embedding matrix during training and inference in a highly efficient way. Our approach achieves a hundred-fold or more reduction in the space required to store the embeddings with almost no relative drop in accuracy in practical natural language processing tasks.

title: Compressing word embeddings

venue: In International Conference on Neural Information Processing,

authors:
Sanjeev Arora
Mikhail Khodak
Nikunj Saunshi
Kiran Vodrahalli

title: A compressed sensing view of unsupervised text embeddings, bag-of-n-grams, and LSTMs

authors:
Haim Avron
Michael Kapralov
Cameron Musco
Christopher Musco
Ameya Velingker
Amir Zandieh

title: Random Fourier features for kernel ridge regression: Approximation bounds and statistical guarantees

venue: In Proceedings of the 34th International Conference on Machine Learning,

authors:
Jarosław Buczyński
Joseph M Landsberg

title: Ranks of tensors and a generalization of secant varieties

venue: Linear Algebra and its Applications,

authors:
Benjamin Charlier
Jean Feydy
Joan Glaunes

title: KeOps: Calcul rapide sur GPU dans les espaces à noyaux, 2018

authors:
Danqi Chen
Adam Fisch
Jason Weston
Antoine Bordes

title: Reading Wikipedia to answer opendomain questions

venue: arXiv preprint arXiv:1704.00051,

authors:
Liqun Chen
Yizhe Zhang
Ruiyi Zhang
Chenyang Tao
Zhe Gan
Haichao Zhang
Bai Li
Dinghan Shen
Changyou Chen
Lawrence Carin

title: Improving sequence-to-sequence learning via optimal transport

authors:
Tianqi Chen
Bing Xu
Chiyuan Zhang
Carlos Guestrin

title: Training deep nets with sublinear memory cost

venue: arXiv preprint arXiv:1604.06174,

authors:
Rewon Child
Scott Gray
Alec Radford
Ilya Sutskever

title: Generating long sequences with sparse transformers

venue: arXiv preprint arXiv:1904.10509,

authors:
Christopher De Sa
Megan Leszczynski
Jian Zhang
Alana Marzoev
Christopher R Aberger
Kunle Olukotun
Christopher Ré

title: High-accuracy low-precision training

venue: arXiv preprint arXiv:1803.03383,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Trevor Gale
Erich Elsen
Sara Hooker

title: The state of sparsity in deep neural networks

authors:
Jacob Gardner
Geoff Pleiss
Kilian Q Weinberger
David Bindel
Andrew G Wilson

title: GPyTorch: Blackbox matrix-matrix gaussian process inference with GPU acceleration

authors:
Suyog Gupta
Ankur Agrawal
Kailash Gopalakrishnan
Pritish Narayanan

title: Deep learning with limited numerical precision

venue: In Proceedings of the 32nd International Conference on Machine Learning,

authors:
Song Han
Huizi Mao
William J Dally

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

venue: arXiv preprint arXiv:1510.00149,

authors:
Zhiting Hu
Haoran Shi
Bowen Tan
Wentao Wang
Zichao Yang
Tiancheng Zhao
Junxian He
Lianhui Qin
Di Wang

title: Texar: A modularized, versatile, and extensible toolkit for text generation

venue: arXiv preprint arXiv:1809.00794,

title: Rouge: A package for automatic evaluation of summaries

venue: In Text summarization branches out,

authors:
Yinhan Liu
Myle Ott
Naman Goyal
Jingfei Du
Mandar Joshi
Danqi Chen
Omer Levy
Mike Lewis
Luke Zettlemoyer
Veselin Stoyanov

title: Roberta: A robustly optimized bert pretraining approach

authors:
Minh-Thang Luong
Hieu Pham
Christopher D Manning

title: Effective approaches to attentionbased neural machine translation

venue: In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing,

authors:
Avner May
Jian Zhang
Tri Dao
Christopher Ré

title: On the downstream performance of compressed word embeddings

venue: In Advances in Neural Information Processing Systems, pp

authors:
Paulius Micikevicius
Sharan Narang
Jonah Alben
Gregory Diamos
Erich Elsen
David Garcia
Boris Ginsburg
Michael Houston
Oleksii Kuchaiev
Ganesh Venkatesh

title: Mixed precision training

venue: arXiv preprint arXiv:1710.03740,

authors:
Tomas Mikolov
Ilya Sutskever
Kai Chen
Greg S Corrado
Jeff Dean

title: Distributed representations of words and phrases and their compositionality

authors:
Hesham Mostafa
Xin Wang

title: Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization

venue: In International Conference on Machine Learning,

authors:
Jeffrey Pennington
Richard Socher
Christopher Manning

title: GloVe: Global vectors for word representation

venue: In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing,

authors:
Alec Radford
Jeffrey Wu
Rewon Child
David Luan
Dario Amodei
Ilya Sutskever

title: Language models are unsupervised multitask learners

venue: OpenAI Blog,

authors:
Marc’Aurelio Ranzato
Sumit Chopra
Michael Auli
Wojciech Zaremba

title: Sequence level training with recurrent neural networks

venue: In International Conference on Learning Representations, pp

authors:
Raphael Shu
Hideki Nakayama

title: Compressing word embeddings via deep compositional code learning

authors:
Nimit Sharad Sohoni
Christopher Richard Aberger
Megan Leszczynski
Jian Zhang
Christopher Ré

title: Low-memory neural network training: A technical report

authors:
Jun Suzuki
Masaaki Nagata

title: Learning compact neural word embeddings by parameter space sharing

venue: In International Joint Conference on Artificial Intelligence,

authors:
Jian Zhang
Avner May
Tri Dao
Christopher Ré

title: Low-precision random Fourier features for memory-constrained kernel approximation

venue: arXiv preprint arXiv:1811.00155,

heading: 1 INTRODUCTION

text:
Modern deep learning approaches for natural language processing (NLP) often rely on vector representation of words to convert discrete space of human language into continuous space best suited for further processing through a neural network. For a language with vocabulary of size d, a simple way to achieve this mapping is to use one-hot representation – each word is mapped to its own row of a d× d identity matrix. There is no need to actually store the identity matrix in memory, it is trivial to reconstruct the row from the word identifier. Word embedding approaches such as word2vec (Mikolov et al., 2013) or GloVe (Pennington et al., 2014) use instead vectors of dimensionality p much smaller than d to represent words, but the vectors are not necessarily extremely sparse nor mutually orthogonal. This has two benefits: the embeddings can be trained on large text corpora to capture the semantic relationship between words, and the downstream neural network layers only need to be of width proportional to p, not d, to accept a word or a sentence. We do, however, need to explicitly store the d× p embedding matrix in GPU memory for efficient access during training and inference. Vocabulary sizes can reach d = 105 or 106 (Pennington et al., 2014), and dimensionality of the embeddings used in current systems ranges from p = 300 (Mikolov et al., 2013; Pennington et al., 2014) to p = 1024 (Devlin et al., 2018). The d × p embedding matrix thus becomes a substantial, often dominating, part of the parameter space of a learning model.
In classical computing, information is stored in bits – a single bit represents an element from the set B = {0, 1}, it can be in one of two possible states. A quantum equivalent of a bit, a qubit, is
∗Corresponding author. 1PyTorch implementation available at: https://github.com/panaali/word2ket
fully described by a single two-dimensional complex unit-norm vector, that is, an element from the set C2. A state of an n-qubit quantum register corresponds to a vector in C2n . To have exponential dimensionality of the state space, though, the qubits in the register have to be interconnected so that their states can become entangled; a set of all possible states of n completely separated, independent qubits can be fully represented by C2n instead of C2n . Entanglement is a purely quantum phenomenon – we can make quantum bits interconnected, so that a state of a two-qubit system cannot be decomposed into states of individual qubits. We do not see entanglement in classical bits, which are always independent – we can describe a byte by separately listing the state of each of the eight bits. We can, however, approximate quantum register classically - store vectors of size m using O (logm) space, at the cost of losing the ability to express all possible m-dimensional vectors that an actual O (logm)-qubit quantum register would be able to represent. As we show in this paper, the loss of representation power does not have a significant impact on NLP machine learning algorithms that use the approximation approaches to store and manipulate the high-dimensional word embedding matrix.

heading: 1.1 OUR CONTRIBUTION

text:
Here, we used approaches inspired by quantum computing to propose two related methods, word2ket and word2ketXS, for storing word embedding matrix during training and inference in a highly efficient way2. The first method operates independently on the embedding of each word, allowing for more efficient processing, while the second method operates jointly on all word embeddings, offering even higher efficiency in storing the embedding matrix, at the cost of more complex processing. Empirical evidence from three NLP tasks shows that the new word2ket embeddings offer high space saving rate at little cost in terms of accuracy of the downstream NLP model.
2 FROM TENSOR PRODUCT SPACES TO word2ket EMBEDDINGS

heading: 2.1 TENSOR PRODUCT SPACE

text:
Consider two separable3 Hilbert spaces V and W . A tensor product space of V and W , denoted as V ⊗ W , is a separable Hilbert space H constructed using ordered pairs v ⊗ w, where v ∈ V and w ∈ W . In the tensor product space, the addition and multiplication in H have the following properties
c {v ⊗ w} = {cv} ⊗ w = v ⊗ {cw} , (1) v ⊗ w + v′ ⊗ w = {v + v′} ⊗ w, v ⊗ w + v ⊗ w′ = v ⊗ {w + w′} .
The inner product between v ⊗ w and v′ ⊗ w′ is defined as a product of individual inner products 〈v ⊗ w, v′ ⊗ w′〉 = 〈v, v′〉 〈w,w′〉 . (2)
It immediately follows that ||v ⊗ w|| = ||v|| ||w||; in particular, a tensor product of two unit-norm vectors, from V andW , respectively, is a unit norm vector in V ⊗W . The Hilbert space V ⊗W is a space of equivalence classes of pairs v ⊗ w; for example {cv} ⊗ w and v ⊗ {cw} are equivalent ways to write the same vector. A vector in a tensor product space is often simply called a tensor.
Let {ψj} and {φk} be orthonormal basis sets in V andW , respectively. From eq. 1 and 2 we can see that ∑
j
cjψj ⊗ {∑
k
dkφk } = ∑ j ∑ k cjdkψj ⊗ φk,
〈ψj ⊗ φk, ψj′ ⊗ φk′〉 = δj−j′δk−k′ , where δz is the Kronecker delta, equal to one at z = 0 and to null elsewhere. That is, the set {ψj ⊗ φk}jk forms an orthonormal basis in V ⊗ W , with coefficients indexed by pairs jk and
2In Dirac notation popular in quantum mechanics and quantum computing, a vector u ∈ C2 n
is written as |u〉, and called a ket.
3That is, with countable orthonormal basis.
numerically equal to the products of the corresponding coefficients in V and W . We can add any pairs of vectors in the new spaces by adding the coefficients. The dimensionality of V ⊗W is the product of dimensionalities of V andW . We can create tensor product spaces by more than one application of tensor product,H = U⊗V⊗W , with arbitrary bracketing, since tensor product is associative. Tensor product space of the form
n⊗ j=1 Hj = H1 ⊗H2 ⊗ . . .⊗Hn
is said to have tensor order4 of n.

heading: 2.2 ENTANGLED TENSORS

text:
Consider H = V ⊗ W . We have seen the addition property v ⊗ w + v′ ⊗ w = {v + v′} ⊗ w and similar property with linearity in the first argument – tensor product is bilinear. We have not, however, seen how to express v ⊗ w + v′ ⊗ w′ as φ ⊗ ψ for some φ ∈ V , ψ ∈ W . In many cases, while the left side is a proper vector from the tensor product space, it is not possible to find such φ and ψ. The tensor product space contains not only vectors of the form v ⊗ w, but also their linear combinations, some of which cannot be expressed as φ⊗ ψ. For example, ∑1 j=0 ∑1 k=1 ψj⊗φk√ 4 can
be decomposed as {∑1
j=0 1√ 2 ψj
} ⊗ {∑1
k=1 1√ 2 φk
} . On the other hand, ψ0⊗φ0+ψ1⊗φ1√
2 cannot; no
matter what we choose as coefficients a, b, c, d, we have
1√ 2 ψ0 ⊗ φ0 + 1√ 2 ψ1 ⊗ φ1 6= (aψ0 + bψ1)⊗ (cφ0 + dφ1)
= acψ0 ⊗ φ0 + bdψ1 ⊗ φ1 + adψ0 ⊗ φ1 + bcψ1 ⊗ φ0,
since we require ac = 1/ √ 2, that is, a 6= 0, c 6= 0, and similarly bd = 1/ √ 2, that is, b 6= 0, c 6= 0, yet we also require bd = ad = 0, which is incompatible with a, b, c, d 6= 0. For tensor product spaces of order n, that is, ⊗n j=1Hj , tensors of the form v = ⊗n j=1 vj , where vj ∈ Hj , are called simple. Tensor rank5 of a tensor v is the smallest number of simple tensors that sum up to v; for example, ψ0⊗φ0+ψ1⊗φ1√
2 is a tensor of rank 2. Tensors with rank greater than one
are called entangled. Maximum rank of a tensor in a tensor product space of order higher than two is not known in general (Buczyński & Landsberg, 2013).
2.3 THE word2ket EMBEDDINGS
A p-dimensional word embedding model involving a d-token vocabulary is6 a mapping f : [d] → Rp, that is, it maps word identifiers into a p-dimensional real Hilbert space, an inner product space with the standard inner product 〈·, ·〉 leading to the L2 norm. Function f is trained to capture semantic information from the language corpus it is trained on, for example, two words i, j with 〈f(i), f(j)〉 ∼ 0 are expected to be semantically unrelated. In practical implementations, we represent f as a collection of vectors fi ∈ Rp indexed by i, typically in the form of d× p matrix M , with embeddings of individual words as rows.
We propose to represent an embedding v ∈ Rp of each a single word as an entangled tensor. Specifically, in word2ket, we use tensor of rank r and order n of the form
v = r∑ k=1 n⊗ j=1 vjk, (3)
4Note that some sources alternatively call n a degree or a rank of a tensor. Here, we use tensor rank to refer to a property similar to matrix rank, see below.
5Note that some authors use rank to denote what we above called order. In the nomenclature used here, a vector space of n×m matrices is isomorphic to a tensor product space of order 2 and dimensionality mn, and individual tensors in that space can have rank of up to min(m,n).
6We write [d] = {0, ..., d}.
where vjk ∈ Rq . The resulting vector v has dimension p = qn, but takes rnq = O (rq log p/q) space. We use q ≥ 4; it does not make sense to reduce it to q = 2 since a tensor product of two vectors in R2 takes the same space as a vector in R4, but not every vector in R4 can be expressed as a rank-one tensor in R2 ⊗ R2. If the downstream computation involving the word embedding vectors is limited to inner products of embedding vectors, there is no need to explicitly calculate the qn-dimensional vectors. Indeed, we have (see eq. 2)
〈v, w〉 =
〈 r∑
k=1 n⊗ j=1 vjk, r∑ k′=1 n⊗ j=1 wjk′
〉 =
r,r∑ k,k′=1 n∏ j=1 〈vjk, wjk′〉 .
Thus, the calculation of inner product between two p-dimensional word embeddings, v and w, represented via word2ket takes O ( r2q log p/q ) time and O (1) additional space.
In most applications, a small number of embedding vectors do need to be made available for processing through subsequent neural network layers – for example, embeddings of all words in all sentences in a batch. For a batch consisting of b words, the total space requirement is O (bp+ rq log p/q), instead of O (dp) in traditional word embeddings.
Reconstructing a b-word batch of p-dimensional word embedding vectors from tensors of rank r and order n takesO (brpn) arithmetic operations. To facilitate parallel processing, we arrange the ordern tensor product space into a balanced tensor product tree (see Figure 1), with the underlying vectors vjk as leaves, and v as root. For example, for n = 4, instead of v = ∑ k((v1k ⊗ v2k)⊗ v3k)⊗ v4k
we use v = ∑ k(v1k ⊗ v2k) ⊗ (v3k ⊗ v4k). Instead of performing n multiplications sequentially, we can perform them in parallel along branches of the tree, reducing the length of the sequential processing to O (log n).
Typically, word embeddings are trained using gradient descent. The proposed embedding representation involves only differentiable arithmetic operations, so gradients with respect to individual elements of vectors vjk can always be defined. With the balanced tree structure, word2ket representation can be seen as a sequence of O (log n) linear layers with linear activation functions, where n is already small. Still, the gradient of the embedding vector v with respect to an underlying tunable parameters vlk involves products ∂ (∑ k ∏n j=1 vjk ) /∂vlk = ∏ j 6=l vjk, leading to potentially high Lipschitz constant of the gradient, which may harm training. To alleviate this problem, at each node in the balanced tensor product tree we use LayerNorm (Ba et al., 2016).
3 LINEAR OPERATORS IN TENSOR PRODUCT SPACES AND word2ketXS

heading: 3.1 LINEAR OPERATORS IN TENSOR PRODUCT SPACES

text:
Let A : V → U be a linear operator that maps vectors from Hilbert space V into vector in Hilbert space U ; that is, for v, v′,∈ V , α, β ∈ R, the vector A(αv + βv′) = αAv + βAv′ is a member of U . Let us also define a linear operator B :W → Y . A mapping A ⊗ B is a linear operator that maps vectors from V ⊗ W into vectors in U ⊗ Y . We define A⊗B : V ⊗W → U ⊗ Y through its action on simple vectors and through linearity
(A⊗B) ∑ jk ψj ⊗ φk  =∑ jk (Aψj)⊗ (Bφk),
for ψj ∈ V and φk ∈ U . Same as for vectors, tensor product of linear operators is bilinear∑ j ajAj ⊗(∑ k bkBk ) = ∑ jk ajbk (Aj ⊗Bk) .
In finite-dimensional case, for n× n′ matrix representation of linear operator A and m×m′ matrix representing B, we can represent A⊗B as an mn×m′n′ matrix composed of blocks ajkB.
3.2 THE word2ketXS EMBEDDINGS
We can see a p-dimensional word embedding model involving a d-token vocabulary as a linear operator F : Rd → Rp that maps the one-hot vector corresponding to a word into the corresponding word embedding vector. Specifically, if ei is the i-th basis vector in Rd representing i-th word in the vocabulary, and vi is the embedding vector for that word in Rp, then the word embedding linear operator is F = ∑d i=1 viei
T . If we store the word embeddings a d × p matrix M , we can then interpret that matrix’s transpose, MT , as the matrix representation of the linear operator F .
Consider q and t such that qn = p and tn = d, and a series of n linear operators Fj : Rt → Rq . A tensor product ⊗n j=1 Fj is a Rd → Rp linear operator. In word2ketXS, we represent the d× p word embedding matrix as
F = r∑ k=1 n⊗ j=1 Fjk, (4)
where Fjk can be represented by a q×tmatrix. The resulting matrix F has dimension p×d, but takes rnqt = O (rqtmax(log p/q, log d/t)) space. Intuitively, the additional space efficiency comes from applying tensor product-based exponential compression not only horizontally, individually to each row, but horizontally and vertically at the same time, to the whole embedding matrix.
We use the same balanced binary tree structure as in word2ket. To avoid reconstructing the full embedding matrix each time a small number of rows is needed for a multiplication by a weight matrix in the downstream layer of the neural NLP model, which would eliminate any space saving, we use lazy tensors (Gardner et al., 2018; Charlier et al., 2018). If A is an m× n matrix and matrix B is p× q, then ijth entry of A⊗B is equal to
(A⊗B)ij = ab(i−1)/pc+1,b(j−1)/qc+1bi−b(i−1)/pcp,j−b(j−1)/qcq.
As we can see, reconstructing a row of the full embedding matrix involves only single rows of the underlying matrices, and can be done efficiently using lazy tensors.
4 EXPERIMENTAL EVALUATION OF word2ket AND word2ketXS IN DOWNSTREAM NLP TASKS
In order to evaluate the ability of the proposed space-efficient word embeddings in capturing semantic information about words, we used them in three different downstream NLP tasks: text summarization, language translation, and question answering. In all three cases, we compared the accuracy in the downstream task for the proposed space-efficient embeddings with the accuracy achieved by regular embeddings, that is, embeddings that store p-dimensional vectors for d-word vocabulary using a single d× p matrix.
In text summarization experiments, we used the GIGAWORD text summarization dataset (Graff et al., 2003) using the same preprocessing as (Chen et al., 2019), that is, using 200K examples in training. We used an encoder-decoder sequence-to-sequence architecture with bidirectional forwardbackward RNN encoder and an attention-based RNN decoder (Luong et al., 2015), as implemented in PyTorch-Texar Hu et al. (2018). In both the encoder and the decoder we used internal layers with dimensionality of 256 and dropout rate of 0.2, and trained the models, starting from random weights and embeddings, for 20 epochs. We used the validation set to select the best model epoch, and reported results on a separate test set. We used Rouge 1, 2, and L scores (Lin, 2004). In addition to testing the regular dimensionality of 256, we also explored 400, and 8000, but kept the dimensionality of other layers constant.
The results in Table 1 show that word2ket can achieve 16-fold reduction in trainable parameters at the cost of a drop of Rouge scores by about 2 points. As expected, word2ketXS is much more spaceefficient, matching the scores of word2ket while allowing for 34,000 fold reduction in trainable parameters. More importantly, it offers over 100-fold space reduction while reducing the Rouge scores by only about 0.5. Thus, in the evaluation on the remaining two NLP tasks we focused on word2ketXS.
The second task we explored is German-English machine translation, using the IWSLT2014 (DEEN) dataset of TED and TEDx talks as preprocessed in (Ranzato et al., 2016). We used the same sequence-to-sequence model as in GIGAWORD summarization task above. We used BLEU score
to measure test set performance. We explored embedding dimensions of 100, 256, 400, 1000, and 8000 by using different values for the tensor order and the dimensions of the underlying matrices Fjk. The results in Table 2 show a drop of about 1 point on the BLEU scale for 100-fold reduction in the parameter space, with drops of 0.5 and 1.5 for lower and higher space saving rates, respectively.
The third task we used involves the Stanford Question Answering Dataset (SQuAD) dataset. We used the DrQA’s model (Chen et al., 2017), a 3-layer bidirectional LSTMs with 128 hidden units for both paragraph and question encoding. We trained the model for 40 epochs, starting from random weights and embeddings, and reported the test set F1 score. DrQA uses an embedding with vocabulary size of 118,655 and embedding dimensionality of 300. As the embedding matrix is larger, we can increase the tensor order in word2ketXS to four, which allows for much higher space savings.
Results in Table 3 show a 0.5 point drop in F1 score with 1000-fold saving of the parameter space required to store the embeddings. For order-4 tensor word2ketXS, we see almost 105-fold space saving rate, at the cost of a drop of F1 by less than two points, that is, by a relative drop of less than 3%. We also investigated the computational overhead introduced by the word2ketXS embeddings. For tensors order 2, the training time for 40 epochs increased from 5.8 for the model using regular embedding to 7.4 hours for the word2ketXS-based model. Using tensors of order 4, to gain additional space savings, increased the time to 9 hours. Each run was executed on a single NVIDIA Tesla V100 GPU card, on a 2 Intel Xeon Gold 6146 CPUs, 384 GB RAM machine. While the training time increased, as shown in Fig. 3, the dynamics of model training remains largely unchanged.
The results of the experiments show substantial decreases in the memory footprint of the word embedding part of the model, used in the input layers of the encoder and decoder of sequence-tosequence models. These also have other parameters, including weight matrices in the intermediate layers, as well as the matrix of word probabilities prior to the last, softmax activation, that are not compressed by our method. During inference, embedding and other layers dominate the memory
footprint of the model. Recent successful transformer models like BERT by (Devlin et al., 2018), GPT-2 by (Radford et al., 2019), RoBERTa by (Liu et al., 2019) and Sparse Transformers by (Child et al., 2019) require hundreds of millions of parameters to work. In RoBERTaBASE, 30% of the parameters belong to the word embeddings.
During training, there is an additional memory need to store activations in the forward phase in all layers, to make them available for calculating the gradients in the backwards phase. These often dominate the memory footprint during training, but one can decrease the memory required for storing them with e.g. gradient checkpointing Chen et al. (2016) used recently in Child et al. (2019).

heading: 4.1 RELATED WORK

text: Given the current hardware limitation for training and inference, it is crucial to be able to decrease the amount of memory these networks requires to work. A number of approaches have been used in lowering the space requirements for word embeddings. Dictionary learning (Shu & Nakayama, 2018) and word embedding clustering (Andrews, 2016) approaches have been proposed. Bit encoding has been also proposed Gupta et al. (2015). An optimized method for uniform quantization of floating point numbers in the embedding matrix has been proposed recently (May et al., 2019). To compress a model for low-memory inference, (Han et al., 2015) used pruning and quantization for lowering the number of parameters. For low-memory training sparsity (Mostafa & Wang, 2019) (Gale et al., 2019) (Sohoni et al., 2019) and low numerical precision (De Sa et al., 2018) (Micikevicius et al., 2017) approaches were proposed. In approximating matrices in general, Fourier-based approximation methods have also been used (Zhang et al., 2018; Avron et al., 2017). None of these approaches can mach space saving rates achieved by word2ketXS. The methods based on bit encoding, such as Andrews (2016); Gupta et al. (2015); May et al. (2019) are limited to space saving rate of at most 32 for 32-bit architectures. Other methods, for example based on parameter sharing Suzuki & Nagata (2016) or on PCA, can offer higher saving rates, but their storage requirement is limited by d+p, the vocabulary size and embedding dimensionality. In more distantly related work, tensor product spaces have been used in studying document embeddings, by using sketching of a tensor representing n-grams in the document Arora et al. (2018).

heading: ACKNOWLEDGMENTS

text: T.A. is funded by NSF grant IIS-1453658.


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.

summaries: 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.

summaries: 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:
Brenna D Argall
Sonia Chernova
Manuela Veloso
Brett Browning

title: A survey of robot learning from demonstration

venue: Robotics and autonomous systems,

authors:
Christopher G Atkeson
Stefan Schaal

title: Robot learning from demonstration

venue: In ICML,

authors:
Peter Auer
Nicolo Cesa-Bianchi
Paul Fischer

title: Finite-time analysis of the multiarmed bandit problem

venue: Machine Learning,

authors:
Paul Bakker
Yasuo Kuniyoshi

title: Robot see, robot do: An overview of robot imitation

venue: In AISB96 Workshop on Learning in Robots and Animals,

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston

title: Curriculum learning

venue: In Proceedings of the 26th annual international conference on machine learning,

title: Real-time strategy games: A new AI research challenge

authors:
David Churchill
Michael Buro

title: Build order optimization in Starcraft

venue: In Seventh Artificial Intelligence and Interactive Digital Entertainment Conference,

authors:
Edoardo Conti
Vashisht Madhavan
Felipe Petroski Such
Joel Lehman
Kenneth Stanley
Jeff Clune

title: Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents

venue: In Advances in Neural Information Processing Systems,

authors:
Antoine Cully
J-B Mouret

title: Evolving a behavioral repertoire for a walking robot

venue: Evolutionary computation,

authors:
Antoine Cully
Jeff Clune
Danesh Tarapore
Jean-Baptiste Mouret

title: Robots that can adapt like animals

authors:
Benjamin Eysenbach
Abhishek Gupta
Julian Ibarz
Sergey Levine

title: Diversity is all you need: Learning skills without a reward function

venue: arXiv preprint arXiv:1802.06070,

authors:
Bernard Gorman
Mark Humphrys

title: Imitative learning of combat behaviours in first-person computer games

venue: Proceedings of CGAMES,

authors:
Alex Graves
Greg Wayne
Malcolm Reynolds
Tim Harley
Ivo Danihelka
Agnieszka GrabskaBarwińska
Sergio Gómez Colmenarejo
Edward Grefenstette
Tiago Ramalho
John Agapiou

title: Hybrid computing using a neural network with dynamic external

venue: memory. Nature,

authors:
Stefan Freyr Gudmundsson
Philipp Eisen
Erik Poromaa
Alex Nodet
Sami Purmonen
Bartlomiej Kozakowski
Richard Meurling
Lele Cao

title: Human-like playtesting with deep learning

venue: IEEE Conference on Computational Intelligence and Games (CIG),

authors:
Jack Harmer
Linus Gisslén
Jorge del Val
Henrik Holst
Joakim Bergdahl
Tom Olsson
Kristoffer Sjöö
Magnus Nordin

title: Imitation learning with concurrent actions in 3D games

authors:
Jonathan Ho
Stefano Ermon

title: Generative adversarial imitation learning

authors:
Niels Justesen
Sebastian Risi

title: Learning macromanagement in StarCraft from replays using deep learning

authors:
Niels Justesen
Philip Bontrager
Julian Togelius
Sebastian Risi

title: Deep learning for video game playing

venue: IEEE Transactions on Games,

authors:
Joel Lehman
Kenneth O Stanley

title: Abandoning objectives: Evolution through the search for novelty alone

title: Evolving a diversity of virtual creatures through novelty search and local competition

venue: In Proceedings of the 13th annual conference on Genetic and evolutionary computation,

authors:
Yunzhu Li
Jiaming Song
Stefano Ermon

title: InfoGAIL: Interpretable imitation learning from visual demonstrations

authors:
Laurens van der Maaten
Geoffrey Hinton

title: Visualizing data using t-SNE

venue: Journal of machine learning research,

authors:
Tambet Matiisen
Avital Oliver
Taco Cohen
John Schulman

title: Teacher-student curriculum learning

venue: arXiv preprint arXiv:1707.00183,

authors:
Leland McInnes
John Healy
James Melville

title: Umap: Uniform manifold approximation and projection for dimension reduction

venue: arXiv preprint arXiv:1802.03426,

authors:
Josh Merel
Yuval Tassa
Sriram Srinivasan
Jay Lemmon
Ziyu Wang
Greg Wayne
Nicolas Heess

title: Learning human behaviors from motion capture by adversarial imitation

venue: arXiv preprint arXiv:1707.02201,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Jean-Baptiste Mouret
Jeff Clune

title: Illuminating search spaces by mapping elites

venue: arXiv preprint arXiv:1504.04909,

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

title: Overcoming exploration in reinforcement learning with demonstrations

venue: IEEE International Conference on Robotics and Automation (ICRA),

authors:
Andrew Y Ng
Daishi Harada
Stuart Russell

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

authors:
Santiago Ontanón
Gabriel Synnaeve
Alberto Uriarte
Florian Richoux
David Churchill
Mike Preuss

title: A survey of real-time strategy game ai research and competition in Starcraft

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

authors:
Deepak Pathak
Pulkit Agrawal
Alexei A Efros
Trevor Darrell

title: Curiosity-driven exploration by self-supervised prediction

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

authors:
Justin K Pugh
Lisa B Soros
Kenneth O Stanley

title: Quality diversity: A new frontier for evolutionary computation

venue: Frontiers in Robotics and AI,

authors:
Lawrence Saul
Sam Roweis

title: An introduction to locally linear embedding

venue: Journal of Machine Learning Research,

title: Is imitation learning the route to humanoid robots

venue: Trends in cognitive sciences,

authors:
Tom Schaul
Daniel Horgan
Karol Gregor
David Silver

title: Universal value function approximators

venue: In International conference on machine learning,

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

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

venue: search. nature,

authors:
David Silver
Thomas Hubert
Julian Schrittwieser
Ioannis Antonoglou
Matthew Lai
Arthur Guez
Marc Lanctot
Laurent Sifre
Dharshan Kumaran
Thore Graepel

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

venue: arXiv preprint arXiv:1712.01815,

authors:
Peng Sun
Xinghai Sun
Lei Han
Jiechao Xiong
Qing Wang
Bo Li
Yang Zheng
Ji Liu
Yongsheng Liu
Han Liu

title: TStarBots: Defeating the Cheating Level Built-in AI in StarCraft II in the Full Game

venue: arXiv preprint arXiv:1809.07193,

authors:
Richard S. Sutton
Andrew G. Barto

title: Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018

authors:
Zhentao Tang
Dongbin Zhao
Yuanheng Zhu
Ping Guo

title: Reinforcement learning for buildorder production in StarCraft II

venue: Eighth International Conference on Information Science and Technology (ICIST),

authors:
Joshua B. Tenenbaum
Vin De Silva
John C. Langford

title: A Global Geometric Framework for Nonlinear Dimensionality Reduction

venue: Science Reports,

authors:
Christian Thurau
Christian Bauckhage
Gerhard Sagerer

title: Imitation learning at all levels of game-AI

venue: In Proceedings of the international conference on computer games, artificial intelligence, design and education,

authors:
Oriol Vinyals
Timo Ewalds
Sergey Bartunov
Petko Georgiev
Alexander Sasha Vezhnevets
Michelle Yeo
Alireza Makhzani
Heinrich Küttler
John Agapiou
Julian Schrittwieser

title: Starcraft II: A new challenge for reinforcement learning

venue: arXiv preprint arXiv:1708.04782,

authors:
Wu
Dani Yogatama
Julia Cohen
Katrina McKinney
Oliver Smith
Tom Schaul
Timothy Lillicrap
Chris Apps
Koray Kavukcuoglu
Demis Hassabis
David Silver

title: AlphaStar: Mastering the Real-Time Strategy Game StarCraft II. https://deepmind.com/blog/ alphastar-mastering-real-time-strategy-game-starcraft-ii/, 2019

authors:
Ziyu Wang
Josh S Merel
Scott E Reed
Nando de Freitas
Gregory Wayne
Nicolas Heess

title: Robust imitation of diverse behaviors

authors:
Huikai Wu
Junge Zhang
Kaiqi Huang

title: Msc: A dataset for macro-management in StarCraft II

venue: arXiv preprint arXiv:1710.03131,

heading: 1 INTRODUCTION

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.

heading: 2 BACKGROUND

heading: 2.1 IMITATION LEARNING

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.

heading: 2.2 QUALITY DIVERSITY & BEHAVIORAL REPERTOIRES

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).

heading: 2.3 BANDIT ALGORITHMS & BAYESIAN OPTIMIZATION

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.

heading: 2.4 DIMENSIONALITY REDUCTION

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.

heading: 2.5 UNIVERSAL POLICIES

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.

heading: 3 BEHAVIORAL REPERTOIRE IMITATION LEARNING (BRIL)

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.

heading: 3.1 BEHAVIORAL SPACES FROM DEMONSTRATIONS

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.

heading: 3.2 IMITATION LEARNING ON BEHAVIORAL CLUSTERS

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.

heading: 3.3 LEARNING BEHAVIORAL REPERTOIRES

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.

heading: 4 EXPERIMENTS

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]

heading: 4.1 BEHAVIORAL FEATURE SPACE

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.

heading: 4.2 CLUSTERING

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.

heading: 4.3 PERFORMANCE IN STARCRAFT

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.

heading: 4.4 ONLINE ADAPTATION

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.

heading: 5 DISCUSSION

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.

heading: 6 CONCLUSIONS

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.

heading: A APPENDIX

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.