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

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

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

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

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

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

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

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

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

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

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

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

• Функция полезности состояния ${\displaystyle 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]}$, где математическое ожидание берётся в соответствии с распределением ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},.)}$
• Функция полезности действия ${\displaystyle 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]}$, где математическое ожидание берётся в соответствии с ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},.)}$

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

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

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

Чтобы дать формальное определение оптимальной стратегии необходимо ввести отношение порядка на множестве стратегий. ${\displaystyle \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 — «агент-критик с асинхронным преимуществом»). Однако для этих алгоритмов по-прежнему отсутствуют теоретические гарантии.^[2]

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

• Теория игр

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