Марковские процессы (MDP)

Саттон и Барто: Temporal-Difference Learning

В 1988 году Ричард Саттон и Эндрю Барто опубликовали основополагающую работу о Temporal-Difference Learning - алгоритме обучения, который учится из разницы между предсказаниями в последовательных состояниях. Именно их MDP-формализм стал стандартом RL. Их учебник «Reinforcement Learning: An Introduction» (1998, 2nd ed. 2018) - до сих пор главная книга по RL.

Цели урока

• Понимать Марковское свойство и уметь проверять его для реальных задач
• Различать дискретные и непрерывные пространства состояний и действий
• Знать полное определение MDP как кортежа (S, A, P, R, gamma)
• Понимать роль discount factor и уметь выбирать его значение

2016. AlphaGo обыграл Ли Седоля 4:1. Задача: 10^170 состояний доски - больше атомов во Вселенной. Решение: MCTS + policy gradient на MDP-формализме. То же self-play обучает роботов Boston Dynamics ходить. DeepMind в 2022 применил MDP к управлению плазмой в токамаке. Один формализм - бесконечно разные задачи.

• **AlphaGo / AlphaZero (DeepMind)** - MDP с 10^170 состояний доски, PPO + MCTS решает задачу через self-play
• **Boston Dynamics Spot** - locomotion как непрерывный MDP: state = 20 углов суставов + скорости, действия = крутящие моменты
• **DeepMind Tokamak (2022)** - управление плазмой в термоядерном реакторе как MDP: 90 переменных состояния, 19 управляющих катушек
• **Netflix рекомендации** - последовательность выборов пользователя как MDP: state = история просмотров, action = показать фильм
• **OpenAI Dota 2** - OpenAI Five: multi-agent MDP с частичной наблюдаемостью, 20000 действий на шаг

Предварительные знания

• Введение в RL: агент и среда

Пространство состояний и Марковское свойство

2016. AlphaGo. На доске - позиция с 10^170 возможными продолжениями. AlphaGo не помнит все предыдущие ходы - только текущую позицию. И этого достаточно. Это интуиция **Марковского свойства**: будущее зависит только от настоящего, а не от истории, которая привела к нему.

**Марковское свойство:** P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, ..., s_0, a_0). Вероятность перехода зависит только от текущего состояния и действия - вся история уже закодирована в s_t.

**Пространство состояний S** - множество всех возможных ситуаций агента. Дискретное (конечное число клеток на доске) или непрерывное (позиция и скорость робота). Выбор определяет алгоритм: таблица vs нейронная сеть.

Если задача не Марковская, можно «починить» расширением состояния. Автопилот: стек из 4 последних кадров - скорость и направление теперь вычислимы. Покер: добавляем историю ставок. DeepMind так и делает в Atari - 4 последних кадра вместо одного.

**Дискретное vs непрерывное** - фундаментальное различие. Для дискретных состояний можно использовать Q-таблицы. Для непрерывных нужны аппроксиматоры - нейронные сети. Отсюда рождается Deep RL: DQN, PPO, SAC.

Пространство действий

**Пространство действий A** - множество всех действий, доступных агенту. Дискретные действия - Atari: 18 кнопок джойстика. Непрерывные - манипулятор Boston Dynamics: 20 степеней свободы, каждая с крутящим моментом в диапазоне [-100, 100] Нм. Размерность пространства действий определяет, какой алгоритм применим.

Важный приём - **action masking**: не все действия допустимы в каждом состоянии. В шахматах нельзя пойти конём на занятую своей фигурой клетку. Вместо штрафа за недопустимые действия - маскировать их. AlphaGo Zero использует маски для всех допустимых ходов при каждом MCTS-шаге.

**Размерность пространства действий** критически влияет на сложность обучения. CartPole с 2 действиями учится за минуты. Робот с 20 степенями свободы (непрерывными) - задача на порядки сложнее. Это **curse of dimensionality** в пространстве действий.

Для непрерывных действий нельзя использовать Q-таблицу - нужны алгоритмы вроде DDPG, SAC, PPO. Для дискретных - классические Q-learning и DQN работают отлично. SAC особенно хорош для робототехники: максимизирует и награду, и энтропию политики.

Функция переходов

