summaries: This paper proposes a method for continual learning. The model has three components: a) a data generator to be used at training time to replay past examples, b) a parameter generator that takes the input observation to produce parameters for c) the actual classifier. The authors demonstrate the method on simple datasets with a stream of 2 or 3 tasks.

summaries: This paper proposes a Dynamic Parameter Generator (DPG) that given a test input modifies the parameters of a classification model. They also propose to regularize the training using a Data Generator (DG) to slow down catastrophic forgetting. DG is used to constrain the training that the internal representations of data generated by DG does not rapidly change. DG removes the need for storage of data or labels.

abstractText: Learning multiple tasks sequentially is important for the development of AI and lifelong learning systems. However, standard neural network architectures suffer from catastrophic forgetting which makes it difficult for them to learn a sequence of tasks. Several continual learning methods have been proposed to address the problem. In this paper, we propose a very different approach, called Parameter Generation and Model Adaptation (PGMA), to dealing with the problem. The proposed approach learns to build a model, called the solver, with two sets of parameters. The first set is shared by all tasks learned so far and the second set is dynamically generated to adapt the solver to suit each test example in order to classify it. Extensive experiments have been carried out to demonstrate the effectiveness of the proposed approach.

authors:
Rahaf Aljundi
Francesca Babiloni
Mohamed Elhoseiny
Marcus Rohrbach
Tinne Tuytelaars

title: Memory aware synapses: Learning what (not) to forget

venue: arXiv preprint arXiv:1711.09601,

authors:
Andrew Brock
Theodore Lim
James M Ritchie
Nick Weston

title: Smash: one-shot model architecture search through hypernetworks

venue: arXiv preprint arXiv:1708.05344,

authors:
Raffaello Camoriano
Giulia Pasquale
Carlo Ciliberto
Lorenzo Natale
Lorenzo Rosasco
Giorgio Metta

title: Incremental robot learning of new objects with fixed update time

venue: In Robotics and Automation (ICRA),

authors:
Zhiyuan Chen
Bing Liu

title: Lifelong machine learning

authors:
Misha Denil
Babak Shakibi
Laurent Dinh
Nando De Freitas

title: Predicting parameters in deep learning

venue: In Advances in neural information processing systems,

authors:
Chrisantha Fernando
Dylan Banarse
Charles Blundell
Yori Zwols
David Ha
Andrei A Rusu
Alexander Pritzel
Daan Wierstra

title: Pathnet: Evolution channels gradient descent in super neural networks

venue: arXiv preprint arXiv:1701.08734,

authors:
Tommaso Furlanello
Jiaping Zhao
Andrew M Saxe
Laurent Itti
Bosco S Tjan

title: Active long term memory networks

venue: arXiv preprint arXiv:1606.02355,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Xu He
Herbert Jaeger

title: Overcoming catastrophic interference using conceptor-aided backpropagation

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

venue: In CVPR,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
James Kirkpatrick
Razvan Pascanu
Neil Rabinowitz
Joel Veness
Guillaume Desjardins
Andrei A Rusu
Kieran Milan
John Quan
Tiago Ramalho
Agnieszka Grabska-Barwinska

title: Overcoming catastrophic forgetting in neural networks

venue: Proceedings of the national academy of sciences,

authors:
Sang-Woo Lee
Jin-Hwa Kim
Jaehyun Jun
Jung-Woo Ha
Byoung-Tak Zhang

title: Overcoming catastrophic forgetting by incremental moment matching

venue: In Advances in Neural Information Processing Systems,

authors:
Jens Lehmann
Robert Isele
Max Jakob
Anja Jentzsch
Dimitris Kontokostas
Pablo N Mendes
Sebastian Hellmann
Mohamed Morsey
Patrick Van Kleef
Sören Auer

title: Dbpedia–a largescale, multilingual knowledge base extracted from wikipedia

venue: Semantic Web,

authors:
Jingyang Li
Maosong Sun
Xian Zhang

title: A comparison and semi-quantitative analysis of words and character-bigrams as features in chinese text categorization

venue: In ACL,

authors:
Shen Li
Zhe Zhao
Renfen Hu
Wensi Li
Tao Liu
Xiaoyong Du

title: Analogical reasoning on chinese morphological and semantic relations

venue: In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics

title: Gradient episodic memory for continual learning

authors:
Nicolas Y Masse
Gregory D Grant
David J Freedman

title: Alleviating catastrophic forgetting using context-dependent gating and synaptic stabilization

venue: arXiv preprint arXiv:1802.01569,

authors:
Michael McCloskey
Neal J Cohen

title: Catastrophic interference in connectionist networks: The sequential learning problem

venue: In Psychology of learning and motivation,

authors:
German I Parisi
Ronald Kemker
Jose L Part
Christopher Kanan
Stefan Wermter

title: Continual lifelong learning with neural networks: A review

venue: arXiv preprint arXiv:1802.07569,

authors:
Jeffrey Pennington
Richard Socher
Christopher D. Manning

title: Glove: Global vectors for word representation

venue: In Empirical Methods in Natural Language Processing (EMNLP), pp. 1532–1543,

authors:
Sylvestre-Alvise Rebuffi
Alexander Kolesnikov
Georg Sperl
Christoph H Lampert

title: icarl: Incremental classifier and representation learning

venue: In Proc. CVPR,

authors:
Jonathan Schwarz
Jelena Luketina
Wojciech M Czarnecki
Agnieszka Grabska-Barwinska
Yee Whye Teh
Razvan Pascanu
Raia Hadsell

title: Progress & compress: A scalable framework for continual learning

venue: arXiv preprint arXiv:1805.06370,

authors:
Ari Seff
Alex Beatson
Daniel Suo
Han Liu

title: Continual learning in generative adversarial nets

venue: arXiv preprint arXiv:1705.08395,

authors:
Joan Serrà
Dı́dac Surı́s
Marius Miron
Alexandros Karatzoglou

title: Overcoming catastrophic forgetting with hard attention to the task

venue: arXiv preprint arXiv:1801.01423,

authors:
Hanul Shin
Jung Kwon Lee
Jaehong Kim
Jiwon Kim

title: Continual learning with deep generative replay

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V Le

title: Sequence to sequence learning with neural networks. In Advances in neural information processing

authors:
Ragav Venkatesan
Hemanth Venkateswara
Sethuraman Panchanathan
Baoxin Li

title: A strategy for an uncompromising incremental learner

venue: arXiv preprint arXiv:1705.00744,

authors:
Wenhui Wang
Nan Yang
Furu Wei
Baobao Chang
Ming Zhou

title: Gated self-matching networks for reading comprehension and question answering

venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),

authors:
Jaehong Yoon
Eunho Yang
Jeongtae Lee
Sung Ju Hwang

title: Lifelong learning with dynamically expandable

authors:
Friedemann Zenke
Ben Poole
Surya Ganguli

title: Continual learning through synaptic intelligence

venue: arXiv preprint arXiv:1703.04200,

heading: 1 INTRODUCTION

text:
It is well-known that neural networks (NNs) suffer from catastrophic forgetting (CF) (McCloskey & Cohen, 1989), which refers to the phenomenon that when learning a sequence of tasks, the learning of each new task may cause the NN to forget the models learned for the previous tasks. Without solving this problem, an NN is hard to adapt to lifelong or continual learning, which is important for AI.
Problem Statement: Given a sequence of supervised learning tasks T = (T1, T2, . . . , TN ), we want to learn them one by one in the given sequence such that the learning of each new task will not forget the models learned for the previous tasks.
In recent years, many approaches (often called continual learning) have been proposed to lessen the effect of CF (Chen & Liu, 2018; Parisi et al., 2018), e.g., dynamically expandable network (DEN) (Yoon et al., 2018), learning without forgetting (LWF) (Li & Hoiem, 2016)), elastic weight consolidation (EWC) (Kirkpatrick et al., 2017), incremental moment matching (IMM) (Lee et al., 2017), gradient episodic memory (GEM) (Lopez-Paz et al., 2017), generative replay (GR) (Shin et al., 2017), etc. These existing studies except DEN and LWF focused on learning a model parameterized by a single joint set of parameters θ∗ which is assumed to work well for all tasks. We call them joint parameterization (JP) methods. DEN and LWF require constantly increasing the number of parameters and thus can result in a huge and complex model.
JP methods, however, suffer from accuracy deterioration. Assume we have two tasks A and B that need to be learned sequentially. Let θ∗A and θ ∗ B be the optimal parameters for Task A and Task B respectively when each of them is learned individually. Let θ∗ be the joint parameters learned by the existing approaches to perform Tasks A and B in sequence. Inevitably, θ∗ is different from θ∗A and/or θ∗B and is highly likely to result in more errors for the two tasks than θ ∗ A and θ ∗ B individually.
∗Equal contribution †Corresponding author
In this paper, we propose a different approach, called Parameter Generation and Model Adaptation (PGMA), to dealing with CF and to significantly reducing accuracy deterioration. PGMA does not learn a joint parameter set θ∗. Instead, it learns a parameter generator f(·) and a shared parameter set θ0. The key idea of PGMA is as follows: The overall classification network, called the solver S, has two disjoint subsets/parts of parameters. The first subset is θ0, which is shared by all tasks learned so far. The second subset is just a place holder H that will be filled by parameters generated by f(·) for each test instance. That is, given a test instance, a set of parameters will be generated by the learned parameter generator f(·) to replace H . Solver S then combines θ0 and the generated parameters for the test instance to classify it. Clearly, unlike existing JP approaches, we do not have a network with a set of fixed parameters for S. The idea is that θ0 contains the common features of all tasks, and the generated parameters for each test instance adapt S for each test instance in order to classify it.
Since f(·) and the shared parameters θ0 will change during training for each new task, forgetting can occur for previous tasks. To deal with it, in training f(·) and S for each task Ti, in addition to the training data of Ti, a small number of replayed samples will be generated by a data generation network for the previous tasks to ensure that the knowledge learned for previous tasks remain stable/unforgotten. Compared with the existing generative replay methods, our method does not need labels for the replayed data because we use the replayed data only to constrain the training of S and f(·) rather than to treat them as surrogates of labeled training data from previous tasks. Further, since in the existing replay methods, the labels are produced by the current learned network itself, the labels can be noisy and biased, which may result in errors being accumulated and propagated to subsequent tasks. Our method does not have this problem.
Apart from reducing the effect of accuracy deterioration of the existing approaches, the proposed approach also has some other advantages. First, no parameter increase or network expansion is needed to learn new tasks. Second, no previous data needs to be stored to enable the system to remember the previously learned models or knowledge.
Experiments conducted using two image datasets (MNIST and CIFAR-10) and two text datasets (DBPedia ontology (Lehmann et al., 2015) and THUCNews (Li et al., 2006)) show that the proposed approach PGMA works well for different scenarios and different types of datasets, and outperforms the existing strong baselines markedly.

heading: 2 PROPOSED PGMA FRAMEWORK

text:
Let the sequence of supervised learning tasks be T = (T1, T2, . . . , TN ). Each task Ti is represented by Ti = {xij , yij |j ∈ (1, . . . , Ni)}, where xij is the j-th example/sample of Ti, and yij is its label. We use (xt, yt) to denote a test instance/example. To simplify the notation, we will just use (xi, yi) to denote a training example from task Ti, omitting the second subscript j. Note that in the paper, we use the terms example, sample, and instance interchangeably.
The proposed parameter generation and model adaptation (PGMA) architecture has three main components:
• Solver S: It is the main classification model. As mentioned in Section 1, the parameter set of S consists of two subsets, θ0 that is shared by all tasks (and instances) and H , a parameter place holder, which will be replaced by the generated parameters set pi (or pt) for each training (or testing) example xi (or xt). pi (or pt) basically serves to adapt the solver S to classify the example in training or testing. This is the key idea of our approach. We adopt this parameter split as several studies (Yoon et al., 2018; Li & Hoiem, 2016; Kirkpatrick et al., 2017) have shown that only part of parameters of a neural network needs to be adjusted when learning a new task. See Section 2.2 • Dynamic Parameter Generator (DPG) f(·): It takes the embedding zi (or zt) of each input training (or testing) example xi (or xt) to generate the parameters pi (or pt) for solver S. Note that we use zi (or zt) rather than the raw data xi (or xt) because the raw data’s dimension can be very high. The embedding zi (or zt) as a low dimensional dense representation reduces the mapping space for DPG and thus reduces the difficulty in its parameter generation. See Section 2.2. • Data Generator (DG): It has two functions. The main function is to generate a set of replayed data or samples {x′m}Mm=1 using its decoder DGD for previous tasks to deal with catastrophic forgetting. The other function is to generate the embedding zi (or zt) of each input training (or testing) example xi (or xt) using its encoder DGE . See Section 2.3.

