Abstract
Communication is crucial for solving cooperative Multi-Agent Reinforcement Learning (MARL) tasks in partially observable Markov Decision Processes. Existing works often rely on black-box methods to encode local information into continuous messages, leading to high overhead and poor interpretability. Prior discrete methods often use heuristic designs without quantitative guarantees. This paper establishes an upper bound on the return gap between an ideal policy with full observability and an optimal partially observable policy with discrete communication. We propose Return-Gap-Minimization Communication (RGMComm), which recasts communication as an online clustering problem over local observations. By minimizing a novel Regularized Information Maximization (RIM) loss based on cosine distance, RGMComm achieves near-optimal returns with low-bandwidth, interpretable messages.
Introduction
In cooperative Multi-Agent Reinforcement Learning (MARL), agents typically operate within Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs). Because each agent only perceives a subset of the environment, communication is essential for coordination. However, existing communication protocols face significant challenges. Continuous communication methods, while expressive, often act as uninterpretable "black boxes" and consume excessive bandwidth. Conversely, discrete communication methods, which are more practical for real-world constraints, often rely on heuristic techniques like the Gumbel-softmax trick to maintain differentiability. Most importantly, these methods lack theoretical guarantees regarding the performance loss—the "return gap"—incurred by partial observability.
RGMComm addresses these issues by providing a theoretically grounded framework for discrete communication. It minimizes the return gap by treating message generation as a clustering task, ensuring that agents share only the most critical information needed to approximate full observability.
Methodology: Communication as Online Clustering
The core innovation of RGMComm is the transformation of communication into an online clustering problem. The authors mathematically demonstrate that the return gap is bounded by the average cosine distance between the action-value (Q-value) vectors of observations that are assigned the same message.
Theoretical Foundation
If two distinct local observations lead to the same optimal action, they should ideally be grouped together. RGMComm clusters an agent's local observations such that the cluster label serves as the discrete message broadcast to others. This approach ensures that the "meaning" of a message is tied directly to the underlying value function.
RGMComm Architecture and RIM Loss
To implement this, RGMComm utilizes a Regularized Information Maximization (RIM) loss function. This loss minimizes the cosine distance between Q-vectors within the same cluster, directly targeting the theoretical return gap. Simultaneously, it maximizes mutual information to prevent degenerate solutions where all observations are mapped to a single message or clusters are unevenly distributed.
The clustering module is trained alongside standard actor-critic MARL algorithms by sampling action-values from a replay buffer, allowing it to scale to continuous state-space environments.
Experiments and Results
The performance of RGMComm was evaluated using the Multi-Agent Particle Environment (MPE), including tasks such as Predator-Prey and Cooperative Navigation.
Performance Comparison
RGMComm was compared against several state-of-the-art baselines, including continuous methods (CommNet, SARNet) and discrete methods (VQ-VIB, IC3Net).
As shown in the results, RGMComm consistently achieves higher rewards while using significantly less bandwidth. In some scenarios, a 1-bit or 2-bit message was sufficient to reach near-optimal performance. Remarkably, in Cooperative Navigation, RGMComm even outperformed policies with full observability, likely because the discrete communication acted as a filter for environmental noise.
Discussion and Conclusion
RGMComm represents a significant step forward in MARL communication. By linking the return gap to vector distances, it provides a principled way to design discrete communication protocols. The resulting messages are not only efficient but also naturally interpretable, as they correspond to specific clusters of the value function.
While the current theory is rooted in discrete observation spaces, the empirical success in continuous environments suggests broad applicability. Future work will focus on scaling RGMComm to even more complex, large-scale multi-agent systems.
Summary updated