Universally Expressive Communication in Multi-Agent Reinforcement Learning
Authors: Matthew Morris
Thomas D Barrett
Arnu Pretorius
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-agent reinforcement learning
communication
expressivity
graph neural networks

Abstract: Allowing agents to share information through communication is crucial for solving complex tasks in multi-agent reinforcement learning. In this work, we consider the question of whether a given communication protocol can express an arbitrary policy. By observing that many existing protocols can be viewed as instances of graph neural networks (GNNs), we demonstrate the equivalence of joint action selection to node labelling. With standard GNN approaches provably limited in their expressive capacity, we draw from existing GNN literature and consider augmenting agent observations with: (1) unique agent IDs and (2) random noise. We provide a theoretical analysis as to how these approaches yield universally expressive communication, and also prove them capable of targeting arbitrary sets of actions for identical agents. Empirically, these augmentations are found to improve performance on tasks where expressive communication is required, whilst, in general, the optimal communication protocol is found to be task-dependent.

Universally Expressive Communication in Multi-Agent Reinforcement Learning
Matthew Morris
Thomas D. Barrett
InstaDeep Ltd. & University of Oxford aatthew.morris@cs a.. ac. uk
InstaDeep Ltd.
t. bawreett@nnstddepp.oom
Armu Pretorius InstaDeep Ltd.
a. pretorrissinstaddee..p com
Abstract
Allowing agents to share information through communication is crucial for solving complex tasks in multi-agent reinforcement learning. this work, we consider the question of whether a given communication protocol can express arbitrary policy. By observing that many existing protocols can be viewed as instances graph neural networks (GNNs), we demonstrate the equivalence of joint action selection to node labelling. With standard GNN approaches provably limited their expressive capacity, draw from existing GNN literature and consider augmenting agent observations with: (1) unique agent IDs and (2) random noise. We provide theoretical analysis expressive communication, and also prove them capable of targeting arbitrary sets found
how these approaches yield universally
of actions for identical agents. Empirically, these augmentations improve performance on tasks where expressive communication is required, whilst, in general, the optimal communication protocol is found be task-dependent.
Introduction
Communication lies at the heart of many multi-agent reinforcement learning (MARL) systems. In MARL, multiple agents must account for each other's actions during both training and execution and, indeed, solving complex tasks in high-dimensional spaces often requires cooperative joint policy that difficult, or even impossible, to learn independently. Therefore, allowing agents to share information is erucial and how best to achieve this has remained keen area of research since the seminal proposals of learned communication by Foerster et al. [14] and Sukhbaatar et al. [51]. Whilst approach has emerged, considerations for MARL communication
single universally-adopes include inductive biases that aid learning. For example, an agent's policy should often not depend on the order in which messages received at given time step. i.e. be permutation invariant.
In this context, graph neural networks (GNNs) provide a rich framework for MARL communication. It is natural to consider agents as nodes in a graph, with communication channels corresponding to edges between them. GNNs are specifically designed to respect this (typically non-Euclidian) structure [5] and, indeed, many of the most successful MARL communication models fall within this paradigm, including CommNet [51]. IC3Net [49], GA- GA-Comm [29], MAGIC [37], Agent- Graph [2], IP [44], TARMAC [9], IMMAC [52]. DGN [24], VBC [64], MAGNet [33], and TMC [65]. Other models such as ATOC [23] and BiCNet [43] do not fall within the paradigm since they L.SMss for combining messages, which not permutation invariant, and models such RIAL,,
DIAL [14], ETCNet [21], and SchedNet [25] do not since they used a fixed message- paaaagg structure.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Figure 1: A pair of graphs indistinguishable by 1-WL
However, although traditional GNNs such as those used MARL to date can readily provide permutation invariant communication, they are not universally expressive.
The expressivity of GNNs often considered in the context the 1-WL graph coloring algorithm [60]. In brief, 1-WL tests if two graphs are non-isomorphic by iteratively re-coloring the nodes and has been proven to not be universally expressive (i.e. there exist non-isomorphic graphs that 1-WL can't distinguish). Moreover, Morris et al. [34] and Xu et al. [61] proved that for any two non-isomorphic graphs indistinguishable by 1-WL, there is no GNN that can produce different outputs for those two graphs. An example of such graphs is given in Figure 1. This direct correspondence between GNNs and I-WL equivalently limits the expressivity of any MARL communication built on top of GNNs. Whist higher-order GNN architectures which go beyond 1-WL expressivity have been proposed (see [35] for an overview), many of these models do not scale well and are computationally infeasible in practice. However, recent works have shown that augmenting the node features can provide an alternative path to increased expressivity without computationally expensive architectural changes [1, 10J. It is then natural to ask if, and how, these advancements can be brought into the MARL setting.
In this paper, we investigate the effectiveness of GNNs for universally expressive communication in MARL. We define Graph Decision Networks (GDNs), framework for MARL communication which captures many of the most successful methods. We highlight the correspondence between GDNs and the node labeling problem in GNNs, thus making concrete limits GDN expressivity. For moving beyond these limits, we consider two augmentations from the GNN literature random node initialization (RNI) [1] and colored local iterative procedure (CIIP) [10], where random noise and unique labels added graph nodes, respectively. We provide theoretical analysis to how these algorithms yield universally expressive communication in MARL, and also prove their ability to solve coordination problems where the optimal policy requires arbitrary sets of actions from identical agents. We then perform an empirical study where we augment several state-of-the MARL communication algorithms with RNI and unique labels. By evaluating performance across both standard benchmarks and specifically designed tasks, we show that when complex non- coordination or symmetry breaking is required, universally expressive communication can provide significant performance improvements. However, in more moderate cases, augmented communication reduce convergence speeds and result in suboptimal policies. Therefore, whilst more expressive GNN architectures are required to improve performance on certain problems, a more complete picture relating expressivity downstream performance remains an open question for future work.
2
Background
Multi-Agent Reinforcement Learning We consider the setting of Decentralized Partially Ob- servable Markov Decision Processes [39] augmented with communication between agents. At each timestep / every agent E {1...., N) gets a local observation of, takes an action at. and receives reward rf. We consider two agent paradigms: value-based [53] and actor-critic [15, 32). For brevity, we collectively refer to the policy network actor-critic methods and the Q-network in value-based methods as the actor network. In this paper, we consider by default parameter sharing between agent's networks, which often used to yield faster and more stable training in MARL [14, 18, 45, 62].
Graph Neural Networks GNNs can refer to large variety of models; in this paper, we define the term to correspond to the definition of Message Passing Neural Networks (MPNNs) by Gilmer et al. [17], which is the most common GNN architecture. Notable instances of this architecture include Graph Convolutional Networks (GCNs) [12], GraphSAGE [19], and Graph Attention Networks (GATs) [56]. A GNN consists of multiple message- messagc-passing layers, each of which updates the node

---

Figure 2: The Graph Decision Network (GDN) framework
Graph Neural Network
Diseeostions and Envronment
attributes/ labels (terms used interchangeably.. For layer m and node i with current attribute uf", the new attribute un a is computed as
m++1 = I
Suger (ef)) N())),
(oo (VG())))
where ((1) is all nodes with edges connecting to i and 8m 6% 8" the (possibly trainable) parameters of the update, aggregation, and readout functions for layer m. Parameters may be shared
e between layers, e.g. 0, 0r. The functions fnger, read are permutation invariant, Importantly, GNNs are invariant equivariant graph functions.
Expressivity of Multi-Agent Communication
3.1 Graph Decision Networks
Many of the most successful MARL communication methods can be captured within the fol- lowing framework. At each time step, define attributed graph G (V, E) with nodes V(G)= := {all agents}. edges E(G) == [(t,j) agent i communicating with j}. and for all agents the node is labeled with the observation of This graph is passed through a GNN f which outputs values for each node and passes each resulting node value through the actor network of the corre- sponding agent. Assuming that the actor networks used for each actor), we can substitute them for final GNN layer M, where for (v, ~)) P(v) and P represents the shared actor network. We refer communication methods that fall within this paradigm as graph decision networks (GDNs). The framework is illustrated visually in Figure 2.
shared weights (i.e. the same neural network
Given the above assumption of shared weights, any GDN simply reduces to GNN node labelling problem, where the correct label for a given node is the corresponding actor network output that collectively maximizes the joint reward (or the individual reward, depending trained). Going forward, we only deal with such GDNs (ones with a shared actor network). In the case of stochastic policies [15, 63], the target labels parameters of output distributions, instead of atomic actions. This applies to both discrete and continuous distributions. Note that this is not how RL agents actually trained (i.e. they reward signals, not supervised learning).
how the agent is
However, given that this paper aims to analyze expressivity, we argue that it does not matter how the GDN is trained. All that expressivity is concerned with is the ability of model to produce certain output, not how the training paradigm causes the model to converge to the solution. All we have know is that there are "optimal" actor network outputs for each agent, under some metric of optimality, and then we can reason about the ability of the model to provide these outputs. Scenarios with heterogeneous agents can still be considered within this paradigm, by allocating portion of the observations to indicate the agent type (e.g. through a one-hot encoding) [54]. Models with recurrent networks also fall within the paradigm, where the hidden or cell states for the networks can be considered as part of the agent observations.
Due to the reduction of GDNs to GNN node labelling problem, GDNs suffer from the same expressivity limits as GNNs, about which there is plethora work [4, 8, 16, 30, 31, 34, 38, 40, 61]. These expanded upon in Appendix A.4, For our analysis, we focus particularly ways to achieve
3

---

Figure 3: A simple example of symmetry breaking
Communicate
expressivity, but note that the above reduction unlocks many tools for reasoning about the expressivity of GDNs.
universal
3.2 Desired Properties MARL Communication
Whilst conventional GDNs cannot capture functions with expressive power beyond 1-WL [34, 61], recent GNN architectures have been proposed achieve expressivity beyond 1-WL, even ones which are able to express any equivariant graph function. We can use these insights to construct more expressive GDNs. However, we note that classes models which always yield equivariant functions not necessarily desirable, since they cannot break symmetries between agents when required. Many MARL environments require agents to coordinate, needing some joint action to solve the task. However, if agents have identical observations and communication graph structure in pure GDN framework, there is no way for them to disambiguate between each other and distribute the required actions amongst themselves. For a simple example, consider setting where two agents have identical observations but must take opposite actions then the only way for them to solve the environment to communicate in such way that they can break this symmetry and take different actions from one another. This example is illustrated in Figure 3.
More formally, since GNNs are equívariant graph functions, GDNs are equivariant functions on the agent observations and communication graph structure. This means that agents within the same graph orbit will always produce the same output. For graph G, consider two nodes u, G. If there exists an automorphism a G such that a(u) = v, then u and v are said to be similar nodes. The relation is similar to forms equivalence relation on the nodes of G. Each equivalence class is called an orbit. Intuitively, every node in an orbit "has the same structure". We denote the set of all orbits of G by R(G): this forms partition of (G)).
Theorem 1. Given GDN f. observations O = {ol...., )n and communication graph G such that nodes and j are similar in G and o, Oj, then holds that f(O); = f(O),-
Full proofs for all theorems in this paper can be found in Appendix B. We formally state the desired symmetry breaking that would enable them solve such
behaviour of GDNs which we refer coordination problems. Given a graph G with orbits R(G), GDN ought to be able to produce, or target, multiset of labels Ag for each orbit TR:
Vru E R(G), (o(G), (iE AA.
where gG);; the output of g(G) for agent i. Thus, ideally, MARL communication methods should possess all the following properties: (1) universal expressivity for equivariant graph functions, (2) symmetry breaking for coordination problems, and (3) computational efficiency. We apply two existing GNN augmentations GDNs to achieve this, both of which come with minimal extra computational cost. In the following section, we provide theorems which prove that the first two properties are satisfied by these augmentations.
3.3 Expressive Graph Decision Networks
Random Node Initialization Sato et al. [47] propose augmenting GNNs with random node inirialization (RNI), where for each node in the input graph, number of randomly sampled values are concatenated to the original node attribute. For all graphs nodes, the random values are sampled from the same distribution. Abboud et al. [1] prove that such GNNs are universal and can approximate any permutation invariant equivariant graph function. Technically, random initialization breaks the node invariance in GNNs, since the result of the message passing will depend on the structure of the

---

graph as well as the values of the random initializations. However, when one views the model as computing a random variable, the random variable is still invariant when using RNL. In expectation. the mean of random features will be used for GNN predictions, and is the same across each node. However, the variability of the random samples allows the GNN to discriminate between nodes that have different random initializations, breaking the 1-WL upper bound.
Abboud et al. [1] formally state and prove a universal approximation result for invariant graph functions. They note that it can be extended to equivariant functions, which is what GDNs are. As such, we adapt and state the theorem for equivariant functions. Let G,, be the class of all n-node graphs. Let f Gn - IR"," graph function which outputs a real value for each node in V(G). We say that a randomized function X that associates with every graph G G,, sequence of random variables X6 ( (......... X, (G), one for each node, is an (c, a)approximmato of f if for all G E Gn it holds that Vi E (1, 2, ..., n), Pr([ (G)) S <) 2 1- ò, where f(G); is the output of f(G) for node i. Note that a GNN h with RNI computes such functions X. If X is computed by h, we say that h (c, aapproxiimts f. We can now state the following theorem:
Theorem 2. Let 2 1 and let f Gn + R be equivariant. Then for all e, 0, there is a GNN with RNI that (e, 8) approxxmmatss f.
Such GNNs are also able to solve symmetry-breaking coordination problems by using RNI to disambiguate between otherwise identical agents. To formally state this property, we need define (e, apprroxiiation for sets. We say that two multisets A, B containing random variables are (c, 6)- equal, denoted A E,5 B, if there exists a bijection T A + B such that Ya E A, Pr((a - T(a) S
<) 2 1-6.
Theorem 3. Let n. 21 1 and consider a set T, where each (G, A) E T is a graph-labels pair, such that GE Gn and there is multiset of target labels Ag A for each orbit r E R(G), with | |rx]-
Then for all c, 5 > O there is a GNN with RNI which satisfies:
V(G, A) T Vra E R(G), (o(G), (iEr)) =
In the GDN case, adding RNI means concatenating noise to the agent observations, thus achieving universal approximation and enabling the solving of symmetry-breaking coordination problems.
Unique Node Identifiers Dasoulas et al. [10] augment GNNs with a coloring scheme to define colored local iterative procedure (CIIP). They use colors differentiate otherwise identical node attributes, with k-CLIP corresponding to le different colorings being sampled and maximized over. They prove theoretically that when maximizing over all such possible colorings. co-CLIP can represent any invariant graph function.
Assigning nodes unique IDs is equivalent to 1-CLIP, since this guarantees that every node with identical attributes will have a unique "color": its particular unique ID. Therefore, we can leverage the universality result for 1-CLIP (Theorem 4 in [10]), which states that with any given degree of precision, 1-CLIP can approximate any invariant graph function. However, Dasoulas et al. [10] note that such solutions may be difficult to converge to and require large number of training steps in practice. Intuitively, this is because the GNN has to learn to deal with n! permutations of unique IDs. Similarly the RNI case, we extend their theorem to equivariant functions.
Theorem 4. Let n 2 1 and let f Gn + IR" be equivariant. Then all >> 0, there is a GNN with unique node IDs that e-approximates f.
Such GNNs can also solve symmetry-breaking coordination problems, in similar way to ones with RNL We say that two multisets A, B, which do not contain random variables, are e-equal, denoted A = B, if there exists a bijection т A + B such that Va E A, la -(a)l <.
Theorem Let n 2 1 and consider a set T,, where each (G, E T is a graph-labels pair. such that G E Gn and there is multiset of target labels A₁ E A for each orbit r& E R(G), with |Axl = |rk]-
Then for all e, > there is a GNN with unique node IDs g which satisfies:
V(G, A) T Vra E R(G), (o(G)) (( E.A, A
In the GDN case, this means that by giving each agent a unique ID in its observations, we can achieve universal approximation and enabling the solving of symmetry-breakinn coordination problems.
5

---

Table 1: Architecture of the Baselines
Name
Communication Graph
Agents
GNN Architecture
CommNet [51]
Complete (or environment-baseen
Recurrent A2C
Sum Aggregation
IC3Net [49]
Complete + Gating
Recurrent A2C
Sum Aggregation
TarMAC [9]
Complete + Learned Soft Edges
Recurrent A2C
GAT
T-IC3Net [49, 9]
Gating + Learned Soft Edges
Recurrent A2C
GAT
MAGIC [37]
Learned
Recurrent A2C
GAT
DGN [24]
Environment-basse based
Q-network
GCN
4
Experiments
4.1 Methods
Baselines For evaluation, we adopt a diverse selection of MARL communication methods which fall under the GDN paradigm. These are shown in Table along with the communication graph structure, agent model, and GNN architecture. We use the code provided by Jiang et al. [24]. Niu et al. [37] as starting points. All of the implementations are extended support multiple rounds of whessage-passing and the baselines are augmented with the ability for their communication to be masked by the environment (e.g. based on distance or obstacles in the environment). We fix the number of message-passing rounds to be 4 and otherwise use the original models and hyperparameters from [24, 37J. Full experiment and hyperparameter details can be found in Appendix C, and full results are shown in Appendix D.
Environments Predator-Prey [9, 27, 29, 37, 49] and Traffic Junction [9, 27, 29, 37, 49, 51] are common MARL communication benchmarks. In Predator-Prey, predator agents are tasked with capturing prey and in Traffic Junction, agents need successfully navigate traffic intersection (full descriptions of each environment are given in Appendix C.2). We perform evaluations these benchmarks to test how well our universally expressive GDN models perform when there is not necessarily benefit to having communication expressivity beyond 1-WL. We also introduce two new environments, Drone Scatter and Box Pushing, to respectively test cemmetry-breaking and communication expressivity beyond I-WL.
Drone Scatter consists of 4 drones in a homogeneous field surrounded by fence. Their goal is to move around and find target hidden in the field, which they can only notice when they get close to. The drones do not have GPS and can only see directly beneath them using their cameras, as well as observing their last action. The best way for them to locate the target is to split up and search in different portions of the field, despite them having the same observations; thus, they are given rewards for splitting up.
Box Pushing consists of 10 robots in 12x12 construction site, which has boxes within that need to be moved to the edge of the site: the clearing area. Robots attach themselves to boxes before they can move them: when attached, robots can no longer see around themselves. Free-roaming robots can communicate with any other free-roaming robots, but attached robots can only communicate with the robots directly adjacent to them. The environment either spawns with one large box or two small boxes and agents spawn already attached. 4 attached robots all moving in the same direction are needed move a small box, and all power moving in the same direction to move large box. To solve the environment, the robots need to be able to communicate with each other to figure out which type of box they are on and all push correctly, at the same time, and the same direction. Since the communication graphs corresponding to the scenarios with small and large boxes are 1-WL. indistinguishable, communication beyond I-WI. is needed to optimally solve the environment.
Evaluation Procedure We augment baseline communication methods with RNI and unique IDs to perform our evaluations. Agent IDs are represented by one-hot encodings and "0.25 RNI" refers to 25% of the observation space being randomly initialized. We sample each RNI value uniformly from [-1, 1]. For each scenario and for every baseline communication method, we compare models: the baseline without modifications, the baseline augmented with unique IDs for each agent, the baseline augmented with 0.75 RNI, and finally 0.25 RNI. The only exceptions are the Drone Scatter evaluations, where 0.25 RNI is not used since the observation space is not large enough, and the

---

Table 2: Mean and 95% confidence interval for Easy Traffic Junction across all baselines
Baseline
Metric
Baseline
Unique IDs 0.75 RNI 0.25 RNI
CommNet
Success
1 0
1 1
1 + 0
1 + 0
DGN
Success
0.987 0
0.99 0
0.848 + 0.15
0.996
IC3Net
Success
1
1
1
0.986 + 0.02
MAGIC
Success
0.63440..1
0.764 + 0.13
0.684 0.11
0.787 + 0.09
TarMAC
Success
0.994 + 0.01
1
0.933 0.04
1 1 0.974 0.04
T-IC3Net
Success
1
0.998 =
0.94
Drone Scatter experiments using stochastic evaluation, where DGN is not used since it does not support stochastic evaluation.
For each run, corresponding to a random initialization (one seed) of the model in question, we perform periodic evaluations during training. Each epoch consists of 5000 training episodes, after which 100 evaluation episodes are used to report aggregate metric scores, yielding an evaluation score for the model after every epoch. Following [15, 22, 41, 46, 59, 63, 66], we take the value of a metric for a run to be the best value achieved during training. that our metrics are robust against runs which converge at some point and then degrade in performance as they continue to train. In such cases, one would use the parameters from the best performing model found during training for real-world evaluation; thus, that performance makes more sense to report than the model performance once training has finished. We utilize 10 seeds for Box Pushing experiments and 5 for all others. For each scenario, metric, baseline communication method, and variant thereof, we report the mean metric value across all seeds and a 95% confidence interval. To calculate the confidence interval, we assume a normal distribution and compute the interval as 1.96 x SEM (standard error of the mean). Finally, for all Box Pushing experiments, we make use of form of hybrid imitation learning to help deal with exceptionally sparse rewards (full details are given in Appendix C.3).
established practice in MARL evaluation
4.2 Results
Benchmark Environments Experimental results on the benchmark environments are shown in Table 2 for Easy Traffic Junction, Table 3 for Predator-Prey, Prey, and Table for Medium Traffic Junction. In general, unique IDs tends to perform comparably to the baseline. The only exception to this is for IC3Net on Medium Traffic Junction, where unique IDs struggle.
0.75 RNI is categorically the worst method, consistently getting outperformed by all other methods and only coming out top for MAGIC on Medium Traffic Junction, which is not significant due to the instability of that set of results. 75% of observations being randomly initialized appears far too much for the system be able to learn effective policies. However, universality results still hold for lower ratios of RNI.
0.25 RNI exhibits strong performance on Easy Traffic Junction, always solving the environment and almost always outperforming the bascline. However, on sparse-reward problems (such as Predator- Prey and, to a lesser extent, Medium Traffic Junction) RNI methods typically take longer to converge than the bascline and unique IDs, and 0.25 RNI can struggle to reach the performance of baseline methods. This aligns with Abboud al. [1]'s observation that GNNs with RNI take significantly longer to converge than normal GNNs. This is only is exacerbated in a MARL setting with sparse reward signals, where slow convergence is expected regardless of the RNI augmentation. Indeed, on all examples, RNI methods typically take longer to converge than the baselines and unique IDs.
Overall, we conclude that both unique IDs and 0.25 RNI achieve sufficient performance the benchmarks to qualify them for use, especially given that the extra expressivity they provide not strictly necessary. With respect to the different baselines, CommNet work the best when the optimal policy is also simple, such as for Easy Traffic Junction, but that more sophisticated baselines outperform them on the complex environments. We also note the very unstable performance of MAGIC for the Traffic Junction environments.
note that simple baselines such as
Weisfeiler- Lehman Expressivity Results for the Box Pushing environment are shown in Table 5. 0.25 RNI is the clear winner, achieving the top performance across almost all baselines and only
7

---

Table 3: Mean and 95% confidence interval for Predator-Preyy across all baselines
Baseline
Metric
Baseline
Unique IDs
0.75 RNI
0.25 RNI
CommNet
Success
0.88 = 0.03
0.908 + 0.02
0.194 + 0.02
0,476 + 0.05
DGN
Success
0.014 0
0.016 0
0.026 + 0.03
0.032
IC3Net
Success
0.952 0
0.93 + 0.02
0.454 0.08
0.933 0.02
MAGIC
Success
0.892 0.02
0.888 + 0.05
0.112 0.03
0.451 + 0.09
TarMAC
Success
0.169 0.09
0.24 + 0.11
0.068 +
0.086 + 0.02
T-IC3Net
Success
0.938 + 0.02
0.938 + 0.01
0.27 0.02
0.913 + 0.02
Table 4: Mean and 95% confidence interval for Medium Traffic Junction across all baselines
Bascline
Metric
Baseline
Unique IDs
0.75 RNI
0.25 RNI
CommNett
Success
0.761 + 0.31
0.793 + 0.33
0.046 + 0
0.614 1 0.11
DGN
Success
1
1 1
0.062 +
0.619 1 0.4
IC3Net
Success
0.971 + 0.04
0.804 0.1
0.588 0.03
0.13
MAGIC
Success
0.551
0.28
0.526 + 0.33
0.734 0.21
0.4 0.35
TarMAC
Success
0.052 0
0.05 +
0.054 0.01
T-IC3Net
Success
0.89 + 0.17
0.909 + 0.08
0.362 + 0.18
0.962 = 0.02
slightly worse performance the others. never outperformed by the bascline. This indicates that when communication expressivity beyond I-WL is helpful for solving the environment, using RNI is the clear choice. Across all but one method, unique IDs also outperformed the baseline, demonstrating the benefit of having higher expressivity. However, unique IDs tend yield less stable solutions and less effective policies than 0.25 RNI. We postulate that is easier for agents to overfit on the particular unique IDs used, since they are deterministically assigned. On the other hand, using RNI encourages the agents to learn policies which respect the permutation invariance between agents since agents will receive different random observation augmentations each time step.
For completeness, we note that expressivity beyond 1-WL not strictly needed to solve the Box Pushing environment, demonstrated by several baselines achieving a "ratio cleared" score greater than 0.5, meaning they learned to sometimes clear both types boxes. This is because the environ- ment can be solved, albeit inefficiently, by recurrent policies which learn alternate actions between "normal" and "power" moves each time step. Such policies are guaranteed to move the box every time steps.
Figure 4: Training curves for IC3Net and CommNet on the benchmark communication environments
CH
1909

---

Table 5: Mean and 95% confidence interval for Box Pushing across all baselines
Baseline
Metric
Baseline
Unique IDs
0.75 RNI
0.25 RNI
CommNet
Ratio Cleared
0.786 + 0.08
0.829 + 0.08
0.768 = 0.08
0.795 = 0.09
DGN
Ratio Cleared
0.603 0
0.756 + 0.06
0.958 +
0.957 = 0.01
IC3Net
Ratio Cleared
0.49 + 0.15
0.617 0.14
0.34 0.18
0.676 + 0.06
MAGIC
Ratio Cleared
0.958 + 0.04
0.985 0.01
0.975 0.04
0.998 +
TarMAC
Ratio Cleared
0.629 + 0.14
0.578 0.11
0.662 + 0.06
0.679 + 0.06
T-IC3Net
Ratio Cleared
0.558 + 0.13
0.596 + 0.11
0.458 + 0.18
0.643 + 0.15
Table 6: Mean and 95% confidence interval for Drone Scatter across all baselines except DGN, including a purely random agent. Stochastic evaluation
Baseline
Metric
Bascline
Unique IDs
0.75 RNI
CommNet
Pairwise Distance
11.34 + 0.9
12.08 + 1.12
8.687 + 1.4
Steps Taken
11.5
9.767 + 0.32
11.74 1.39
IC3Net
Pairwise Distance
9.108 = 1.45
13.3 + 0.71
10.99 + 0.38
Steps Taken
11.94 0.84
10.13 0.25
11.66
MAGIC
Pairwise Distance
7.693 + 1.47
12.59 +
7
Steps Taken
13.05 + 0.58
11.12 1.05
18.54
TarMAC
Pairwise Distance
+
10.26 +
8
Steps Taken
13.49 0.1
10.7 0.35
12.85 1 0.57
T-IC3Net
Pairwise Distance
8.891 0.27
9.552 1 0.57
Steps Taken
12.28 0.6
10.33 + 0.46
12.22 1 0.82
Random
Pairwise Distance
5.8 + 0.02
Steps Taken
17.39 + 0.04
Symmetry Breaking Results for the Drone Scatter experiments shown in Table and Table 7, for agents with stochastic and greedy evaluation respectively. Across all of them, unique IDs exhibits consistently superior performance than 0.75 RNI and the baseline, since it deterministically breaks the symmetry between agents and allows them to split up easily to solve the environment. In the stochastic case, 0.75 RNI performs similarly the baseline, but is markedly superior to the baseline the greedy case. The comparison to a purely random agent indicates that the models are learning much more effective policies than just moving around at random.
Baseline methods with stochastic evaluation achieve consistently higher pairwise distances than their greedy counterparts, meaning they are learning to split up to find the target. They are capable of this due to a combination of things: stochastic policy, recurrent networks, and agents observing their last actions. Initially, agents cannot differentiate between each other, and all produce the same action distribution. However, the distribution is diverse, then they are expected to produce different actions since they sample randomly from this distribution, which are observed in the next time step. The different observations lead to different hidden states the recurrent networks, effectively changing the observations between agents and allowing them to differentiate between each other. This is not the case for greedy action selection, which common when doing policy evaluation in MARL, where the actions chosen will always be the same.
5 Conclusion
We introduce GDNs, framework for MARL communication, and formally show how it corresponds to the node labelling problem in GNNs. Our theoretical contributions use this observation to demonstrate that existing MARL communication methods relying conventional GNN architectures have provably limited expressivity. Driven by this, we prove how augmenting agent observations with unique IDs random noise yields universally expressive invariant communication in MARL, whilst also providing desirable properties such as being able to perform symmetry-breakeee targeting arbitrary sets of joint actions for identical agents.
Experimentally, we compare these augmentations across different MARL communication baselines that fall within the GDN paradigm, using benchmark communication environments and 2 tasks

---

Table 7: Mean and 95% confidence interval for Drone Scatter across all baselines. Greedy evaluation
Baseline
Metric
Bascline
Unique IDs
0.75 RNI
CommNet
Pairwise Distance
8.849 = 0.63
13.28 + 1.27
8.589 + 1.35
Steps Taken
13.79 = 0.12
9.554 + 0.33
12.62 = 1.19
DGN
Pairwise Distance
3.221 + 0.18
4.427 + 0.67
3.706 + 0.83
Steps Taken
13.36 + 0.15
13.27 0.21
13.46 + 0.14
IC3Net
Pairwise Distance
7.69 + 1.03
14.09 0.54
11 0.86
Steps Taken
13.25:0:4
0.2
11.42 + 0,48
MAGIC
Pairwise Distance
+ 6.61
0.6
7.107 + 1.59
Steps Taken
13.27
11.84
13.61 0.25
TarMAC
Pairwise Distance
3.666:0.22
0.779
8.999 - 0.94
Steps Taken
18.73=0.2
11.01 0.86
12.19 0.82
T-IC3Net
Pairwise Distance
7.28 0.69
13.51 0.98
10.87 = 1.17
Steps Taken
13.96 1 0.26
10.63 + 0.66
11.73 + 0.54
Figure 5: Training curves for IC3Net (top) and CommNet / DGN (bottom) on Box Pushing (left), Drone Scatter with stochastic evaluation (middle), and Drone Scatter with greedy evaluation (right)
balveding
Tacck
designed to separately test expressivity and bymmetry--reaking. Ultimately, we find that, whilst unique IDs smaller RNI augmentations can typically be applied without detriment standard environments, they do not readily provide improved performance either. However, on environments where more complex coordination is required, these augmentations mance. With RNI and unique IDs being best suited to environments requiring increased expressivity ceaametry-breaknng breaking. respectively, it interesting to note that single method emerges which can recommend as the de facto choice for MARL practitioners. This suggests that more complete picture of the relationship between communication expressivity and downstream performance relevant tasks remains an open question for future research. Furthermore, insights into GNN architec- tures can be leveraged in GDNs, which opens many promising avenues for future work in MARL communication.
essential for strong perfor-
and symmetry
10

---

References
[1] Ralph Abboud, Ismail Iaan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 2112-2118, 2021.
[2] Akshat Agarwal, Sumit Kumar, and Katia Sycara. Learning transferable cooperative behavior multi-agent teams. arXiv preprint arXiv: 19t.::109000022,,, 2019.
[3] Albert-Laaszlo Barabasi and Zoltan Oltvai. Network biology: understanding the cell's functional organization. Nature reviews genetics, 5(2):101-113, 2004.
[4] Pablo Barceló, Egor Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan- Pablo Silva. The logical expressiveness of graph neural networks. 8th International Conference on Learning Representations (ICLR 2020), 2020.
[5] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs geodesics, and gauges. arXiv preprint arXiv:2104.0 13478, 2021.
[6] Jacopo Castellini, Frans A Oliehoek, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. 18th International Conference Autonomous Agents and Multiagent Systems, 2019.
[7] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances neural information processing systems, 32, 2019.
[8] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33: 33:10333-10395 2020.
[9] Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. International Conference on Machine Learning, pages 1538-1546. PMLR, 2019.
[10] George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. International Joint Conference on Artificial Intelli- gence, pages 2126-2132, 2020.
[11] Kefan Dong. Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma. On the expressivity of neural networks for deep reinforcement learning. In International Conference on Machine Learning, pages 2627-2637. PMLR, 2020.
[12] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru- Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
[13] David Easley and Jon Kleinberg, Networks, crowds, and markets: Reasoning about highly connected world. Cambridge university press, 2010.
[14] Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agen reinforcement learning. Advances in neural information processing systems, 29, 2016.
[15] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
[16] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419-3430. PMLR, 2020.
[17] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning, pages 1263-1272. PMLR, 2017.

---

[18] Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi- control using deep reinforcement learning. In International conference on autonomous agents and multiagent systems, pages 66-83. Springer, 2017.
[19] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[20] Todd Hester, Matej Vecerik, Olivier Pietquin, Marc Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. Deep q-learning from demonstrations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[21] Guangzheng Hu, Yuanheng Zhu, Dongbin Zhao, Mengehen Zhao, and Jianye Hao. Event- triggered multi-agent reinforcement learning with communication under limited-bandwidth bandwidth constraint. arXiv preprint arXiv:2010.04978, 2020.
[22] Hengyuan Hu and Jakob N Foerster. Simplified action decoder for deep multi-agent reinforce- ment learning. 8th International Conference on Learning Representations (ICLR), 2020.
[23] Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent coopera- tion. Advances in neural information processing systems, 31, 2018.
[24] Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement learning. International Conference on Learning Representations, 2020.
[25] Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. Learning schedule communication in multi-agent reinforcement learning. International Conference on Learning Representutions, 2019.
[26] Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. Covari- ant compositional networks for learning graphs. arXiv preprint arXiv: 044, 2018.
[27] Sheng Li, Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. Deep implicit coordination graphs for multi-agent reinforcement learning. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021.
[28] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 153-163. Elsevier, 1994.
[29] Yong Liu, Weixun Wang, Yujing Hu, Jianye Hao, Xingguo Chen, and Yang Gao. Multi-agent game abstraction via graph attention neural network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7211-7215 2020.
[30] Andreas Loukas. What graph neural networks cannot learn: depth vs width. International Conference on Learning Representations (ICLR), 2020.
[31] Andreas Loukas. How hard is to distinguish graphs with graph neural networks? Advances in neural information processing systems, 33:3465-344 3476, 2020.
[32] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competttve environments. Advances in neural information processing systems, 30, 2017.
[33] Aleksandra Malysheva, Tegg Tackyong Sung, Chac-Bong Sohn, Daniel Kudenko, and Aleksei Shpilman. Deep multi-agent reinforcement learning with relevance graphs. arXiv preprint /....25511.155: 2018.
[34] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[35] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint arXiv:21 122.02211. 2021.
12

---

[36] Ryan L Murphy, Balasubramanian Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pooling: Learning deep commutation-invaiiinn functions for variable-sin size imputs. International Conference Learning Representations (ICIR), 2019.
[37] Yaru Niu, Rohan Paleja, and Matthew Gombolay. Multi-agent graph-attention communication and teaming. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pages 964-973, 2021.
[38] Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: 190500950000 2019.
[39] Frans A Oliehoek. Decentralized pomdps. In Reinforcement Learning, pages 471-503, Springer, 2012.
[40] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. ICLR, 2020.
[41] Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V Albrecht. Bench- marking multi-agen deep reinforcement learning algorithms in cooperative tasks. Advances in Neural Information Processing Systems Track on Dalasets and Benchmarks, 2021.
[42] Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[43] Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang. Haitao Long, and Jun Wang. Multiagent vidirectionally-coordiim coordinated nets: Emergence of human-level coordination in learning to play starcraft combat games. arXiv preprint arXiv: 10069, 2017.
[44] Chao Qu, Hui Li, Chang Liu, Junwu Xiong, James Zhang, Wei Chu, Weiqiang Wang, Yuan Qi, and Le Song. Intention propagation for multi-agent reinforcement learning. arXiv preprint arXiv:2004.08888 2020.
[45] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4295-4304,
PMLR, 2018.
[46] Ifrah Saced, Andrew C Cullen, Sarah Erfani, and Tansu Alpean. Domain-aware multiagent reinforcement learning in navigation. In 2021 International Joint Conference on Neural Networks (IJCNN), pages 1 1-8. IEEE, 2021.
[47] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 333-341. SIAM, 2021.
[48] Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3693-3702, 2017.
[49] Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when to communicate at scale in multiagent cooperative and competitive tasks. ICLR, 2019.
[50] Kaushik Subramanian, Charles L Isbell Jr. and Andrea L Thomaz. Exploration from demonstra- tion for interactive reinforcement learning. In Proceedings of the 2016 international conference on autonomous agents & multiagent systems, pages 447 2016.
[51] Sainbayar Sukhbaatar, Rob Fergus, al. Learning multiagent communication with backpropa- gation. Advances in neural information processing systems, 29:2244-2252, 2016.
[52] Chuxiong Sun, Bo Wu, Rui Wang, Xiaohui Hu, Xiaoya Yang, and Cong Cong. Intrinsic motivated multi-agent communication. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pages 1668-1670, 2021.
13

---

[53] Ardi Tampuu, Tambet Matüsen, Dorian Kodelja, llya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent cooperation and competition with deep reinforcement learning. PloS one, 12(4))e0173395, 2017.
[54] Justin K Terry, Nathaniel Grammel, Ananth Hari, Luis Santos, and Benjamin Black. Revisiting parameter sharing in multi-agent deep reinforcement learning. arXiv preprint arXiv:2005. 1300000533362 13625, 2020.
[55] Michel Tokic. Adaptive e-greedy exploration in reinforcement learning based on value differ- ences. In Annual Conference on Artificial Intelligence, pages 203-210. Springer, 2010.
[56] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations (ICLR), 2018.
[57] Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passingg Advances in Neural Information Processing Systems, 13:14143-14155 2020.
[58] Ziyu Wang. Victor Bapst, Nicolas Heess, Volodymyr Mnih, Remi Munos, Koray Kavukcuoglu, and Nando de Freitas. Sample efficient actor-critic with experience replay. International Conference on Learning Representations (ICLR), 2017.
[59] Pascal Weber, Daniel Wälchli, Mustafa Zeqiri, and Petros Koumoutsakos. Remember and forget experience replay for multi-agent reinforcement learning. arXiv preprint arXiv:2203.133: 2022.
[60] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 129):12-16, 1968.
[61] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations (ICLR). 2019.
[62] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5571-5580. PMLR, 2018.
[63] Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955, 2021.
[64] Sai Qian Zhang, Qi Zhang, and Jieyu Lin. Efficient communication multi-agent reinforcement learning via variance based control. Advances in Neural Information Processing Systems, 32, 2019.
[65] Sai Qian Zhang, Qi Zhang, and Jieyu Lin. Succinct and robust multi-agent communication with temporal message control. Advances in Neural Information Processing Systems, 33: 17271-17282, 2020.
[66] Jian Zhao, Mingyu Yang, Xunhan Hu, Wengang Zhou, and Houqiang Li. Dqmix: A distribu- tional perspective on multi-agent reinforcement learning. arXiv preprint arXi::2202.10134 2022.
[67] Changxi Zhu, Mehdi Dastani, and Shihan Wang. A survey of multi-agent reinforcement learning with communication. arXiv preprint
2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
14

---

(b) Did you describe the limitations of your work? [Yes] The theoretical assumptions are stated concretely in Section 3. The limitation of our empirical analysis not providing complete picture relating expressivity to performance on MARI. environments is clearly stated the abstract and introduction.
(c) Did you discuss any potential negative societal impacts your work? [N/A] We identified no negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) Assumptions are stated in Section 3 and Appendix B.
(b) Did you include complete proofs of all theoretical results? [Yes] Full proofs for all of our theoretical results are provided in Appendix B.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or a URL)? [Yes] Code, environments, and instructions for reproducibility are included in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All training details are stated in Section 4.1 and Appendix C.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] 95% CI error bars are reported for all results in Section
4.2 and Appendix C.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] The above details are provided in Appendix D.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] [24, 37]
(b) Did you mention the license of the assets? [Yes] See Appendix C.I.
(c) Did you include any new assets either in the supplemental material as URL? [Yes] New environments and code provided in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "ru_MwuRprS", "reviewer": "Reviewer_Kpp5", "summary": "The paper proposes to represent the problem of learning communication for multi-agent systems RL using Graph neural network representations.  In addition to the formalization, the paper explores the use of 2 techniques from the GNN literature: random noise, and unique node IDs, towards better expressivity in MARL.", "questions": "- You propose 3 desideratas for MARL communication (l.139-141):  In what way do the 2 proposed techniques (random noise and unique IDs) help achieve each of these?\n- Much of the motivation seems to be focused on expressivity of the graph (with the goal of “universal expressivity”).  However I would think it’s as important (or more) for that level of expressivity to be efficiently learnable (i.e. learnable in a relatively small number of samples).  Can you explain your view on efficient learnability in the context of this work?  And what are the properties of the proposed methods in this dimension?  You point out (l.184) that many samples may be needed for unique node IDs; is this the case in your results?\n- Your results are based on “value of a metric for a run to be the best value achieved during training” (l.246).  While this may be standard in the literature, it seems to obfuscate the question of learning efficiency and stability, which I view as important properties.  Can you include in your results for each technique what was the #training samples at which this best value was reached?   And total #training samples that you ran, in the case that this is not 5000 (as per l.243).  This would help get more nuanced understanding of learning efficiency, and also support some of your claimes, such as “RNI methods typically take longer to converge than the baseline and unique IDs” (l.269-270), and “unique IDs tend to yield less stable solutions” (l.286-287).\n", "limitations": "- The authors provide reasonable discussion of the technique limitations of their work, but I would like more detail on the empirical results, as per questions above.\n- The authors do not raise ethical or social aspects of the work.  I don’t see any major ethical concerns related to this work.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(+) The idea of exploring the GNN paradigm for learning communication protocols for MARL is intriguing, and brings some interesting new perspective on the problem.  There is some interest in evaluating the effectiveness of techniques such as random noise and unique IDs in the MARL setting.\n(+) The paper has good coverage of related work.\n(+) The paper includes a good number of baselines and domains in the empirical results.\n \n(-) In terms of clarity the paper is at times hard for a reader with more RL expertise, but less GNN expertise, to fully understand. E.g. 1-WL graph colouring, which appears to be a key concept, is defined very briefly.  What is \\alpha in your definition of graph (l.84)?\n(-) The specific techniques used, namely random noise and unique node IDs, are not particularly insightful.  They seem to bring expressivity, but perhaps at the expense of learnability (more on this below).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "oslt6Bl9tXy", "reviewer": "Reviewer_89rL", "summary": "This paper attempts to improve communication in multi-agent systems by drawing from graph neural network techniques—they consider agents as nodes in a graph that allows techniques such as node labeling to apply in this setting. They introduce two augmentations to GNNs i.e., adding randomisation into node initialisation and a unique identifier method to differentiate agent ids in their observations,, and show how these algorithms allow more expressive communication. They evaluate this on standard benchmarks (3 different environments) and show that this improves performance in instances of symmetry breaking, but results in policies that are less than optimal in others.\n", "questions": "1. In line 23: why should the order of messages not matter? Even in some of the newer symbolic emergent communication settings, the ordering of distinct tokens matters in terms of comprehension of the message, and especially when moving to natural language, the history of messages/ordering of context makes a large difference to the meaning of the input. I understand that this paper does not deal with natural language, but it would be good to add to line 23 to explain why ordering should not matter, to clarify the distinction between permutation invariance in this setting, as opposed to other settings with richer language, where this should not hold.\n2. Do you have insights on when the RNI vs. Unique ID should/shouldn’t yield improvements for different models/environments? Based on the results tables there seems to be clear difference in improvements of these two (they seem to work / not work symmetrically) and it would be helpful to try to pick those results apart to understand why this happens, to give us insight into the underlying working of these augmentations to the GNNs.\n", "limitations": "It would be good to have a larger discussion on when these GNN (with augmentation) methods should not be expected to yield better performance, since that’s helpful to our understanding of these newer methods. Overall I like this paper a lot, I think I would just like to understand it more!\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper is well written and clearly explained—nearly every question I had was answered immediately and was easy to follow.\n2. They introduce a nice analogy between MARL communication methods and graph neural networks, where agents form the nodes in the graph (labeled with agent observations) and communication occur along the edges.\n3. For the two augmentations to the GNNS that they propose, they clearly state out the procedure as well as prove why this should work.\n4. They evaluate these augmentations empirically, in comparison to a baselines on several different standard MARL environments and show that both augmentations yield improved performance over baselines, for different types of models that they augment.\n\nWeaknesses:\n\n1. I like that there are definite gains in performance on adding the two augmentations over baselines, but I’m wondering if the gains might only be prevalent in the simplistic MARL environments used here? Do the authors have insights on the complexities of the different environments and whether some augmentations work better/worse for the different types of environments?\n2. E.g., specifically for the unique node identifier augmentation, I’m curious to hear the authors thoughts on how this might impact performance if the agents are more diverse in terms of the attributes/skills/inventory items they possess (e.g., see environments like craftworld), and one unique identifier might not be enough information to be useful?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fIX7FyNJ4v", "reviewer": "Reviewer_yud9", "summary": "This work tackles the challenge of enabling GNNs to learn richer communication protocols for MARL. To this end, the authors initially formalise previous GNN-based approaches to learn communication protocols in MARL as a node prediction problem. The authors subsequently propose RNI and CLIP, two input preprocessing methods that improve the functional expressivity of previous GNN-based MARL approaches. The authors provide theoretical analysis to prove that combining GNNs with RNI/CLIP ensures the existence of GNNs capable of learning communication protocols that require (i) symmetry breaking and (ii) functional expressiveness beyond 1-WL. Empirical evaluation of the returns from combining previous GNN-based MARL approaches and RNI/CLIP shows the proposed approach produces improved performance in environments requiring symmetry breaking and functional expressiveness beyond 1-WL.", "questions": "**Questions**\n\n1. Are there any interesting insights that can be obtained from the messages passed by agents equipped with RNI/CLIP (particularly in terms of symmetry-breaking)?\n2. What are the possible solutions to improve RNI's slow convergence in environments not requiring symmetry breaking? \n\n**Suggestions**\n1. Despite the theoretical analysis on RNI/CLIP being useful, I believe most of the space allocated to this is better served for (i) demonstrating the convergence/learning progress of RNI/CLIP and (ii) showing RNI/CLIP learns useful messages for symmetry breaking or going beyond 1-WL expressivity. After all, these theoretical guarantees are mostly limited to only guaranteeing the existence of GNNs that can approximate the optimal communication protocol.\n\n2. Although helping strengthen the claims made in this work, the wide-range of evaluated communication learning methods can be reduced to only include fewer algorithms to make the presented results more compact. Additional comparisons of RNI/CLIPs performance for other algorithms may subsequently appear in the Appendix.", "limitations": "The authors have adequately highlighted the limitations of their work through their experiments and the resulting analysis. In terms of societal impact, I do not think that this work requires additional information regarding its negative societal impact since its application is still rather limited to simple MARL environments. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**\n\n**1. (Minor weakness) The proposed approach is incremental relative to previous works.**\n\nDespite the novelty of the proposed approaches' application to learning communication protocols in MARL, these techniques have previously been proposed for other prediction problems, as alluded to by the authors in Lines 144 and 175. Line 155 also indicates that some theoretical contributions are minor extensions of theorems proven in previous work. Nevertheless, this weakness is outweighed by the remaining theoretical and empirical studies that the authors have conducted to show that the proposed approach can learn communication protocols requiring symmetry breaking and going beyond 1-WL expressivity in MARL.\n\n**Quality**\n\n**1. (Major Strength) Result reproducibility.**\n \nThe authors have provided adequate descriptions of the model architecture and hyperparameters, environments, and experiment protocols that ensure their results are reproducible.\n\n**2. (Major Strength) The experiment design adequately demonstrates the claims made in by the authors.**\n\nThe environment and baseline selection empirically highlight the claims of this work regarding RNI/CLIP's ability to learn improved communication protocols in environments requiring (i) symmetry-breaking or (ii) function estimators beyond the 1-WL expressivity. Note that the evaluation in Predator-Prey and Easy Traffic Junction also highlights the potential weaknesses of the proposed approach when applied to environments not requiring (i) or (ii). This provides valuable insights that can inform the readers when applying the proposed technique to other environments.\n\n**3. (Minor weakness) Missing theoretical/empirical analysis to strengthen the claims of this work further.**\n\nDespite ensuring the existence of a learned GNN that can help with (i) symmetry-breaking, I believe the theoretical analysis on the ability of RL-based optimisation techniques to learn such GNNs is lacking. Nonetheless, the empirical demonstration of RNI/CLIP's performance indicates that this is not a significant issue for the evaluated environments. Furthermore, since the work mentioned convergence as a potential issue with a few proposed approaches, it is crucial to report the learning curve from the experiments in the experiment section (although this is provided in the Appendix).\n\nThat aside, it will also be interesting to analyze messages that RNI/CLIP passes in environments requiring (i) or (ii). Specifically, in terms of proving the usefulness of RNI/CLIP in addressing (i), inspecting the passed representation may highlight how they aid the symmetry-breaking process.\n\n**Clarity**\n\n**1. (Strength) The paper is well-written.**\n\nThe document is generally well-written. The method description and related theoretical analysis were clear and concise. Furthermore, the experiment section clearly states the intention behind the design/selection of various baseline/environments for demonstrating the central claims of the work.\n\n**Significance**\n\n**1. (Strength) The work provides significant results for people working in applying GNNs for learning communication protocols for MARL.**\n\nDespite the proposed approach mainly being incremental compared to previous work, the theoretical and empirical analysis provides findings useful for people working in communication for MARL. The way the authors highlighted the potential limitations of the work is specifically helpful for future research.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8ZO0JO9dJ_q", "reviewer": "Reviewer_zdMz", "summary": "This work studies the expressivity of GNN when used as a communication function within multi-agent reinforcement learning systems (MARL) and defines a formal framework called graph decision networks (GDN) and observation extension procedures to improve expressivity.", "questions": "Please read above\n\n* In section 2 background the MARL introduction assumes a lot of previous knowledge from the reader, I understand that there is limited space, but authors could elaborate a bit on parameter sharing.  \n\n\nI believe this is specially important for stabilising a \"Universally Expressive\" framework. As the authors point out they are not the first to use parameter sharing with the end of stabilise training, but it is an assumption that is not present on most of SOTA MARL algorithms, e.g. MAPPO, IPPO, QMIX, MAVEN....\n\n", "limitations": "Authors do set clearly the limited scope of their review and analysis, although I believe that having parameter sharing in all the empirical evaluation gives an additional limitation of the analysis that could have been avoided,", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Authors provide a sound contribution. First, theoretically with their analysis of communication expressiveness in exiting techniques while introducing their framework. second with an extensive empirical evaluation with multiple baselines and environments. \n\nRegarding originality, I believe the paper may be labelled as incremental since the framework and analysis are about augmenting expressivity of existing baselines.\n\nAbout clarity, due to the theoretical nature of the paper it is hard to read. In this regard I believe that brief paragraphs explaining the directions of each section would greatly improve readability. Also at first read is not clear what are the significances of the GDN and what is analysing existing work, some check on that would help.\n\nLast, I believe that the significance of the work is low, and this is my biggest concern with this work. It is concerned about communication in MARL but only with GNNs, I believe authors could do more to highlight the relevance of this study. There are a plethora of works about MARL communication and emergent languages which are not concerned about GNNs. Given the large scope of this conference I believe some comparison with those should be included.  \n\n\nGiven all of this, since I believe that evaluating significance is inevitably a subjective topic, I lean towards acceptance despite having my reservations towards novelty and significance.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept