TACTIC: Task-Aware Sparse Coordination Graphs for Multi-Task Multi-agent Reinforcement Learning

Coordination graphs specify which agents exchange information in cooperative multi-agent reinforcement learning (MARL). Existing sparse-graph methods, however, rely on heuristic, edge-uniform criteria for topology and structurally blind bottlenecks for message bandwidth, and lack a principled way to jointly learn heterogeneous connectivity and allocate differentiated communication capacity. We propose Heterogeneous Information-Bottleneck Coordination Graphs (HIBCG), which couples a group-aligned block-diagonal prior-assigning heterogeneous edge density per group blockwith per-agent message compression on the learned graph. Theoretically, we show that the group-aligned prior is never worse than a flat isotropic prior, that the structural penalty decomposes additively across group blocks, and that minimising the standard TD loss lower-bounds IB relevance without a separate mutual-information estimator. Across nine scenarios in SMACv1, SMACv2, and MAgent Battle (up to 100 agents), HIBCG attains the strongest results on heterogeneous multi-role maps, scales where several baselines fail to converge, and is validated by ablations and theory-aligned diagnostics of the group-aligned prior and dual-path design.