Управляемый Марковский процесс и Беллман

Марковский процесс принятия решений описывает не «умного агента», а повторяющийся выбор под неопределённостью. Уравнение Беллмана делает главный трюк динамического программирования: длинное будущее раскладывает на ближайший шаг и задачу того же типа. Дальше остаётся арифметика — и очень внимательный разбор того, что мы записали в состояние и в награду.

Курьер у развилки

Курьер едет к станции. На перекрёстке он может выбрать короткую улицу, которая иногда перекрыта, или длинный надёжный маршрут. Решение влияет не только на ближайшую минуту: от новой позиции зависят следующие варианты. Простая классификация «какую кнопку нажать» такого продолжения не видит — она отвечает на вопрос про одну картинку, а не про цепочку последствий.

Марковский процесс принятия решений, MDP, задаётся пятёркой

$$(\mathcal S,\mathcal A,P,R,\gamma).$$

Здесь $\mathcal S$ — множество состояний, $\mathcal A$ — множество действий, $P(s'\mid s,a)$ — вероятности переходов, $R(s,a,s')$ — награда, $0\le\gamma<1$ — коэффициент дисконтирования. Пятёрка — это вся модель мира: дальше в рассуждениях не появится ни одного факта, которого в ней нет.

Марковское условие утверждает:

$$\Pr(S_{t+1}\mid S_0,A_0,\ldots,S_t,A_t)=P(S_{t+1}\mid S_t,A_t).$$

Текущее состояние должно содержать всё прошлое, существенное для прогноза следующего шага. Если в «состоянии» записана только улица, но не время суток, хотя пробки зависят от часа, условие нарушено. Тогда надо расширить состояние, а не надеяться на красивую формулу.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Обратите внимание, что «хуже сейчас» и «хуже в итоге» разошлись уже на трёх состояниях. Первый шаг автобуса может привести на остановку — промежуточное положение, из которого до цели ещё далеко. Но даже с учётом этого риска автобус выигрывает почти четыре единицы. Именно такие пересчёты и делает уравнение Беллмана, только на тысячах состояний сразу.

Что обязано лежать в состоянии

Марковость — не свойство мира, а свойство описания. Один и тот же процесс может быть марковским в подробных координатах и немарковским в бедных. Скорость автомобиля не выводится из одной фотографии, но выводится из пары кадров; значит, состояние — пара кадров, а не кадр.

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

Стратегия превращает MDP в цепь Маркова

Стратегия, или policy, задаёт распределение действий:

$$\pi(a\mid s)=\Pr(A_t=a\mid S_t=s).$$

Детерминированная стратегия выбирает одно действие, стохастическая смешивает их. После фиксации $\pi$ управляемый процесс превращается в обычную цепь Маркова — ту самую, чьи стационарные распределения мы гоняли в уроке 67, — с переходами

$$P^\pi(s'\mid s)=\sum_a\pi(a\mid s)\,P(s'\mid s,a).$$

Это ключ ко всей конструкции: управление — это выбор одной цепи Маркова из семейства, занумерованного стратегиями. Задача «найти лучшую стратегию» — задача о выборе среди цепей, а не о поиске одной удачной траектории.

Цель — максимизировать ожидаемый дисконтированный возврат

$$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots=\sum_{k\ge0}\gamma^kR_{t+k+1}.$$

Ряд сходится, когда награды ограничены: при $|R|\le R_{\max}$ имеем $|G_t|\le R_{\max}/(1-\gamma)$. Дисконт нужен не только ради сходимости; он задаёт горизонт внимания.

Дисконт: как далеко мы смотрим

При $\gamma=0$ агент видит только ближайшую награду. При $\gamma$, близком к единице, далёкие последствия значимы. Эффективный горизонт имеет порядок

$$\sum_{k\ge0}\gamma^k=\frac1{1-\gamma},$$

