Марковский процесс принятия решений

Марковский процесс принятия решений (МППР, англ. Markov decision process, MDP) — математический формализм для марковского дискретного стохастического процесса управления, основа для моделирования последовательного принятия решений в ситуациях, где результаты частично случайны и частично зависят от лица, принимающего решения. МППР используется во множестве областей, включая робототехнику, автоматизированное управление, экономику и производство. Подход обучения с подкреплениями, основанный на данной модели, применяется, например, в нейронной сети AlphaZero.

Определение

Диаграмма обучения с подкреплением в МППР

Пример МППР с 3 состояниями и 2 действиями

Марковские процессы принятия решений представляют собой инструмент для постановки задачи обучения, где достижение цели осуществляется через взаимодействие и последовательное принятие решений. Окружающая среда (или просто среда), представляет собой сторону, с которой взаимодействует агент. Агент выбирает действия, в то время как среда реагирует на эти действия и предоставляет новые ситуации для агента. Кроме того, среда генерирует вознаграждения — числовые значения, которые агент стремится максимизировать с течением времени путем выбора действий. Инженерам будут более понятны термины: агент — устройство управления или контроллер, среда — управляемая система, действие — управляющий сигнал.

Формально определить марковский процесс принятия решений можно, задав 4-кортеж $(S,A,P_{\cdot }(\cdot ,\cdot ),R_{\cdot }(\cdot ,\cdot ))$, где

• $S$ — конечное множество состояний среды, из которых агент наблюдает $S_{t}\in S$ в момент времени $t=0,1,2\dots$,
• $A(s)$ — конечное множество действий, доступных из состояния $s$, из которых агент может выбрать для момента времени $t$ действие $a_{t}\in A(s)$,
• $P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$ — вероятность перехода состояний. То есть, вероятность того, что действие $a$ в состоянии $s$ в момент времени $t$ приведёт в состояние $s'$ в момент $t+1$,
• $R_{a}(s,s')$ вознаграждение, получаемое после перехода в состояние $s'$ из состояния $s$ при совершении действия $a$.

Совместно агент и среда порождают траекторию $S_{0},A_{0},R_{0},S_{1},A_{1},R_{1},\dots$.

Стратегия $\pi$ — функция (в общем случае распределение вероятностей), сопоставляющая состоянию действие. При наличии такой функции МППР можно рассматривать как Марковскую цепь.

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

Цель оптимизации

Решить марковский процесс принятия решений означает найти оптимальную стратегию, максимизирующую вознаграждение (функцию ценности). Самая простая функция ценности — это математическое ожидание формального ряда $E\left[\sum _{t=0}^{\infty }{R_{a_{t}}(s_{t},s_{t+1})}\right]$, где $a_{t}=\pi (s_{t})$, а математическое ожидание берётся в соответствии с распределением вероятности $s_{t+1}\sim P_{a_{t}}(s_{t},.)$, но такую функцию можно использовать только если ряд сходится всегда, что обычно означает наличие конечного состояния МППР — такого, что $P_{a}(s,s)=1$ и $R_{a}(s,s)=0$. Если же сходимость ряда не гарантируется, можно:

• Рассмотреть только конечное число слагаемых $E\left[\sum _{t=0}^{N}{R_{a_{t}}(s_{t},s_{t+1})}\right]$
• Ввести $\gamma \in [0,1]$ — коэффициент обесценивания (дисконтирования) $E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]$, который контролирует предпочтение агентом мгновенных вознаграждений по сравнению с вознаграждениями в будущем

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

Для максимизации такого ряда вводят две функции:

• Функция полезности состояния $V_{\pi }(s)=E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\mid s_{0}=s,a_{t}={\pi }(s_{t})\right]$, где математическое ожидание берётся в соответствии с распределением $s_{t+1}\sim P_{a_{t}}(s_{t},.)$
• Функция полезности действия $Q_{\pi }(s,a)=E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\mid s_{0}=s,a_{0}=a,a_{t}={\pi }(s_{t})\;\forall t\geqslant 1\right]$, где математическое ожидание берётся в соответствии с $s_{t+1}\sim P_{a_{t}}(s_{t},.)$

А также их максимумы по всем стратегиям:

• $V_{*}(s)=\max \limits _{\pi }V_{\pi }(s)$
• $Q_{*}(s,a)=\max \limits _{\pi }Q_{\pi }(s,a)$

Можно доказать, что эти функции также являются функциями полезности состояния и полезности действия соответственно, а также, что они достигаются на детерминированной стратегии. Заметим, что по функции $Q_{*}$ можно восстановить её стратегию, которая будет оптимальной.

Сравнение стратегий

Чтобы дать формальное определение оптимальной стратегии необходимо ввести отношение порядка на множестве стратегий. $\pi _{1}\preccurlyeq \pi _{2}\iff \forall V_{\pi _{1}}(s)\leqslant V_{\pi _{2}}(s),\;s\in S$. Наибольшая стратегия называется оптимальной.

Можно доказать, что оптимальная стратегия существует.

Алгоритмические реализации

Большинство алгоритмов марковских процессов принятия решений основаны на итерации уравнения Беллмана с фиксированной точкой. Примеры включают итерацию состояния среды (англ. value iteration), итерацию стратегии (англ. policy iteration), метод временных разностей (англ. time difference, TD), Q-обучение и т. д. Анализ этих алгоритмов в табличном случае и случае линейной аппроксимации функции часто использует свойство сжатия оператора Беллмана. В последнее десятилетие нелинейные аппроксимации, такие как нейронные сети, стали более популярными. Однако для нелинейных аппроксимаций функций это свойство сжатия уже не выполняется, что часто приводит к нестабильности. Было предложено множество вариантов и модификаций для стабилизации обучения, например, DQN (англ. Deep Q-Network — «глубокая Q-сеть»), A3C (англ. Asynchronous Advantage Actor-Critic — «агент-критик с асинхронным преимуществом»). Однако для этих алгоритмов по-прежнему отсутствуют теоретические гарантии.

Расширения

Дискретные марковские процессы принятия решений хорошо изучены. Существуют расширения для непрерывных состояний среды с линейной или нелинейной аппроксимацией функций, случаев частичной наблюдаемости (англ. partially observable MDP), структурированных МППР (например, динамические байесовские сети англ. DBN) и другие, но алгоритмы становятся намного менее устойчивыми.

См. также

• Теория игр

Литература

• Саттон Р. С., Барто Э. Дж. Обучение с подкреплением: Введение = Reinforcement Learning. — 2-е изд.. — Москва: ДМК Пресс, 2020. — С. 552.