ACORN: Acyclic Coordination with Reachability Network to Reduce Communication Redundancy in Multi-Agent Systems

Effective communication is essential in multi-agent reinforcement learning (MARL) for coordinating actions and maximizing collective rewards. Two common approaches for establishing communication are Graph Neural Networks (GNNs) and Transformers. Both methods introduce communication redundancy in complex scenarios. GNN-based methods model agent relationships through entire graph structures, leading to increased computational time. Transformers also increase computations due to self-attention calculations at each node. In this study, the ACORN (Acyclic Coordination with Reachability Networks) framework was introduced, utilizing acyclic coordination combined with a reachability-based attention mechanism. The most relevant nodes and connections in the GNN graph are used for self-attention calculations. Time complexity is reduced to 𝑂 (|𝑉 | × 𝑛𝑘 × 𝑑), which is significantly better than the 𝑂 (|𝑉 | 2 𝑑) complexity of standard Transformers. Acyclicity is ensured through Auto-Regressive Policy Learning and Sequence-Based Critic Learning. Experiments demonstrate that ACORN outperforms state-of-the-art methods, achieving an average improvement of 11% over MAT in challenging SMACV2 tasks and a 17% improvement within the same training time and steps.