acceptodds
Under review as a conference paper at ICLR 2027

SDec-MAT: Sequence Modeling for Semi-Decentralized Multi-Agent Reinforcement Learning

Abstract

In real-world multi-agent systems, imperfect communication makes purely centralized execution challenging. Centralized training with decentralized execution is a common approach under constrained communication, typically with parameter sharing and often with observation sharing among connected neighbors. These methods perform strongly on common benchmarks, which rarely demand strict coordination. Their tasks are either solvable without it or expose information that lets independently acting agents coordinate implicitly. We introduce the Multi-Agent Counting (MAC) diagnostic suite, in which an exact number of agents must take a specified action while communication links change over time. We prove that parameter-shared decentralized policies cannot reliably solve such tasks when agents' observations are identical, and that, when team membership varies, even agents with distinct observations cannot in general learn to guarantee the exact count. We propose the Semi-Decentralized Multi-Agent Transformer (SDec-MAT), which builds on the Multi-Agent Transformer and the Semi-Decentralized POMDP framework. SDec-MAT masks its attention with the current communication graph, so each agent sees only its neighbors' observations and chooses its action based on the actions of neighbors that act before it, while agents without links act independently. Because connected sub-teams decide jointly, SDec-MAT attains high success across the MAC suite, where baselines given agent IDs succeed only inconsistently, and generalizes zero-shot to agent dropouts, team partitions and larger multi-target teams better than these baselines. We further extend a graph-based particle navigation task into a joint decision-making task in which targets are captured only by simultaneous actions of at least or exactly three agents. Decentralized baselines complete the task under the at-least rule but with frequent false captures, whereas among methods with nonzero success, SDec-MAT makes the fewest false captures in every condition and is the only method to succeed under the exact rule with a high false-capture penalty. SDec-MAT also remains competitive on the StarCraft Multi-Agent Challenge.

Primary area:
reinforcement learning
Keywords:
multi-agent reinforcement learning, semi-decentralized execution, multi-agent transformer, sequence modeling, communication constraints, coordination, zero-shot generalization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_gdSkOpenReview ↗
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
  1. 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?

  2. 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?

  3. 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?

  4. 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

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.

  • Task classes. The new Proposition C.2 (Appendix C.3, with proof and an exact-count example) shows that, with an agent's input and the other agents' policies fixed, conditioning on predecessor actions raises the agent's optimal response value exactly when no single action is optimal for every predecessor action it can receive. The opening paragraph of Section 5.3 now states this criterion.
  • SMAC. SMAC is our check that SDec-MAT also works on a standard benchmark that does not require exact counting, as the reviewer notes among the strengths. Its heterogeneous units observe different positions, health and types, so independent agents can take different roles without predecessor actions, and the two methods reach comparable win rates: on par on 3s5z and 5m_vs_6m, and slightly lower for SDec-MAT on MMM and 8m_vs_9m. SDec-MAT therefore remains competitive on a standard benchmark.

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.

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

The paper studies exact-count coordination under symmetric or membership-blind inputs. SDec-MAT restricts MAT’s observation attention and autoregressive action dependencies to the current communication graph. Experiments cover the MAC diagnostic suite, roster changes, joint-action navigation, and four SMAC maps.

Critical strengths
  1. A useful diagnostic task. MAC distinguishes selecting the right number of participants on average from selecting exactly that number reliably. The impossibility results identify the input and independence assumptions responsible for the gap (Section 4.1).

  2. A well-chosen architectural control. MAT-Dec shares the masked encoder and critic but removes predecessor-action conditioning. This is the most direct evidence that action dependence, rather than the Transformer architecture alone, explains the gain (Section 4.3).

  3. Promising evidence beyond the impossibility construction. Spatial observations in navigation allow an independent coordination rule. In the reported training rollouts, SDec-MAT reduces false captures and is the only tested method to succeed in the exact/high-penalty condition (Section 5.3).

