Controlled study finds Monte Carlo Tree Search underperforms simpler scheduler for DAG workflows under equal budget

A new arXiv preprint reports a preregistered, controlled computational study comparing Monte Carlo Tree Search (MCTS) to a randomized-restart list scheduler for scheduling directed-acyclic-graph (DAG) workflows under identical search budgets. The study was designed to test whether MCTS’s proposed advantages hold when compared directly to a simpler method given the same computational effort.

All methods were evaluated under a locked analysis plan with an independent checker confirming the validity of 768 confirmation-stage schedules and their finish times. At the main budget of 2048 evaluated schedules, MCTS was 2.88% worse than the restarts (95% CI [-3.62%, -2.15%]) on the 72 of 96 held-out instances with positive baseline-relative headroom. The deficit persisted even when accounting for potential budget starvation: on a separate exploration pool, restarts self-improved by 1.85% while MCTS gained only 0.24%.

The authors attribute much of the deficit to the studied selection rule, which deterministically locks onto the first-expanded child, keeping trials correlated. Swapping the selection rule for textbook UCT reduced the deficit to -0.26% (95% CI [-0.71%, +0.23%]) without reversing its sign, suggesting that the choice of selection policy is a key driver of MCTS’s underperformance.

A structural analysis mapped where the tree-based approach stops paying off: restarts outperformed MCTS on sparse, irregular workflows, while no detectable difference was observed on regular layered workflows, and dense workflows left little room for improvement. The study’s scope was limited to a controlled synthetic domain with task sizes N in {8, 16, 32}, 2–8 processors, and budgets up to 2048, and the authors explicitly state they make no claims about larger budgets or real-world systems.

The work is presented as a preregistered negative result with open evaluation artifacts archived on Zenodo, including companion repositories for reproducibility.