2025-11-24T20:25:17.007327

ReZero: Boosting MCTS-based Algorithms by Backward-view and Entire-buffer Reanalyze

Xuan, Niu, Pu et al.
Monte Carlo Tree Search (MCTS)-based algorithms, such as MuZero and its derivatives, have achieved widespread success in various decision-making domains. These algorithms employ the reanalyze process to enhance sample efficiency from stale data, albeit at the expense of significant wall-clock time consumption. To address this issue, we propose a general approach named ReZero to boost tree search operations for MCTS-based algorithms. Specifically, drawing inspiration from the one-armed bandit model, we reanalyze training samples through a backward-view reuse technique which uses the value estimation of a certain child node to save the corresponding sub-tree search time. To further adapt to this design, we periodically reanalyze the entire buffer instead of frequently reanalyzing the mini-batch. The synergy of these two designs can significantly reduce the search cost and meanwhile guarantee or even improve performance, simplifying both data collecting and reanalyzing. Experiments conducted on Atari environments, DMControl suites and board games demonstrate that ReZero substantially improves training speed while maintaining high sample efficiency. The code is available as part of the LightZero MCTS benchmark at https://github.com/opendilab/LightZero.
academic

ReZero: Ускорение алгоритмов на основе MCTS с помощью обратного представления и переанализа всего буфера