Critical weaknesses
  1. Final-policy coordination is not established in navigation. Tables 3 and 5 report three-seed training rollouts with group exploration active for all methods. This is a controlled training comparison, but not a separate evaluation of the learned policies. Since navigation is the main evidence beyond the counting construction, this gap materially limits the empirical case (Appendix E.3).

  2. The structural explanation for ID-equipped baselines is not established. Theorem 4.3 requires identical complete inputs for an agent across changing rosters. Sections 5.1 and 5.2 invoke it without establishing this for the communication baselines. Aggregating one-hot IDs can reveal membership; aggregation alone does not imply membership blindness. The observed failures therefore need to be distinguished from representational impossibility.

  3. Theorem 4.2 omits tied boundary and interior optima. The absence of a strictly dominating boundary does not imply that every maximizer is interior. This is a local error in the classification of optimal shared policies, not a failure of Theorem 4.1 or the uniform-penalty result (Appendix B.3).

Questions for authors
  1. Do the saved navigation policies retain their success and false-capture advantages in separate evaluation with group exploration disabled?

  2. Which ID-equipped communication baselines actually satisfy Condition 4, after including received messages in their complete inputs? If membership can be inferred, please interpret those failures as learning or generalization failures rather than an impossibility result.

  3. Could Theorem 4.2 include tied boundary and interior maxima? With N=4, K=3 and rewards (0, −1/16, 1/24, 1/16, −1/4), expected reward is −p(p−1/2)², maximized at both 0 and 1/2. This is a local correction; it does not affect Theorem 4.1.

2 comments

We thank reviewer JCv3 for the careful and constructive review. We address each point below.

JCv3 - W1/Q1

W1/Q1. Final-policy evaluation in Joint-Action Navigation. Agreed. We address this with a separate evaluation of the saved policies with group exploration off, which now replaces Table 3. The answer to Q1 is yes: the saved policies retain their success and their false-capture advantage.

We retrained all four methods for 5M environment steps with five seeds in every condition. Each frozen 5M-step policy is evaluated on 200 episodes from initial states shared across methods, with group exploration off and actions sampled from the policy.

Table 3 of the revised paper. Values are mean ± std over 5 seeds. Opt. marks optimistic advantages in training. Success is the share of episodes in which all three targets are captured; FCap is the number of false captures per episode.

Success rate (%).

ConditionOpt.SDec-MATInforMARLMAT-DecMAPPO
At least 3, −1–99.0 ± 0.499.4 ± 0.499.3 ± 0.898.1 ± 1.0
At least 3, −5✓98.5 ± 0.998.9 ± 0.497.6 ± 2.658.8 ± 41.4
Exactly 3, −1–95.8 ± 7.294.1 ± 2.90.0 ± 0.051.1 ± 46.9
Exactly 3, −5✓91.7 ± 4.80.0 ± 0.00.0 ± 0.00.1 ± 0.2
Exactly 3, −5–0.0 ± 0.00.0 ± 0.00.0 ± 0.00.0 ± 0.0

False captures per episode (FCap).

ConditionOpt.SDec-MATInforMARLMAT-DecMAPPO
At least 3, −1–0.152 ± 0.0421.912 ± 0.1970.136 ± 0.0352.421 ± 0.117
At least 3, −5✓0.187 ± 0.0310.835 ± 0.2550.324 ± 0.1762.431 ± 1.368
Exactly 3, −1–0.531 ± 0.6473.755 ± 0.5180.731 ± 0.3924.406 ± 2.589
Exactly 3, −5✓0.584 ± 0.3990.707 ± 0.3830.662 ± 0.3913.100 ± 0.664
Exactly 3, −5–0.015 ± 0.0170.001 ± 0.0020.001 ± 0.0020.000 ± 0.000
  • Success. SDec-MAT succeeds under both rules and both penalties. Under the exact rule it succeeds in 95.8% of episodes at −1 and in 91.7% at −5 with optimism, where no baseline exceeds 0.1%. MAT-Dec, which differs from SDec-MAT only in lacking predecessor-action conditioning, stays at 0.0% under the exact rule, so the success gap there is attributable to that conditioning.
  • False captures. Where InforMARL succeeds, SDec-MAT succeeds about as often with several times fewer false captures: 0.152 against 1.912 under the at-least rule at −1, 0.187 against 0.835 at −5, and 0.531 against 3.755 under the exact rule at −1. MAPPO makes between 2.421 and 4.406 in the same conditions. Under the at-least rule, where excess participation is harmless, MAT-Dec and SDec-MAT are comparable.

