acceptodds
Under review as a conference paper at ICLR 2027

Scalable Multi-Agent Reinforcement Learning over Hypergraphic Environment

Abstract

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.

Primary area:
reinforcement learning
Keywords:
Multi-Agent Reinforcement Learning, Scalable Reinforcement Learning, Semi-Decentralized Training

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_3F1LOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes HygRL, a hypergraph-based framework for scalable cooperative MARL. It decomposes the global learning problem into overlapping hyperedge-localized subproblems, trains a centralized critic and local policies within each hyperedge, and averages overlapping policies for decentralized execution. The authors formulate a hypergraphic MAMDP and derive approximation and performance bounds involving local transition errors, reward errors, and policy disagreement. Experiments across wireless communication, power grid load balancing, and traffic signal control evaluate up to 55 agents with 10 random seeds, reporting substantial improvements over centralized and graph-based baselines in several larger configurations.

Critical strengths
  1. Hyperedge-localized CTDE addresses a relevant scalability problem in networked MARL. The separation between local centralized training and decentralized policy aggregation provides a concrete approach to handling overlapping groups.

  2. The experimental evaluation covers three different networked control domains and includes both MLP and GRU policies. Several larger configurations show substantial gains over global CTDE.

Critical weaknesses
  1. Appendix A.6 claims (Me=O(melog⁡nmax⁡,e)M_e=O(m_e\log n_{\max,e})), but its explicit expression contains (m_e\psi_e), where (ψe=ϵr(e)+∑i∈eδi\psi_e=\epsilon_r(e)+\sum_{i\in e}\delta_i). Under the stated assumptions, this term can scale as (O(me2)O(m_e^2)).

  2. The global bound sums contributions across all hyperedges. Independence of each local term from the total agent count does not establish that the global degradation bound is independent of system size.

  3. The practical MRF construction also requires justification: it constructs local approximations conditioned on the full global state-action pair, without establishing that the resulting surrogate kernel depends only on the hyperedge-local variables required by Definition 1.

  4. In happo.py, the randomized update order is generated but not used, and the accumulated importance-ratio correction is not passed to subsequent actor updates. The supplied implementation therefore does not match the sequential HAPPO update assumed by the theoretical analysis.

  5. In the five-agent wireless configuration, Graph.yml contains access-point identifiers, while the NPPO implementation interprets them as neighboring agent indices. This may invalidate the intended graph-based comparison for that configuration.

Questions for authors
  1. Were the reported HAPPO and HygHAPPO results generated using the supplied happo.py implementation? If so, why are the randomized update order and accumulated importance-ratio correction not used in the actor updates?

  2. How is the claimed (O(m_e\log n_{\max,e})) bound obtained when (m_e\psi_e) may grow quadratically? Does Corollary 2 hold deterministically or only in expectation over update orders? How does the bound account for the total number of hyperedges?

  3. How does Appendix B.2 construct a unique surrogate kernel (P_e(\cdot\mid z_e)) when its mean-field approximation is computed using the full global state-action pair?

  4. Could the authors verify the NPPO neighborhood construction and provide a graph-based localized CTDE baseline with matched critic capacity and group size?

  5. What are the wall-clock training times, peak memory requirements, and total parameter counts as the number of agents and hyperedges increases? Were global CTDE baselines independently tuned, particularly in configurations where their performance deteriorates sharply?

2 comments

We thank the reviewer for a precise report and correct the five issues below.

W1 (order of Mₑ). Correct. Since δᵢ≤1, mₑψₑ = mₑεᵣ + mₑΣδᵢ ≤ mₑεᵣ + mₑ², so Mₑ=O(mₑ(mₑ+log nmax,e)), not O(mₑ log nmax,e). The reviewer's O(mₑ²) diagnosis is correct. Corollary 2's inequality is unchanged; A.6 and the discussion are corrected, including removal of "tightens as sparser".

W2 (global bound). The unnormalized sum has one term per hyperedge and does grow with |E|; per-term independence does not give n-independence. With max mₑ≤m, max nᵢ≤κ and Rₑ≤mₑ R̄, 1/n Σ MₑRₑ = O(κm(m+logκ+εᵣ)R̄). Corollary 2 holds in expectation over the random order; for a fixed order mₑ becomes 2mₑ−1. Measured δᵢ is 0.7–2.6% on wireless and 1.0% on Beijing. The number of hyperedges enters through |E|≤κn/mmin; we delete the claims "never depends on n" and "tightens as sparser".

W3 (B.2). Correct: qₑ^(z) depends on the full z, so Pₑ:=qₑ^(z) is not a kernel. We now use the fiber average Pₑ(·|zₑ)=∫qₑ^(zₑ,z₋ₑ)ν(dz₋ₑ|zₑ) with a fixed policy-independent ν. Let ρclique be the clique influence coefficient. Under weak coupling ρclique≤Cρ ε and bₑ≤Cb ε, so εₚ(e)≤ρclique(1+3Cb/Cρ)≤(Cρ+3Cb)ε. Hence ε<1/(Cρ+3Cb) suffices and implies ρclique<1/(1+3Cb/Cρ). Outside this regime B.2 remains a well-defined kernel but gives no certified bound; the theorem is conditional on Definition 1 and does not use B.2.

