acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Master-Mind: Joint Action Refinement through Iterative Intent Denoising in Multi-Agent Pathfinding

Abstract

Decentralized multi-agent path finding (MAPF) with communication requires agents to reach individual goals without collisions under partial observability. Learnable policies trained on expert data provide an effective approach to this problem. However, when several coordinated joint actions are valid in the same context, independently sampling from per-agent distributions can recombine locally valid choices into incompatible joint actions. This failure can arise from the final sampling mechanism even when the per-agent action distributions are learned correctly. DMM (Decentralized Master-Mind) addresses this by replacing one-shot action sampling with discrete, iterative refinement of action intents across communication rounds, inspired by iterative refinement in generative models such as diffusion and flow matching. Agents initialize random action intents and refine them through local communication, coupling their choices before commitment. DMM is pretrained with imitation learning on expert MAPF solutions and further optimized with MICPO, a critic-free group-relative reinforcement-learning method designed for multi agent, multi-round action refinement. DMM generally achieves higher success rates and lower solution costs than the evaluated learnable baselines. On 1,600 MovingAI tasks, DMM fine-tuned with MICPO solves 1,598, the highest coverage among the evaluated methods, while achieving solution costs close to those of the strongest baselines. DMM also scales to over one million simultaneously acting agents in obstacle-containing environments. These results show that round-level intent refinement can substantially improve joint-action coordination while preserving decentralized execution.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Multi-Agent Pathfinding, Multi-Agent Coordination, Learned Communication, Imitation Learning, Multi-Agent Reinforcement Learning, Decentralized Planning, Generative Policies

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_aJUMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates the coordination failure that arises when agents sample actions independently based on marginal policies that are locally rational yet mutually incompatible. The authors first characterize this limitation through a KL-divergence decomposition, linking the approximation gap—stemming from conditionally independent execution—to "conditional total correlation" and "missing information." To address this, the authors propose the "Decentralized Master-Mind" framework, in which each agent maintains a stochastic intent representation. This representation is iteratively refined through multiple rounds of synchronized local communication and a discrete voting mechanism, ultimately guiding the agents' specific actions within the environment. The approach is evaluated on the "Diagnostic Corridor" task, the POGEMA benchmark, and large-scale MovingAI instances, using model versions with 3 million and 800,000 parameters, respectively. Furthermore, the paper presents a GPU-accelerated implementation that integrates DMM with CS-PIBT, capable of handling synthetic scenarios involving up to approximately one million agents.

Critical strengths
  1. This work addresses a genuine and significant challenge in decentralized MAPF: in scenarios requiring coordination—such as "you go left, I go right" or one agent yielding while another passes—the marginal distributions of individual agents may appear reasonable in isolation, yet independent sampling can lead to inconsistent joint actions. The paper provides a clear theoretical formulation of this issue by characterizing the KL divergence between the optimal product distribution and the expert joint distribution, using terms for conditional total correlation and missing information.

  2. The mechanism for iteratively sharing "intents" is intuitively appealing and compatible with local, synchronous communication. Each agent begins with a stochastic intent and, through multiple rounds of broadcasting, discrete voting, and intent updates, eventually commits to a final action. Unlike a single-shot communication scheme, this approach allows agents to observe the gradual convergence of others' intents—a logical mechanism for distributed symmetry breaking. Furthermore, the evaluation of the method using both 3M and 0.8M parameter-scale models demonstrates that it does not rely exclusively on massive neural networks.

Critical weaknesses
  1. The theory merely establishes the existence of an expressivity gap when using "conditionally independent final-action sampling"; it does not prove that DMMs can bridge this gap. The KL-divergence decomposition demonstrates that a product distribution cannot, in the general case, represent the joint distribution of expert actions—this serves as a diagnostic of the problem, not a guarantee regarding the correctness, convergence, or expressive capacity of DMMs.

  2. The use of teacher forcing—maintained at a rate of 0.8—effectively injects expert trajectories into the model to a very high degree. Since no expert input is available during deployment, a significant train–test exposure bias is introduced. Consequently, it is impossible to determine whether the performance gains of the DMM stem from its inference mechanism or from the high proportion of teacher forcing employed.

