acceptodds
Under review as a conference paper at ICLR 2027

Action Graph Policies

Abstract

Coordinating teams of autonomous agents to achieve a common goal is a foundational challenge in multi-agent reinforcement learning (MARL). From automated warehouses where multiple robots must lift heavy pallets to tactical defense systems where fleets must maneuver jointly to surround a target, success in many real-world applications requires multiple agents to synchronize co-dependent actions to achieve the task. In this paper, we propose Action Graph Policies (AGP) for collaborative MARL, where we make candidate actions, rather than agents, the fundamental units of relational reasoning. We construct what we call an “action graph”, whose nodes represent available agent-action pairs and we apply multi-head attention over this graph to learn dependencies among candidate action choices. Information exchange across this graph contextualizes each action with respect to the choices available to the entire team, enabling policies to account for for teammates' actions before selecting their own, without explicitly enumerating the joint action space. Theoretically, we analyze settings where typical MARL approaches suffer from either miscoordination or exponential costs from explicitly modeling joint-action dependencies. Empirically, we demonstrate that AGP achieves higher aggregate performance than fourteen strong related MARL methods over nineteen cooperative tasks drawn from three benchmark suites, Level-Based Foraging, the StarCraft Multi-Agent Challenge (SMAC) and SMACv2, and a Staffing game of our own. Through qualitative post-training analyses, we also pair visualizations of learned action graphs with task episodes, demonstrating how action dependencies align with coordinated behavior. With ablations assessing the contribution of the action-graph representation, and computational complexity analysis of AGP, our findings demonstrate the value of explicitly modeling action dependencies for learning policies whose success depends on what agents can accomplish together. Anonymized code can be found at: https://anonymous.4open.science/r/agp-marlanonymous.4open.science/r/agp-marl.

Primary area:
reinforcement learning
Keywords:
multi-agent reinforcement learning, cooperative decision-making, coordinated policies

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_5BBaOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Action Graph Policies (AGP), a novel method that relies on action-graph representations for learning cooperative MARL policies. To enable action-level coordination, AGP represents action co-dependence by building a graph with agent-action pairs as nodes, connecting them using within-agent and across-agent edges. During decision-making, AGP exchanges information on this graph by updating node representations using multi-head attention. Experiments across different benchmarks (i.e., Staffing game, LBF, SMAC, and SMACv2) show that AGP outperforms several baselines.

Critical strengths

Improving action coordination in MARL by building an action-agent graph to represent action co-dependence is an interesting and well-motivated direction. Indeed, going beyond agent-agent graphs can help address scalability and representation issues of existing methodologies. This supports the core idea of AGP, paving the way for novel designs of MARL policies with improved action-level coordination across agents.

Critical weaknesses
  1. The set Eacross\mathcal{E}_{across} of across-agent edges in the action graph (Definition 4.1) enables information exchange across agents, making it crucial for the effectiveness of AGP. However, the design choice of "connecting action-agent pairs with the same action" seems arbitrary and not fully empirically supported. First, multiple choices for connecting agents through actions (e.g., same action, action ordering, or even random) can result in the same 1-hop distance between agents, making them equivalent in terms of receptive field. Second, while it is true that some environments require agents to take the same actions to achieve good performance, this information is not known in advance and, in some tasks, may not even be true. This is further supported by the ablation in Figure 6: the "no edges at all" variant strongly degrades performance in LBF, while causing only a minor loss in SMAC. This suggests that AGP outperforms baselines in Staffing and LBF because the underlying graph construction is closely aligned with the underlying task, whereas in SMAC and SMACv2 the relatively modest gains may come from architectural/optimization choices rather than algorithmic ones.

  2. To build the action-agent graph, AGP requires having access to prior knowledge of the problem and an inductive bias on the action structure beforehand. This can strongly limit the applicability of the proposed approach. For example, in heterogeneous settings, agents can have different and totally unrelated action spaces, which would make the graph in AGP disconnected.

Questions for authors
  1. When no prior knowledge is available, how should Eacross\mathcal{E}_{across} be defined? For example, in a generic heterogeneous setting, could the authors clarify how the injective map ϕi\phi_i (Appendix B.6) should be defined?

  2. How robust is AGP to different choices for the edges Eacross\mathcal{E}_{across} connecting the agents? Evaluating the impact of other heuristics can help further validate the proposed method.

  3. How do the authors expect their model to work in settings where the underlying action structure used to build the graph in AGP does not match the optimal solution for the task? For example, using the current implementation where across-agent edges are built connecting agent-action pairs with the same action, how would AGP perform in settings with large action spaces requiring anti-coordination? Any additional results or insights in this direction would be appreciated.

  4. Given that the graph used in AGP has a higher number of nodes (NMNM) and edges (NM(N+M−2)NM(N+M-2)) compared to standard agent graphs (NN nodes and a worst case of N2N^2 edges), what is the wall-clock cost of AGP compared to the baselines?

Minor comments about clarity:

  • Definition 3.1 (action co-dependence) could be improved, particularly in the first sentence.
  • Section 3 could be made easier to follow, for example, by structuring the presentation using sub-sections or paragraphs.
  • The scheme reported in Figure 5 could help to further support the proposed method, but at the current stage, it is hard to interpret. For example, edges and labels often overlap.
  • A detailed explanation of each ablation used in Section 6 (i.e., the labels of Figure 6) is only provided in the Appendix, which makes it difficult to understand the results in the main text and forces the reader to go back and forth between pages.
