acceptodds
Under review as a conference paper at ICLR 2027

MATCHA: Bridging the Gap between Sample and Wall-Clock Efficiency in Model-Based Multi-Agent Reinforcement Learning

Abstract

Model-based Multi-Agent Reinforcement Learning (MBMARL) has demonstrated superior sample efficiency compared to model-free baselines. However, its practical impact is often limited by high wall-clock training time. To bridge this gap, we introduce **MATCHA**, a system-algorithm co-design that makes search-based MBMARL efficient on modern accelerators. At system level, MATCHA implements an end-to-end, device-centric framework that keeps data collection, planning, and learning on the accelerator, massively reducing costly CPU–GPU communication. At the algorithmic level, we propose Path-Guided Frontier Search (PGFS), which selects nodes directly from the frontier of the tree using a global score based on cumulative path statistics. This reduces selection and expansion to a single vectorized tensor operation, avoiding depth-dependent sequential tree traversal on the GPU. Across SMAX, Overcooked, and MPE, MATCHA matches or exceeds the sample efficiency of strong MBMARL baselines while substantially reducing training time, achieving up to end-to-end wall-clock speedup with minimal GPU resources.

Primary area:
reinforcement learning
Keywords:
multi-agent, model-based, reinforcement learning, wall-clock efficiency, sample efficiency, search, MARL

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_CyuWOpenReview ↗
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
  1. The engineering is careful and convincing, with effectiveness and speedups held up across benchmarks
  2. 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.
  3. 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
  1. 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?
  2. 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.
  3. 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.
  4. Needs more apple to apple comparison, e.g., it compared a new GPU implementation against MAZero's original CPU-based code.
  5. 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
  1. 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?
  2. Why expand only one leaf per step? Expanding many at once would be the genuinely parallel version.
  3. How does PGFS do on a single-agent benchmark? Nothing in it is specific to multiple agents?
  4. What happens if PGFS evaluates one child per step instead of all 40?
7 comments

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)

Method00.1M0.2M0.3M0.4M0.5M
MATCHA w/ PGFS0.00±0.000.00 \pm 0.000.70±0.120.70 \pm 0.120.98±0.040.98 \pm 0.040.95±0.090.95 \pm 0.091.00±0.001.00 \pm 0.00-
MATCHA w/ LevinTS0.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.00
MATCHA w/ Best-First Search0.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.00

Time (hours) - Win Rate (mean ± 95% CI)

Method00.511.5
MATCHA w/ PGFS0.00±0.000.00 \pm 0.000.93±0.140.93 \pm 0.140.98±0.020.98 \pm 0.02-
MATCHA w/ LevinTS0.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.00
MATCHA w/ Best-First Search0.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.000.00±0.000.00 \pm 0.00

Total Transitions - Return (mean ± 95% CI)

Method00.1M0.2M0.3M0.4M0.5M
MATCHA w/ PGFS0.30±0.060.30 \pm 0.061.66±0.121.66 \pm 0.121.98±0.051.98 \pm 0.051.94±0.091.94 \pm 0.092.00±0.002.00 \pm 0.00-
MATCHA w/ LevinTS0.01±0.020.01 \pm 0.020.20±0.000.20 \pm 0.000.21±0.020.21 \pm 0.020.27±0.110.27 \pm 0.110.29±0.090.29 \pm 0.090.34±0.120.34 \pm 0.12
MATCHA w/ Best-First Search0.26±0.060.26 \pm 0.060.52±0.060.52 \pm 0.060.58±0.180.58 \pm 0.180.69±0.120.69 \pm 0.120.73±0.120.73 \pm 0.120.72±0.130.72 \pm 0.13

Time (hours) - Return (mean ± 95% CI)

Method00.511.5
MATCHA w/ PGFS0.30±0.060.30 \pm 0.061.92±0.151.92 \pm 0.151.98±0.031.98 \pm 0.03-
MATCHA w/ LevinTS0.01±0.020.01 \pm 0.020.20±0.000.20 \pm 0.000.26±0.080.26 \pm 0.080.31±0.120.31 \pm 0.12
MATCHA w/ Best-First Search0.26±0.060.26 \pm 0.060.55±0.100.55 \pm 0.100.63±0.040.63 \pm 0.040.70±0.170.70 \pm 0.17

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.

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 K∈5,10,40K\in\\{5,10,40\\}, 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_times and num_simulations and 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 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:

Method3s_vs_5z (s)2s3z (s)
MAZero (CPU-centric)0.4020.385
MATCHA w/ GPU MCTS0.0910.089
MATCHA w/ GPU Gumbel MCTS0.0530.053
MATCHA (PGFS)0.0150.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=1 and NUM_EPOCHS=2 for 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=4 across 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_times and num_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.

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

