Spinning Up, часть 2: виды алгоритмов RL

Где в курсе то же самое проще

Две ветви «без модели» разобраны в модуле 6.0 руками и кодом: Q-learning и DQN, on-policy против off-policy — в уроке 6.0.2 «Монте-Карло, TD и Q-learning»; градиент политики, actor-critic и PPO — в уроке 6.0.3. Планирование по модели (MCTS) встречается в уроке 6.4.4 о test-time compute. Эта страница — карта, на которой все эти методы видны вместе.

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

Таксономия алгоритмов RL

flowchart TD
RL["Алгоритмы RL"] --> MF["Без модели (Model-Free RL)"]
RL --> MB["С моделью (Model-Based RL)"]
MF --> PO["Оптимизация политики"]
MF --> QL["Q-learning"]
PO --> PG["Policy Gradient"]
PO --> A2C["A2C / A3C"]
PO --> PPO["PPO"]
PO --> TRPO["TRPO"]
PO -.-> DDPG["DDPG"]
QL -.-> DDPG
PO -.-> TD3["TD3"]
QL -.-> TD3
PO -.-> SAC["SAC"]
QL -.-> SAC
QL --> DQN["DQN"]
QL --> C51["C51"]
QL --> QR["QR-DQN"]
QL --> HER["HER"]
MB --> LM["Модель обучается"]
MB --> GM["Модель дана"]
LM --> WM["World Models"]
LM --> I2A["I2A"]
LM --> MBMF["MBMF"]
LM --> MBVE["MBVE"]
GM --> AZ["AlphaZero"]

Неполная, но полезная таксономия алгоритмов современного RL. Пунктир — алгоритмы между оптимизацией политики и Q-learning. В оригинале — рисунок rl_algorithms_9_15.svg; ссылки на статьи — в конце страницы

Начнём с оговорки: нарисовать точную и всеобъемлющую таксономию алгоритмов современного RL действительно трудно, потому что модульность алгоритмов плохо укладывается в древовидную структуру. Кроме того, чтобы картинка помещалась на страницу и легко усваивалась во вводном тексте, приходится опустить довольно много продвинутого материала (исследование, перенос обучения, метаобучение и т. д.). С учётом этого наши цели —

• выделить самые фундаментальные решения при разработке алгоритмов глубокого RL: что учить и как учить;
• показать компромиссы, связанные с этими решениями;
• и поместить несколько известных современных алгоритмов в контекст этих решений.

RL без модели против RL с моделью

Одна из важнейших развилок в алгоритме RL — вопрос о том, есть ли у агента доступ к модели среды (или учит ли он её). Под моделью среды мы понимаем функцию, которая предсказывает переходы между состояниями и награды.

Главный плюс модели в том, что она позволяет агенту планировать: думать наперёд, смотреть, что произойдёт при разных вариантах выбора, и явно решать, какой вариант взять. Затем агент может дистиллировать результаты планирования в выученную политику. Особенно известный пример такого подхода — AlphaZero. Когда это работает, можно получить заметный выигрыш в эффективности использования данных (sample efficiency) по сравнению с методами без модели.

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

Алгоритмы, которые используют модель, называют методами с моделью (model-based), а те, что не используют, — методами без моделиобучение без модели среды (model-free RL)EN model-free reinforcement learningАгент не знает вероятностей переходов и наград и учится только на собственном опыте. (model-free). Методы без модели отказываются от потенциального выигрыша в эффективности использования данных, зато их обычно проще реализовать и настроить. На момент написания этого введения (сентябрь 2018) методы без модели популярнее и гораздо лучше разработаны и проверены, чем методы с моделью.

Что учить

Ещё одна критически важная развилка в алгоритме RL — вопрос о том, что учить. Обычный список кандидатов:

• политики, стохастические или детерминированные,
• функции ценности действия (Q-функции),
• функции ценности,
• и/или модели среды.

Что учить в RL без модели

Есть два основных подхода к представлению и обучению агентов в RL без модели.

Оптимизация политики (policy optimization). Методы этого семейства явно представляют политику как $\pi_{\theta}(a|s)$. Они оптимизируют параметры $\theta$ либо напрямую — градиентным подъёмом по целевой функции качества $J(\pi_{\theta})$, — либо косвенно, максимизируя локальные приближения $J(\pi_{\theta})$. Эта оптимизация почти всегда выполняется on-policyon-policy (обучение на данных текущей политики)EN on-policyПротивоположность — off-policy, обучение на данных другой политики.: каждое обновление использует только данные, собранные во время действий по самой свежей версии политики. Обычно при оптимизации политики учат ещё и аппроксиматор $V_{\phi}(s)$ для функции ценности on-policy $V^{\pi}(s)$, который помогает понять, как обновлять политику.