**Функция переходов P(s'|s, a)** - вероятность попасть в состояние s', находясь в s и совершив действие a. Это «физика» среды. Манипулятор толкает объект: P(s'|s, a) определяется законами Ньютона. Финансовый рынок: P(s'|s, a) включает рыночный шум, реакцию других игроков, макроэкономические события.

Среды бывают **детерминированными** (одно действие всегда ведёт в одно и то же состояние) и **стохастическими** (результат случаен). Реальный мир почти всегда стохастичен: бросок мяча зависит от ветра, поворот руля - от состояния дороги, ответ пользователя - от его настроения.

Для маленьких дискретных сред функцию переходов можно записать как **матрицу переходов**. Для каждого действия a - матрица |S| x |S|, где элемент [i][j] = P(s_j | s_i, a).

Полная спецификация MDP - кортеж **(S, A, P, R, gamma)**: пространство состояний, пространство действий, функция переходов, функция наград и discount factor. Имея все 5 компонентов, задачу можно решить математически через dynamic programming.

**Model-based vs Model-free RL.** Если агент знает P(s'|s,a) - model-based подход. Если нет - model-free. Большинство практических алгоритмов RL (Q-learning, PPO, SAC) - model-free: учатся из опыта, не зная переходов. Реальный мир слишком сложен, чтобы его моделировать явно.

Discount factor и горизонт планирования

**Discount factor gamma ∈ [0, 1)** - не просто «нетерпеливость» агента. Строгое математическое обоснование: он гарантирует, что сумма наград **сходится** при бесконечных эпизодах. Без него сумму наград сравнить невозможно - обе уходят в бесконечность.

Gamma определяет **эффективный горизонт планирования** агента. Правило большого пальца: награды дальше 1/(1-gamma) шагов практически не учитываются.

**Формальное определение MDP:** кортеж (S, A, P, R, gamma), где S - множество состояний, A - множество действий, P: S x A x S → [0,1] - функция переходов, R: S x A → R - функция наград, gamma ∈ [0,1) - discount factor. Все задачи RL - от gridworld до управления термоядерным реактором - это MDP с пятью компонентами.

Gamma - гиперпараметр, который задаётся вручную. На практике начинают с gamma=0.99, а если обучение нестабильно - уменьшают. Слишком маленький gamma = близорукий агент (AlphaGo с gamma=0.5 не выиграет партии). Слишком большой - медленная сходимость.

Теперь есть полный язык для описания задач RL. Любая среда - от gridworld до управления термоядерным реактором (DeepMind и Tokamak, 2022) - это MDP с пятью компонентами. В следующем уроке - уравнения Беллмана для решения MDP.

Ключевые идеи

• **Марковское свойство** - будущее зависит только от текущего состояния, не от истории. AlphaGo не помнит все ходы - только текущую позицию
• **Пространства состояний и действий** бывают дискретными (Q-таблица) и непрерывными (нейросеть). Это определяет выбор алгоритма
• **Функция переходов P(s'|s,a)** описывает «физику» среды. Стохастичность - норма: реальный мир скользкий, как Frozen Lake
• **Discount factor gamma** - математическая необходимость для конечности суммы наград. Горизонт планирования ≈ 1/(1-gamma)
• **MDP = (S, A, P, R, gamma)** - полный язык для любой задачи RL: от gridworld до токамака
• Саттон и Барто (1988) заложили TD-Learning и MDP-формализм, без которого не было бы ни AlphaGo, ни ChatGPT RLHF
• Model-free RL не требует знания P(s'|s,a) - большинство production алгоритмов (PPO, SAC, DQN) model-free

Связанные темы

MDP - фундамент, на котором строятся все алгоритмы RL:

• Введение в RL — Интуитивные понятия агента, среды и награды, которые MDP формализует математически
• Bellman Equations — Уравнения для вычисления ценности состояний в MDP - мост от модели к решению
• Теория вероятностей — P(s'|s,a) - условная вероятность; дисконтированный return - математическое ожидание

Вопросы для размышления

• Опишите типичный день как MDP: что будет состояниями, действиями, переходами и наградами? Является ли эта задача Марковской?
• Почему gamma = 1.0 нельзя использовать для бесконечных эпизодов, но можно для конечных (например, шахматная партия)?
• Какие реальные задачи сложно формализовать как MDP? Подумайте о ситуациях, где определение состояния неоднозначно.

Связанные уроки

• rl-01 — Интуитивные понятия агента, среды и награды
• rl-03 — Уравнения Беллмана - следующий шаг после формализации MDP
• prob-03-conditional — P(s'|s,a) - условная вероятность из теорвера
• alg-21-dp — Dynamic programming решает MDP через уравнения Беллмана
• prob-04-bayes — Байесовский вывод используется в model-based RL