# Алгоритмы принятия решений: от MCTS до AlphaGo

Источник: https://www.youtube.com/watch?v=iLMzsV0JOHk
Канал: Stanford Online
Опубликовано: 04.12.2024

---

## Планирование и поиск стратегий в условиях неопределённости
[[JUMP:00:05]]

Лекция Stanford Online по курсу AA228/CS238 посвящена методам онлайн-планирования и поиска стратегий (policy search) в задачах, где будущее состояние агента неопределенно. Ключевая концепция — различие между «офлайн» и «онлайн» планированием. Если офлайн-стратегии вычисляются заранее для всех возможных состояний, то онлайн-методы фокусируются на достижимом пространстве состояний «здесь и сейчас», используя схему планирования с «редеющим горизонтом» (receding horizon planning).

### 🧠 Концепции планирования
[[JUMP:01:03]]

*   **Достижимое пространство состояний (Reachable State Space):** Это набор будущих состояний, которые агент может посетить, исходя из текущей позиции. Действия из прошлого (например, когда вам было 12 лет) в это пространство уже не входят.
*   **Планирование с редеющим горизонтом:** Агент планирует действия на глубину $D$, выполняет первый шаг, переходит в новое состояние и повторяет процесс, сдвигая горизонт. Это стандарт для автономного вождения (например, системы Waymo), где автомобиль постоянно обновляет маршрут при появлении новых данных.

Спикер проводит аналогию с «мышлением системы 1 и системы 2» (по Даниэлю Канеману):

*   **Система 1 (Bullet Chess):** Быстрая интуитивная реакция, основанная на готовых паттернах.
*   **Система 2 (Делиберация):** Медленный просчет вариантов, глубокая оценка возможных ответных ходов противника.

### 🛠 Методы онлайн-планирования
[[JUMP:15:51]]

В лекции подробно разбираются несколько алгоритмов поиска:

1.  **Lookahead with Rollouts:** Использует «просмотр вперед» для оценки полезности стратегии через серию симуляций (rollouts).
    *   *Процесс:* Для оценки состояния используется случайная или заранее обученная стохастическая стратегия, которая «проигрывает» ситуацию до глубины $D$.
    *   *Недостаток:* Высокая вычислительная сложность при больших пространствах состояний.

2.  **Forward Search:** Построение полного дерева поиска всех возможных переходов.
    *   *Сложность:* $O((S \times A)^D)$, где $S$ — состояния, $A$ — действия, $D$ — глубина. Спикер иронично называет этот фактор "SAD" (от S-A-D), так как дерево разрастается катастрофически быстро.

3.  **Branch and Bound:** Пытается сократить перебор, отсекая ветви дерева, которые математически не могут быть лучше уже найденного оптимального пути.
    *   *Условие отсечения:* Если верхняя граница (upper bound) текущего действия хуже, чем уже найденная лучшая полезность (utility), ветвь обрезается.

4.  **Sparse Sampling:** Вместо ветвления по всем состояниям, алгоритм берет ограниченное число выборок (samples) переходов. Это снижает сложность до $m \times A^D$, делая поиск более управляемым, но привнося ошибку аппроксимации.

### 🎲 Monte Carlo Tree Search (MCTS)
[[JUMP:34:47]]

MCTS — один из самых популярных и масштабируемых методов. Его работа делится на четыре фазы:

1.  **Selection:** Выбор перспективного действия с использованием стратегии Upper Confidence Bound (UCB), которая балансирует исследование новых путей и использование уже проверенных.
2.  **Expansion:** Выполнение действия и переход в новое состояние.
3.  **Simulation:** Оценка полезности состояния (часто через rollouts или нейросеть).
4.  **Update:** Обновление оценок (Q-функции и счетчиков посещений) вверх по дереву.

Пример с игрой *2048* показывает, что MCTS позволяет агенту «думать» перед ходом, имитируя поведение системы 2, что существенно эффективнее, чем просто полагаться на базовую нейросеть (система 1).

### 🧬 Гибридные подходы и поиск стратегий
[[JUMP:62:44]]

В современных системах, таких как *AlphaGo Zero*, используются гибридные методы: обучение нейросети с помощью self-play и MCTS.

*   *Инсайт от Энди Джонса:* Существует «трейдофф» между вычислительными мощностями при обучении (offline) и при выполнении (online). Снижение затрат на обучение в 10 раз может компенсироваться увеличением онлайн-вычислений в 15 раз при сохранении того же качества игры.

В разделе **Policy Search** обсуждаются методы оптимизации параметров стратегии ($\theta$) напрямую, без вычисления значений состояний.

*   **Local Search:** Локальные изменения параметров с оценкой через роллауты.
*   **Cross Entropy Method:** Вместо локального изменения, алгоритм сэмплирует параметры из распределения, оценивает их и «подгоняет» распределение под лучшие результаты, что зачастую эффективнее для сложных пространств.