то есть при $\gamma=0{,}9$ около 10 шагов, при $\gamma=0{,}99$ — около 100. Вес события через десять шагов равен $0{,}9^{10}=0{,}349$ при $\gamma=0{,}9$ и всего $0{,}5^{10}=0{,}00098$ при $\gamma=0{,}5$: в тысячу раз меньше внимания к тому же самому будущему.

Смена $\gamma$ меняет не точность решения, а саму постановку. Возьмём выбор из двух маршрутов. Рискованный рывок заканчивается за один шаг: с вероятностью $0{,}75$ награда $+10$, с вероятностью $0{,}25$ авария и $-20$. Его ценность не зависит от дисконта вовсе:

$$Q_{\text{рывок}}=0{,}75\cdot10+0{,}25\cdot(-20)=2{,}5.$$

Надёжный объезд — три шага по $-0{,}5$, а затем $+10$:

$$Q_{\text{объезд}}(\gamma)=-0{,}5\,(1+\gamma+\gamma^2)+10\gamma^3.$$

При $\gamma=0{,}5$ это $0{,}375$ — объезд хуже рулетки. При $\gamma=0{,}9$ это $5{,}935$ — объезд лучше более чем вдвое. Граница проходит по корню уравнения $Q_{\text{объезд}}(\gamma)=2{,}5$, то есть при $\gamma^*=0{,}712$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Две функции ценности

Связь между ними прямая:

$$V^\pi(s)=\sum_a\pi(a\mid s)\,Q^\pi(s,a),$$ $$Q^\pi(s,a)=\sum_{s'}P(s'\mid s,a)\bigl[R(s,a,s')+\gamma V^\pi(s')\bigr].$$

Функция $Q$ удобнее для действия: чтобы выбрать ход, не нужно знать модель переходов, достаточно сравнить числа. Функция $V$ компактнее: у неё $|\mathcal S|$ значений против $|\mathcal S||\mathcal A|$. Этот обмен ещё всплывёт в уроке 71, где $Q$ обучают прямо по наблюдённым переходам.

Уравнение Беллмана как рекурсия

Разделим возврат на первый шаг и остаток:

$$G_t=R_{t+1}+\gamma G_{t+1}.$$

Возьмём условное математическое ожидание и получим для фиксированной стратегии

$$V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a) \bigl[R(s,a,s')+\gamma V^\pi(s')\bigr].$$

Оптимальная ценность выбирает лучшее действие:

$$V^*(s)=\max_a\sum_{s'}P(s'\mid s,a)\bigl[R(s,a,s')+\gamma V^*(s')\bigr].$$

Правая часть содержит ту же функцию $V^*$ в следующем состоянии. Это и есть принцип оптимальности: хвост оптимального плана сам обязан быть оптимален для достигнутого состояния. Длинный план исчез, остались уравнения на числа.

Почему итерация сходится: сжатие

Доказательство укладывается в три строки. Для каждого $s$

$$|(TV)(s)-(TW)(s)|\le\max_a\Bigl|\sum_{s'}P(s'\mid s,a)\,\gamma\,[V(s')-W(s')]\Bigr| \le\gamma\lVert V-W\rVert_\infty,$$

потому что $|\max_ax_a-\max_ay_a|\le\max_a|x_a-y_a|$, вероятности неотрицательны и в сумме дают единицу. Остальное — теорема Банаха о сжимающих отображениях.

Гарантия $\gamma$ — верхняя оценка, а не предсказание. На нашей сетке фактическое отношение соседних ошибок оказалось $0{,}33$ при $\gamma=0{,}7$, $0{,}43$ при $\gamma=0{,}9$ и $0{,}92$ при $\gamma=0{,}99$: реальное сжатие быстрее обещанного, потому что часть вероятностной массы утекает в терминальные состояния и обратно не возвращается.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Итерация ценности: волна от цели

Начнём с произвольного $V_0$, часто нулевого, и повторим

