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

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

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

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

Марковский процесс принятия решений, 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).

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

Дерево переходов курьера с действиями, вероятностями, наградами и объединёнными состояниями — Рис. 69.1. Один выбор разворачивает дерево будущего
Квадраты обозначают состояния, цветные стрелки — действия, подписи на ветвях — $P(s'\mid s,a)$ и немедленные награды. Одинаковые состояния на втором уровне объединены: MDP хранит состояние, а не всю историю пути.

Стратегия и случайность

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

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

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

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.

При $\gamma=0$ агент видит только ближайшую награду. При $\gamma$ близком к единице далёкие последствия значимы. Эффективный горизонт имеет порядок $1/(1-\gamma)$ : при $\gamma=0{,}9$ около 10 шагов, при $0{,}99$ — около 100.

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

Разделим возврат:

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) \left[R(s,a,s')+\gamma V^\pi(s')\right].

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

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

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

Итерация ценности

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

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

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

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

Одна итерация табличного алгоритма требует порядка $|\mathcal S|^2|\mathcal A|$ операций для плотных переходов и меньше для разреженных. Ошибка после $k$ шагов убывает геометрически, но при $\gamma\approx1$ медленно.

Последовательность тепловых карт ценности на сетке и стрелки оптимальной стратегии — Рис. 69.2. Как ценность распространяется от цели
Панели соответствуют итерациям $k=0,1,2,8$ . Зелёная клетка даёт награду, красные клетки опасны, стены непроходимы. Волна ненулевой ценности расходится на один шаг за итерацию; итоговые стрелки показывают policy, а не одну траекторию.

Лаборатория городских маршрутов

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

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

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

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

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

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

Potential-based shaping вида

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

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

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

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

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

Реальный кейс: управление энергией здания

CityLearn предоставляет симуляторы зданий с нагрузкой, солнечной генерацией, аккумуляторами и погодой. Состояние может включать час, температуру, прогноз нагрузки и заряд батареи. Действие — зарядить, разрядить или не трогать накопитель. Награда штрафует пиковое потребление, стоимость и выбросы.

Перед обучением нужен простой baseline: не использовать батарею; заряжать ночью по фиксированному расписанию; жадно покрывать текущую нагрузку. Сложный агент должен выигрывать у них на одинаковых погодных периодах.

Оценивать только среднюю награду мало. Нужны пиковая мощность, стоимость, число нарушений ограничений батареи и устойчивость к другому году погоды. Временной split обязателен: будущее лето не должно попадать в обучающий период.

Суточные графики нагрузки, тарифа, заряда батареи и действий двух стратегий — Рис. 69.3. Состояние батареи связывает часы
На общей временной оси показаны потребление дома, тариф и state of charge. Серая стратегия реагирует только на текущую цену, синяя сохраняет заряд перед вечерним пиком. Заштрихованная область отмечает ограничение мощности; фигура объясняет, почему локально дешёвое действие может ухудшить возврат.

Мини-исследование: неопределённость переходов

Итерация ценности использует точные вероятности, но оценка $P$ по малому журналу шумна. Возьмите сетку лаборатории и для каждого действия сгенерируйте лишь 20 переходов. Получите empirical $\widehat P$ , вычислите policy, затем повторите сбор 200 раз. Для каждой клетки отметьте, как часто выбиралось каждое действие.

Карта стабильности policy информативнее одной стрелки. В состоянии, где два $Q$ различаются на $0{,}001$ , небольшая ошибка переходов переворачивает выбор почти без потери возврата. В другом состоянии неправильное действие может быть редким, но дорогим. Поэтому рядом с частотой переключения покажите regret относительно policy на истинном $P$ .

Добавьте pessimistic оценку: из ожидаемого результата действия вычитайте бонус неопределённости, зависящий от числа наблюдений. Агент станет обходить малоизученные рёбра. Это разумно в safety-задаче и слишком осторожно в исследовательской игре. Сравните оба режима при двух ценах аварии.

Наконец, проверьте simulator mismatch: уменьшите фактическую эффективность батареи на 10%, не переобучая policy. Такой stress test связывает MDP с domain shift. Если стратегия выигрывает только при точной модели, вывод должен звучать как результат симуляции, а не готовое управление зданием.

Разделите uncertainty на aleatoric и epistemic. Случайный боковой снос останется даже при бесконечном журнале; неизвестная его вероятность сужается с данными. В первой ситуации policy управляет риском, во второй может собирать информацию. Нарисуйте для одного состояния posterior вероятности перехода и induced distribution разности $Q(a_1)-Q(a_2)$ .

Если интервал разности пересекает ноль, заявлять единственное лучшее действие рано. Можно выбрать консервативное, запросить ещё данные или показать обе policy. Такой вывод полезнее стрелки без масштаба уверенности.

На карте подпишите и абсолютный разрыв ценностей: частое переключение между почти равными действиями не является практической катастрофой.

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

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

Задачи

3баллов

