RGMComm: Return Gap Minimization via Discrete Communications in Multi-Agent Reinforcement Learning

Jingdi Chen, Lü Tian, Joe-Wong, Carlee

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 RGMComm architecture integrates a clustering module $g_1(\cdot)$ that generates discrete messages $m_1$ to minimize the return gap via a specialized loss function.

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).

Mean episode reward comparison on the Predator-Prey task. RGMComm with 4 labels (2 bits) significantly outperforms both continuous and discrete baselines.

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

Abstract

Communication is crucial for solving cooperative Multi-Agent Reinforcement Learning tasks in partially observable Markov Decision Processes. Existing works often rely on black-box methods to encode local information/features into messages shared with other agents, leading to the generation of continuous messages with high communication overhead and poor interpretability. Prior attempts at discrete communication methods generate one-hot vectors trained as part of agents' actions and use the Gumbel softmax operation for calculating message gradients, which are all heuristic designs that do not provide any quantitative guarantees on the expected return. 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. This result enables us to recast multi-agent communication into a novel online clustering problem over the local observations at each agent, with messages as cluster labels and the upper bound on the return gap as clustering loss. To minimize the return gap, we propose the Return-Gap-Minimization Communication (RGMComm) algorithm, which is a surprisingly simple design of discrete message generation functions and is integrated with reinforcement learning through the utilization of a novel Regularized Information Maximization loss function, which incorporates cosine-distance as the clustering metric. Evaluations show that RGMComm significantly outperforms state-of-the-art multi-agent communication baselines and can achieve nearly optimal returns with few-bit messages that are naturally interpretable.
BibTeX
@inproceedings{chen2024rgmcomm,
  author = {Jingdi Chen and Lü Tian and Joe-Wong, Carlee},
  title = {{RGMComm: Return Gap Minimization via Discrete Communications in Multi-Agent Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i16.29680},
}
Figure