MCTS Loses to Random Restarts by 2.88% in DAG Scheduling at Equal Budget

Researchers on arXiv put Monte Carlo Tree Search and a plain list scheduler with random restarts under identical conditions: 2048 constructed and evaluated schedules per task. The search tree lost. On 72 of 96 held-out instances where the baseline solution had room for improvement, MCTS was 2.88% worse on makespan (95% CI from −3.62% to −2.15%). The work does not prove that MCTS is useless. It does show that a comparison without a simple competitor on the same budget says little.

A protocol that could have refuted MCTS

The authors start from an observation: papers on MCTS for DAG workflow scheduling rarely give the simple method the same amount of compute. Here, every participant gets the same number of candidate schedules. The primary participant is the MCTS method, declared in advance as the main one. The control is a list scheduler with randomized restarts and no tree. A third participant, MCTS with textbook UCT, was later added on the same domain.

The analysis plan was fixed before data collection. An independent checker verified all 768 schedules from the confirmatory stage: all are valid, and completion times are computed correctly.

• Main budget: 2048 evaluated schedules.
• Gap between MCTS and restarts: −2.88%, CI [−3.62%; −2.15%].
• Self-improvement on a separate exploration pool: restarts +1.85%, MCTS +0.24%.
• First MCTS results: 700 of 720 matched the warm start it was given.
• MCTS with textbook UCT: −0.26%, CI [−0.71%; +0.23%].
• Scale: 8, 16 and 32 tasks, 2–8 processors, budgets up to 2048.

Why the tree did not help

The first hypothesis was that MCTS simply ran out of budget. The data do not support it: on the exploration pool, restarts improved on themselves by 1.85%, while MCTS managed only 0.24%. Moreover, in 700 of 720 cases MCTS's first result was just the starting solution it had been handed. In other words, the tree barely moved away from its starting point.

The authors attribute this to the selection rule. It deterministically sticks to the first expanded child, so trials within a branch are strongly correlated. Restarts pick a fresh trajectory each time and draw their gains from the tails of the distribution. The authors call the link to makespan an inference, not a proven causal mechanism. An experiment replacing the rule with classic UCT supports the explanation: the gap shrinks to 0.26%, and the confidence interval now includes zero. But the sign stays negative, so MCTS does not beat restarts even in the corrected version.

Separately, the authors built a structural map. On sparse, irregular workflows, restarts win. On regular layered ones, no differences are visible. On dense graphs there is almost nothing to improve, because the baseline solution is already close to the limit.

What to check before building a tree

For engineers who schedule tasks in data pipelines, model training or agent chains, the takeaway is down to earth. Before adopting MCTS, run a randomized list scheduler on the same number of evaluations. It can be implemented in an evening and gives an honest baseline. If the tree does not beat it, the added complexity is not justified.

The second check is the share of solutions where the search moved away from the warm start. If almost all results match the start, the algorithm is barely exploring. The third is the branch selection rule itself: it determines whether the tree will be diverse.

The authors state the limitations of the work themselves. The experiment is synthetic, the graphs are small (up to 32 tasks), and the budget does not exceed 2048. There is no conclusion about larger budgets or real workflows. But as a model of discipline, the work is useful: preregistration, an equal budget and independent validation of schedule validity. For agent systems, where schedulers are often introduced because of a trendy algorithm name, this kind of control is needed no less than new methods.