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

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

Определение[править | править вики-текст]

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

Чтобы определить марковский процесс принятия решений, нужно задать 4-кортеж $(S,A,P_{\cdot }(\cdot ,\cdot ),R_{\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')=\Pr(s_{t+1}=s'\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'$ $s'$ ко времени $t+1$ $t+1$ ,
$R_{a}(s,s')$ $R_{a}(s,s')$ вознаграждение, получаемое после перехода в состояние $s'$ $s'$ из состояния $s$ $s$ с вероятностью перехода $P_{a}(s,s')$ $P_{a}(s,s')$ .