9 comments
AuthorsOpenReview ↗

Authors' Response to Reviewer 5BBa (1/2)

Authors' Response to Reviewer 5BBa (1/2)

Thank you for the detailed review. Your first weakness is the question we most wanted to test, and we ran the alternatives you named on four representative hard tasks (Table R2 in the global response).

W1, Q2. Is the same-action rule arbitrary, and how robust is AGP to other rules? While any across-agent matching reaches the same teammates in one hop, the information transmitted over that hop differs. An edge carries a teammate’s evaluation of one specific action. Under the same-action rule, an agent’s candidate action, such as "attack enemy 2", directly receives how each teammate rates that exact action, which is the primary signal needed to decide whether to coordinate or diverge. Under a random or shifted matching, the first hop delivers a teammate’s valuation of an unrelated action, delaying the relevant signal by a layer and mixing it with other action features. This rule is also theoretically grounded: combined with within-agent edges, same-action edges connect the entire graph so that within two layers, every action candidate receives information from every other candidate, including unrelated actions (Prop. 4.3). Nothing is excluded; the most direct coordination signal simply arrives first. Table R2 demonstrates this empirical advantage (see global response, item 2). Averaged across four difficult tasks, same-action edges achieve a score of 83.7 compared to 72 to 80 for alternative rules, with no alternative outperforming it on any individual task. On Staffing, where rewards depend on the number of agents per task, every alternative drops by 6 to 16 points, including the dense variant that could theoretically learn any matching. On Foraging and 10m_vs_11m, the alternatives perform within seed noise of the same-action rule. Ultimately, same-action edges provide the lowest computational cost without sacrificing performance.

W1. Does the rule assume agents should take the same action? No. Connecting same-action nodes across agents only establishes a communication channel between candidates for that action; it does not constrain agents to select the same behavior. Whether to coordinate or anti-coordinate is entirely determined by the learned attention weights. Depending on the task, the model learns to use these edges to encourage joint action ("join"), as when agents load an item together on Foraging or focus fire on one target on several StarCraft maps, or to promote anti-coordination ("avoid"), as on Staffing, where over-staffing a task is penalized (see Appendix I, highlighted in magenta, and our response to Reviewer Sjk3, Q5).

W1. Are the StarCraft gains architectural? We interpret Figure 6 in the same way and view it as highlighting the two core components of AGP working together. AGP is not solely defined by across-agent edges. Its core design gives every candidate action its own node initialized with an entity-centric embedding (Eq. 6; see also our reply to Reviewer jvQR, W2), combining the agent's history, a shared action embedding, and local observations of the action's target entity. Across-agent edges then allow these action nodes to communicate directly across teammates. In StarCraft, an action like "attack enemy k" explicitly references its target, meaning its node encodes the agent's local view of enemy k. Because target selection is central to coordination on these maps, part of the coordination structure is captured at the node level. While the environment provides the raw observations, structuring the policy around action-entity nodes is a core algorithmic contribution of AGP. Conversely, in environments like Foraging where actions lack target-specific features, across-agent message passing carries the entire coordination burden, for instance, removing those edges drops performance by 48 points (as well as 32 points on Staffing and 16 points on 10m_vs_11m). On 3s5z_vs_3s6z and SMACv2, removing across-agent edges performs comparably to the full model (see global response, Table R2; App. G, in magenta), showing that the gains over MAPPO there stem primarily from our action-node representation. Crucially, these improvements are driven by the action-graph structure rather than model capacity or hyperparameter tuning: standard agent-level baselines matched to AGP's parameter count or message size still drop by 12 to 18 win-rate points (Fig. 6, rows 2 and 3; see also our reply to Reviewer jvQR, W1). Both components are integral to AGP, with different tasks relying more heavily on one or the other. We have clarified this distinction in Section 6 (ablations, in blue).

AuthorsOpenReview ↗

Authors' Response to Reviewer 5BBa (2/2)

Authors' Response to Reviewer 5BBa (2/2)

W2, Q1. What prior knowledge does AGP need, and how is E_across defined without it? AGP requires only a mapping of which actions correspond across agents, which is the action indexing that every method already uses. It does not need any prior knowledge of the reward structure or which agents must coordinate. Constructing the graph covers three cases: for homogeneous agents with shared action spaces, action k links directly to action k; for partially overlapping heterogeneous action spaces, ϕᵢ assigns the same label to actions with the same semantic effect (such as attacking the same enemy), leaving unique actions unlinked across agents (App. B.6, in magenta); and for completely disjoint heterogeneous action spaces, a single common action such as no-op acts as a bridge that connects the entire graph within two layers (Sec. 4.1 and Prop. 4.3, in magenta). We empirically tested this worst-case disjoint setting in the bridge row of Table R2 (see global response): relying on just one shared action retains 79 to 93 percent of the full model's score, matches the best baseline on Staffing (79.4 vs. DICG's 78.7), and outperforms the strongest baseline on Foraging by 33 points. Additionally, when no action correspondence is defined at all, AGP can use a dense across-agent graph instead of the sparse action graph: it needs no labels and stays close to the same-action rule except on Staffing (Table R2; Fig. 6, row 10, and Sec. 6, in magenta; see also our reply to Reviewer Sjk3, Q3, on continuous actions and independently built candidate sets).

