acceptodds
Under review as a conference paper at ICLR 2027

PACT: Plan-Augmented Coordination via Trace-Graphs for Dynamic Multi-Agent Combinatorial Optimization

Abstract

Multi-agent approaches have been investigated recently as a means of improving the scalability of reinforcement learning for neural combinatorial optimization. Existing methods assume that all problem instance information is known upfront. However, real-world problems are often : relevant information is progressively revealed as the agents take actions (e.g., arriving at an edge in a routing problem only to discover it is untraversable). In such cases, existing methods fail to coordinate agents to explore and exploit the progressively revealed information. To address the arising coordination challenge, we introduce PACT (lan-ugmented oordination via race-graphs). PACT augments the environment graph with auxiliary nodes representing the plans of agents, which are connected to the resource nodes to indicate future dependencies. The proposed message-passing scheme over the augmented graph grounds inter-agent coordination in the environment and enables proactive, rather than reactive, conflict resolution. We show that PACT improves solution quality in dynamic problems relative to baselines and exhibits the best transfer to larger instances on which, remarkably, it outperforms centralized oracles with privileged access to instance uncertainty.

Primary area:
reinforcement learning
Keywords:
Neural Combinatorial Optimization, Multi-agent Combinatorial Optimization, Multi-agent Coordination, Multi-agent Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_gzzcOpenReview ↗
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
AuthorsOpenReview ↗

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=4K = 4), the coordination rounds (R=2R = 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).

MACTP16×4×6 (ID)32×6×10128×12×24512×24×481024×32×64
PACT3.66 (99.1)5.79 (99.6)18.6 (99.7)72.3 (99.0)86.1 (99.6)
PACT-AC3.97 (97.0)6.69 (97.6)23.3 (94.4)157.7 (84.2)420.7 (74.6)
DFJSP20×8×6 (ID)30×14×650×16×880×20×8120×24×10
PACT162.5 (100.0)141.5 (100.0)233.2 (100.0)283.9 (100.0)398.4 (100.0)
PACT-AC168.2 (100.0)157.0 (100.0)250.0 (100.0)301.4 (100.0)420.8 (100.0)
NCFFSP20×4×3 (ID)30×6×350×7×380×6×4120×8×4
PACT41.5 (100.0)35.9 (100.0)48.8 (99.9)83.4 (99.7)86.7 (99.4)
PACT-AC49.5 (100.0)44.3 (100.0)55.9 (99.2)91.5 (98.8)92.3 (98.4)

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=1H_p = 1) on MACTP, likewise with 5 of the 10 seeds, keeping all other settings identical to the paper's Hp=4H_p = 4 model. The Hp=4H_p = 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).

AuthorsOpenReview ↗

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 (K=4K = 4), number of coordination rounds (R=2R = 2) 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.

Reviewer_TQtQOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes PACT for cooperative routing and scheduling with information revealed during execution. Each agent generates candidate plans, which are linked to the resources they would use in a shared graph. A graph network updates plan scores using estimated resource demand, then actions are selected. The method is trained with a modified PPO objective. Experiments on three domains report gains over learning-based baselines and transfer to larger instances.

Critical strengths
  • Figures 1 and 2 is well designed, and make problem setting and proposed approach easier to understand.

  • Studying combinatorial optimization under partial observability is an interesting and relevant direction.

Critical weaknesses

W1: Sampling reports the best of 128 completed runs, which does not measure expected performance in a single online execution. Please also report the mean cost and success rate across individual stochastic runs.

W2: The paper calls the gradual revelation of fixed hidden conditions dynamic. In RL terms, this is just partial observability: transitions appear deterministic once the initial instance and hidden conditions are fixed. Please clarify this distinction and the intended meaning of dynamic in the paper.

W3: Figure 3 shows rapid saturation, especially on MACTP. This raises the question of how much learned coordination these small instances require. Random legal-action and simple heuristic baselines would help establish task difficulty and the benefit of learning.