Questions for authors

See Weaknesses

2 comments

We sincerely thank the reviewer for the detailed feedback and for recognizing the importance of the coordination problem, its theoretical formulation, and the intuition behind iterative intent exchange. It helped us tie the theory more closely to DMM's mechanism and clarify the role of teacher forcing. Changes made in response to this review are highlighted in green.

W1

We agree with the reviewer that the decomposition in Section 4 (the factorization-gap proposition) only diagnoses the limitation of independent final-action sampling; it does not establish correctness or convergence guarantees for DMM itself.

Our additional theoretical result concerns expressive capacity. Appendix B.4 now gives a constructive result for the corridor: under explicit expressivity assumptions, exchanging initial intents lets the two agents agree on who moves and who waits, and repeated votes make their joint-action distribution approach the expert distribution. This shows that the mechanism can approximate the expert joint-action distribution beyond the limits of independent final-action sampling. Still, it does not show that training finds this solution or guarantee that the mechanism generalizes to other settings.

Whether trained models learn such coordination is therefore an empirical question. We compute the empirical KL divergence separately for each of the five independently trained checkpoints before averaging (Appendix H.2, Table 9). For the same checkpoints, the mean KL divergence decreases from 0.067 with four refinement rounds to 0.015 with eight rounds. Both values are well below 0.693, the theoretical lower bound for independent final-action sampling. Every checkpoint's estimate falls below this bound, providing empirical evidence that DMM learns coordinated joint actions in the corridor.

SettingKL divergence
DMM, 4 rounds0.0671 ± 0.0136
DMM, 8 rounds0.0151 ± 0.0118
Independent action sampling; Theoretical lower bound0.6931

DMM values are reported as the mean ± the half-width of the 95% Student's t confidence interval across five independently trained checkpoints, with 1,000 joint-action samples drawn from each checkpoint. KL divergence is computed separately for each checkpoint against the equal-weight expert distribution over the two valid joint actions, using natural logarithms.

W2

All reported benchmark scores are obtained without teacher forcing. Teacher forcing is used only during imitation pretraining; MICPO rollouts, fine-tuning, and evaluation use the model's own intents and votes. The 0.8 floor is the minimum probability of using an expert action when constructing the internal intent trajectory during pretraining.

Expert actions guide the initial intents and refinement votes so that agents learn from expert-guided intents communicated by neighboring agents. Once the teacher-forcing probability reaches 0.8, each refinement vote uses a sample from the model with probability 0.2. This introduces no additional expert data: it reuses the labels already present in the training set.

We have expanded Appendix E with ablations of the method's components and training procedures. Section E.2 evaluates DMM with different numbers of communication rounds; Sections E.3 and E.4 examine the contributions of internal communication components and MICPO components. Section E.5 presents training curves across different seeds. Finally, Section E.6 evaluates the effect of teacher forcing during pretraining.

We pretrain DMM-3M on the original dataset with teacher forcing either completely disabled or annealed from 1 to 0.8 over the first 100k updates. Both runs use the same training seed and otherwise identical settings. We evaluate their 200k-update checkpoints on the full POGEMA benchmark (Table 6):

Map familyNo teacher forcingAnneal 1 → 0.8
Random90.0095.39
Mazes86.7292.97
Warehouse97.0198.44
Cities87.6292.73
Overall90.3995.02

In this comparison, teacher forcing during pretraining improves success rates in every map family, raising the overall success rate from 90.39% to 95.02%. These gains persist when evaluation uses no teacher forcing. Although this comparison does not isolate exposure bias, it shows a positive net effect of teacher forcing under the tested schedule.

Teacher forcing alone does not account for the gains. In Appendix E.3, Table 4, all variants are retrained with the same teacher-forcing schedule, annealed from 1 to 0.8. Removing intent messages lowers the success rate by 10.0 percentage points. In the corridor, the results also suggest that maintaining a nonzero teacher-forcing floor helps the model learn coordinated joint actions: DMM trained with a zero floor produces valid joint actions about 50% of the time, similar to the independently sampling baselines (Table 2). These findings support the role of teacher forcing in learning to coordinate through refinement; teacher forcing is not used at evaluation.