Пара примеров методов оптимизации политики:

• A2C / A3C — выполняет градиентный подъём, чтобы напрямую максимизировать качество;
• и PPO — его обновления максимизируют качество косвенно: они максимизируют суррогатную целевую функцию (surrogate objective), которая даёт консервативную оценку того, насколько изменится $J(\pi_{\theta})$ в результате обновления.

Q-learning. Методы этого семейства учат аппроксиматор $Q_{\theta}(s,a)$ для оптимальной функции ценности действия $Q^*(s,a)$. Обычно они используют целевую функцию на основе уравнения Беллмана. Эта оптимизация почти всегда выполняется off-policyoff-policy (обучение на данных другой политики)EN off-policyПолитика, которую учим, отличается от той, что собирала данные. Пример — Q-learning; в PPO и GRPO — поправка π/π_old.: каждое обновление может использовать данные, собранные в любой момент обучения, независимо от того, как агент решал исследовать среду, когда эти данные получал. Соответствующая политика получается через связь между $Q^*$ и $\pi^*$: действия агента Q-learning задаются формулой

$$a(s) = \arg \max_a Q_{\theta}(s,a).$$

Словами: в каждом состоянии агент берёт то действие, у которого выученная Q-функция наибольшая.

Примеры методов Q-learning:

• DQN — классика, которая во многом дала старт области глубокого RL;
• и C51 — вариант, который учит распределение отдачи, матожидание которого равно $Q^*$.

Компромиссы между оптимизацией политики и Q-learning. Главная сила методов оптимизации политики в их принципиальности: вы напрямую оптимизируете то, что вам нужно. Поэтому они, как правило, стабильны и надёжны. Методы Q-learning, напротив, оптимизируют качество агента лишь косвенно, обучая $Q_{\theta}$ удовлетворять уравнению самосогласованности. У такого обучения много способов сломаться, поэтому оно обычно менее стабильно.¹ Зато методы Q-learning, когда работают, заметно эффективнее используют данные, потому что переиспользуют их лучше, чем методы оптимизации политики.

Промежуточные варианты между оптимизацией политики и Q-learning. По счастливому совпадению оптимизация политики и Q-learning не противоречат друг другу (а при некоторых условиях, как выясняется, эквивалентны), и существует целый спектр алгоритмов между двумя крайностями. Алгоритмы из этого спектра умеют аккуратно балансировать сильные и слабые стороны обеих сторон. Примеры:

• DDPG — алгоритм, который одновременно учит детерминированную политику и Q-функцию, используя каждую для улучшения другой;
• и SAC — вариант, который использует стохастические политики, энтропийную регуляризацию и несколько других трюков, чтобы стабилизировать обучение и набирать на стандартных бенчмарках больше, чем DDPG.

Что учить в RL с моделью

В отличие от RL без модели, для RL с моделью нет небольшого числа легко определимых групп методов: моделями можно пользоваться множеством независимых способов. Мы приведём несколько примеров, но список далеко не полон. В каждом случае модель может быть либо дана, либо выучена.

Основа: чистое планирование. Самый базовый подход никогда явно не представляет политику, а выбирает действия чистыми методами планирования, например управлением с прогнозирующей моделью (model-predictive control, MPC). В MPC каждый раз, когда агент наблюдает среду, он вычисляет план, оптимальный относительно модели. План описывает все действия на некоторое фиксированное окно времени после текущего момента. (Будущие награды за пределами горизонта алгоритм планирования может учесть с помощью выученной функции ценности.) Затем агент выполняет первое действие плана и сразу отбрасывает остальное. Новый план он вычисляет каждый раз, готовясь взаимодействовать со средой, чтобы не использовать действие из плана с горизонтом короче желаемого.

• Работа MBMF исследует MPC с выученными моделями среды на некоторых стандартных бенчмарках глубокого RL.