W4: Both scheduling tasks use a one-step planning horizon (Appendix B.4). These experiments do not establish the benefit of coordinating over multiple future steps. A planning-horizon ablation on MACTP would help isolate that benefit.

Questions for authors

Q1: What happens when an agent retires? Is its goal counted as completed? Can the agent receive another goal, or does it stop acting for the rest of the episode?

Q2: Since all agents receive the same graph observation, what precisely is decentralized during execution?

Q3: Are these exact environment variants is contribution of this paper?

5 comments
AuthorsOpenReview ↗

Comment 1 of 3: Response to Weaknesses 1-2

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: Expected performance of a single stochastic run

Response: Thank you for raising this point. We agree that best-of-128 does not reflect a single online execution. The greedy rows in Table 1 already correspond to single executions with greedy decoding, and we now also report the mean over the 128 sampled rollouts: for each test instance, cost and success are averaged over its 128 rollouts, then over the 100 test instances, using the same 10 trained models as in the paper. The results are summarized below (cost, with success in % in parentheses and the lowest cost in bold).

MACTP16×4×6 (ID)32×6×10128×12×24512×24×481024×32×64
PARCO4.51 (99.2)8.13 (99.3)63.4 (83.3)2159.4 (8.6)5953.2 (6.8)
MACSIM4.28 (98.5)7.34 (99.4)29.8 (99.1)90.7 (99.7)136.9 (99.7)
PACT3.92 (99.7)6.67 (99.5)21.7 (99.7)66.6 (99.9)98.5 (100.0)
DFJSP20×8×6 (ID)30×14×650×16×880×20×8120×24×10
PARCO174.4 (100.0)151.1 (100.0)261.3 (100.0)367.5 (98.9)3615.6 (38.9)
MACSIM492.8 (63.5)695.5 (79.8)987.0 (76.6)1468.5 (74.0)1691.3 (68.9)
PACT165.6 (100.0)144.2 (100.0)246.9 (100.0)300.5 (100.0)424.5 (100.0)
NCFFSP20×4×3 (ID)30×6×350×7×380×6×4120×8×4
PARCO43.8 (100.0)49.7 (100.0)83.9 (100.0)N/AN/A
MACSIM45.6 (100.0)42.5 (100.0)58.8 (100.0)207.4 (86.2)246.9 (91.2)
PACT42.3 (100.0)41.4 (100.0)49.0 (100.0)96.9 (99.9)119.4 (99.3)

We have included these results as "Samp. (mean)" rows in Tables 4–6 of our rebuttal revision, with the definition in Appendix B.1. It can be observed that PACT has the lowest mean cost on all 15 configurations, so its advantage under sampling does not rely on selecting the best of 128 runs.

Weakness 2: Meaning of "dynamic"

Response: Thank you for pointing this out. We agree that in RL terms, our setting is partial observability: the hidden conditions are fixed for the episode and revealed gradually during execution. This is how Section 3 formalizes the problem: a multi-agent POMDP whose latent realization ξ\xi is drawn once and then held fixed. We use "dynamic" in the sense of the combinatorial optimization literature, where dynamic vehicle routing and dynamic scheduling refer to instance information revealed during execution (Pillac et al., 2013; Ouelhadj & Petrovic, 2009). We have added a footnote at the definition of the setting in Section 1 that states this correspondence explicitly.

References:

Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés L Medaglia. A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1):1–11, 2013.

Djamila Ouelhadj and Sanja Petrovic. A survey of dynamic scheduling in manufacturing systems. Journal of scheduling, 12(4):417–431, 2009.

AuthorsOpenReview ↗

Comment 2 of 3: Response to Weaknesses 3-4

Weakness 3: Random and heuristic baselines

