The Pulse
DAG Study Finds MCTS Trails Randomized Restarts by 2.88%
A controlled arXiv study found one Monte Carlo Tree Search scheduler produced schedules 2.88% worse than randomized-restart list scheduling at an equal evaluation budget. The result applies to a small synthetic benchmark, and a textbook UCT
AI.info Team · Written with AI ·
At an equal budget of 2,048 evaluated schedules, one Monte Carlo Tree Search (MCTS) scheduler finished 2.88% behind a simpler randomized-restart method in a controlled study posted to arXiv on October 8. The comparison covered 72 held-out synthetic workflow instances where the researchers found room for either method to improve; the reported 95% confidence interval ran from 3.62% to 2.15% worse for MCTS. The result challenges claims about this particular scheduler, not MCTS as a whole.
One budget, two search strategies
Yuyu Zhang compared an MCTS scheduler with a randomized-restart list scheduler that uses no search tree. Each method received the same number of candidate schedules to build and evaluate. The restart control repeatedly chose a task at random from those ready to run, then placed it on the processor with the earliest finish time.
The paper says the analysis plan was fixed before data collection and an independent checker verified all 768 schedules in the confirmation-stage runs. The researchers compared results against a per-instance portfolio of four scheduling heuristics: HEFT, CPOP, PEFT and OCT. They excluded 24 of the 96 held-out instances from the main comparison because those instances were already at the study’s lower bound, leaving no measured improvement headroom.
“We do not claim that MCTS cannot help scheduling, that this implementation stands for all MCTS schedulers, or that these synthetic results carry over to production workflows.”
Yuyu Zhang, “Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study”
The scheduler’s early lead came from its warm start
The MCTS arm began with a CPOP schedule; the restart control did not. At the first evaluated schedule, that gave MCTS an advantage, but the paper reports that 700 of 720 first results in a separate exploration pool were simply the supplied warm start. As the budget grew, the control improved more: on that exploration pool, restarts gained 1.85% over their starting point, compared with 0.24% for MCTS.
The authors also ran a supplementary comparison that gave the control the same CPOP warm start. The MCTS deficit remained, at 2.93% in that comparison. But the paper cautions that the experiment compares two complete procedures; it does not isolate the tree itself, since the methods also differ in how they search and handle processor placement.
Results depend on the DAG’s shape
Randomized restarts won on sparse, irregular workflow structures, including fork-join and sparse-wide instances. The study detected no difference on regular layered workflows, while dense instances were outside the main comparison because the starting heuristic already met the lower bound. The authors describe this as a pattern across their tested families, not proof that any single structural feature causes the result.
The study’s MCTS selection rule also behaved differently from a broadly exploring tree search. The authors measured it concentrating visits on the first child expanded; they say the link between that behavior and the makespan deficit remains an inference. In a follow-up using textbook UCT, the measured difference narrowed to 0.26% worse for MCTS, but the confidence interval crossed zero, so the study did not establish either method as the winner in that comparison.
A result bounded by synthetic tests
The benchmark used synthetic DAGs with 8, 16 or 32 tasks and 2 to 8 processors, with search budgets capped at 2,048 schedules. The paper makes no claim about production workflows or larger budgets, and its main experiment does not settle whether other MCTS designs would perform better. Its central finding is narrower: on this benchmark, under the tested equal-schedule budget, randomized restarts beat the studied MCTS configuration on instances with room to improve.