Экспертная итерация (expert iteration). Естественное продолжение чистого планирования — использовать и учить явное представление политики $\pi_{\theta}(a|s)$. Агент запускает в модели алгоритм планирования (например, поиск по дереву Монте-Карло, MCTSпоиск по дереву Монте-Карло (MCTS)EN Monte Carlo tree search (MCTS)Алгоритм поиска, прославившийся благодаря AlphaGo. Для генерации текста пространство ходов слишком велико — ещё одна «неудачная попытка» R1.), порождая действия-кандидаты для плана сэмплированием из текущей политики. Алгоритм планирования выдаёт действие лучше того, что выдала бы одна политика, — поэтому он «эксперт» по отношению к политике. Затем политику обновляют так, чтобы она выдавала действие, больше похожее на результат алгоритма планирования.

• Алгоритм ExIt использует этот подход, чтобы учить глубокие нейросети играть в Hex.
• AlphaZero — ещё один пример этого подхода.

Аугментация данных для методов без модели. Политику или Q-функцию учат алгоритмом RL без модели, но 1) дополняют реальный опыт вымышленным при обновлении агента или 2) используют для обновления агента только вымышленный опыт.

• Пример дополнения реального опыта вымышленным — MBVE.
• Пример обучения агента только на вымышленном опыте — World Models; авторы называют это «обучением во сне».

Встраивание циклов планирования в политику. Ещё один подход встраивает процедуру планирования прямо в политику как подпрограмму — так что полные планы становятся для политики дополнительной информацией, — а выход политики обучают любым стандартным алгоритмом без модели. Ключевая идея в том, что в такой схеме политика может научиться решать, как и когда пользоваться планами. Из-за этого смещение модели становится меньшей проблемой: если в каких-то состояниях модель плоха для планирования, политика может просто научиться её игнорировать.

• Пример агентов, наделённых таким «воображением», — I2A.

Ссылки на алгоритмы из таксономии

1. A2C / A3C (Asynchronous Advantage Actor-Critic): Mnih et al, 2016
2. PPO (Proximal Policy Optimization): Schulman et al, 2017
3. TRPO (Trust Region Policy Optimization): Schulman et al, 2015
4. DDPG (Deep Deterministic Policy Gradient): Lillicrap et al, 2015
5. TD3 (Twin Delayed DDPG): Fujimoto et al, 2018
6. SAC (Soft Actor-Critic): Haarnoja et al, 2018
7. DQN (Deep Q-Networks): Mnih et al, 2013
8. C51 (Categorical 51-Atom DQN): Bellemare et al, 2017
9. QR-DQN (Quantile Regression DQN): Dabney et al, 2017
10. HER (Hindsight Experience Replay): Andrychowicz et al, 2017
11. World Models: Ha and Schmidhuber, 2018
12. I2A (Imagination-Augmented Agents): Weber et al, 2017
13. MBMF (Model-Based RL with Model-Free Fine-Tuning): Nagabandi et al, 2017
14. MBVE (Model-Based Value Expansion): Feinberg et al, 2018
15. AlphaZero: Silver et al, 2017

---

Примечание переводчика: где на этой карте языковые модели

Карта нарисована в 2018 году, до RLHF для языковых моделей, но языковые модели на ней легко найти. RLHF в ChatGPT (урок 6.3.2) — это PPO, то есть ветвь «без модели → оптимизация политики». GRPO из DeepSeekMath и DeepSeek-R1 (урок 6.4.1) — та же ветвь: PPO без обученного критика $V_\phi$. Вычисления во время ответа с поиском по дереву и проверкой вариантов (урок 6.4.4) ближе к ветви «модель дана»: «модель среды» для текста — сама языковая модель, которая умеет продолжать любой префикс.

Словарик

English	Русский
model-free / model-based RL	RL без модели / с моделью среды
sample efficiency	эффективность использования данных
policy optimization	оптимизация политики
surrogate objective	суррогатная целевая функция
on-policy / off-policy	on-policy (данные текущей политики) / off-policy (любые данные)
model-predictive control (MPC)	управление с прогнозирующей моделью
expert iteration	экспертная итерация
Monte Carlo Tree Search	поиск по дереву Монте-Карло
deadly triad	«смертельная триада»

Назад: Часть 1. Дальше: Часть 3 — введение в оптимизацию политики.

Footnotes

1. Подробнее о том, как и почему методы Q-learning могут ломаться, см.: 1) классическую статью Цициклиса и ван Роя; 2) гораздо более свежий обзор Сепешвари (раздел 4.3.2); 3) главу 11 Саттона и Барто, особенно раздел 11.3 о «смертельной триаде» (deadly triad): аппроксимация функций, бутстрэп и off-policy данные вместе делают алгоритмы обучения ценности нестабильными. ↩