Q3. What if the edge structure does not match the task, for example anti-coordination? Staffing is directly an anti-coordination task where over-staffing is penalized and agents must spread out across tasks (Sec. 5, in magenta). Even as the action space scales from 11 to 501 actions, AGP achieves 95 to 82 percent of the optimal value (Table 3 and Fig. 4), because linking agents evaluating the same task allows them to negotiate who should step back. To test cases where the graph structure actively mismatches the task, the shifted and random rows of Table R2 evaluate deliberately incorrect matchings (see global response). These mismatched structures cause only a mild drop of 1 to 3.5 points on Foraging and 10m_vs_11m, and 6 to 10 points on Staffing (where both variants still outperform every baseline). On 3s5z_vs_3s6z, random matching lowers the score by 17 points, which remains within the high seed variance of that map. Overall, a mismatched edge structure degrades AGP gradually and does not break it.

Q4. What is the wall-clock cost? We report detailed runtime and memory measurements in Table R4 of the global response. At inference time, decision latency is 0.4 to 0.9 ms, which is faster than CommFormer across all four measured scenarios and faster than MAT on three, while GPU memory usage remains low at 3 to 6 GB. During training, per-step runtime is 4 to 32 times slower than MAPPO and scales with N·M, which is consistent with other coordination-graph methods (see also our reply to Reviewer Sjk3, Q2). On a single NVIDIA RTX 6000 Ada Generation GPU (48 GB), full AGP runs take ~2 hours on 50-task Staffing, ~6 hours on 10m_vs_11m, ~10 hours on Foraging 25x25, and 34–50 hours on larger StarCraft maps. This matches other coordination-graph methods, though it is slower than MAT or MAPPO (see also Tables R7-R8 in App. J, and our replies to Reviewer Sjk3, Q2). Moreover, when compute is constrained, reducing the network from two layers to one halves the computational cost while losing only two points on Foraging (Fig. 6, row 9).

M1 to M4. We have addressed all four presentation suggestions in the revised manuscript: Definition 3.1 now begins with an intuitive explanation in plain language, Section 3 is organized with clear paragraph headings for easier reading, Figure 5 has been redrawn at full width to eliminate overlapping edges and labels, and the caption of Figure 6 now explicitly defines every ablation variant in the main text.

If our response addresses your feedback, we kindly ask you to consider raising your score, and please let us know if there is anything we can clarify further during the discussion period.

Thank you for the detailed rebuttal. Explicitly reporting the computational costs helps in understanding the applicability of AGP compared to the baselines. The additional clarifications on the meaning of the set Eacross\mathcal{E}_{across} in AGP are also useful.

However, my main concerns regarding the definition of Eacross\mathcal{E}_{across} have not yet been fully addressed. I appreciate the new experiments in Table R2 and additional explanations, but I do not think they provide sufficiently strong evidence to support the proposed design as a general rule.

First, uncertainty estimates are not reported in Table R2, making it difficult to determine if the performance gains of the "same action" rule over the variants are statistically significant or within seed noise. This is particularly relevant in Foraging and 10m_vs_11m, where the improvements over the best variants are relatively small. Moreover, in 3s5z_vs_3s6z, "No across-agent edges" achieves a higher average result than "same action". The proposed rule performs well on Staffing, but this result alone does not provide sufficient evidence to support this choice as a general approach.

Second, I'm not fully convinced by the proposed action correspondences in heterogeneous settings. In particular, I do not see why the "action indexing that every method already uses" should be sufficient to establish correspondences between actions, as different indexings may be unrelated to the semantic effect of the actions. Therefore, mapping actions with the same semantic effect seems to require additional domain knowledge. Furthermore, when no correspondence is available, adding a common action (e.g., no-op) may ensure graph connectivity, but the results in Table R2 suggest that this does not necessarily provide an equally effective structure for communication.

Follow-up questions:

  • To better assess the new results, could you report the uncertainty estimates in Table R2?
  • Why should action indexing imply a correspondence mapping between actions in heterogeneous settings?
  • Could you provide a practical example of how ϕi\phi_i can be defined without requiring additional prior knowledge?
Reviewer_Sjk3OpenReview ↗
Rating
1
Confidence
2(−1)
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies communication-based cooperative MARL with action-conditioned representations. The proposed method, AGP, makes one node for each agent-action candidate in a discrete action space. The architecture applies attention in two alternating steps. The first step operates among the candidates of each agent. The second step operates across agents, among the candidates of the same action type. AGP then gives one action distribution for each agent. The main architectural change is the granularity and the connectivity of the representations that the agents communicate. The paper reports higher aggregate performance than 14 baselines on 19 scenarios.

Critical strengths

None

Critical weaknesses

The reviewer thinks that the paper does not clearly show that the communication comparisons are fair. For AGP, the authors assume an all-to-all channel. They also assume synchronous communication rounds that are complete in each decision step. Each baseline has its own original limits on connectivity, message timing, and bandwidth. The paper does not clearly state how the implemented comparisons apply these limits.