The paper follows this evaluation throughout. The opening paragraph of Section 5.3 now says that all methods are trained for 5M steps with five seeds and that Table 3 is a separate evaluation of the frozen policies with group exploration off. The results paragraph of Section 5.3 reads Table 3 as above. The abstract now states that, under the exact rule, SDec-MAT succeeds where the same architecture without this conditioning fails, with far fewer false captures than the baselines that succeed; and the Conclusion now says that SDec-MAT coordinates more reliably than the baselines under the exact rule. Appendix E.3 is now a training and evaluation protocol: it states the 5M-step budget and the five seeds, has a new paragraph on the evaluation, and its settings table (Table 6) covers all five conditions. Appendix E.2 adds the targets captured per episode and the variation across SDec-MAT's seeds.

JCv3 - W2/Q2

W2/Q2. We thank the reviewer and agree that ID-bearing messages reveal membership. In the submission, CommNet, TarMAC and InforMARL also carried the IDs in their messages or graph nodes, so Condition 4 did not hold for them. In the revision, the baselines receive their IDs only in their own policy input, not in their messages (Section 5.1), so an agent cannot tell which teammates are present and Condition 4 holds for all baselines. All policy-gradient methods, including SDec-MAT, were retrained with the same random seeds under matched settings. All ID-equipped baselines now sit at the membership-blind ceilings of Table 1 (0.700 for Drop 1 and 0.600 for Drop 2, within sampling error; stated in Section 5.1 and derived in Appendix D.4) and below the ceiling of 0.414 in Split, as Theorem 4.3 predicts, while SDec-MAT attains 1.000 without retraining.

To make the reviewer's distinction explicit, the new Appendix H retrains CommNet, TarMAC and InforMARL with the IDs also inside their messages or graph nodes. Condition 4 then fails, and the survivors of a dropout can tell who is missing: CommNet learns to let the K lowest IDs it hears act, solving Drop 1 (1.000) and reaching 0.966 in Drop 2. The theorem's assumption is therefore what separates the two cases, and Section 5.1 now reports both. Where membership can be inferred, we interpret the remaining failures as the reviewer suggests, as failures to learn or generalize rather than as an impossibility result (Appendix H): TarMAC (0.534 in Drop 1, 0.399 in Drop 2) and InforMARL (0.764 and 0.601) do not learn such a rule, and on Team Partition every baseline stays far below SDec-MAT with IDs in its messages as well (Figure H.2). Conversely, with IDs in its graph nodes InforMARL can tell which agents are docked in Charging Rendezvous, and its success there rises toward SDec-MAT's (Figure H.2).

What none of these baselines does is generalize beyond the training roster. In Split, where ten agents share the five training IDs, no baseline exceeds 0.413, against 1.000 for SDec-MAT; in multi-target Aerial Ordering, SDec-MAT remains the best method in every configuration, with 0.985 and 0.969 under Isolated communication and Exact split against at most 0.859 and 0.757 for the baselines (Tables 2 and 14). SDec-MAT needs no identifiers in its policy input: each agent counts the coordinating actions of its accessible predecessors, a quantity that depends neither on which agents are present nor on how many there are.

JCv3 - W3/Q3

