Марковский процесс принятия решений
Марковский процесс принятия решений (англ. Markov decision process (MDP)) — спецификация задачи последовательного принятия решений для полностью наблюдаемой среды с марковской моделью перехода и дополнительными вознаграждениями. Слово марковский в названии отражает выполнение марковского свойства для таких процессов. Такой процесс служит математической основой для моделирования последовательного принятия решений в ситуациях, где результаты частично случайны и частично под контролем лица, принимающего решения. Сегодня эта спецификация используется во множестве областей, включая робототехнику, автоматизированное управление, экономику и производство. Подход обучения с подкреплениями, основанный на данной модели используется например в AlphaZero.
Определение[править | править код]
Чтобы определить марковский процесс принятия решений, нужно задать 4-кортеж , где
- конечное множество состояний,
- конечное множество действий (часто представляется в виде множеств , действий доступных из состояния ),
- вероятность, что действие в состоянии во время приведет в состояние ко времени ,
- вознаграждение, получаемое после перехода в состояние из состояния , при совершении действия .
Стратегия — функция (в общем случае распределение вероятностей), сопоставляющая состоянию действие, при наличии такой функции Марковский процесс принятия решений можно рассматривать, как Марковскую цепь.
Цель оптимизации[править | править код]
Решить марковский процесс принятия решений означает найти стратегию, максимизирующую "вознаграждение" (функцию ценности) - оптимальную стратегию. Самая простая функция ценности это математическое ожидание формального ряда , где , а математическое ожидание берётся в соответствии с , но такую функцию можно использовать только если гарантируется, что ряд сходится всегда, что обычно означает наличие терминального состояния, состояния MDP такого, что и . Если же сходимость ряда не гарантируется, то обычно делают одно из двух:
- Рассматривают только конечное число слагаемых
- Вводят коэффициент приведения
На практике второй вариант более гибкий, так как учитывает более долгосрочную перспективу и чаще используется именно он. Для максимизации такого ряда вводят две функции:
- Функция полезности состояния , где математическое ожидание берётся в соответствии с
- Функция полезности действия , где математическое ожидание берётся в соответствии с
А также их максимумы по всем стратегиям:
Можно доказать, что эти функции также являются функциями полезности состояния и полезности действия соответственно, а также, что они достигаются на детерминированной стратегии. Заметим, что по функции можно восстановить её стратегию, которая будет оптимальной.
Сравнение стратегий[править | править код]
Чтобы дать формальное определение оптимальной стратегии необходимо ввести отношение порядка на множестве стратегий. . Наибольшая стратегия называется оптимальной.
Можно доказать, что оптимальная стратегия существует.
См. также[править | править код]
Литература[править | править код]
- Р. С. Саттон, Э. Г. Барто. Обучение с подкреплением. 2-е изд. 2014.
Это статья-заготовка по математике. Вы можете помочь проекту, дополнив эту статью, как и любую другую в Википедии. Нажмите и узнайте подробности. |