The second weakness is practical efficiency and scalability. The paper gives asymptotic analyses. But it does not report measured training wall-clock time, decision latency, or peak memory against the baselines. This is important because AGP keeps one representation for each action in the full discrete action vocabulary. Its within-agent attention also increases quadratically with the number of candidates. In addition, the reviewer thinks that the method cannot be extended to a continuous action space. The method needs action types that match across agents, and a continuous action space does not have such types.

For these reasons, the reviewer thinks that the assumptions of the method are too strong. These assumptions are an all-to-all synchronous channel and a discrete action vocabulary that all agents share.

Questions for authors
  1. How do the results change when all baselines get the same connectivity, the same communication rounds in each decision step, and the same payload budget as AGP? In particular, does AGP keep its advantage when the strongest baseline can also use an unrestricted channel? Also, how does AGP perform with a communication graph that has a distance limit?

  2. What are the training wall-clock time, the inference latency for each decision, the peak memory, and the communication payload of AGP? Please compare these values with those of the strongest baselines.

  3. How can AGP work with continuous actions? How can it work with candidate sets that each agent makes independently? In these cases, it is not easy to find matching action types across agents.

  4. Is the actor architecture tied to PPO/MAPPO, or can an off-policy actor-critic method also use it? If the architecture is not tied to MAPPO, please give results of AGP with an off-policy actor-critic method.

  5. After communication, AGP samples the action of each agent independently. How does AGP solve the sampling difficulty under this factorized sampling? Final returns alone do not answer this question. Which operational measures show that AGP finds or executes rewarding coordinated patterns better than the baselines? Which measures separate this effect from the effect of better local action representations?

8 comments
AuthorsOpenReview ↗

Authors' Response to Reviewer Sjk3 (1/2)

Authors' Response to Reviewer Sjk3 (1/2)

Thank you for the detailed review. Below we address each of your comments and suggestions. We have now run the further requested experiments and analyses on representative hard tasks; the tables are in the global response.

W1. Is the communication comparison fair? The revised paper now states the setting of each baseline (App. A.1, Table R6). The communication baselines ran on the same all-to-all agent graphs as AGP, with two synchronous rounds per step for the communication-based methods (TarMAC, MASIA, MAGIC, GA-Comm, T2MAC) and eight max-plus rounds per step for the coordination-graph methods (DCG, CASEC). All-to-all is only the starting point: AGP applies soft attention over this graph, so each candidate learns which teammates to weight and sparsity arises implicitly. The communication-based baselines do the same through attention or learned gates (see global response, item 3). No baseline was delayed. Only CommFormer and CASEC restrict the graph, under a preset budget that is part of their design. We did not impose AGP's settings on them because that would change the methods. We have now added experiments in which we lifted these restrictions (see global response, Table R3): CommFormer's graph is opened to all agents and TarMAC's message is made as wide as AGP's. Averaged over the eight scenarios the lifted arms gain 3.5 and 0 points, and AGP stays 21 ahead of the best arm. On the two staffing games and the two foraging tasks neither change closes the gap, and AGP stays 22 to 32 and 26 to 40 points ahead. On StarCraft the effect is mixed: the open graph raises CommFormer from 58 to 97 percent on 27m_vs_30m and wide TarMAC comes within noise of AGP on 3s5z_vs_3s6z, while the same changes lower them on other maps. The paper's ablations point the same way: agent-level nodes given AGP's message size do not recover AGP (Fig. 6, row 3; Sec. 6 and App. G, in magenta), and AGP with a rank-1 message, about one agent-level vector, keeps most of its gain on foraging and StarCraft (Table 5; see also our reply to Reviewer jvQR, W1).

W3, Q1. Is the all-to-all assumption too strong, and what happens under a distance limit? AGP does not depend on the all-to-all agent graph. It is the starting point, and attention decides what is used (see W1 above). We ran the distance limit you asked for (see global response, item 1 and Table R1). With every across-agent edge restricted to teammates in sight, AGP keeps its score on all four scenarios and is at or above its unlimited score on three. Under the same limit CommFormer falls from 100 to 47 on 10m_vs_11m and DICG from 96 to 79. DICG remains 1 to 3 points above AGP on two maps, which is within seed noise, so we call the two level; on the super-hard 3s5z_vs_3s6z AGP leads DICG by 18 points. AGP's gain does not depend on every agent reaching every other; part of the baselines' StarCraft lead did.

W2, Q2. What does AGP cost? We measured all requested runtime, memory, and communication metrics (see global response, item 4 and Table R4; full tables in App. J, Tables R7 and R8). At inference time, AGP is fast and lightweight: a forward decision takes 0.4 to 0.9 ms. This is faster than CommFormer across all four measured scenarios and faster than MAT on three, because AGP applies two parallel attention layers regardless of the number of agents. GPU memory stays within 3 to 6 GB, compared to up to 33 GB for replay-based baselines. Training is the primary bottleneck, which we state explicitly in the revision: per-step training time is 4 to 32 times slower than MAPPO depending on the task, as attention operates over N·M action nodes rather than N agents. However, this overhead is in line with existing coordination-graph baselines (DCG is 2.5 to 27 times slower than MAPPO, and DICG is 3 to 14 times slower), while offering much stronger expressivity. Standard coordination graphs only score pairwise interactions; modeling higher-order coordination among k agents requires payoff tables of size Mᵏ for each group, which quickly becomes intractable. In contrast, AGP’s complexity does not grow with the order k of agent coordination (App. B.2, in magenta). Finally, while AGP transmits a larger message payload (2·M·128 floats per agent per step) than baselines, applying a rank-4 projection compresses communication roughly twentyfold with no performance loss across three benchmark suites (Table 5; App. H and App. J, in magenta; see also our replies to Reviewer 5BBa, Q4, and Reviewer jvQR, W2).