W3/Q3. We thank the reviewer for this careful counterexample, which is correct: with N=4, K=3 and r = (0, −1/16, 1/24, 1/16, −1/4), E[r|p] = −p(p−1/2)² attains its maximum 0 at both p=0 and p=1/2. Our proof of case (ii) showed that an interior maximizer exists, but not that every maximizer is interior, since the best boundary case may tie with an interior point. We have restated Theorem 4.2 (Section 4.1, proof in Appendix B.3) as a statement about the set of maximizers, with two cases: (i) all maximizers are deterministic if at least one boundary case yields a strictly greater return than every p ∈ (0,1); (ii) otherwise at least one maximizer is stochastic, with p† = K/N as the unique maximizer under uniform miscoordination penalties. The reviewer's example falls under case (ii): no boundary case dominates strictly, and the interior point p = 1/2 is a maximizer alongside p = 0. Pickup Consensus contains both cases (new paragraph in Appendix D.4): with its reward and horizon, the return-maximizing shared policy is stochastic for K = 2 and K = 4 (case ii) and never attempts for K = 3 (case i). As the reviewer notes, Theorem 4.1, the uniform-penalty result and all experiments are unaffected.

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

This paper studies exact-count coordination in cooperative multi-agent reinforcement learning, where exactly KK agents must take a designated action. It introduces the Multi-Agent Counting (MAC) suite—Aerial Ordering, Charging Rendezvous, and Team Partition—and shows that, under identical observations, parameter sharing, and conditionally independent execution, the number of coordinating agents follows a Binomial distribution, so an interior target KK cannot be reached with probability one. It also shows that the deterministic identifier-to-action mappings required for exact success may become infeasible when the active team changes without changing an agent's input. SDec-MAT adapts the Multi-Agent Transformer to the current communication graph: masked attention aggregates only neighbours' observations, and agents are decoded autoregressively in index order, each conditioning on the realized actions of accessible lower-index neighbours; isolated agents act independently. Experiments cover Pickup Consensus, including zero-shot dropout and partition tests, the MAC suite with multi-target generalization, Joint-Action Navigation requiring at least or exactly three simultaneous CAPTURE actions, and four SMAC maps compared with MAT-Dec.

Critical strengths

SMAC and MPE do not test whether exactly KK agents take the same action. Under identical observations, a shared policy, and independent actions, five agents cannot beat success rates of 0.3460.346, 0.3460.346, and 0.4100.410 for K=2,3,4K=2,3,4. Forcing that shared policy to be deterministic does not help: every agent acts or none does, so the count is 00 or 55. Separate deterministic choices matter only when agents can have different probabilities. Theorem 4.3 says that if an agent's input stays the same across team compositions and no 00-11 assignment satisfies all of them, no conditionally independent policy can hit the exact count in every composition. Pickup Consensus is the identical-observation setting. Its dropout variants are what Theorem 4.3 is about. MAT-Dec keeps the same encoder, critic, and hyperparameters and only drops predecessor actions. On Team Partition it stays near zero, while SDec-MAT reaches about 0.90.9 without the agent IDs given to the baselines. The masked decoder can count predecessor actions when those predecessors are exactly the active ones. Otherwise the count can be wrong.

Critical weaknesses

W1 Figure 3 does not test Theorems 4.1 or 4.2. Both need identical observations, a shared policy, and a reward that depends only on the count. None of the three MAC tasks has that reward: Aerial Ordering penalizes mean distance, Charging Rendezvous gives −100-100 if any battery is depleted, and Team Partition pays per zone and adds −25-25 for a missed window. Aerial Ordering is also heterogeneous and includes the connected-worker count. Charging Rendezvous's five observation dimensions are not listed, and agents start at different distances. Section 5.1 says static IDs break Condition 2, and Section 5.2 gives every baseline those IDs. Only Team Partition changes who is active. Theorem 4.3 is one count, and the paper applies it to these quotas without a separate argument.

W2 Pickup Consensus is fully connected, so Equation (1) is MAT's chain rule, and the critic bias ηΛ\eta\Lambda does not change the softmax. The paper says MAT redraws the order every iteration, while SDec-MAT keeps it fixed. SDec-MAT's own width is stated, one block and one head at width 64 in Table 7, but MAT's width is not, so a width-matched MAT run is not there. The experiments compare only with MAT-Dec.

