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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Чтобы определить марковский процесс принятия решений, нужно задать 4-кортеж , где

  • конечное множество состояний,
  • конечное множество действий (часто представляется в виде множеств , действий доступных из состояния ),
  • вероятность, что действие в состоянии во время приведет в состояние ко времени ,
  • вознаграждение, получаемое после перехода в состояние из состояния , при совершении действия .

Стратегия  — функция (в общем случае распределение вероятностей), сопоставляющая состоянию действие, при наличии такой функции Марковский процесс принятия решений можно рассматривать, как Марковскую цепь.

Цель оптимизации[править | править код]

Решить марковский процесс принятия решений означает найти стратегию, максимизирующую "вознаграждение" (функцию ценности) - оптимальную стратегию. Самая простая функция ценности это математическое ожидание формального ряда , где , а математическое ожидание берётся в соответствии с , но такую функцию можно использовать только если гарантируется, что ряд сходится всегда, что обычно означает наличие терминального состояния, состояния MDP такого, что и . Если же сходимость ряда не гарантируется, то обычно делают одно из двух:

  • Рассматривают только конечное число слагаемых
  • Вводят коэффициент приведения

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

  • Функция полезности состояния , где математическое ожидание берётся в соответствии с
  • Функция полезности действия , где математическое ожидание берётся в соответствии с

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

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

Сравнение стратегий[править | править код]

Чтобы дать формальное определение оптимальной стратегии необходимо ввести отношение порядка на множестве стратегий. . Наибольшая стратегия называется оптимальной.

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

См. также[править | править код]

Литература[править | править код]

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