Thank you again for your constructive review. We have provided detailed replies and uploaded a revised manuscript addressing your comments.

Given the borderline assessment and the approaching end of the discussion period, could you kindly let us know whether there are any remaining concerns about the paper that we could clarify or address?

Reviewer_Qn6yOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

Decentralized Master-Mind aims to tackle Multi-agent Path Finding (MAPF) with a diffusion / flow-matching inspired iterative refinement via communicating the intent of nearby agent, that changes every iteration, allowing for nearby agents to couple their choices before committing to an action. This method directly tackles a key issue in MAPF exemplified by the two-agent symmetric corridor conflict example where the joint action distribution has multiple valid modes but since agents sample their actions independently it might lead to invalid actions.

Hence, this paper pre-trains a decentralized policy with imitation learning using the proposed iterative refinement with evolving intent method and further improve the task performance of the learned decentralized policy with what they call Multi-agent Iterative Commitment Policy Optimization (MICPO) which is inspired by GRPO. The strong performances, decent runtime and scalability of DMM+MICPO is demonstrated with two different benchmarks (POGEMA and MovingAI) with up to a million agents. In the POGEMA benchmark, the best performing DMM+MICPO variant out-performs all previous SOTA method and comes close to LaCAM* centralized solver with optimal guarantees.

Critical strengths
  1. The authors identify a clear and consequential problem in current MAPF methods (the multimodality of optimal joint actions), explains it well through a didactic example (symmetrical corridor) and provided some theoretical backing to its claims (minor proofs in Decentralized Factorization Gap section).
  2. The novelty is clear compared to other MAPF methods and the paper positions it well with sufficient related work and additional related work in the appendix on relevant methods. Taking inspiration from diffusion, which is currently pervasive in the AI / Robotics field, and adapting the core idea of iteratively refining given some observation to the multi-agent context is novel, original and done elegantly. The same could be said about the adapting GRPO to the multi-agent context (MICPO) but I am not entirely familiar with GRPO. Nonetheless, the inspiration from prior method is clear and the adaptation to MAPF is done well and considers the intricacies / complexities of having to coordinate multiple agents and sharing evolving intent.
  3. Well-rounded experiments strongly validate the proposed method. The experiments include multiple baselines, two different benchmarks, scalability up to a million agents and ablations on core mechanisms. The metrics reported are also sufficient and includes both performance and runtime, showing that there is no trading of runtime for performance and DMM has significant edge over baselines.
Critical weaknesses
  1. The authors mention inspiration from diffusion / flow matching but do not provide enough related work or a comparison with other possibly similar methods from diffusion in the main text. Readers might not be able to fully discern the contribution of DMM from the main text as there is no comparison to possibly similar ideas in the context of diffusion.
  2. Some minor clarity issues including
  • Brief descriptions of the benchmarks and how they differ in the introduction and experiments. It is unclear as to why MovingAI benchmark requires additional components like shielding and Repeat-State-Escape vs POGEMA.
  • Mentioning K (number of iterations) in Figure.1 without proper definition.
  • SoC (Sum of Cost) and MS (Max Span) not mentioned before abbreviation.
Questions for authors

Apart from the weaknesses mentioned.

  1. Why are the other types of baselines that were mentioned in the related work, e.g. direct local prediction methods, unused for benchmarking?
  2. Unsure about the Repeat-State-Escape, why is it needed on MovingAI but not in POGEMA? Giving more information about the benchmark might help with clarity of the experiment section.
2 comments

We sincerely thank the reviewer for the thoughtful and encouraging feedback and for recognizing the paper's motivation, novelty, and experimental evaluation. The constructive suggestions have helped us improve the paper's clarity, strengthen its positioning relative to prior work, and broaden the empirical comparisons. We have revised the manuscript accordingly, with changes made in response to this review highlighted in blue. Below, we respond to each concern and question.

W1

