MCTS проигрывает простому планировщику: жесткий тест на DAG-задачах

Суть эксперимента: равные условия для разных подходов

Исследователь Юйю Чжан (Yuyu Zhang) провел контролируемое сравнение двух подходов к планированию задач в виде направленных ациклических графов (DAG). В отличие от многих работ, где сложные методы сравниваются с простыми при неравных ресурсах, здесь использовался протокол Equal-Budget: обеим сторонам выделялся идентичный объем вычислений — количество создаваемых и оцениваемых расписаний.

В исследовании участвовали три алгоритма:

• Основной кандидат (Main Arm): Специализированный метод MCTS для планирования.
• Контроль (Control): Простой планировщик списков с случайными перезапусками (Randomized-Restart List Scheduling), не использующий дерево поиска.
• Фоллоу-ап (Follow-up): Классический алгоритм UCT (Upper Confidence Bound applied to Trees) для проверки гипотезы о выборе правил.

Результаты: MCTS проигрывает на 2.88%

При базовом бюджете в 2048 оцененных расписаний MCTS показал результат, который статистически значимо хуже простого планировщика. Разница составила 2.88% (95% доверительный интервал [-3.62%, -2.15%]).

Анализ показал, что проблема не в нехватке бюджета (starvation). При использовании отдельного пула для исследования (exploration pool) простой планировщик улучшал результат на 1.85%, в то время как MCTS — лишь на 0.24%. Более того, 700 из 720 первых результатов MCTS были просто «теплым стартом» (warm start), то есть алгоритм тратил ресурсы на инициализацию, а не на поиск.

Почему дерево поиска «зависло»?

Ключевой причиной проигрыша стала эвристика выбора узла (selection rule). В исследуемой версии MCTS правило детерминированно фиксировалось на первом расширенном дочернем узле. Это создавало сильную корреляцию между испытаниями и мешало алгоритму исследовать хвосты распределения, откуда часто приходят улучшения у метода с перезапусками.

Замена правила на классический UCT устранила большую часть отставания (разница сократилась до -0.26%), но не сделала MCTS победителем. Это указывает на то, что проблема не только в выборе узла, но и в самой структуре поиска для данного типа задач.

Где MCTS бесполезен, а где полезен?

Исследование выявило четкую зависимость эффективности от структуры графа:

• Разреженные нерегулярные графы: Здесь выигрывает Randomized-Restart. У дерева поиска нет структуры для навигации, и оно проигрывает в эффективности.
• Регулярные многослойные графы: Различий между методами статистически не обнаружено.
• Плотные графы: Пространство решений настолько ограничено, что улучшать нечего ни одному из методов.

Параметры теста

Эксперимент проводился на синтетическом наборе данных с количеством задач N ∈ {8, 16, 32} и от 2 до 8 процессоров. Все 768 расписаний на этапе подтверждения были проверены независимым контролером на корректность времени завершения.

Результаты подтверждают важность preregistered negative results: сложные методы не всегда лучше простых, если их сравнивать в строго равных условиях.

Источник: arXiv cs.AI ↗