- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This work proposes PGFS (Path-Guided Frontier Search), which selects nodes directly from the frontier of the search tree using a global score based on cumulative path statistics. This turns each search step into a single batched GPU operation instead of the slow step-by-step tree walk in standard MCTS. It also runs training fully on the GPU. It beats strong model-based multi-agent RL baselines on sample efficiency while training up to 16.3x faster on a single GPU.
Critical strengths
- The engineering is careful and convincing, with effectiveness and speedups held up across benchmarks
- The idea is simple and fits the hardware. It's easy to understand and implement, and it maps naturally onto GPUs. The multi-GPU design (implementation) is elegant.
- Clear ablation and analysis: the per-component profiling shows exactly where time goes, and how the bottleneck moves from search to training. Evaluation settings are also thorough.
Critical weaknesses
- Proposed components such as on-GPU training, GPU tree search, frontier-style search mostly exist already; more elaboration and isolated comparison with them to show the uniqueness is needed, e.g., for the search Levin Tree Search or best-first search may work work similarly?
- Gumbel MCTS learns just as well from the same amount of data. PGFS gets there while evaluating about 40x more positions per search. Its real gain is a search that runs faster at the settings used in training.
- The headline wins over MAZero can be confounded. MATCHA also changes the policy loss, adds a discount head, and reimplements everything. On Overcooked, MAZero scores about zero even where simple baselines learn, which looks like a broken baseline.
- Needs more apple to apple comparison, e.g., it compared a new GPU implementation against MAZero's original CPU-based code.
- How the baselines were set up isn't described. MAZero and MAMBA were built for other environments, and the paper doesn't say how they were adapted or tuned
Questions for authors
- The 100 expansions per search still happen one after another, just like in MCTS. Only two things run in parallel: scoring the whole list in one step, and evaluating all children of the chosen leaf at once?
- Why expand only one leaf per step? Expanding many at once would be the genuinely parallel version.
- How does PGFS do on a single-agent benchmark? Nothing in it is specific to multiple agents?
- What happens if PGFS evaluates one child per step instead of all 40?
7 comments
W2-W3
W2: Gumbel MCTS learns just as well from the same amount of data. PGFS gets there while evaluating about 40x more positions per search.
A: We thank the reviewer for this observation. We would like to clarify that, for fair comparison and speed consideration, the actual implementation of PGFS does not evaluate each child node during expansion. Instead, child nodes inherit their parent’s value estimate for selection. A node is evaluated only when it is selected for expansion, exactly as in MCTS and Gumbel MCTS. Therefore, none of the PGFS experiments reported in the paper uses 40× as many evaluations. All comparisons use the same numbers of simulations and evaluations. As supporting evidence, Appendix A.13 shows that wall-clock time is nearly identical for , which would not hold if all K children were evaluated.
On the nature of the gain, we agree with the reviewer that the gain is speed, and this is our intended claim: PGFS matches or exceeds the sample efficiency of Gumbel MCTS at a much lower wall-clock cost (Figures 7 and 12).
W3: The headline wins over MAZero can be confounded. MATCHA also changes the policy loss, adds a discount head, and reimplements everything. On Overcooked, MAZero scores about zero even where simple baselines learn, which looks like a broken baseline.
A: We thank the reviewer for the careful reading and address each point in turn.
1. Discount prediction is not a difference between MATCHA and the baselines. On Overcooked and MPE, discount prediction is enabled for all model-based methods (MATCHA, MAZero and MAMBA) to account for episode truncation. On SMAX it is disabled for all of them. The wording in Appendix C suggested otherwise, and we have corrected it.
2. The policy loss does not drive the results. We use a cross-entropy loss because the PGFS policy target already incorporates value information. The GPU MCTS and GPU Gumbel MCTS variants share exactly this loss, yet their sample efficiency differs widely (Figures 7 and 12). The differences therefore come from the search procedure, not the loss.
3. The headline results do not depend on Overcooked. On SMAX alone, the throughput speedup over MAZero is 18.0× (63.84 vs. 3.54 FPS), above the 16.3× average. MATCHA also reaches the 0.8 win-rate threshold in fewer samples than MAZero on all 10 SMAX maps (Table 3).
4. The MAZero baseline is sound.
- Implementation: we use the official implementation, and our runs on the original SMAC match its published curves.
- SMAX: the same code learns well and is the strongest baseline there in sample efficiency.
- Tuning: starting from its SMAC configuration, we swept
sampled_action_timesandnum_simulationsand retained the defaults. On Overcooked we additionally swept the update-to-data ratio and report the best setting (0.2). - MAMBA: an independent official model-based implementation, also tuned, likewise fails to reach the threshold on 4 of 5 Overcooked layouts within 1M steps (Table 4).
We therefore believe the Overcooked result reflects a real difficulty of existing model-based MARL methods on sparse-reward, long-horizon tasks, not a faulty setup.
W4-W5
W4 Needs more apple to apple comparison, e.g. a new GPU implementation against MAZero's original CPU-based code.
Re: We would like to clarify the experimental design, which we believe already provides the controlled comparison requested, shown in Table 1 and Figures 2b, 7 and 12.
1. Our goal is not a faster implementation of MAZero. We propose a new search algorithm (PGFS) and a device-centric architecture, and claim that together they greatly reduce wall-clock time while retaining the sample efficiency of search-based MBMARL. MAZero is the state-of-the-art reference for this claim. We therefore use its official implementation, run on identical hardware (Appendix A.2), which is standard practice and the strongest available version of the baseline.
2. Controlled comparisons of the search algorithm are shown in Table 1, Figures 2b, 7, 12. To isolate PGFS, we hold the implementation fixed and change only the search. MATCHA w/ GPU MCTS and w/ GPU Gumbel MCTS run in the same device-centric framework, on the same GPUs, with the same hyperparameters. From Table 1, PGFS is 3.2–3.6× faster per training step than GPU Gumbel MCTS and 5.3–6.2× faster than GPU MCTS. Timing one search in isolation (Figure 2b), PGFS is 15.5× and 18.2× faster at N = 350. Figures 7 and 12 show that this does not cost sample efficiency.
Summing the per-component costs in Table 1 gives the time per training step:
| Method | 3s_vs_5z (s) | 2s3z (s) |
|---|---|---|
| MAZero (CPU-centric) | 0.402 | 0.385 |
| MATCHA w/ GPU MCTS | 0.091 | 0.089 |
| MATCHA w/ GPU Gumbel MCTS | 0.053 | 0.053 |
| MATCHA (PGFS) | 0.015 | 0.017 |
- Architecture: moving from MAZero to a GPU-resident tree search gives a 4.3–4.4× speedup.
- PGFS: with the implementation held fixed, PGFS gives a further 3.2–3.6× over GPU Gumbel MCTS and 5.3–6.2× over GPU MCTS.
- Where the gain is: it is concentrated in the search-bound stages. Against GPU Gumbel MCTS, data collection is about 16× faster and reanalysis 3.9–5.8× faster.
As shown in Table 2, 16.3×overall speedup is the end-to-end gain over the existing pipeline, which is what a practitioner would experience. We do not attribute it to the search algorithm alone; Table 1 separates the architecture and search contributions.
W5: How the baselines were set up isn't described.
Re Thank you for highlighting this omission. We used the official implementations of https://github.com/bold-lab-ai/JaxMARL, https://github.com/jbr-ai-labs/mamba, and https://github.com/liuqh16/mazero.
- Model-free baselines. We started from JaxMARL’s environment-specific tuned configurations and conducted additional sweeps. We retained the defaults for IPPO and MAPPO, and selected
NUM_ENVS=1andNUM_EPOCHS=2for VDN, QMIX, and IQL to improve sample efficiency. - MAMBA. We started from its default SMAC/MPE configurations and conducted additional sweeps. We set
n_workers=4across SMAX, Overcooked, and MPE to improve training speed without compromising sample efficiency. For Overcooked, we compared both advantage normalization settings (it’s enabled for MPE and disabled for SMAC by default) and disabled it based on slightly better sample efficiency. - MAZero. We started from its SMAC configuration for SMAX and MPE, swept
sampled_action_timesandnum_simulations, and retained their default values. On Overcooked, MAZero still struggled after sweeping its update-to-data ratio ; the reported results use UTD = 0.2. We also finetuned its actor parallelism to improve wall-clock efficiency (15 workers for 1 GPU and 27 workers for 2 GPUs). However, despite all these efforts, we still could not make MAZero work on Overcooked.
For the model-based baselines, we enabled discount prediction on MPE and Overcooked to account for episode truncation.
It’s worth mention that MATCHA uses the same core hyperparameters across tasks, with discount prediction enabled only for MPE and Overcooked, showing a significant lower hyper-parameter tuning effort comparing with MAZero. Upon acceptance, we will release all evaluation scripts, including those for the baselines.
W1
W1: LevinTS and best-first search may work similarly.
A: We respectfully disagree with this. Although PGFS, LevinTS, and best-first search share a common component called “frontier”, they differ fundamentally in their scope and level of specification. Treating LevinTS or best-first search as a direct replacement for PGFS therefore is not proper.
PGFS is designed for finite-budget policy improvement within a MuZero-style model-based RL framework. Its design specifies how to incorporate model-predicted policy priors, rewards, and values to do action selection and backup; how to construct an improved policy; and how to estimate root-state and root-action values. It therefore comprise substantially more than a frontier-sampling step.
In contrast, the original Levin TS is a heuristic search algorithm for goal-reaching problems. Its search criterion does not incorporate rewards or value estimates, and it does not specify how to construct an improved policy or estimate state and action values. Replacing PGFS with LevinTS in our framework would require substantial algorithmic extensions to define all these components mentioned above. Such extensions establish the interface between planning and learning and are substantive parts of an RL planning algorithm, rather than implementation details.
Best-first search, meanwhile, is a broader framework in classical graph theory. It describes the general principle of expanding the most promising node according to a scoring function, rather than uniquely specifying a particular algorithm. Concrete instantiations, such as Greedy Best-First Search (GBFS), present similar substantial adaptation requirements.
Nevertheless, we did our best to integrate the frontier-selection strategies of LevinTS and best-first search into our framework in Appendix A.7, highlighted in red.
For ease of reference, we have organized the results (Fig. 15) shown in the appendix figure into four tables.
Total Transitions - Win Rate (mean ± 95% CI)
Time (hours) - Win Rate (mean ± 95% CI)
Total Transitions - Return (mean ± 95% CI)
Time (hours) - Return (mean ± 95% CI)
As shown in Fig. 15 in the updated version of the paper and these tables, the returns of both baselines increase gradually over 500k environment steps, while their win rates remain at zero throughout. We hypothesize that, under a limited search budget, LevinTS and best-first search can be misled by inaccurate policy priors or value estimates early in training. PGFS combines path priors with return estimates to perform stochastic frontier selection, which may better sustain exploration and help discover coordinated behaviors that lead to wins.