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

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

Определение

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

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

• $S$ конечное число состояний,
• $A$ конечное число действий (часто представляется в виде, $A_s$ конечное число действий, доступных из состояния $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$ с вероятностью перехода $P_a(s,s')$.

См. также

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