Abstract
Communication is crucial for solving cooperative Multi-Agent Reinforcement Learning (MARL) tasks in partially observable Markov Decision Processes (POMDPs). 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 are often heuristic and lack 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 recast multi-agent communication as an online clustering problem over local observations, using the return gap bound as a clustering loss. We propose the Return-Gap-Minimization Communication (RGMComm) algorithm, which utilizes a novel Regularized Information Maximization loss function with cosine-distance as the clustering metric. Evaluations show that RGMComm significantly outperforms state-of-the-art baselines, achieving nearly optimal returns with naturally interpretable few-bit messages.
Introduction
In cooperative multi-agent tasks, agents often operate under partial observability, where no single agent has a complete view of the environment state. To coordinate effectively, agents must communicate. However, current communication strategies face a trade-off: continuous communication provides high performance but is resource-intensive and uninterpretable, while existing discrete methods are heuristic and lack theoretical performance guarantees.
This research addresses the fundamental question: Can we mathematically quantify the return lost by using discrete messages instead of full observability, and can we design an algorithm to minimize that loss?
Methods: RGMComm and the Return Gap
The core innovation of RGMComm is treating message generation as an online clustering problem. If different local observations lead to the same optimal team action, they should be grouped into the same discrete message label.
Theoretical Foundation
The authors derive a closed-form upper bound on the return gap—the difference in expected return between a policy with full observability and one using discrete communication. This gap is bounded by $O(\sqrt{\epsilon n Q_{max}})$, where $\epsilon$ represents the average cosine distance between action-value (Q-value) vectors within a message cluster. This theoretical result suggests that minimizing intra-cluster cosine distance directly minimizes the performance loss.
Algorithm Architecture
RGMComm implements this by training a message-generation network $g_n(\cdot)$ alongside standard actor-critic methods like MADDPG. The network is optimized using a Regularized Information Maximization (RIM) loss:
- Cosine-Distance Clustering Loss ($L_{CD}$): Groups observations with similar Q-value structures.
- Mutual Information Loss ($L_{MI}$): Ensures clusters are balanced and the mapping is unambiguous.
Results and Discussion
The researchers evaluated RGMComm on standard Multi-Agent Particle Environment (MAPE) benchmarks, including Predator-Prey and Cooperative Navigation.
Performance and Efficiency
RGMComm consistently outperformed state-of-the-art baselines such as CommNet, TarMAC, and VQ-VIB. Notably, in the Predator-Prey task, RGMComm achieved near-optimal returns using as few as 2 to 4 message labels (1-2 bits). The experimental results validated the theoretical bound: as the number of labels increased (reducing $\epsilon$), the return gap decreased accordingly.
Interpretability and Scalability
A key finding is that cosine distance is a superior metric for MARL clustering compared to Euclidean distance, as the direction of Q-vectors indicates the optimal action distribution. Furthermore, the learned messages are naturally interpretable; for instance, a specific bit might consistently signal proximity to a target. The algorithm also demonstrated robust scalability as the number of agents increased from 2 to 6.
Conclusion
RGMComm provides a theoretically grounded framework for discrete multi-agent communication. By bridging the gap between observability and communication through online clustering, it enables efficient, high-performance, and interpretable coordination. Future work includes automating the selection of message alphabet sizes and testing in more dynamic environments.
Reference: Chen, J., Lan, T., & Joe-Wong, C. (2023). RGMComm: Return Gap Minimization via Discrete Communications in Multi-Agent Reinforcement Learning. arXiv:2308.03358v5.
Summary updated