summaries: This paper studies the problem of set encoding in the setting where the cardinality of the set is prohibitively large or unbounded. For example, this is the case when dealing with streaming data. A property called Mini-Batch Consistency (MBC) is defined, and it is argued that set encoding algorithms must have the MBC property to learn useful representations of the entire set when partitions of the set are being processed incrementally. A slot-based algorithm that is MBC is proposed. It models interactions between the inputs and slots to learn strong representations. The algorithm, called the Slot Set Encoder (SSE), is compared against Deep Sets and the Set Transformer on a variety of relevant tasks.

summaries: The authors proposes the use of attention based set encoder which can scale to arbitrary set sizes. Attention in Transformers has the quadratic dependence on number of positions (i.e. cardinality of the set). The proposed method makes the problem easier by enabling the use of slots while preserving a property which method defines as mini-batch consistency. The proposed method is invariant to the order of the subsets, and invariant to permutations on the set elements.

summaries: The paper addresses the problem of set encoding when the set is too large to fit in the memory, or given as a stream of data. The proposed method randomly partitions the set,  encodes each random subset and then aggregates all the encodings. The key contribution of the proposed method is that the aggregation of the encodings is required to be equal to the encoding of the full set and it satisfies permutation invariance and equivariance. This property is formally defined and named as Mini-Batch Consistent Set Encoding in the paper. Compared to DeepSets, which also satisfy Mini-Batch Consistent Set Encoding, the proposed method can model pairwise interactions, while DeepSets lack this property. The encoding is implemented using previously introduced slot attention [8] (the attention is done over “slots” instead of self-attention) with the two differences: softmax is replaced with sigmoid in constructing the attention matrix and GRU update of slots is omitted here. The experiments compare the proposed method with two previous methods for set encoding in three tasks showing some improvement.

summaries: This paper addresses the problem of set encoding when the dimensionality and/or cardinality of the set it too large to fit into memory to feed into an encoder or when set elements arrive in a stream. This paper defines a property, mini-batch consistency, for set encoding functions that encode the set in non-overlapping subsets (mini-batches) then aggregate the mini-batch encodings to achieve the set encoding. If obeying mini-batch consistency, the encoder achieves the same set encoding as if the encoding function was applied directly to the entire set. Finally, the paper proposes an encoding function, Slot Set Encoder, to satisfy mini-batch consistency.

summaries: This paper introduces a new concept called “mini-batch consistency” (MBC), which is presented as necessary for efficiently training large-scale set encoding models using mini-batch processing of sets.  MBC is appropriate when the cardinality of the sets in the data is very high, and thus all set elements cannot be loaded into memory, or when the data arrives in a stream.  MBC adheres to the required properties of invariance and equivariance for set encoding models.  A MBC-based set encoding mechanism is also proposed, called the slot set encoder.  Extensive experimental results are provided, which demonstrate that the proposed method is scalable and generally outperforms competing approaches.

abstractText: Most existing set encoding algorithms operate under the implicit assumption that all the set elements are accessible, and that there are ample computational and memory resources to load the set into memory during training and inference. However, both assumptions fail when the set is excessively large such that it is impossible to load all set elements into memory, or when data arrives in a stream. To tackle such practical challenges in large-scale set encoding, the general set-function constraints of permutation invariance and equivariance are not sufficient. We introduce a new property termed Mini-Batch Consistency (MBC) that is required for large scale mini-batch set encoding. Additionally, we present a scalable and efficient attention-based set encoding mechanism that is amenable to mini-batch processing of sets, and capable of updating set representations as data arrives. The proposed method adheres to the required symmetries of invariance and equivariance as well as maintaining MBC for any partition of the input set. We perform extensive experiments and show that our method is computationally efficient and results in rich set encoding representations for set-structured data.

title: B

venue: van Merrienboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee

authors:
M. Garnelo
D. Rosenbaum
C.J. Maddison
T. Ramalho
D. Saxton
M. Shanahan
Y.W. Teh
D.J. Rezende
S. Eslami

title: Conditional neural processes

venue: arXiv preprint arXiv:1807.01613

authors:
H. Kim
A. Mnih
J. Schwarz
M. Garnelo
A. Eslami
D. Rosenbaum
O. Vinyals
Y.W. Teh

title: Attentive neural processes

venue: arXiv preprint arXiv:1901.05761

authors:
Y. LeCun
L. Bottou
Y. Bengio
P. Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE, 86(11):2278–2324

authors:
J. Lee
Y. Lee
J. Kim
A. Kosiorek
S. Choi
Y.W. Teh

title: Set transformer: A framework for attentionbased permutation-invariant neural networks

venue: International Conference on Machine Learning, pages 3744–3753. PMLR

title: Deep learning face attributes in the wild

venue: In Proceedings of International Conference on Computer Vision (ICCV),

authors:
F. Locatello
D. Weissenborn
T. Unterthiner
A. Mahendran
G. Heigold
J. Uszkoreit
A. Dosovitskiy
T. Kipf

title: Object-centric learning with slot attention

venue: arXiv preprint arXiv:2006.15055

authors:
D. Lopez-Paz
R. Nishihara
S. Chintala
B. Scholkopf
L. Bottou

title: Discovering causal signals in images

venue: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6979–6987

authors:
R.L. Murphy
B. Srinivasan
V. Rao
B. Ribeiro

title: Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs

venue: arXiv preprint arXiv:1811.01900

authors:
J. Snell
K. Swersky
R.S. Zemel

title: Prototypical networks for few-shot learning

venue: arXiv preprint arXiv:1703.05175

authors:
A. Vaswani
N. Shazeer
N. Parmar
J. Uszkoreit
L. Jones
A.N. Gomez
Ł. Kaiser
I. Polosukhin

title: Attention is all you need

venue: Advances in neural information processing systems, 30:5998–6008

authors:
Z. Wu
S. Song
A. Khosla
F. Yu
L. Zhang
X. Tang
J. Xiao

title: 3d shapenets: A deep representation for volumetric shapes

venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1912–1920

authors:
M. Zaheer
S. Kottur
S. Ravanbakhsh
B. Poczos
R.R. Salakhutdinov
A.J. Smola

title: Deep sets

venue: Advances in neural information processing systems, pages 3391–3401

authors:
Y. Zhang
J. Hare
A. Prügel-Bennett

title: Fspool: Learning set representations with featurewise sort pooling

venue: arXiv preprint arXiv:1906.02795

heading: 1 Introduction

text:
Recent interest in neural network architectures that operate on sets [14, 6] has garnered momentum given that many problems in machine learning can be reformulated as learning functions on sets. Problems such as point cloud classification [13], image reconstruction [3, 4, 7], classification, set prediction [8], and set extension can all be cast in this framework of learning functions over sets. Given that sets have no explicit structure on the set elements, such functions are required to conform to symmetric properties such as permutation invariance or equivariance for consistent processing.
A defining property of many practical functions over sets involves an encoding of the input set to a vector representation, the set encoding. This set encoding is then used for downstream tasks such as reconstruction or classification. In DeepSets [14], a sum-decomposable family of functions is derived for a class of neural network architectures that encode a given set to such a representation. However, the simplicity of the functions derived in DeepSets makes it ineffective for modeling pairwise interactions between the elements of the sets. Set Transformers [6] remedy this by using Transformers [12] to model higher order interactions resulting in rich and expressive set representations.
In all these works, there is an implicit assumption in the experimental setup that the cardinality of the set is manageable, and that there are ample computational resources available for processing all the elements during the set encoding process. However in real-world applications such as large scale point cloud classification and data intensive applications in particle physics, the set size can be extremely large. In such cases, even if one has access to a set encoding function that is linear w.r.t. the number of elements in the set, it is still impossible to encode such sets in a single batch since we may not be able to load the full set into memory. Current encoding methods deal with this issue by sampling
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
subsets of the full set (as a data preprocessing step) and encoding them to a representative vector, as done in the ModelNet40 [13] experiments in [14, 6]. However, this results in the loss of information about the full set, which is undesirable when huge amounts of monetary resources are invested in obtaining data such as in the Large Hadron Collider (LHC) experiments, and hence is imperative that the data is exploited for maximum performance on the given task. As such, it is necessary to have a set encoder that can take advantage of the full data, in a computationally efficient way.
To this end, when the set is too large to fit in the memory, or given as a stream of data, we propose to iteratively encode it over multiple rounds, by randomly partitioning it, encoding each random subset (mini-batch) with the set encoder at each round, and aggregating all the encodings. However, naive mini-batch set encoding could compromise essential properties of the set encoder such as permutation invariance and equivariance. To use a concrete example, in Figure 2 we show the performance of Set Transformer (in Negative Log-Likelihood) on an image reconstruction task. By processing the full set (in this case concatenations of pixel and coordinate values), the model performs as expected (SetTransformer in Figure 2). However when we instead partition the set elements into mini-batches, independently encode each batch and aggregate them to obtain a single set encoding, we observe performance degradation in the model as shown in Figure 2 (SetTransformer(MiniBatch) in Figure 2).
This degradation stems from the attention module in Set Transformer where mini-batch encoding and aggregation results in mini-batch inconsistent set encoding.
In this work, we identify and formalize a key property, Mini-Batch Consistency (MBC), that is necessary for mini-batch encoding of sets. In what follows, we present the necessary constraints required for MBC and propose a slot based attentive set encoder, the Slot Set Encoder (SSE) which is MBC. SSE largely alleviates the performance degradation in mini-batch encoding of large sets. We depict MBC and non-MBC set encoders in Figure 1.
Our contributions in this work are as follows:
• We identify and formalize a key property of set encoding functions called Mini-Batch Consistency (MBC), which requires that mini-batch encoding of a set is provably equal to the encoding of the full set (in Section 2.2).
• We present the first attention based set encoder that satisfies MBC. Our method can efficiently scale to arbitrary set sizes by removing the dependence of self-attention in the transformer through the use of slots which frees the transformer from requiring to process the full set in a single pass (in Section 2.3).
• We perform extensive experiments on various tasks such as image reconstruction, point cloud classification and dataset encoding where we demonstrate that SSE significantly outperforms the relevant baselines (Section 3).