W3 The three tests are defined. The paper does not say whether KK is redrawn, or whether a K=4K=4 episode stays in the denominator, and it limits Theorem 4.3 to K∈2,3K\in2,3. If KK stays uniform on 2,3,42,3,4 and those episodes count, Drop 2 cannot exceed 2/32/3. SDec-MAT is 1.0001.000 and CommNet is 0.7520.752. No Drop is 1.0001.000, so an independent policy has exactly KK deterministic actors. If they still cannot tell who dropped, Drop 1 is at most 0.400.40 and Drop 2 at most 0.1330.133. Every Drop 2 entry is above 0.1330.133, including TarMAC at 0.549±0.1730.549\pm0.173. Without using the full-team result, Drop 2 is still at most 0.5330.533, and every baseline except TarMAC is above it. On Drop 1, every baseline except CommNet (0.550±0.2130.550\pm0.213) is clearly above 0.400.40. Split reuses five one-hot IDs. Pickup Consensus states the success rule, but it gives no reward function, horizon, number of evaluation episodes, or seed count.

W4 Tables 3 and 5 are training rollouts with exploration on, over 3 seeds. The −5-5 penalty is tied to optimistic advantages, and the adoption probability and step budget change with the rule. Appendix E.2 says these rows cannot be attributed to the penalty or the capture rule. Under exactly three at −5-5, every other success rate is 0, so the abstract's claim about nonzero methods is empty. In the other three conditions SDec-MAT's success is not higher.

W5 Execution waits on a fixed index order. The graph stays fixed during the decision, and existing links are assumed to deliver. A step takes at most NN rounds, and that number is reached only when GtG_t has an index-increasing path through every agent. That cost is not in the horizon or the reward, and no round count or latency is reported. The experiments do not drop, delay, or change links during decoding. Joint-Action Navigation is not always complete. SMAC uses radius 3, below sight range 9, is compared only with MAT-Dec, and is slightly lower on MMM and 8m_vs_9m.

W6 MAPPO, CommNet, and TarMAC use 5-step returns, batches of 10 episodes, and clip 0.5. InforMARL uses GAE, but 10 environments and clip 0.5. SDec-MAT uses 32 environments and clip 10. MAT-Dec shares that setting and stays near zero on Team Partition, so that gap is not the hyperparameters. Figures 2 and 3 and Tables 1 and 2 give no seed count. The Team Partition text says the quota and one arrival bit, but Table 4 lists 14 dimensions. RbonusR_{\text{bonus}} has no value, the −25-25 penalty is for a window missing from Equation (14), and Φ(s)\Phi(s) is only described in words.

Questions for authors

Q1 Drop 1, Drop 2, and the split are defined. After a dropout, is KK redrawn, and does a K=4K=4 episode stay in the denominator when only three agents remain? In Split each baseline ID is used by two agents. How are SDec-MAT's indices assigned there?

Q2 Why is MAT absent from Figure 2 and Table 1? On this fully connected task, Equation (1) is MAT's chain rule.

Q3 What are Team Partition's 14 observation dimensions? The text says every present agent sees the same thing, and also that the observation includes its own arrival bit, while agents arrive in two waves. Is that bit the same for every agent? Condition 4 requires Hi(su)=Hi(sv)H_i(s_u)=H_i(s_v) when agent ii belongs to both active sets. Do these 14 dimensions stay the same in that case?

Q4 Can success and false captures be reported with exploration turned off? All four methods use the same group exploration. The paper points out that every baseline still fails under exactly-three at −5-5, so that exploration does not explain those failures. It does not make the same claim for SDec-MAT. Within the exact rule, both the −1-1 and −5-5 rows use 4M steps and padopt=0.5p_{\text{adopt}}=0.5. Optimistic advantages are off at −1-1 and on at −5-5. Those two rows therefore differ by the penalty and by optimistic advantages, not by the step budget. The step budget changes with the capture rule, 2M for at-least and 4M for exact. What is exactly-three at −5-5 without optimistic advantages?

