- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies strict coordination in multi-agent reinforcement learning under intermittent communication. The authors first introduce the Multi-Agent Counting (MAC) benchmark and theoretically show that parameter-shared decentralized policies cannot reliably achieve exact coordination under symmetric observations, while identifier-based solutions may fail when team membership changes. To address this issue, they propose SDec-MAT, a semi-decentralized Multi-Agent Transformer that masks attention according to the real-time communication graph and conditions each agent’s action on accessible predecessor actions. Experiments show strong performance on exact-coordination tasks and improved zero-shot robustness to agent dropout, network partitions, and changing team sizes.
Critical strengths
-
Clear and meaningful problem formulation. The paper identifies a structural limitation of parameter-shared decentralized policies in exact-count coordination tasks and supports this observation with formal theoretical analysis.
-
Good alignment between theory, benchmark, and method. The proposed MAC suite is specifically designed to expose strict coordination failures, while SDec-MAT directly addresses them through communication-aware autoregressive decision making.
-
Strong zero-shot robustness. SDec-MAT generalizes well to agent dropout, team partition, and larger multi-target settings, substantially outperforming identifier-based decentralized baselines.
-
The method remains competitive on standard MARL benchmarks. Although designed for exact coordination, SDec-MAT does not suffer a severe performance loss on SMAC.
Critical weaknesses
-
The methodological novelty is moderate. SDec-MAT mainly extends MAT with communication-graph masking and predecessor-action conditioning; the strongest novelty lies more in the problem formulation and theoretical analysis than in the architecture itself.
-
The proposed MAC tasks are relatively synthetic. Since they are explicitly constructed around exact-count coordination, it remains unclear how frequently the identified limitation appears in more realistic and complex multi-agent applications.
-
The empirical validation on standard benchmarks is limited. On SMAC, SDec-MAT is only comparable to MAT-Dec and is slightly worse on some maps, suggesting that the proposed mechanism provides limited benefit when exact coordination is not required.
-
Sequential decoding introduces additional latency. The decision delay increases with sub-team size, and the method assumes that the communication graph remains fixed during generation of a joint action, which may restrict practical deployment in highly dynamic systems.
Questions for authors
-
The MAC benchmark is specifically designed around exact-count coordination. Could the authors further discuss how common this type of coordination requirement is in real-world multi-agent applications?
-
SDec-MAT relies on sequential predecessor-action conditioning. How does the resulting communication and decision latency scale with larger teams, and what are the practical limits of this design?
-
The method assumes that the communication graph remains fixed during one joint-action generation process. How sensitive is SDec-MAT to faster topology changes or delayed/lost messages within a decision step?
-
On standard SMAC tasks, SDec-MAT is only comparable to MAT-Dec and is slightly worse on some maps. Could the authors clarify in which classes of tasks predecessor-action conditioning is expected to provide consistent benefits beyond exact-count coordination?
2 comments
gdSk - W4/Q2
W4/Q2. Latency of sequential decoding and its scaling with team size. Agreed, and now quantified. The number of action rounds in a decision is the number of agents on the longest path in the communication graph that follows the decoding order (Section 4.3). It is bounded by the size of the connected sub-team, not of the team, and agents that are not connected decide in parallel. The new Appendix E.4 reports the measured counts for every Navigation condition (Table 8): with six agents, a decision takes between 3.19 and 4.32 action rounds on average, against 6 on a complete graph, the case in which SDec-MAT is MAT. For larger teams the cost grows with the longest chain of connected agents in decoding order and reaches N only when such a chain spans the whole team. The practical limit is that the rounds of a sub-team complete within one decision epoch, during which the graph is assumed fixed. Appendix E.4 states that this cost is reported in protocol rounds, and that their duration in real time depends on the communication hardware and is outside the scope of the paper.
gdSk - Q3
Q3. Topology changes and delayed or lost messages within a decision. SDec-MAT handles topology changes between decisions, which our tasks contain: Aerial Ordering and Charging Rendezvous evaluate changing local connectivity, and Navigation recomputes the graph at every step. While one joint action is generated, it assumes a fixed graph and reliable delivery. For lost messages we now report a measurement (Appendix E.4, new Table 9): each predecessor-action message is lost independently with probability ε at every decision, while observations are still shared, so the test measures how far the trained policy tolerates missing actions. The policies are not trained for this. The frozen exact-rule policies tolerate moderate loss: up to ε = 0.2, success stays within 1.4 points of its value without loss, and false captures rise from 0.53 to 0.83 per episode at −1 and from 0.58 to 1.23 at −5 with optimism. With every action message lost, success falls to 67.0% and 62.7%: connected agents then receive no predecessor action at any decision, a situation that does not occur in training, where connected agents always receive their predecessors' actions. Delayed messages and topology changes within a decision are not tested. Making the policy robust to lost messages, for example by letting an agent predict a missing predecessor action or by training with lost messages, is outside the scope of this work and left to future work; the Conclusion lists message loss, delay and topology change within a decision among the limitations.
We thank reviewer gdSk for the positive and constructive review. We address each point below.
gdSk - W1
W1. Novelty in the problem formulation and the theoretical analysis. Agreed: the novelty lies in the problem formulation and the theoretical analysis, and the architecture is designed to serve them. The paper formulates exact-count coordination and its diagnostic suite, proves that conditionally independent policies cannot reach an exact count reliably (Theorems 4.1 to 4.3), and then asks for the smallest mechanism that removes this obstruction under partial communication. SDec-MAT is that mechanism: attention and decoding follow the live communication graph, so each agent conditions on the observations and predecessor actions of its neighbors. Because it changes MAT in this one respect, the comparison with MAT-Dec, which lacks only predecessor-action conditioning, isolates its effect. The revision extends the analysis: the new Proposition C.2 in Appendix C.3 shows that conditioning on predecessor actions raises an agent's optimal response value exactly when no single action is optimal for every predecessor action it can receive, which says where the mechanism has value beyond exact counts.
gdSk - W2/Q1
W2/Q1. We thank the reviewer. Exact or bounded participation is common in multi-robot systems. In Gerkey & Matarić (2004), a package's size fixes how many robots must carry it, so each package needs a team of exactly that size, as each target in Aerial Ordering. In Asghar et al. (2023), energy-limited UAVs recharge on ground vehicles that can each charge only a limited number of UAVs at a time, as at the two-port station of Charging Rendezvous. In Berman et al. (2009), robots without communication spread over several sites in target proportions, as the zone quotas of Team Partition, but the count at each site is correct only on average. In Al-Husseini et al. (2026), joint tasks such as pushing a large box or a joint evacuation pickup succeed only when the required agents act together under intermittent communication. Section 4.2 now discusses these applications with these references. Proposition C.2 (Appendix C.3) states when predecessor actions help beyond exact counts (see W3/Q4).
gdSk - W3/Q4
W3/Q4. Standard benchmarks, and the task classes in which predecessor-action conditioning helps. We address the second part with a new result and the first by stating the role of SMAC.