heading: 2.1 OVERALL APPROACH OF PGMA

text:
We work backward by describing testing first before training. Given a test instance xt, DGE first generates its embedding zt, which is fed to f(·) to generate a set of parameters pt. Solver S then takes xt as input and uses the trained/learned shared parameters θ0 and pt to classify xt. θ0 contains the common features of all tasks learned so far. pt simply adapts S for xt in order to classify xt.
For training, the pipeline of the proposed PGMA framework is shown in Figure 1. Given a new task Ti with its data (xi, yi), solver S and DPG f(·) are jointly trained to learn Ti and also not to forget the previously learned tasks. In each iteration, a set of parameters pi is generated by the current DPG f(zi, µ) for each training instance xi (zi being its embedding), where µ is the set of parameters of the DPG network, which is trained.
In training the solver S and DPG for the new task Ti, both f(·) and the shared parameters θ0 will change, which can cause forgetting in DPG for previous tasks. To keep DPG remembering the acquired knowledge for previous tasks, we minimize the variation of certain layers’ output caused by the changes of θ0 and f(·) using the set of replayed samples {x′m}Mm=1 generated by DG.
PGMA has two training components: (1) DPG and solver S (DPG&S for short), i.e., DPG is optimized together with solver S. (2) DG. The two components have their respective objective functions (see Sections 2.2 and 2.3), and are trained alternately. This is because DPG takes input zi (which is produced by DG) to generate parameters, and alternating training ensures consistent convergence rates of DG and DPG.

heading: 2.2 DYNAMIC PARAMETER GENERATOR (DPG) AND SOLVER S IMPLEMENTATION

text:
Several neural networks can be used to implement DPG for parameter generation, e.g., convolutional neural network (CNN), recurrent neural network (RNN) and multilayer perceptron (MLP). The objective of this paper is not to explore all possible implementations. We found that a straightforward implementation using MLP can already achieve good results. Formally, DPG can be written as:
pi = f(zi, µ) = σ(wDzi + b) (1)
where σ is the activation function, and wD and b are the parameters of DPG and denoted by µ.
For the implementation of solver S, several deep learning networks can be used as well. Again, a MLP is employed in this work. Each layer of the MLP is a perceptron and can be formalized by output = σ(wxinput), where xinput denotes the input of the particular perceptron. We also call a perceptron a basic unit 1. In general, for each basic unit k of the solver S, we can have a shared portion of the parameters θ0,k and a generated portion of the parameters pi,k, i.e.,
θ∗i = combine(θ0,pi) = {[w∗i,k]}Kk=1 = {[θ0,k;pi,k]}Kk=1 (2)
where combine(.) is concatenation and K is the number of basic units that the solver has. In our case, K is the number of hidden layers (basic units) of the solver MLP.
It is important to note that the above is the most general case. In practice, there is no need to adapt all the basic units in the solver, but only a subset of them. In our experiments (Section 3), we will see that adapting only the final layer of the solver MLP can already achieve good results.
1This is because most of the existing networks can be regarded as the composition of multiple basic units, even for those with complex structures, e.g., seq2seq (Sutskever et al., 2014), R-Net (Wang et al., 2017), Resnet (He et al., 2016) and Densenet (Huang et al., 2017). Further, complex structures give us more freedom to decide which part of the parameters should be generated.
However, one may still ask whether the proposed combination method has sufficient capacity to adjust the solver S in general because only part of the parameters are generated. Actually, pik can affect all dimensions of the output of its corresponding basic unit k:
w∗i,kxinput = [θ0,k;pi,k]xinput = θ0,kx 1 input + pi,kx 2 input (3)
where x1input and x 2 input are the block vectors of xinput. pi,kx 2 input can be regarded as the bias and can adapt the output vector to any point in the vector space.
To train DPG&S, we use cross entropy loss (Lce). The objective function of the solver S including DPG f(zi, µ) and θ0 for learning each new classification task Ti is defined as:
minimize µ,θ0
Lce(S(xi, θ∗i ), yi)
s.t. M∑ m=1 ||R(x′m, θ∗i )−R(x′m, θ∗i−1)|| < r (4)
where Lce is the cross entropy loss,R(·) denotes the output of all basic units (which can be any layer or a set of layers2) in solver S, which we will introduce later, and θ∗i is the whole set of parameters of S (θ∗i = combine(pi, θ0)) representing the adaptation of S. We can see that the generated replayed samples x′m are used as constraints to alleviate DPG&S’s forgetting. Specially, we extend the knowledge distillation loss (Hinton et al., 2015) to the general situation. That is, to keep the past learned knowledge, the output of the basic units in the solver should not change much when learning a new task with the help of the generated data. If we do not consider the activation function, the constraints in Eq. 4 can also be written as:
min M∑ m=1 K∑ k=1 ||w∗i,kx′m,k −w∗i−1,kx′m,k|| (5)
where K again denotes the number of basic units and M denotes the number of replayed samples. The basic unit with a smaller k is at the relative lower layer of the solver network.3 x′m,k is the input of the kth basic unit and is calculated through forward propagation, except x′m,1 = DGD(z sample m , θ ′ d) which is the initial replayed sample x′m generated by DG (before optimizing the current task Ti). w∗i,k is the combined parameter introduced in Section 2.2.
Two questions may be asked about Eqs. 4 and 5. (1) Since the replayed data x′ (denoting all x′m) is used in Eqs. 4 and 5, does it play the same role as the original data x from previous tasks? (2) What is the impact of the constraints on learning the new task? We answer the two questions now.
Question 1: The answer is positive. Since the purpose of the constraints is to maintain the learned effect of the old data, clearly, using the original old data x in the constraints is better. However, we proved the positive answer to question 1, which is given in Appendix.
Question 2: In calculating Eq. 5, if we stack all {x′m,k}Mm=1 (column vectors) into a matrix X′k, Eq. 5 can be regarded as constraining w∗i,kX ′ k to remain unchanged. If X ′ k is a row low rank matrix, w∗i,k can be trained to fit the new tasks. Otherwise, especially if X ′ k is a row full rank matrix, w ∗ i,k cannot be trained and therefore cannot learn new tasks. However, benefiting from dynamic parameter generation, our approach will not suffer from this problem. That is because w∗i,k is specially generated through DPG to perform well with input X′k. And the new parameters will be generated to fit new tasks while w∗i,k is able to remain unchanged.

heading: 2.3 DATA GENERATOR (DG)

text:
As indicated earlier, DG has two functions. First, it compresses the original input data xi to zi using its encoder to reduce the number of dimensions of xi and consequently reduces the mapping space of DPG to make the generation of the parameters pi easier. The compression is formulated by:
zi = DGE(xi, θe) (6) 2Note that in this case, the parameters in R is a subset of parameters (θ∗i ) for solver S. To simplify the
expression and without causing confusion, we don’t introduce new symbols and let the symbols unchanged. 3Note that constraining only the units in the last layer can already achieve good results.
where DGE is the encoder of DG with parameters θe.
Second, it generates the replayed data for previous tasks to deal with forgetting in solver S and DPG. Note that DG differs from data generators in the existing generative replay (GR) methods (Shin et al., 2017) as GR needs to generate both the replay data x′m and their labels y ′ m (using the solver learned so far), which can be noisy. DG only generates the data x′m but not the labels (which are not needed by our approach), and then the labeling errors won’t affect our model PGMA, but will hurt GR.
Each replayed sample x′m is generated by the decoder of DG, called DGD:
x′m = DGD(z sample m , θ ′ d) (7)
where zsamplem is the m th sample sampled from the multivariate normal distribution.4 θ′d is the set of parameters of DGD before optimizing the current task Ti.
DG can be implemented with an auto-encoder, e.g., VAE-like (Variational Auto-Encoder (Kingma & Welling, 2013)) and WAE-like (Wasserstein Auto-Encoder) auto-encoders. We use WAE in DG since it can let different examples get a chance to stay far away from each other, which promotes better reconstruction (Tolstikhin et al., 2017).5 Note that DG also suffers from forgetting, which is dealt with like DPG and also using specially designed losses (see below).
To train DG, we use mean square error as the reconstruction loss to enable its replay ability of the past data, and add to it the penalized form of the Wasserstein distance between the distribution of zi and multivariate normal distribution to help generate data (Tolstikhin et al., 2017) (together denoted as Lwae).
Note also since we only have one data generator DG, it has the forgetting problem caused by incremental training of new tasks too. To avoid forgetting in DG, we investigated using loss functions to constrain DG to overcome its forgetting as shown in Figure 2. We describe this approach here:
min M∑ m=1 ||zsamplem −DGE(x′m, θe)|| (8)
min M∑ m=1 ||DGD(zsamplem , θd)− x′m|| (9)
where x′m is the replayed data (see Eq. 7), θe and θd are the encoder’s and decoder’s parameters of DG in the process of learning the new task Ti, respectively, and zsamplem and M have the same meanings as they are in DPG&S. Eq. 8 constrains the consistency of DG’s decoder and encoder over the randomly sampled zsamplem . Eq. 9 ensures that DG’s decoder can still remember the old data. Using Eqs. 8 and 9, we can maintain DG’s ability to reflect the old data. Overall, the final objective function for DG is composed by Lwae, Eq. 8 and 9.

heading: 2.4 THE COMPLETE TRAINING PROCEDURE

text:
Finally, we summarize the whole training procedure of PGMA in Algorithm 1, which is selfexplanatory. “//” is followed by comments. The test procedure is straightforward, see Section 2.1.
4In training, we force zi to satisfy the multivariate normal distribution. We can then sample many zsamplem from the multivariate normal distribution.
5Our approach is not limited to using WAE. Other auto-encoders may also be applied.
Algorithm 1 PGMA (Parameter Generation and Model Adaptation) training
Input: T = {Ti}Ni=1, where Ti = {xij , yij} Initial: Randomly initialize f(·), DG, S; // Learning the first task for all n = 0, . . . , until convergence do
5: Sample a mini-batch from T1; // Training DG Minimize Lwae and then update DG; // Training DPG and S. pn and Sn below // denote a batch of generated parameters
10: // and adapted solvers, respectively Compute pn using Eqs. 1 & 6; // Section 2.2 Construct Sn using pn and θ0; // Section 2.2 Minimize Lce then update f(·) and S;
end for
15: // Learning the subsequent tasks for all i = 2; i ≤ N ; i++ do
Generate replayed samples x′m by DG; for all n = 0, . . . , until convergence do
Sample a mini-batch from Ti; 20: Minimize Lwae, Eqs. 8 &9 and then update
DG; // Section 2.3 Compute pn using Eqs. 1 & 6; Construct Sn using pn and θ0; Minimize Lce, Eq. 5, and then update f(·) and S; // Section 2.2
end for 25: end for

heading: 3 EXPERIMENTS

text: We now evaluate the proposed approach PGMA6 and compare it with state-of-the-art baselines using two image datasets and two text datasets.

heading: Datasets

text: • Two image datasets: (1) MNIST: this dataset consists of 70,000 images of handwritten digits from 0 to 9. We use 60,000/3000/7000 images for training/validation/testing respectively. (2) CIFAR-10: this dataset consists of 60,000 32x32 color images of 10 classes, with 6000 images per class. There are 50,000/3000/7000 images for training/validation/testing respectively. • Two text datasets: (1) DBPedia ontology: this is a crowd-sourced dataset (Lehmann et al., 2015) with 560,000 training samples and 70,000 test samples. Out of the 70,000 test samples, we use 10,000 for validation and 60,000 for test. (2) THUCNews: this dataset consists of 65,000 sentences of 10 classes (Li et al., 2006). We randomly select 50,000/5000/10,000 sentences for training/validation/testing respectively.