Q5 The paper states that one step uses at most NN rounds. It does not report how many rounds or messages the experiments used. How does an agent know the shared index without receiving an identifier? What is the success rate if that index order is randomly permuted? The protocol assumes that existing links deliver and that the graph stays fixed. What happens if a predecessor action is lost, or the graph changes, during the decision?

Q6 How many seeds and evaluation episodes are behind Figures 2 and 3 and Tables 1 and 2? MAPPO, CommNet, and TarMAC use 5-step returns, batches of 10 episodes, and clip 0.5. InforMARL uses GAE, as SDec-MAT does, but 10 environments and clip 0.5. Were these four tuned under the same budget?

8 comments

We thank reviewer oRwq for the thorough and precise review. We address each point below.

oRwq - W1

W1. We thank the reviewer. The main text stated Condition 1 too loosely. We clarify it and show how the reward of each task meets it.

Coordination state. As in Appendix B, Conditions 1–3 are stated at a coordination state s, not for the whole game, and r(X) is the expected return-to-go at s given the coordination count X. Rewards collected before s, such as navigation, step and shaping terms, do not depend on the decision at s; they shift the return but do not move its maximizer. The success ceiling of Eq. (5) needs no reward assumption at all (new Corollary B.1). We have rewritten the opening of Section 4.1 to introduce s explicitly.

Each task at its coordination state:

Pickup Consensus: all five agents receive the same observation at every step. A pickup by exactly K agents gives +10 and any other nonzero count gives −10; both end the episode. X = 0 costs only the −0.3 step penalty. r(X) is maximized at X = K ∈ {2, 3, 4}.

Aerial Ordering: the sensor cannot lift (PICKUP is reserved for workers sharing the target cell with the sensor, Appendix D.1), so the agents that decide at s are the workers, which are homogeneous. s is reached when more than K free workers are assembled on the target and connected to the sensor. Each of them observes (1, K/K_max, 0, m/(N−1), 1): the connected-worker count m is the same for all of them, so their observations are identical. A lift by exactly K workers gives +20 (10 for the lift, 10 for completion); any other nonzero count gives −20 and ends the episode. The step penalty, which shrinks as the team approaches the target, is collected before s and drives the workers to it.

Charging Rendezvous: s is reached when a cohort of three drones docks at a station with two free ports. Each drone is dispatched with exactly the charge its trip needs, so all arrive with the same residual battery b0. Their five observation dimensions, now listed in Appendix D.2 (on the charger, battery level, charging, connected, satisfied), are therefore identical: (1, b0, 0, 1, 0). If X does not exceed the free ports, all requesters are admitted, and each drone that reaches the target level earns +10; otherwise all requests are rejected with −5 per excess requester; if no drone requests, each idle port costs −0.5 while the docked drones wait. The return-to-go is maximized when X equals the number of free ports. A shaping reward for each cell of progress toward the station is collected before s and brings the drones to it.

Team Partition: s is the step at which the commit gate opens, with six active agents whose 14-dimensional observations are identical (see Q3). The decision reward is 10 per zone whose quota is met, plus 10 if all quotas are met, and −20 otherwise (−25 if the gate is not used); it depends only on the counts per zone. Approach shaping and step costs are collected before s and bring the agents to the staging cell.

oRwq - W1 (continued)

Flow of the experiments.

(1) Pickup Consensus satisfies Conditions 1–3 exactly and tests Theorems 4.1–4.2. Without IDs, the policy-gradient baselines settle at stochastic behavior near the shared-policy ceiling and QMIX at the deterministic no-attempt behavior, the two kinds of shared policy in Theorem 4.2, while SDec-MAT solves the task (Figure 2a). Since an episode continues until some agent picks up, the per-episode ceiling is 0.381, 0.349 and 0.410 for K = 2, 3, 4 (average 0.380), slightly above the per-step values of Eq. (5); both are now given in Section 5.1 and Appendix D.4.