heading: 2 Mini-Batch Consistent Set Encoding with Slot Set Encoders

heading: 2.1 Preliminaries

text: Suppose we are given a dataset of sets D = {Xi, . . . , XN} where |D| = N and each Xi ∈ Rni×d where ni is the number of elements in Xi and each element x (j) i (that is, the jth element of Xi) is represented by a d dimensional tensor. For each Xi, the ordering of the ni individual elements is considered arbitrary and could be any permutation of the indices. We further assume that both ni and d can be large enough such that processing an instance Xi is prohibitive both in terms of memory and computation. As an example, the processing task could be encoding each element Xi to a representative vector to be used for downstream tasks such as set reconstruction, set classification or set prediction. Current set encoding methods such as Zaheer et al. [14] and Lee et al. [6] deal with such large sets by sampling a smaller subset of the original set as a preprocessing step. In essence, they approximate the full set with a random subset which can be undesirable when we want to exploit all the data at our disposal for maximum performance. In this section, we present a method for encoding arbitrarily sized set data via a mini-batch encoding scheme. Our method can then iteratively encode subsets of Xi and aggregate the subset-encodings to obtain the full set representation. Our method is Mini-Batch Consistent, invariant to the order of the subsets, and invariant to permutations on the set elements. For clarity, when we say a set Xi is mini-batch processed, we mean that a random partition function can be applied to Xi to obtain proper subsets of Xi. The subsets, which we call mini-batches, are then processed independently and aggregated to obtain a representation for Xi.

heading: 2.2 Mini-Batch Consistent Set Encoding

text:
We consider a single element Xi ∈ D with ni elements each with d dimensions. We truncate notation and write Xi, ni as X and n respectively since we present our algorithm for a single sample here. Our ultimate goal is to encode the set X to a representation Z ∈ Rd′ where d′ is the dimension of the encoding vector. We assume that both d and n are large such that it is not feasible to process X as a whole. To get around this computational problem, we propose to perform mini-batch encoding of X where the mini-batch samples are with respect to the number of elements n. Specifically, we partition X such that X can be written as a finite union X = X1 ∪X2 ∪ . . .∪Xp and each Xi in this partition has ni = |Xi| elements and p is the total number of partitions. We further assume that X is partitioned such that we can efficiently process a given mini-batch Xi in the partition. Each partition Xi is encoded with a set encoding function f(Xi) to obtain Zi. We then define the set encoding problem as follows:
Z = g ( f(X1), f(X2), . . . , f(Xp) ) (1)
where g(·) is an aggregation function that takes individual Zi’s and combines them to obtain Z. We further require that the functions f and g are Mini-Batch Consistent. Property 2.1 (Mini-Batch Consistency). Let X ∈ Rn×d be partitioned such that X = X1 ∪X2 ∪ . . .∪Xp and f : Rni×d 7→ Rd ′ be a set encoding function such that f(X) = Z. Given an aggregation function g : {Zj ∈ Rd ′}pj=1 7→ Rd ′ , g and f are Mini-Batch Consistent if and only if
g ( f(X1), . . . , f(Xp) ) = f(X)
Property 2.1 ensures that no information is lost by encoding the full set in independent mini-batches, and that the aggregation function g guarantees the same output as encoding the full set in a single batch. Additionally, Property 2.1 is general and places no restriction on the form of the functions f and g except that when used together, MBC must be satisfied. In what follows, we define an attention-based set encoding function f together with aggregation functions g that satisfy Property 2.1.

heading: 2.3 Slot Set Encoder

text:
In this section, we provide a formulation for an attention based set encoding function f in Equation 1 which utilizes slots [8]. Given an input set X ∈ Rn×d, we begin by sampling a random initialization for K slots S ∈ RK×h where h is the dimension of each slot. Specifically,
S ∼ N (µ, diag(σ)) ∈ RK×h, (2)
where µ ∈ R1×h and σ ∈ R1×h are learnable parameters. Optionally, instead of sampling random initialization for theK slots, we can instead designate deterministic learnable parameters Sχ ∈ RK×h. An advantage of random initialization over learnable parameters is that at test time, we can increase or decrease K for the randomly initialized model. In the ablation studies in section 3.1.1, we explore the performance gains that result from the choice of slot initialization. The key design choice in the slot set encoder is that unlike attention based set encoding methods like Lee et al. [6], we compute attention over S (no self-attention) instead of computing it over the n elements of X (self-attention). This allows us to remove the dependence of the set encoding function on n, alleviating the requirement of processing the entire set at once, and allowing for MBC encoding of partitions of X since the same slots are used to encode all mini-batches. Specifically, we compute dot product attention between S and X according to the following formulation:
attni,j := σ(Mi,j) where M := 1√ d̂ k(X) · q(S)T ∈ Rn×K (3)
where k and q are linear projections of X and S to a common dimension d̂ and σ is the sigmoid activation function. There is a key difference in our attention formulation in that we use a sigmoid instead of a softmax to construct the attention matrix. Using a softmax, even when computed over S, breaks MBC as it requires a batch dependent normalization term which will vary across different partitions of X . By using the sigmoid function, we are able to free our model of this constraint and satisfy MBC. Finally, we weight the inputs based on the computed attention matrix to obtain the final slot set encoding Ŝ for X:
Ŝ :=WT · v(X) ∈ RK×d̂ where Wi,j := attni,j∑K l=1 attni,l
(4)
where v is also a linear projection applied to X and W ∈ Rn×K are the weights computed over slots instead of elements. The normalization constant in W occurs over the slot dimension K, and only contains a linear combination of a single ni ∈ X and slots S and therefore has no dependence on other elements within the partition Xi. The Slot Set Encoder is fully described in Algorithm 1.
The Slot Set Encoder in Algorithm 1 is functionally composable over partitions of the input set X . More concretely, for a given slot initialization and any partition of X ,
f(X) = g(f(X1), f(X2), . . . , f(Xp)) (5)
Where the aggregation function g is chosen to satisfy Property 2.1. This is convenient since it allows us to define g from the following set of operators: g ∈ {mean, sum, max, min}. We note that to satisfy MBC, we have chosen g to be an associative function but it is entirely possible to formulate a non-associative g and corresponding f that satisfies MBC and we leave that for future work. Proposition 2.1. For a given input set X ∈ Rn×d and slot initialization S ∈ RK×d, the functions f and g as defined in Algorithm 1 are Mini-Batch Consistent for any partition of X and hence satisfy Property 2.1.
Proposition 2.2. Let X ∈ Rn×d and S ∈ RK×d be an input set and slot initialization respectively. Additionally, let SSE(X,S) be the output of Algorithm 1, and πX ∈ Rn×n and πS ∈ RK×K be arbitrary permutation matrices. Then,
SSE(πX ·X,πS · S) = πS · SSE(X,S)
Proofs of Proposition 2.1 & 2.2 involve showing that each component in Algorithm 1 are both MBC, and permutation invariant or equivariant. Details can be found in the Appendix with discussions on why the baselines fail or satisfy MBC.

heading: 2.4 Hierarchical Slot Set Encoder