heading: Experiment Settings

text:
Data Preparation: To simulate sequential learning, we adopt the same two data processing methods as in (Lee et al., 2017), named disjoint and shuffled. • Disjoint: This method divides each dataset into several subsets of classes. Each subset is a task. For example, we divide the MNIST dataset into two tasks (or subsets of classes). The first task consists of digits (classes) {0, 1, 2, 3, 4} and the second task consists of the remaining digits (classes) {5, 6, 7, 8, 9}. The systems learn the two subsets as two tasks in a sequential fashion and regard them together as 10-class classification. In order to consider more tasks in testing, for MNIST, CIFAR-10, and THUCNews, which all have 10 classes, we created two experiment settings of 2 tasks (5 classes per task) and 5 tasks (2 classes per task). For DBPedia, which has 14 classes, we created three experiment settings, 2 tasks (7 classes per task), 3 tasks (5, 5, and 4 classes for the three tasks respectively), and 5 tasks (3, 3, 3, 3, and 2 classes for the 5 tasks respectively). • Shuffled: This method shuffles the input pixels of an image with a fixed random permutation. Two experiment settings were created: 3 tasks and 5 tasks. In both cases, the dataset for the first task is the original dataset. The datasets for the rest of the tasks are constructed through shuffling. Since shuffling of words in a sentence will change the sentence meaning and results in confusion, thus this experiment is not done on text datasets.
Baselines: We use three state-of-the-art baselines that are representative of the current approaches: 1) EWC (elastic weight consolidation) (Kirkpatrick et al., 2017); 2) IMM (incremental moment matching) (Lee et al., 2017); 3) GR (generative replay) (Shin et al., 2017). We use the open source code released by the authors or the third party for comparison. We use Adam algorithm to update the parameters and also use Adam as a baseline to show how serious the forgetting problem is.
6https://github.com/morning-dews/PGMA tensorflow
Training Details: For fair comparison, our proposed approach uses the same solver (or classifier) as the baselines. That is, a multilayer perceptron is adopted as the solver/classifier (as the baselines all use this method), which is a 3-layer network (i.e., two basic units with each hidden layer as a unit) followed by a softmax layer. For our approach, the total number of parameters in the solver includes both the generated parameters p and the shared parameters θ0. Due to the differences among different datasets, we adopt different settings for them, see Table 5 in Appendix for details. All baselines and our approach use the same setting for the same dataset. We use a 3-layer perceptron (with 2 hidden layers) network (we also call it T-net) for DPG and set the size of each hidden layer to 1000. Each T-net can generate 100 parameters at a time. We can parallel several T-nets in the DPG to generate more parameters when needed. The network parameters are updated using the Adam algorithm with a learning rate of 0.001.

heading: Results and Analysis

text:
Figure 3 shows the test accuracy plots per 40 training steps of each method for each task as the tasks are sequentially learned. IMM is not shown here because IMM works by combining well trained models of individual tasks to form one joint model for all tasks. Thus, we cannot draw an accuracy curve with increased training steps like others. However, its final results and those of the other systems are given in Tables 1 and 2. Shuffled CIFAR-10 is also not included in the figure because our experiments show that it cannot be learned by CNN. It is also not used in any existing paper. Note that due to space limitations, Figure 3 only plots the results of those settings with only 2 and 3 tasks.
From Figure 3, we can make the following observations:
(1). The proposed PGMA method consistently outperforms the baselines in overcoming forgetting, by a big margin in most cases.
(2). EWC does not perform well for the disjoint setting. GR is better but still poorer than our method. Adam’s results show that forgetting is very serious for all datasets and settings.
Time efficiency: Due to DPG, our method uses slightly more time than baselines, under 25% for training and under 28% for testing compared to GR, which is efficient. This is a small price to pay for the major gain in accuracy in dealing with catastrophic forgetting.
Memory usage: There is no need for our method to save data, which results in a large memory saving. For more details about time efficiency and memory usage, please see Appendix (Section C).
From Table 1, we can see that our PGMA method is consistently superior to EWC, GR, and IMM on different datasets with 2 or 3 tasks (5 tasks results are given in Table 2). We believe that is because our PGMA model can reduce the effect of the accuracy deterioration problem discussed in Section 1. Adam’s results show that forgetting is very serious as it does not deal with the forgetting problem. EWC’s performance is poor for the disjoint case (a more realistic setting in practice), which is also reported by other researchers (Lee et al., 2017). Appendix has the results for only the last task.
Table 2 shows the results for 5 tasks. EWC and Adam are not included as they performed poorly. Again, we observe that our PGMA method is markedly better than the baselines.

heading: Ablation Study

text:
Here we study how the system behaves with less and less parameters in θ0 or more and more parameters replaced by the parameters generated by DPG. We selected the disjoint MNIST 2 tasks setting to conduct the experiment as it is more useful than the shuffled setting and also more difficult.
Table 3 shows the accuracy results (averaged in the same way as in Table 1) when a portion of the parameters in only the last layer of the solver is replaced by the parameters generated by DPG. We observe that the accuracy improves with increased percentages of parameters being replaced.
The best accuracy is obtained when 80% of the parameters in the last layer are replaced through DPG, and the accuracy won’t further improve with more replaced parameters. This observation indicates that replacing a part of parameters in solver to adapt new input tasks is sufficient. The same conclusion can also be made by replacing the parameters in the first hidden layer of the solver (which has 2 hidden layers). We fix the replacing percentage of the last layer to 20%, and then increase the replacing percentages of the first layer. The best accuracy reaches 94.31%(±0.84%) when replacing 40% parameters of the first layer, which gains only 1.87% in accuracy compared with no replacement. This result indicates that it suffices to replace the parameters in the last layer.
Table 4 shows the contribution of different components. We can see a significant drop if DPG is removed. The second row gives the performance of our model when only DG and constraints are used. The third row shows the result without using constraints (DG+label(like GR)) but replacing them with the replay method. We can see that constraints work better than predicting labels.

heading: 4 RELATED WORK

text:
Many approaches have been proposed to deal with catastrophic forgetting (CF), which is one of the challenging problems of neural networks for lifelong learning (Chen & Liu, 2018). EWC (Kirkpatrick et al., 2017) quantifies the importance of weights to previous tasks, and selectively alters the learning rates of weights. Following EWC, Zenke et al. (2017) measured the synapse consolidation strength in an online fashion and used it as regularization. Learning without forgetting (LWF) (Li & Hoiem, 2016) feeds the old network with new training data in new tasks and regards the output as ”pseudolabels”. In Incremental Moment Matching (IMM) (Lee et al., 2017), each trained network on one task is preserved and all networks are merged into one at the end of the sequence of tasks.
Above approaches focus on adjusting the network weights. Another main approach is to add some data of past tasks to the new task training to prevent forgetting the past. Gradient Episodic Memory (GEM) (Lopez-Paz et al., 2017) stores a subset of training data for every finished task, and limits the loss function on these so-called ”memories”. Instead of keeping some real data from previous tasks, Generative Replay (GR) (Shin et al., 2017) keeps data generators for previous tasks and learns using a mix of real data of the new tasks and replayed data of previous tasks. Seff et al. (2017) proposed to solve continual generative modeling by combining the ideas of data generation and EWC.
Other existing approaches include iCaRL (Rebuffi et al., 2017), Pathnet (Fernando et al., 2017), memory aware synapses (Aljundi et al., 2017), phantom sampling (Venkatesan et al., 2017), active long term memory networks (Furlanello et al., 2016), conceptor-aided backprop (He & Jaeger, 2018), gating networks (Masse et al., 2018; Serrà et al., 2018), dynamically expandable networks (DEN) (Yoon et al., 2018), progress & compress (Schwarz et al., 2018) (active column is distilled into the knowledge base, taking care to protect any previously acquired skills), and incremental regularized least squares (Camoriano et al., 2017). Most of those works suffer from accuracy deterioration as discussed in Section 1 while some dynamically expanding the network size (e.g., DEN and LWF), which results in a huge and complex model. Our method is different from these existing approaches.
Several existing works generate parameters, but they are for different purposes. Denil et al. (2013) trained several different architectures by learning only a small number of weights and predicting the rest. Ha et al. (2016) used a small network to generate the weights for a larger network. Brock et al. (2017) learned an auxiliary HyperNet to generate weights for the main model. Our method uses the generated parameters for model adaptation for continual learning.

heading: 5 CONCLUSION

text: This paper proposed a novel approach PGMA to dealing with catastrophic forgetting. The approach learns to build a model with two sets of parameters. The first set is shared by all tasks learned so far and the second set is dynamically generated to adapt the model (solver) to suit each individual test example. As we discussed in related work, this is different from all existing methods. Experimental results showed that the proposed approach outperformed the existing baseline methods markedly.

heading: ACKNOWLEDGMENTS

text: We thank Zhangming Chan and Shen Gao for helping check the code. This work was supported by the National Key Research and Development Program of China (No. 2017YFC0804001). Bing Liu’s work was partially supported by National Science Foundation (NSF) under grant no. IIS 1838770, by a research contract with Huawei Technologies Co. Ltd., and by a research gift from Tencent Holdings Limited. Rui Yan’s work was supported by the National Science Foundation of China (NSFC No. 61672058; NSFC No. 61876196), CCF-Tencent Open Research Fund and Microsoft Research Asia (MSRA) Collaborative Research Program.

heading: APPENDIX

heading: A PROOF FOR QUESTION 1

text:
Proof: Our objective is to minimize ||R(x, θ∗i )−R(x, θ∗i−1)||. SinceR(·) is differentiable and its derivative function is bounded (as it uses 1-Lipschitz activation function, e.g., RELU or tanh), R(·) thus satisfies the Lipschitz condition. After some manipulation, we obtain:
||R(x, θ∗i )−R(x, θ∗i−1)|| = ||R(x, θ∗i )−R(x′, θ∗i ) +R(x′, θ∗i )−R(x′, θ∗i−1) +R(x′, θ∗i−1)−R(x, θ∗i−1)|| ≤ ||R(x, θ∗i )−R(x′, θ∗i )||+ ||R(x′, θ∗i )−R(x′, θ∗i−1)||+ ||R(x′, θ∗i−1)−R(x, θ∗i−1)|| ≤ L1||(x− x′)||+ ||R(x′, θ∗i )−R(x′, θ∗i−1)||+ L2||(x− x′)|| = ||R(x′, θ∗i )−R(x′, θ∗i−1)||︸ ︷︷ ︸
minimize replayed samples
+(L1 + L2)||(x− x′)||
(10)
where the last inference is based on Lipschitz continuity, and L1 and L2 are Lipschitz constants. We can see that if the solver has a small Lipschitz constant or the DG’s reconstruction error is small, minimizing Eq. 4 is consistent with constraining using the original data.

heading: B PARAMETER SETTINGS

heading: C MORE EXPERIMENTAL RESULTS

heading: Memory

text:
• The memory used by our model is around 151.49MB, by IMM is around 38.96MB * task num (task num will be 3 if there are three tasks), and by GR is around 70.13MB. The memory required by all these systems are very small as compared to the total memory available in a modern computer.
• Our data generator DG has around 1,460,361 parameters (around 44.57MB, calculated by 32 Byte per parameter), which is fixed. Saving data would need much more memory. Taking the MNIST dataset as an example. It has 60,000 training samples and the size of each sample is 28*28. The memory needed to store the data is 28*28*60,000 = 47,040,000 (around 358.89MB, calculated by 8 Byte per unit). And this number multiplies when the number of tasks increases.

heading: Training and Test Time