We have expanded the discussion in Section 2, Related Work, and added citations to foundational diffusion and flow-matching papers (Ho et al., 2020; Lipman et al., 2023).

In the main-text Related Work section, we now explicitly contrast DMM with DiffLNS, MADiff, and AID. DiffLNS centrally generates joint plans for search-based repair, MADiff's decentralized variant predicts teammates without online communication, and AID exchanges trajectory-derived intent distributions. DMM instead exchanges evolving one-step action intents during refinement, allowing neighbors to coordinate before commitment. We also clarify there that diffusion and flow matching inspire refinement from random initialization, while training uses imitation learning and MICPO.

W2

We have clarified the motivation for the two evaluation protocols in the opening paragraph of Section 5 (Experiments). POGEMA provides a framework for training and evaluating learned policies; we use it to assess their coordination behavior without additional action correction. MovingAI provides standard MAPF instances for comparing solvers, including classical search-based and hybrid approaches. Neither CS-PIBT nor RSE is required to evaluate DMM on MovingAI: both are optional additions to the learned policy. In our main MovingAI experiments, we use CS-PIBT and RSE with DMM and HMAGAT to improve their performance and compare them with classical search-based and hybrid methods. These configurations are not decentralized because CS-PIBT and RSE use the global configuration. With these additions, DMM achieves results competitive or even better than the evaluated search-based and hybrid approaches.

We have clarified the optional nature of CS-PIBT and RSE in Section 5 and added MovingAI experiments without RSE in Appendix I. We also define K in the caption of Figure 1 as the number of intent-refinement rounds per environment step and introduce sum of costs (SoC) and makespan (MS), together with their mathematical definitions, in Section 3 (Problem Setup).

Q1

Direct local prediction was already represented by MAPF-GPT. We have broadened the POGEMA comparison with PRIMAL, DHC, DCC, SCRIMP, and additional MAPF-GPT sizes to assess direct local prediction and communication-based policies without additional action correction. Appendix I, Tables 10 and 11, reports their success rates and sum of costs; Tables 12 and 13 provide a separate comparison of solvers using CS-PIBT on MovingAI. We will release the evaluation configurations, checkpoint references, and commands used for all baselines in our repository to make these comparisons reproducible.

Q2

We included RSE to improve solver performance on MovingAI: CS-PIBT prevents collisions but can revisit earlier configurations, so RSE considers alternative actions when this occurs. It is an optional solver component, not a benchmark requirement. POGEMA instead evaluates learned policies without additional action correction.

Appendix F.1, Table 7, shows that our main DMM configuration achieves lower sum of costs, while sampling without RSE retains almost identical success rates, differing by at most one solved task out of 1,600 for both DMM models. Thus, DMM retains high success rates without RSE.

Thank you for taking your time to address my concerns regarding the positioning of your paper with respect to diffusion and expanding the comparisons with other baselines, unfortunately, I am unable to raise my score further!

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

DMM improves decentralized MAPF by exchanging and refining stochastic action intents before commitment. It combines imitation learning with MICPO group-relative fine-tuning. A KL decomposition explains why independent per-agent sampling may produce incompatible joint modes. The experiments evaluate unshielded policies, shielded solvers, controlled corridor conflicts, and million-agent execution scenarios.

Critical strengths
  1. Clear mechanism with direct evidence. The factorization analysis is supported by a controlled corridor test: valid joint actions rise from roughly 50% for independent-sampling baselines to 94.8 with four refinement rounds and 99.9% with twelve(Appendix H.2).
  2. Strong stand alone and systems results. Unshielded POGEMA tests support the policy contribution: success reaches 0.922 versus LC-MAPF's 0.805 on the largest Cities-Tiles setting. MovingAI and million-agent experiments provide additional practical evidence.
Critical weaknesses
  1. The ablation in Appendix E.3 modify communication inpus only at test time, while the models were trained with the full inputs. The resulting performance drop may therefore reflect a mismatch between training and test inputs, rather than solely the benefit of intent communication. Retraining the ablated variants would help separate these effects.
  2. Fine-tuning improves performance, but shared-intent grouping, conponent-wise normalization, and extreme-trajectory replay are not separately ablated. A simpler establish which adaptations matter. Selecting only extreme-return trajectories also changes the optimization distribution and deserves analysis.
  3. Moving AI uses different time and step budgets, and primary SoC distributions use method-specific solved cohorts. Million-agent execution additionaaly uses unshielded results, but restrict claims about comparative efficiency and fully decentralized scalability.
