Minimizing Return Gaps with Discrete Communications in Decentralized POMDP

Jingdi Chen, Tian Lan

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:

  1. Cosine-Distance Clustering Loss ($L_{CD}$): Groups observations with similar Q-value structures.
  2. Mutual Information Loss ($L_{MI}$): Ensures clusters are balanced and the mapping is unambiguous.
RGMComm architecture showing the integration of message generation with the RL policy and the specific loss function.

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.

Comparison of RGMComm against several state-of-the-art baselines in the Predator-Prey environment.

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

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{chen2024minimizing,
  author = {Jingdi Chen and Tian Lan},
  title = {{Minimizing Return Gaps with Discrete Communications in Decentralized POMDP}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i16.29680},
}
Figure