W4 (HAPPO). Confirmed: order was shuffled but not used, and m was not passed. The reported runs used that implementation. We fixed both lines, reran all HAPPO/HygHAPPO experiments, and regenerated every table, effect size and p-value. Examples: WC-20 GRU 723.19±39.35 vs 539.94±62.43 (d=3.33, p=1.9e-6); WC-50 GRU 1210.18±163.83 vs 562.00±208.81 (d=3.28, p=1.2e-6). The margin falls from 1119 to 183 at 20 GRU and from 1037 to 648 at 50 GRU, remaining significant; the corrected HAPPO learns at 20 rather than failing. The ordering is unchanged in 20/22 settings; HAPPO is ahead only on WC-5 MLP (p=0.21) and WC-35 GRU (p=0.12), where both are highly variable, so we claim no ordering there and withdraw the previous 35-agent advantage. The full 22-row table is in the revision.

W5 (Penta graph). Confirmed: generator.py wrote AP identifiers, not adjacency; only the WC-5 NPPO rows were affected. We corrected the writer, regenerated Graph.yml without changing Config.yml, added tests and a runtime guard, and retrained NPPO: 98.50±31.46 (MLP) and 97.90±32.59 (GRU), against 257.24±0.84 and 257.27±1.26 for HygHAPPO. The defect is confined to Penta: the other wireless presets have symmetric adjacency with indices below n, and the LB/LS graphs are generated by networkx. The ordering is unchanged. NPPO is a simple graph-neighbourhood PPO baseline, not a re-implementation of Qu et al. (2022); that claim is withdrawn.

Q1. Answered in W4: the reported results came from the supplied implementation; there is no design rationale for the omission.

Q2. See W1 and W2.

Q3. See W3.

Q4. See W5: NPPO is corrected and relabelled.

Q5. Total parameters are 1.12–2.65× the CTDE counterpart (median 1.75). The largest unit sees at most 12 agents, against 50 for a joint critic, and total parameters grow with Σnᵢ. The comparison uses one shared hyperparameter set, chosen once on a separate validation configuration; we do not claim the global baselines are optimally tuned. We do not report wall-clock time because the runs were distributed over heterogeneous machines.

Other corrections. Beijing 53, Manhattan 47, San Francisco 55, Los Angeles 33; the submission reported 33, 47 and 55 for the last three. The significance test now uses Welch's unequal-variance form; no decision changes at 0.05 or 0.01.

Reviewer_3F1LOpenReview ↗

Thank you for your response.

While some of my concerns have been addressed, I still believe that the paper falls substantially short of the minimum standards for acceptance at ICLR. Therefore, I will maintain my original rating.

Reviewer_k3DGOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes HygRL a scalable hybrid semi-decentralized multi-agent reinforcement learning framework that leverages hypergraphs to model higher-order interdependencies among agents. By decomposing the global task into hyperedge-localized subtasks trained in parallel and employing mean policy aggregation to resolve conflicts during decentralized execution the method addresses the scalability limitations of existing centralized and graph-based approaches. The authors provide theoretical performance error bounds for the hypergraph decomposition and demonstrate through experiments in wireless communication power grid load balancing and traffic signal control that HygRL consistently outperforms baseline methods in both final performance and sample efficiency as the number of agents increases.

Critical strengths
  1. The writing is well-presented.
  2. The motivation is well-justified.
Critical weaknesses
  1. In the method section, I am particularly concerned that the theoretical guarantees rely on Assumption 1, which bounds the divergence between an agent’s local hyperedge policies and their aggregated policy. The method lacks explicit mechanisms (e.g., regularization) to enforce this consistency during independent hyperedge training. I would like to know how this assumption can be ensured in practical implementations.
  2. My primary concern lies with the experimental evaluation, which I believe requires significant adjustments. Specifically, I have identified several key issues: (1) The current maximum scale of 35 agents is insufficient to convincingly demonstrate scalability. The authors should consider referencing and comparing against recent works in Mean-Field MARL or Networked MARL to better validate this claim. (2) The distinction between this work and Ego-Graph [1] methods is unclear. I did not find a clear differentiation in the text, nor were there any baseline comparisons against Ego-Graph approaches. (3) If the core contribution is scalability, the authors should include decentralized baselines such as Mean-Field MARL, Networked MARL, or other Graph-Based MARL methods to provide a more relevant comparison. (4) How sensitive is the performance to different hypergraph structures? Specifically, it is important to analyze how the method performs when the hypergraph partitioning is suboptimal or imperfect.

References

[1] Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning. In NeurIPS 2025.

Questions for authors

Please refer to "Critical Weaknesses".

4 comments

We thank the reviewer for a specific report.

