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

Определение

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

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

• ${\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 }$ — функция (в общем случае распределение вероятностей ), сопоставляющая состоянию действие. При наличии такой функции МППР можно рассматривать как Марковскую цепь .

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

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

Решить марковский процесс принятия решений означает найти оптимальную стратегию, максимизирующую вознаграждение ( функцию ценности ). Самая простая функция ценности — это математическое ожидание формального ряда ${\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 — «агент-критик с асинхронным преимуществом»). Однако для этих алгоритмов по-прежнему отсутствуют теоретические гарантии.

Расширения

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

См. также

• Теория игр

Примечания

Литература

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