Response: Thank you for this suggestion. We agree that random and heuristic baselines are important, as they let the reported costs be judged in context. We have added a random legal-action baseline and simple heuristic baselines. On DFJSP and NCFFSP, we use three classic priority dispatching rules (Panwalkar & Iskander, 1977): FIFO (first in, first out), SPT (shortest processing time) and MWKR (most work remaining). On MACTP, the Nearest-goal heuristic lets each agent replan, at every step, a shortest path to its nearest unvisited goal, treating edges not yet revealed as traversable (Koenig et al., 2003). The heuristics complete all test instances, and their test costs are summarized below (the lowest cost is in bold).

MACTP16×4×6 (ID)32×6×10128×12×24512×24×481024×32×64
Nearest-goal6.3611.931.1169.7201.9
PACT (g.)3.665.7918.672.386.1
DFJSP20×8×6 (ID)30×14×650×16×880×20×8120×24×10
FIFO181.8158.5261.9317.8444.0
SPT183.6161.8267.3322.4450.5
MWKR174.2159.3249.8306.1430.7
PACT (g.)162.5141.5233.2283.9398.4
NCFFSP20×4×3 (ID)30×6×350×7×380×6×4120×8×4
FIFO61.359.177.2131.0138.4
SPT52.152.966.5104.5112.0
MWKR58.455.771.7123.0128.5
PACT (g.)41.535.948.883.486.7

We have included these results in Table 1 of our rebuttal revision, with the heuristics described in Appendix B.1. It can be observed that PACT under greedy decoding has lower cost than every heuristic on every configuration. The best heuristic is 7–12% above PACT on DFJSP, 25–47% on NCFFSP and 67–135% on MACTP. Even on the in-distribution MACTP configuration, Nearest-goal costs 74% more than PACT (6.36 vs 3.66). The random baseline, in which each agent picks uniformly among its legal actions at every step, completes only 53% of the MACTP validation episodes (cost 32.4) and has cost 260.8 on DFJSP and 178.8 on NCFFSP. It is now shown as a grey dashed line in Figure 3. Regarding the rapid saturation, the training instances are small by design. The advantage of PACT grows under zero-shot transfer to larger instances and is most pronounced on the largest MACTP configuration (Table 1).

Weakness 4: Planning-horizon ablation on MACTP

Response: Thank you for suggesting this ablation. This point was also raised by Reviewer ozhV (Weakness 1 and Question 1). In the paper, PACT plans Hp=4H_p = 4 steps ahead on MACTP and Hp=1H_p = 1 step on DFJSP and NCFFSP. We have now trained a separate PACT model with Hp=1H_p = 1 on MACTP, keeping the number of candidate plans per agent (KK), the number of coordination rounds (RR), the training configuration and all other settings identical to the Hp=4H_p = 4 model. Due to the limited rebuttal period, the Hp=1H_p = 1 model 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 (mean over seeds, with the lower cost in bold).

MACTPHpH_p16×4×6 (ID)32×6×10128×12×24512×24×481024×32×64
Cost ↓43.665.7918.672.386.1
15.818.2336.082.7114.2
Success (%) ↑499.199.699.799.099.6
197.898.697.898.699.2
Objective ↓43.435.6817.846.270.5
13.556.1118.351.374.2

We have included these results in Appendix C.4 of our rebuttal revision (Table 8). It can be observed that the Hp=4H_p = 4 model attains lower cost, higher success and lower objective on all five configurations. On most configurations, the cost gap comes mainly from failed episodes, since cost includes failure penalties. The objective over successful episodes differs less.

MACTP and the scheduling problems need different horizons because contention arises at different distances. On MACTP, goals typically lie several moves away, so a plan must span multiple steps before two agents' contention for the same goal becomes visible. On DFJSP and NCFFSP, each dispatching action directly occupies a job, so contention is already exposed by the first action of a plan, and Hp=1H_p = 1 suffices. We have added this explanation to Appendix B.4. Section 5.3 now summarizes the ablation as support for multi-step coordination where contested resources lie several steps ahead.