AuthorsOpenReview ↗

Authors' Response to Reviewer Sjk3 (2/2)

Authors' Response to Reviewer Sjk3 (2/2)

W2, Q3. Continuous actions and independent candidate sets. AGP as presented needs a finite set of candidate actions, and the Limitations say so (Sec. 6, in magenta). For continuous actions our suggestion is concrete: each agent proposes a small set of candidates, either bins of each action dimension or a few samples from a proposal policy, and these candidates become the nodes. The rest of the architecture is unchanged. What remains is to decide which candidates of different agents are linked. When candidates refer to something shared, such as a target, a task or a region, that reference is the link (App. B.6, in magenta). When they do not, candidates can be linked by how close their learned embeddings are. When nothing matches at all, one action shared by all agents is enough to connect the graph (Prop. 4.3, in magenta); we tested this case (see global response, Table R2, bridge row), and it keeps 79 to 93 percent of the full model's score. We have not run continuous-action tasks and leave them to future work. (See also our reply to Reviewer 5BBa, Q1, which treats agents with different action sets case by case.)

Q4. Is the actor tied to PPO? No. Nothing in Eqs. 6 to 10 depends on PPO. The actor maps histories and received messages to a distribution over actions, and with a replay buffer the messages are simply recomputed with the current parameters. To test this we placed the actor, unchanged, inside QMIX, an off-policy learner, with the action-graph cell as the utility network, and trained it on SMACv2 (see global response, item 5 and Table R5). Off-policy learning reuses past experience and is generally more sample-efficient, so it does not need the paper's 20M steps, and we compare all arms at 5M. On smacv2_10_units AGP-Q reaches 73 percent at that budget, where QMIX is at 41 and the PPO-trained AGP at 27; on smacv2_5_units it reaches 67, against 58 and 37. The architecture therefore trains off-policy, and learns faster there, as one expects from replay. QMIX is a value-based learner, so we also placed the actor inside an off-policy soft actor-critic (FOP; Factorizing Optimal Joint Policy of Maximum-Entropy Multi-Agent Reinforcement Learning; ICML '21). AGP performs better than FOP there as well, and at 5M it ends ahead of FOP on both SMACv2 scenarios (36 against 32 with ten units, 59 against 54 with five; Table R9 and App. K.4).

Table R9. AGP actor inside an off-policy soft actor-critic (FOP) on SMACv2 after 5M steps.

Armsmacv2_10_unitssmacv2_5_units
AGP actor inside FOP (new)36.259.1
FOP, its own actor (new)31.553.8

Q5. How does factorised sampling coordinate, and what shows it beyond return? Each agent samples independently after it has read its teammates' candidate representations, so the conditionals are already coordinated before anyone commits (see also our reply to Reviewer jvQR, W1). The paper measures this with four tests other than return (three in App. I, marked in magenta, and one ablation in Fig. 6), and the revision brings them into Sec. 6 (post-hoc analysis, in blue). (a) Removing the exchange at evaluation drops foraging food from 79 to 23 percent and exact staffing from 0.77 to 0.00. (b) Candidates read teammates considering the same task at 1.41 times uniform weight, against 0.79 for others. (c) On 15x15-4p-5f, where AGP and MAPPO both collect nearly all the food, AGP agents collide at 0.042 per step against 0.111, so equal return hides different joint behaviour. (d) Keeping the across-agent block and its parameters but letting each node attend only to itself costs 29 food points, the same as removing the exchange (Fig. 6, rows 4 and 5). The last two separate coordination from a better local representation. (See also our reply to Reviewer 5BBa, W1, on what the same-action edges learn.)

If our response addresses your feedback, we kindly ask you to consider raising your score, and please let us know if there is anything we can clarify further during the discussion period.

Thank you for the additional experiments and explanations. They address several practical questions. However, the reviewer's main concern remains the connection between the motivation, the proposed method, and the experiments used to test its reasoning.

First, Section 3 discusses the low probability of sampling coordinated action patterns and the limits of pairwise value functions. However, AGP still samples each agent’s action independently after communication. The graph connectivity results do not explain how AGP reduces this sampling difficulty. Also, the inability to represent a reward function exactly does not establish an inability to learn its optimal actions.

The reviewer thinks that the behavior analyses do not directly test the sampling argument. Removing communication during evaluation shows that a trained policy uses communication. Lower collision rates show better behavior after training. Neither result shows that AGP discovers rewarding action combinations more efficiently during training.

Second, the authors should provide more detail in the procedure beyond the simple results report in Appendix K.2 and Table R1. Please define the communication mask explicitly. Here are example detail questions.

  1. Does it restrict the existing across-agent edges before attention normalization?
  2. Is visibility evaluated separately in each direction?
  3. Which distance measure defines “5 cells” in Foraging?
  4. Is all setting maintained in both training and evaluation?