Состояния равны дом, остановка, школа, причём школа терминальна и имеет ценность 0. Из дома действие пешком всегда ведёт в школу с наградой $-8$ , а автобус с вероятностью $0{,}7$ ведёт в школу с наградой $-3$ и с вероятностью $0{,}3$ на остановку с наградой $-1$ . С остановки единственное действие детерминированно ведёт в школу с наградой $-6$ . При $\gamma=0{,}9$ вычислите $Q(s,a)=\sum_{s'}p(s'|s,a)[r+\gamma V(s')]$ для двух действий из дома и выберите лучшее. Случайности в расчёте нет; ответ нужен в единицах награды с точностью $10^{-3}$ .

4баллов

Для конечного MDP с $\gamma=0{,}9$ рассмотрите оптимальный оператор Беллмана

(TV)(s)=\max_a\sum_{s'}p(s'|s,a) \bigl[r(s,a,s')+0{,}9V(s')\bigr].

Докажите $\lVert TV-TW\rVert_\infty\le0{,}9\lVert V-W\rVert_\infty$ , используя $|\max_a x_a-\max_a y_a|\le\max_a|x_a-y_a|$ и $\sum_{s'}p(s'|s,a)=1$ . Начальный вектор, seed и единицы измерения для доказательства не нужны; зачёт требует пройти все переходы неравенства и объяснить единственность неподвижной точки.

5баллов

В сетке $4\times4$ строки нумеруются сверху вниз 1–4, столбцы слева направо 1–4. Клетка $(1,4)$ терминальна: вход в неё даёт $+10$ ; вход в опасную $(2,3)$ даёт $-8$ и не завершает эпизод; любой другой переход даёт $-1$ . Действия U,R,D,L: выбранное выполняется с вероятностью $0{,}8$ , а каждое перпендикулярное ему с вероятностью $0{,}1$ ; выход за границу оставляет агента на месте. Используйте $\gamma=0{,}9$ , $V_0(s)=0$ и $V_{k+1}=TV_k$ ; остановитесь при $\lVert V_{k+1}-V_k\rVert_\infty<10^{-6}$ . Ничьи policy разрешайте порядком U,R,D,L, случайности нет. Зачёт требует карту $V$ , policy, последнюю невязку и разрыв между лучшим и вторым $Q$ в каждой нетерминальной клетке.

6баллов

Сконструируйте конечный MDP из 3–6 состояний, не более трёх действий на состояние и наград в диапазоне $[-10,10]$ . Полностью перечислите $p(s'|s,a)$ и $r(s,a,s')$ , задайте одно терминальное состояние с ценностью 0 и добейтесь различия оптимальных действий хотя бы в двух состояниях между $\gamma=0{,}5$ и $\gamma=0{,}95$ . Для обеих задач начните value iteration с $V_0=0$ , остановитесь при $\lVert TV_k-V_k\rVert_\infty<10^{-10}$ и разрешайте ничьи по номеру действия. Случайности нет; зачёт требует две таблицы $V,Q,\pi$ , невязки и объяснение различия через короткие и отложенные награды.

7баллов

Рассмотрите сутки $h=0,\ldots,23$ с часовой нагрузкой $L_h=1{,}2+0{,}4\,\mathbf1_{7\le h\le8} +1{,}0\,\mathbf1_{17\le h\le21}$ кВт·ч и тарифом $c_h=4$ руб/кВт·ч при $0\le h\le5$ , $12$ при $17\le h\le21$ и $7$ в остальные часы. Заряд батареи $q_h\in\{0,0{,}5,\ldots,6\}$ кВт·ч, $q_0=q_{24}=3$ кВт·ч; действие $a_h=q_{h+1}-q_h\in\{-2,-1{,}5,\ldots,2\}$ кВт·ч. При одностороннем КПД $\eta=0{,}9$ покупка из сети равна $g_h=L_h+a_h/\eta$ для $a_h\ge0$ и $g_h=L_h+\eta a_h$ для $a_h<0$ ; допустимы только $0\le q_{h+1}\le6$ и $g_h\ge0$ . Минимизируйте $\sum_hc_hg_h$ точным обратным динамическим программированием, разрешая ничьи меньшим $a_h$ . Случайности нет. Сравните рублёвую стоимость с $a_h=0$ и следующим полностью заданным жадным baseline. Начиная с $q_0=3$ , просматривайте часы по порядку: в 0–5 выбирайте наибольшее допустимое $a_h$ ; в 6–16 полагайте $a_h=0$ ; в 17–21 выбирайте наименьшее допустимое $a_h$ ; в 22–23 выбирайте допустимое действие с наименьшим $|q_{h+1}-3|$ . Для последнего критерия ничью разрешайте меньшим $a_h$ , а на часе 23 отбрасывайте все действия, кроме дающих $q_{24}=3$ . «Допустимое» во всех случаях означает принадлежность заданной сетке, $0\le q_{h+1}\le6$ , $g_h\ge0$ и возможность вернуться к $q_{24}=3$ оставшимися действиями величины не более 2. Затем умножьте $L_h$ в 17–21 на $1{,}15$ и заново вычислите оптимальную и жадную policy. Зачёт требует четыре последовательности действий, их стоимости в рублях, проверку $q_{24}=3$ и число изменившихся оптимальных действий.