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

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

ОпределениеПравить

 

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

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

• $S$$S$  конечное множество состояний,
• $A$$A$  конечное множество действий (часто представляется в виде множеств $A_s$$A_s$ , действий доступных из состояния $s$$s$ ),
• $P_a(s,s^{\prime })=Pr(s_{t+1}=s^{\prime }\mid <!--\; \mid \; -->s_t=s,a_t=a)$$P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$  вероятность, что действие $a$$a$  в состоянии $s$$s$  во время $t$$t$  приведет в состояние $s^{\prime }$$s'$  ко времени $t+1$$t+1$ ,
• $R_a(s,s^{\prime })$$R_{a}(s,s')$  вознаграждение, получаемое после перехода в состояние $s^{\prime }$$s'$  из состояния $s$$s$ , при совершении действия $a$$a$ .

Стратегия $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  — функция (в общем случае распределение вероятностей), сопоставляющая состоянию действие, при наличии такой функции Марковский процесс принятия решений можно рассматривать, как Марковскую цепь.

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

Решить марковский процесс принятия решений означает найти стратегию, максимизирующую "вознаграждение" (функцию ценности) - оптимальную стратегию. Самая простая функция ценности это математическое ожидание формального ряда $E\left[\underset{t=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{R}_{a_t}(s_t,s_{t+1})\right]$$E\left[\sum _{t=0}^{\infty }{R_{a_{t}}(s_{t},s_{t+1})}\right]$ , где $a_t=\mathrm{\pi <!--\; \pi \; -->}(s_t)$$a_{t}=\pi (s_{t})$ , а математическое ожидание берётся в соответствии с $s_{t+1}\sim <!--\; \sim \; -->P_{a_t}(s_t,.)$$s_{t+1}\sim P_{a_{t}}(s_{t},.)$ , но такую функцию можно использовать только если гарантируется, что ряд сходится всегда, что обычно означает наличие терминального состояния, состояния MDP такого, что $P_a(s,s)=1$$P_{a}(s,s)=1$  и $R_a(s,s)=0$$R_{a}(s,s)=0$ . Если же сходимость ряда не гарантируется, то обычно делают одно из двух:

• Рассматривают только конечное число слагаемых $E\left[\underset{t=0}{\overset{N}{\sum <!--\; \sum \; -->}}{R}_{a_t}(s_t,s_{t+1})\right]$$E\left[\sum _{t=0}^{N}{R_{a_{t}}(s_{t},s_{t+1})}\right]$ 
• Вводят коэффициент приведения $E\left[\underset{t=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{\mathrm{\gamma <!--\; \gamma \; -->}}^t{R}_{a_t}(s_t,s_{t+1})\right]$$E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]$ 

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

• Функция полезности состояния $V_{\mathrm{\pi <!--\; \pi \; -->}}(s)=E\left[\underset{t=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{\mathrm{\gamma <!--\; \gamma \; -->}}^t{R}_{a_t}(s_t,s_{t+1})\mid <!--\; \mid \; -->s_0=s,a_t=\mathrm{\pi <!--\; \pi \; -->}(s_t)\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 <!--\; \sim \; -->P_{a_t}(s_t,.)$$s_{t+1}\sim P_{a_{t}}(s_{t},.)$ 
• Функция полезности действия $Q_{\mathrm{\pi <!--\; \pi \; -->}}(s,a)=E\left[\underset{t=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{\mathrm{\gamma <!--\; \gamma \; -->}}^t{R}_{a_t}(s_t,s_{t+1})\mid <!--\; \mid \; -->s_0=s,a_0=a,a_t=\mathrm{\pi <!--\; \pi \; -->}(s_t)\mathrm{\forall <!--\; \forall \; -->}t⩾<!--\; ⩾\; -->1\right]$$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 <!--\; \sim \; -->P_{a_t}(s_t,.)$$s_{t+1}\sim P_{a_{t}}(s_{t},.)$ 

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

• $V_{\ast <!--\; \ast \; -->}(s)=\underset{\mathrm{\pi <!--\; \pi \; -->}}{max}{V}_{\mathrm{\pi <!--\; \pi \; -->}}(s)$$V_{*}(s)=\max \limits _{\pi }V_{\pi }(s)$ 
• $Q_{\ast <!--\; \ast \; -->}(s,a)=\underset{\mathrm{\pi <!--\; \pi \; -->}}{max}{Q}_{\mathrm{\pi <!--\; \pi \; -->}}(s,a)$$Q_{*}(s,a)=\max \limits _{\pi }Q_{\pi }(s,a)$ 

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

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

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

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

См. такжеПравить

• Теория игр
• Q-обучение

ЛитератураПравить

• Р. С. Саттон, Э. Г. Барто. Обучение с подкреплением. 2-е изд. 2014.