text:
The Slot Set Encoder can encode any given setX ∈ Rn×d to a d̂ dimensional vector representation. In the mini-batch setting, all partitions are independently encoded and aggregated using the aggregation function g. In many practical applications, it is useful to model pairwise interactions between the elements in the given set since not all elements contribute equally to the set representation. Indeed this is the key observation of Lee et al. [6] which models such pairwise and higher order interactions between set elements and obtain significant performance gains over Zaheer et al. [14] which assumes
that all elements contribute equally to the set encoding. In the Slot Set Encoder, we would like to be able to model such pairwise and higher order interactions. However to satisfy Mini-Batch Consistency, we cannot model interactions between set elements given that the Slot Set Encoder removes all dependencies on n. Hence, we propose to model interactions among slots via a stack of Slot Set Encoders. Specifically, instead of using a Slot Set Encoder with K = 1, we stack T Slot Set Encoders each with Ki slots and set KT = 1 for the final encoder. Concretely, if we let SSE be an instance of the Slot Set Encoder defined in Algorithm 1, then we can define a series of such functions, SSE1, . . . , SSET . Then for a set X , a composition of these Slot Set Encoders is a valid set encoding function that satisfies all the requirements outlined in Section 2.3, such that:
f(X) = SSET (. . . SSE2(SSE1(X))) (6)
This gives a hierarchy of Slot Set Encoders capable of modeling pairwise and higher order interactions between slots. The Hierarchical Slot Set Encoder is analogous to stacking multiple Induced Set Attention blocks followed by a final Pooling MultiHead Attention used in Set Transformer [6]. The major difference is that our model still remains MBC, a property violated by Set Transformer.

heading: 2.5 Approximate Mini-Batch Training of Mini-Batch Consistent Set Encoders

text:
Algorithm 1 Slot Set Encoder. Partitioned input X = {X1, . . . , Xp} Initialized slots S ∈ RK×h aggregation function g.
1: Input: X = {X1, X2, . . . , Xp}, S ∈ RK×h, g 2: Output: Ŝ ∈ RK×d 3: Initialize Ŝ 4: S = LayerNorm(S) 5: for i = 1 to p do 6: Compute attni(Xi, S) using Equation 3 7: Compute Ŝi(Xi, attni) using Equation 4 8: Ŝ = g(Ŝ, Ŝi) 9: end for
10: return Ŝ Set encoding mechanisms such as Zaheer et al. [14] and Lee et al. [6] require that gradient steps are taken with respect to the full set. However, in the Mini-Batch Consistent setting described so far, this is not feasible given large set sizes or constraints on computational resources. A solution to this problem is to train on partitions of sets sampled at each iteration of the optimization process. We verify this approach empirically and show that the Slot Set Encoder presented so far can be trained on partitions of sets and still generalize to the full set at test time. In these experiments (Figure 3b), we train set encoders on subsets of sets sampled at each optimization iteration and perform inference on the full set. Specifically, at some iteration t, we sample a mini-batch of size B × ñ × d, where B is the batch size and ñ is the cardinality of a partition of a set with n elements (ñ < n). For this empirical analysis, we use the CelebA dataset [7] where the pixels in an image forms a set and the task is to reconstruct the image using the set encoding of a few pixels given as context points.

heading: 3 Experiments

text: We evaluate our model on the ImageNet [2], CelebA [7], MNIST [5] and ModelNet40 [13] datasets. Details on these datasets can be found in the Appendix. In these experiments, all sets arrive in a streaming setting in a mini-batch fashion where we only get subsets (batches) of the full set at an instance. Once the mini-batch is encoded, we only have access to the set encoding vector (we do not keep the original set elements since it requires further storage) which must be updated as more batches of the set arrive. We provide further implementation details in the Appendix.

heading: 3.1 Image Reconstruction

text:
In this task, we are given a set of pixels (each 3 dimensional) with their corresponding coordinate points (each 2 dimensional), termed context values, and the task is to reconstruct the full image given the coordinates of the pixels we wish to predict using only the context points. The context points are 5 dimensional vectors formed by concatenating the pixels and their corresponding coordinates. We use Conditional Neural Processes [3], CNP, for this task. CNP has a set encoding layer for compressing the context points into a single vector representation that is then passed to a decoder for constructing the full image. Here, our goal is to demonstrate that the Slot Set Encoder is a proper set encoding
function capable of learning rich set representations. We sample 200, 400, and 500 context points for images of size 32 × 32 and 1000 context points for images of size 64 × 64. As baselines, we use the mean set encoding mechanism of Zaheer et al. [14] and the Pooling MultiHead Attention (PMA) Blocks of Lee et al. [6]. We compare this with a variant of the Slot Set Encoder with random slot initialization. All the methods encode the given set to a 64 dimensional representative vector and are trained for 200 epochs. Additionally, for fair comparison, we only use a single Slot Set Encoder in our models as well as a single PMA block for Set Transformers.
The results for these experiments are presented in Figure 3a where it can be seen that the Slot Set Encoder model learns richer set representations resulting in lower negative log-likelihood when trained on full sets. Additionally in Figure 3b we demonstrate the scalability of the Slot Set Encoder where models initially trained on 1000 context points (in Figure 3a) are used to encode larger sets of context points (2000 - 4000) at test time. Since Set Transformer is not Mini-Batch Consistent, it cannot make use of the additional context points as it violates Property 2.1 hence in the constraints of the experiments, we use a 1000 context points for Set Transformer. DeepSets and Slot Set Encoders can utilize the additional data but the representation obtained by the Slot Set Encoder is richer in its representation power resulting in significant performance gains at test time as well as better generalization to larger set sizes than was used during training. In Section 3.1.1 we further discuss Figure 3b in the context of constrained resources and streaming data.

heading: 3.1.1 Ablation

text:
The Slot Set Encoder presented so far has various components and evaluation modes that can have an impact on the richness of the resulting set representation. In this subsection, we perform extensive ablation studies to explore how these various components contribute to the performance of the encoder.
Constrained Resources and Streaming Data In order to demonstrate the utility of the models that satisfy Property 2.1, we simulate cases where the computational resources are limited in terms of memory. Specifically, we assume that our computational budget allows us to only compute the set representation for 1000 context points at a time. Under these constraints, the Set Transformer can only be used to encode 1000 context points since the Softmax attention layer requires all the set elements to be in memory. For MBC DeepSets, and Slot Set Encoder, we can use mini-batches of of size 1000 and iteratively update the set representation until the full set has been encoded. Additionally, this setting is akin to the case of streaming data where the set elements arrive or are obtained at irregular intervals and hence the set encoding representation must be incrementally updated.
We present the results of this experiment for an input image with 4096 pixels with 1000 context points randomly selected and encoded at each time step. From Figure 3b it can be seen that for both DeepSets and the Slot Set Encoder, the more batches we encode, the better the performance. However, the Slot Set Encoder significantly outperforms DeepSets due to it’s ability to model interactions between the set elements and slots. Additionally, it can be seen that the MBC models get better as
more data arrives justifying our initial motivation for making use of all the available set elements instead of using a randomly sampled subset (in the preprocessing stage) in place of the full set.
Mini-Batch Training of Mini-Batch Consistent Set Encoders In Section 2.5, we proposed to train the Slot Set Encoder by approximating the full training procedure on partitions of the set. As we highlighted, under memory constraint and large set size assumptions, we cannot take gradient steps with respect to the full set. To demonstrate that this mini-batch training generalizes when the full set is processed at inference time, we train a model on 1000 elements and test it on larger set sizes. This result is demonstrated in Figure 3b on the CelebA dataset where the model performance improves as larger sets are processed. In Figure 3c, we take the same model and evaluate it on smaller set sizes of 100-500 context points and compare it to both DeepSets and Set Transformers where again we find that the Slot Set Encoder perform significantly better. Additionally, Figure 3d shows that the models trained in this fashion can achieve a faster convergence rate. We find that for the problems we consider in this work, this mini-batch training is sufficient and generalizes at inference time.
Choice of Aggregation Function In Section 2.3, we stated that we choose the aggregation function g from the set {mean, sum, max, min}. On the CelebA experiments, we explore the effects of making such a choice for the model with random slot initialization. In Figure 4a, we take a model trained on sets with cardinality 1000 and evaluate it on larger sets at test time. As can be inferred, the aggregation functions mean and sum consistently outperform the min and max for this task. This is intuitive since in the image reconstruction task, an aggregation function that considers the contribution of all pixels is necessary. In Section 3.2, we use a model with max as the aggregation function for Point Cloud Classification where it performs better than the other options. We find that the choice of the aggregation function g is very much informed by the task at hand. We observe a similar trend for the Slot Set Encoder with deterministic slot initialization and report this result in the Appendix.
Deterministic (D) vs Random (R) Slot Initialization For slot initialization, we have the choice of using deterministic or random (with learnable µ and σ) slots. In this choice, we find in almost all our experiments that random initialization performs better across all the tasks we investigated. This trend can be observed in Figure 4b where using random slot initialization results in lower negative log-likelihoods. To explain this behaviour, we reiterate that slots attend to different portions of the input set and hence the usage of random initialization encourages the model to attend to a wider coverage of the input sets during training as opposed to deterministic slot initialization.
Number of Slots When we define slots S ∈ RK×h, we must decide the number of slots K to use and we explore the effects of this choice on model performance here. We fix a model that encodes an input set to a 64 dimensional vector and train multiple models with varying K (specifically, we test for K = 1, 32, 64, 128, 256) and we observe that using very small or large number of slots can have a negative effect on the performance of the model for both deterministic and random slot initialization. For this specific model, we find that selecting K between 32 and 128 performs best. Additionally, we find that this parameter is also very dependent on the task. More details are provided in the Appendix.
Dimension of Slots Additionally, for slots S ∈ RK×h, we can choose the dimension of each slot h arbitrarily since the projection layer will eventually reduce it to ĥ. Similarly to the experiments on the number of slots, we fix a model that encodes sets to 64 dimensions using a single Slot Set Encoder and vary the dimensions of the slot keeping K = 1. We experiment with d = 32, 64, 128, 256 and find that this parameter has a significant impact on the performance of the model. Specifically, we
find that for slots with random initialization, the dimension of the slots can have a negative impact if not chosen properly. For deterministic initialization, increasing the slot dimension generally results in better performance. In our experiments involving randomly initialized slots, we train multiple models with varying h and pick the best one. The results discussed here can be found in the Appendix.
Hierarchical Slot Set Encoder Finally, we explore stacking multiple layers of Slot Set Encoders based on the hierarchical formulation presented in Section 2.4. We start with a single Slot Set Encoder with K = 1 and h = 32 and for each hierarchy, we double the slot dimension. For this experiment, we find that stacking multiple Slot Set Encoders for the tasks we consider provides marginal performance gains and can result in performance degradation when the hierarchy gets very deep. This is shown in Figure 4c where the performance of the model degrades after 4 hierarchies.
3.2 Point Cloud Classification
Using the ModelNet40 dataset, we train models that encode an input set (point cloud) to a single set representation that is used to classify the object as one of 40 classes. We follow the experimental settings of Zaheer et al. [14] and Lee et al. [6] where for point clouds with cardinality less than 5000, all the compared methods encode the point cloud to a 256 dimensional vector and 512 for point clouds with 5000 points or more. Set Transformer and DeepSets use a proprietary version of the ModelNet40 dataset however in our experiments, we use the raw ModelNet40 dataset which can sample an arbitrary number of points, and sample points for each instance randomly at every iteration.
The ModelNet40 dataset is difficult to classify when the number of elements in the set is relatively small. This is shown in Table 1 where we test the two variants of our model with both deterministic (D) and random
(R) slot initialization. The Slot Set Encoder models outperform DeepSets and Set Transformer. As the number of points increase to 5000, DeepSets and the Slot Set Encoder model achieve similar performance as expected. From the Table 1, it can be seen that the two competing models are DeepSets and our models and hence we check the generalization of both models in the Mini-Batch testing setting where a model trained on sets with 100 elements is tested on 200, 300, 400 and 500 elements. As can be seen from Figure 4d, although DeepSets is Mini-Batch Consistent, it experiences performance degradation when the set size grows on the ModelNet40 dataset. Conversely, the Slot Set Encoder based model gets better as the set size increases at test time showing that it generalizes better than DeepSets with Mini-Batch training (Section 2.5).

