PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.31531v1cs.LG

TL;DR

Shared rewards in partially observable cooperative MARL leave individual and coalition contributions unresolved, while dynamic grouping can change the critic's decomposition basis over time. HySTAR anchors a sparse hypergraph while adapting spatiotemporal representations and agent-specific advantages; it consistently outperforms several baseline families across four benchmarks.

  • Problem

    Shared rewards make it difficult to assign team outcomes to individual agents and high-order coalitions, and dynamic grouping can change the value-component mapping over time.

    Source: Introduction · p. 1

  • Method

    HySTAR uses an anchored sparse hypergraph as a stable decomposition scaffold, adapts spatiotemporal representations, and combines temporal and structural relevance to form agent-specific advantages.

    Source: Introduction · p. 1

  • Results

    HySTAR consistently outperforms MAPPO-style, value-factorization, and dynamic-grouping baselines across SMAC, GRF, Traffic Junction, and MPE; it ranks first on all six GRF scenarios, with relative gains reaching 14.3% over MAPPO and 33.4% over HYGMA.

    Source: Introduction · p. 1, Conclusion · p. 7

  • Takeaways & Limitations

    Controlled topology and agent-death analyses support anchoring a sparse decomposition scaffold while adapting the representations propagated over it.

    Source: Conclusion · p. 7

    HySTAR assumes consistent agent-slot ordering, uses communication-augmented execution, and adds critic parameters relative to MAPPO and IPPO.

    Source: Limitations · p. 7

Abstract

from arXiv · show

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.

Introduction

HySTAR separates a stable credit-assignment basis from adaptive representations to address structural target drift in cooperative MARL. Across four benchmarks, it reports consistent improvements over MAPPO-style, value-factorization, and dynamic-grouping baselines.

Introduction

  • Shared rewards leave individual-agent and high-order coalition contributions unresolved, while MAPPO represents coordinated contributions only implicitly through one global value.Dynamic grouping adds structural target drift when relations or active agents change the mapping from agents and coalitions to value components, even when coordination roles remain similar.Source: Introduction · p. 1
  • HySTAR anchors an overlapping sparse hypergraph as a persistent agent-level decomposition scaffold while adapting spatiotemporal representations to current interactions and trajectories.AHVD evaluates agent and team values on the scaffold, and STCA combines temporal and structural relevance to construct agent-specific advantages.Source: Introduction · p. 1
  • HySTAR ranks first on all six GRF scenarios, with relative gains reaching 14.3% over MAPPO and 33.4% over HYGMA.It also obtains the best reported result on 11 of 12 selected SMAC maps; on 3s5z_vs_3s6z it improves over MAPPO from 84.4% to 98.5%, a 16.7% relative gain, and on 6h_vs_8z it improves over HYGMA from 85.0% to 98.3%, a 15.6% relative gain.Source: Introduction · p. 1
  • The paper contributes a communication-augmented CTDE framework, AHVD and STCA, and evaluations across four MARL benchmarks with topology, agent-death, neighborhood, and parameter-efficiency analyses.The actor uses decentralized observations at execution, while privileged global state is used only during training.Source: Introduction · pp. 1–2

Related Work

Related work situates HySTAR among cooperative MARL, relational representation learning, and shared-reward credit-assignment methods.

Multi-Agent Reinforcement Learning

  • Cooperative MARL methods include value-decomposition approaches that factorize joint values and policy-gradient or actor-critic methods; HySTAR builds on MAPPO with structured high-order critic decomposition.CTDE centralizes information during training while preserving decentralized execution.Source: Multi-Agent Reinforcement Learning · p. 2

Graph and Hypergraph Representation Learning

  • Hypergraphs represent non-binary relations through hyperedges, extending pairwise graphs for coordinated behavior involving more than two agents.HYGMA discovers adaptive groups, whereas HySTAR maintains an anchored sparse hypergraph skeleton under a comparable communication-augmented execution setting.Source: Graph and Hypergraph Representation… · p. 2

Value Decomposition and Credit Assignment

  • Prior credit-assignment approaches use counterfactual or Shapley-style signals, auxiliary objectives, behavioral diversity, or reward shaping; STCA combines temporal credit with high-order structural scores.STCA converts the shared team advantage into agent-specific shaped advantages.Source: Value Decomposition and Credit… · p. 2

Method

HySTAR combines communication-augmented CTDE with a fixed overlapping hypergraph scaffold: spatiotemporal representations adapt, while AHVD and STCA derive agent-specific advantages for PPO.

Method

  • The task is modeled as a Dec-POMDP with local observations, joint actions, state transitions, and shared rewards.Source: Method · p. 3

Overview

  • HySTAR anchors the topology while adapting representations; its actor produces actions and Credit Logits, and STCA combines Credit and Value Scores to allocate the mixed team advantage.Source: Overview · p. 3

Spatiotemporal Representation Learning

Anchored Hypergraph Value Decomposition

  • AHVD fixes uniformly covered overlapping hyperedges before training, then uses stacked node–edge–node messages to propagate features and score action-aware values.Overlapping hyperedges support routes across agents with O(Nk) message complexity.Source: Anchored Hypergraph Value Decomposition · p. 4

Spatiotemporal Credit Assignment

  • STCA equally mixes current and rollout Credit Logits, combines Credit and Value Scores using update-dependent structural mixing, and produces agent-specific PPO advantages.Source: Spatiotemporal Credit Assignment · p. 4

Optimization Objective

  • The actor, baseline critic, and AHVD critic use separate optimizers, while a distillation loss aligns temporal credit logits with AHVD agent values.The actor follows the PPO clipped objective, and the baseline critic uses the standard clipped MAPPO value loss.Source: Optimization Objective · p. 4