The paper addresses the slow wall-clock training of search-based MBMARL, where CPU-side MCTS and repeated CPU–GPU transfers offset sample-efficiency gains. MATCHA combines a device-centric, end-to-end vectorized training architecture with Path-Guided Frontier Search (PGFS), which replaces sequential MCTS traversal and backpropagation with global frontier sampling implemented as tensor operations. Experiments on SMAX, Overcooked, and MPE report sample efficiency comparable to or better than MBMARL baselines and up to 16.3× higher average throughput than MAZero.

Critical strengths
  1. Important systems bottleneck. Search-based MBMARL is often sample-efficient but impractically slow due to CPU-side planning and CPU–GPU communication; addressing this under realistic GPU budgets is valuable.
  2. Useful co-design and ablations. PGFS removes serial tree traversal, and comparisons against GPU-resident MCTS, Gumbel MCTS, SPO, and component profiling help separate algorithmic from systems effects.
Critical weaknesses
  1. Insufficient reproducibility for a systems-speedup claim. No author code or precise software/kernel/configuration release is provided. JAX/XLA/CUDA versions, compilation setup, baseline commits, worker counts, and tuning effort are not reported, so reviewers cannot assess how much of the 16.3× speedup comes from PGFS versus implementation or baseline engineering.
  2. Narrow wall-clock comparison. Main wall-clock results compare mainly against MAZero and MAMBA, while fast vectorized model-free methods such as MAPPO/IPPO appear mainly in sample-efficiency plots. Time-to-threshold comparisons against tuned vectorized model-free baselines are needed. FPS is also not defined precisely, including whether JIT compilation, initialization, reanalysis, and optimization are counted.
  3. Limited statistical reporting for the headline result. Table 2 gives only aggregate FPS despite five-seed experiments; it omits per-task throughput, uncertainty, speedup distributions, and time-to-threshold summaries. The evidence therefore does not establish that the 16.3× speedup is robust across tasks and seeds.
Questions for authors
  1. Will you release code, baseline configurations/commits, software versions, and timing scripts?
  2. Define FPS exactly, including whether compilation, initialization, reanalysis, and optimization are counted.
  3. Provide per-task throughput and speedups with uncertainty over five seeds, plus time-to-threshold results.
  4. How does MATCHA compare in wall-clock time to tuned vectorized MAPPO/IPPO at matched target performance?
  5. How do frontier size, memory use, and search latency scale with simulation budget, action branching, and observation dimension?
6 comments

Q1: Will you release code, baseline configurations/commits, software versions, and timing scripts?

A:

  1. For the code releasing, yes, we will release the whole codebase, including the timing scripts after acceptance.
  2. For the software versions, we use CUDA runtime 12.9 (nvidia-cuda-runtime-cu12==12.9.79), cuDNN 9.24.0.43, and NVIDIA driver 570.133.07. We further release our requirements.txt here.
numpy==2.5.1
cython==3.0.11
wandb==0.28.1
matplotlib==3.11.1
imageio==2.37.2
graphviz==0.20.3
tensorboard==2.19.0
tensorboard-plugin-profile==2.19.6
tensorboardX==2.6.4
seaborn==0.13.2
requests[socks]==2.32.3
jax[cuda12]==0.11.0 ; sys_platform == "linux"
jax==0.11.0 ; sys_platform == "darwin"
jaxlib==0.11.0
flax==0.12.8
chex==0.1.90
ipywidgets==8.1.5
ipykernel==6.29.5
orbax-checkpoint==0.11.31
ale-py==0.11.2
opencv-python==4.11.0.86
hydra-core==1.3.2
  1. For the baseline configurations/commits. We used the official implementations of https://github.com/bold-lab-ai/JaxMARL (v 0.1.0, commit 66f41e5), https://github.com/jbr-ai-labs/mamba (commit 2c97258), and https://github.com/liuqh16/mazero (commit b1c5084).
  • 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=1 and NUM_EPOCHS=2 for VDN, QMIX, and IQL to improve their sample efficiency.
  • MAMBA. We started from its default SMAC/MPE configurations and conducted additional sweeps. We set n_workers=4 across 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_times and num_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 fine-tuned actor parallelism to improve wall-clock efficiency (15 workers for 1 GPU and 27 workers for 2 GPUs).

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.

Q2: Define FPS exactly, including whether compilation, initialization, reanalysis, and optimization are counted.

A: FPS is the total transitionstotal wall clock time\frac{\text{total transitions}}{\text{total wall clock time}}. This is an end-to-end measure, so all components including compilation, initialization, reanalysis, and optimization are counted.

