HySTAR: Anchored Hypergraphs for Stable Credit Assignment in Cooperative Multi-Agent Reinforcement Learning

Xinglong Luo; Yuding Zhang; Yuheng Kuang; Shuxuan Yuan; Zhenni Zeng; Weiqiang Zhu; Zhenhai Ji; Zhengning Wang

cs.LGSep 25, 2026

HySTAR: Anchored Hypergraphs for Stable Credit Assignment in Cooperative Multi-Agent Reinforcement Learning

Authors: Xinglong Luo, Yuding Zhang, Yuheng Kuang, Shuxuan Yuan, Zhenni Zeng, Weiqiang Zhu, Zhenhai Ji, Zhengning Wang

Organizations: University of Electronic Science and Technology of China · Independent Researcher

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.

Figures & tables

Figure 1: Motivation and design of HySTAR. MAPPO uses a single global value; dynamic grouping introduces group-level credit and changes its basis when relations or the active-agent set evolve; HySTAR maintains a stable agent-level decomposition basis through an anchored sparse hypergraph while adapting the representations propagated over it.

Figure 2: Overall architecture of HySTAR. The actor and centralized critic use independent MLP/ST-Encoder branches with the same architecture: their MLP outputs are $x_{t}^{i}$ and $\widetilde{x}_{t}^{i}$ , and their spatiotemporal representations are $Z_{t}^{i}$ and $\widetilde{Z}_{t}^{i}$ , respectively. The Policy Head $\pi_{\theta}(\cdot)$ outputs $a_{t}^{i}$ , the Credit Head $g(\cdot)$ outputs the Credit Logit $c_{t}^{i}$ , and the Critic Value Head $h(\cdot)$ outputs $V_{\phi,t}$ . During training, AHVD propagates information through overlapping routes $i-k\rightarrow e_{i-k}\rightarrow i\rightarrow e_{i}\rightarrow i+k$ . STCA fuses the resulting Credit and Value Scores into Final Scores for agent-specific policy advantages.

Figure 3: Average step reward (top) and evaluation win rate (bottom) on three super-hard SMAC maps: 6h_vs_8z , 27m_vs_30m , and MMM2 . Curves and shaded regions denote the mean and one standard deviation across independent seeds.

Map	Difficulty	QMIX ( Rashid et al. 2018 )	IPPO ( De Witt et al. 2020 )	MAPPO ( Yu et al. 2022 )	MAT ( Wen et al. 2022b )	HYGMA ( Liu and Li 2025 )	HySTAR (Ours)
3m	Easy	96.9(1.3)	100.0(0.0)	100.0(0.0)	100.0(1.8)	99.1(1.1)	100.0(0.0)
1c3s5z	Easy	96.1(1.7)	100.0(0.0)	100.0(0.0)	100.0(2.4)	97.0(2.0)	100.0(0.0)
8m	Easy	97.7(1.9)	100.0(0.7)	100.0(0.0)	100.0(1.1)	98.0(1.6)	100.0(0.0)
MMM	Easy	95.3(2.5)	96.9(0.0)	96.9(0.6)	100.0(2.2)	98.2(2.9)	100.0(1.8)
3s_vs_5z	Hard	98.4(2.4)	100.0(0.0)	100.0(0.6)	100.0(1.7)	99.0(0.9)	100.0(0.0)
5m_vs_6m	Hard	75.8(3.7)	87.5(2.3)	89.1(2.5)	93.8(4.4)	95.2(2.3)	95.6(2.1)

Table 1: Median evaluation win rate and standard deviation on selected SMAC maps. Difficulty is indicated for each map. For each map, we bold the method with the highest median win rate; when multiple methods have the same median, the one with the lower standard deviation is highlighted. Methods with identical median and standard deviation are jointly highlighted.

Figure 4: Learning curves on the cooperative MPE tasks Spread, Reference, and Comm. Curves and shaded regions denote the mean and one standard deviation across random seeds; higher episode reward is better.

Scenario	QMix ( Rashid et al. 2018 )	CDS ( Li et al. 2021 )	TiKick ( Huang et al. 2021 )	MAPPO ( Yu et al. 2022 )	HYGMA ( Liu and Li 2025 )	HySTAR (Ours)
3v.1	8.12(2.83)	76.60(3.27)	76.88(3.15)	88.03(1.06)	97.70(0.70)	98.26(0.93)
CA(easy)	15.98(2.85)	63.28(4.89)	/	87.76(1.34)	90.12(1.26)	91.80(1.05)
CA(hard)	3.22(1.60)	58.35(5.56)	73.09(2.08)	77.38(4.81)	69.67(5.21)	84.60(3.20)
Corner	16.10(3.00)	3.80(0.54)	33.00(3.01)	65.53(2.19)	56.18(3.66)	74.90(2.50)
PS	8.05(3.66)	94.15(2.54)	/	94.92(0.68)	90.36(0.73)	96.30(0.70)
RPS	8.08(4.71)	62.38(4.56)	79.12(2.06)	76.83(1.81)	63.11(4.04)	84.20(2.40)

