MCTS проиграл случайным рестартам 2,88% в планировании DAG при равном бюджете

Исследователи на arXiv поставили Monte Carlo Tree Search и обычный list scheduler со случайными перезапусками в одинаковые условия: по 2048 построенных и оценённых расписаний на каждую задачу. Дерево поиска проиграло. На 72 из 96 отложенных инстансов, где у базового решения был запас для улучшения, MCTS оказался на 2,88% хуже по makespan (95% ДИ от −3,62% до −2,15%). Работа не доказывает, что MCTS бесполезен. Зато показывает, что сравнение без простого конкурента с тем же бюджетом мало что говорит.

Протокол, который мог опровергнуть MCTS

Авторы исходят из наблюдения: статьи про MCTS в планировании DAG-воркфлоу редко дают простому методу столько же вычислений. Здесь все участники получают одинаковое число кандидатов-расписаний. Основной участник — MCTS-метод, заранее заявленный как главный. Контроль — list scheduler с рандомизированными перезапусками и без дерева. Позже на той же области добавили третьего — MCTS с учебным UCT.

План анализа зафиксировали до сбора данных. Независимый чекер проверил все 768 расписаний подтверждающей стадии: все валидны, времена завершения посчитаны верно.

• Основной бюджет: 2048 оценённых расписаний.
• Разрыв MCTS и рестартов: −2,88%, ДИ [−3,62%; −2,15%].
• Самоулучшение на отдельном пуле исследования: рестарты +1,85%, MCTS +0,24%.
• Первые результаты MCTS: 700 из 720 совпали с warm start, который ему передали.
• MCTS с учебным UCT: −0,26%, ДИ [−0,71%; +0,23%].
• Масштаб: 8, 16 и 32 задачи, 2–8 процессоров, бюджеты до 2048.

Почему дерево не помогло

Первая гипотеза — что MCTS просто не хватило бюджета. Данные её не поддерживают: на пуле исследования рестарты улучшали себя на 1,85%, а MCTS только на 0,24%. К тому же в 700 из 720 случаев первый результат MCTS был лишь тем стартовым решением, которое ему выдали. То есть дерево почти не уходило от стартовой точки.

По версии авторов, причина в правиле выбора. Оно детерминированно залипает на первом раскрытом потомке, поэтому испытания внутри ветки сильно коррелируют. Рестарты каждый раз выбирают новую траекторию и берут выигрыш из хвостов распределения. Связь с makespan авторы называют выводом, а не доказанным причинным механизмом. Подтверждает версию эксперимент с заменой правила на классический UCT: отставание сжимается до 0,26%, и доверительный интервал уже включает ноль. Но знак остаётся отрицательным, так что MCTS не обгоняет рестарты даже в исправленной версии.

Отдельно авторы построили структурную карту. На разреженных нерегулярных воркфлоу выигрывают рестарты. На регулярных слоистых различий не видно. На плотных графах улучшать почти нечего, потому что базовое решение уже близко к пределу.

Что проверить перед тем, как строить дерево

Для инженеров, которые планируют задачи в пайплайнах данных, обучении моделей или агентных цепочках, вывод приземлённый. Прежде чем внедрять MCTS, стоит запустить list scheduler с рандомизацией на том же числе оценок. Это реализуется за вечер и даёт честную точку отсчёта. Если дерево не обходит её, сложность не оправдана.

Вторая проверка — доля решений, где поиск ушёл от warm start. Если почти все результаты совпадают со стартом, алгоритм почти не исследует. Третья — само правило выбора ветки: от него зависит, будет ли дерево разнообразным.

Ограничения работы авторы называют сами. Эксперимент синтетический, графы небольшие (до 32 задач), бюджет не превышает 2048. О больших бюджетах и реальных воркфлоу вывода нет. Но как образец дисциплины работа полезна: преregистрация, равный бюджет и независимая проверка валидности расписаний. Для агентных систем, где планировщики часто вводят из-за модного названия алгоритма, такой контроль нужен не меньше, чем новые методы.