Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strengths:
1. This paper is well written and clearly explained—nearly every question I had was answered immediately and was easy to follow.
2. 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.
3. For the two augmentations to the GNNS that they propose, they clearly state out the procedure as well as prove why this should work.
4. 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.

Weaknesses:

1. 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?
2. 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?

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

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!
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: **Originality**

**1. (Minor weakness) The proposed approach is incremental relative to previous works.**

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

**Quality**

**1. (Major Strength) Result reproducibility.**
 
The authors have provided adequate descriptions of the model architecture and hyperparameters, environments, and experiment protocols that ensure their results are reproducible.

**2. (Major Strength) The experiment design adequately demonstrates the claims made in by the authors.**

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

**3. (Minor weakness) Missing theoretical/empirical analysis to strengthen the claims of this work further.**

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

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

**Clarity**

**1. (Strength) The paper is well-written.**

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

**Significance**

**1. (Strength) The work provides significant results for people working in applying GNNs for learning communication protocols for MARL.**

Despite 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.
questions: **Questions**

1. 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)?
2. What are the possible solutions to improve RNI's slow convergence in environments not requiring symmetry breaking? 

**Suggestions**
1. 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.

2. 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.
(+) The paper has good coverage of related work.
(+) The paper includes a good number of baselines and domains in the empirical results.
 
(-) 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)?
(-) 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).

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

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.
- The authors do not raise ethical or social aspects of the work.  I don’t see any major ethical concerns related to this work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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. 

Regarding originality, I believe the paper may be labelled as incremental since the framework and analysis are about augmenting expressivity of existing baselines.

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

Last, 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.  


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

questions: Please read above

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


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


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,
review_title: null

Meta-review: metareview: Reviewers found the paper's connections between MARL and GNNs interesting and well-written, and the experiments convincing. Given the unanimous support, I recommend acceptance. That said, I encourage the authors to integrate reviewer feedback, including trying to move some of the details and plots requested to the main text.
confidence: Less certain
Decision: Accept