Questions for authors
  1. How do the ablated variants perform when retrained with their modified communication inputs, so that training and test inputs match?
  2. Which components improve performance under matched budgets, and how variable are results across training seeds?
  3. Can the authors report equal-time success curves,common-cohort SoC, and large scale policy-versus-shielding costs and intervention rates?
2 comments

We thank the reviewer for the constructive feedback and for recognizing the clarity of DMM's coordination mechanism and the strength of our empirical results. These suggestions have helped us strengthen the component ablations, assess variability across training runs, and clarify the benchmark comparisons and scalability results. We have revised the manuscript accordingly, with changes made in response to this review highlighted in purple. Below, we respond to each concern and question.

W1 and Q1

We have added retraining experiments in Appendix E.3, Table 4. Each variant is trained from scratch for 200,000 updates on the same subset of the original dataset, using paired seeds and the same communication rule during training and evaluation.

Across four paired runs, DMM achieves 90.89% success on POGEMA, compared with 80.86% without intent messages, 85.90% with fixed intent broadcasts, and 87.99% without learned feature messages. DMM also achieves the lowest mean SoC. These results show that the benefit of evolving intents persists when training and test inputs match. Learned feature messages give a smaller and more variable gain: the full model is ahead in each of the four paired seeds, by 0.4 to 5.5 percentage points.

W2 and Q2

We have added matched-budget ablations in Appendix E.4, Table 5, using the same pretrained DMM-3M checkpoint and 96,000 MICPO updates. Full solves approximately 18 more tasks on average across the two seeds and achieves 5.2% lower mean SoC than the all-off control. Uniform replay alone costs about as much as switching all three adaptations off, so extreme-trajectory replay accounts for most of this difference; single normalization and independent initial intents reduce success by 3-4 and 3-9 tasks, respectively, with similar SoC.

Appendix D.3 clarifies that all 24 trajectories determine advantage normalization, while only the top four and bottom four by raw return are replayed, reweighting optimization. Uniform selection of eight trajectories tests this choice at the same replay budget.

A second fine-tuning seed reproduces Full's advantage over uniform replay. Both repeats start from the same pretrained checkpoint:

Fine-tuning runConfigurationSuccess, %Mean SoC
1Full98.842,845.32
1Uniform replay98.182,979.33
2Full98.872,840.56
2Uniform replay98.032,980.92

Success and mean SoC use all 3,193 POGEMA scenarios, including failures. Unfinished agents contribute the episode horizon.

Appendix E.5 additionally reports three independent pretraining runs, with MICPO on two of them yielding SoC reductions of 13.8% and 14.1%. All component ablations in Table 5 now include both fine-tuning seeds.

W3 and Q3

We have added Appendix F.2 with success curves at common runtime thresholds and pairwise SoC comparisons on common solved instances.

For the success curves, each point reports the fraction of the same 1,600 MovingAI instances solved within the corresponding runtime threshold, using recorded solver runtimes. Unsolved instances remain in the denominator.

For SoC, we compare each DMM-MICPO variant with every other method on the instances solved by both within 600 seconds, with each pair's sample size reported in the legend. We deliberately use pairwise common cohorts: restricting every comparison to instances solved by all six methods would exclude challenging instances that some methods solve but others cannot. The curves show the fraction of each pair's common cohort on which one method reduces SoC by at least the indicated percentage. Solid lines favor DMM-MICPO; dashed lines favor the compared method.

For the large-scale experiments, the million-agent figure shows how policy, shielding, and observation-preparation costs evolve throughout a rollout. The scalability appendix additionally reports mean, 99th-percentile, and maximum stage times across four runs at each population size. At 1,048,576 agents, the mean costs are 439.9 ms per step for policy inference with message passing, 249.2 ms for CS-PIBT with action broadcast, and 73.5 ms for observation preparation.