Experiments

HySTAR is evaluated across four cooperative MARL benchmarks, with environment-specific settings and metrics. The setup also specifies the principal SMAC comparison methods and reports learning curves across random seeds.

Experimental Setup

  • SMAC tests partially observable combat with heterogeneous units and agent death, while MPE tests Spread, Reference, and Comm coordination.GRF evaluates coordinated play against scripted opponents; Traffic Junction varies the active-agent set under stochastic vehicle arrivals.Source: Experimental Setup · p. 5
  • The reported metrics are median win rate on SMAC, success rate on GRF, success rate and convergence epochs on Traffic Junction, and episode reward on MPE.Learning curves show the mean and one standard deviation across seeds.Source: Experimental Setup · p. 5
  • MPE learning curves cover Spread, Reference, and Comm; shaded regions show one standard deviation across random seeds, and higher episode reward is better.The setup also identifies Table 2 as reporting average success rate and standard deviation for six GRF academy scenarios, and Table 3 as reporting Traffic Junction success rate and convergence epochs.Source: Figure 4 · p. 6, Table 2 · p. 6, Table 3 · p. 6

Performance on SMAC

HySTAR reports strong results on SMAC and MPE: it leads on most selected SMAC maps and achieves the highest final reward on all three MPE tasks.

Performance on SMAC

  • HySTAR achieves the best reported result on 11 of 12 SMAC maps, including relative gains of 16.7% over MAPPO and 15.6% over HYGMA on two hard maps.On 3s5z_vs_3s6z, it rises from 84.4% with MAPPO to 98.5%; on 6h_vs_8z, it rises from 85.0% with HYGMA to 98.3%.Source: Performance on SMAC · p. 6

Performance on MPE

  • HySTAR obtains the highest final reward on Spread, Reference, and Comm, with its clearest advantage on Spread.Because MPE returns are negative, the authors report absolute reward improvements rather than percentage ratios.Source: Performance on MPE · p. 6
  • The fixed active-agent set in MPE shows that anchoring is useful beyond agent-death or variable-team settings, while the ST-Encoder adapts task-dependent interactions.Source: Performance on MPE · p. 6

Performance on GRF

HySTAR performs strongly on GRF and Traffic Junction, while ablations examine topology, critic stability around agent death, and neighborhood size.

Performance on GRF

  • HySTAR ranks first on all six GRF scenarios; on RPS it improves over HYGMA from 63.11% to 84.20%, a 33.4% relative gain.On Corner, it improves over MAPPO from 65.53% to 74.90%, a 14.3% relative gain.Source: Performance on GRF · p. 6

Performance on Traffic Junction

  • HySTAR reaches 99.9% success in both Traffic Junction settings and reduces convergence epochs relative to HYGMA and MAGIC.Against MAGIC, convergence epochs fall by 40.2% and 31.9%; stochastic arrivals continually change the active-agent set.Source: Performance on Traffic Junction · p. 6

Ablation Study

  • With the representation backbone and actor input controlled, HySTAR has the highest and most stable MMM2 win rate among the topology variants.Anchored Dense and GCN also underperform; the comparisons distinguish the anchored sparse scaffold from additional connectivity and pairwise aggregation.Source: Ablation Study · pp. 6–7, Figure 5 · p. 7
  • Around allied-agent death, HySTAR shows the smallest critic-loss disturbance and lowest late-stage loss; Dynamic w/o Mask has the largest increase and slowest recovery.Dynamic w/ Mask is intermediate, indicating that anchoring stabilizes the critic beyond masking alone.Source: Figure 6 · p. 7, Ablation Study · p. 7
  • On 27m_vs_30m, small neighborhoods omit useful coordination context, while k values above 8 add redundant interactions and yield unchanged or lower performance.Source: Ablation Study · p. 7

Parameter Efficiency Analysis

On 27m_vs_30m, HySTAR combines a high win rate with comparatively modest critic capacity, while neighborhood-size results indicate a useful context-versus-redundancy trade-off.

Parameter Efficiency Analysis

  • 100.0% win rate with 149.889K critic parameters; HySTAR uses 40.9% fewer parameters than MAT while matching its win rate.Compared with MAPPO, HySTAR uses 19.1% more critic parameters and improves win rate from 93.8% to 100.0%.Source: Table 4 · p. 7, Parameter Efficiency Analysis · p. 7

Limitations

HySTAR has an agent-slot ordering assumption, uses cross-agent representations during execution, and adds critic parameters relative to MAPPO and IPPO.

  • HySTAR assumes consistent agent-slot ordering; general permutations produce a different anchored incidence pattern.Source: Limitations · p. 7
  • Execution uses cross-agent representations and therefore follows communication-augmented CTDE.Source: Limitations · p. 7
  • The ST-Encoder, AHVD, and STCA add critic parameters relative to MAPPO and IPPO.Source: Limitations · p. 7

Conclusion

HySTAR combines a stable sparse decomposition scaffold with adaptive spatiotemporal representations, and its results support this design across four MARL benchmarks.

  • Across SMAC, GRF, Traffic Junction, and MPE, HySTAR consistently outperforms MAPPO-style, value-factorization, and dynamic-grouping baselines.Source: Conclusion · p. 7
  • AHVD decomposes values over temporally consistent support, while STCA produces agent-specific optimization signals.Source: Conclusion · p. 7
  • Controlled topology variants and agent-death analysis support anchoring a sparse decomposition scaffold while adapting propagated representations.Source: Conclusion · p. 7

Related papers

Loading 2609.31531v1…