$$V_{k+1}(s)=\max_a\sum_{s'}P(s'\mid s,a)\bigl[R(s,a,s')+\gamma V_k(s')\bigr].$$

После сходимости извлечём жадную стратегию:

$$\pi^*(s)\in\arg\max_a\sum_{s'}P(s'\mid s,a)\bigl[R(s,a,s')+\gamma V^*(s')\bigr].$$

На сетке $5\times5$ с целью $+10$, ямой $-8$, тремя стенами и боковым сносом $0{,}1$ картина буквально видна: после одной итерации ненулевую ценность имеют 2 клетки, после двух — 4, и волна расходится ровно на клетку за шаг. Информация о цели распространяется со скоростью один переход за применение оператора.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Лаборатория: сетка, дисконт и снос

Сначала сделайте движение почти детерминированным и ползунком $k$ прогоните итерацию по шагам: волна ценности расходится от цели, пока не накроет всю сетку. Затем меняйте $\gamma$ и смотрите, когда агент выбирает короткую дорогу рядом с ямой, а когда — длинный безопасный обход. Наконец, увеличьте снос: оптимальный маршрут отойдёт от ямы на дополнительную клетку, хотя ни одна награда не изменилась.

Сравните цвет ценности и стрелки стратегии. Соседние состояния могут иметь близкие $V^*$, но разные лучшие действия. И наоборот, одна стрелка не сообщает, насколько выбор уверен: об этом говорит разрыв между лучшим и вторым $Q$, который показывает третий режим. Щелчок по свободной клетке переносит яму — стратегия перестраивается не только рядом с новой ямой, но и в дальних углах.

Разрыв между лучшим и вторым действием

Формально стратегия — это argmax, и любая ничья разрешается произвольно. На практике важно, насколько уверенно взят максимум. Определим разрыв

$$\Delta(s)=\max_aQ^*(s,a)-\max_{a\ne a^*(s)}Q^*(s,a).$$

В нашей сетке минимальный разрыв равен $0{,}0049$ — в клетке четвёртой строки и второго столбца два действия почти равноценны. Стрелка там нарисована уверенно, но её направление держится на пяти тысячных.

Реальные данные: сутки одной станции велопроката

Абстрактная сетка удобна, но проверять принцип оптимальности лучше на данных. Возьмём тот же реальный журнал велопроката, что и в уроке 50: 17 379 часовых записей за два года. Средний спрос по часам — знакомый двугорбый профиль: в 4 утра в среднем $6{,}35$ поездки в час по городу, в 8 утра — $359{,}01$, а максимум приходится на 17 часов, $461{,}45$.

Смасштабируем город до одной станции делением на 80 и объявим модель: в час $h$ число желающих распределено по Пуассону со средним $\lambda_h$, где $\lambda_{17}=5{,}77$, а $\lambda_4=0{,}079$. Пуассоновская форма — наше модельное допущение; реальны здесь именно $\lambda_h$, снятые с журнала. Станция вмещает 12 велосипедов, каждая состоявшаяся поездка приносит 3 условные единицы, фургон привозит до 4 велосипедов за час по цене $1{,}2$ за штуку. Уехавший велосипед на станцию не возвращается — это упрощение, оговорим его честно.

Состояние — пара «час, число велосипедов на станции», действие — сколько привезти, награда — выручка минус стоимость довоза. Горизонт конечный, 24 часа, поэтому рекурсия Беллмана считается обратным ходом:

$$V_{24}(q)=0,$$ $$V_h(q)=\max_{a}\Bigl\{-c\,a+\sum_{d\ge0}p_h(d) \bigl[3\min(d,q+a)+V_{h+1}\bigl(q+a-\min(d,q+a)\bigr)\bigr]\Bigr\}.$$

