Планирование и поиск стратегий в условиях неопределённости 0:05
Лекция Stanford Online по курсу AA228/CS238 посвящена методам онлайн-планирования и поиска стратегий (policy search) в задачах, где будущее состояние агента неопределенно. Ключевая концепция — различие между «офлайн» и «онлайн» планированием. Если офлайн-стратегии вычисляются заранее для всех возможных состояний, то онлайн-методы фокусируются на достижимом пространстве состояний «здесь и сейчас», используя схему планирования с «редеющим горизонтом» (receding horizon planning).
🧠 Концепции планирования 1:03
- Достижимое пространство состояний (Reachable State Space): Это набор будущих состояний, которые агент может посетить, исходя из текущей позиции. Действия из прошлого (например, когда вам было 12 лет) в это пространство уже не входят.
- Планирование с редеющим горизонтом: Агент планирует действия на глубину $D$, выполняет первый шаг, переходит в новое состояние и повторяет процесс, сдвигая горизонт. Это стандарт для автономного вождения (например, системы Waymo), где автомобиль постоянно обновляет маршрут при появлении новых данных.
Спикер проводит аналогию с «мышлением системы 1 и системы 2» (по Даниэлю Канеману):
- Система 1 (Bullet Chess): Быстрая интуитивная реакция, основанная на готовых паттернах.
- Система 2 (Делиберация): Медленный просчет вариантов, глубокая оценка возможных ответных ходов противника.
🛠 Методы онлайн-планирования 15:51
В лекции подробно разбираются несколько алгоритмов поиска:
-
Lookahead with Rollouts: Использует «просмотр вперед» для оценки полезности стратегии через серию симуляций (rollouts).
- Процесс: Для оценки состояния используется случайная или заранее обученная стохастическая стратегия, которая «проигрывает» ситуацию до глубины $D$.
- Недостаток: Высокая вычислительная сложность при больших пространствах состояний.
-
Forward Search: Построение полного дерева поиска всех возможных переходов.
- Сложность: $O((S \times A)^D)$, где $S$ — состояния, $A$ — действия, $D$ — глубина. Спикер иронично называет этот фактор "SAD" (от S-A-D), так как дерево разрастается катастрофически быстро.
-
Branch and Bound: Пытается сократить перебор, отсекая ветви дерева, которые математически не могут быть лучше уже найденного оптимального пути.
- Условие отсечения: Если верхняя граница (upper bound) текущего действия хуже, чем уже найденная лучшая полезность (utility), ветвь обрезается.
-
Sparse Sampling: Вместо ветвления по всем состояниям, алгоритм берет ограниченное число выборок (samples) переходов. Это снижает сложность до $m \times A^D$, делая поиск более управляемым, но привнося ошибку аппроксимации.
🎲 Monte Carlo Tree Search (MCTS) 34:47
MCTS — один из самых популярных и масштабируемых методов. Его работа делится на четыре фазы:
- Selection: Выбор перспективного действия с использованием стратегии Upper Confidence Bound (UCB), которая балансирует исследование новых путей и использование уже проверенных.
- Expansion: Выполнение действия и переход в новое состояние.
- Simulation: Оценка полезности состояния (часто через rollouts или нейросеть).
- Update: Обновление оценок (Q-функции и счетчиков посещений) вверх по дереву.
Пример с игрой 2048 показывает, что MCTS позволяет агенту «думать» перед ходом, имитируя поведение системы 2, что существенно эффективнее, чем просто полагаться на базовую нейросеть (система 1).
🧬 Гибридные подходы и поиск стратегий 62:44
В современных системах, таких как AlphaGo Zero, используются гибридные методы: обучение нейросети с помощью self-play и MCTS.
- Инсайт от Энди Джонса: Существует «трейдофф» между вычислительными мощностями при обучении (offline) и при выполнении (online). Снижение затрат на обучение в 10 раз может компенсироваться увеличением онлайн-вычислений в 15 раз при сохранении того же качества игры.
В разделе Policy Search обсуждаются методы оптимизации параметров стратегии ($\theta$) напрямую, без вычисления значений состояний.
- Local Search: Локальные изменения параметров с оценкой через роллауты.
- Cross Entropy Method: Вместо локального изменения, алгоритм сэмплирует параметры из распределения, оценивает их и «подгоняет» распределение под лучшие результаты, что зачастую эффективнее для сложных пространств.
