arXiv cs.AI· Yuyu Zhang·· 6 天前AI 评分20
等预算下 MCTS 与随机重启列表调度在 DAG 工作流上的对照计算研究
Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study
AI 导读
一项预注册的等预算对照研究显示，在 2048 次候选调度评估的预算下，MCTS 调度方法比无搜索树的随机重启列表调度差 2.88%（95% CI [-3.62%,-2.15%]）。
正文 · AI 翻译
摘要：蒙特卡洛树搜索（MCTS）常被提议用于调度有向无环图（DAG）工作流，但大多数研究从未进行过能够反驳它的比较——即让一个简单得多的方法获得相同的搜索投入。我们在受控协议下进行了这一比较。所有分支获得相同的预算——构建和评估的候选调度数量相同：一个 MCTS 调度方法，预注册为主要分支；一个无搜索树的随机重启列表调度器作为对照；以及一个教科书式 UCT MCTS 分支，作为同一领域上的注册后续实验。分析计划在数据收集前锁定；独立检查员确认全部 768 个确认阶段调度有效且完工时间正确。在 2048 个已评估调度的主要预算下，MCTS 比随机重启差 2.88%（95% CI [-3.62%,-2.15%]；96 个留出实例中有 72 个具有正的相对基线余量）。这一劣势并非预算不足：在单独的探索池上，随机重启自我改进 1.85%，而 MCTS 仅提升 0.24%，且 MCTS 的 720 个首次结果中有 700 个仅仅是它被赋予的热启动。所研究的选择规则确定性地锁定到第一个扩展的子节点，使其试验相互关联，而随机重启从尾部获得收益；与完工时间的因果联系仍是一种推断。一张结构图定位了树停止带来收益的位置：随机重启在稀疏不规则工作流上获胜，在规则分层工作流上检测不到差异，而密集工作流则没有改进空间。将规则替换为教科书式 UCT 消除了大部分劣势（-0.26%，95% CI [-0.71%,+0.23%]），但未改变其符号。结果仅限于受控合成领域（任务数 N 在 {8,16,32}，2-8 个处理器，预算最高 2048）；我们不对更大预算作出任何断言。
| 评论： | 19 页，4 幅图。预注册的负面结果，附开放评估协议；配套工件存档于 https://doi.org/10.5281/zenodo.22929494 和 https://doi.org/10.5281/zenodo.22930513 |
| 主题： | 人工智能（cs.AI）；分布式、并行与集群计算（cs.DC）；机器学习（cs.LG） |
| 引用为： | arXiv:2610.12542 [cs.AI] |
| （或本版本使用 arXiv:2610.12542v1 [cs.AI]） | |
| https://doi.org/10.48550/arXiv.2610.12542 arXiv 颁发的 DOI，通过 DataCite（待注册） |
提交历史
来自：Yuyu Zhang [查看电子邮件]
[v1]
2026 年 10 月 8 日星期四 16:01:53 UTC（241 KB）
来源：arXiv cs.AI · arxiv.org