text:
Taking the CIFAR10 dataset as an example (others are similar), the total time used by our model and baselines are shown in Table 6. We can see that our method needs a bit more time than baselines but not too much (under 25% for training and under 28% for testing compared with GR). This is a small price to pay for the major gain in accuracy and in dealing with the catastrophic forgetting problem.
Accuracy on the Last Task
ADAM gets the best accuracy on the last task as Adam optimizer learns the new task only and does not need to worry about the forgetting problem on the old tasks. For the last task, our PGMA system obtained comparable accuracy on average with the baselines designed for overcoming forgetting. However, we are much better at preventing forgetting of old tasks. The results for the last task are given in Table 7. Note that although EWC is quite good at the last task but it suffers seriously from forgetting as shown in Table 1 or Figure 3, which is consistent with results reported in other papers.

title: OVERCOMING CATASTROPHIC FORGETTING FOR CONTINUAL LEARNING VIA MODEL ADAPTATION


summaries: This paper used graph neural networks to do relational reasoning of multi-agent systems to predict the actions and returns of MARL agents that they call Relational Forward Modeling. They used RFM to analyze and assess the coordination between agents in three different multi-agent environments. They then constructed an RFM-aumented RL agent and showed improved training speeds over non relational reasoning baseline methods.

summaries: This paper studies predicting multi-agent behavior using a proposed neural network architecture. The architecture, called a relational forward model (RFM) is the same graph network proposed by Battaglia et al., 2018, but adds a recurrent component. Two tasks are define: predict the next action of each agent, and predict the sum of future rewards. The paper demonstrates that RFMs outperform two baselines and two ablations. The authors also show that edge activation magnitudes are correlated with certain phenomenons (e.g. an agent walking towards an entity, or an entity being “on” or “off”). The authors also show that appending the output of a pre-trained RFM to the state of a policy can help it learn faster.

abstractText: The behavioral dynamics of multi-agent systems have a rich and orderly structure, which can be leveraged to understand these systems, and to improve how artificial agents learn to operate in them. Here we introduce Relational Forward Models (RFM) for multi-agent learning, networks that can learn to make accurate predictions of agents’ future behavior in multi-agent environments. Because these models operate on the discrete entities and relations present in the environment, they produce interpretable intermediate representations which offer insights into what drives agents’ behavior, and what events mediate the intensity and valence of social interactions. Furthermore, we show that embedding RFM modules inside agents results in faster learning systems compared to non-augmented baselines. As more and more of the autonomous systems we develop and interact with become multi-agent in nature, developing richer analysis tools for characterizing how and why agents make decisions is increasingly necessary. Moreover, developing artificial agents that quickly and safely learn to coordinate with one another, and with humans in shared environments, is crucial.

authors:
Trapit Bansal
Jakub Pachocki
Szymon Sidor
Ilya Sutskever
Igor Mordatch

title: Emergent Complexity via Multi-Agent Competition

authors:
Peter W. Battaglia
Razvan Pascanu
Matthew Lai
Danilo Rezende
Koray Kavukcuoglu

title: Interaction Networks for Learning about Objects, Relations and Physics

authors:
Kyunghyun Cho
Bart van Merrienboer
Caglar Gulcehre
Dzmitry Bahdanau
Fethi Bougares
Holger Schwenk
Yoshua Bengio

title: Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation

authors:
Lasse Espeholt
Hubert Soyer
Remi Munos
Karen Simonyan
Volodymir Mnih
Tom Ward
Yotam Doron
Vlad Firoiu
Tim Harley
Iain Dunning
Shane Legg
Koray Kavukcuoglu

title: IMPALA: Scalable Distributed Deep-RL with Importance

venue: Weighted Actor-Learner Architectures. arXiv,

authors:
Jakob N. Foerster
Yannis M. Assael
Nando de Freitas
Shimon Whiteson

title: Learning to Communicate with Deep Multi-Agent Reinforcement Learning

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

title: Learning with Opponent-Learning Awareness

authors:
Justin Gilmer
Samuel S. Schoenholz
Patrick F. Riley
Oriol Vinyals
George E. Dahl

title: Neural Message Passing for Quantum Chemistry. 2017

venue: URL http://arxiv.org/abs/1704

authors:
Jessica B. Hamrick
Andrew J. Ballard
Razvan Pascanu
Oriol Vinyals
Nicolas Heess
Peter W. Battaglia

title: Metacontrol for Adaptive Imagination-Based Optimization. 2017

venue: URL http: //arxiv.org/abs/1705.02670

authors:
He He
Jordan Boyd-Graber
Kevin Kwok
Hal Daumé

title: Opponent Modeling in Deep Reinforcement Learning

venue: arXiv, 2016a. URL http://arxiv.org/abs/1609.05559

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

venue: In IEEE International Conference on Computer Vision (ICCV), volume 11-18-Dece,

authors:
Zhang-Wei Hong
Shih-Yang Su
Tzu-Yun Shann
Yi-Hsiang Chang
Chun-Yi Lee

title: A Deep Policy Inference Q-Network for Multi-Agent Systems. 2017

venue: URL https://arxiv.org/ abs/1712.07893

title: VAIN: Attentional Multi-agent Predictive Modeling. arXiv, 2017

venue: URL http: //arxiv.org/abs/1706.06122

authors:
Edward Hughes
Joel Z Leibo
Matthew G Philips
Karl Tuyls
Edgar A Du Nez-Guzmán
Antonio García
Castã Neda
Iain Dunning
Tina Zhu
Kevin R Mckee
Raphael Koster
Heather Roff
Thore Graepel

title: Inequity aversion resolves intertemporal social dilemmas

authors:
Max Jaderberg
Wojciech M. Czarnecki
Iain Dunning
Luke Marris
Guy Lever
Antonio Garcia Castaneda
Charles Beattie
Neil C. Rabinowitz
Ari S. Morcos
Avraham Ruderman
Nicolas Sonnerat
Tim Green
Louise Deason
Joel Z. Leibo
David Silver
Demis Hassabis
Koray Kavukcuoglu
Thore Graepel

title: Human-level performance in first-person multiplayer games with population-based deep reinforcement

venue: URL http://arxiv.org/abs/1807.01281

authors:
Thomas Kipf
Ethan Fetaya
Kuan-Chieh Wang
Max Welling
Richard Zemel

title: Neural Relational Inference for Interacting Systems. arXiv, 2018

venue: URL http://arxiv.org/abs/1802

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

title: A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning

venue: Advances in Neural Information Processing Systems

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

title: Multi-agent Reinforcement Learning in Sequential Social Dilemmas

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

authors:
Adam Lerer
Alexander Peysakhovich

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

authors:
Ryan Lowe
Yi Wu
Aviv Tamar
Jean Harb
Pieter Abbeel
Igor Mordatch

title: Multi-Agent ActorCritic for Mixed Cooperative-Competitive Environments. arXiv, 2017

venue: URL http://arxiv. org/abs/1706.02275

authors:
Ari S. Morcos
David G.T. Barrett
Neil C. Rabinowitz
Matthew Botvinick

title: On the importance of single directions for generalization

authors:
Chris Olah
Alexander Mordvintsev
Ludwig Schubert

title: Feature Visualization. Distill, 2(11):e7, 2017

venue: ISSN 2476-0757. doi: 10.23915/distill.00007. URL https://distill.pub/2017/ feature-visualization

authors:
Razvan Pascanu
Yujia Li
Oriol Vinyals
Nicolas Heess
Lars Buesing
Sebastien Racanière
David Reichert
Théophane Weber
Daan Wierstra
Peter Battaglia

title: Learning model-based planning from scratch

authors:
Julien Perolat
Joel Z. Leibo
Vinicius Zambaldi
Charles Beattie
Karl Tuyls
Thore Graepel

title: A multi-agent reinforcement learning model of common-pool resource appropriation

authors:
Alexander Peysakhovich
Adam Lerer

title: Consequentialist conditional cooperation in social dilemmas with imperfect information

venue: arXiv, 2017a. URL

title: Prosocial learning agents solve generalized Stag Hunts better than selfish ones. arXiv, 2017b. URL http://arxiv.org/abs/1709.02865

authors:
Roberta Raileanu
Emily Denton
Arthur Szlam
Rob Fergus

title: Modeling Others using Oneself in Multi-Agent Reinforcement Learning

venue: arXiv preprint arXiv:1902.09640,

authors:
David Raposo
Adam Santoro
David Barrett
Razvan Pascanu
Timothy Lillicrap
Peter Battaglia

title: Discovering objects and their relations from entangled scene

venue: representations. arXiv,

authors:
Adam Santoro
David Raposo
David G.T. Barrett
Mateusz Malinowski
Razvan Pascanu
Peter Battaglia
Timothy Lillicrap

title: A simple neural network module for relational reasoning. arXiv, 2017

venue: URL http://arxiv.org/abs/1706.01427

authors:
Franco Scarselli
Marco Gori
Ah Chung Tsoi
Markus Hagenbuchner
Gabriele Monfardini

title: The graph neural network model

venue: IEEE Transactions on Neural Networks,

authors:
Sainbayar Sukhbaatar
Arthur Szlam
Rob Fergus

title: Learning Multiagent Communication with Backpropagation

venue: arXiv,

authors:
Nicholas Watters
Andrea Tacchetti
Theophane Weber
Razvan Pascanu
Peter Battaglia
Daniel Zoran

title: Visual Interaction Networks. arXiv, 2017

venue: URL http://arxiv.org/abs/1706

authors:
Théophane Weber
Sébastien Racanière
David P. Reichert
Lars Buesing
Arthur Guez
Danilo Jimenez Rezende
Adria Puigdomènech Badia
Oriol Vinyals
Nicolas Heess
Yujia Li
Razvan Pascanu
Peter Battaglia
Demis Hassabis
David Silver
Daan Wierstra

title: ImaginationAugmented Agents for Deep Reinforcement Learning. 2017

authors:
Jason Yosinski
Jeff Clune
Anh Nguyen
Thomas Fuchs
Hod Lipson

title: Understanding Neural Networks Through Deep Visualization

authors:
Vinicius Zambaldi
David Raposo
Adam Santoro
Victor Bapst
Yujia Li
Igor Babuschkin
Karl Tuyls
David Reichert
Timothy Lillicrap
Edward Lockhart
Murray Shanahan
Victoria Langston
Razvan Pascanu
Matthew Botvinick
Oriol Vinyals
Peter Battaglia

title: Relational Deep Reinforcement Learning

authors:
Matthew D Zeiler
Rob Fergus

title: Visualizing and Understanding

venue: Convolutional Networks

authors:
Eric Zhan
Stephan Zheng
Yisong Yue
Long Sha
Patrick Lucey

title: Generative Multi-Agent Behavioral Cloning

authors:
Stephan Zheng
Yisong Yue
Patrick Lucey

title: Generating Long-term Trajectories Using Deep Hierarchical Networks. 2017

venue: URL http://arxiv.org/abs/1706.07138

heading: 1 INTRODUCTION

text:
The study of multi-agent systems has received considerable attention in recent years and some of the most advanced autonomous systems in the world today are multi-agent in nature (e.g. assembly lines and warehouse management systems). In particular, research in multi-agent reinforcement learning (MARL), where multiple learning agents perceive and act in a shared environment, has produced impressive results (Jaderberg et al., 2018; Pachocki et al., 2018; Leibo et al., 2017; Hughes et al., 2018; Peysakhovich & Lerer, 2017a; Lerer & Peysakhovich, 2017; Bansal et al., 2017; Lanctot et al., 2017).
One of the outstanding challenges in this domain is how to foster coordinated behavior among learning agents. In hand-engineered multi-agent systems (e.g. assembly lines), it is possible to obtain coordination by design, where expert engineers carefully orchestrate each agent’s behavior and role in the system. This, however, rules out situations where either humans or artificial learning agents are present in the environment. In learning-based systems, there have been some successes by introducing a centralized controller (D’Andrea, 2012; Foerster et al., 2016; 2017; Hong et al., 2017; Lowe et al., 2017). However, these cannot scale to large number of agents or to mixed human-robot ensembles. There is thus an increasing focus on multi-agent systems that learn how to coordinate on their own (Jaderberg et al., 2018; Pachocki et al., 2018; Perolat et al., 2017).
Alongside the challenges of learning coordinated behaviors, there are also the challenges of measuring them. In learning-based systems, the analysis tools currently available to researchers focus on the functioning of each single agent, and are ill-equipped to characterize systems of diverse agents as a whole. Moreover, there has been little development of tools for measuring the contextual interdependence of agents’ behaviors in complex environment, which will be valuable for identifying the conditions under which agents are successfully coordinating.
Here we address these two challenges by developing Relational Forward Models (RFM) for multiagent systems. We build on recent advances in neural networks that effectively perform relational reasoning with graph networks (GN) (Battaglia et al., 2018) to construct models that learn to predict the forward dynamics of multi-agent systems. First, we show that our models can surpass previous top methods on this task (Kipf et al., 2018; Hoshen, 2017). Perhaps more importantly, they produce intermediate representations that support the social analysis of multi-agent systems: we use our models to propose a new way to characterize what drives each agent’s behavior, track when agents influence each other, and identify which factors in the environment mediate the presence and valence of social interactions. Finally, we embed our models inside agents and use them to augment the host agent’s observations with predictions of others’ behavior. Our results show that this leads to agents that learn to coordinate with one another faster than non-augmented baselines.