Никакого $\gamma$ здесь нет: горизонт конечен и задан сутками. Это важный частный случай — динамическое программирование работает и без дисконта, если будущее кончается.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Ночная строка — самая поучительная. В 2 часа спрос почти нулевой, немедленная награда от довоза отрицательна: платим $1{,}2$ и почти ничего не зарабатываем. Тем не менее оптимальный план возит. Причина целиком в слагаемом $V_{h+1}$: заполненная ночью станция окупится утренним пиком. Никакой отдельной «эвристики запаса» мы не писали; она вывелась из уравнения.

Жадность на текущий час против плана

Сравним четыре стратегии на одинаковом спросе, начиная с 6 велосипедов в полночь. Ожидаемая суточная прибыль считается точно, тем же обратным ходом, без симуляций.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Жадная стратегия проигрывает не из-за плохой арифметики: каждое её решение оптимально для своего часа. Она проигрывает потому, что оптимизирует не ту величину. Заменить $V_{h+1}$ нулём — значит объявить, что после текущего часа мир кончается; при таком допущении ночной довоз действительно бессмыслен.

Модель известна не всегда

Итерация ценности предполагает известные $P$ и $R$. В реальном управлении переходы приходится оценивать из данных или узнавать опытом. Model-based подход строит модель и решает уравнение, model-free сразу оценивает ценность или стратегию; Q-learning заменит точное ожидание по $P$ наблюдённым переходом.

Оценка $\widehat P$ по короткому журналу шумна, а стратегия — это argmax, который шум легко переворачивает. Проведём эксперимент: для каждой пары $(s,a)$ на сетке сгенерируем по $n$ переходов, решим уравнение Беллмана для $\widehat P$ и сравним полученные действия с точным ответом. При $n=5$ различаются 27,5 % клеток, при $n=20$ — 17,5 %, при $n=300$ — всё ещё 9,7 %.

Остаточные проценты не означают, что при $n=300$ агент плох: почти все расхождения приходятся на клетки с малым $\Delta$, где цена ошибки того же порядка, что и разрыв. Поэтому карта стабильности стратегии информативнее одной стрелки: рядом с частотой переключения надо показывать и абсолютный разрыв ценностей.

Полезно разделить неопределённость на две части. Случайный боковой снос — aleatoric: он останется даже при бесконечном журнале, и стратегия может им только управлять. Незнание вероятности сноса — epistemic: оно сужается с данными, и ради него имеет смысл собирать наблюдения. Первое — свойство мира, второе — свойство нашего незнания; смешивать их в одном числе вредно, о чём говорил и урок о доверительных интервалах.

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

Награда не обязана совпадать с целью

Разработчик выбирает $R$, но надеется получить полезное поведение. Если курьеру начислять $+1$ за скорость на каждом участке, агент может ездить кругами по быстрой магистрали. Если роботу-пылесосу платить за собранную пыль, он может рассыпать её снова. Такое использование дыр в заданной метрике называют reward hacking, и это не сбой алгоритма, а его добросовестная работа.

Полезно различать:

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

Существует безопасный способ подсказывать. Potential-based shaping вида

$$R'(s,a,s')=R(s,a,s')+\gamma\Phi(s')-\Phi(s)$$

при стандартных условиях сохраняет множество оптимальных стратегий: телескопическая сумма добавок по траектории равна $\gamma^T\Phi(s_T)-\Phi(s_0)$ и не зависит от того, как именно агент шёл. Проверим численно: на нашей сетке с $\Phi=V^*$ стратегия совпала с исходной во всех 20 нетерминальных клетках, а безобидный на вид бонус $+2$ за действие «вправо» изменил её в 15 клетках из 20.

Дынкин: момент остановки и наименьшая мажоранта

У уравнения Беллмана есть близкий родственник — задача об оптимальной остановке. Процесс идёт сам, управлять можно только одним: решить, когда сказать «стоп» и забрать выигрыш $g(s)$. Ценность

$$V(s)=\sup_{\tau}\mathbb E_s\bigl[g(S_\tau)\bigr]$$