References:

Shrikant S Panwalkar and Wafik Iskander. A survey of scheduling rules. Operations research, 25(1):45–61, 1977.

Sven Koenig, Craig Tovey, and Yuri Smirnov. Performance bounds for planning in unknown terrain. Artificial Intelligence, 147(1-2):253–279, 2003.

AuthorsOpenReview ↗

Comment 3 of 3: Response to Questions 1-3

Question 1: What happens when an agent retires

Response: Thank you for this question. This point was also raised by Reviewer ozhV (Weakness 2). Yes, the goal counts as covered. The agent cannot claim another goal and stops acting for the rest of the episode, incurring no further cost. Retirement is optional, however, and the wording of Appendix A.1 was misleading on this point: an agent covers a goal simply by visiting it and need not stop there. Claiming is an optional terminate action that retires the agent. Since agents cannot wait in place, it is the only way to stop incurring travel cost. We have rewritten the problem definition in Appendix A.1 accordingly.

Question 2: What is decentralized during execution

Response: Thank you for this question. Observations are shared, but action selection is not: each agent samples its own action from its own policy πi\pi_i, and the joint action is the collection of these individual choices. No distribution over the joint action space is formed. Coordination happens through message passing on the plan-augmented trace-graph before each agent makes its own choice. Agents therefore coordinate through communication rather than joint action selection, as in prior work where agents share information but act through individual policies (Zhang et al., 2018; Fu et al., 2022).

Question 3: Whether the environment variants are a contribution

Response: Thank you for this question. No, we do not claim the environments as a contribution. The underlying problems are established in combinatorial optimization: dynamic scheduling (Ouelhadj & Petrovic, 2009), dynamic vehicle routing (Pillac et al., 2013), the (multi-agent) Canadian Traveller Problem (Papadimitriou & Yannakakis, 1991; Shiri & Salman, 2017) and non-clairvoyant scheduling (Motwani et al., 1994), all cited in the paper. As stated in the reproducibility statement, the source code will be released upon publication, so others can use our implementations of these environments.

References:

Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5872–5881. PMLR, 2018.

Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang, and Yi Wu. Revisiting some common practices in cooperative multi-agent reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 6863–6877. PMLR, 2022.

Djamila Ouelhadj and Sanja Petrovic. A survey of dynamic scheduling in manufacturing systems. Journal of scheduling, 12(4):417–431, 2009.

Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés L Medaglia. A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1):1–11, 2013.

Christos H Papadimitriou and Mihalis Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84(1):127–150, 1991.

Davood Shiri and F. Sibel Salman. On the online multi-agent O-D k-Canadian traveler problem. Journal of Combinatorial Optimization, 34(2):453–461, 2017.

Rajeev Motwani, Steven Phillips, and Eric Torng. Nonclairvoyant scheduling. Theoretical Computer Science, 130(1):17–47, 1994.

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

This paper studies dynamic multi-agent combinatorial optimization (DMACO), a setting in which edge traversability in routing, machine breakdowns in job shops, and processing times in flow shops are revealed only through execution. It casts DMACO as a cooperative MPOMDP on a graph whose only inter-agent coupling is a capacity/demand constraint, and introduces PACT. Each agent proposes K short-horizon candidate plans, which are attached to the graph through the elements they occupy, forming a plan-augmented trace-graph. Capacity-aware message passing then re-scores the agents' plan preferences before each agent samples one plan and executes only its first action. Training uses a factored PPO objective over proposal, rollout, and selection. On the MACTP, DFJSP and NCFFSP tasks, PACT is compared with two neural MACO solvers, four MARL baselines, and Gurobi and OR-Tools as oracle and replanner references, under one in-distribution and four zero-shot sizes.

Critical strengths

The paper provides a comprehensive theoretical analysis and is clearly organized. The experiments closely match the main claims and provide convincing support for the theoretical results and their practical usefulness.

Critical weaknesses