Corrections. (1) HAPPO. The randomized update order was generated but not used, and the importance-ratio accumulation was dropped; HygHAPPO embeds the same update. Fixed and all runs redone: the margin falls from 1119 to 183 at 20 (GRU) and 1037 to 648 at 50, both significant; ordering unchanged in 20 of 22 settings. (2) Graph baseline. Its five-agent graph file held access-point ids where agent neighbours were expected; re-run it reaches 98.50/97.90 against 257.2/257.3. It is also not a re-implementation of Qu et al. (2022); we implemented that algorithm (SAC) and report it as the networked baseline. (3) Agent counts. Beijing 53, Manhattan 47, San Francisco 55, Los Angeles 33. (4) Significance. The script used Student's rather than Welch's; recomputed, no decision changes.

W1. The assumption cannot be violated: TV(πi,e,πˉi)≤1ni∑e′∋iTV(πi,e,πi,e′)≤ni−1ni\mathrm{TV}(\pi_{i,e},\bar\pi_i)\le\frac1{n_i}\sum_{e'\ni i}\mathrm{TV}(\pi_{i,e},\pi_{i,e'})\le\frac{n_i-1}{n_i}, since one term vanishes. It is zero when ni=1n_i=1 and at most 4/54/5 here as ni≤5n_i\le5, and substituting it leaves Theorems 1–2 and Corollaries 1–2 unchanged, so the guarantee concerns Algorithm 1 rather than a hypothesis class; the revision states it as a definition with an unconditional corollary. The mean is the KL projection of the heads and δi\delta_i its residual, which the bound already carries through ϕe=ϵp+∑iδi\phi_e=\epsilon_p+\sum_i\delta_i, measured at 0.7–2.6% on wireless and 1.0% on Beijing. A penalty on δi\delta_i would act on that same quantity, so we have not added one. What the aggregation costs follows from conflict, not overlap: opposed rewards attain (ni−1)/ni(n_i-1)/n_i, aligned ones give zero.

W2.1. The largest setting is San Francisco at 55, not 35: 35 is one of four wireless sizes; the scale will be stated in every caption. The ordering is unchanged in 20 of 22 settings and the margin is largest at the largest size of each family: 648 over HAPPO at 50 (GRU) and 851 under MLP, 1190 at Beijing, 1332 at San Francisco, 711 over the neighbour baseline there. The exceptions are grid-4x2 (max⁡e∣e∣/n=0.5\max_e|e|/n=0.5) and Los Angeles (33 agents, pressure reward near-local). Networked MARL is compared: SAC is at parity at 5 agents (p=0.20p=0.20, 0.360.36) and behind at 20 and 50 by 82/261 (MLP) and 236/438 (GRU), and κ=2\kappa=2 already covers the whole twenty-user layout. We report no setting above 55 and do not extrapolate; a larger real network is beyond our compute budget here.

W2.2. The distinction was absent and we add it, as a class: methods that estimate their structure during training, of which [1] is the decentralized member (a posterior over per-agent masks under an ELBO) and HYGMA the centralized one. HygRL takes the structure as input, as networked MARL takes the graph as input. Two consequences favour it: the decomposition errors are properties of a given H\mathcal H, so the bound is about a fixed partition, while the ELBO of [1] bounds evidence rather than the return of the coupled algorithm; and it adds no second source of non-stationarity. The cost is adaptivity. On the unit axis, three differences: [1] optimises one value and one policy per agent, ours a joint policy and value over ee; its target adds neighbours' rewards with decay, ours decomposes exactly, ∑er~e=r\sum_e\tilde r_e=r; it needs neighbour states at execution, we need none. We have not reproduced its experiments and report no number against it: the class is represented by HYGMA, behind the matched backbone at both sizes, and a decentralized member at a matched backbone is the missing row. The two classes compose, since [1]'s posterior, symmetrised and closed into cliques, is a hypergraph for our framework.

W2.3. IPPO uses no neighbourhood information and wins on grid-4x2 and Los Angeles; HYGMA selects 2–5 groups against our 12 and 14 and is behind at both sizes; on traffic SAC does not converge; DGN and DCG keep global critics and sit with CTDE. We did not add a mean-field row: its mean action is a sufficient statistic only for exchangeable agents with weak coupling, and in load balancing the roles have different action spaces while a capacity constraint is not a function of the mean. Appendix D.7 states this and names MF-PPO on wireless as the smallest missing row.

W2.4. We replace the hypergraph by a random hypergraph keeping every size, degree and environment parameter, 14% of incidences retained. The gain disappears: 681.20 and 723.19 become 136.34 and 103.61 (d=12.8d=12.8, 12.512.5; p<10−14p<10^{-14}), while HAPPO, whose unit is the whole system and whose decomposition error is zero, scores 222 and 183 below. A wrongly grouped hypergraph is worse than not decomposing (136 and 104 against 459 and 540), so the performance of this method also depends on the quality of its hypergraph structure. One realisation, one environment, one endpoint rather than the graded curve.

Reviewer_k3DGOpenReview ↗

Thank you very much for the response, but there are still many unresolved issues.