(2) Unique IDs break Condition 2, and with them the baselines solve Pickup Consensus on the training team (Figure 2b). Dropout and split change the sub-team at test time. The survivors cannot tell who is missing, and Theorem 4.3 shows that no such policy can guarantee the count for every sub-team. The ID-equipped baselines stay at the resulting ceilings in Drop 1 and Drop 2 (0.700 and 0.600, within sampling error) and below it in Split (0.414), now stated in Section 5.1, while SDec-MAT attains 1.000 without retraining.

(3) The coordination states of the three MAC tasks satisfy Conditions 1–3 as shown above, so we give the baselines IDs in their policy inputs there, and Theorem 4.3 applies to all three: the sub-team at s changes across episodes while each agent's ID does not. In Aerial Ordering it is the set of workers that have reached the target, in Charging Rendezvous the randomly drawn cohort, and in Team Partition a random six of the nine agents. Team Partition has one quota per zone, and Theorem 4.3 applies in its multi-action form (Appendix C.1): exchanging an active agent for an absent one forces all six active agents to choose the same zone, whereas every quota is positive, so no ID rule meets the quotas. Theorem 4.3 removes the guarantee at s; what this costs depends on the task. Under the matched settings, CommNet, TarMAC and InforMARL also reach high success in single-target Aerial Ordering, while the baselines remain well below SDec-MAT in Charging Rendezvous and Team Partition (Figure 3, Section 5.2), and below it in Aerial Ordering with several concurrent targets (Table 2). The new Appendix D.5 explains this for Aerial Ordering: by Theorem 4.3, a valid ID rule exists when the count m of workers at the target equals K (all of them lift), not when m > K and some worker is absent, since that worker can be exchanged for a present one. The baselines therefore succeed when workers arrive one at a time, so that m reaches K; in episodes where workers arrive together and m jumps past K, their success drops to 0.31–0.47 (Table 5), while SDec-MAT keeps 0.94–0.97. These baselines receive their IDs in their own policy input only, for which Condition 4 holds; with IDs also in their messages or graph nodes, Condition 4 fails, and those results are in Appendix H.

Appendix D now gives the full reward and the coordination state of every task, and Sections 4.1, 4.2, 5.1 and 5.2 are revised accordingly.

oRwq - W2/Q2

W2/Q2. As the reviewer observes, on this fully connected task Eq. (1) is MAT's chain rule and the critic bias is constant across pairs. This is by design and one of the main ideas of the paper: under full communication, SDec-MAT is MAT. SDec-MAT spans the communication spectrum of the SDec-POMDP with a single model, becoming MAT under full communication (MPOMDP) and MAT-Dec with self-loops only (Dec-POMDP). On Pickup Consensus, SDec-MAT is therefore a width-matched MAT (1 block, 1 head, d = 64); on this task the global state equals the observation (Appendix D.4), so the critic's state input adds nothing either. Its results in Figure 2 and in the No Drop, Drop 1 and Drop 2 columns of Table 1, where the remaining agents are still fully connected, are MAT's results. The only remaining difference in the actor, the decoding order, is immaterial here: observations are identical, so permuting the agents leaves the network's input unchanged and only relabels which agent receives which action, while the reward depends only on the count. Under Split and in the MAC suite, MAT cannot be executed, because it would decode disconnected agents in a single chain and thus require communication that does not exist; MAT-Dec is the variant that remains executable there, which is why the experiments compare with it. We now state this explicitly in Section 4.3, in our contributions and in the caption of Figure 2; Section 3.2 already notes that MAT is executable only when the communication graph is complete.

oRwq - W3/Q1

W3/Q1. We thank the reviewer; the protocol was underspecified.