Q3: (1) Provide per-task throughput and speedups with uncertainty over five seeds, (2) plus time-to-threshold results. (3) How does MATCHA compare in wall-clock time to tuned vectorized MAPPO/IPPO at matched target performance?

A: To address these questions, we have added Appendix A.4, with the new content highlighted in red.

(1) We add Table 5 for a per-task breakdown of the speedups reported in Table 2, and add Table 6 for a per-task throughput for all algorithms with 95% confidence intervals across five random seeds.

(2) We also add per-task time-to-threshold and samples-to-threshold results for all algorithms (Tables 3 and 4).

(3) All model-free baselines use tuned, fully vectorized implementations. As shown in Tables 3 and 4, at matched target performance, model-free baselines often require tens of times as many samples as MATCHA, whereas MATCHA often requires tens of times as much wall-clock time. Many model-free baseline–task pairs do not reach the threshold within the recorded budget. These results illustrate the trade-off between sample efficiency and wall-clock efficiency in model-based and model-free methods. MATCHA substantially improves the wall-clock efficiency of model-based methods while retaining their sample efficiency, thereby narrowing this gap.

Q4: How do frontier size, memory use, and search latency scale with simulation budget, action branching, and observation dimension?

A: Let the simulation budget be NN, action branching factor be KK, and observation dimension be DD. The frontier size is O(NK)O(NK), memory use is O(NK(D+m))O(NK(D+m)), where mm is the number of the agents. The search latency is O(CN+Nlog⁡N+Nlog⁡K)O(CN+N\log N+N\log K), where CC is the time complexity for one model forward pass, which is analyzed in Appendix B.3.

Table 3 (smax X-to-threshold)

(a) Samples to 80% win (million environment steps)

TaskMATCHAMAZeroMAMBAIPPOMAPPOIQLQMIXVDN
3s_vs_5z0.11>1.000.198.723.56>2.00>2.001.91
2s3z0.080.330.152.610.95>2.00>2.001.64
6h_vs_8z0.050.110.181.911.151.901.061.20
3s5z0.300.53>1.00>10.002.76>2.00>2.00>2.00
8m0.130.35>1.00>10.004.76>2.00>2.00>2.00
5m_vs_6m0.75>1.50>1.50>10.00>10.00>2.00>2.00>2.00
3s5z_vs_3s6z1.24>1.50>1.50>10.00>10.00>2.00>2.00>2.00
10m_vs_11m0.46>1.50>1.50>10.00>10.00>2.00>2.00>2.00
smacv2_5_units0.611.15>1.50>10.00>10.00>2.00>2.00>2.00
smacv2_10_units0.66>1.50>1.50>10.00>10.00>2.00>2.00>2.00

(b) Time to 80% win (minutes)

TaskMATCHAMAZeroMAMBAIPPOMAPPOIQLQMIXVDN
3s_vs_5z16.73>4168.20617.702.531.54>19.75>18.3918.32
2s3z18.231410.90461.600.710.43>20.68>22.4016.73
6h_vs_8z12.75525.83783.180.680.6531.2917.5819.38
3s5z93.672420.87>2943.00>3.551.51>35.08>35.32>38.44
8m39.181745.86>5907.60>3.862.66>35.11>35.35>34.54
5m_vs_6m168.24>6957.00>9768.60>3.66>5.39>30.14>31.86>29.84
3s5z_vs_3s6z384.58>7143.60>5527.80>3.74>5.44>37.22>37.32>35.14
10m_vs_11m196.69>8532.60>9355.80>4.06>6.07>40.39>41.57>38.49
smacv2_5_units135.504913.63>5648.40>3.24>4.94>32.15>32.52>32.44
smacv2_10_units261.48>7945.20>7411.20>3.88>6.47>41.66>40.63>43.85

Table 4 (overcooked, X-to-threshold)

(a) Samples to threshold (million environment steps)

TaskThresholdMATCHAMAZeroMAMBAIPPOMAPPOIQLQMIXVDN
cramped_room190.600.19>1.000.920.740.650.990.491.19
coord_ring244.330.44>1.00>1.002.191.80>5.00>5.00>5.00
forced_coord191.830.28>1.00>1.00>5.004.81>5.00>5.001.56
counter_circuit15.950.91>1.00>1.001.190.881.693.341.81
asymm_advantages399.130.55>1.00>1.001.390.902.59>5.00>5.00

(b) Time to threshold (minutes)

TaskThresholdMATCHAMAZeroMAMBAIPPOMAPPOIQLQMIXVDN
cramped_room190.6027.84>2337.00412.490.100.411.392.551.81
coord_ring244.3369.23>2347.20>446.400.311.25>7.22>45.34>8.06
forced_coord191.8344.31>2343.60>449.40>0.703.32>7.30>45.742.53
counter_circuit15.95157.78>2340.60>440.400.180.712.5835.473.04
asymm_advantages399.1395.55>2353.80>444.000.220.794.13>59.57>8.51