The LBF results come from a small exploratory study, leaving the generality of the findings in broader MARL settings unclear.

Questions for authors
  1. How does the monitor distinguish harmful coverage erosion from a shift toward a different but equally successful strategy?
  2. How should the monitored patterns be updated when old patterns become obsolete and new successful patterns emerge?
  3. Could the LBF results be confirmed on new partner pairings, with the erosion score and window fixed in advance?
5 comments

We thank the reviewer for the positive assessment and for the accurate summary of PACT. We are glad that the reviewer found the analysis well-organized and the experiments convincing. On the Weaknesses and Questions: we would like to address these points properly. However, we could not connect them to our paper, as PACT does not include LBF experiments, a monitor, or a coverage-erosion score. We would be grateful if the reviewer could clarify which part of the paper these comments refer to. If perhaps the comments corresponding to another paper were erroneously pasted, we’d appreciate it if the comments concerning our paper were instead provided. Thank you again for your time.

Thank you for pointing this out, and I apologize for the mix-up. My questions about PACT are:

  1. Equation (6) aggregates demand across all plan steps. How does the message-passing module account for step indices on trace edges when re-scoring candidate plans?

  2. Algorithm 4 selects each agent's plan independently. Where and how is the joint capacity constraint in Equation (1) enforced in the implementation?

  3. The proposal loss considers all candidates, whereas the rollout loss is computed only for the selected plan. Why are unselected rollouts excluded, given that their traces also influence coordination and plan selection?

AuthorsOpenReview ↗

Comment 1 of 1: Response to Questions 1-3

Thank you for the clarification and for these questions about PACT. We respond to each of them below. The rebuttal revision has also been updated, and the corresponding changes in the revised manuscript are highlighted in red.

Question 1: Step indices in message passing

Response: Thank you for this question. The plan step index jj is recorded in every trace (Eq. (4)) and carried by each trace arc together with the demand. The message passing of Eq. (8) is edge-aware: the message along each trace arc depends on the states of its two endpoint nodes and on the attributes of the arc, including the demand and the plan step jj. The environment element contributes its capacity-aware load from Eq. (7), and the message pairs this contention with the step at which the plan reaches the element. A candidate plan that reaches a contested environment element at its first step and one that reaches it several steps later therefore receive different messages and can receive different score updates in Eq. (9). How much weight contention at each step receives is learned by the message function. We have added this explanation to Algorithm 3 in Appendix D of our rebuttal revision.

Question 2: Enforcing the joint capacity constraint

Response: Thank you for raising this point. We agree that this should be stated explicitly: Algorithm 4 does not enforce the joint capacity constraint in Eq. (1), and the joint capacity constraint is enforced by the environment. Each agent's action mask checks only that agent's own action against the remaining capacities, since checking the joint action would require selecting actions over the joint action space, i.e., centralized control. When the chosen actions jointly exceed the remaining capacity of an environment element, the environment selects at random which of the conflicting actions are executed. The other agents commit to no element (∅\varnothing, Section 3) in that step, so the executed joint action always satisfies Eq. (1). On MACTP, such an agent stays at its node, which is imposed by the environment and is not a wait action, and on DFJSP and NCFFSP, the machine is not dispatched. Coordination is thus designed to make such conflicts unlikely, but it does not guarantee that the joint action chosen by the agents is feasible. We have added this description to the MPOMDP formulation of each problem in Appendix A of our rebuttal revision.

Question 3: Rollout loss on the selected plan only

