- 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
-
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.
-
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
-
Appendix A.6 claims (), but its explicit expression contains (m_e\psi_e), where (). Under the stated assumptions, this term can scale as ().
-
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.
-
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.
-
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.
-
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
-
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?
-
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?
-
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?
-
Could the authors verify the NPPO neighborhood construction and provide a graph-based localized CTDE baseline with matched critic capacity and group size?
-
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
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.
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.