Table 5 (speedup breakdown)

EnvTaskMATCHA FPS (mean ± 95% CI)MAZero FPS (mean ± 95% CI)MATCHA speedup vs. MAZero
SMAX3s_vs_5z106.40 ± 0.744.00 ± 0.1526.6×
SMAX2s3z74.90 ± 0.033.89 ± 0.0519.3×
SMAX6h_vs_8z65.90 ± 0.893.58 ± 0.0618.4×
SMAX3s5z53.70 ± 0.283.63 ± 0.1914.8×
SMAX8m54.00 ± 0.093.31 ± 0.3516.3×
SMAX5m_vs_6m73.70 ± 0.683.59 ± 0.0420.5×
SMAX3s5z_vs_3s6z53.90 ± 0.223.50 ± 0.3215.4×
SMAX10m_vs_11m39.00 ± 0.642.93 ± 0.0913.3×
SMAXsmacv2_5_units75.10 ± 0.033.89 ± 0.1919.3×
SMAXsmacv2_10_units41.80 ± 0.423.15 ± 0.0413.3×
Overcookedcramped_room112.30 ± 0.207.13 ± 0.2115.8×
Overcookedcoord_ring106.60 ± 0.517.10 ± 0.2615.0×
Overcookedforced_coord106.40 ± 0.657.11 ± 0.0115.0×
Overcookedcounter_circuit96.10 ± 0.037.12 ± 0.3213.5×
Overcookedasymm_advantages95.70 ± 0.227.08 ± 0.1913.5×
Overall15 tasks77.034.7316.3×

Table 6 (FPS)

EnvTaskMATCHA FPS (mean ± 95% CI)MAZero FPS (mean ± 95% CI)MAMBA FPS (mean ± 95% CI)IPPO FPS (mean ± 95% CI)MAPPO FPS (mean ± 95% CI)IQL FPS (mean ± 95% CI)QMIX FPS (mean ± 95% CI)VDN FPS (mean ± 95% CI)
smax3s_vs_5z106.40 ± 0.744.00 ± 0.155.15 ± 0.3557384.43 ± 1153.4638568.00 ± 2200.651686.71 ± 8.901811.91 ± 39.311736.31 ± 233.78
smax2s3z74.90 ± 0.033.89 ± 0.055.26 ± 0.3461393.75 ± 692.5136869.53 ± 1072.591611.17 ± 39.591487.19 ± 18.811631.58 ± 66.99
smax6h_vs_8z65.90 ± 0.893.58 ± 0.063.73 ± 0.3546930.07 ± 1084.5929661.17 ± 570.371011.40 ± 8.301009.86 ± 0.871028.38 ± 115.54
smax3s5z53.70 ± 0.283.63 ± 0.195.66 ± 1.1746800.90 ± 43.7630426.70 ± 1105.97949.66 ± 2.46943.42 ± 28.91866.81 ± 103.06
smax8m54.00 ± 0.093.31 ± 0.352.82 ± 0.1043042.18 ± 877.7829886.21 ± 511.95948.93 ± 0.75942.62 ± 16.36964.53 ± 37.05
smax5m_vs_6m73.70 ± 0.683.59 ± 0.042.56 ± 0.2545354.91 ± 9.2530828.07 ± 2149.721105.54 ± 19.451045.75 ± 7.921116.55 ± 106.91
smax3s5z_vs_3s6z53.90 ± 0.223.50 ± 0.324.52 ± 1.5344397.40 ± 1333.5930552.47 ± 409.24895.08 ± 9.09892.76 ± 21.41948.22 ± 134.25
smax10m_vs_11m39.00 ± 0.642.93 ± 0.092.67 ± 0.2740943.20 ± 775.6727385.64 ± 1999.48824.91 ± 2.38801.47 ± 2.55865.75 ± 51.20
smaxsmacv2_5_units75.10 ± 0.033.89 ± 0.194.43 ± 1.7951210.96 ± 608.3133616.03 ± 2818.171036.27 ± 16.591024.48 ± 25.681026.97 ± 145.64
smaxsmacv2_10_units41.80 ± 0.423.15 ± 0.043.37 ± 0.2242769.43 ± 774.8725700.14 ± 1907.88799.75 ± 14.77820.03 ± 23.36759.86 ± 73.70
overcookedcramped_room112.30 ± 0.207.13 ± 0.2137.33 ± 1.10119804.84 ± 110.9126749.50 ± 371.1511822.28 ± 96.303193.73 ± 1485.0610919.89 ± 131.37
overcookedcoord_ring106.60 ± 0.517.10 ± 0.2637.30 ± 1.30117920.01 ± 463.8124093.77 ± 194.5411522.79 ± 226.411834.91 ± 153.4410317.08 ± 523.18
overcookedforced_coord106.40 ± 0.657.11 ± 0.0137.04 ± 0.64117893.99 ± 434.1824103.06 ± 797.3311388.43 ± 401.381818.69 ± 121.0610308.50 ± 513.41
overcookedcounter_circuit96.10 ± 0.037.12 ± 0.3237.78 ± 1.10108628.09 ± 383.1220678.22 ± 168.2310900.34 ± 61.981569.84 ± 6.889922.49 ± 99.06
overcookedasymm_advantages95.70 ± 0.227.08 ± 0.1937.48 ± 0.64105053.13 ± 573.6519042.91 ± 539.2310450.63 ± 74.541396.58 ± 56.079765.51 ± 220.75
Reviewer_QLNuOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces MATCHA, a model-based RL method that substantially improves wall-clock efficiency over other model-based baselines. There are two main parts to the introduced method. The first is an end-to-end GPU accelerated pipeline that does not rely on the CPU for model-based planning. The second part is the Path Guided Frontier Search (PGFS) algorithm, that is used as an alternative to MCTS. Rather than starting each trajectory at the root as in MCTS, PGFS instead maintains a set of all unexpanded leaf nodes, and expands the the most promising node in this set. This allows for faster planning, and better utilisation of parallelised GPU acceleration.

