ユユ・チャン (Yuyu Zhang) 氏は10月8日(現地時間)、学術論文公開サイトarXiv cs.AIにて、モンテカルロ木探索 (MCTS) とより簡素なスケジューリング手法の性能比較に関する研究結果を発表しました。同氏の研究は、指向性非巡回グラフ (DAG) ワークフローのスケジューリングで頻繁に提案されるMCTSが、同探索予算を与えられた場合、ランダム再起動リストスケジューラ (randomized-restart list scheduler) よりも劣ることを示しています。
チャン氏の研究は、厳密な管理プロトコルの下で実施されました。MCTSスケジューリング手法を主要な比較対象とし、探索ツリーを持たないランダム再起動リストスケジューラを対照群、教科書的なUCT MCTSを追跡対象としました。全ての比較対象には、同数の候補スケジュールが構築および評価される同一の予算が割り当てられました。
2048のスケジュールを評価した主要な予算において、MCTSはランダム再起動リストスケジューラよりも2.88%劣る結果となりました（95%信頼区間は[-3.62%, -2.15%]）。この性能差は予算不足によるものではなく、個別の探索プールにおける改善率で見ると、ランダム再起動リストスケジューラが1.85%改善したのに対し、MCTSは0.24%の改善に留まりました。また、MCTSの初期結果720件中700件は、与えられたウォームスタートに過ぎませんでした。
研究されたMCTSの選択ルールは、最初に展開された子ノードに決定論的にロックされ、その試行が相関性を保つ一方で、ランダム再起動は分布の裾野から利益を引き出すという特徴があります。ツリーが効果を発揮しなくなる箇所を特定する構造マップによると、ランダム再起動はスパースで不規則なワークフローで優位に立ち、規則的な階層型ワークフローでは性能差が検出されませんでした。また、密なワークフローでは改善の余地がないと結論付けられています。
選択ルールを教科書的なUCTに切り替えた場合、性能差の大部分は解消されたものの、その符号は反転しませんでした（-0.26%、95%信頼区間は[-0.71%, +0.23%]）。これらの結果は、8、16、32のタスク、2～8のプロセッサ、および最大2048の予算を持つ制御された合成ドメインに限定されます。
参考: arXiv cs.AI — 2026年10月12日 13:00 (JST)