研究揭示：同等预算下随机重启列表调度优于蒙特卡洛树搜索用于DAG工作流

摘要：一项由arXiv发布的研究对蒙特卡洛树搜索（MCTS）和随机重启列表调度方法在有向无环图（DAG）工作流中的应用进行了对比。研究在相同计算预算下进行评估，结果显示随机重启列表调度方法在性能上优于MCTS，差距为2.88%。研究指出，MCTS的劣势并非源于搜索预算不足，而是其选择规则倾向于锁定首次扩展的子节点，导致其无法充分利用搜索空间的优势。实验还表明，在稀疏不规则的工作流中，随机重启方法表现更优，而规则分层的工作流中两者差异不大。

---

研究背景与动机

蒙特卡洛树搜索（MCTS）常被提议用于调度有向无环图（DAG）工作流，但大多数研究并未在同等条件下与更简单的调度方法进行对比。本研究旨在通过严格的实验设计，评估MCTS与随机重启列表调度方法在相同计算预算下的性能差异。

实验设计与方法

研究采用受控协议，所有调度方法在相同的预算下进行评估，即构建和评估相同数量的候选调度方案。主要实验包括：

• MCTS调度方法：作为主要研究对象。
• 随机重启列表调度方法：作为对照组，不使用搜索树。
• 教科书式UCT MCTS：作为补充研究对象。

数据分析计划在数据收集前锁定，并由独立检查员确认所有768个确认阶段的调度结果有效且完成时间正确。

主要发现

1. 性能对比：在2048个评估调度的预算下，MCTS比随机重启方法差2.88%（95%置信区间为[-3.62%, -2.15%]）。
2. 预算非瓶颈：在独立的探索池中，随机重启方法自我改进1.85%，而MCTS仅提高0.24%。此外，MCTS的首次结果中有700/720是预热的初始值。
3. 选择规则的影响：MCTS的选择规则锁定在首次扩展的子节点上，导致其相关性保持不变，而随机重启方法则从尾部中获取收益。
4. 结构化分析：在稀疏不规则的工作流中，随机重启方法表现更优；在规则分层的工作流中，两者无显著差异；而在密集工作流中，两者均无改进空间。
5. UCT调整：将选择规则替换为教科书式UCT后，差距缩小至-0.26%（95%置信区间为[-0.71%, +0.23%]），但符号未逆转。

工程权衡与讨论

• 性能与复杂性：随机重启方法在计算复杂度上较低，更适合资源受限的环境。
• 适用场景：MCTS在规则分层的工作流中表现尚可，但在复杂、不规则的工作流中劣势明显。
• 改进方向：调整选择规则或结合其他优化技术可能提升MCTS的性能。

结论

本研究通过受控实验揭示了随机重启列表调度方法在DAG工作流调度中的优越性，并为未来研究提供了新的方向。

---

消息来源：ArXiv AI (cs.AI) (2026-10-12)

—— 完 ——

主题标签： #MCTS 关注 #DAG 关注 #调度算法 关注 #随机重启 关注 #蒙特卡洛树搜索 关注