DEEP REINFORCEMENT LEARNING WITH RELATIONAL INDUCTIVE BIASES
We introduce an approach for augmenting model-free deep reinforcement learning agents with a mechanism for relational reasoning over structured representations, which improves performance, learning efficiency, generalization, and interpretability. Our architecture encodes an image as a set of vectors, and applies an iterative message-passing procedure to discover and reason about relevant entities and relations in a scene. In six of seven StarCraft II Learning Environment mini-games, our agent achieved state-of-the-art performance, and surpassed human grandmasterlevel on four. In a novel navigation and planning task, our agent's performance and learning efficiency far exceeded non-relational baselines, it was able to generalize to more complex scenes than it had experienced during training. Moreover, when we examined its learned internal representations, they reflected important structure about the problem and the agent's intentions. The main contribution of this work is to introduce techniques for representing and reasoning about states in model-free deep reinforcement learning agents via relational inductive biases. Our experiments show this approach can offer advantages in efficiency, generalization, and interpretability, and can scale up to meet some of the most challenging test environments in modern artificial intelligence.
The authors present a deep reinforcement learning approach that uses a “self-attention”/“transformer”-style model to incorporate a strong relational inductive bias. Experiments are performed on a synthetic “BoxWorld” environment, which is specifically designed (in a compelling way) to emphasize the need for relational reasoning. The experiments on the BoxWorld environment clearly demonstrate the improvement gained by incorporating a relational inductive bias, including compelling results on generalization. Further experimental results are provided on the StarCraft minigames domain. While the results on StarCraft are more equivocal regarding the importance of the relational module—the authors do set a new state of the art and the results are suggestive of the potential utility of relational inductive biases in more general RL settings.
Overall, this is a well-written and compelling paper. The model is well-described, the BoxWorld results are compelling, and the performance on the StarCraft domain is also quite strong. The paper clearly demonstrates the utility of relational inductive biases in reinforcement learning.
In terms of areas for potential improvement:
1) With regards to framing, a naive reader would probably get the impression that this is the first-ever work to consider a relational inductive bias in deep RL, which is not the case, as the NerveNet paper (Wang et al., 2018) also considers using a graph neural network for deep RL. There are clear differences between this work and NerveNet—most prominently, NerveNet only uses a relational inductive bias for the policy network by assuming that a graph-structured representation is known a priori for the agent. Nonetheless, NerveNet does also incorporate a relational inductive bias for deep RL and shows how this can lead to better generalization. Thus, this paper would be improved by properly positioning itself w.r.t. NerveNet and highlighting how it is different. 
2) As with other work using non-local neural networks (or fully-connected GNNs), there is the potential issue of scalability due to the need to consider all input pairs. A discussion of this issue would be very useful, as it is not clear how this approach could scale to domains with very large input spaces. 
3) Some details on the StarCraft experiments could be made more rigorous and quantitative. In particular, the following instances could benefit from more experimental details and/or clarifications: 
Figure 6: The performance of the control model and relational model seem very close. Any quantitative insight on this performance gap would improve the paper. For instance, is the gap between these two models significantly larger than the average gap between runs over two different random seeds? It would greatly strengthen the paper to clarify that quantitive aspect. 
Page 8: ”We observed that—at least for medium sized networks—some interesting generalization capabilities emerge, with the best seeds of the relational agent achieving better generalization scores in the test scenario” — While there is additional info in the appendix, without quantitative framing this statement is hard to appreciate. I would suggest more quantitive detail and rigorous statistical tests, e.g.,  something like “When examining the best 10 out of ??? seeds, the relational model achieved an average performance increase of ???% compared to the control model (p=???, Wilcoxon signed-rank test). However, when examining all seeds ???? was the case.” 
Page 8: “while the former adopted a "land sweep strategy", controlling many units as a group to cover the space, the latter managed to independently control several units simultaneously, suggesting a finer grained understanding of the game dynamics.” This is a great insight, and the paper would be greatly strengthened by some quantitive evidence to back it up (if possible). For instance, you could compute the average percentage of agents that are doing the same action at any point in time or within some distance from each other, etc. Adding these kinds of quantitative statistics to back up these qualitative insights would both strengthen the argument, while also making it more explicit how you are coming to these qualitative judgements. 
Figure 8 caption: “Colored bars indicate mean score of the ten best seeds” — how bad is the drop to the n-10 non-best seeds? And how many seeds where used in total?
Page 13: “following Table 4 hyperparameter settings and 3 seeds” — if three seeds are used in these experiments, how are 10+?? seeds used for the generalization experiments? The main text implies that the same models for the “Collect Mineral Shards” were re-used, but it appears that many more models with different seeds were trained specifically for the generalization experiment. This should be clarified. Alternatively, it is possible that “seeds” refers to both random seeds and hyperparameter combinations, and it would improve the paper to clarify this. It is possible that I missed something here, but I think it highlights the need for further clarification.