(i) After a dropout, K is redrawn uniformly from the values feasible for the remaining team (K ∈ {2,3} for Drop 1, K = 2 for Drop 2), independently of which agents dropped, who are chosen uniformly at random. No episode with K = 4 arises, so every episode in the denominator is solvable and the 2/3 and 0.533 bounds do not apply.

(ii) The bounds of 0.40 and 0.133 assume that the survivors keep the K lifters of the full team; under our protocol, in which K is redrawn among the feasible values, that assumption would give 0.5 and 0.3. However, the first observation field is K/n, where n is the current team size (the team-size field is kept at its training value), so after a dropout the survivors receive an input not seen in training, and the ID-to-action mapping at that input need not be the trained one. The correct bound is therefore the maximum over all membership-blind ID-to-action mappings: 0.700 for Drop 1, 0.600 for Drop 2 and 0.414 for Split. For example, in Drop 1 with K = 3 the survivors see 3/4, and the best mapping lets four IDs lift, which succeeds exactly when one of them has dropped (probability 0.8). These ceilings are now stated in Section 5.1, with their derivation in Appendix D.4. The baselines' 0.36 in Split is the value of a mapping whose lifter sets for K = 2, 3, 4 are nested (0.365); the ceiling of 0.414 needs sets that are not nested (Appendix D.4).

(iii) In the submission, CommNet, TarMAC and InforMARL also carried the IDs in their messages, so the survivors could tell who was missing and Theorem 4.3 did not apply to them; this is how CommNet's 0.752 on Drop 2 could exceed the 0.600 ceiling. In the revision, the IDs enter only each agent's own policy input (Section 5.1), and all policy-gradient methods, including SDec-MAT, were retrained with the same random seeds under matched settings (Q6). All ID-equipped baselines now sit at the ceilings on Drop 1 and Drop 2 and below it on Split, as Theorem 4.3 predicts; entries are empirical rates over 4000 episodes, whose standard error at the ceiling is about 0.007 (Drop 1) and 0.008 (Drop 2), so entries such as 0.703 are at the ceiling within sampling error (Appendix D.4). The case with IDs in the messages is now Appendix H: CommNet then solves Drop 1 and reaches 0.966 in Drop 2, but no baseline exceeds 0.413 in Split (Section 5.1; see also our answer to JCv3 W2). SDec-MAT attains 1.000 in every case.

(iv) In Split, the ten agents are randomly divided into two groups of five, with K drawn independently from {2,3,4} for each group; each of the five one-hot IDs is issued to two agents, who may fall in the same group. SDec-MAT's indices are array positions only: they are not an input to the policy (the decoder has no ID or positional embedding) and serve only as a tie-breaking order within each group's chain.

(v) The reward and horizon are now given in Appendix D.4, and the number of evaluation episodes and seeds in the caption of Table 1: all entries use greedy evaluation over 4000 episodes per checkpoint and condition, and 3 seeds. We now state the full protocol in Section 5.1, with details in Appendix D.4.

oRwq - Q3

Q3. The 14 dimensions are the three quotas K1, K2, K3 ∈ {1, 2, 3, 4} as one-hot vectors (12), a staging indicator (the agent is on the staging cell) and a co-occupancy bit (it shares the cell with at least one other agent); Appendix D.3 now lists them. The environment is unchanged; the submission's description, "the public quota and its own arrival bit", was imprecise. The observation contains no agent identifier and no record of the wave in which the agent arrived, so the two waves change when agents reach the cell but not what they observe there. At the coordination state both bits equal 1 for all six agents on the cell, so their observations are identical (Condition 2). For Condition 4: the retrained MAPPO, CommNet, TarMAC and InforMARL are feed-forward (Q6), and their IDs enter only their own policy input, not their messages, so an agent's complete input at s is the quota, the two bits and its ID. None of these depends on which other agents are active, so for a given quota H_i(s_u) = H_i(s_v) whenever agent i belongs to both active sets, and Theorem 4.3 applies in its multi-action form (Appendix C.1; see W1).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.