Table 2: Average success rate and standard deviation on six GRF academy scenarios.

Method	$\mathbf{7\times 7}$ , $N_{\max}=5$ $p_{\mathrm{arrive}}=0.3$	$\mathbf{14\times 14}$ , $N_{\max}=10$ $p_{\mathrm{arrive}}=0.2$
TarMAC-IC3Net ( Das et al. 2019 )	$84.8\pm 4.5\%~(599\pm 187)$	$95.5\pm 1.3\%~(1706\pm 104)$
GA-Comm ( Liu et al. 2020 )	$95.9\pm 0.1\%~(891\pm 141)$	$97.1\pm 0.7\%~(1573\pm 253)$
MAGIC ( Niu et al. 2021 )	$99.9\pm 0.1\%~(440\pm 64)$	$99.9\pm 0.1\%~(819\pm 85)$
HYGMA ( Liu and Li 2025 )	$99.7\pm 0.1\%~(272\pm 41)$	$99.2\pm 0.1\%~(569\pm 34)$
HySTAR (Ours)	$99.9\pm 0.1\%~(263\pm 45)$	$99.9\pm 0.1\%~(558\pm 56)$

Table 3: Traffic Junction success rate and convergence epochs.

Figure 5: Topology ablation on MMM2 . All hypergraph and graph variants use the same ST-Encoder, actor input, representation dimension, training budget, and evaluation protocol; MAPPO is included as an external reference. HySTAR achieves the highest and most stable win rate.

Figure 6: Normalized critic value loss around an agent-death event on MMM2 .

Figure 7: Sensitivity to the neighborhood size

k

on the large-scale 27m_vs_30m scenario.

Method	Params (K)	$\Delta$ Param.	Win Rate	$\Delta$ Win
MAPPO ( Yu et al. 2022 )	125.861	0.0%	93.8%	0.0%
IPPO ( De Witt et al. 2020 )	114.641	+8.9%	69.5%	$-25.9\%$
MAT ( Wen et al. 2022b )	253.455	$-101.4\%$	100.0%	+6.6%
HySTAR (Ours)	149.889	$-19.1\%$	100.0%	+6.6%

Table 4: Parameter efficiency on 27m_vs_30m .

Cooperative MARL

Cooperative multi-agent reinforcement learning (MARL) trains agents to coordinate toward shared goals under partial information and decentralized control.

See all 247 papers

HyPOLE: Hyperproperty-Guided Multi-Agent Reinforcement Learning under Partial Observation
Jun 29, 2026Arshia Rafieioskouei, Tzu-Han Hsu, Matthew Lucas +1Formal Methods for RL Reinforcement Learning
Department of Computer Science and Engineering, Michigan State University, MI, USA.
HiComm: Hierarchical Communication for Multi-agent Reinforcement Learning
Jun 28, 2026Runze Zhao, Dongruo Zhou, Sumit Kumar Jha +2Multi-Agent Communication Cooperative MARL
Luddy School of Informatics, Computing, and Engineering Indiana University Bloomington Bloomington, IN 47408 · Department of Computer & Information Science & Engineering University of Florida Gainesville, FL 32611 · Department of Electrical Engineering and Computer Science United States Military Academy West Point, NY 10996 +1
Hierarchical Lead Critic based Multi-Agent Reinforcement Learning
Feb 25, 2026David Eckel, Henri MeeßMulti-Agent Reinforcement Learning Cooperative MARL
Fraunhofer Institute IVI, Ingolstadt, Germany

Jun 29, 2026J/K move · Enter open · S save

HyPOLE: Hyperproperty-Guided Multi-Agent Reinforcement Learning under Partial Observation

Arshia Rafieioskouei, Tzu-Han Hsu, Matthew Lucas, Borzoo Bonakdarpour

Department of Computer Science and Engineering, Michigan State University, MI, USA.

Formal Methods for RL Reinforcement Learning Partially Observable RL Decentralized MARL Policy Learning Multi-Agent Reinforcement Learning

Open paper AskPDF arXiv

Formal specification is a powerful tool to guide the learning process and provides significant advantages over reward shaping: (1) mathematical rigor; (2) expressiveness to specify objectives and constraints, and (3) the ability to define tactics to achieve objectives. However, these benefits remain largely unexplored in the context of Multi-Agent Reinforcement Learning (MARL). This paper introduces HyPOLE, a novel framework for MARL under partial observability, where learning is guided by the expressive power of the so-called hyperproperties and, in particular, the temporal logic HyperLTL. We integrate Centralized Training for Decentralized Execution (CTDE) techniques with HyPOLE to synthesize decentralized policies, and our evaluation on SMAC, MessySMAC, and WildFire benchmark demonstrates clear advantages over baselines.

Abstract

Cooperative MARL

Explore similar work

HyPOLE: Hyperproperty-Guided Multi-Agent Reinforcement Learning under Partial Observation

HiComm: Hierarchical Communication for Multi-agent Reinforcement Learning

Hierarchical Lead Critic based Multi-Agent Reinforcement Learning