Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning
This work provides a principled solution to the problem of learning sparse coordination graphs in MARL, addressing the lack of theoretical guarantees in existing heuristic methods.
HIBCG introduces a theoretically grounded method for learning sparse coordination graphs in multi-agent reinforcement learning, using graph information bottleneck to justify edge existence and message capacity. It achieves differential edge control and capacity allocation via a water-filling principle, with formal guarantees on topology learning.
Coordination graphs are a central abstraction in cooperative multi-agent reinforcement learning (MARL), yet existing sparse-graph learners lack a theoretically grounded mechanism to decide which edges should exist and how much information each edge should carry. Current methods rely on heuristic criteria that offer no formal guarantee on the learned topology, and no 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 in which both edge existence and message capacity are theoretically justified. With the graph information bottleneck (GIB) serving as the underlying 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 -- and 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.