Critical strengths

The clear strength of this work can be seen in the empirical results presented. Figures 3 and 4 clearly show MATCHA consistently outperforming the included benchmarks in wall-clock efficiency. Additionally, Figures 5 and 6 demonstrate MATCHA also outperforming baselines when comparing sample efficiency. These results are clearly demonstrated in two diverse environments in SMAX and Overcooked (as well as additional MPE results in the appendix), with a number of settings explored in each of these environments.

The PGFS algorithm represents a novel alternative to MCTS that facilitates further wall-clock efficiency, with direct comparisons to MCTS illustrated in Figure 7. This ablation shows clear wall-clock efficiency improvements, even when all other conditions are held the same, indicating the benefit of the PGFS method.

Overall, I think the strong empirical results support for the method indicate this paper represents a compelling contribution.

Critical weaknesses

I think the primary weakness of this work is in the framing of the contributions. The way that I have understood the paper is that there are two main contributions to this work. The first is GPU acceleration, and the second is PGFS. Whilst these both serve to speed up training, I think these should be treated as somewhat distinct contributions and I don't think the paper does a clear job of isolating these contributions. The core of the empirical results shown in this paper (e.g. Figures 3-6) are directly comparing MATCHA with the CPU model-based methods. This presentation does highlight the combined strength of the two contributions, but it doesn't illustrate the respective effects of each contribution.

This is addressed in the Figure 7 ablation, which is helpful in isolating the effect of PGFS compared to MCTS, but the experimentation is limited, as it is confined to only two SMAX experiments. To properly analyse the effectiveness of PGFS, these results need to be shown in the full environment testing set. I think its a very important determination to be made about whether the benefit of PGFS is just in wall clock time (which is clearly still a valuable contribution), or if it also outperforms MCTS consistently when comparing total transitions. Similarly, it would be beneficial to see how identical algorithms perform where one is partially relying on the CPU and the other is fully GPU accelerated. When the paper has two relatively distinct contributions, it needs to be clear exactly how each one individually affects the results.

There are two more minor weaknesses that I also want to raise.

The first is the lack of model-free baselines in the wall-clock efficiency comparisons. Obviously, the advantage of model-based approaches is generally seen in sample efficiency, so if MATCHA was outperformed in wall-clock efficiency by some model-free baselines, it certainly does not invalidate the contribution. However, I think it weakens the paper only showing these model-free baselines in the sample efficiency context.

The other weakness I wanted to flag is more of a limitation in how PGFS would interact with a stochastic environment. This is not an issue with how PGFS is used in this work, as my understanding is the learned transition model is deterministic. However, comparing PGFS more generally to MCTS, PGFS appears to assume that all frontier nodes are guaranteed to be reachable, which may not be the case in a stochastic environment. PGFS effectively only tests each state-action transition once, so there is seemingly no capacity to handle environments without deterministic transitions. I don't think this is a major weakness of the work, as for this application, this functionality is not required, but I do think it is a limitation that should be flagged in relation to how PGFS could be applied as a more general alternative to MCTS. I would be interested to hear if the the authors have any insight as to whether PGFS could be applied in a stochastic setting.