Thank you very much for the response, but there are still many unresolved issues.

  1. Regarding the response to W2.1, you stated, “We report no setting above 55 and do not extrapolate; a larger real network is beyond our compute budget here.” To my knowledge, many Networked MARL methods [1,2] involve significantly more agents than this. If such scales cannot be achieved, I believe this contradicts the claim of being “Scalable” as stated in the paper’s title.

  2. Regarding the response to W2.3, although the authors provided some explanations, I do not understand why a method claimed to be Scalable MARL does not include Mean-Field MARL as a baseline for comparison. Furthermore, I could not find relevant descriptions in Appendix D.7 about Mean-Field MARL method. I suggest that the authors provide further clarification on this point.

  3. An additional concern is why the authors compared their method with many Centralized Training approaches. Generally, Centralized Training methods are not considered scalable. Including them in the comparison may affect the fairness of the evaluation.

Reference

[1] Efficient and scalable reinforcement learning for large-scale network control. In Nature Machine Intelligence 2024.

[2] GAT-MF: Graph attention mean field for very large scale multi-agent reinforcement learning. In KDD. 2023.

We thank the reviewer for the three follow-ups. They turn on one point we should have stated at the outset: the paper proposes an algorithm framework, not a complete algorithm. It takes an existing CTDE learner, localises its critic to a group, and leaves the learner's update rule unchanged. The claim is about that learner: where it alone degrades or stops learning as the system grows, the same learner inside the framework keeps working. The experiments are paired by construction: HAPPO against HygHAPPO and MAPPO against HygMAPPO with the same backbone and hyperparameters in each pair, and QMIX against HygQMIX in the appendix. Each comparison is therefore the same learner with and without the framework. An advantage of the design, which we should have stated, is that it is non-invasive: the learner's update rule, hyperparameters and implementation are untouched, so an existing CTDE method is placed inside the framework with little or no modification rather than replaced.

1. On the scale. "Scalable" refers to that extension of the base learner's range, not to a claim on the largest benchmark. What the runs are meant to show is that the framework is beneficial to a fixed learner where that learner breaks: on wireless at 20 agents (GRU), MAPPO scores −339.66-339.66 and becomes 705.58705.58 inside the framework, and HAPPO 539.94539.94 becomes 723.19723.19; at 50 agents MAPPO 429.05429.05 becomes 1198.691198.69 and HAPPO 562.00562.00 becomes 1210.181210.18; on traffic at San Francisco (55 agents), HAPPO −5852.53-5852.53 becomes −4521.41-4521.41. The reported scale in that line is broad rather than uniformly large: Qu et al. (2022, Operations Research) evaluate 36 users, Ren et al. (2025, AISTATS) 50 agents, and the largest numbers come from per-agent model-based methods (Ma et al., 2024, Nature Machine Intelligence). The largest setting we run is 55, and the quantities that would decide whether it runs beyond that are reported: the largest critic sees 12 agents and the largest unit covers 7 to 34% of the system above 20 agents. Whether the effect persists at 400 is not something we claim. If the AC reads the title as a claim to the scale of the networked benchmarks, we will qualify it in the abstract.

2. On the mean-field baseline. The mean-field material is in Section 1, not in D.7, which reports the value-based experiment. We do not add a mean-field row, and the reason is that mean field is a different class of approximation rather than a baseline of the same kind. It replaces the joint action by a statistic of the population and relies on exchangeability: MF-PPO shares one permutation-invariant actor-critic and requires the team reward and the transition kernel to be invariant under permutations of the agents (Li et al., 2021), and the largest mean-field result we know, GAT-MF with more than 3,000 agents, states that "considering the homogeneity among the agents, the network parameters are shared among the agents, reducing memory consumption" (Hao et al., 2023, KDD). A survey of scalable MARL describes the same line as learning "a single policy or value function ... for all assumed homogeneous agents" and notes that its convergence results "require very strong assumptions" (Cui et al., 2022). Mean-field work already handles a small number of types, either by separating a few complex agents from a population (major-minor mean field, Cui et al., 2024) or by conditioning the mean on a type (multi-type mean field, Ganapathi Subramanian et al., 2020), so the premise we need is fewer types than agents. Our instances do not meet it: the wireless benchmarks have 20 distinct access sets for 20 users, and 41 for 50, while in load balancing the resistances, voltage bounds, exceed costs and load profiles differ per node even within a role, and in traffic there is no common phase basis across intersections, with the interaction carried by specific links rather than by a population statistic. A type-conditioned mean field would therefore average over non-identical agents at the scale of the system itself. What we do compare on the same axis is the networked actor-critic of Qu et al. (2022, Operations Research), whose critic conditions on the neighbours' joint actions, which determine the mean; on wireless it is behind at 20 and 50, and on traffic it does not converge in our hands, which we report without claiming it as a property of the class.

3. On the CTDE baselines. They are not competitors we claim to be scalable; they are the controls for the framework's only intervention. Because the framework changes where the critic lives and nothing else, the comparison that tests the claim is the same learner with and without it, which is why the CTDE rows are central and why the claim is stated as a difference rather than as a ranking. Against the decentralized line alone the claim would be a different one, and we do not make it.

