Sparse Topology-Aware Pairwise Scoring for Large-Scale Multi-Agent Reinforcement Learning

In multi-agent reinforcement learning (MARL), communication enables agents to mitigate partial observability and stochasticity through information sharing, but large-scale systems inherently lead to a rapidly growing number of pairwise interactions. Previous studies often struggle to simultaneously achieve scalability and task adaptivity in large-scale multi-agent communication. To address this challenge, we propose a scalable communication scheme for large-scale MARL, termed $\textit{Sparse tOpology-aware Pairwise Scoring}$ (SOPS). We argue that scalable MARL communication requires decoupling scalability from task-adaptive link allocation. To ensure scalability, we constrain communication to an exponential-graph backbone with a small diameter, which preserves rapid potential information mixing while keeping per-agent candidates logarithmic. On top of this constraint, we learn a task-conditioned probabilistic subgraph distribution via a pairwise scoring network over agent states and edge-type embeddings to allocate sparse links for maximizing return, optimized end-to-end through differentiable Gumbel-Sigmoid reparameterization. Evaluation results show that SOPS significantly outperforms existing state-of-the-art methods across cooperative benchmarks of diverse scales and exhibits robust zero-shot transfer capabilities.

When many AI agents need to work together — for example, coordinating a fleet of robots or managing large-scale infrastructure — they must communicate to share information. However, as the number of agents grows, having every agent talk to every other agent becomes prohibitively expensive, much like trying to hold a conversation in a room with hundreds of people all speaking at once. We designed a communication scheme called SOPS that organizes agents into a structured network where each agent only needs to talk to a small number of carefully chosen partners. The network is designed so that information can still spread to all agents within just a few hops, similar to the "six degrees of separation" concept in social networks. On top of this structure, agents learn to dynamically select the most useful communication links based on the current task. Our approach enables large teams of agents to coordinate effectively while using far less communication bandwidth, and agents trained on small teams can transfer their learned strategies to much larger teams without retraining.