heading: 3.3 Cluster Centroid Prediction

text:
In order to show the effectiveness of Mini-Batch Consistent set encoding on sets of high cardinality, we experiment with Prototypical Networks [11] for classification on the ImageNet and MNIST datasets (see the Appendix for MNIST results). We use a pretrained ResNet50 backbone with the final layer removed, and train the set-encoding layers for DeepSets/SSE in the latent feature space. We train for 20-way classification with 2 support and 2 query instances. Each support set is encoded to a 128 dimensional vector (centroid), and we then train the model to minimize the Euclidean distance between the query instances and the corresponding class centroid. There is no decoder in this experiment, as we only utilize the pooled representation for inference. We investigate the effects of testing on both lower and higher ’way’ (5-1000 way) problems (Figure 5) and different encoded support set sizes (Figure 6). Given the large size of the set, we compare our model with DeepSets, as it is the only other MBC set encoder. In Figure 6 we plot accuracy vs. encoded set size for various ’ways’. In both the 1 and 20 way tasks, our SSE and Deepsets show similar performance, we attribute
this to the fact that 1 way classification provides minimally informative singleton sets, and 20-way classification is the setting in which the model was trained. The Slot Set Encoder generalizes better on the other 10 and 1000 way experiments which differ from the training setting.

heading: 4 Related Work

text:
Set Encoding In DeepSets, Zaheer et al. [14] show that neural architectures for set data are required to obey the permutation invariance/equivariance symmetry and can be formulated as the following sum-decomposition of two functions, f(xn) = f̃ (∑n i=1 φ(xi) ) where φ is a feature extractor and f̃ is some non-linear activation function such as ReLU. Additionally, instead of the sum operator, min,max and mean also satisfy the imposed constraints. While there exist previous works [9] on invariant pooling methods, DeepSets provided a universal model for constructing such neural networks. However, the architectures proposed in DeepSets are simple and in some cases lack expressivity. Set Transformer [6] solves this issue by formulating a set compatible version of the Transformer [12] which is capable of modeling pairwise interactions among the input set. Additionally, Lee et al. [6] reduce the complexity of Transformers from O(n2) to O(mn) by introducing inducing points that serve as queries to reduce the size of the input set before self-attention. Other methods that tackle the set encoding problem include Murphy et al. [10] and Zhang et al. [15]. However all of these methods require processing all elements of the input set at once and hence cannot be used in the MBC setting.
Slot Attention Locatello et al. [8] introduced a slot attention mechanism to learn object-centric representations. Slots are variables which adapt and bind to objects (sets of features) to form non-stationary, input-dependent representations. The slot attention mechanism works by iteratively updating an initialized set of slots with a GRU [1] to adapt them to the current inputs. Through the adaptation process, the slots compete for sets of similar features which compose objects by specializing their weights to achieve a higher activation value in the softmax of the attention matrix. While the idea of slots provided an initial inspiration for our work, they were not designed for set encoding like DeepSets and break MBC for a couple of reasons: 1) The GRU iteratively updates the slots, which depends heavily on the set elements. 2) the Softmax normalization layer depends on all elements in the set and 3) updates on hidden states in the model also break MBC.

heading: 5 Conclusion

text:
In this work, we have identified a key limitation of set encoding methods when applied to large scale / streaming set encoding. Additionally, we identified a key property, Mini-Batch Consistency, that is required to guarantee that set encoding methods are amenable to mini-batch processing of set. We further detailed the formulation of an instance of an attentive set encoding mechanism dubbed Slot Set Encoder that respects the symmetries of permutation invariance/equivariance, is Mini-Batch Consistent and can be trained with a mini-batch approximation of the full set gradients. We demonstrated the utility of SSE with extensive experiments and ablation studies and verified that
SSE is capable of learning rich set representations while satisfying MBC. An interesting direction of future research would be to use more sophisticated methods to approximate the mini-batch training routine (in Section 2.5) with respect to the full set without having to consider all elements in the set.

heading: 6 Acknowledgment

text: This work was supported by the Engineering Research Center Program through the National Research Foundation of Korea (NRF) funded by the Korean Government MSIT (NRF-2018R1A5A1059921), the Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No.2020-0-00153), the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2021R1F1A1061655), the Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government(MSIT) (No.2021-0-02068, Artificial Intelligence Innovation Hub), the Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government(MSIT) (No.2019-0-00075, Artificial Intelligence Graduate School Program(KAIST)) and the HPC Support Project, supported by the Ministry of Science and ICT and NIPA.

title: Mini-Batch Consistent Slot Set Encoder for Scalable Set Encoding


summaries: This paper builds off of Gray et. al. by swapping out the blueprint that is trained on human data with one that is trained from scratch using a deep learning variant of Nash-Q learning. The new method is able to achieve what appears to be superhuman performance in 1v1 Diplomacy and also does well but with mixed results in 6v1 Diplomacy against existing methods.

summaries: The paper proposes learning methods for the No-Press variant of the board game Diplomacy.   The method uses an equilibrium search method (similar to [9]) to solve for Nash in a single turn of the game, estimating future returns with a value function one turn in the future. Then a policy is trained to predict the equilibrium found, while the value function is trained to predict the values of the Nash equilibrium, which implements value iteration.  The equilibrium search method is based on prior work [9]. This tackles the large action space by restricting search to only the most likely actions from a policy network. This is extended in this work by using Double Oracle to expand the action set, and using a Diplomacy-specific method to generate proposal actions, which exploits the graph structure of the game. The paper also introduces a transformer-based model for learning to play Diplomacy, which outperforms previous Graph-Network approaches, and advances methods to estimate the exploitability of a Diplomacy agent.  Experimental results show that this results in an agent that can defeat human opponents convincingly in a 2-player variant of Diplomacy.