heading: 1.1 RELATED WORK

text:
Relational reasoning has received considerable attention in recent years and researchers have developed deep learning models that operate on graphs, rather than vectors or images, and structure their computations accordingly. These methods have been successfully applied to learning the forward dynamics of systems comprised of multiple entities and a rich relational structure, like physics simulation, multi-object scenes, visual question answering and motion-capture data (Scarselli et al., 2009; Battaglia et al., 2016; Raposo et al., 2017; Santoro et al., 2017; Gilmer et al., 2017; Watters et al., 2017; Kipf et al., 2018; Zambaldi et al., 2018). Recently, this class of methods have been shown to successfully predict the forward dynamics of multi-agent systems, like basketball or soccer games, and to some extent, to provide insights into the relational and social structures present in the data (Hoshen, 2017; Kipf et al., 2018; Zhan et al., 2018; Zheng et al., 2017).
With the recent renaissance of deep-learning methods in general, and of deep reinforcement learning (RL) in particular, considerable attention has been devoted to developing analysis tools that allow researchers to understand what drives agents’ behavior, what are the most common failure modes and provide insights into the inner workings of learning systems (Zeiler & Fergus, 2013; Yosinski et al., 2015; Olah et al., 2017; Morcos et al., 2018). In particular, Rabinowitz et al. (2018) embed entire behavioral trajectories of single RL agents as points in an unstructured, high-dimensional space, relying on the inherent structure of the data to yield interpretable representations of whole behavioral motifs.
Finally, coordination in multi-agent system has been a topic of major interest as of late and some of the most advanced MARL systems rely on the emergence of coordination among teammates to complete the task at hand (Jaderberg et al., 2018; Pachocki et al., 2018). Despite these recent successes, coordination is still considered a hard problem and several attempts have been made to promote the emergence of coordination by relaxing some assumptions (Foerster et al., 2016; 2017; Sukhbaatar et al., 2016; Raileanu et al., 2018; He et al., 2016a). Here we show that, by embedding RFM modules in RL agents, they can learn to coordinate with one another faster than baseline agents, analogous to imagination-augmented agents in single-agent RL settings (Hamrick et al., 2017; Pascanu et al., 2017; Weber et al., 2017).

heading: 2 RELATIONAL ANALYSIS OF MARL SYSTEMS

heading: 2.1 METHODS

