Марковский процесс принятия решений (MDP): кортеж и решение

Марковский процесс принятия решений (MDP, Markov Decision Process) - это математический каркас, в котором описывают задачи последовательного принятия решений в случайной среде. Агент находится в одном из состояний, выбирает действие, среда отвечает наградой и переводит агента в новое состояние - и так шаг за шагом. На MDP стоит вся теория обучения с подкреплением, динамическое программирование Беллмана и значительная часть исследования операций. Ниже разберём, из чего состоит кортеж MDP, что такое функция ценности, как уравнение Беллмана превращается в работающий алгоритм и почему коэффициент дисконтирования так сильно меняет ответ. Чтобы сразу увидеть, как ценность состояний и политика зависят от параметров среды, ниже стоит интерактивный калькулятор.

Кортеж MDP: пять элементов

Формально марковский процесс принятия решений задаётся кортежем из пяти элементов:

$$\langle S, A, P, R, \gamma \rangle$$

• $S$ - множество состояний среды (где может находиться агент);
• $A$ - множество действий, доступных агенту;
• $P(s' \mid s, a)$ - функция переходов: вероятность оказаться в состоянии $s'$, если в состоянии $s$ выбрано действие $a$;
• $R(s, a)$ - функция награды за выбор действия $a$ в состоянии $s$ (иногда награду пишут как $R(s, a, s')$);
• $\gamma \in [0, 1]$ - коэффициент дисконтирования будущих наград.

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

Рассчитать для своей задачи

Цель агента: дисконтированная награда

Агент не максимизирует награду одного шага - он максимизирует суммарную награду за всю траекторию. Поскольку процесс может длиться бесконечно, награды будущего обесцениваются множителем $\gamma$ на каждом шаге. Суммарная дисконтированная награда (отдача, return) от момента $t$:

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$

Дисконт $\gamma$ играет двойную роль. Математически он гарантирует, что бесконечная сумма сходится (при $\gamma < 1$ и ограниченных наградах). Содержательно он задаёт «горизонт планирования»: при $\gamma$ близком к нулю агент близорук и хватает ближайшую награду, при $\gamma$ близком к единице он терпеливо оптимизирует далёкое будущее.

Политика и функция ценности

Политика $\pi$ - это правило выбора действия. Детерминированная политика $\pi(s)$ возвращает одно действие, стохастическая $\pi(a \mid s)$ - распределение вероятностей по действиям. Решить MDP означает найти оптимальную политику $\pi^*$, дающую наибольшую ожидаемую отдачу из любого состояния.

Чтобы сравнивать политики, вводят функцию ценности состояния $V^\pi(s)$ - ожидаемую дисконтированную отдачу, если из состояния $s$ следовать политике $\pi$:

$$V^\pi(s) = \mathbb{E}_\pi \left[\, G_t \mid S_t = s \,\right]$$

Рядом полезна функция ценности действия $Q^\pi(s, a)$ - ожидаемая отдача, если в $s$ сделать действие $a$, а дальше следовать $\pi$. Именно через $Q$ удобно сравнивать действия и улучшать политику.

Уравнение Беллмана

Центральный результат теории - рекуррентное соотношение, связывающее ценность состояния с ценностями соседних. Для оптимальной функции ценности оно принимает вид уравнения оптимальности Беллмана:

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

Смысл: ценность состояния равна награде за лучшее действие плюс дисконтированная ожидаемая ценность того, куда это действие приведёт. Подробный разбор каждого члена и вывод этого соотношения - в отдельной статье про уравнение Беллмана. Здесь важно главное: уравнение Беллмана - это не формула «в один проход», а система уравнений, которую решают итеративно.

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

Самый прямой алгоритм решения MDP - итерация по ценности (value iteration). Стартуем с произвольной оценки $V_0$ (часто нули) и многократно применяем правый бок уравнения Беллмана как оператор обновления:

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

Оператор Беллмана является сжимающим отображением с коэффициентом $\gamma$, поэтому последовательность $V_k$ сходится к единственной неподвижной точке $V^*$ со скоростью геометрической прогрессии. Останавливаются, когда максимальное изменение ценности за итерацию (невязка Беллмана) падает ниже заданного порога. Оптимальную политику извлекают одним проходом: в каждом состоянии берут действие с наибольшим значением $Q^*(s, a)$.

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

Рассчитать для своей задачи

Итерация по политике

Альтернатива - итерация по политике (policy iteration), которая чередует два шага:

1. Оценка политики (policy evaluation): для фиксированной политики $\pi$ решают линейную систему Беллмана и находят $V^\pi$.
2. Улучшение политики (policy improvement): в каждом состоянии переключаются на действие, жадное по полученной $V^\pi$.

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

Стохастичность среды

Функция переходов $P(s' \mid s, a)$ - это то, что отличает MDP от обычного графа кратчайших путей. Если действие «вперёд» выполняется не всегда, а с вероятностью $p < 1$ (и с вероятностью $1 - p$ агент проскальзывает), то оптимальная политика учитывает риск. Чем выше стохастичность, тем сильнее обесцениваются дальние состояния и тем осторожнее ведёт себя агент. Это видно в калькуляторе: при $p = 0.5$ ценность старта проседает, потому что половина шагов уводит не туда.

Связь с обучением с подкреплением

В классическом MDP функции $P$ и $R$ известны заранее, и задачу решают динамическим программированием. В обучении с подкреплением (RL) среда задана как MDP, но её динамика неизвестна - агент узнаёт о наградах и переходах только из опыта взаимодействия. Алгоритмы вроде Q-обучения оценивают $Q^*$ напрямую по сэмплам, не строя модель $P$. По сути RL - это MDP, решаемый «вслепую», методом проб и ошибок, но на том же фундаменте уравнения Беллмана.

Частые ошибки

• Путают награду и ценность. Награда $R$ - мгновенный сигнал за один шаг; ценность $V$ - ожидаемая сумма дисконтированных наград за всё будущее. Максимизируют именно ценность.
• Берут $\gamma = 1$ в бесконечном MDP. Без дисконта (и без терминальных состояний) сумма наград расходится, и ценности уходят в бесконечность. Для эпизодических задач $\gamma = 1$ допустимо, для непрерывных - нет.
• Забывают про стохастичность переходов. Решают MDP как детерминированный граф, игнорируя $P(s' \mid s, a)$. В случайной среде это даёт неверную политику.
• Считают, что итерация по ценности даёт точное $V^*$ за конечное число шагов. Она сходится в пределе; на практике останавливаются по порогу невязки, и политика стабилизируется раньше, чем сами ценности.
• Нарушают свойство Маркова. Описывают состояние неполно, так что будущее зависит от прошлого - и удивляются, почему политика плохо работает.

FAQ

Чем MDP отличается от марковской цепи? Марковская цепь описывает случайную динамику без управления: переходы заданы и агент ни на что не влияет. В MDP добавлены действия и награды - агент активно выбирает действие, меняя распределение переходов. Цепь - это MDP с единственным действием.

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

Что такое POMDP? Частично наблюдаемый MDP: агент не видит истинное состояние, а получает лишь наблюдения. Решение строится над распределением вероятностей по состояниям (belief state), что заметно усложняет задачу.

Коротко

Марковский процесс принятия решений задаётся кортежем $\langle S, A, P, R, \gamma \rangle$ и моделирует последовательный выбор действий в случайной среде со свойством Маркова. Цель - найти политику, максимизирующую дисконтированную отдачу; её ценность описывает уравнение оптимальности Беллмана. Решают MDP итерацией по ценности или по политике; когда динамика среды неизвестна, тот же каркас лежит в основе обучения с подкреплением. Дисконт $\gamma$ задаёт горизонт планирования, а функция переходов $P$ - стохастичность, и оба параметра напрямую меняют оптимальную политику.