Reviewer_k3DGOpenReview ↗

Thank you very much for the response. I will maintain my score.

Thank you very much for the response. The authors have addressed some of my concerns, but there are still several issues that remain unresolved. I believe this work still requires substantial improvement and clarification in many aspects, which cannot be adequately addressed during this rebuttal period. I recommend that the authors should undertake major revisions to the manuscript, particularly by revising the descriptions of motivation, method, and experimental setup.

Reviewer_cEaWOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies scalable methods for cooperative MARL in large-scale networked systems. According to the authors, existing graph-based methods decompose a network into pairwise edges and local neighborhoods but overlook intrinsic, overlapping higher-order interdependencies, where transitions or rewards depend jointly on more than two agents, e.g., r(s1,s2,s3)=s1s2s3r(s_1,s_2,s_3)=s_1s_2s_3. The authors therefore propose using hypergraphs to organize the multi-agent environment into hyperedge-localized subtasks. Each subtask has a joint critic and separate local actors. An agent belonging to multiple hyperedges maintains a separate actor for each hyperedge, and the method averages their action distributions to obtain its executed policy.

Theoretically, the authors provide approximation bounds and, for the HATRL-based instantiation, a bound on possible performance degradation at each iteration. These bounds depend on disagreement between an agent’s hyperedge-specific policies and their aggregate, as well as dynamics and reward approximation errors caused by ignoring influences outside each hyperedge.

Empirically, they conduct experiments on wireless communication, power-grid load balancing, and traffic-signal control with up to 55 agents. The authors report that their method outperforms the tested centralized training with decentralized execution (CTDE) baselines from 20 agents onward in final performance and sample efficiency, with the largest gains in settings involving higher-order cooperation.

Critical strengths

Overall, I think the motivation behind the paper is relatively clear. The main benefit of HygRL compared with global CTDE is that it avoids training a critic over the entire system, which may require more samples to train well. Instead, it trains smaller hyperedge-localized critics. The tradeoff is the approximation error from ignoring influences outside each hyperedge, together with the disagreement introduced by aggregating policies. Explicitly organizing training around meaningful interaction groups seems reasonable.

Critical weaknesses
  1. However, I am not sure that the benefit over graph-based neighborhood methods is sufficiently established. Using a graph with pairwise edges does not imply that the transition models or critics are restricted to pairwise interaction functions. Methods using κ\kappa-hop neighborhoods, such as Qu et al. [1] and Ren et al. [2], can also capture higher-order interactions within those neighborhoods. In fact, even a one-hop neighborhood can capture such interactions if it contains the relevant agents and the critic is sufficiently expressive. These methods train an individual critic for each agent, but this is not necessarily a limitation. They also maintain one actor per agent, avoiding the need to average multiple hyperedge-specific policies for the same agent. I think the paper should explain more clearly when its particular approach offers advantages over these neighborhood-based methods—such as Qu et al. for discrete state-action spaces and Ren et al. for continuous state-action spaces—and why.

  2. The need to average policies across multiple hyperedges seems to be a critical issue. While policy disagreement appears in the bound, the paper would be significantly strengthened by a toy example or analysis explaining when this averaging works well and when it is more damaging.

  3. More generally, the paper would benefit from greater intuition about how performance depends on the topology and connectivity of the underlying problem, for example, in sparse versus tightly connected networks. In particular, how do hyperedge size, overlap, and coupling across hyperedge boundaries affect the benefits and approximation errors? This would help readers understand when HygRL is preferable and when alternatives such as the κ\kappa-hop methods of Qu et al. and Ren et al. may be more appropriate.

References

[1] Guannan Qu, Adam Wierman, and Na Li. “Scalable Reinforcement Learning for Multiagent Networked Systems.” Operations Research, 70(6):3601–3628, 2022.

[2] Zhaolin Ren, Runyu Zhang, Bo Dai, and Na Li. “Scalable Spectral Representations for Multiagent Reinforcement Learning in Network MDPs.” AISTATS, PMLR 258:550–558, 2025.

Questions for authors

Please see the critical weaknesses above.

2 comments

We thank the reviewer for a specific report.

Corrections. HAPPO's update order and ratio accumulation were wrong; both are fixed, all HAPPO and HygHAPPO runs redone, and the margin at 20 agents falls from 1119 to 183. NPPO's five-agent graph file held access-point ids; re-run it reaches 98.50/97.90 against 257.2/257.3. The agent counts are Beijing 53, Manhattan 47, San Francisco 55, Los Angeles 33. The significance script used Student's rather than Welch's test; every p-value is recomputed and no decision changes.

W1. We did describe NPPO as a PPO re-implementation of Qu et al. (2022), and that description was wrong. NPPO is a simple graph-neighbourhood PPO baseline: one policy and one state-value critic per agent, conditioned on the closed one-hop neighbourhood, updated on the agent's own return. It is no longer presented as a re-implementation, and we make no claim about that paper on its basis.