text:
Our RFM is based on graph networks (GN) (Battaglia et al., 2018), and is trained by supervised learning to predict the dynamics of multi-agent systems. Our model takes as input a semantic description of the state of the environment, and outputs either an action prediction for each agent, or a prediction of the cumulative reward each agent will receive until the end of the episode. We show that our model performs well at these tasks, and crucially, produces interpretable intermediate representations that are useful both as analysis tools, and as inputs to artificial agents who can exploit these predictions to improve their decision-making.
GN encoder
Graph GRU
GN decoder
Gtout <latexit sha1_base64="Fm4Iz64LvWn082kf2+Dq6sd1g9I=">AAAB+3icbVDLSsNAFJ34rPUV69LNYBFclUQEXbgouNBlBfuANobJdNIOnWTCzI1YQn7FjQtF3Poj7vwbJ20W2npg4HDOvdwzJ0gE1+A439bK6tr6xmZlq7q9s7u3bx/UOlqmirI2lUKqXkA0EzxmbeAgWC9RjESBYN1gcl343UemNJfxPUwT5kVkFPOQUwJG8u3azQP42SAiMFZRJlPIc9+uOw1nBrxM3JLUUYmWb38NhpKmEYuBCqJ133US8DKigFPB8uog1SwhdEJGrG9oTCKmvWyWPccnRhniUCrzYsAz9fdGRiKtp1FgJouQetErxP+8fgrhpZfxOEmBxXR+KEwFBomLIvCQK0ZBTA0hVHGTFdMxUYSCqatqSnAXv7xMOmcN12m4d+f15lVZRwUdoWN0ilx0gZroFrVQG1H0hJ7RK3qzcuvFerc+5qMrVrlziP7A+vwB7zuU/g==</latexit><latexit sha1_base64="Fm4Iz64LvWn082kf2+Dq6sd1g9I=">AAAB+3icbVDLSsNAFJ34rPUV69LNYBFclUQEXbgouNBlBfuANobJdNIOnWTCzI1YQn7FjQtF3Poj7vwbJ20W2npg4HDOvdwzJ0gE1+A439bK6tr6xmZlq7q9s7u3bx/UOlqmirI2lUKqXkA0EzxmbeAgWC9RjESBYN1gcl343UemNJfxPUwT5kVkFPOQUwJG8u3azQP42SAiMFZRJlPIc9+uOw1nBrxM3JLUUYmWb38NhpKmEYuBCqJ133US8DKigFPB8uog1SwhdEJGrG9oTCKmvWyWPccnRhniUCrzYsAz9fdGRiKtp1FgJouQetErxP+8fgrhpZfxOEmBxXR+KEwFBomLIvCQK0ZBTA0hVHGTFdMxUYSCqatqSnAXv7xMOmcN12m4d+f15lVZRwUdoWN0ilx0gZroFrVQG1H0hJ7RK3qzcuvFerc+5qMrVrlziP7A+vwB7zuU/g==</latexit><latexit sha1_base64="Fm4Iz64LvWn082kf2+Dq6sd1g9I=">AAAB+3icbVDLSsNAFJ34rPUV69LNYBFclUQEXbgouNBlBfuANobJdNIOnWTCzI1YQn7FjQtF3Poj7vwbJ20W2npg4HDOvdwzJ0gE1+A439bK6tr6xmZlq7q9s7u3bx/UOlqmirI2lUKqXkA0EzxmbeAgWC9RjESBYN1gcl343UemNJfxPUwT5kVkFPOQUwJG8u3azQP42SAiMFZRJlPIc9+uOw1nBrxM3JLUUYmWb38NhpKmEYuBCqJ133US8DKigFPB8uog1SwhdEJGrG9oTCKmvWyWPccnRhniUCrzYsAz9fdGRiKtp1FgJouQetErxP+8fgrhpZfxOEmBxXR+KEwFBomLIvCQK0ZBTA0hVHGTFdMxUYSCqatqSnAXv7xMOmcN12m4d+f15lVZRwUdoWN0ilx0gZroFrVQG1H0hJ7RK3qzcuvFerc+5qMrVrlziP7A+vwB7zuU/g==</latexit><latexit sha1_base64="Fm4Iz64LvWn082kf2+Dq6sd1g9I=">AAAB+3icbVDLSsNAFJ34rPUV69LNYBFclUQEXbgouNBlBfuANobJdNIOnWTCzI1YQn7FjQtF3Poj7vwbJ20W2npg4HDOvdwzJ0gE1+A439bK6tr6xmZlq7q9s7u3bx/UOlqmirI2lUKqXkA0EzxmbeAgWC9RjESBYN1gcl343UemNJfxPUwT5kVkFPOQUwJG8u3azQP42SAiMFZRJlPIc9+uOw1nBrxM3JLUUYmWb38NhpKmEYuBCqJ133US8DKigFPB8uog1SwhdEJGrG9oTCKmvWyWPccnRhniUCrzYsAz9fdGRiKtp1FgJouQetErxP+8fgrhpZfxOEmBxXR+KEwFBomLIvCQK0ZBTA0hVHGTFdMxUYSCqatqSnAXv7xMOmcN12m4d+f15lVZRwUdoWN0ilx0gZroFrVQG1H0hJ7RK3qzcuvFerc+5qMrVrlziP7A+vwB7zuU/g==</latexit>
Gt 1hid <latexit sha1_base64="TTYaLKTJF7FnWkmBKBRepTsjYHc=">AAAB/3icbVDLSsNAFJ34rPUVFdy4GSyCG0sigi5cFFzosoJ9QBvDZDJph85MwsxEKDELf8WNC0Xc+hvu/BsnbRbaemDgcM693DMnSBhV2nG+rYXFpeWV1cpadX1jc2vb3tltqziVmLRwzGLZDZAijArS0lQz0k0kQTxgpBOMrgq/80CkorG40+OEeBwNBI0oRtpIvr1/fZ/pEzf3sz5Heih5NqRhnvt2zak7E8B54pakBko0ffurH8Y45URozJBSPddJtJchqSlmJK/2U0UShEdoQHqGCsSJ8rJJ/hweGSWEUSzNExpO1N8bGeJKjXlgJouQatYrxP+8XqqjCy+jIkk1EXh6KEoZ1DEsyoAhlQRrNjYEYUlNVoiHSCKsTWVVU4I7++V50j6tu07dvT2rNS7LOirgAByCY+CCc9AAN6AJWgCDR/AMXsGb9WS9WO/Wx3R0wSp39sAfWJ8/b2WWWQ==</latexit><latexit sha1_base64="TTYaLKTJF7FnWkmBKBRepTsjYHc=">AAAB/3icbVDLSsNAFJ34rPUVFdy4GSyCG0sigi5cFFzosoJ9QBvDZDJph85MwsxEKDELf8WNC0Xc+hvu/BsnbRbaemDgcM693DMnSBhV2nG+rYXFpeWV1cpadX1jc2vb3tltqziVmLRwzGLZDZAijArS0lQz0k0kQTxgpBOMrgq/80CkorG40+OEeBwNBI0oRtpIvr1/fZ/pEzf3sz5Heih5NqRhnvt2zak7E8B54pakBko0ffurH8Y45URozJBSPddJtJchqSlmJK/2U0UShEdoQHqGCsSJ8rJJ/hweGSWEUSzNExpO1N8bGeJKjXlgJouQatYrxP+8XqqjCy+jIkk1EXh6KEoZ1DEsyoAhlQRrNjYEYUlNVoiHSCKsTWVVU4I7++V50j6tu07dvT2rNS7LOirgAByCY+CCc9AAN6AJWgCDR/AMXsGb9WS9WO/Wx3R0wSp39sAfWJ8/b2WWWQ==</latexit><latexit sha1_base64="TTYaLKTJF7FnWkmBKBRepTsjYHc=">AAAB/3icbVDLSsNAFJ34rPUVFdy4GSyCG0sigi5cFFzosoJ9QBvDZDJph85MwsxEKDELf8WNC0Xc+hvu/BsnbRbaemDgcM693DMnSBhV2nG+rYXFpeWV1cpadX1jc2vb3tltqziVmLRwzGLZDZAijArS0lQz0k0kQTxgpBOMrgq/80CkorG40+OEeBwNBI0oRtpIvr1/fZ/pEzf3sz5Heih5NqRhnvt2zak7E8B54pakBko0ffurH8Y45URozJBSPddJtJchqSlmJK/2U0UShEdoQHqGCsSJ8rJJ/hweGSWEUSzNExpO1N8bGeJKjXlgJouQatYrxP+8XqqjCy+jIkk1EXh6KEoZ1DEsyoAhlQRrNjYEYUlNVoiHSCKsTWVVU4I7++V50j6tu07dvT2rNS7LOirgAByCY+CCc9AAN6AJWgCDR/AMXsGb9WS9WO/Wx3R0wSp39sAfWJ8/b2WWWQ==</latexit><latexit sha1_base64="TTYaLKTJF7FnWkmBKBRepTsjYHc=">AAAB/3icbVDLSsNAFJ34rPUVFdy4GSyCG0sigi5cFFzosoJ9QBvDZDJph85MwsxEKDELf8WNC0Xc+hvu/BsnbRbaemDgcM693DMnSBhV2nG+rYXFpeWV1cpadX1jc2vb3tltqziVmLRwzGLZDZAijArS0lQz0k0kQTxgpBOMrgq/80CkorG40+OEeBwNBI0oRtpIvr1/fZ/pEzf3sz5Heih5NqRhnvt2zak7E8B54pakBko0ffurH8Y45URozJBSPddJtJchqSlmJK/2U0UShEdoQHqGCsSJ8rJJ/hweGSWEUSzNExpO1N8bGeJKjXlgJouQatYrxP+8XqqjCy+jIkk1EXh6KEoZ1DEsyoAhlQRrNjYEYUlNVoiHSCKsTWVVU4I7++V50j6tu07dvT2rNS7LOirgAByCY+CCc9AAN6AJWgCDR/AMXsGb9WS9WO/Wx3R0wSp39sAfWJ8/b2WWWQ==</latexit>
Gthid <latexit sha1_base64="N3DONKaVTWiaOJQfnkEeGTR4488=">AAAB+3icbVDLSsNAFL3xWesr1qWbYBFclUQEXbgouNBlBfuANobJZNoOnZmEmYlYQn7FjQtF3Poj7vwbJ20W2npg4HDOvdwzJ0wYVdp1v62V1bX1jc3KVnV7Z3dv3z6odVScSkzaOGax7IVIEUYFaWuqGeklkiAeMtINJ9eF330kUtFY3OtpQnyORoIOKUbaSIFdu3nQQTbgSI8lz8Y0yvPArrsNdwZnmXglqUOJVmB/DaIYp5wIjRlSqu+5ifYzJDXFjOTVQapIgvAEjUjfUIE4UX42y547J0aJnGEszRPamam/NzLElZry0EwWIdWiV4j/ef1UDy/9jIok1UTg+aFhyhwdO0URTkQlwZpNDUFYUpPVwWMkEdamrqopwVv88jLpnDU8t+HdndebV2UdFTiCYzgFDy6gCbfQgjZgeIJneIU3K7derHfrYz66YpU7h/AH1ucPuc+U2w==</latexit><latexit sha1_base64="N3DONKaVTWiaOJQfnkEeGTR4488=">AAAB+3icbVDLSsNAFL3xWesr1qWbYBFclUQEXbgouNBlBfuANobJZNoOnZmEmYlYQn7FjQtF3Poj7vwbJ20W2npg4HDOvdwzJ0wYVdp1v62V1bX1jc3KVnV7Z3dv3z6odVScSkzaOGax7IVIEUYFaWuqGeklkiAeMtINJ9eF330kUtFY3OtpQnyORoIOKUbaSIFdu3nQQTbgSI8lz8Y0yvPArrsNdwZnmXglqUOJVmB/DaIYp5wIjRlSqu+5ifYzJDXFjOTVQapIgvAEjUjfUIE4UX42y547J0aJnGEszRPamam/NzLElZry0EwWIdWiV4j/ef1UDy/9jIok1UTg+aFhyhwdO0URTkQlwZpNDUFYUpPVwWMkEdamrqopwVv88jLpnDU8t+HdndebV2UdFTiCYzgFDy6gCbfQgjZgeIJneIU3K7derHfrYz66YpU7h/AH1ucPuc+U2w==</latexit><latexit sha1_base64="N3DONKaVTWiaOJQfnkEeGTR4488=">AAAB+3icbVDLSsNAFL3xWesr1qWbYBFclUQEXbgouNBlBfuANobJZNoOnZmEmYlYQn7FjQtF3Poj7vwbJ20W2npg4HDOvdwzJ0wYVdp1v62V1bX1jc3KVnV7Z3dv3z6odVScSkzaOGax7IVIEUYFaWuqGeklkiAeMtINJ9eF330kUtFY3OtpQnyORoIOKUbaSIFdu3nQQTbgSI8lz8Y0yvPArrsNdwZnmXglqUOJVmB/DaIYp5wIjRlSqu+5ifYzJDXFjOTVQapIgvAEjUjfUIE4UX42y547J0aJnGEszRPamam/NzLElZry0EwWIdWiV4j/ef1UDy/9jIok1UTg+aFhyhwdO0URTkQlwZpNDUFYUpPVwWMkEdamrqopwVv88jLpnDU8t+HdndebV2UdFTiCYzgFDy6gCbfQgjZgeIJneIU3K7derHfrYz66YpU7h/AH1ucPuc+U2w==</latexit><latexit sha1_base64="N3DONKaVTWiaOJQfnkEeGTR4488=">AAAB+3icbVDLSsNAFL3xWesr1qWbYBFclUQEXbgouNBlBfuANobJZNoOnZmEmYlYQn7FjQtF3Poj7vwbJ20W2npg4HDOvdwzJ0wYVdp1v62V1bX1jc3KVnV7Z3dv3z6odVScSkzaOGax7IVIEUYFaWuqGeklkiAeMtINJ9eF330kUtFY3OtpQnyORoIOKUbaSIFdu3nQQTbgSI8lz8Y0yvPArrsNdwZnmXglqUOJVmB/DaIYp5wIjRlSqu+5ifYzJDXFjOTVQapIgvAEjUjfUIE4UX42y547J0aJnGEszRPamam/NzLElZry0EwWIdWiV4j/ef1UDy/9jIok1UTg+aFhyhwdO0URTkQlwZpNDUFYUpPVwWMkEdamrqopwVv88jLpnDU8t+HdndebV2UdFTiCYzgFDy6gCbfQgjZgeIJneIU3K7derHfrYz66YpU7h/AH1ucPuc+U2w==</latexit>
Gtin <latexit sha1_base64="poANnJCpZrUCRM6QZRfO85b+M60=">AAAB/HicbVDLSsNAFJ34rPUV7dJNsAiuSiKCLlwUXOiygn1AG8NkOmmHzkzCzI1QQvwVNy4UceuHuPNvnLRZaOuBgcM59zLnnjDhTIPrflsrq2vrG5uVrer2zu7evn1w2NFxqghtk5jHqhdiTTmTtA0MOO0limIRctoNJ9eF332kSrNY3sM0ob7AI8kiRjAYKbBrNw8Z5EE2EBjGSmRM5nlg192GO4OzTLyS1FGJVmB/DYYxSQWVQDjWuu+5CfgZVsAIp3l1kGqaYDLBI9o3VGJBtZ/NwufOiVGGThQr8yQ4M/X3RoaF1lMRmskio170CvE/r59CdOmbg5IUqCTzj6KUOxA7RRPOkClKgE8NwUQxk9UhY6wwAdNX1ZTgLZ68TDpnDc9teHfn9eZVWUcFHaFjdIo8dIGa6Ba1UBsRNEXP6BW9WU/Wi/VufcxHV6xyp4b+wPr8AdHQlX8=</latexit><latexit sha1_base64="poANnJCpZrUCRM6QZRfO85b+M60=">AAAB/HicbVDLSsNAFJ34rPUV7dJNsAiuSiKCLlwUXOiygn1AG8NkOmmHzkzCzI1QQvwVNy4UceuHuPNvnLRZaOuBgcM59zLnnjDhTIPrflsrq2vrG5uVrer2zu7evn1w2NFxqghtk5jHqhdiTTmTtA0MOO0limIRctoNJ9eF332kSrNY3sM0ob7AI8kiRjAYKbBrNw8Z5EE2EBjGSmRM5nlg192GO4OzTLyS1FGJVmB/DYYxSQWVQDjWuu+5CfgZVsAIp3l1kGqaYDLBI9o3VGJBtZ/NwufOiVGGThQr8yQ4M/X3RoaF1lMRmskio170CvE/r59CdOmbg5IUqCTzj6KUOxA7RRPOkClKgE8NwUQxk9UhY6wwAdNX1ZTgLZ68TDpnDc9teHfn9eZVWUcFHaFjdIo8dIGa6Ba1UBsRNEXP6BW9WU/Wi/VufcxHV6xyp4b+wPr8AdHQlX8=</latexit><latexit sha1_base64="poANnJCpZrUCRM6QZRfO85b+M60=">AAAB/HicbVDLSsNAFJ34rPUV7dJNsAiuSiKCLlwUXOiygn1AG8NkOmmHzkzCzI1QQvwVNy4UceuHuPNvnLRZaOuBgcM59zLnnjDhTIPrflsrq2vrG5uVrer2zu7evn1w2NFxqghtk5jHqhdiTTmTtA0MOO0limIRctoNJ9eF332kSrNY3sM0ob7AI8kiRjAYKbBrNw8Z5EE2EBjGSmRM5nlg192GO4OzTLyS1FGJVmB/DYYxSQWVQDjWuu+5CfgZVsAIp3l1kGqaYDLBI9o3VGJBtZ/NwufOiVGGThQr8yQ4M/X3RoaF1lMRmskio170CvE/r59CdOmbg5IUqCTzj6KUOxA7RRPOkClKgE8NwUQxk9UhY6wwAdNX1ZTgLZ68TDpnDc9teHfn9eZVWUcFHaFjdIo8dIGa6Ba1UBsRNEXP6BW9WU/Wi/VufcxHV6xyp4b+wPr8AdHQlX8=</latexit><latexit sha1_base64="poANnJCpZrUCRM6QZRfO85b+M60=">AAAB/HicbVDLSsNAFJ34rPUV7dJNsAiuSiKCLlwUXOiygn1AG8NkOmmHzkzCzI1QQvwVNy4UceuHuPNvnLRZaOuBgcM59zLnnjDhTIPrflsrq2vrG5uVrer2zu7evn1w2NFxqghtk5jHqhdiTTmTtA0MOO0limIRctoNJ9eF332kSrNY3sM0ob7AI8kiRjAYKbBrNw8Z5EE2EBjGSmRM5nlg192GO4OzTLyS1FGJVmB/DYYxSQWVQDjWuu+5CfgZVsAIp3l1kGqaYDLBI9o3VGJBtZ/NwufOiVGGThQr8yQ4M/X3RoaF1lMRmskio170CvE/r59CdOmbg5IUqCTzj6KUOxA7RRPOkClKgE8NwUQxk9UhY6wwAdNX1ZTgLZ68TDpnDc9teHfn9eZVWUcFHaFjdIo8dIGa6Ba1UBsRNEXP6BW9WU/Wi/VufcxHV6xyp4b+wPr8AdHQlX8=</latexit>
(a) (b)
Agent
RFM
횷
Teammate Action Prediction
Ego-centric Observations Action
Reward
Environment
Environment Graph
Teammate ActionStop Gradient
Augmented Observations
+
(c)
Figure 1: (a) The RFM module stacks a GN Encoder, a Graph GRU and a GN Decoder to obtain a relational reasoning module that holds state information across time steps. (b) Example of an environment graph representation. Edges connect agents (magenta and orange) to all entities and are color-coded according to the identity of the receiver. (c) RFM-augmented agents, the output of the the RFM module is appended to the original observation input to the policy network. The on-board RFM module is trained with full supervision and alongside the policy network.

heading: 2.1.1 RELATIONAL FORWARD MODELS AND BASELINES ARCHITECTURES

