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 xti and xti , and their spatiotemporal representations are Zti and Zti , respectively. The Policy Head πθ(⋅) outputs ati , the Credit Head g(⋅) outputs the Credit Logit cti , and the Critic Value Head h(⋅) outputs Vϕ,t . During training, AHVD propagates information through overlapping routes i−k→ei−k→i→ei→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
7×7 , Nmax=5parrive=0.3
14×14 , Nmax=10parrive=0.2
TarMAC-IC3Net ( Das et al. 2019 )
84.8±4.5%(599±187)
95.5±1.3%(1706±104)
GA-Comm ( Liu et al. 2020 )
95.9±0.1%(891±141)
97.1±0.7%(1573±253)
MAGIC ( Niu et al. 2021 )
99.9±0.1%(440±64)
99.9±0.1%(819±85)
HYGMA ( Liu and Li 2025 )
99.7±0.1%(272±41)
99.2±0.1%(569±34)
HySTAR (Ours)
99.9±0.1%(263±45)
99.9±0.1%(558±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.
Cooperative multi-agent reinforcement learning (MARL) trains agents to coordinate toward shared goals under partial information and decentralized control.
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.
Arshia Rafieioskouei, Tzu-Han Hsu, Matthew Lucas +1
Department of Computer Science and Engineering, Michigan State University, MI, USA.
Cooperative multi-agent reinforcement learning (MARL) often relies on communication to mitigate partial observability, yet most existing protocols treat messages as flat dense vectors detached from the structure of the observations they summarize. This design overlooks an important source of inductive bias in many cooperative environments, where observations naturally follow a hierarchy such as groups and entities. We propose HiComm, a plug-in communication module that grounds messages in the sender's hierarchical observation. HiComm is receiver-driven: the receiver issues a query, and the hierarchy is resolved through a three-stage decoding process that first selects a group, then a sender, and then an entity within that group, returning the corresponding feature slice as the message. This converts communication from unstructured vector transmission into structured information retrieval over the sender's observation hierarchy. We instantiate this mechanism with Straight-Through Gumbel-Softmax for differentiable discrete selection and a lightweight shared projection design that attaches to standard MARL pipelines. Experiments across cooperative MARL tasks with different observation structures and coordination demands show that HiComm matches or outperforms representative learned communication baselines while reducing communication volume by up to 23× per receiver per episode.
Runze Zhao, Dongruo Zhou, Sumit Kumar Jha +2
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
Cooperative Multi-Agent Reinforcement Learning (MARL) solves complex tasks that require coordination from multiple agents, but is often limited to either local (independent learning) or global (centralized learning) perspectives. In this paper, we introduce a novel sequential training scheme and MARL architecture, which learns from multiple perspectives on different hierarchy levels. We propose the Hierarchical Lead Critic (HLC) - inspired by natural emerging distributions in team structures, where following high-level objectives combines with low-level execution. HLC demonstrates that introducing multiple hierarchies, leveraging local and global perspectives, can lead to improved performance with high sample efficiency and robust policies. Experimental results conducted on cooperative, non-communicative, and partially observable MARL benchmarks demonstrate that HLC outperforms single hierarchy baselines and scales robustly with increasing amounts of agents and difficulty.