берётся по всем моментам остановки $\tau$ — правилам, которые смотрят только в прошлое. Уравнение оптимальности принимает вид

$$V(s)=\max\bigl\{g(s),\ \mathbb E_s[V(S_1)]\bigr\}:$$

либо забрать сейчас, либо подождать один шаг и оказаться в задаче того же типа.

Общую теорию таких задач для марковских процессов построил Евгений Борисович Дынкин — ученик Колмогорова, автор фундаментальной монографии «Марковские процессы» (1963). Ему принадлежат понятие характеристического оператора и формула, связывающая математическое ожидание в момент остановки с генератором процесса. Именно эта техника позволила говорить об оптимальном управлении непрерывным процессом так же спокойно, как мы говорим о таблице $5\times5$.

Формулировка стоит расшифровки. «Мажоранта» — функция не меньше выигрыша: право подождать никогда не хуже, чем его отсутствие. «Эксцессивная» — не возрастающая в среднем вдоль процесса, аналог условия $V\ge\mathbb E[V(S_1)]$. «Наименьшая» — ровно то же, что неподвижная точка оператора Беллмана, к которой сходятся итерации сверху. Три разных языка — сжимающее отображение, наименьшая мажоранта и принцип оптимальности — описывают один и тот же объект.

Описанная Ховардом policy iteration — второй классический алгоритм наряду с итерацией ценности. Она делает более дорогие шаги (решение линейной системы), но их обычно нужно единицы, и в конечном MDP она завершается за конечное число итераций: стратегий конечное число, а каждая следующая строго лучше предыдущей.

Работа Шепли вышла на четыре года раньше книги Беллмана и содержала, по сути, ту же итерацию — только для игры двух лиц. MDP получается из неё, если у второго игрока отобрать выбор и оставить природу с фиксированными вероятностями. Эту связь мы уже видели в уроке 26, где минимаксная постановка описывала состязание двух оптимизаторов.

Цена состояния: почему таблица не всегда работает

Табличная итерация требует порядка $|\mathcal S|^2|\mathcal A|$ операций на шаг для плотных переходов и заметно меньше для разреженных. Пока состояний тысячи, это ничто. Но состояние управления зданием — это температура, погода, заряд, прогноз; сетка по десяти переменным с десятью уровнями каждая даёт

$$|\mathcal S|=10^{10}$$

ячеек, и ни память, ни время не выдержат. Беллман называл это проклятием размерности — и то же проклятие мы считали в уроке 60, когда смотрели, как пустеет шар внутри куба.

Выход тот же, что во всём курсе: заменить таблицу параметрической функцией. Вместо $|\mathcal S|$ чисел храним веса $w$ и приближаем $V_w(s)\approx V^*(s)$. Уравнение Беллмана превращается в задачу минимизации невязки

$$L(w)=\mathbb E_{s}\bigl[\bigl(V_w(s)-(TV_w)(s)\bigr)^2\bigr],$$

и мы возвращаемся к градиентному спуску — с той существенной разницей, что цель $TV_w$ сама зависит от $w$ и во время обучения движется. Разбираться с этим будет урок 71.

Что именно оптимизировало уравнение

MDP начинается не с нейросети, а с выбора состояния, действия, переходов, награды и горизонта. Беллмановская рекурсия превращает длинный план в локальное уравнение; сжатие гарантирует сходимость при $\gamma<1$; жадность по сошедшейся ценности даёт оптимальную стратегию сразу во всех состояниях. На реальном профиле спроса эта машина обыграла жадность на 21,9 %, не зная о велосипедах ничего, кроме таблицы вероятностей.

Но математически оптимальная стратегия оптимальна лишь для записанной модели. Марковость состояния, честность вероятностей, соответствие награды настоящей цели и разумность горизонта — четыре допущения, которые уравнение принимает без проверки. Проверять их — часть задачи, а не подготовка к ней. Формулу мы решили; осталось убедиться, что решали ту.

Задачи