Coordination graphs are a central abstraction in cooperative multi-agent reinforcement learning (MARL). However, existing sparse-graph learners lack a theoretically grounded mechanism to determine the existence of edges and the information each edge should carry. Current methods rely on heuristic criteria that do not guarantee the learned topology and lack a principled way to allocate different communication capacities to structurally different agent relationships.
To address this, we propose Heterogeneous Information-Bottleneck Coordination Graphs (HIBCG), which learns a group-aware sparse graph where both edge existence and message capacity are theoretically justified. Utilizing the graph information bottleneck (GIB) as the foundational tool, HIBCG first constructs a group-aligned block-diagonal prior that provides a closed-form criterion for edge retention, determining which edges should exist and at what density per group block. It then controls per-agent feature bandwidth on the resulting topology, compressing messages to retain only task-relevant content.
We prove that the group-aligned prior strictly tightens the variational bound on topology learning, that the objective decomposes per group block enabling differential edge control, and that capacity allocation follows a water-filling principle.
Blogger's Review: The introduction of HIBCG provides a theoretical foundation for enhancing communication efficiency in multi-agent systems, significantly improving collaboration among agents. By effectively controlling edges and compressing information, HIBCG optimizes the flow of information and offers new directions for future MARL research. Its theoretical rigor and practical applicability make it a worthy subject for further study and application.