summaries: Diplomacy is a complex 7-player strategy game that poses a challenge for RL due to its simultaneous moves and combinatorially large action space. In recent years significant progress has been made on learning human-level play by starting from imitation learning on a dataset of human play from websites, and then using some policy improvement algorithms. This paper tackles the exploration problem, introducing a policy improvement algorithm that reaches competitive-quality play without requiring a dataset, using Nash Q-learning, a double oracle-like method, regret matching, and geographically local perturbations for action proposals. They also find advantage from switching to a transformer-based architecture.  Their method (DORA) exhibits strong results in 1v1 human play, as well as being the first from-scratch agent able to play on par with DipNet (an imitation baseline) in a 1v6 setting, in a metagame that DORA wasn’t trained in.  Separately, their policy improvement method on top of an imitation network beats previous SOTA (SearchBot).

summaries: This paper describes an algorithm that trains agents through self-play with no human data and no reward shaping, and can accommodate the large action space of Diplomacy. It is an algorithm for action exploration and equilibrium approximation in games with combinatorial action spaces. This algorithm simultaneously performs value iteration reinforcement learning while learning a policy proposal network. Meanwhile, a double oracle step is used to explore additional actions to add to the policy proposals. They train an agent completely from scratch for a 2-player variant of Diplomacy and show that it achieves superhuman performance. They also train an agent for the 7-player no-press Diplomacy entirely from scratch with no human data for the first time and show that this agent differs radically from past agents that required human data. This approach therefore opens up the ability to investigate novel ways of playing the game.

summaries: The paper proposes an approach called DORA for building agents for the Diplomacy board game, which is a long standing AI challenge. The key achievement in the paper is constructing agents in a way that does not rely on imitating human gameplay (as opposed to some recent works which at least in part leverages historical game data). Diplomacy is hard because it has a large action space and as it is a game with many players (7 in the full game, but only two int eh France/Austria variant). The results are very good for the two player (France/Austria) variant against people. The results are more mixed in the 7 player game - when there are many copies of DORA, it does very well, but less well when there are many copies of another bot and one DORA player.

abstractText: Prior AI successes in complex games have largely focused on settings with at most hundreds of actions at each decision point. In contrast, Diplomacy is a game with more than 10 possible actions per turn. Previous attempts to address games with large branching factors, such as Diplomacy, StarCraft, and Dota, used human data to bootstrap the policy or used handcrafted reward shaping. In this paper, we describe an algorithm for action exploration and equilibrium approximation in games with combinatorial action spaces. This algorithm simultaneously performs value iteration while learning a policy proposal network. A double oracle step is used to explore additional actions to add to the policy proposals. At each state, the target state value and policy for the model training are computed via an equilibrium search procedure. Using this algorithm, we train an agent, DORA, completely from scratch for a popular two-player variant of Diplomacy and show that it achieves superhuman performance. Additionally, we extend our methods to full-scale no-press Diplomacy and for the first time train an agent from scratch with no human data. We present evidence that this agent plays a strategy that is incompatible with human-data bootstrapped agents. This presents the first strong evidence of multiple equilibria in Diplomacy and suggests that self play alone may be insufficient for achieving superhuman performance in Diplomacy.

authors:
Lukáš Adam
Rostislav Horčík
Tomáš Kasl
Tomáš Kroupa

title: Double oracle algorithm for computing equilibria in continuous games

authors:
Thomas Anthony
Tom Eccles
Andrea Tacchetti
János Kramár
Ian Gemp
Thomas C Hudson
Nicolas Porcel
Marc Lanctot
Julien Pérolat
Richard Everett

title: Learning to play no-press diplomacy with best response policy iteration

venue: arXiv preprint arXiv:2006.04635,

authors:
Christopher Berner
Greg Brockman
Brooke Chan
Vicki Cheung
Przemysław Dębiak
Christy Dennison
David Farhi
Quirin Fischer
Shariq Hashme
Chris Hesse

title: Dota 2 with large scale deep reinforcement learning

venue: arXiv preprint arXiv:1912.06680,

title: An analog of the minimax theorem for vector payoffs

venue: Pacific Journal of Mathematics,

authors:
Noam Brown
Anton Bakhtin
Adam Lerer
Qucheng Gong

title: Combining deep reinforcement learning and search for imperfect-information games

venue: arXiv preprint arXiv:2007.13544,

authors:
Noam Brown
Tuomas Sandholm

title: Simultaneous abstraction and equilibrium finding in games

venue: In Twenty-Fourth International Joint Conference on Artificial Intelligence,

title: Solving imperfect-information games via discounted regret minimization

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

title: Superhuman AI for multiplayer poker

venue: Science, page eaay2400,

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

title: Impala: Scalable distributed deeprl with importance weighted actor-learner architectures

venue: arXiv preprint arXiv:1802.01561,

authors:
Jonathan Gray
Adam Lerer
Anton Bakhtin
Noam Brown

title: Human-level performance in no-press diplomacy via equilibrium search

venue: arXiv preprint arXiv:2010.02923,

title: Approximation to bayes risk in repeated play

venue: Contributions to the Theory of Games,

authors:
Sergiu Hart
Andreu Mas-Colell

title: A simple adaptive procedure leading to correlated

venue: equilibrium. Econometrica,

authors:
Junling Hu
Michael P Wellman

title: Nash q-learning for general-sum stochastic games

venue: Journal of machine learning research,

authors:
Manish Jain
Dmytro Korzhyk
Ondřej Vaněk
Vincent Conitzer
Michal Pěchouček
Milind Tambe

title: A double oracle algorithm for zero-sum security games on graphs

venue: In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Marc Lanctot
Kevin Waugh
Martin Zinkevich
Michael Bowling

title: Monte carlo sampling for regret minimization in extensive games

venue: In Advances in neural information processing systems,

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

title: A unified game-theoretic approach to multiagent reinforcement learning

venue: In nternational Conference on Neural Information Processing Systems,

title: Markov games as a framework for multi-agent reinforcement learning

venue: In Machine learning proceedings

authors:
R Duncan Luce
Howard Raiffa

title: Games and decisions: Introduction and critical survey

venue: Courier Corporation,

authors:
Stephen Mcaleer
JB Lanier
Roy Fox
Pierre Baldi

title: Pipeline psro: A scalable approach for finding approximate nash equilibria in large games

venue: Advances in Neural Information Processing Systems,

authors:
Brendan McMahan
Geoffrey Gordon
Avrim Blum

title: Planning in the presence of cost functions controlled by an adversary

venue: In International conference on machine learning,

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

title: Human-level control through deep reinforcement learning

authors:
Philip Paquette
Yuchen Lu
Seton Steven Bocco
Max Smith
O-G Satya
Jonathan K Kummerfeld
Joelle Pineau
Satinder Singh
Aaron C Courville

title: No-press diplomacy: Modeling multi-agent gameplay

venue: In Advances in Neural Information Processing Systems,

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga

title: Pytorch: An imperative style, high-performance deep learning library

title: Stochastic games

venue: Proceedings of the national academy of sciences,

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

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

venue: search. Nature,

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

title: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play

authors:
David Silver
Julian Schrittwieser
Karen Simonyan
Ioannis Antonoglou
Aja Huang
Arthur Guez
Thomas Hubert
Lucas Baker
Matthew Lai
Adrian Bolton

title: Mastering the game of go without human knowledge

authors:
Vasilis Syrgkanis
Alekh Agarwal
Haipeng Luo
Robert E Schapire

title: Fast convergence of regularized learning in games

authors:
Tom Van de Wiele
David Warde-Farley
Andriy Mnih
Volodymyr Mnih

title: Q-learning in enormous action spaces via amortized approximate maximization

venue: arXiv preprint arXiv:2001.08116,

authors:
Oriol Vinyals
Igor Babuschkin
Wojciech M Czarnecki
Michaël Mathieu
Andrew Dudzik
Junyoung Chung
David H Choi
Richard Powell
Timo Ewalds
Petko Georgiev

title: Grandmaster level in starcraft ii using multi-agent reinforcement learning

text:
1 Introduction
Classic multi-agent AI research domains such as chess, Go, and poker feature action spaces with at most thousands of actions per state, and are therefore possible to explore exhaustively a few steps deep. In contrast, modern multi-agent AI benchmarks such as StarCraft, Dota, and Diplomacy feature combinatorial action spaces that are incredibly large. In StarCraft and Diplomacy, this challenge has so far been addressed by bootstrapping from human data [32, 24, 3, 11]. In Dota, this challenge was addressed through careful expertdesigned reward shaping [4].
In contrast, in this paper we describe an algorithm that trains agents through self play without any human data and can accommodate the large action space of Diplomacy, a longstanding AI benchmark game in which the number of legal actions for a player on a turn is often more than 1020 [24].
We propose a form of deep RL (reinforcement learning) where at each visited state the agent approximates a Nash equilibrium for the stage game with 1-step lookahead search, plays the equilibrium policy, and uses the equilibrium value as the training target. Since the full action space is too large to consider, this equilibrium is computed over a smaller set of candidate
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
actions. These actions are sampled from an action proposal network that is trained in unison with the value model. We show that our deep Nash value iteration algorithm, when initialized with a human-bootstrapped model, defeats multiple prior human-derived agents in no-press Diplomacy by a wide margin.
Next, we investigate training an agent completely from scratch with no human data in Diplomacy. In order to improve action exploration when training from scratch, the proposal actions are augmented with exploratory actions chosen through a double-oracle-like process, and if these discovered actions end up as part of the equilibrium then they will be learned by the proposal network. Using this technique, which we call DORA (Double Oracle Reinforcement learning for Action exploration), we develop a superhuman agent for a popular two-player variant of Diplomacy. Our agent is trained purely through self-play with no human data and no reward shaping.
We also train a DORA agent for the 7-player game of no-press Diplomacy, the first no-press Diplomacy agent to be trained entirely from scratch with no human data. When 6 DORA agents play with 1 human-data-based agent, all human-data-based agents perform extremely poorly. However, when one DORA agent plays with 6 human-data-based agents, the bot underperforms. These results suggest that self-play in 7-player Diplomacy may converge to equilibria that are incompatible with typical human play. This is in contrast to previous large-scale multi-agent benchmarks like multiplayer poker [9] and validates Diplomacy as a valuable benchmark for learning policies that are compatible with human behavior.