We have also implemented that paper's algorithm as published (SAC): a truncated action-value Q_i(s_N, a_N) conditioned on the neighbourhood's joint action, an on-policy TD target on the agent's own reward, and a policy gradient weighted by the sum of the neighbours' action-values. Two deviations: the Q tables are networks, and the critic is fitted to the episodes of one iteration over 20 full-batch passes instead of one update per step. The algorithm assumes finite action sets, so load balancing is excluded and the comparison is on wireless and traffic.

SAC is at parity at 5 agents (GRU: 248.92 against 257.27, p=0.36), behind HygHAPPO at 20 (599.62 against 681.20, p=0.045) and at 50 (772.09 against 1210.18, p=8.4e-5), and far above IPPO and NPPO on wireless. On traffic it is below both, so the graph baseline stays the comparison there and we draw no conclusion from those rows. At 35 agents no method is stable (standard deviations 78 to 242) and we claim no ordering. We report every setting the new baseline was run on, not only those where it is weak, and we do not attribute the gap to the unit alone, since the critic and the update rule differ as well.

The cost falls on the per-agent side. On Hive50 those critics hold 37.7M parameters against 4.6M (38.3M against 5.9M with actors), and more parameters must be fitted from the same transitions. Execution of the averaged policy costs one forward pass, since drawing a head and then an action realises the mixture; training needs all n_i heads only because the score function needs the density. At kappa=2 the neighbourhood already holds 5 of 5, 19 of 20 and 7 of 8 agents, so a larger neighbourhood is a return to a near-centralized critic.

W2. The hyperedge objective is defined on the product policy pi_e, while the data come from the averaged policy. For product policies the total variation is at most the sum of the members' divergences, so the mismatch is bounded by sum of delta_i and enters the bound through phi_e = epsilon_p + sum delta_i. If the heads agree, delta_i = 0 and the aggregation costs nothing. It is largest when an agent belongs to two groups with opposed preferences; with opposite pure heads delta_i = 1/2 is attained, while for r_A = r_B = 1{a_i=1} both heads coincide and the loss is zero although the overlap is maximal. What prices the aggregation is conflict, not overlap. Measured over visited states, delta_i averages 0.7 to 2.6% on wireless and 1.0% on Beijing, reaching 0.67 only at near-tie states; on WC-20 only 1.0 to 1.6% of (agent, step) pairs exceed a total variation of 0.1. The bound uses a supremum and is correspondingly pessimistic. We do not compare aggregation rules.

W3. Hyperedge size enters m_e, through the critic input and the joint action space. Overlap enters delta_i through n_i. The coupling constants epsilon_p and epsilon_r measure the residual dependence on the complement. They are assumption constants, not quantities we estimate, so we do not read the sign off them. Since the method takes a hypergraph as input, connectivity has two axes: more hyperedges adds terms to an additive bound and, with overlap, raises delta_i; larger hyperedges raises m_e, but their effect on epsilon_p and epsilon_r is not determined, only the limit is, since a cover of all agents has no complement. What we observe is behaviour: on wireless IPPO and NPPO are far behind, on Los Angeles IPPO is already best, and on grid-4x2 a group covers half the system. Decomposition helps when a decentralized learner is clearly insufficient and the unit stays small; the two failures are the two ways this can break. In most settings we study HygRL is ahead of both CTDE and the graph baselines; the exceptions are the eight-agent grid, Los Angeles, and the unstable 35-agent point. A degree-preserving randomisation of the hypergraph removes the gain (681.20 to 136.34), so the topology, not the construction, is what matters.

Reviewer_cEaWOpenReview ↗

Thanks for the responses

On W1, I thank the authors for the additional experiments. On W2, I thank the authors for the explanation but still think a simple toy example would be helpful. On W3, my concern remains since the authors are unable to provide a convincing theoretical explanation of how the topology influences the performance of the algorithm and when it is preferred over another scalable MARL approaches.

So, my score remains.

Reviewer_XtRtOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

HygRL decomposes a cooperative multi-agent task into hyperedge-local sub-tasks, trains a local critic and local joint policy per hyperedge in parallel, and averages the per-hyperedge policies at execution. Decomposition error bounds are derived, and three domains are evaluated with up to 55 agents.

Critical strengths
  1. The hypergraph is a pluggable input, CTDE is localized inside each hyperedge, execution is fully decentralized, and the base learner is left unchanged.
  2. Shared PPO backbone, identical hyperparameters across all six methods, and communication constraints matched with the graph baseline.
  3. When the hypergraph collapses to a single hyperedge, the guarantee reduces exactly to that of the embedded algorithm.
