Автоматы и сознание
Иерархия целей - Options Framework
Цели урока
- Понимать почему плоский RL не справляется с задачами длинного горизонта
- Знать формализм Options: initiation set, внутренняя политика, termination condition
- Разбираться в Semi-MDP и как дисконтирование работает для options разной длины
- Видеть как Feudal RL и World Models решают задачу иерархического планирования
Предварительные знания
- MDP: состояния, действия, политика, функция ценности
- POMDP: частичная наблюдаемость и belief state
- Понятие дисконтирования gamma в RL
Плоский RL при горизонте 1000 шагов имеет 10^1000 траекторий - больше атомов во Вселенной. Единственный выход - иерархия: разбить задачу на options, каждый из которых решает свой кусок.
- **AlphaGo (2016)** - 1202 GPU, 40 дней обучения на 30 млн партий. Даже так пространство состояний 10^170 требовало умных эвристик
- **Claude Code** - иерархия: цель пользователя -> options (explore/fix/implement) -> инструменты (Glob/Read/Edit/Bash)
- **Robotics (Boston Dynamics)** - иерархия: задание (принести предмет) -> локомоция (как идти) -> моторные команды
- **Видеоигры (AlphaStar, OpenAI Five)** - тысячи шагов в матче, только иерархические методы справились
- **DeepMind Feudal Networks (2017)** - в 3 раза быстрее плоского A3C на задачах с разреженными наградами
Options Framework - Саттон, Прекуп, Сингх 1999
Работа 'Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning' формализовала идею макро-действий. До этого иерархические подходы существовали, но без строгой математики. Options дали единый язык: initiation set, политика, termination - и доказали что любой MDP можно решить через options без потери оптимальности. Саттон - автор главного учебника по RL (Sutton & Barto), который бесплатно доступен онлайн.
Почему плоский RL ломается на длинных задачах
**AlphaGo (2016) выиграл у Ли Седоля, но потребовал 1202 GPU и 40 дней обучения на 30 миллионах партий.** Игра в го - 250 ходов в среднем, пространство состояний 10^170. Когда горизонт планирования достигает тысяч шагов, число возможных траекторий становится 10^1000 - больше атомов во Вселенной. Плоский RL здесь не работает. Нужна иерархия.
**Проклятие горизонта:** при горизонте T шагов и алфавите действий размером |A| число возможных траекторий равно |A|^T. Для T=1000 и |A|=10 это 10^1000 - поиск в таком пространстве невозможен ни при каких вычислительных ресурсах.
Что ломается при плоском MDP
| Проблема | Почему возникает | Пример |
|---|---|---|
| Разреженные награды | Победа только в конце - тысячи шагов без сигнала | Собрать ресурсы, построить базу, победить - награда одна |
| Взрыв состояний | Позиция x ресурсы x здания x враги = миллионы | Игровой агент в Minecraft |
| Нет переноса навыков | Каждая задача обучается с нуля | Навык 'открыть дверь' нельзя переиспользовать |
| Долгое обучение | Агент не знает промежуточных целей | AlphaGo: 40 дней на 1202 GPU |
Решение - разбить задачу на уровни. Верхний уровень планирует на абстрактном уровне ('открой дверь'), нижний выполняет примитивные действия ('напрягите бицепс, поверните руку'). Каждый уровень работает с коротким горизонтом.
Увеличение вычислительных ресурсов решит проблему длинного горизонта
10^1000 превышает число атомов во Вселенной - никакие ресурсы не помогут без изменения подхода
Экспоненциальный взрыв не побеждается линейным увеличением ресурсов. Единственный выход - уменьшить эффективный горизонт через иерархию, сжав 1000 шагов до 10 options.
Почему число траекторий при T=1000 и |A|=10 равно 10^1000?
Options Framework - формализм макро-действий
**Ричард Саттон в 1999 году предложил формализм Options - и это стало основой всего Hierarchical RL.** Работа 'Between MDPs and semi-MDPs' дала агентам понятие 'навыка': последовательности примитивных действий, которую можно вызывать как одно макро-действие. Вместо 1000 шагов - 10 options.
**Option** - это тройка (I, pi, beta): initiation set I (в каких состояниях можно начать), внутренняя политика pi (что делать внутри option), termination condition beta (вероятность завершения в каждом состоянии).
Компоненты option на примере
| Компонент | Что это | Пример: option 'исправь баг' |
|---|---|---|
| I - initiation set | Условие старта option | Пользователь сообщил об ошибке |
| pi - внутренняя политика | Что делать шаг за шагом | Read файл -> Edit код -> Bash тест |
| beta - termination | P(остановиться | текущее состояние) | beta=1.0 когда тесты прошли, beta=0.0 иначе |
Иерархия options в Claude Code
Options - это просто функции, разбитые на подфункции (декомпозиция кода)
Options - формальная модель временных абстракций со своей политикой и условием завершения
Обычная декомпозиция кода - статическая. Option - динамическая: он сам решает когда продолжать, а когда останавливаться (beta). Именно это позволяет верхнему уровню планировать без знания деталей нижнего.
Зачем option нужен компонент termination (beta)?
Semi-MDP и планирование в воображении
**Обычный MDP предполагает что каждое действие занимает ровно один шаг. Options ломают это допущение.** Option 'explore codebase' занимает 5-20 шагов, option 'fix bug' - 3-50. Когда действия длятся разное время, MDP превращается в Semi-MDP (SMDP) - и математика меняется.
**Semi-MDP (SMDP)** - расширение MDP где действия (options) занимают случайное число шагов k. Q-значение option omega в состоянии s: Q(s, omega) = E[сумма(gamma^t * r_t, t=0..k-1) + gamma^k * Q(s_k, pi(s_k))]. Ключевое: дисконт gamma^k накапливается за всё время option.
| Параметр | Смысл | Эффект на обучение |
|---|---|---|
| k - длина option | Случайное число шагов | Чем длиннее option, тем сильнее дисконтирование |
| gamma^k - накопленный дисконт | Будущие награды обесцениваются | При gamma=0.9 и k=10: gamma^10 = 0.35 |
| r_t - награды внутри | Каждый шаг внутри option приносит r_t | Option суммирует все промежуточные награды |
| s_k - финальное состояние | Состояние после завершения option | С него начинается следующий option |
World Model - планирование без реальных действий
Если у агента есть модель мира (функция предсказания следующего состояния и награды), он может 'проигрывать' options в воображении до того как выбрать лучший. Это называется model-based RL - и именно так работает стратегическое планирование у людей.
| Подход | Как принимает решения | Плюсы / Минусы |
|---|---|---|
| Model-Free RL | Состояние -> политика -> действие (напрямую) | Быстро, но не планирует наперёд |
| Model-Based RL | Состояние -> воображение N вариантов -> лучший -> действие | Планирует, но нужна точная модель мира |
| Dyna-Q (Sutton) | Реальный опыт + симулированный опыт из модели | Баланс: планирование + real-world exploration |
Option A: 10 шагов, суммарная награда +50. Option B: 3 шага, суммарная награда +20. gamma=0.9. Какой выгоднее при условии что награда приходит в конце?
Feudal RL и обнаружение options
**DeepMind в 2017 году показал что феодальная иерархия обучается в 3 раза быстрее плоского A3C на задачах с разреженными наградами.** Feudal Networks (FuN) разделяют агента на Manager и Worker: менеджер ставит цели на длинном горизонте, работник выполняет примитивные действия. Это разделение труда делает каждый уровень проще.
Три способа создать options
| Подход | Как получить options | Когда применять |
|---|---|---|
| Предопределённые (hand-crafted) | Человек задаёт options вручную | Когда структура задачи известна заранее - Claude Code, роботика |
| Option Discovery (subgoal) | Находить 'бутылочные горлышки' в графе состояний | Когда структура неизвестна - игры, навигация |
| Feudal Networks (FuN) | Manager учит options неявно через цели | Когда нет возможности задать options вручную |
**Claude Code = предопределённая иерархия:** цель пользователя (уровень 3) -> options: explore/fix/implement (уровень 2) -> инструменты: Glob/Read/Edit/Bash (уровень 1). Options заданы разработчиками явно - это позволяет агенту сразу использовать правильные навыки без обучения с нуля.
Иерархия в экосистеме
Связь с другими темами курса
- MDP — Options работают поверх MDP, превращая его в Semi-MDP
- POMDP — В частичной наблюдаемости options помогают действовать на более абстрактном уровне
- Attention и Memory — World Model требует памяти о прошлых состояниях - тема следующего урока
World Model должна быть точной копией реального мира для планирования
Даже приближённая модель полезна - она помогает отсеять явно плохие варианты
Идеальная модель мира невозможна и не нужна. Цель - сократить пространство поиска, отбросив плохие options заранее. Мозг человека тоже работает с 'размытой' моделью реальности и при этом принимает хорошие решения.
Почему в Feudal RL Worker получает внутреннюю награду, а не внешнюю?
Ключевые идеи
- **Плоский RL** деградирует на длинных задачах - пространство состояний растёт экспоненциально, сигнал reward редкий
- **Options Framework** - формализм макро-действий: option = политика + условие прекращения + начальное множество состояний
- **Semi-MDP** - временная абстракция, где агент действует на уровне опций с переменной длительностью, а не примитивных шагов
- **World Model** в воображении позволяет планировать через options без реального взаимодействия со средой
- **Feudal RL** - иерархия менеджер/работник: менеджер ставит подцели, работник их достигает; options обнаруживаются автоматически
- **Temporal abstraction** - ключевой принцип: агент на разных уровнях иерархии работает с разным временным масштабом
Вопросы для размышления
- Какие неявные 'options' используются при написании кода ежедневно - и как это влияет на скорость работы по сравнению с разработчиком, который действует только примитивными шагами?