Stable team credit assignment improves multi-agent reinforcement learning
HySTAR: Anchored Hypergraphs for Stable Credit Assignment in Cooperative Multi-Agent Reinforcement Learning
Machine Learning
Summary
Assigning rewards fairly among team members in cooperative tasks is hard when agents can only see part of the environment and must work together. The authors present HySTAR, a method that uses a fixed structure (a hypergraph) to consistently break down team rewards into parts relevant to individual agents and groups. This helps avoid confusion caused by changing team groupings over time. Tests show HySTAR works better than previous methods on several simulated teamwork tasks.
What this means in practice
- •For robotics teams: Coordinate multiple robots in partially known environments by accurately attributing team successes to individual and group actions.
- •For traffic management teams: Improve multi-agent controllers in traffic simulations to better assign credit and speed up learning for coordinated vehicle behaviors.
Authors
Xinglong Luo, Yuding Zhang, Yuheng Kuang, Shuxuan Yuan, Zhenni Zeng, Weiqiang Zhu, Zhenhai Ji, Zhengning Wang
Abstract
Cooperative multi-agent reinforcement learning under partial observability and shared rewards requires assigning team outcomes to individual agents and high-order coalitions. A MAPPO-style critic compresses joint behavior into one global value, while critics that dynamically reconstruct the grouping topology change the mapping from agents and coalitions to value components as interactions or active agents evolve. We refer to this inconsistency as structural target drift. We introduce HySTAR, a MAPPO-based framework that separates adaptive representation learning from a temporally consistent high-order value-decomposition basis. HySTAR anchors an overlapping sparse hypergraph as a uniformly covered decomposition scaffold, uses a spatiotemporal encoder to represent physical and task-dependent interactions, and combines temporal and structural relevance to construct agent-specific advantages. Experiments on SMAC, GRF, Traffic Junction, and MPE demonstrate consistent improvements over MAPPO-style, value-factorization, and dynamic-grouping baselines. On the hardest SMAC settings, HySTAR achieves relative gains of 16.7\% over MAPPO and 15.6\% over HYGMA, ranks first on all six GRF scenarios, reduces Traffic Junction convergence epochs by up to 40.2\% relative to MAGIC, and obtains the highest MPE episode rewards. Controlled topology, agent-death, neighborhood, and parameter analyses support the benefit of anchoring the decomposition scaffold while adapting the propagated representations.