heading: 2 Background and Related Work

heading: 2.1 Description of Diplomacy

text:
In this section we summarize the rules of Diplomacy. For a more detailed description, see [24]. No-press Diplomacy is a zero-sum board game where 7 players compete for control on a map of Europe. The map contains 75 locations, 34 of which are supply centers (SCs). Each player begins with 3-4 units and 3-4 SCs and a player wins by controlling a majority (18) of the SCs. If no player controls a majority and all remaining players agree to a draw, then the victory is divided between the uneliminated players. In case of a draw, we use the Sum-of-Squares (SoS) scoring system that defines the score of player i as C2i / ∑ i′ C 2 i′ , where Ci is the SC count for player i.
Each turn during movement, all players simultaneously choose an action composed of one order for every unit they control. An order may direct a unit to hold stationary, to move to an adjacent location, to support a nearby unit’s hold or move, to move across water via convoy, or to act as the convoy for another unit. Because a player may control up to 17 units with an average of 26 valid orders for each unit, the number of possible actions is typically too large to enumerate. Additionally, in Diplomacy, often supports or other critical orders may be indistinguishable from a no-op except in precise combinations with other orders or opponent actions. This makes the action space challenging to learn with black-box RL. Actions are simultaneous, so players typically must play a mixed strategy to avoid being predictable and exploitable.
In the popular France vs. Austria (FvA) variant of Diplomacy, the number of players is reduced to two, but the victory condition and all game rules, including the number of locations and centers, remain the same. FvA serves as an effective way to isolate the challenge of an astronomically large imperfect-information action space from the challenge of Diplomacy’s multi-agent nature.

heading: 2.2 Stochastic Games

text:
Stochastic games [26] are a multi-agent generalization of Markov decision processes. At each state, each player chooses an action and the players’ joint action determines the transition to the next state. Formally, at each state s ∈ S agents simultaneously choose a joint action a = (a1, . . . , aN ) ∈ A1×· · ·×AN , whereN is the number of players. Agents then receive a reward according to a vector function r(s,a) ∈ RN and transition to a new state s′ = f(s,a). The game starts at initial state s0 and continues until a terminal state is reached, tracing a trajectory τ = ((s0,a0), ..., (st−1,at−1)) where f(st−1,at−1) is terminal. Each agent i plays according to a policy πi : S → ∆Ai, where ∆Ai is a set of probability distributions over actions inAi. Given a policy profileπ = (π1, . . . , πN ), the probability of a trajectory is p(τ |π) = ∏ (s,a)∈τ p(a|a ∼ π(s)), and we define the vector of
expected values of the game rooted at state s as V (π, s) = ∑ τ∈T (s) p(τ |π) ∑ (st,at)∈τ γ tr(st,at) where T (s) is the set of terminal trajectories beginning at s. We denote by V (π) := V (π, s0) the value of a game rooted in the initial state. We denote by π−i the policies of all players other than i.
A best response (BR) for agent i against policy profile π is any policy that achieves maximal expected value. That is, π∗i is a BR to π if Vi(π ∗ i , π−i) = maxπ′i Vi(π ′ i, π−i). A policy profile is a Nash equilibrium (NE) if all players’ policies are BRs to each other. Letting Vi be the ith component of V , π is a NE if:
∀i ∀π′i : Vi(π) ≥ Vi(π′i,π−i) An -NE is a policy profile in which an agent can only improve its expected reward by at most by switching to a different policy. If a policy profile is an -NE, we say its exploitability is .
We may also talk about Nash equilibria for one stage of the game rather than the whole game. For any state s, supposing we have values Q(s,a) that represent the expected values of playing joint action a in state s assuming some policy profile is played thereafter, we may define a new 1-step game where instead the game ends immediately after this action andQ(s,a) is itself the final reward. For such stage games, notationally we denote NE using the symbol σ rather than π.

heading: 2.3 Nash Q-Learning

text:
Value iteration methods such as Nash-Q have been developed that provably converge to Nash equilibria in some classes of stochastic game, including 2p0s (two-player zero-sum) stochastic games [19, 14]. Nash-Q learns joint Q values Q(s,a) that aim to converge to the state-action value of (s,a) assuming that some NE π is played thereafter. This is done by performing 1-step updates on a current estimated functionQ as in standard Q-learning, but replacing the max operation with a stage game NE computation.
Formally, suppose that a is played in s leading to s′. A NE σ, σi ∈ ∆Ai, is computed for the stage game at s′ whose payoffs for each joint action a′ are specified by the current values of Q(s′,a′). The value of this game to each player assuming this NE is then used as the target values ofQ(s,a). The update rule is thus:
Q(s,a)← (1− α)Q(s,a) + α ( r(s,a) + γ ∑ a′ σ(a′)Q(s′,a′) ) , (1)
where α is the learning rate, γ is the discount factor, and σ(a) := ∏ i σi(ai) is the probability of joint action a.
As presented later in Section 3.1, the foundation of our algorithm is an adaptation of Nash QLearning, with several modifications to make it suitable for deep RL and adjusted to use a value function rather than a Q function.

heading: 2.4 Double Oracle

text:
Double oracle (DO) is an iterative method for finding a NE over a large set of actions in a matrix game [22]. It leverages the fact that computing a best response is computationally much cheaper than computing a NE. Starting from a small set of candidate actions A0i ⊆ Ai for each player i, on each iteration it computes a NE σt in the matrix game restricted to the candidate actions At. Then, at each iteration t for each player i it finds the best response action at+1i ∈ Ai to the restricted NE σt and creates At+1i := A t i ⋃ {at+1i }. Formally, a t+1 i is an action in the full action set Ai that satisfies
at+1i = arg max a′∈Ai ∑ a∈At Qi(s, a1, . . . , ai−1, a ′, ai+1, . . . , aN ) ∏ j 6=i σtj(aj). (2)
DO-inspired methods have been used in a variety of other work for handling large or continuous action spaces [15, 7, 18, 1, 21]. Although in the worst case the equilibrium policy may have support over a large fraction of the action space, in practice in many problems a small subset of actions may suffice, and in this case DO-based methods can be computationally efficient due to being able to restrict equilibrium computation to only a tiny fraction of the total number of actions.
As we will present in Section 3.2, we make use of a DO-like procedure both within the RL loop and at inference time, and show it to be an effective way to introduce novel good actions to the policy.

heading: 2.5 Regret Matching

text:
Both Nash-Q-Learning and DO require the computation of NEs in matrix games, which we approximate using the iterative regret matching (RM) algorithm [5, 13], as has been done in past work [11]. RM is only guaranteed to converge to a NE in 2p0s games and other special classes of games [12]. Nevertheless, past work has found that it produces competitive policies that have low exploitability in important non-2p0s games including six-player poker and no-press Diplomacy [9, 11]. We therefore use RM to approximate a NE σ in restricted matrix games during DO.
In RM, each player i has a regret value for each action ai ∈ Ai. The regret on iteration t is denoted Regretti(ai). Initially, all regrets are zero. On each iteration t of RM, σ t i(ai) is set according to
σti(ai) =  max{0,Regretti(ai)}∑ a′ i ∈Ai max{0,Regretti(a′i)} if ∑ a′i∈Ai
max{0,Regretti(a′i)} > 0 1 |Ai| otherwise
(3)
Next, each player samples an action a∗i fromAi according to σti and all regrets are updated such that
Regrett+1i (ai) = Regret t i(ai) + vi(ai, a ∗ −i)− ∑ a′i∈Ai σti(a ′ i)vi(a ′ i, a ∗ −i), (4)
where vi(a) is the utility of player i in the matrix game. This sampled form of RM guarantees that the average policy over all iterations converges to a -NE in 2p0s games at a rate of at worst O( 1 2 ) iterations with high probability [17]. In order to improve empirical performance, we use linear RM [8], which weighs updates on iteration t by t.1 We also use optimism [30], in which the most recent iteration is counted twice when computing regret.