The reviewer understood the paper stated that Foraging agents observe all agents and food items. Namely, limiting communication does not also limit their observation access.

Third, the reviewer still does not know that the proposed solution can work on a continuous-action space. Independently sampled candidates do not generally share action labels across agents. The response does not explain how to construct reliable connections between these candidates.

Finally, the off-policy experiments need a clearer explanation. Appendix K.4 states that only the actor changes, but it gives limited detail about message computation and actor training.

In the reviewer's view, the experiments support the usefulness of action-specific representations. However, they provide less direct support for the explanation that motivates AGP as a response to combinatorial sampling and higher-order coordination difficulties.

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

This paper proposes a new method for a communication-based multi-agent RL problem. The idea is to build an action-level graph instead of the commonly used agent-level graph. The agent-action pairs are considered as the nodes in the graph to increase action coordination. Building on the constructed graph, an attention-based GNN is built to learn the embedding for each node. The action of each agent is generated from the new representation.

Critical strengths

The figures are clear in showing the idea and motivation. The experiments, especially Figure 3, clearly show the good performance compared with many other MARL algorithms. The extensive ablation studies and discussions are convincing.

Critical weaknesses

The current design (Eq. (10)) is more likely to consider all agents as a 'big' agent to optimise all actions jointly. The agents are not decentralised. The other MARL algorithms only exchange messages but, after that, the actions are generated 'independently '.

The messages are not well described. What the message should contain and how to use it. I cannot find it in Eq (10) and (6).

The motivating example (Level-based Foraging) in the introduction is not clear. A figure might be helpful.

The definition of the action graph in Definition 4.1 seems inconsistent with the one in Figure 1(b).

Questions for authors

How is the message used in the Action Graph Policy?

What is the difference between the Action Graph Policy and the joint 'big' agent that considers all agents as one?

Why is the std of all methods in Figure 3 very small, except for AGP in Staffing and Foraging?

2 comments
AuthorsOpenReview ↗

Authors' Response to Reviewer jvQR

Authors' Response to Reviewer jvQR

Thank you for the positive and detailed review. The new experiments are in the global response; here we answer your points directly.

W1. Are the agents one "big" agent? No. Eq. 10 is written for a single agent: the softmax runs over that agent's own M candidates only. The symbol m₋ᵢ is the set of messages the agent has received, which are fixed inputs at the moment of sampling, like an observation. Each agent then samples its own action in parallel, without seeing what the others sample, and the joint policy is the product in Eq. 1 (App. A.1 states this, in magenta; see also our reply to Reviewer Sjk3, Q5). This is the same order of events as in TarMAC or CommFormer: exchange first, then act independently. What differs is the content of the messages. We have rewritten the text after Eq. 10 to say this (Sec. 4.2, in blue). The gain is not hidden centralisation either: an agent-level policy given AGP's parameter count or message size on the same agent graph loses 18 food points and 12 to 18 win-rate points (Fig. 6, rows 2 and 3; see also our reply to Reviewer 5BBa, W1).

W2, Q1. What is the message and how is it used? Each agent builds one 128-dimensional vector per candidate action from its history, a shared embedding of the action, and the observed features of the action's target (Eq. 6). After attending over its own candidates (Eq. 7), the agent broadcasts these M vectors. That block is the message. A teammate's candidate for the same action attends over the received vectors (Eq. 8), and after two such layers each agent scores its own candidates (Eq. 10). The message therefore carries the agent's current assessment of each of its options. It carries no raw observations, no chosen action and no global state (as App. A.1 and App. E state, in magenta). The revision now defines m₋ᵢ and describes the message right after Eq. 10 (Sec. 4.2, in blue). (For the size of the message, see our reply to Reviewer Sjk3, Q2; for what the action embeddings contribute, see our reply to Reviewer 5BBa, W1.)

W3, W4. Done. Section 3 now has a figure of the foraging example (Figure R1), and Figure 1(b) is redrawn with one node per agent and action, to match Definition 4.1.

Q2. How does AGP differ from a joint agent? A joint agent sees the global state and outputs one of |A|ᴺ joint actions. An AGP agent sees its own history and the received messages, and outputs one of its own M actions. Parameters are shared across agents and do not grow with N, and the cost per layer is O(N·M·(N + M)·d) (Prop. 4.4; for the measured cost, see global response, Table R4). The centralised critic is used in training only, as in MAPPO (Sec. 4.2, in magenta; App. E).

Q3. Why is AGP's band wide in Figure 3? The shaded bands are 95 percent intervals over seeds (Sec. 5; App. E, in magenta), and we evaluate every 1M steps (every 0.25M on staffing) across all methods. While these naturally reduce step-to-step noise across all curves, the wider visual band for AGP on Staffing and Foraging reflects how seeds learn in sparse-reward tasks rather than instability. On these two benchmarks, baselines plateau early in suboptimal local optima where agents fail to coordinate, so all seeds stall at the same low reward ceiling and overlap tightly. In contrast, Staffing and Foraging have threshold-based coordination rewards where different AGP seeds discover the joint strategy at slightly different training steps; because return jumps sharply upon discovery, minor horizontal timing shifts across seeds create a wider vertical spread during the steep climb before narrowing at convergence. Conversely, StarCraft provides dense shaping rewards (damage dealt and enemy kills), allowing all AGP seeds to progress at a uniform pace with narrow bands throughout training.