Whilst I have raised a number of weaknesses here, I do think the current results clearly illustrate the benefits of MATCHA over existing baselines. Additional results, specifically around more thoroughly isolating the effect of each individual contribution, would strengthen the work.

Questions for authors
  1. Why do the plots in Figure 5 have somewhat inconsistent total transition numbers? I understand that the model-based methods may have longer wall-clock times, so may be able to be run for more total transitions, but the number of total transitions does not remain consistent with the model-based methods. I don't think this changes the conclusion of the results, but it appears a strange design choice. There are some other somewhat strange plots, like the Figure 7 2s3z total transitions plot has MATCHA with Gumbel MCTS not quite finishing all 2×1052 \times 10^5 transitions.
  2. Could you provide wall-clock time comparisons between the model-based and model-free methods?
  3. Can the authors provide any insight on how PGFS could be applied to stochastic environments?
4 comments

W1: The contribution of Device-Centric pipeline and PGFS should be isolated better. (1) It would be beneficial to see how identical algorithms perform where one is partially relying on the CPU and the other is fully GPU accelerated. (2) Fig. 7 (search ablation) should be extended to the full test set.

A: (1) We agree that comparing CPU-centric and GPU-centric implementations of the same algorithm can help disentangle the contributions of our device-centric framework and the PGFS algorithm. Indeed, Table 1 was designed for this purpose. MAZero serves as the CPU-centric baseline, while MATCHA w/ GPU MCTS can be viewed as an approximate GPU-centric counterpart to MAZero. Comparing these two configurations reveals the throughput gains attributable to the framework. Table 1 also includes MATCHA w/ GPU Gumbel MCTS and MATCHA; comparing these configurations with MATCHA w/ GPU MCTS reveals how different search algorithms affect throughput.

The results show that replacing the CPU-centric framework with a GPU-centric framework improves throughput across all three stages: Data Collection, Reanalysis, and Optimization. Further replacing the search algorithm with PGFS has little effect on Optimization throughput but substantially improves Data Collection and Reanalysis, both of which require search. Thus, moving from MAZero to MATCHA, the GPU-centric framework and PGFS progressively shift the throughput bottleneck from the search-dependent Data Collection and Reanalysis stages to the search-independent Optimization stage.

(2) We agree that extending Fig. 7 to the full test set would strengthen the work. Due to limited time, we have currently added two addition SMAX maps (5m_vs_6m and 8m) for ablation in Appendix A.3. PGFS outperforms Gumbel MCTS in sample efficiency on 5m_vs_6m and performs comparably on 8m, surpassing MCTS on both tasks while achieving substantially higher wall-clock efficiency than both baselines. This new result is consistent with existing results in our original submission.

We will add this full ablation once the rest experiments are complete. Evaluating all search algorithms across all tasks with multiple random seeds requires substantial time, particularly because the baselines are slower. To ensure fair runtime comparisons, these experiments must also run sequentially on the same device configuration, limiting parallelism. This makes it unlikely that these additional experiments can be completed within a short timeframe. But we will try our best to do it.

Q1: Why do the plots in Figure 5 have somewhat inconsistent total transition numbers?

A: The different total transition counts reflect the substantial computational cost of the model-based baselines, whose single-seed run typically takes more than a week. We therefore allocated a budget of 1M transitions to each of the five relatively easier maps in the first row and 1.5M transitions to the harder maps in the second row. We also stopped runs early once performance had converged, which explains why some curves end before reaching these budgets.

Q2: In Fig 7 2s3z, MATCHA with Gumbel MCTS doesn’t finish 2×1052\times 10^5 transitions.

A: Thank you for the careful observation. This was a plotting error: the final few logging points from one Gumbel MCTS run were not successfully uploaded to Weights & Biases (wandb). As a result, averaging across runs truncated the curve at the endpoint of the shortest recorded run. We have recovered the missing data and updated Fig. 7 to show the complete curve up to 2×1052 \times 10^5 transitions.

Q3: Model-free baseline wall clock efficiency comparison.

A: To address this question, we have added per-task time-to-threshold and samples-to-threshold results for all algorithms (Tables 3 and 4 in Appendix A.4). All model-free baselines use tuned, fully vectorized GPU-centric implementations. As shown in Tables 3 and 4, at matched target performance, model-free baselines often require tens of times more samples than MATCHA, whereas MATCHA often requires tens of times as much wall-clock time. Many model-free baseline–task pairs do not reach the threshold within the recorded budget. These results illustrate the trade-off between sample efficiency and wall-clock efficiency in model-based and model-free methods. MATCHA substantially improves the wall-clock efficiency of existing model-based MARL methods while retaining their sample efficiency, thereby narrowing this gap.

