Scalable Multi-Agent Reinforcement Learning over Hypergraphic Environment

Scalability is a fundamental challenge in cooperative multi-agent reinforcement learning (MARL) for large-scale networked systems. Existing graph-based methods address this issue by sparsifying global coordination into pairwise edges and local neighborhoods, but always overlook the intrinsic overlapping higher-order interdependencies inherent in complex systems. In this paper, we propose HygRL, a novel MARL framework for networked systems with hypergraphic structure. We utilize hypergraphs to model the evolution of the multi-agent environment, where each hyperedge represents a group of interdependent agents. HygRL decomposes the global task into hyperedge-localized sub-tasks trained in parallel, while a mean policy aggregation resolves conflicts among overlapping hyperedges during decentralized execution. In particular, we theoretically derive the first performance error bound for hypergraph decomposition, quantifying the effects of approximate decomposition and aggregated policy sampling on training performance. As a special case, when the hypergraph degenerates to a single hyperedge, HygRL reduces to a CTDE algorithm and recovers the corresponding theoretical guarantees as the decomposition error vanishes. Experiments across three domains with up to 55 agents demonstrate that HygRL consistently outperforms CTDE, fully decentralized, and graph-based baselines.