text:
A GN is a neural network that operates on graphs. The input to a GN is a directed graph, (u, V,E), where u ∈ Rdu is a graph-level attribute vector (e.g. the score in a football game), V = {vi}i=1:nv is a set of vertices (e.g. the players) with attributes vi ∈ Rdv (e.g the players’ (x,y) coordinates on the pitch), and E = {(ek, rk, sk)}k=1:ne is a set of directed edges which connect sender vertex, vsk to receiver vertex vrk and have attribute ek ∈ Rde (e.g. same team or opponent). The output of a GN is also a graph, with the same connectivity structure as the input graph (i.e., same number of vertices and edges, as well as same sender and receiver for each edge), but updated global, vertex, and edge attributes. See Fig. 1b for an example graph.
The sequence of computations in a GN proceed by updating the edge attributes, followed by the vertex attributes, and finally the global attributes. These computations are implemented via three “update” functions (the φs) and three “aggregation” functions (the ρs),
e′k = φ e (ek, vrk , vsk , u) , v′i = φ v (ē′i, vi, u) , u′ = φu (ē′, v̄′, u) ,
ē′i = ρ e→v (E′i) , v̄′ = ρv→u (V ′) ,
ē′ = ρe→u (E′)
(1)
where E′i = {(e′k, rk, sk)}rk=i. The edges are updated by φe, as a function of the sender vertex, receiver vertex, edge, and global attributes. We term the updated edge attribute the “message”, e′k. Next, each vertex, i, is updated by aggregating the e′k messages for which i = rk, and computing the updated vertex attribute, v′i, as a function (φ
v) of these aggregated messages, as well as the current vertex and global attributes. Finally, the global attributes are updated, by φu, as a function of the current global attribute and all aggregated e′k and v ′ i attributes.
Since a GN takes as input a graph and outputs a graph, GN blocks can be composed to form more complex, and powerful, architectures. These architecture can also be made recurrent in time by introducing a state graph, and using recurrent neural networks (RNNs) as the φ functions. GN-based architectures can be optimized with respect to some objective function by gradient descent (using backpropagation through time for recurrent implementations). Here we focus on supervised learning using datasets of input-output pairs. See (Battaglia et al., 2018) for further details.
We construct our RFM architecture by arranging three GN blocks as in Fig. 1a. We selected this specific architecture to allow our model to perform relational reasoning steps both on the raw input data, before time recurrence is included, and then again on the output of our time recurrent block. This allows the recurrent block to construct memories of the relations between entities and not simply of their current state.
Architecture details are as follows: input graphs Gtin go through a GN encoder block, a basic GN module whose φv, φe and φu are three separate 64-unit MLPs, with 1 hidden layer, and ReLU activations and whose ρ functions are summations. The output of the GN encoder block is used, in conjunction with a state graph Gt−1hid , in a “GraphGRU”, where each φ function is a Gated Recurrent Unit (GRU) (Cho et al., 2014) with a hidden state size of 32 for each of vertices, edges and globals. The GraphGRU’s output is then copied into a state graph and an output graph. The state graph is
used in the following time step, while the output graph is passed through a GN decoder block. This last block’s structure has an identical to the GN encoder’s, and outputs the model’s predictions (e.g. the actions of each agent).
We compared the prediction performance of our RFM module to two state-of-the-art relational reasoning baselines: Neural Relational Inference networks (Kipf et al., 2018) and Vertex Attention Interaction Networks (Hoshen, 2017). These architectures are similar to our RFM module. In particular, NRI models operate on graph structured data and, with the exception that the graph connectivity map is not given, but rather estimated from trajectories using an auto-encoder architecture, they are identical to our model. VAIN networks are essentially single feed-forward GN blocks where the φe and ρe→v functions take particular and restricted form: φe(ek, vrk , vsk , u) = e ‖a(vrk )−a(vsk )‖ 2
and ρe→v(E′i) = vi ∑ sk e′k, with a(·) a learnable function.
We also compared our full RFM against ablated variants, which allowed us to measure the importance of the relational reasoning component, and of time recurrence. In particular we considered a Feedforward model, which had no GraphGRU block, and a No-relation model, which was a full fledged RFM module but operated on graphs with only self-connections (i.e., edges where si = ri). Finally, we included a vector-based MLP + LSTM model among our baselines, so as to highlight the advantage of using graphs over vector based modules. This last model operated on the concatenation of the vertex attributes and had a standard Encoder MLP (64-units), LSTM (32-hidden units), Decoder MLP (2 hidden layers, 32-units each) architecture. We matched all models for capacity (with the exception of NRI which has about 3x more parameters than other models because of its autoencoder connectivity map estimator). Models were within 3% of each other in terms of number of parameters (as reported by the TensorFlow checkpoint loader).

heading: 2.1.2 MARL ENVIRONMENTS AND AGENT ARCHITECTURE

text:
We considered three multi-agent environments for our study: Cooperative Navigation (Lowe et al., 2017), Coin Game (Raileanu et al., 2018) and Stag Hunt (Peysakhovich & Lerer, 2017b).
Cooperative Navigation (Lowe et al., 2017). Two agents navigate an empty 6 × 6 arena to cover two tiles. A reward of +1 is given to both agents whenever both tiles are covered, i.e., when each agent is on a tile of its own. Episodes are of fixed length (20 environment steps), to encourage a swift resolution of the underlying assignment problem. The positions of both tiles and the starting positions of each agent are randomized at the start of each episode.
Coin Game (Raileanu et al., 2018). Two agents roam an 8× 8 arena populated with 12 coins, 4 of each of 3 colors, for 10 environment steps. Agents can collect coins by stepping on them; out of the 3 coin colors, two colors carried a reward and one a punishment. Crucially, each of the two agents only has access to information about 1 good color. The short episode duration incentivizes agents to quickly infer what the unknown good color is by observing their teammate actions, so that all good coins can be collected. At the end of each episode both agents are rewarded according to how many good coins have been collected by either agent. Conversely, they are penalized according to the number of bad coins collected, again by either agent. The role of each color, coin positions, and starting coordinates for the agents are randomized in each episode.
Stag Hunt (Peysakhovich & Lerer, 2017b). We implemented a Markov version of the classic Stag Hunt game where two (or four) agents navigate an arena populated with 3 red Stags (each of which is static, and occupies a 2× 2 tile) and 12 green apples, for 32 environment steps. Agents can collect apples by themselves for a reward of +1 or, by both stepping on the same stag, capture it for a reward of +10. Collected apples and captured stags became unavailable for some time (denoted by dimmed colors), and at each time step have a small probability of becoming available again. All entities’ locations are randomized at the start of each episode.
We trained populations of RL agents to convergence on these three tasks using a multi-agent implementation of importance-weighted actor-learner (Jaderberg et al., 2018; Espeholt et al., 2018), a batched advantage actor-critic (A2C) algorithm. For each episode, a group of agents were randomly sampled, with replacement, from a population of 4 learners; at each time step agents received an ego-centric, top-down view of the environment which was large enough to contain the entire arena, and, in the Coin Game, one of the 2 good colors. Agents then selected one of 5 actions to be performed (move left, move right, move up, move down, and stay). Within each agent, the input
image was parsed by a single convolutional layer (3× 3-filters, 6 output channels) whose output was fed to a 256-unit single-layer MLP. The MLP output vector was concatenated with each player’s last reward, and one-hot encoded last action, as well as, for the Coin Game, one of the two coin colors that carried a positive reward. The resulting vector served as input to a 256-hidden-units LSTM whose output was fed into a single soft-max layer. Throughout the learning process, there was no sharing of weights, gradients or any communication channel between the agents, consistent with standard MARL settings.

heading: 2.1.3 OFFLINE TRAJECTORIES COLLECTION AND MODEL TRAINING

text:
To train the forward RFM model, we collected 500,000 episodes of behavioral trajectories of trained agents acting in their respective environments. At each time step, we collected a semantic description of the state of the environment, as well as the action taken by each agent and the reward they received. These descriptions were compiled into a graph, where agents and static entities (i.e., apples, stags, coins, and tiles) were represented by vertices whose attributes, vi, were: the entity’s position in the arena; the one-hot encoded type of the entity (e.g. agent, apple, etc.); (when applicable) the entity’s state (e.g. available / collected); and (when applicable) the last action taken. When attributes were not applicable (e.g. the last action of an apple), we padded the corresponding attribute features with zeros. Edges connected all non-agent entities to all agents as well as agents to each other. Input edges contained no attributes and were characterized by senders and receivers only (see Fig. 1b for an example environment graph). In order to understand our analysis contributions, it is crucial to note that while the input graph to our RFM module contained no edge attributes, and edges were simply characterized by their sender and receiver vertices, the edges of a RFM’s output graph did contain attributes. These attributes were computed by the network itself and amounted to distributed representations of the effect the sender entity had on the receiver agent.
We also collected 2,500 further episode trajectories for performance reporting and analysis. Training of both RFM and baseline models was conducted using gradient descent to minimize the cross-entropy loss between predicted and ground-truth actions. The training procedure was halted after one million steps, during each of which the gradient was estimated using a batch of 128 episodes. Results are presented in Sec. 2.2.1.

heading: 2.2 RESULTS

heading: 2.2.1 ACTION PREDICTION PERFORMANCE

text:
We trained our RFM modules and baseline models to predict the actions of each agent in each of the three games we considered. Models were given a graph representation of the state of the environment, and produced an action prediction for each agent. After training (see Sec. 2.1.3), we used held-out episodes to assess the performance of each model in terms of mean length of perfect roll-out: the mean number of steps during which prediction and ground truth do not diverge. This metric gives
us a measure of how long we could simulate the agents’ behavior before making a mistake. For completeness, we report next-action classification accuracy in Sec. A.5.
Results are shown in Fig. 2. As expected, all models achieve similar scores on the Coop Nav game, which is a rather simple environment. Our RFM module outperforms the NRI baseline by a substantial margin on the Coin Game and Stag Hunt environments. Since the two models are identical, except for the initial graph structure inference step, this result suggests that when the importance of some relations is revealed over time, rather than obvious from the start, the graph structure inference step proposed in NRI might not be appropriate. Our RFM consistently outperforms the VAIN model, and on Stag Hunt our Feedforward model does as well. This indicates that, for this particular task, distributed interaction representations are superior to simple attention weights. Finally, the MLP+LSTM and No-relation models performed worst across the board, which suggests that relations between entities, rather than the state of the entities themselves, carry most of the predictive power in these environments.
These results reproduce and advance the conclusion that relational models can be trained to perform action prediction for multi-agent systems, and are superior to non-relational models for this task (Kipf et al., 2018; Hoshen, 2017).

heading: 2.2.2 RELATIONAL ANALYSIS OF THE STAG HUNT GAME: ACTIONS

text:
Here we introduce our relational analysis tools and use the Stag Hunt game as a case study. While we illustrate our findings on a simple game, these intuitions can be easily transferred to more complex domains.
We propose the Euclidean norm of a message vector (i.e., ‖e′k‖) as a measure of the influence a sender entity, vsk , has on a receiver, vrk . We validate this suggestion in Fig. 3 (top row), where we show that the edge norm between a sender entity (either a stag or an apple) and a receiver agent is predictive of which entity the agent will move towards, or away from, at the next time step.
This intuition can be developed to discover the events that qualitatively change agents’ behavior, as well as the factors that mediate how agents interact with one another. Fig. 3 (middle row), for example, shows how the norm of an edge between a stag and an agent changes over time. The importance of the relation is modulated by the prey’s state: when a stag becomes available, the edge norm rises substantially; when a stag is consumed, the edge norm drops. Remarkably, the presence or absence of a stag also influences the edge norm between the two teammates, as shown in Fig. 3 (bottom row): in the time step immediately before they consume a stag, the edge between the two teammates is higher than immediately afterwards. In contrast, this effect does not occur with apples, which do not require coordination between teammates to consume. Finally, as shown in Fig. 3 (bottom row), we find that agents’ influence on each other’s behavior is higher when there is a scarcity of apples (as agents compete for this resource). We note that while significant changes in edge norm or the rank order of edge norm can be used to discover events that qualitatively change agents behavior and factors that mediate agents’ social interaction, the raw values have no intrinsic meaning.
Taken as a whole, these findings highlight how the norm of the edge messages, computed by a RFM which is trained to predict the future actions in a multi-agent system, contain intepretable and quantifiable information about when and how certain entities and relations influence agents’ behavior, and about which entities and situations mediate the social influence between agents.

heading: 2.2.3 RELATIONAL ANALYSIS OF THE STAG HUNT GAME: RETURN