Q4: Can the authors provide any insight on how PGFS could be applied to stochastic environments?

A: Thank you for this question. In stochastic environments, PGFS may be interpreted as performing approximate open-loop planning based on learned reward and value predictions. Like MuZero and MAZero, MATCHA uses a deterministic latent model. Its predictions are learned from sampled trajectories and may approximate averages over stochastic outcomes. Ideally, its path score would approximate the expected bootstrapped return of executing a fixed action sequence: RVθ(s0,a0:k−1)≈E[∑i=0k−1γiri+γkV(sk) ∣ s0,a0:k−1]RV_\theta(s_0,a_{0:k-1}) \approx \mathbb{E}\Big[\textstyle\sum_{i=0}^{k-1}\gamma^i r_i+\gamma^k V(s_k)\,\Big|\,s_0,a_{0:k-1}\Big], where the expectation is over environmental outcomes generated by executing the specified action sequence from s0s_0. PGFS uses this prediction to score paths (Eq. 1), without explicitly representing chance outcomes. Replanning after each real environment step allows execution to adapt to new observations, while each searched action sequence remains open-loop.

This interpretation has two limitations. First, open-loop planning ignores the ability to react to new observations within the search horizon. Second, the expectation is learned from closed-loop data, so it can be biased when later actions correlate with random outcomes. Both effects are small when the search is shallow, which is also why frame skipping (DQN on Atari) and action chunking (Diffusion Policy) work well in practice.

Empirically, the SMACv2-like scenarios in SMAX randomize team compositions and randomize more diverse start positions, and MATCHA performs well on them (Figures 3 and 5). This indicates robustness to episode-level randomness, though it is not a test of stochastic transitions.

Response to Rebuttal

Thank you for your response to my rebuttal, I appreciate the time taken to answer my questions, and to produce additional results. With regard to the specific issues you have addressed.

W1

Whilst I agree that Table 1 does serve to address the GPU vs CPU comparisons, the core comparisons that are actually interesting to me are GPU to GPU comparisons of different implementations. Based on the plots shown in Figure 7, as well as the additional results in the Appendix, it seems very clear that MATCHA with GPU Gumbel MCTS is by far the most comparable baseline for MATCHA with PGFS. This really should have been included as a baseline in Figures 3, 4, 5, and 6 for all environments. I understand it may be infeasible to produce this in the limited rebuttal time, but based purely on the results you have presented so far, it seems that this was the strongest baseline, so I am unclear why this was not included to begin with.

There are clear benefits of MATCHA with PGFS over MATCHA with GPU Gumbel MCTS in wall clock time shown in the current results, but it definitely hampers the soundness of the paper that this baseline was not more thoroughly explored.

I do however think that making sample efficiency claims about MATCHA is not hugely supported, again based on Figure 7 and the new plots in the Appendix, it is really only in 5m_vs_6m where there is a noticeable improvement in sample efficiency against MATCHA with GPU Gumbel MCTS. Again, if this baseline had been more thoroughly tested, stronger claims could perhaps be made, but currently there is insufficient evidence.

Q1

Thank you for clarifying the reasoning behind the total transition counts. It is understandable to terminate runs early if they have converged, and generally are slow to run. However, in the three runs where MAZero has been terminated early in Figure 5, it does not appear to have converged. I find this especially confusing given that MATCHA does outperform MAZero in these results, so I am unclear why the authors are suggesting the baseline has converged when it is not clear that it has.

Q3

I understand that the model-free baselines will generally perform better under wall clock comparisons - the benefit of model-based methods is in sample efficiency. However, I don't understand why the authors have not just included these model-free baselines in Figures 3 and 4, or at least in equivalent plots in the appendix. Whilst the tables obviously do communicate this information as well, it would be so much clearer in plot form.

Q4

I apologise if my initial question was unclear, I had outlined this more thoroughly in the weaknesses section, but did not explicitly reference this in the question. My question is not about how MATCHA can be applied to stochastic environments - it is clear that, if you learn a deterministic model of the environment, this is not an issue. My question about how PGFS could be used more generally, as MCTS is. MCTS is often applied in settings where the model of the world is a fixed, hand-designed simulator, and these simulators may include stochastic transitions. MCTS, by sampling from the root, can handle that, but as far as I can tell, PGFS assumes all frontier nodes are guaranteed to be reachable, which is a false assumption in a stochastic environment. My question was, can the authors propose a modification to PGFS that would allow it to work more generally in these settings - or correct my understanding of the method if I have misinterpreted it. I do not think this is a critical error with PGFS, as in the context of MATCHA, this is not required, but I was interested in hearing whether the authors had any insight here.

Thank you for the detailed follow-up. We address each point below.