Critical weaknesses
  1. The hypergraph MARL methods that the paper explicitly criticizes are never compared against, so the central claim is not tested against its closest competitors.
  2. No random-partition control with preserved hyperedge sizes. Gains therefore cannot be separated from the simpler explanation that each training unit just has a smaller joint action space.
  3. The bound relates the joint return to the sum of local returns, which is not the return of any single policy. It is a consistency bound on the decomposition rather than a suboptimality bound, and no error constant is ever estimated, so no prediction of the theory is checked empirically. One error coefficient enters the bound with a negative sign, so the guarantee does not tighten monotonically as the approximation errors shrink, contrary to what the text claims. Scalability is asserted but not measured: no wall-clock time, memory, parameter count or communication volume is reported, even though the per-agent parameter count grows with the number of hyperedges an agent belongs to. "Consistently outperforms" is contradicted by the small-grid and Los Angeles results, where the decentralized and graph baselines are better.
Questions for authors
  1. What is the hyperedge size distribution in each environment, and how much of the reported gain survives if memberships are randomized while sizes are preserved?
  2. Can the approximation errors be estimated numerically in one small environment, and how does the predicted bound compare with the observed gap?
  3. Since the bound relates the joint return to the sum of local returns, what does it imply about optimality relative to centralized training?
  4. In the small grid and Los Angeles, decentralized and graph baselines outperform HygRL. What characterizes the regime in which decomposition hurts?
  5. Does the advantage persist with a value-based base learner, or is it specific to the PPO family?
1 comment

We thank the reviewer for a specific report.

Corrections. (1) HAPPO implementation: our implementation generated the randomized update order but did not use it, and dropped the importance-ratio accumulation; HygHAPPO embeds the same update, so both carried the defect. Fixed and all runs redone: the margin falls from 1119 to 183 at 20 (GRU) and 1037 to 648 at 50, both still significant, and the ordering is unchanged in 20 of 22 settings, HAPPO leading in two without significance. (2) Graph baseline: its five-agent graph file held access-point ids where agent neighbours were expected; re-run it reaches 98.50/97.90 against 257.2/257.3, ordering unchanged. Our re-audit also found that we had called it a re-implementation of Qu et al. (2022); it is a simple graph-neighbourhood PPO baseline. (3) Agent counts: Beijing 53, Manhattan 47, San Francisco 55, Los Angeles 33. (4) Significance: the script used Student's rather than Welch's; recomputed, no decision changes.

W1. Our closest method is not HYGMA but the graph-based localization line of Qu et al. (2022): it also takes the structure as given, and we compare against its algorithm (SAC) where it applies, and against NPPO. HYGMA estimates its hypergraph from the global system and keeps a centralized critic; we implemented its policy-based version anyway. At 20 and 50 agents it reaches 531–783 against 648–1210 for HygMAPPO/HygHAPPO, significant in three of four settings and not at 20 agents GRU (p=0.062, seeds spanning ±269). It is a re-implementation with coarser grouping, 2–5 groups against our 12 and 14 (Appendix D.1).

W2. We replace the hypergraph by a random hypergraph that keeps every size, degree and environment parameter, changing only membership (14% of incidences retained). The gain disappears: 681.20 and 723.19 become 136.34 and 103.61 (d=12.8, 12.5; p<1e-14). A smaller unit alone does not explain it either: HAPPO, whose unit is the whole system and whose decomposition error is zero, scores 222 and 183 below. Size contributes, structure contributes, neither alone reproduces the result.

W3. (i) Scope. The analysis takes a CTDE algorithm as given and bounds what decomposing it changes, not the quality of the fixed point; we claim nothing about optimality. The corollaries state what HATRL, which we embed as HAPPO, satisfies: no update leaves the local or joint return lower by more than DeReD_eR_e or ∑eMeRe\sum_e M_eR_e, and with a trivial hypergraph Me=0M_e=0, so they reduce to its own guarantee. Theorem 2 is retitled and the corollaries become a subsection. (ii) Constants. They are assumed, not fitted, as in Qu et al. (2020), Zhang et al. (2024) and Ma et al. (2024), none of which estimates them. We measure the one that needs no model, δi\delta_i: 0.7–2.6% on wireless, 1.0% on Beijing, sampled maximum 0.67 at near-ties. We do not evaluate the right-hand side, which needs the surrogate MDPs. (iii) Sign. The term −2ϵp/(1−γ)-2\epsilon_p/(1-\gamma) is exact, the correction for evaluating the auxiliary sum at a=1+ϵpa=1+\epsilon_p, and is compensated by the ϵp\epsilon_p-dependence of F\mathcal F: with x=(1+ϵp)/ϕex=(1+\epsilon_p)/\phi_e, h(x)=1−γx+γxlog⁡γ (x−1)h(x)=1-\gamma^x+\gamma^x\log\gamma\,(x-1) is minimised at x=1x=1, so the derivative is 2[h(x)−(1−γ)]/(1−γ)2≥02[h(x)-(1-\gamma)]/(1-\gamma)^2\ge0. The bound is nondecreasing in every error coefficient (now Lemma 1). (iv) Scalability is comparative: above 20 agents the decomposed learner is ahead in 21 of 22 comparisons, the exception being 35 agents GRU. The largest critic sees ∣e∣≤12|e|\le12 agents against 50, parameters are 1.12–2.65× the CTDE count, execution needs no communication, and we report no wall-clock time because the machines were heterogeneous. (v) "Consistently outperforms" is replaced by two scoped statements; IPPO and the graph baseline win on grid-4x2 and IPPO on Los Angeles.

