# Heterogeneous Information-Bottleneck Coordination Graphs for Multi-Agent Reinforcement Learning

arXiv: https://arxiv.org/abs/2605.17393 · HTML: https://mlsanity.com/paper/2605.17393/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 44 of its 62 references that are in the map.
- First posted on arXiv 17 May 2026.

## Builds on (most cited first, 30 of 44)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Learning Multiagent Communication with Backpropagation](https://mlsanity.com/paper/1605.07736/) (2016)
- [Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks](https://mlsanity.com/paper/2006.07869/) (2020)
- [TarMAC: Targeted Multi-Agent Communication](https://mlsanity.com/paper/1810.11187/) (2018)
- [Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.11251/) (2021)
- [Learning Attentional Communication for Multi-Agent Cooperation](https://mlsanity.com/paper/1805.07733/) (2018)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [Graph Convolutional Reinforcement Learning](https://mlsanity.com/paper/1810.09202/) (2018)
- [ROMA: Multi-Agent Reinforcement Learning with Emergent Roles](https://mlsanity.com/paper/2003.08039/) (2020)
- [SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2212.07489/) (2022)
- [A Survey of Multi-Agent Deep Reinforcement Learning with Communication](https://mlsanity.com/paper/2203.08975/) (2022)
- [Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneck](https://mlsanity.com/paper/1910.12911/) (2019)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Learning to Schedule Communication in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1902.01554/) (2019)
- [Learning Nearly Decomposable Value Functions Via Communication Minimization](https://mlsanity.com/paper/1910.05366/) (2019)
- [Multi-Agent Game Abstraction via Graph Attention Neural Network](https://mlsanity.com/paper/1911.10715/) (2019)
- [MAgent: A Many-Agent Reinforcement Learning Platform for Artificial Collective Intelligence](https://mlsanity.com/paper/1712.00600/) (2017)
- [Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2006.11438/) (2020)
- [Learning Multi-Agent Communication from Graph Modeling Perspective](https://mlsanity.com/paper/2405.08550/) (2024)
- [Hierarchical Cooperative Multi-Agent Reinforcement Learning with Skill Discovery](https://mlsanity.com/paper/1912.03558/) (2019)
- [Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.04222/) (2020)
- [Learning Agent Communication under Limited Bandwidth by Message Pruning](https://mlsanity.com/paper/1912.05304/) (2019)
- [Context-Aware Sparse Deep Coordination Graphs](https://mlsanity.com/paper/2106.02886/) (2021)
- [Adapting Multi-modal Large Language Model to Concept Drift From Pre-training Onwards](https://mlsanity.com/paper/2405.13459/) (2024)
- [Group-Aware Coordination Graph for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10976/) (2024)
- [Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.10728/) (2024)

## Abstract (arXiv)

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.