heading: 3 Algorithms

text: We now describe DORA in detail. DORA simultaneously learns a state-value function and an action proposal distribution via neural networks trained by bootstrapping on an approximate Nash equilibrium for the stage game each turn. A DO-based process is used to discover actions.

heading: 3.1 Deep Nash Value Iteration

text:
The core of the learning procedure is based on Nash Q-Learning as presented in Section 2.3, but simplified to use only a value function, with adaptations for large action spaces and function approximation.
Approximating a Q-function in a game with an action space as large as Diplomacy is challenging. However, in Diplomacy as in many other domains, the reward r(s, a) depends only on the next state s′ = f(s, a) and not on how it was reached, and since the transition function is known and can be simulated exactly, we can redefine r to be a function of just the next state s′. In that case, we can rewrite Update Rule 1 (from Section 2.3) in terms of a state value function:
V (s)← (1− α)V (s) + α(r(s) + γ ∑ a′ σ(a′)V (f(s,a′))) (5)
Since the state space is large, we use a deep neural network V (s; θv) with parameters θv to approximate V (s). Since the action space is large, exactly computing the Nash equilibrium σ for the 1-step matrix game at a state is also infeasible. Therefore, we train a policy proposal network π(s; θπ) with parameters θπ that approximates the distribution of actions under the equilibrium policy at state s. We generate a candidate action set at state s by sampling Nb actions from π(s; θπ) for each player and selecting the Nc Nb actions with highest likelihood. We then approximate a NE σ via RM (described in Section 2.5) in the restricted matrix game in which each player is limited to their Nc actions assuming successor states’ values are given by our current value network V (s; θv).
We explore states via self-play to generate data, with both players following the computed NE policy with an probability of instead exploring a random action from among the Nc proposals. Also, in
1In practice, rather than weigh iteration t’s updates by t we instead discount prior iterations by t t+1 in order to reduce numerical instability. The two options are mathematically equivalent.
place of θv and θπ , self-play uses slightly-lagged versions of the networks θ̂v and θ̂π to compute σ that are only updated periodically from the latest θv and θπ in training, a normal practice that improves training stability [23]. We then regress the value network towards the computed stage game value under the NE σ using MSE loss (whose gradient step is simply the above update rule), and regress the policy proposal network towards σ using cross entropy loss:
ValueLoss(θv) = 1
2
( V (s; θv)− r(s)− γ
∑ a′ σ(a′)V ( f(s,a′); θ̂v ))2 PolicyLoss(θπ) = −
∑ i ∑ ai∈Ai σi(a) log πi(s, ai; θπ),
(6)
We show in Appendix B that in 2p0s games, the exact tabular form of the above algorithm with mild assumptions and without the various approximations for deep RL provably converges to a NE. Outside of 2p0s games and other special classes, both Nash Q-learning and RM lack theoretical guarantees; however, prior work on Diplomacy and 6-player poker have shown that similar approaches still often perform well in practice [11, 3, 9], and we also observe that DORA performs well in 7-player no-press Diplomacy.
At a high level our algorithm is similar to previous algorithms such as AlphaZero [28] and ReBeL [6] that update both a policy and value network based on self-play, leveraging a simulator of the environment to perform search. The biggest differences between our algorithm and AlphaZero are that 1-ply RM acts as the search algorithm instead of Monte Carlo tree search (just as in [11]), the value update is uses a 1-step bootstrap instead of the end-of-game-value (which allows the trajectory generation to be off-policy if desired), and the policy network acts as an action proposer for the search but does not regularize the search thereafter. Our algorithm is also similar to a recent method to handle large action spaces for Q-learning [31] and reduces to it in single-agent settings.

heading: 3.2 Double-Oracle-Based Action Discovery

text:
The algorithm in Section 3.1 relies on the policy network to generate good candidate actions. However, good actions initially assigned too low of a probability by the network may never be sampled and reinforced. To address this, we use a mechanism based on double oracle, described in Section 2.4, to introduce novel actions. However, vanilla DO requires computing the expected value of all actions against the restricted matrix game NE. Since our action space is too large to enumerate, we generate only a pool of Np Nc actions to consider. A natural idea to generate this pool would be to sample actions uniformly at random from all actions. However, our results in Section 5.1 show this approach performs poorly. Intuitively, in a combinatorial action space as large as in Diplomacy often only a minuscule fraction of actions are reasonable, so random sampling is exceedingly unlikely to find useful actions (see Fig 1 for an example).
We instead generate the pool of Np actions for a player by generating local modifications of the candidate actions already in the restricted matrix game equilibrium. We first sample uniformly among the player’s Nd (d ≤ c) most probable actions in that equilibrium. Next, for each sampled action, we randomly sample a single location on the map and consider all units of the player adjacent to the location. For those units, we randomly choose legal valid new orders. We add the order in this pool that best-responds to the equilibrium as a new candidate action, and DO proceeds as normal.
As shown in Table 3, we found this method of action sampling to outperform simply picking legal and valid combinations of orders uniformly at random. Intuitively, this is likely because locality in Diplomacy, as in a wide variety of other problem domains and algorithms, is a powerful inductive bias and heuristic. Perturbations of good actions are vastly more likely than random actions to also be good, and spatially-nearby actions are more likely to need to covary than spatially-distant ones.
To further improve the scalability of our algorithm, we apply several additional minor approximations, including computing some of the above expected values using sampling and capping the number of DO iterations we perform. For details, see Appendix D.

heading: 4 Implementation and Methods

text: We describe our implementation of the above algorithms and training methods as applied to training in Diplomacy. For details on the exact parameters, see Appendix D. The code and the models are available online 2.

heading: 4.1 Data Generation and Training

text:
We implement deep Nash value iteration following the same considerations as deep Q-learning. Multiple data generation workers run self-play games in parallel. The policy and value targets on each turn along with the game state they correspond to are collected in a shared experience replay buffer and sampled by a set of training workers to train the networks. The policy proposal and value networks used by the data generation workers are only periodically updated from those in training.
During self play, each agent plays according to its part of the computed approximate-NE policy σ with probability 1− , and with probability plays a uniformly random action from the Nc actions obtained from the policy proposal network. We also use larger values of on the first two turns to quickly introduce diversity from the opening state, similar to the use of larger early exploration settings in other work, for example AlphaZero [29, 28]. Detailed parameters are in Appendix D.
Algorithm 1 Approximated Double Oracle 1: function FINDEQUILIBRIUMWITHDO(s, Nc, Np, Niters, ) 2: A← SAMPLEACTIONSFROMPROPOSALNET(s, Nc) 3: σ ← COMPUTEEQUILIBRIUM(s,A) 4: for t = (1..Niters) do 5: modified← 0 6: for i = (1..Nplayers) do 7: Âi ← GENERATEACTIONS(s,Ai, Np) . Uniform sampling or local modification 8: vi ← Ea∼σ [Vi(f(s,a); θv)] 9: a∗i , v ∗ i ← argmax
ai∈Âi Ea−i∼σ−i [Vi(f(s,a); θv)]
10: if v∗i − vi > then 11: Ai ← Ai ⋃ {a∗i } 12: σ ← COMPUTEEQUILIBRIUM(s,A) 13: modified← 1 14: if !modified then 15: Break
return σ
16: function GENERATEACTIONSLOCALMODIFICATION(s, Abase, Np) 17: A← {} 18: while |A| < Np do 19: a← SAMPLEACTION(Abase) 20: loc← SAMPLEMAPLOCATION() 21: clique← GETNEIGHBOURS(loc) 22: a′ ← RANDOMCOORDINATEDMODIFICATION(a, clique) 23: A← A ⋃ {a′}
return A

heading: 4.2 Model Architecture

text:
Our model closely follows the encoder-decoder architecture of [11]. We use the policy head to model the policy proposal distribution and the value head to predict the expected values of the players.
We found several adjustments to be effective for our use in deep Nash-based RL. Firstly, we removed all dropout layers, as we found this to improve training stability. Secondly, we replaced the graph convolution-based encoder with a simpler transformer encoder, improving model quality and removing the need to hardwire the adjacency matrix of the Diplomacy map into the architecture. Lastly, we also split the network into separate policy and value networks. Since our regret minimization procedure is essentially only a 1-ply search, the states on which we need to evaluate policy
2https://github.com/facebookresearch/diplomacy_searchbot
(the current state) and value (the states after one turn) are disjoint, so there is no gain to computing both policy and value in one network query, and we found splitting the networks improved the quality and effective capacity of the models. We measure the impact of these choices in Table 2 and describe the architecture in more detail in Appendix A.

heading: 4.3 Exploitability Testing