W1 (Gumbel MCTS as a baseline). We agree that MATCHA w/ GPU Gumbel MCTS is an informative comparison for PGFS, and that evaluating it on all tasks would strengthen the paper. It appeared only as an ablation for two reasons:

  1. It is not a prior method. To our knowledge, no open-source MBMARL method uses Gumbel MCTS. This variant exists only within our device-centric framework, so we treated it as an ablation of our contribution and compared Figures 3–6 against published methods.
  2. The ablation maps were fixed in advance. The two maps for the original search ablation were selected before running that ablation, rather than chosen based on its results.

We are now extending the comparison. Runs on 5m_vs_6m, 8m, 6h_vs_8z, 3s5z are complete. Across all six tasks evaluated so far, PGFS achieves substantially better wall-clock efficiency than both GPU search baselines, while maintaining sample efficiency comparable to GPU Gumbel MCTS and exceeding that of standard GPU MCTS. The final version will report this variant on the full task set.

W1 (sample-efficiency claims). We agree with your assessment. Against GPU Gumbel MCTS, PGFS achieves broadly comparable sample efficiency on most evaluated tasks, with a clearer advantage on 5m_vs_6m. This supports parity, not superiority. We have revised Sections 5.3 and 5.4 accordingly.

Our sample-efficiency claims are relative to prior MBMARL methods (Figures 5–6). Relative to Gumbel MCTS, the claim is speed at matched sample efficiency.

Q1 (early termination). Thank you for catching this. It is a plotting error of the similar kind as in Q2. On the three tasks concerned (2s3z, 6h_vs_8z, 8m), every individual MAZero run maintained a win rate above 95% for at least 50k steps before termination; we therefore considered these runs converged. Because convergence was assessed separately for each run, the runs ended at different steps. However, our plotting script truncated all runs to the shortest one before averaging, omitting the later observations from longer runs. We have now revised Figure 5 to retain these observations. To average runs of different lengths, we carry forward each stopped run’s last recorded win rate to the common plotting cutoff. This follows the official implementation in DreamerV2 [1].

[1] Hafner, Danijar and Lillicrap, Timothy and Norouzi, Mohammad and Ba, Jimmy. Mastering Atari with Discrete World Models, ICLR 2021, https://github.com/danijar/dreamerv2/blob/6124db46d6be27d209060e2a11677661a218294d/dreamerv2/common/plot.py#L431-L441

Q3 (model-free baselines in plots). We agree that plots communicate this more clearly than tables. We have added wall-clock learning curves that include all model-free baselines for SMAX and Overcooked (Fig 20 and 21, Appendix A.14). They use a logarithmic time axis. The time-to-threshold tables remain in Appendix A.4 as a quantitative complement.

The model-free baselines were originally run with fixed environment-step budgets solely for sample-efficiency comparisons. We are currently extending these runs to better compare wall-clock efficiency and will update these figures once the longer runs are complete.

Q4 (stochastic simulators). Thank you for clarifying, and apologies for misreading the question. We believe PGFS can be extended for stochastic models. One possible approach is to follow Stochastic MuZero and represent stochasticity using chance nodes. The tree would contain two types of nodes: decision nodes and chance nodes. At a decision node ss, selecting an action aa leads to a chance node cc. At the chance node, a stochastic transition leads to a subsequent decision node s′s'.

At a decision node ss, the probability of selecting action aa is proportional to exp⁡(log⁡p(a∣s)+αQ(s,a))\exp(\log p(a| s) + \alpha Q(s,a)). At a chance node, the probability of selecting chance outcome bb is 1/m1/m, where mm is the branching factor of the chance node. For each leaf in the frontier, we define its selection probability as the product of the probabilities associated with all edges along its path from the root. This probability can be readily computed from the parent's probability, allowing us to continue selecting a frontier node for expansion with a single sampling operation.

The main characteristic of this approach is that we do not update the statistics of intermediate nodes through backpropagation during search, as standard MCTS does, and thereby adjust their probabilities of selecting children. However, after the search is complete and the simulation budget has been exhausted, we can perform a single bottom-up tree dynamic programming pass to re-estimate the value of each node. This tree traversal is performed only once, with an O(N)O(N) total cost and an amortized O(1)O(1) cost per simulation, so it does not change the overall asymptotic complexity of PGFS.

Comments on the paper

1 comment

Thanks the authors for the thorough response.

it addresses most of my concerns; my assessment has been updated.

Minor point: overcooked metrics explanation: MATCHA succeeds where both model-based baselines fail, and no same-framework search comparison there. PGFS and GPU Gumbel MCTS perform similarly on SMAX, so the gap may come from other parts of the system rather than the search alone.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.