Q1. Sizes run 2–12: 5 on wireless-20, cliques of 4 in load balancing, 2–5 in traffic. Q2. No: ϵp,ϵr\epsilon_p,\epsilon_r are worst-case quantities over surrogate MDPs we do not materialise, and a sampled supremum is a lower bound; δi\delta_i is measurable, and only 1.0–1.6% of agent-steps on WC-20 exceed a TV of 0.1. Q3. Nothing about optimality: the bound is about the effect of decomposing, and W2 is its experimental counterpart. Q4. No validated structural predictor. The hypergraph does not change how the environment evolves; it captures structure already there, so its statistics describe rather than cause the result. Both failures are settings where the graph baselines already win. Q5. QMIX embeds unchanged, but near-deterministic heads make the mean a mixture of best responses. With Boltzmann heads at τ=0.1\tau=0.1, the five-agent ablation goes from −37.0 under ε-greedy (257.2 for QMIX) to 246.0, and Beijing reaches −5141 against −5422 (p=0.11) with better sample efficiency. We claim no final-return advantage; Appendix D.2.

Comments on the paper

1 comment

General Response to the AC and Reviewers

We thank the AC and the reviewers for detailed, constructive reports. We summarize our contribution to the major concerns raised in review.

Contributions. (i) We propose HygRL, a novel scalable MARL framework which captures higher-order interactions and supports heterogeneous agents, built on a hypergraph representation of the system structure. HygRL takes a hypergraph representation of the system structure, trains one joint policy per hyperedge, and reconciles overlapping hyperedges by mean policy aggregation at execution. The hyperedge, not a graph radius, defines the learning group. Graph-based MARL uses graph distance as a proxy: a κ\kappa-hop radius can include non-interacting agents and miss interacting ones, and enlarging it approaches a global critic. Mean-field MARL generally requires a degree of homogeneity and exchangeability; HygRL requires neither. The benefits are: higher-order interactions modeled directly, broad applicability to heterogeneous agents, training scaled by the maximum hyperedge size rather than nn, high compatibility with existing CTDE methods, preserving decentralized execution without communication.

(ii) Existing hypergraph MARL methods mainly focus on learning or constructing the hypergraph and typically retain a global critic. We instead study how a given hypergraph affects MARL performance and give, to our knowledge, the first two-level decomposition result for hypergraph-based MARL. Theorem 1 bounds how closely each hyperedge-local MDP approximates the true local dynamics; Theorem 2 bounds the gap between the return of the behavior policy πˉ\bar{\pi} and the sum of the local returns. This separates local approximation from global recombination, making the effect of the hypergraph explicit.

(iii) Following the reviews, we further strengthened the experiments. Our goal is to answer three questions: whether the benefit over CTDE, graph, hypergraph and value-based baselines holds; whether the gain comes from the hypergraph structure; and how HygRL scales. The design removes implementation confounds, compares against these baselines, and uses a random hypergraph construction that changes only hyperedge membership while preserving degree, hyperedge size, hyperedge count and environment parameters. The results show the benefit in 20 of 22 settings, its disappearance in the random hypergraph experiment, and its largest margins at the largest sizes.

Theory. We thank Reviewer 3F1L for pointing out two minor errors. All errors are now corrected as the revised version. In B.6, MeM_e, the total deviation of a single hyperedge, has the corrected order O(me(me+log⁡nmax⁡))O(m_e(m_e+\log n_{\max})): it depends on hyperedge size and overlap, not explicitly on the total number of agents nn.

Experiments. We thank Reviewer 3F1L for the implementation check that led us to correct and rerun the affected experiments and significance tests, and Reviewers XtRt, cEaW and k3DG for prompting the additional comparisons and experiments. We added the hypergraph baseline HYGMA (Liu and Li, 2025), implemented in the same code base with a MAPPO-style backbone, the SAC baseline of Qu et al. (2022), a QMIX instantiation (Rashid et al., 2018), and the random hypergraph experiment.

In comparison, the Hyg variants outperform their CTDE counterparts in most settings; on wireless, HYGMA is behind HygMAPPO at 20 and 50 agents, and SAC is at parity at five agents but behind at the two larger sizes. The random hypergraph experiment removes the gain, confirming that the benefit comes from proper decomposition.

In terms of scalability, across 5 to 55 agents, the CTDE baselines become less effective at the larger sizes, while the same learners inside our framework improve clearly. The benefit is visible across domains and is most pronounced at the larger sizes.

Cost. The parameter increase over CTDE is controlled: total parameters are 1.12--2.65$\times$ the CTDE counterpart (median 1.75), and this increase is what enables the scale-up gain. Compared with graph-based baselines such as SAC, HygHAPPO uses fewer parameters, for example 5.9M versus 39.8M on the 50-agent wireless setting.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.