Response: Thank you for this question. Unselected rollouts are excluded from the rollout loss because they influence the executed action only indirectly. Each agent executes the first action of its selected plan, and the advantage A^t\hat A_t evaluates this action. Assigning the same A^t\hat A_t to the actions of unselected rollouts would give them a weak learning signal and add noise to the gradient estimate. Unselected rollouts are nevertheless trained through the shared policy, since all KK rollouts are generated by the same candidate plan generation policy πθplan\pi_\theta^{\mathrm{plan}}, which the rollout loss updates on the selected plan. The proposal loss considers all candidates for a different reason. The KK first actions are drawn jointly without replacement, so their importance ratio is defined on their joint probability as an ordered set (Section 4.4) and is not split into selected and unselected parts. For these reasons, the proposal loss covers all KK first actions, while the rollout loss covers only the selected plan, accepting a bias in the gradient estimate in exchange for lower variance.

Reviewer_ozhVOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper considers multi-agent optimization problems where some information only becomes available during execution. PACT has each agent propose several plans, then uses a graph connecting those plans to shared resources to adjust their scores. Agents execute one action and repeat the process with the updated information. Results on routing and scheduling problems show improvements over the tested baselines, including when moving from small training instances to larger test instances.

Critical strengths
  1. PACT represents competition between agents through the resources their plans share. Its demand-and-capacity interface allows the same coordination framework to be applied to routing and scheduling.
  2. The improvements also appear under single-run greedy evaluation. On the largest DFJSP instance size, PACT reduces cost from MAPPO’s 429.2 to 398.4 while both achieve 100% completion. This provides evidence of better solution quality beyond improvements due to failure penalties or best-of-128 selection.
Critical weaknesses
  1. not yet sure which part of the method accounts for the gains. Both scheduling tasks use a one-step horizon, and the routing experiment does not compare its four-step plans against a trained one-step version. Removing coordination hurts performance, but that does not tell us whether routing communication through resources is better than another way of coordinating the same candidate plans. The DCG comparison is helpful, although it changes more than the communication structure. These are the two ideas the paper emphasizes, so I would like more direct evidence for them.

  2. I also had trouble reconciling the MACTP description with the results. Appendix A.1 says an agent retires after claiming a goal and that all goals must be claimed. How, then, do instances with four agents and six goals achieve high success rates? This may just be a wording issue, but it matters for understanding whether the simulator and solver baselines solve the same problem.

Questions for authors
  1. How does a separately trained one-step PACT compare with the four-step version on MACTP, with the other settings kept comparable? This would help me judge the contribution of planning beyond the next action.

  2. Have you compared the trace-graph with an agent-centric coordination module that receives the same candidate-plan information? A difference in quality or runtime would make the case for resource-based coordination more convincing.

4 comments
AuthorsOpenReview ↗

Comment 1 of 2: Response to Weakness 1 (Part A)

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: Evidence for the two main ideas

Response: Thank you for pointing this out. We added one ablation for each of the two ideas, and in both the full method has the lower mean cost on every configuration tested.

Planning horizon. This point was also raised by Reviewer TQtQ (Weakness 4). In the paper, PACT plans Hp=4H_p = 4 steps ahead on MACTP and Hp=1H_p = 1 step on DFJSP and NCFFSP. We have now trained a separate PACT model with Hp=1H_p = 1 on MACTP, keeping the number of candidate plans per agent (KK), the number of coordination rounds (RR), the training configuration and all other settings identical to the Hp=4H_p = 4 model. Due to the limited rebuttal period, the Hp=1H_p = 1 model 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 (mean over seeds, with the lower cost in bold).

MACTPHpH_p16×4×6 (ID)32×6×10128×12×24512×24×481024×32×64
Cost ↓43.665.7918.672.386.1
15.818.2336.082.7114.2
Success (%) ↑499.199.699.799.099.6
197.898.697.898.699.2
Objective ↓43.435.6817.846.270.5
13.556.1118.351.374.2

We have included these results in Appendix C.4 of our rebuttal revision (Table 8). It can be observed that the Hp=4H_p = 4 model attains lower cost, higher success and lower objective on all five configurations. On most configurations, the cost gap comes mainly from failed episodes, since cost includes failure penalties. The objective over successful episodes differs less.