These experiments evaluate the locally communicating DMM policy combined with centralized CS-PIBT. DMM completes all 16 large-scale scenarios, whereas GPU-PIBT reaches the 32,768-step horizon without completing any. At one million agents, DMM's mean step time is 763 ms, compared with 229 ms for GPU-PIBT; its benefit in this experiment is successful completion at a higher computational cost per step.

We also report shielding intervention rates. An intervention occurs when the executed action differs from the highest-scoring valid proposal before CS-PIBT conflict resolution. Each run's rate is normalized by all agent-step decisions. Averaged equally over four runs per population, the rates are 0.30%, 2.36%, 6.95%, and 11.42% at 131,072, 262,144, 524,288, and 1,048,576 agents, respectively. Table 8 in Appendix G reports the corresponding ranges across runs.

After carefully reading the authors' rebuttal, I find that my main concerns have been adequately addressed:

  1. W1/Q1 (component ablations): The new retraining experiments in Appendix E.3 (Table 4), with paired seeds and matched train/test conditions, convincingly show that the benefit of evolving intents persists.
  2. W2/Q2 (matched-budget ablations): The new ablations in Appendix E.4 (Table 5) isolate the contribution of extreme-trajectory replay, and the second fine-tuning seed reproduces the Full model's advantage. The additional pretraining runs in Appendix E.5 further address my concern about run-to-run variability.
  3. W3/Q3 (runtime and scalability): The success curves at common runtime thresholds and the pairwise SoC comparisons on common cohorts (Appendix F.2) are a fair and informative way to handle the comparison. The reported shielding intervention rates at million-agent scale are also valuable new information.

Given that my concerns have been addressed with solid experimental evidence, I am raising my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal and Revisions

We sincerely thank the reviewers for their thoughtful feedback. We appreciate their recognition of DMM’s clear coordination mechanism and empirical results (Reviewer b24y), the originality of intent refinement and breadth of evaluation (Reviewer Qn6y), and the importance of the coordination problem, its theoretical formulation and iterative intent exchange (Reviewer aJUM). Their comments helped strengthen the component studies, clarify training and improve benchmark comparisons.

We have provided detailed replies to each reviewer. The main revisions are summarized below:

  • We added a constructive corridor result for coordination through exchanged intents under explicit expressivity assumptions, alongside joint-action KL divergences across independently trained checkpoints. These distinguish theoretical capacity from learned coordination. See Appendices B.4 and H.2, Table 9. (Reviewer aJUM.)

  • We clarified that teacher forcing is confined to imitation pretraining and absent from MICPO and evaluation. A matched comparison with and without teacher forcing shows a benefit when evaluation uses no expert guidance. The communication ablations separately compare variants with identical teacher-forcing schedules. See Appendices E.3 and E.6. (Reviewer aJUM.)

  • We retrained communication variants with matching training and test inputs and added matched-budget MICPO ablations and additional independent training runs. These support the benefit of evolving action intents and identify extreme-trajectory replay as a major contributor to fine-tuning gains. We also clarified trajectory selection and its use in policy updates. See Appendices D.3 and E.3–E.5. (Reviewer b24y.)

  • We added MovingAI success curves at shared runtime thresholds and pairwise cost comparisons on common solved instances. Million-agent results report stage-wise computation costs and shielding intervention rates, explicitly distinguishing the decentralized policy from centralized shielding used in these runs. See Appendices F.2 and G. (Reviewer b24y.)

  • We expanded related work to clarify DMM’s diffusion and flow-matching inspiration and its differences from related methods. We broadened baseline comparisons and clarified benchmark protocols, notation and the optional roles of shielding and repeat-state escape. See Sections 2, 3 and 5 and Appendices F.1 and I. (Reviewer Qn6y.)

We appreciate the follow-up from Reviewers b24y and Qn6y, including b24y’s confirmation that their main concerns were addressed. We thank the Area Chair for facilitating discussion; we have not yet received further feedback on theoretical scope and teacher forcing (Reviewer aJUM).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.