- 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
-
The set 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.
-
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
-
When no prior knowledge is available, how should be defined? For example, in a generic heterogeneous setting, could the authors clarify how the injective map (Appendix B.6) should be defined?
-
How robust is AGP to different choices for the edges connecting the agents? Evaluating the impact of other heuristics can help further validate the proposed method.
-
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.
-
Given that the graph used in AGP has a higher number of nodes () and edges () compared to standard agent graphs ( nodes and a worst case of 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
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 in AGP are also useful.
However, my main concerns regarding the definition of 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 can be defined without requiring additional prior knowledge?
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).