text:
To obtain a metric of the exploitablity of our final agents, we also train additional exploiter agents that rather than attempting to play an equilibrium, instead hold the exploited agent fixed and attempt to converge to a best response. We compare two approaches.
In the first approach, we reimplement the same actor-critic method with sampled entropy regularization previously used in [11] for 7-player no-press Diplomacy and apply it to 2-player FvA. In this approach, the other agent is treated as a black box, reducing the problem to just a standard Markov Decision Process to which we can apply classical RL techniques. Namely, we use Impala [10], an asynchronous version of actor-critic algorithm. Since search agents may take several seconds to act, [11] first trained a policy network to copy the behavior of the search agent and then applied RL to exploit this proxy agent. The proxy agent acts much faster, which enabled generating data faster. In contrast, we optimized the training loop so that it was possible to train to exploit the search agent directly without first generating a proxy policy network agent.
In the second approach, we begin with the policy and value models of the exploited agent and resume deep Nash value iteration, except with a single simple modification, described in Appendix E, that results in learning a best response rather than an equilibrium.

heading: 5 Results

text:
Diplomacy features two main challenges for AI research: its large combinatorial action space and its multi-agent (non-2p0s) nature. DORA is intended to address the former challenge. To measure its effectiveness on just the action-exploration aspect, we first present results in a 2p0s variant of Diplomacy called France vs. Austria (FvA). We show DORA decisively beats top humans in FvA.
Next, we present results for 7-player no-press Diplomacy, which has been a domain for much prior research [24, 3, 11]. We train a DORA agent from scratch with no human data and test it against pre-trained models from previous work [24, 11]3. In the 6v1 setting, (six DORA agents playing with one copy of another bot) DORA wins overwhelmingly against all other agents. However, in the 1v6 setting (one DORA agent playing with six copies of another bot), DORA does slightly worse than previous search agents that leveraged human data. Our results suggest that DORA converges to strong play within an equilibrium (i.e., a “metagame”) that is very different from how humans play. Finally, we present results showing that adding our RL algorithm on top of a human-bootstrapped model clearly beats prior bots in both the 1v6 and 6v1 settings.

heading: 5.1 Results in 2-player France vs. Austria

text:
In 2-player FvA, we tested our final DORA agent against multiple top players of this variant, inviting them to play a series of games against our agent. All players were allowed to play an arbitrary number of practice games against the agent before playing official counted games. Prior to running the games, we also implemented a simple variance reduction method, described in Appendix C.
3See Appendix D for the details.
In Table 1 we report both the raw and variance-reduced average scores. DORA defeats top human players by a large and highly significant margin, with an average score of 78% after variance reduction. It also wins significantly more than half of games as France, the side considered much harder to play4. These results show DORA achieves a level of play in FvA above that of top humans.
We ran several ablations to loosely estimate the relative importance of the various components contributing to our final agent for France vs Austria.
GraphConv vs Transformers
Double Oracle at Training Time See Table 2. Although not a primary focus of this paper, we found that at least for use in RL, changing our model architecture to use a transformer encoder rather than a graph-convolution encoder in Section 4.2 resulted in significant gains over prior neural network architectures in Diplomacy [24, 3, 11], while using fewer parameters and still being similarly fast or faster in performance. Enlarging the model and splitting the network led to further gains.
See Table 3. We demonstrate the effectiveness of our DO method in finding improved actions during training. DO’s ability to discover new strong actions for the policy proposal network to learn makes a big difference in the final agent. Local modification sampling is effective, whereas random sampling is relatively ineffective.
Double Oracle at Inference Time See Table 4. We also demonstrate the effectiveness of our DO method in finding improved candidate actions at inference time. Uniform random sampling among legal actions to generate the action pool for finding best responses only improves the weakest of our baseline agent at inference time, due to being ineffective at finding better actions within the huge action space, whereas local modification sampling improves all baselines at inference time.

heading: 5.1.1 Exploitability

text:
We implemented and tested both algorithms from Section 4.3 to estimate a lower bound on the exploitability of our agents. We also test a variant where we adapt deep Nash value iteration for exploitation just as in the second method, but disable policy learning - the value network learns to predict states of higher exploitability, but the policy proposal network is fixed and does not learn.
The results against our best agent are in Table 5. We find that despite being of superhuman strength, the agent is still relatively exploitable. In a 2p0s large-action-space setting, this is not necessarily
4Between agents of similar strength we often observe France winning only about a third of games vs Austria.
surprising. For example in Go, another game with a moderately large action space, there exist gaps of more than 1000 Elo (nearly 100% winrate) between different agents, all of which are superhuman, even with no explicit training for exploitation [27]. Moreover, in imperfect-information games such as Diplomacy, exploiting a fixed agent is much easier than training an agent with low exploitability, since the exploiting agent does not need to precisely balance the probabilities of its actions.
Nonetheless, we also observe that our adaptation of the deep Nash value iteration method greatly outperforms the simpler actor-critic method from [11], and that both value learning and DO-based policy learning are important for its performance, with value learning improving over the baseline from 50% to 60.5%, and policy learning improving further to 85.8% winrate over DORA.
We also observe that applying DO at inference time reduces the exploitability, from 90.5% using our strongest exploiter agent to 85.8%. Even at inference time, DO continues to find and suggest new effective actions that would otherwise be overlooked by the policy proposal network.

heading: 5.2 Results in 7-player No-Press Diplomacy

text:
We also applied our methods to 7-player no-press Diplomacy, training a DORA agent entirely from scratch with no human data in this more-challenging domain. For comparison, we also trained an agent via deep Nash value iteration beginning from policy and value networks first trained on human games. Our best results were achieved when we forced the agent to use the human-initialized policy for action proposal during training games, never updating it, and also stopping the training early - see additional ablations in Appendix H). Since we do not update the action proposal policy used in training games, we also do not apply DO for this agent, and so we refer to this agent as HumanDNVINPU ("deep Nash value iteration, no proposal update"). The results are reported in Table 6. Note that as these are 7-player games, the expected score if the agents perform equally well is 1/7 ∼ 14.3%. Unlike in 2p0s settings, in a competitive multi-agent game, particularly one such as Diplomacy where agents must temporarily ally and coordinate to make progress, there may be multiple different equilibria that are mutually incompatible [20]. An agent playing optimally under one equilibrium may perform very poorly in a pool of agents playing a different equilibrium.
For example in Diplomacy, it may be mutually benefit two agents to ally to attack a third, but in such cases players must often coordinate on a choice, for example on which unit attacks and which unit supports, or on which region to attack. Since an order and a support must exactly match to be effective, each choice may be a stable equilibrium on its own. But an agent that plays one choice in a population of agents that always play another in that situation will fail to match and will do poorly.
Our results are consistent with DORA converging roughly to an equilibrium that is very different than the one played by humans, but playing well within that equilibrium. DORA achieves only about an 11% winrate in a 1-vs-6 setting against one of the strongest prior human-data-based agents, SearchBot [11] (tying would be a score of 1/7≈ 14.3%). However, SearchBot fares even worse with only a 1.1% winrate in a 1-vs-6 setting against DORA.
Against a second DORA trained with a different random seed (Table 7), each DORA scores only about 3-8% against the other 1-vs-6. This suggests that different DORA runs may converge to different equilibria from each other.
Our results with HumanDNVI-NPU are also consistent with reinforcement learning converging to inconsistent equilibria. HumanDNVI-NPU soundly defeats SearchBot, the prior SOTA, winning 36.3% of games 1-vs-6, while SearchBot wins only 0.5% in the reverse matchup. Starting from a human-like policy, deep Nash value iteration massively improves the strength of the agent. Yet HumanDNVI-NPU still does extremely poorly vs DORA, and vice versa. Our results seem to suggest that in 7-player no-press Diplomacy, deep Nash value iteration converges to an equilibrium in which outside agents cannot compete, even agents trained independently by the same method, but that which equilibrium is found depends on initialization, with some equilibria performing far better versus human-like players than others. See also Appendix H for additional ablations and experiments.

heading: 6 Conclusions and Future Work

text:
Diplomacy has been a benchmark for AI research for two main reasons: its massive combinatorial action space and its multi-agent nature. We show that DORA achieves superhuman performance in 2- player Diplomacy without any human data or reward shaping, despite the combinatorial action space and imperfect information. DORA therefore effectively addresses the first challenge of Diplomacy.
Additionally, we show that DORA in full-scale 7-player no-press Diplomacy approximates an equilibrium that differs radically from human-data-based agents. When one human-data-based agent plays against a population of DORA agents, the one agent loses by a wide margin. Similarly, one DORA agent against a population of human-data-based agents does not exceed an average level of performance. These 7-player results provide evidence that self-play from scratch may be insufficient to achieve superhuman performance in Diplomacy, unlike other multiplayer games such as 6-player poker [9]. Furthermore, the results suggest that there may be a wide space of equilibria, with some differing dramatically from human conventions. DORA provides the first competitive technique for exploring this wider space of equilibria without being constrained to human priors.

title: No-Press Diplomacy from Scratch