Diversifying Message Aggregation in Multi-Agent Communication Via Normalized Tensor Nuclear Norm Regularization

Yuanzhao Zhai, Kele Xu, Bo Ding, Dawei Feng, Zijian Gao, Huaimin Wang

TL;DR

This paper introduces a novel regularization technique, NTNNR, to encourage diverse message aggregation strategies in multi-agent communication systems. By analyzing the communication graph's adjacency tensor and introducing a normalized tensor nuclear norm, NTNNR helps agents avoid over-reliance on a few "key" agents, leading to improved coordination, faster training, and better overall performance in complex multi-agent tasks.

What Problem Does This Paper Address?

In multi-agent reinforcement learning (MARL), agents often need to communicate to coordinate their actions effectively. Graph Attention Networks (GATs) have emerged as a popular tool for modeling these communication patterns, allowing agents to selectively attend to messages from their peers. However, a significant challenge with GATs is that they can lead to "homogeneous" message aggregation strategies. This means many agents might excessively focus on the same few "important" agents, limiting the diversity of their behaviors and hindering optimal coordination. This homogeneity can severely restrict the agents' ability to explore emergent strategies and achieve complex collaborative goals.

Methods

The core contribution of this paper is the Normalized Tensor Nuclear Norm Regularization (NTNNR). The authors first analyze the adjacency tensor of the communication graph, which captures the attention weights between agents across different "heads" in a GAT. They propose that the normalized tensor rank of this adjacency tensor can serve as a measure of message aggregation diversity. Since optimizing tensor rank is computationally hard, they introduce a novel Normalized Tensor Nuclear Norm (NTNN) as a convex surrogate. This NTNN is then used as a plug-and-play regularizer that can be added to existing GAT-based communication modules in MARL. By minimizing a loss function that includes this NTNN regularizer, the training process is encouraged to produce more diverse attention patterns, thereby promoting varied message aggregation strategies among agents.

Datasets

The paper evaluates its method on three benchmark scenarios:

  • Predator-Prey: A mixed cooperative-competitive environment where multiple predators must coordinate to capture prey, with a specific requirement for multiple predators to be in a prey's vicinity for a successful capture.
  • Traffic Junction: A cooperative scenario involving cars navigating an intersection, requiring communication to avoid collisions.
  • StarCraft II Multi-Agent Challenge (SMAC): A complex benchmark for evaluating MARL agents in real-time strategy games, specifically using the 3s5z and 2s3z maps.

Key Insights and Ideas

  • Homogeneity is a bottleneck: The paper convincingly demonstrates that homogeneous message aggregation in GATs can lead to suboptimal coordination and limited emergent behaviors.
  • Tensor rank as a diversity metric: The novel idea of using the normalized tensor rank of the adjacency tensor to quantify message aggregation diversity is a key conceptual contribution.
  • NTNN as a practical solution: The NTNN provides a tractable, convex relaxation of the tensor rank, making it suitable for use as a regularizer in deep learning frameworks.
  • Plug-and-play effectiveness: NTNNR's ability to be easily integrated with existing GAT-based Comm-MARL methods without requiring significant architectural changes is a major practical advantage.
  • Diversity benefits both cooperative and competitive tasks: The experiments show that encouraging diverse communication strategies improves performance across different types of MARL tasks.

Key Results

  • Improved Training Efficiency and Performance: GAT with NTNNR consistently outperformed vanilla GAT and other baseline methods in terms of average reward and asymptotic performance across the Predator-Prey and Traffic Junction scenarios.
  • Enhanced Coordination: In the Predator-Prey scenario, NTNNR enabled predators to adopt more diverse strategies, leading to better coordination and successful prey capture. Visualizations showed agents exploring the environment rather than all converging on a single prey.
  • Significant Gains on SMAC: When applied to state-of-the-art methods like GA-Comm and DICG-CE-LSTM on SMAC, NTNNR led to substantial improvements in win rates, demonstrating its general applicability.
  • Robustness to Hyperparameters: The method showed acceptable robustness to the scaling hyperparameters ($\beta_1, \beta_2$), with performance remaining strong within a reasonable range.

Limitations and Future Work

The authors acknowledge that in some multi-agent coordination tasks with "core agents" (agents that are critically important for the system's success), overly diverse message aggregation might be unreasonable. In such cases, NTNNR might not yield significant performance improvements.

Future work suggested by the authors includes quantifying the diversity upper bound for multi-agent systems, which could help in understanding when and how much diversity is beneficial.

Summary updated

Abstract

The use of graph attention networks (GAT) in communication-enhanced multi-agent reinforcement learning (Comm-MARL) has become prevalent. While successful, GAT can lead to homogeneity in the strategies of message aggregation, which can severely limit multi-agent coordination. To address this challenge, we study the adjacency tensor of the communication graph. Then we define a new nuclear tensor rank and its convex surrogate, the normalized tensor nuclear norm to measure the homogeneity of message aggregation. Leveraging the norm, we further propose a plug-and-play regularizer on the adjacency tensor, named Normalized Tensor Nuclear Norm Regularization (NTNNR), to actively enrich the diversity of message aggregation during the training stage. NTNNR is agnostic to specific Comm-MARL algorithms and can be flexibly integrated with different graph-attention methods. Empirical results demonstrate that aggregating messages using NTNNR-enhanced GAT can improve the efficiency of the training and achieve higher asymptotic performance than existing message aggregation methods.
BibTeX
@inproceedings{zhai2023diversifying,
  author = {Yuanzhao Zhai and Kele Xu and Bo Ding and Dawei Feng and Zijian Gao and Huaimin Wang},
  title = {{Diversifying Message Aggregation in Multi-Agent Communication Via Normalized Tensor Nuclear Norm Regularization}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  doi = {10.1109/icassp49357.2023.10096468},
}
Figure