If our response addresses your feedback, we kindly ask you to consider raising your score, and please let us know if there is anything we can clarify further during the discussion period.

Dear Reviewer jvQR,

Thank you again for your constructive feedback, which helped us clarify decentralized execution and message passing, as well as improve our figures.

As the discussion period is nearing its end, we wanted to check in and see if our revisions address your concerns. Please let us know if we can clarify anything further.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Authors' Global Response (1/2)

Authors' Global Response (1/2)

  • Structure. We include a a global response and then also reply to each reviewer; (1/2) and (2/2) mark the parts of one reply.
  • Revised PDF. New/revised text is in blue. Passages that were already in the submission and that our replies point to are in magenta.
  • Tables. New tables and figures are numbered R1, R2 and so on, so the numbering of the submitted version is unchanged. Tables R1 to R5 and R9 appear in our comments and, under the same numbers, in the PDF; Tables R6 to R8 and Figure R1 are in the PDF only.

We thank the reviewers for their careful reading. In addition to the individual responses to each review, we also curate some common clarifications and findings below to support our rebuttal. More specifically: whether the communication comparison is fair, whether the same-action edge rule is arbitrary, what AGP costs, and whether the actor is tied to PPO. We ran new experiments for each.

Three results stand out. AGP keeps its score when communication is limited to teammates in sight, while the baselines that led on StarCraft lose up to half of theirs (Table R1). No alternative edge rule beats same-action edges on any of the four tasks tested (Table R2). AGP decides in under a millisecond, with a fraction of the memory of the coordination-graph methods (Table R4).

All new numbers use one statistic: the final evaluation at the paper's budget, as an interquartile mean over seeds. Staffing is percent of attainable value, foraging is percent of food collected, StarCraft is win rate. AGP is in bold. Tables R1 to R3 each use four representative hard tasks, drawn from the staffing size at which the baselines are strongest, a large foraging grid, and StarCraft maps that are rated hard or super hard or are randomised as in SMACv2. Two of the StarCraft maps are ones on which a baseline beats AGP in the paper, so the selection does not favour AGP.

1. AGP does not need the all-to-all agent graph. The all-to-all agent graph is where AGP starts, not something it depends on (see also item 3 below). We limited every across-agent edge to teammates the agent can currently see: sight range on StarCraft, 5 cells on foraging. This removes half to 70 percent of the edges under random play. The staffing game has no positions, so it is not part of this test. We applied the same limit to the three strongest communication baselines. AGP is unaffected. CommFormer loses 19 to 53 points on the three StarCraft maps, and DICG loses 8 and 17 points on the two maps where it led. Under the limit AGP is the best method on two scenarios and level with DICG on the other two (see also our reply to Reviewer Sjk3, Q1).

Table R1. Score under the distance limit, with the change from the unlimited graph in parentheses. Methods ordered from most to least robust.

Method3s5z_vs_3s6zForaging 20x2010m_vs_11msmacv2_10_unitsMean change
AGP90.6 (+5.2)80.9 (+0.8)78.1 (+4.1)64.6 (−3.1)+1.8
TarMAC64.6 (+1.1)38.4 (−1.8)19.8 (+12.5)45.8 (−13.6)−0.5
DICG72.9 (+5.2)4.8 (+1.3)79.2 (−16.6)67.7 (−8.3)−4.6
CommFormer22.9 (−47.9)25.2 (−2.0)46.9 (−53.1)44.8 (−18.7)−30.4

2. Same-action edges are the best rule we tried. We compared them with a shifted matching, a random matching, a single shared-action bridge, and the paper's dense arm. Averaged over four tasks, same-action edges score 83.7 against 72 to 80 for the alternatives, and no alternative wins on any single task. On staffing every alternative loses 6 to 16 points. The rule is also sufficient in theory: together with the edges inside each agent, it lets every candidate hear from every other candidate, including teammates' candidates for unrelated actions, within two layers (Prop. 4.3). Exchanging at all is decisive on staffing, foraging and 10m_vs_11m; on 3s5z_vs_3s6z the arm without exchange is similar to the full model, and there the gain also comes from the candidate-action nodes and their embeddings (see also our reply to Reviewer 5BBa, W1).

Table R2. Across-agent edge rules, ordered by mean score.

RuleStaffing-10Foraging 20x2010m_vs_11m3s5z_vs_3s6zMean
Same action (AGP)95.280.174.085.483.7
Shifted (a reads a + 1)88.876.672.983.380.4
Dense (all candidates)84.178.572.982.379.5
Random matching84.777.272.968.875.9
Bridge (one shared action)79.472.868.867.772.2
No across-agent edges63.432.358.387.560.4
AuthorsOpenReview ↗

Authors' Global Response (2/2)

Authors' Global Response (2/2)

