- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies multi-agent combinatorial optimization in settings where the problem instance is not fully known in advance, but is instead revealed progressively as agents act. The authors argue that existing neural multi-agent solvers and cooperative MARL methods coordinate agents only at the current decision step and only through agent-centric representations, which mismatches the fact that the actual coordination requirements are induced by shared environment resources and often materialize several steps in the future. It proposes PACT, in which each agent generates several short-horizon candidate plans rather than a single next action, and each candidate plan is attached to the environment graph as an auxiliary node linked to the resource nodes its future actions would demand. Capacity-aware message passing over this plan-augmented graph compares the preference-weighted demand on each resource with its remaining capacity and iteratively revises the agents' plan preferences, after which each agent selects a plan and executes only its first action, replanning at the next step. The whole pipeline, covering plan proposal, plan rollout, and plan selection, is trained end to end with a policy gradient objective. It is tested on three dynamic problems spanning routing and scheduling, namely a multi-agent Canadian Traveller Problem, a dynamic flexible job shop, and a non-clairvoyant flexible flow shop, against neural multi-agent solvers (PARCO, MACSIM), cooperative MARL baselines (MAPPO, IPPO, VDN, DCG), and exact or constraint programming solvers used both as hindsight oracles and as online replanning baselines. PACT achieves better solution quality and higher episode completion rates than the learning baselines in nearly all configurations, transfers zero-shot to instances far larger than those seen in training, and reaches comparable or lower cost than online replanning at a small fraction of its runtime. Ablations indicate that the message passing on the plan-augmented graph, rather than candidate generation alone, accounts for most of the gain.
Critical strengths
-
The coordination mechanism is a good representational idea whose payoff is visible at a scale. Attaching each candidate plan to the resource nodes its future actions would demand, and then aggregating preference-weighted load against remaining capacity at those nodes, replaces pairwise agent factors with an element-centric computation that grows with the number of demanded elements rather than with team size, while the capacity normalization keeps the load features on a common scale regardless of instance size.
-
The empirical study is thorough. The same framework is evaluated on three dynamic problems spanning two domains, against both neural multi-agent solvers and cooperative MARL baselines, with ten training seeds per configuration, per-seed deviations reported in the appendix, and separate reporting of cost including failure penalties and objective over successful episodes.
Critical weaknesses
-
The paper's central conceptual claim is never actually tested. The motivation rests on two asserted mismatches, that coordination should be mediated by environment elements rather than by agent-centric relations, and that it should span future steps rather than the current one, but the only coordination ablation removes coordination altogether. There is no variant that retains the candidate plans and the same number of coordination rounds while making the medium agent-centric, for instance attention directly among plan nodes or message passing on a fully connected agent graph.
-
Several of the headline claims are not supported by the comparisons as they are currently run. The abstract states that PACT outperforms centralized oracles with privileged access to the uncertainty, but the oracle solves the fully revealed realization and is therefore a hindsight bound that an online policy should not be able to beat. On the one large configuration where both oracles actually return solutions, PACT is several times worse, and the apparent wins occur only where a solver times out entirely or where its reported cost is dominated by penalties on instances it failed to complete.
Questions for authors
- Can you report an agent-centric coordination control, for instance attention directly among plan nodes or message passing on a fully connected agent graph, holding the candidate count, the number of coordination rounds, and the compute budget fixed?
4 comments
Comment 2 of 2: Response to Weakness 2 and Question 1
Weakness 2: Oracle claim in the abstract
Response: Thank you for pointing this out. We agree, and we have revised the abstract. The oracle solves the fully revealed realization and is therefore a hindsight reference, not a competitor. As you note, PACT is worse wherever an oracle returns a good solution on a large instance (MACTP 512×24×48: Gurobi 21.9 vs PACT 50.3 with sampling and 72.3 with greedy decoding), and its lower cost occurs only where a solver times out or returns a time-limited solution. On small instances, PACT with sampling approaches the oracle (MACTP 16×4×6: 2.84 vs 2.89). The original sentence, "it outperforms centralized oracles with privileged access to instance uncertainty", now reads:
"We show that PACT improves solution quality in dynamic problems relative to learning-based baselines and exhibits the best transfer to larger instances among them. With best-of-128 sampling, it approaches the cost of hindsight oracles on small instances, and it scales to large instances on which the oracle solvers time out."
Question 1: Agent-centric coordination control with fixed budget
Response: Yes. We address this in our response to Weakness 1. In short, PACT-AC is an agent-centric variant in which the candidate plans attend directly to one another rather than coordinating through the environment elements. By design, it matches PACT in candidate count (), number of coordination rounds () and coordination parameter count (within 0.14%), and it runs on the same hardware. PACT has lower cost on all 15 configurations with equal or higher success.
Thank authors for the new experiments, I think move the paper in the right direction. However, the new control is still limited in scope and statistical support, so I don't think the evidence yet fully establishes that resource center coordination drives the gains, and I will keep my rating.
Thank you for reading our response and for your feedback on the new experiments. We agree that the PACT-AC comparison would benefit from stronger statistical support. If the paper is accepted, we will train PACT-AC with all 10 seeds and report confidence intervals, as for the other learning-based results.
Comment 1 of 2: Response to Weakness 1
Thank you very much for your careful review and valuable suggestions. We have provided point-by-point responses to all raised questions and concerns below. The rebuttal revision has also been uploaded, and all changes in the revised manuscript are highlighted in red.
Weakness 1: Testing the central conceptual claim
Response: Thank you for suggesting this control. This point was also raised by Reviewer ozhV (Weakness 1 and Question 2). We have added PACT-AC, an agent-centric variant of PACT that follows the first control you proposed, attention directly among plan nodes. In PACT, coordination passes through the environment elements: each element aggregates the expected demand of all agents' candidate plans, compares it with its remaining capacity, and exchanges messages with the plans attached to it (Eqs. (6)–(9)). In PACT-AC, the candidate plans of all agents instead exchange information directly with one another through attention, so environment elements and their capacity-aware load features (Eq. (7)) take no part in coordination. PACT-AC keeps the candidate plans (K=4), the coordination rounds (R=2), the plan encoder, training configuration and hardware the same. We sized the coordination module of PACT-AC to match that of PACT, so the two differ in parameter count by at most 0.14% (PACT 31,169 vs PACT-AC 31,210 on scheduling, and PACT 31,425 vs PACT-AC 31,468 on MACTP). Due to the limited rebuttal period, PACT-AC is trained with 5 of the 10 seeds used in the paper. If the paper is accepted, we will report the full 10-seed results in Appendix C.4. The results under greedy decoding are summarized below (cost, with success in % in parentheses and the lower cost in bold).
We have included these results in Appendix C.4 of our rebuttal revision (Table 9). It can be observed that PACT attains lower cost on all 15 configurations with equal or higher success. On MACTP the gap grows with instance size, and PACT-AC completes only 74.6% of the largest instances. This indicates that exchanging information among the candidate plans alone does not account for the gains. The gains arise when coordination passes through the demanded environment elements and their capacity-aware load. In terms of runtime per instance on the largest configurations, PACT-AC is faster on DFJSP (1.89 s vs 2.41 s) and NCFFSP (0.79 s vs 1.84 s) and slower on MACTP (28.2 s vs 11.0 s).
The second mismatch, coordination over future steps, is tested separately. We trained PACT with a one-step planning horizon (Hp=1) on MACTP, likewise with 5 of the 10 seeds, keeping all other settings identical to the paper's Hp=4 model. The Hp=4 model attains lower cost, higher success and lower objective on all five configurations (e.g., cost 3.66 vs 5.81 in distribution and 86.1 vs 114.2 on the largest configuration). These results are in Appendix C.4 (Table 8).