Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study

查看原文 / View Original 编辑 / Edit

Computer Science > Artificial Intelligence arXiv:2610.12542 (cs) [Submitted on 8 Oct 2026] Title: Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study Authors: Yuyu Zhang.

计算机科学 > 人工智能 arXiv:2610.12542 (cs) [提交于 2026 年 10 月 8 日] 标题：有向无环图工作流的等预算蒙特卡洛树搜索与随机重启列表调度对比：一项受控的等预算计算研究作者：张宇宇（音译）。

Abstract: Monte Carlo Tree Search (MCTS) is often proposed for scheduling directed-acyclic-graph (DAG) workflows, yet most studies never run the comparison that could refute it - giving a much simpler method the same search effort. We run that comparison under a controlled protocol. All arms receive an identical budget - the same number of candidate schedules built and evaluated: an MCTS scheduling method, preregistered as the main arm; a randomized-restart list scheduler with no search tree as the control; and a textbook-UCT MCTS arm as a registered follow-up on the same domain.

摘要：蒙特卡洛树搜索（MCTS）常被提议用于调度有向无环图（DAG）工作流，但大多数研究从未进行过能够反驳它的对比实验——即给予一种更简单的方法相同的搜索工作量。我们在受控协议下进行了该项对比。所有实验组均获得相同的预算，即构建和评估相同数量的候选调度方案：一种预注册为主要实验组的 MCTS 调度方法；一种不带搜索树的随机重启列表调度器作为对照组；以及一种作为同一领域注册后续研究的教科书式 UCT MCTS 组。

The analysis plan was locked before data collection; an independent checker confirmed all 768 confirmation-stage schedules valid with correct finish times. At the main budget of 2048 evaluated schedules, MCTS is 2.88% worse than the restarts (95% CI [-3.62%,-2.15%]; the 72 of 96 held-out instances with positive baseline-relative headroom). The deficit is not budget starvation: on the separate exploration pool restarts self-improve by 1.85% where MCTS gains 0.24%, and 700 of 720 of MCTS’s first results are merely the warm start it was handed.

分析计划在数据收集前已锁定；一名独立检查员确认了所有 768 个验证阶段的调度方案均有效且完成时间正确。在 2048 个评估调度方案的主要预算下，MCTS 的表现比随机重启差 2.88%（95% 置信区间 [-3.62%, -2.15%]；在 96 个留存实例中，有 72 个具有正向的基准相对空间）。这种差距并非源于预算匮乏：在独立的探索池中，随机重启方法自我提升了 1.85%，而 MCTS 仅提升了 0.24%，且 MCTS 的 720 个初步结果中有 700 个仅仅是其初始获得的冷启动结果。

The studied selection rule locks deterministically onto the first-expanded child, keeping its trials correlated while restarts draw gains from the tails; the causal link to makespan remains an inference. A structural map locates where the tree stops paying: restarts win on sparse irregular workflows, no difference is detectable on regular layered ones, and dense ones leave no room to improve. Swapping the rule for textbook UCT removes most of the deficit (-0.26%, 95% CI [-0.71%,+0.23%]) without reversing its sign. Results are confined to a controlled synthetic domain (N in {8,16,32} tasks, 2-8 processors, budgets up to 2048); we make no claim about larger budgets.

所研究的选择规则确定性地锁定在第一个扩展的子节点上，使其试验保持相关性，而随机重启则从长尾分布中获益；其与完工时间之间的因果联系仍处于推论阶段。结构图定位了树搜索失效的位置：随机重启在稀疏不规则工作流上胜出，在规则分层工作流上未检测到差异，而密集工作流则没有改进空间。将规则替换为教科书式 UCT 消除了大部分差距（-0.26%，95% 置信区间 [-0.71%, +0.23%]），但并未改变其符号。研究结果仅限于受控的合成领域（任务数 N 为 {8, 16, 32}，处理器数为 2-8，预算最高为 2048）；我们不对更大预算的情况做出任何声明。