MACTP and the scheduling problems need different horizons because contention arises at different distances. On MACTP, goals typically lie several moves away, so a plan must span multiple steps before two agents' contention for the same goal becomes visible. On DFJSP and NCFFSP, each dispatching action directly occupies a job, so contention is already exposed by the first action of a plan, and Hp=1H_p = 1 suffices. We have added this explanation to Appendix B.4. Section 5.3 now summarizes the ablation as support for multi-step coordination where contested resources lie several steps ahead.

AuthorsOpenReview ↗

Comment 2 of 2: Response to Weakness 1 (Part B), Weakness 2 and Questions 1-2

Weakness 1 (continued)

Coordination medium. This point was also raised by Reviewer gzzc (Weakness 1 and Question 1). We have added PACT-AC, an agent-centric variant of PACT. 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. Unlike DCG, PACT-AC keeps the candidate plans (K=4K = 4), the coordination rounds (R=2R = 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). PACT-AC is likewise trained with 5 of PACT's 10 seeds. The results under greedy decoding are summarized below (cost, with success in % in parentheses and the lower cost in bold).

MACTP16×4×6 (ID)32×6×10128×12×24512×24×481024×32×64
PACT3.66 (99.1)5.79 (99.6)18.6 (99.7)72.3 (99.0)86.1 (99.6)
PACT-AC3.97 (97.0)6.69 (97.6)23.3 (94.4)157.7 (84.2)420.7 (74.6)
DFJSP20×8×6 (ID)30×14×650×16×880×20×8120×24×10
PACT162.5 (100.0)141.5 (100.0)233.2 (100.0)283.9 (100.0)398.4 (100.0)
PACT-AC168.2 (100.0)157.0 (100.0)250.0 (100.0)301.4 (100.0)420.8 (100.0)
NCFFSP20×4×3 (ID)30×6×350×7×380×6×4120×8×4
PACT41.5 (100.0)35.9 (100.0)48.8 (99.9)83.4 (99.7)86.7 (99.4)
PACT-AC49.5 (100.0)44.3 (100.0)55.9 (99.2)91.5 (98.8)92.3 (98.4)

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

Weakness 2: Retirement after claiming a goal in MACTP

Response: Thank you for pointing this out. This point was also raised by Reviewer TQtQ (Question 1). The wording of Appendix A.1 was misleading: an agent covers a goal by visiting it and need not stop there, so four agents can cover six goals. Claiming is an optional terminate action that retires the agent. Since agents cannot wait in place, it is the only way to stop incurring travel cost. The solver baselines follow the same coverage and claiming rules as the simulator: each agent's walk may cover several goals and ends at an unclaimed goal, with at most one agent ending at each such goal. The resulting walks are executed in the simulator, so their reported cost follows the same rules. We rewrote Appendix A.1, and its formulation now states the end-of-walk rule explicitly (Eqs. (17)–(18)). The solvers already enforced this rule, so no result changes.

Question 1: Separately trained one-step PACT on MACTP

Response: We address this in our response to Weakness 1 (Planning horizon). In short, PACT with Hp=1H_p = 1 has higher cost, lower success and higher objective than with Hp=4H_p = 4 on all five MACTP configurations.

Question 2: Agent-centric coordination with the same candidate plans

Response: We address this in our response to Weakness 1 (Coordination medium). In short, PACT has lower cost than PACT-AC, an agent-centric variant of PACT, across all 15 configurations while achieving equal or higher success. PACT-AC is faster on DFJSP and NCFFSP and slower on MACTP.

Thank you for the detailed rebuttal and additional experiments.

The comparison with PACT-AC, the 1-step results on MACTP, and the clarification about termination rule in MACTP addressed most of my concerns. So I raised my score to 3.

Thank you for reading our response and for raising your score. We are glad that the comparison with PACT-AC, the one-step results on MACTP and the clarification of the termination rule in MACTP addressed your concerns. Your suggestions made the evidence for the two main ideas of PACT more direct.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.