Основная информация

  • ID статьи: 2404.16364
  • Название: ReZero: Boosting MCTS-based Algorithms by Backward-view and Entire-buffer Reanalyze
  • Авторы: Chunyu Xuan, Yazhe Niu, Yuan Pu, Shuai Hu, Yu Liu, Jing Yang
  • Категория: cs.AI
  • Дата публикации: 31 декабря 2024 г. (последняя версия на arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2404.16364

Аннотация

Алгоритмы на основе поиска методом Монте-Карло (MCTS), такие как MuZero и его производные, достигли широкого успеха в различных областях принятия решений. Эти алгоритмы используют процесс переанализа для повышения эффективности выборки устаревших данных, но это сопровождается значительными затратами на время вычисления. Для решения этой проблемы в данной работе предлагается универсальный метод ReZero для ускорения операций поиска по дереву в алгоритмах MCTS. В частности, вдохновляясь моделью одноруких бандитов, предлагается переанализировать обучающие образцы с использованием техники повторного использования обратного представления, экономя время поиска соответствующих поддеревьев путём использования оценок стоимости конкретных дочерних узлов. Для дальнейшей адаптации к этому дизайну применяется стратегия периодического переанализа всего буфера вместо частого переанализа небольших пакетов. Синергия этих двух подходов значительно снижает затраты на поиск, одновременно гарантируя и даже улучшая производительность.

Исследовательский контекст и мотивация

Определение проблемы

Основная проблема, с которой сталкиваются алгоритмы MCTS в обучении с подкреплением, заключается в чрезмерных затратах на время вычисления, проявляющихся в двух аспектах:

  1. Этап сбора данных: агент должен выполнять MCTS каждый раз при получении нового состояния для выбора действия
  2. Этап переанализа: для получения целевых значений более высокого качества необходимо повторно запустить MCTS с использованием последней модели

Важность проблемы

  • Хотя алгоритмы MCTS демонстрируют отличную эффективность по выборкам, временная эффективность становится узким местом для их дальнейшего распространения
  • Вычисления поиска по дереву сложно распараллеливать с использованием обычных векторизованных сред, что ещё больше усугубляет проблему скорости
  • Существующие методы ускорения либо требуют дополнительных вычислительных ресурсов (например, SpeedyZero), либо сжимают пространство поиска посредством абстракции состояния (например, PTSAZero)

Исследовательская мотивация

Целью данной работы является предложение стратегии ускорения, ортогональной существующим методам, которая не требует сжатия пространства состояний и не вводит дополнительные аппаратные затраты, а вместо этого напрямую сокращает пространство поиска посредством оценки стоимости.

Основные вклады

  1. Предложена техника переанализа с обратным представлением: ускорение одного поиска по дереву с использованием метода, вдохновленного моделью одноруких бандитов, с теоретическими гарантиями сходимости
  2. Разработана структура переанализа всего буфера: дальнейшее сокращение количества вызовов MCTS и повышение возможностей параллелизации
  3. Универсальная структура: может быть беспрепятственно интегрирована в различные алгоритмы MCTS без дополнительных вычислительных ресурсов
  4. Комплексная экспериментальная верификация: валидация метода в среде Atari, наборе DMControl и настольных играх

Подробное описание метода

Определение задачи

В данной работе исследуется, как значительно снизить затраты на время вычисления алгоритмов MCTS, сохраняя при этом их эффективность по выборкам. Входными данными являются данные траектории алгоритма MCTS, выходными данными — ускоренная стратегия поиска и оценка стоимости.

Архитектура основного метода

1. Переанализ с обратным представлением (Backward-view Reanalyze)

Теоретическая основа: вдохновляясь моделью одноруких бандитов, корневой узел поиска по дереву рассматривается как игровой автомат, а каждый дочерний узел — как рычаг. Если можно заранее узнать истинную стоимость состояния конкретного дочернего узла, можно сэкономить время поиска по его поддереву.

Конкретная реализация:

Для соседних временных шагов S^t_l и S^{t+1}_l:
- При поиске S^{t+1}_l получается стоимость корневого узла m^{t+1}_l
- При поиске S^t_l стоимость S^{t+1}_l фиксируется как m^{t+1}_l

Стратегия выбора действия:

a_root = argmax_a I^t_l(a)

где I^t_l(a) = {
    UCBscore(S^t_l, a),  если a ≠ a^t_l
    r^t_l + γm^{t+1}_l,  если a = a^t_l
}

При выборе действия, соответствующего S^{t+1}_l, предварительно сохранённая стоимость используется напрямую, избегая поиска по поддереву.

2. Переанализ всего буфера (Entire-buffer Reanalyze)

Мотивация дизайна: переанализ с обратным представлением требует разделения пакетов на более мелкие подпакеты, что может снизить преимущества параллелизации.

Решение:

  1. Улучшение этапа сбора: прямое использование выборки действий из выходных данных сетевой политики вместо выбора MCTS
  2. Периодический переанализ: переанализ всего буфера после фиксированного количества итераций обучения вместо переанализа небольших пакетов на каждой итерации

Преимущества:

  • Аналогично механизму фиксированной целевой сети в DQN, снижает частоту обновления целевой политики
  • Концентрирует все вызовы MCTS в процессе переанализа, полностью используя преимущества параллелизации больших пакетов
  • Разделяет переанализ и процесс обучения, обеспечивая большее пространство для параллелизации

Теоретический анализ

Теорема 1: для нестационарного одноруких бандитов, удовлетворяющих предположениям уравнения (2), использование оценок выборки вместо значений UCB для оценки конкретного рычага гарантирует ET_i(n)/n → 0 при n → ∞.

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

Экспериментальная установка

Наборы данных и среды

  1. Среда Atari: 26 репрезентативных игр с высокомерными визуальными входами и дискретным пространством действий
  2. Набор DMControl: две задачи непрерывного управления — ball_in_cup-catch и walker-stand
  3. Настольные игры: Connect4 и Gomoku, стратегические игры с особыми пространствами состояний

Метрики оценки

  • Временная эффективность: время вычисления, необходимое для достижения одного уровня производительности
  • Эффективность по выборкам: количество взаимодействий с окружающей средой, необходимых для достижения успешной политики
  • Ускорение поиска: затраты времени одного MCTS и количество вызовов функций

Методы сравнения

  • MuZero: исходный алгоритм MuZero
  • EfficientZero: улучшенный вариант MuZero
  • ReZero-M: MuZero с интегрированным ReZero
  • ReZero-E: EfficientZero с интегрированным ReZero

Детали реализации

  • Коэффициент воспроизведения: 0,25
  • Частота переанализа: 1
  • Размер пакета: 256 (Atari), 64 (DMControl)
  • Количество симуляций MCTS: 50
  • Оборудование: одна видеокарта NVIDIA A100 GPU, 30 ядер CPU, 120 ГБ памяти

Результаты экспериментов

Основные результаты

Улучшение временной эффективности:

  • В большинстве игр ReZero требует в 2-4 раза меньше времени вычисления, чем базовые методы
  • Игра Pong: ReZero-M 1,0±0,1 часа против MuZero 4,0±0,5 часа
  • Игра MsPacman: ReZero-M 1,4±0,2 часа против MuZero 6,9±0,3 часа
  • Игра Connect4: ReZero-M 5,5±0,6 часа против MuZero 9,1±0,8 часа

Сохранение эффективности по выборкам: во всех тестируемых средах ReZero сохраняет сравнимую или даже лучшую эффективность по выборкам, чем базовые методы.

Абляционные исследования

1. Влияние частоты переанализа

Тестирование эффекта частоты переанализа {0, 1/3, 1, 2}:

  • Надлежащая частота переанализа может сэкономить затраты времени без явного снижения производительности
  • Частота 1 достигает оптимального баланса между временем и эффективностью по выборкам

2. Эффект переанализа с обратным представлением

Подробная статистика показывает:

  • Среднее время поиска: ReZero-M 0,69±0,02 мс против MuZero 1,08±0,09 мс
  • Количество вызовов поиска по дереву: ReZero-M 6089 против MuZero 13284
  • Вызовы динамической модели: ReZero-M 122 против MuZero 256

Анализ конкретных случаев

Верификация на игрушечном примере: эксперимент в сеточном мире 7×7 наглядно демонстрирует эффект ускорения пропуска поиска по поддереву. Время поиска в позициях, удалённых от конечной точки, увеличивается, и использование вспомогательной стоимости корневого узла обычно снижает время поиска.

Экспериментальные находки

  1. Переанализ с обратным представлением не только повышает скорость одного поиска, но и улучшает эффективность по выборкам
  2. Переанализ всего буфера эффективно снижает количество вызовов MCTS
  3. Метод демонстрирует последовательный эффект ускорения в различных типах сред принятия решений

Связанные работы

Развитие алгоритмов MCTS

  • AlphaGo/AlphaZero: объединение MCTS с глубоким обучением с подкреплением, прорыв в настольных играх
  • MuZero: расширение на сценарии с неизвестной моделью окружающей среды, более широкая область применения
  • Последующие улучшения: EfficientZero повышает эффективность по выборкам, MuZero Unplugged расширяет на автономные настройки

Исследование ускорения MCTS

  • SpeedyZero: снижение затрат времени посредством параллельного системного дизайна, но требует больше вычислительных ресурсов
  • PTSAZero: сжатие пространства поиска посредством абстракции состояния
  • KataGo: использование наивных приёмов повторного использования информации, но метод обратного представления в данной работе принципиально отличается

Заключение и обсуждение

Основные выводы

  1. ReZero успешно решает проблему чрезмерных затрат на время вычисления в алгоритмах MCTS
  2. Синергия переанализа с обратным представлением и переанализа всего буфера значительно повышает временную эффективность
  3. Метод обладает универсальностью и может применяться к различным вариантам алгоритмов MCTS
  4. Достигается ускорение в 2-4 раза при сохранении эффективности по выборкам

Ограничения

  1. Ограничения одномашинной установки: текущие эксперименты проводились в основном в одномашинной среде, пространство оптимизации для распределённого обучения требует дальнейшего исследования
  2. Охват окружающей среды: эксперименты в среде непрерывного управления относительно ограничены, требуется более полное тестирование
  3. Теоретический анализ: хотя предоставлено доказательство сходимости, теоретические гарантии в реальных сложных средах требуют дальнейшего исследования

Будущие направления

  1. Распределённая оптимизация: применение ReZero к распределённому обучению с подкреплением
  2. Автономное обучение: интеграция с MuZero Unplugged для применения на автономных наборах данных
  3. Базовые модели: построение базовых моделей принятия решений с использованием больших наборов данных, таких как RT-X
  4. Взвешенная выборка: использование более разумных способов приоритизации переанализа части образцов в буфере

Глубокая оценка

Преимущества

  1. Высокая инновационность: переанализ с обратным представлением — это новый подход к ускорению MCTS с прочной теоретической основой
  2. Высокая практическая ценность: значительный эффект ускорения времени имеет важное значение для практического применения алгоритмов MCTS
  3. Хорошая универсальность: дизайн структуры позволяет беспрепятственно интегрировать её в различные алгоритмы MCTS
  4. Достаточные эксперименты: валидация метода в различных типах сред с подробными абляционными исследованиями

Недостатки

  1. Глубина теоретического анализа: хотя предоставлено доказательство сходимости, теоретические гарантии для сложных сред требуют усиления
  2. Распределённые сценарии: отсутствует верификация и оптимизация в многомашинной многокарточной среде
  3. Непрерывное управление: эксперименты в пространстве непрерывных действий относительно ограничены
  4. Долгосрочное воздействие: долгосрочное воздействие на стабильность обучения и финальную производительность требует дополнительного анализа

Влияние

  1. Академический вклад: предоставляет новое направление исследования для ускорения MCTS, уравновешивая теорию и практику
  2. Практическая ценность: напрямую решает ключное узкое место в развёртывании алгоритмов MCTS
  3. Воспроизводимость: предоставляет полную реализацию с открытым исходным кодом, облегчая использование и расширение исследовательским сообществом

Применимые сценарии

  1. Игровой ИИ: настольные игры, видеоигры и другие сценарии, требующие принятия решений в реальном времени
  2. Управление роботами: задачи робототехники, требующие онлайн-планирования
  3. Автономное вождение: быстрое планирование пути и принятие решений
  4. Финансовая торговля: быстрое принятие решений в высокочастотной торговле

Библиография

  1. Schrittwieser, J., et al. (2019). Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588, 604-609.
  2. Silver, D., et al. (2017). Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815.
  3. Ye, W., et al. (2021). Mastering atari games with limited data. Advances in Neural Information Processing Systems, 34, 25476-25488.
  4. Mei, Y., et al. (2023). Speedyzero: Mastering atari with limited data and time. ICLR 2023.

Общая оценка: это высококачественная исследовательская работа, предлагающая инновационное и практичное решение для узкого места в практическом развёртывании алгоритмов MCTS. Дизайн метода остроумен, теоретическая основа прочна, экспериментальная верификация полна, что имеет важное значение для продвижения популяризации алгоритмов MCTS в практических приложениях.