text:
A second key finding is that beyond measuring the intensity of a social influence relation, RFM modules can also be used to quantify their valence. We trained a RFM model to predict the return received by each agent (until the end of the episode), rather than their future action. We used this model to measure the marginal utility of the actual social context, i.e., to ask: what would happen to agent 1’s return if we didn’t know the exact state of agent 2?
The proposed approach is to effectively compare two estimators for agent 1’s return:
R̂a1Full graph = M(sa1 , sa2 , z) (2)
R̂a1Pruned graph = M(sa1 , z) (3) ≈ ∫ M(sa1 , s ′ a2 , z)p(s ′ a2 |sa1 , z)ds ′ a2
where R̂a1Full graph is the model M ’s estimate of the return received by agent 1, given the state of both agents 1 and 2, and all other environment variables, z, whereas R̂a1Pruned graph is that same estimate, without knowledge of the state of agent 2 (i.e., marginalizing out sa2 ). In practice, this latter estimate can be obtained by removing the edge connecting the two agents from the input graph1.
If we find that, in certain situations, the predicted return decreases when removing information about agent 2 (i.e., R̂a1Full graph > R̂ a1 Pruned graph), we would conclude that the actual state of agent 2 results in a better-than-expected return for agent 1, that is, agent 2 is helping agent 1. Conversely, if the predicted return increases we would conclude that agent 2 is hindering agent 1.
We ran this experiment using a set-up identical to the one we used for action prediction, except for three modifications: (1) the target variable and (2) loss function were changed, from cross-entropy between predicted and ground-truth actions, to mean squared error between predicted and true return; and (3) the training set contained an equal proportion of environment graphs with and without edges between teammates. The latter modification ensured that the pruned-graph computations were not out-of-distribution. The ground truth and predicted return (using both the full and pruned graph) for a sample episode are shown in Fig. 4 (left).
We note that within this setup, both the pruned-graph estimator and the full-graph estimator are produced by a single graph neural network. This network is trained to predict agent 1’s return both using the full graph (i.e. knowing the actual state of a2) and the pruned graph (i.e. not knowing the actual state of a2). During training we randomly drop out edges between teammates (to ensure that both full graph and pruned graph are in-distribution for M ). At test time, we then compute the full-graph estimate by using all edges, and the pruned-graph estimator by dropping out edges between teammates.
Similar to the edge-norm relational analysis above, we can find the entities and events that mediate the value of a social interaction. For example, Fig. 4 (middle and right) show the marginal value of a teammate’s particular state (i.e. R̂a1Full graph − R̂ a1 Pruned Graph) over time and around the time of a stag capture. Thus the model estimates that teammates’ specific interactions during this time are beneficial to their return.

heading: 3 RFM-AUGMENTED AGENTS

heading: 3.1 METHODS

text:
We have shown that relational reasoning modules capture information about the social dynamics of multi-agent environments. We now detail how these modules’ predictions can be useful for improving MARL agents’ speed of learning. We extended the agent architecture (described in Sec. 2.1.2) by embedding a RFM module in each agent, and augmenting the policy network’s observations with the RFM’s output. This agent architecture is depicted in Fig. 1c.
Incorporating an on-board RFM module did not provide the agents with any additional information above and beyond that provided to baseline agents. All games were fully observable, so the additional inputs (i.e. the true last action, and the environment graph, which was provided as input to the embedded RFM) did not add any new information to the original egocentric observations. Similarly, the on-board RFM modules were trained from scratch alongside the policy networks, while the agents were learning to act, so that no additional game structure was given to the augmented agents. Finally, we highlight that each learning agent in the arena had its own RFM module and policy networks; there was never any sharing of weights, gradients or communication between the agents.
Our baseline agent policy network architecture comprised of a CNN that processed the actor’s egocentric observation, followed by a MLP+LSTM network that provided action logits (see Sec. 2.1.2 for architecture details). Our augmented agents had an embedded RFM module, which was fed graph representations of the state of the environment, just as in the offline RFM modules in the forward modeling experiments. We trained this module to minimize the cross-entropy loss between its prediction and the last action taken by all fellow agents. We used the prediction output of the on-board RFM module to augment the observation stream at the input of the original policy network. Specifically, the output of the RFM module—predicted action logits for fellow agents—was rendered as image planes whose pixel intensity was proportional to the estimated probability that an agent would be at a certain location at the next time step2. These image planes were appended to the ego-centric top-down observation and fed to the original policy network.

heading: 3.1.1 RESULTS

text:
Our experimental design was relatively straightforward. First, we trained A2C agents (as described in Sec. 2.1.2) to play the three games we considered, as well as a four-player variant of the Stag Hunt game. Second, we paired learning agents with these pre-trained experts: learning agents occupied a
1It is worth highlighting that even though the edge from agent 2 is removed, the estimator R̂a1Pruned graph can implicitly take advantage of sa1 and z to effectively form a posterior over sa2 before marginalizing it out. For this reason, we include p(sa2 |sa1 , z) rather than p(sa2) in equation 2.2.3.
2For example, consider a fellow agent at the center of the map, and prediction logits indicating that, at the next time step, it might move up with a probability of 0.3, and down with a probability of 0.7. The additional image plane would be zero everywhere, with the exception of the pixel above the center (which would have a value of 0.3) and the one below the center (which would have an value of 0.7).
single-player slot in each game, while all their teammates were pre-trained experts. We repeated this procedure using both RFM-enhanced agents and baseline A2C agents as learners. During training we recorded the reward received by the singular learning agent in each episode.
Our results show that agents that explicitly model each other using an on-board RFM learn to coordinate with one another faster than baseline agents (Fig. 5). In Stag Hunt our RFM-augmented agent achieves a score above 25 after around 600K steps, while baseline agents required around 1M steps. This effect is even more prominent in the 4-player version of the game where these scores are achieved around 500K and 1M steps respectively. Similarly in Coop Nav baseline agents required twice as many steps of experience to consistently score above 25 as our RFM-augmented agents. Moreover, in the Coin Game environment, the faster learning rate of RFM-augmented agents appears to be due to a superior efficiency in learning to interpret the teammate’s action and infer the negative coin color in each episode (see Sec. A.1). Finally, we found that augmenting agents with on-board RFM modules was more beneficial to agents learning than using MLP + LSTM models (see Sec. A.2). These results suggest that agents take into account the on-board RFM’s predictions when planning their next action, and that this results in agents that learn faster to coordinate with others, and to discover others’ preferences from their actions.

heading: 4 CONCLUSIONS

text:
Here we showed that our Relational Forward Model can capture the rich social dynamics of multiagent environments, that its intermediate representations contained valuable interpretable information, and that providing this information to learning agents results in faster learning system.
The analysis tools we introduced allow researchers to answer new questions, which are specifically tailored to multi-agent systems, such as what entities, relations and social interactions drive agents’ behaviors, and what environment events or behavior patterns mediate these social and non-social influence signals. Importantly our methods require no access to agents internals, only to behavioral trajectories, making them amenable to analyzing human behavior, sports and ecological systems.
Providing agents with access the output of RFM modules results in agents that learn to coordinate with one another faster than non-augmented baselines. We posit that explicit modeling of teammates and opponents is an important research direction in multi-agent RL, and one that might alleviate the need for communication, parameter sharing or centralized controllers to achieve coordination.
Future work will see our methods applied to more complex and varied domains where artificial and non-artificial agents interact and learn in shared environments. We will focus on identifying entire patterns of behavior for in-agent modeling, so as to adapt the host agent policy more efficiently.

heading: A APPENDIX

text:
A.1 COIN COLLECTION ANALYSIS IN THE COIN GAME
As described in the main text, RFM-augmented agents learn the Coin Game faster than non-augmented baseline agents. This appears to result from learning more efficiently to discern their teammate’s preference. In Fig. 6, the middle panel shows the average number of coins of each color (R: revealed good, U: unrevealed good, B: bad) collected by our RFM-augmented agent during an episode. The right panel shows the same quantities for our baseline agent. We find that the gap between the U curve and the B curve is significantly wider for the RFM-augmented agent than it is for the baseline agent (see, for example, around 50M steps). This suggests that the learning efficiency difference is due to a superior ability to discern the teammate’s preferences.
Finally we highlight that our agents, as well as our baselines, vastly outperform previously-published agents on this game: Separate policy predictor agents (He et al., 2016b) and Self-Other Modeling agents (see Fig. 3 in Raileanu et al. (2018). This might imply that the original paper where this game was suggested had poor baseline agents. We suspect this game is not as complex as it may appear, and that baseline agents are close to optimal; this leaves less room for improvement than other games explored in this work.
A.2 AUGMENTING AGENTS WITH NON-RELATIONAL MODELS
In the main text we showed that agents that explicitly model each other using an on-board RFM learn to coordinate with one another faster than baseline agents. For completeness, we show in Fig. 7 the learning performance of agents that have instead been augmented with MLP+LSTM models (as described in the main text). The learning performance of these agents (red) falls between baseline agents (green), which do not explicitly model other agents, and the RFM-augmented agents (blue), which use a relational architecture to model their teammates’ behavior. The better performance of RFM-augmented agents is expected, given the more accurate forward predictions that RFMs provide.
A.3 TRAINING WITH NON-EXPERT TEAMMATES
In the main text we showed how RFM augmented agents learn to coordinate with expert teammates faster than non-augmented baselines. This set-up as is relevant for many interesting situations, e.g.
when artificial learning agents interact with human experts. For completeness, we show in Fig. 8 the corresponding results when RFM-augments agents train alongside other learning agents (i.e. non-experts). In this case, either all agents in the environment were RFM-augmented (green), or all agents were baseline (blue). We use longer episodes in these experiments (128 steps, rather than 32) in order to make training easier (hence total returns were higher). For brevity, we only report results on the two-player versions of the games.
We see a similar result to the main text: allowing agents to model one another explicitly results in faster learning (e.g. in StagHunt RFM + A2C achieves scores around 48 around 30M steps while vanilla A2C requires 45M training steps. Similarly in CoinGame RFM + A2C achieves a score around 15 in 100M steps while vanilla A2C requires almost 200M steps). We note that this setting presents an additional challenge: a learned model of a teammate’s behavior can only provide useful information for coordination after the teammate’s policy becomes sensible. The advantage conferred by embedding the RFM into the learning agent will thus be delayed relative to the expert teammate condition shown in the main text. Nonetheless, augmenting agents with RFM models still results in faster learning than omitting it altogether.
A.4 CONTROL EXPERIMENTS: WHICH EVENTS MEDIATE INTERDEPENDENT BEHAVIOR
In the main text we showed that our RFM model reveals how agents’ influence on each other is contextual. In particular, we observe in Fig: 3 (bottom row, left and middle panels) that the Euclidean norm of the activation of the edge between the two agents increases when a stag appears. We argue that this indicates that agents coordinate their behavior when stags are available. Here we report control experiments to test alternative hypotheses. In these experiments, we trained agents on two modifications of the StagHunt game, wherein there is no explicit incentive for agents to coordinate:
• Stags carry no rewards. This tests whether the changes in Fig. 3 could be due to arbitrary changes in the environment. Here our hypothesis predicts that stag appearance would have no effect on edge norms, since agents should learn to ignore them. • Stags can be collected by a lone hunter. This tests whether the changes in Fig. 3 could
be due to the appearance of new reward-carrying objects that do not require coordination. Again, our hypothesis predicts that stags would have no effect on the edge norm between agents, since collecting a stag does not require coordination, like apples.
In both cases our experimental pipeline was as described in the main text: (1) train A2C agents on the modified version of the StagHunt game; (2) collect behavioral trajectories from these agents; (3) train a RFM model to predict the action of each agent given the state of the environment; and (4) report the Euclidean norm of the edge activations in the link connecting the two agents at a time just before and just after a Stag or an Apple appear.
Consistent with our primary hypothesis, there is no significant change in the norm of the activations in the edge connecting two agents when Stags (or apples) appear in these situation. This provides evidence that our RFM model is able to reveal which events in the environment mediate how agents influence each one another.
A.5 ACCURACY MEASURE
In the main text we show that our RFM model provides longer perfect rollouts than competing models. Here we provide an alternative metric to measure the relative accuracy of different models. In Fig. 10, we show the next-step action classification accuracy, in the same manner as Fig. 2. Model ranking remain unchanged (with the exception of NRI on CoinGame): the RFM outperforms other models on predicting agent behavior.