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