3. The baselines started from the same agent graph as AGP. AGP starts from an all-to-all agent graph, in which any agent may exchange with any teammate, and applies soft attention over it. Each candidate learns how much weight to give each teammate, so sparsity arises implicitly and no connectivity rule is imposed. TarMAC, MAGIC, GA-Comm, MASIA and T2MAC ran on the same all-to-all agent graphs as AGP, with two synchronous rounds per step and no delay. They become sparse in a similar implicit way, through soft attention (TarMAC, MASIA, and also DICG) or a learned gate on each pair (MAGIC, GA-Comm, T2MAC). The other graph baselines differ: DCG keeps the complete graph fixed, and CommFormer and CASEC start from the complete graph and sparsify it under a preset budget, three edges per agent and the top 30 percent of edges. The revision states this per method (App. A.1, Table R6). Lifting the two restrictions that can be lifted without changing a method, CommFormer's edge budget and TarMAC's narrower message, raises CommFormer's mean over eight scenarios by 3.5 points and leaves TarMAC's unchanged; AGP stays 21 ahead of the best arm (Table R3). It leads by 22 to 32 points on the two staffing games and by 26 to 40 on the two foraging tasks, where its worst seed is above the best seed of every baseline arm. On StarCraft the effect is mixed: a lifted arm is within noise of AGP on three of four scenarios, and CommFormer leads on 10m_vs_11m, as in the paper (see also our reply to Reviewer Sjk3, W1).

Table R3. Restricted baselines, "as run" / "with the restriction removed". TarMAC: message as wide as AGP's. CommFormer: graph open to all agents.

ScenarioAGPTarMACCommFormer
Staffing, 10 tasks95.273.1 / 73.462.2 / 66.4
Staffing, 50 tasks94.051.4 / 62.055.4 / 59.4
Foraging 20x2080.140.2 / 30.527.2 / 26.2
Foraging 25x2561.935.8 / 34.623.9 / 25.9
3s5z_vs_3s6z85.463.5 / 82.370.8 / 64.6
10m_vs_11m74.07.3 / 13.5100.0 / 83.3
smacv2_10_units67.759.4 / 47.963.5 / 66.7
27m_vs_30m100.099.0 / 86.558.3 / 96.9
Mean of eight82.353.7 / 53.857.7 / 61.2

4. Measured cost. One run per 48 GB GPU, paper settings, four scenarios from 36 to 945 candidate nodes. AGP uses 3 to 6 GB where the coordination-graph and value-based methods use up to 33 GB, and its decision latency is under a millisecond, faster than CommFormer on every scenario and than MAT on three of four. Training is where AGP pays: 4 to 32 times slower than MAPPO per environment step. This is in the range of the coordination-graph methods (Table R4). Those methods score pairs of agents, and extending them to groups of three or more multiplies their cost combinatorially, while AGP's cost does not depend on how many agents must coordinate (App. B.2, in magenta). AGP runs on one NVIDIA RTX 6000 Ada Generation GPU (48 GB) take about ~2 hours on the fifty-task staffing game, ~6h on 10m_vs_11m, ~10h on foraging 25x25 and ranges from 34-50 hours on larger and harder Starcraft maps. These are comparable to other coordination-graph methods but higher than MAT or MAPPO. See also Tables R7 and R8 in App. J and our replies to Reviewer Sjk3, Q2, and Reviewer 5BBa, Q4.

Table R4. Cost, range over the four scenarios.

MethodPeak memory, GBDecision latency, msTraining time per step vs MAPPO
AGP2.8 to 5.50.39 to 0.854x to 32x
DCG4.8 to 33.10.30 to 0.472.5x to 27x
DICG4.8 to 33.20.22 to 0.393x to 14x
QMIX4.7 to 33.10.21 to 0.342.7x to 12x
CommFormer1.8 to 5.50.50 to 1.620.6x to 1.3x
MAT1.5 to 4.60.56 to 1.730.6x to 1.3x
MAPPO2.6 to 4.80.19 to 0.391x

5. The actor is not tied to PPO. We placed it, unchanged, inside QMIX, an off-policy learner, with the action-graph cell as the utility network (AGP-Q), and trained it on the paper's two SMACv2 scenarios, the more demanding StarCraft benchmark. Off-policy learners reuse past experience and are generally more sample-efficient, so they do not need the paper's 20M steps, and we report all arms at 5M. At that budget AGP-Q leads on both (Table R5). With ten units it wins 73 percent of games, against 41 for QMIX and 27 for the PPO-trained AGP, and already matches or exceeds what those two reach at the full 20M in the paper (62 and 68). With five units it wins 67 percent, against 58 and 37 (see also our reply to Reviewer Sjk3, Q4).

Table R5. AGP trained off-policy on SMACv2: win rate after 5M steps. Paper arms are read from the paper's own training curves at the same step.

Arm10 units5 units
AGP-Q (new)72.966.7
QMIX (paper)40.657.5
AGP with PPO (paper)27.136.5
MAPPO (paper)18.837.5

Dear Reviewers, 

We’re about halfway through the discussion period. Please read the authors’ rebuttal and assess whether it adequately addresses the key concerns raised in your review. We encourage you to leave a follow-up comment for the authors, indicating which concerns have been resolved and whether any important issues remain or require further clarification. Please update your review and scores as appropriate in light of the rebuttal and discussion.

Thank you for your time and participation. 

Best regards, 

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.