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

Математическая модель последовательного принятия решений в условиях неопределенности

Марковский процесс принятия решений ( MDP ), также называемый стохастической динамической программой или задачей стохастического управления, представляет собой модель последовательного принятия решений , когда результаты неопределенны. ^[1]

Возникнув из исследования операций в 1950-х годах, ^{[2] [3]} MDP с тех пор получили признание в различных областях, включая экологию , экономику , здравоохранение , телекоммуникации и обучение с подкреплением . ^[4] Обучение с подкреплением использует структуру MDP для моделирования взаимодействия между обучающимся агентом и его средой. В этой структуре взаимодействие характеризуется состояниями, действиями и вознаграждениями. Структура MDP разработана для предоставления упрощенного представления ключевых элементов задач искусственного интеллекта . Эти элементы охватывают понимание причины и следствия , управление неопределенностью и недетерминизмом, а также стремление к явным целям. ^[4]

Название происходит от его связи с цепями Маркова , концепцией, разработанной российским математиком Андреем Марковым . «Марков» в «Марковском процессе принятия решений» относится к базовой структуре переходов состояний , которые по-прежнему следуют свойству Маркова . Процесс называется «процессом принятия решений», потому что он включает в себя принятие решений, которые влияют на эти переходы состояний, расширяя концепцию цепи Маркова в область принятия решений в условиях неопределенности.

Определение

Пример простого MDP с тремя состояниями (зеленые круги) и двумя действиями (оранжевые круги), с двумя вознаграждениями (оранжевые стрелки)

Марковский процесс принятия решений представляет собой 4- кортеж , где: ${\displaystyle (S,A,P_{a},R_{a})}$

• ${\displaystyle S}$представляет собой набор состояний, называемый пространством состояний . Пространство состояний может быть дискретным или непрерывным, как и множество действительных чисел .
• ${\displaystyle A}$— это набор действий, называемый пространством действий (альтернативно, это набор действий, доступных из состояния ). Что касается состояния, этот набор может быть дискретным или непрерывным. ${\displaystyle A_{s}}$ ${\displaystyle s}$
• ${\displaystyle P_{a}(s,s')}$на интуитивном уровне — это вероятность того, что действие в состоянии в момент времени приведет к состоянию в момент времени . В общем случае этот вероятностный переход определяется как удовлетворяющий для каждого измеримого. В случае, если пространство состояний дискретно, интеграл подразумевается относительно меры подсчета, так что последний упрощается как ; В случае интеграл обычно подразумевается относительно меры Лебега . ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s'}$ ${\displaystyle t+1}$ ${\displaystyle \Pr(s_{t+1}\in S'\mid s_{t}=s,a_{t}=a)=\int _{S'}P_{a}(s,s')ds',}$ ${\displaystyle S'\subseteq S}$ ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$ ${\displaystyle S\subseteq \mathbb {R} ^{d}}$
• ${\displaystyle R_{a}(s,s')}$это немедленное вознаграждение (или ожидаемое немедленное вознаграждение), получаемое после перехода из состояния в состояние в результате действия . ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle a}$

Функция политики представляет собой (потенциально вероятностное) отображение пространства состояний ( ) в пространство действий ( ). ${\displaystyle \pi }$ ${\displaystyle S}$ ${\displaystyle A}$

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

Целью процесса принятия решений Маркова является поиск хорошей «политики» для лица, принимающего решения: функции , которая определяет действие , которое лицо, принимающее решения, выберет в состоянии . После того, как процесс принятия решений Маркова объединяется с политикой таким образом, это фиксирует действие для каждого состояния, и полученная комбинация ведет себя как цепь Маркова (поскольку действие, выбранное в состоянии, полностью определяется ). ${\displaystyle \pi }$ ${\displaystyle \pi (s)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle \pi (s)}$

Цель состоит в том, чтобы выбрать политику , которая максимизирует некоторую кумулятивную функцию случайных вознаграждений, обычно ожидаемую дисконтированную сумму на потенциально бесконечном горизонте: ${\displaystyle \pi }$

${\displaystyle E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]}$(где мы выбираем , т.е. действия, указанные политикой). И ожидание принимается ${\displaystyle a_{t}=\pi (s_{t})}$ ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

где — фактор дисконтирования, удовлетворяющий , который обычно близок к (например, для некоторой ставки дисконтирования ). Более низкий фактор дисконтирования мотивирует лицо, принимающее решение, отдавать предпочтение принятию мер на раннем этапе, а не откладывать их на неопределенный срок. ${\displaystyle \ \gamma \ }$ ${\displaystyle 0\leq \ \gamma \ \leq \ 1}$ ${\displaystyle 1}$ ${\displaystyle \gamma =1/(1+r)}$ ${\displaystyle r}$

Другая возможная, но строго связанная, цель, которая обычно используется, — это возврат шага. На этот раз вместо использования дисконтного фактора агент интересуется только первыми шагами процесса, причем каждое вознаграждение имеет одинаковый вес. ${\displaystyle H-}$ ${\displaystyle \ \gamma \ }$ ${\displaystyle H}$

${\displaystyle E\left[\sum _{t=0}^{H-1}{R_{a_{t}}(s_{t},s_{t+1})}\right]}$(где мы выбираем , т.е. действия, указанные политикой). И ожидание принимается ${\displaystyle a_{t}=\pi (s_{t})}$ ${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$

где - временной горизонт. По сравнению с предыдущей целью, последняя чаще используется в теории обучения. ${\displaystyle \ H\ }$

Политика, которая максимизирует функцию выше, называется оптимальной политикой и обычно обозначается . Конкретный MDP может иметь несколько различных оптимальных политик. Из-за свойства Маркова можно показать, что оптимальная политика является функцией текущего состояния, как предполагалось выше. ${\displaystyle \pi ^{*}}$

Модели симуляторов

Во многих случаях трудно представить распределения вероятностей перехода, , явно. В таких случаях симулятор может использоваться для неявного моделирования MDP, предоставляя образцы из распределений перехода. Одной из распространенных форм неявной модели MDP является эпизодический симулятор среды, который может быть запущен из начального состояния и выдает последующее состояние и вознаграждение каждый раз, когда он получает входное действие. Таким образом, могут быть созданы траектории состояний, действий и вознаграждений, часто называемые эпизодами . ${\displaystyle P_{a}(s,s')}$

Другой формой симулятора является генеративная модель , одношаговый симулятор, который может генерировать образцы следующего состояния и вознаграждения, учитывая любое состояние и действие. ^[5] (Обратите внимание, что это другое значение, чем термин генеративная модель в контексте статистической классификации.) В алгоритмах , которые выражаются с помощью псевдокода , часто используется для представления генеративной модели. Например, выражение может обозначать действие выборки из генеративной модели, где и являются текущим состоянием и действием, а и являются новым состоянием и вознаграждением. По сравнению с эпизодическим симулятором, генеративная модель имеет то преимущество, что она может выдавать данные из любого состояния, а не только тех, которые встречаются в траектории. ${\displaystyle G}$ ${\displaystyle s',r\gets G(s,a)}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s'}$ ${\displaystyle r}$

Эти классы моделей образуют иерархию информационного содержания: явная модель тривиально дает генеративную модель посредством выборки из распределений, а повторное применение генеративной модели дает эпизодический симулятор. В противоположном направлении, возможно только изучение приближенных моделей посредством регрессии . Тип модели, доступной для конкретного MDP, играет важную роль в определении того, какие алгоритмы решения являются подходящими. Например, алгоритмы динамического программирования , описанные в следующем разделе, требуют явной модели, а поиск по дереву Монте-Карло требует генеративной модели (или эпизодического симулятора, который можно скопировать в любом состоянии), тогда как большинство алгоритмов обучения с подкреплением требуют только эпизодического симулятора.

Пример

Пример балансировки на шесте (рендеринг окружения из теста Open AI gym)

Примером MDP является модель балансировки полюсов, которая исходит из классической теории управления.

В этом примере мы имеем

• ${\displaystyle S}$представляет собой набор упорядоченных кортежей, заданных углом полюса, угловой скоростью, положением тележки и ее скоростью. ${\displaystyle (\theta ,{\dot {\theta }},x,{\dot {x}})\subset \mathbb {R} ^{4}}$
• ${\displaystyle A}$, что соответствует приложению силы слева (справа) к тележке. ${\displaystyle \{-1,1\}}$
• ${\displaystyle P_{a}(s,s')}$— это переход системы, который в данном случае будет детерминированным и будет подчиняться законам механики.
• ${\displaystyle R_{a}(s,s')}$если полюс вверху после перехода, ноль в противном случае. Таким образом, эта функция зависит только от в этом конкретном случае. ${\displaystyle 1}$ ${\displaystyle s'}$

Алгоритмы

Решения для MDP с конечными пространствами состояний и действий могут быть найдены с помощью различных методов, таких как динамическое программирование . Алгоритмы в этом разделе применяются к MDP с конечными пространствами состояний и действий и явно заданными вероятностями перехода и функциями вознаграждения, но основные концепции могут быть расширены для обработки других классов задач, например, с использованием аппроксимации функций .

Стандартное семейство алгоритмов для расчета оптимальных политик для конечных состояний и MDP действий требует хранения двух массивов, индексированных по состоянию: value , который содержит реальные значения, и policy , который содержит действия. В конце алгоритма будет содержать решение и будет содержать дисконтированную сумму вознаграждений, которые будут получены (в среднем) при следовании этому решению из состояния . ${\displaystyle V}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle V(s)}$ ${\displaystyle s}$

Алгоритм состоит из двух шагов: (1) обновление значения и (2) обновление политики, которые повторяются в некотором порядке для всех состояний до тех пор, пока не прекратятся дальнейшие изменения. Оба рекурсивно обновляют новую оценку оптимальной политики и значения состояния, используя более старую оценку этих значений.

${\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}$

${\displaystyle \pi (s):=\operatorname {argmax} _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}}$

Их порядок зависит от варианта алгоритма; их можно также делать для всех состояний сразу или для каждого состояния отдельно, и чаще для некоторых состояний, чем для других. Пока ни одно состояние не будет навсегда исключено из любого из шагов, алгоритм в конечном итоге придет к правильному решению. ^[6]

Известные варианты

Итерация значения

В итерации значений (Беллман 1957) , которая также называется обратной индукцией , функция не используется; вместо этого значение вычисляется в пределах всякий раз, когда это необходимо. Подстановка вычисления в вычисление дает объединенный шаг ^{[ необходимо дополнительное объяснение ]} : harv error: no target: CITEREFBellman1957 (help) ${\displaystyle \pi }$ ${\displaystyle \pi (s)}$ ${\displaystyle V(s)}$ ${\displaystyle \pi (s)}$ ${\displaystyle V(s)}$

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}$

где — номер итерации. Итерация значения начинается с и как предположение о функции значения . Затем она итерируется, многократно вычисляя для всех состояний , пока не сойдется с левой частью, равной правой части (что является « уравнением Беллмана » для этой задачи ^{[ необходимо разъяснение ]} ). Статья Ллойда Шепли 1953 года о стохастических играх включала в себя как особый случай метод итерации значения для MDP, ^[7] но это было признано только позже. ^[8] ${\displaystyle i}$ ${\displaystyle i=0}$ ${\displaystyle V_{0}}$ ${\displaystyle V_{i+1}}$ ${\displaystyle s}$ ${\displaystyle V}$

Итерация политики

В итерации политики (Говард 1960) шаг один выполняется один раз, затем шаг два выполняется один раз, затем оба повторяются до тех пор, пока политика не сойдется. Затем шаг один снова выполняется один раз и так далее. (Итерация политики была изобретена Говардом для оптимизации рассылки каталога Sears , которую он оптимизировал с помощью итерации значения. ^[9] ) harv error: no target: CITEREFHoward1960 (help)

Вместо повторения шага два до сходимости, его можно сформулировать и решить как набор линейных уравнений. Эти уравнения просто получаются путем создания уравнения на шаге два. ^{[ необходимо пояснение ]} Таким образом, повторение шага два до сходимости можно интерпретировать как решение линейных уравнений путем релаксации . ${\displaystyle s=s'}$

Преимущество этого варианта заключается в том, что существует определенное условие остановки: если массив не изменяется в ходе применения шага 1 ко всем состояниям, алгоритм завершается. ${\displaystyle \pi }$

Итерация политики обычно происходит медленнее, чем итерация значения для большого числа возможных состояний.

Измененная итерация политики

В модифицированной итерации политики (van Nunen 1976; Puterman & Shin 1978) шаг один выполняется один раз, а затем шаг два повторяется несколько раз. ^{[10] [11]} Затем шаг один снова выполняется один раз и так далее.

Приоритетная уборка

В этом варианте шаги преимущественно применяются к состояниям, которые в некотором роде важны — либо на основе алгоритма (недавно произошли большие изменения в этих состояниях или вокруг них), либо на основе использования (эти состояния близки к начальному состоянию или иным образом представляют интерес для человека или программы, использующих алгоритм). ${\displaystyle V}$ ${\displaystyle \pi }$

Сложность вычислений

Алгоритмы для поиска оптимальных политик с временной сложностью, полиномиальной по размеру представления проблемы, существуют для конечных MDP. Таким образом, проблемы принятия решений, основанные на MDP, находятся в классе вычислительной сложности P. [ ^12] Однако из-за проклятия размерности размер представления проблемы часто экспоненциален по числу переменных состояния и действия, ограничивая точные методы решения задачами, имеющими компактное представление. На практике методы онлайн-планирования, такие как поиск по дереву Монте-Карло, могут находить полезные решения в более крупных задачах, и, теоретически, можно построить алгоритмы онлайн-планирования, которые могут находить произвольно близкую к оптимальной политику без зависимости вычислительной сложности от размера пространства состояний. ^[13]

Расширения и обобщения

Марковский процесс принятия решений — это стохастическая игра с одним игроком.

Частичная наблюдаемость

Решение выше предполагает, что состояние известно, когда должно быть предпринято действие; в противном случае его невозможно рассчитать. Когда это предположение неверно, проблема называется частично наблюдаемым марковским процессом принятия решений или POMDP. ${\displaystyle s}$ ${\displaystyle \pi (s)}$

Ограниченные марковские процессы принятия решений

Ограниченные марковские процессы принятия решений (CMDPS) являются расширениями марковских процессов принятия решений (MDP). Между MDP и CMDP есть три фундаментальных различия. ^[14]

• После применения действия возникают несколько затрат вместо одной.
• Задачи CMDP решаются только с помощью линейных программ , а динамическое программирование не работает.
• Окончательная политика зависит от начального состояния.

Метод множителей Лагранжа применяется к CMDP. Разработано много алгоритмов на основе Лагранжа.

• Метод прямого и двойного градиента естественной политики. ^[15]

Существует ряд приложений для CMDP. Недавно он использовался в сценариях планирования движения в робототехнике. ^[16]

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

В дискретных марковских процессах принятия решений решения принимаются в дискретные интервалы времени. Однако для непрерывных марковских процессов принятия решений решения могут быть приняты в любое время, которое выберет принимающий решения. По сравнению с дискретными марковскими процессами принятия решений, непрерывные марковские процессы принятия решений могут лучше моделировать процесс принятия решений для системы, которая имеет непрерывную динамику , т. е. динамика системы определяется обыкновенными дифференциальными уравнениями (ОДУ). Такого рода приложения возникают в системах очередей , эпидемических процессах и процессах населения .

Как и в дискретных марковских процессах принятия решений, в непрерывных марковских процессах принятия решений агент стремится найти оптимальную политику , которая могла бы максимизировать ожидаемое накопленное вознаграждение. Единственное отличие от стандартного случая заключается в том, что из-за непрерывной природы переменной времени сумма заменяется интегралом:

${\displaystyle \max \operatorname {E} _{\pi }\left[\left.\int _{0}^{\infty }\gamma ^{t}r(s(t),\pi (s(t)))\,dt\;\right|s_{0}\right]}$

где ${\displaystyle 0\leq \gamma <1.}$

Дискретное пространство: формулировка линейного программирования

Если пространство состояний и пространство действий конечны, мы могли бы использовать линейное программирование для поиска оптимальной политики, что было одним из самых ранних примененных подходов. Здесь мы рассматриваем только эргодическую модель, что означает, что наш MDP с непрерывным временем становится эргодической цепью Маркова с непрерывным временем при стационарной политике . При этом предположении, хотя лицо, принимающее решения, может принять решение в любое время в текущем состоянии, нет никакой выгоды в выполнении нескольких действий. Лучше выполнять действие только в то время, когда система переходит из текущего состояния в другое состояние. При некоторых условиях ^[17] , если наша функция оптимального значения не зависит от состояния , мы будем иметь следующее неравенство: ${\displaystyle V^{*}}$ ${\displaystyle i}$

${\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j\mid i,a)h(j)\quad \forall i\in S{\text{ and }}a\in A(i)}$

Если существует функция , то будет наименьшей, удовлетворяющей приведенному выше уравнению. Чтобы найти , мы могли бы использовать следующую модель линейного программирования: ${\displaystyle h}$ ${\displaystyle {\bar {V}}^{*}}$ ${\displaystyle g}$ ${\displaystyle {\bar {V}}^{*}}$

• Первичная линейная программа (P-LP)

${\displaystyle {\begin{aligned}{\text{Minimize}}\quad &g\\{\text{s.t}}\quad &g-\sum _{j\in S}q(j\mid i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}$

• Двойная линейная программа (D-LP)

${\displaystyle {\begin{aligned}{\text{Maximize}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.t.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j\mid i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i){\text{ and }}\forall i\in S\end{aligned}}}$

${\displaystyle y(i,a)}$является допустимым решением D-LP, если является неродным и удовлетворяет ограничениям в задаче D-LP. Допустимое решение D-LP называется оптимальным решением, если ${\displaystyle y(i,a)}$ ${\displaystyle y^{*}(i,a)}$

${\displaystyle {\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}}$

для всех возможных решений D-LP. Как только мы нашли оптимальное решение , мы можем использовать его для установления оптимальной политики. ${\displaystyle y(i,a)}$ ${\displaystyle y^{*}(i,a)}$

Непрерывное пространство: уравнение Гамильтона–Якоби–Беллмана

В непрерывном времени MDP, если пространство состояний и пространство действий непрерывны, оптимальный критерий может быть найден путем решения уравнения в частных производных Гамильтона–Якоби–Беллмана (HJB) . Для обсуждения уравнения HJB нам нужно переформулировать нашу задачу

${\displaystyle {\begin{aligned}V(s(0),0)={}&\max _{a(t)=\pi (s(t))}\int _{0}^{T}r(s(t),a(t))\,dt+D[s(T)]\\{\text{s.t.}}\quad &{\frac {dx(t)}{dt}}=f[t,s(t),a(t)]\end{aligned}}}$

${\displaystyle D(\cdot )}$это функция конечного вознаграждения, это вектор состояния системы, это вектор управления системой, который мы пытаемся найти. показывает, как вектор состояния изменяется со временем. Уравнение Гамильтона–Якоби–Беллмана выглядит следующим образом: ${\displaystyle s(t)}$ ${\displaystyle a(t)}$ ${\displaystyle f(\cdot )}$

${\displaystyle 0=\max _{u}(r(t,s,a)+{\frac {\partial V(t,s)}{\partial x}}f(t,s,a))}$

Мы могли бы решить уравнение, чтобы найти оптимальное управление , которое могло бы дать нам функцию оптимального значения ${\displaystyle a(t)}$ ${\displaystyle V^{*}}$

Обучение с подкреплением

Обучение с подкреплением — это междисциплинарная область машинного обучения и оптимального управления , главной целью которой является нахождение приблизительно оптимальной политики для MDP, где вероятности перехода и вознаграждения неизвестны. ^[18]

Обучение с подкреплением может решать процессы Markov-Decision без явного указания вероятностей перехода, которые вместо этого необходимы для выполнения итерации политики. В этой обстановке вероятности перехода и вознаграждения должны быть изучены из опыта, т. е. путем предоставления агенту возможности взаимодействовать с MDP для заданного количества шагов. Как на теоретическом, так и на практическом уровне усилия направлены на максимизацию эффективности выборки, т. е. минимизацию количества выборок, необходимых для изучения политики, производительность которой близка к оптимальной (из-за стохастической природы процесса изучение оптимальной политики с конечным количеством выборок, как правило, невозможно). ${\displaystyle \varepsilon -}$

Обучение с подкреплением для дискретных MDP

Для целей этого раздела полезно определить дополнительную функцию, которая соответствует выполнению действия и последующему оптимальному продолжению (или в соответствии с любой текущей политикой): ${\displaystyle a}$

${\displaystyle \ Q(s,a)=\sum _{s'}P_{a}(s,s')(R_{a}(s,s')+\gamma V(s')).\ }$

Хотя эта функция также неизвестна, опыт во время обучения основан на парах (вместе с результатом ; то есть, «я был в состоянии , и я пытался делать, и произошло»). Таким образом, у вас есть массив , и вы используете опыт для его непосредственного обновления. Это известно как Q-обучение . ${\displaystyle (s,a)}$ ${\displaystyle s'}$ ${\displaystyle s}$ ${\displaystyle a}$ ${\displaystyle s'}$ ${\displaystyle Q}$

Другие области применения

Обучающиеся автоматы

Другое применение процесса MDP в теории машинного обучения называется обучающимися автоматами. Это также один из типов обучения с подкреплением, если среда является стохастической. Первая статья об обучающихся автоматах подробно рассмотрена Нарендрой и Татхачаром (1974), которые изначально были явно описаны как конечные автоматы . ^[19] Подобно обучению с подкреплением, алгоритм обучающихся автоматов также имеет преимущество решения проблемы, когда вероятность или награды неизвестны. Разница между обучающимися автоматами и Q-обучением заключается в том, что первая техника опускает память о Q-значениях, но обновляет вероятность действия напрямую, чтобы найти результат обучения. Обучающиеся автоматы — это схема обучения со строгим доказательством сходимости. ^[20]

В теории обучающихся автоматов стохастический автомат состоит из:

• набор x возможных входов,
• множество Φ = { Φ ₁ , ..., Φ _s } возможных внутренних состояний,
• набор α = { α ₁ , ..., α _r } возможных выходов или действий, где r ≤ s ,
• начальный вектор вероятности состояния p (0) = ≪ p ₁ (0), ..., p _s (0) ≫,
• вычислимая функция A , которая после каждого временного шага t генерирует p ( t + 1) из p ( t ), текущего входа и текущего состояния, и
• функция G : Φ → α, которая генерирует выходной сигнал на каждом временном шаге.

Состояния такого автомата соответствуют состояниям «дискретно-параметрического марковского процесса ». ^[21] На каждом временном шаге t = 0,1,2,3,... автомат считывает входные данные из своего окружения, обновляет P( t ) до P( t + 1) с помощью A , случайным образом выбирает последующее состояние в соответствии с вероятностями P( t + 1) и выводит соответствующее действие. Окружение автомата, в свою очередь, считывает действие и отправляет следующие входные данные автомату. ^[20]

Категориально-теоретическая интерпретация

Помимо наград, процесс принятия решений Маркова можно понять в терминах теории категорий . А именно, пусть обозначает свободный моноид с порождающим множеством A. Пусть Dist обозначает категорию Клейсли монады Жири. Тогда функтор кодирует как множество состояний S , так и функцию вероятности P. ${\displaystyle (S,A,P)}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}\to \mathbf {Dist} }$

Таким образом, процессы принятия решений Маркова могут быть обобщены от моноидов (категорий с одним объектом) до произвольных категорий. Можно назвать результат зависимым от контекста процессом принятия решений Маркова , поскольку перемещение от одного объекта к другому изменяет набор доступных действий и набор возможных состояний. ^{[ необходима цитата ]} ${\displaystyle ({\mathcal {C}},F:{\mathcal {C}}\to \mathbf {Dist} )}$ ${\displaystyle {\mathcal {C}}}$

Альтернативные обозначения

Терминология и обозначения для MDP не полностью устоялись. Существует два основных направления — одно фокусируется на задачах максимизации из контекстов, таких как экономика, используя термины действие, вознаграждение, ценность и называя фактор дисконтирования β или γ , в то время как другое фокусируется на задачах минимизации из инженерии и навигации ^{[ требуется ссылка ]} , используя термины управление, стоимость, стоимость-к-переходу и называя фактор дисконтирования α . Кроме того, обозначения для вероятности перехода различаются.

Кроме того, вероятность перехода иногда записывается как , или, реже, ${\displaystyle \Pr(s,a,s')}$ ${\displaystyle \Pr(s'\mid s,a)}$ ${\displaystyle p_{s's}(a).}$

Смотрите также

• Вероятностные автоматы
• Алгоритм расчета коэффициентов
• Квантовые конечные автоматы
• Частично наблюдаемый марковский процесс принятия решений
• Динамическое программирование
• Уравнение Беллмана для приложений в экономике.
• Уравнение Гамильтона–Якоби–Беллмана
• Оптимальное управление
• Рекурсивная экономика
• Проблема овец Мабиногион
• Стохастические игры
• Q-обучение
• цепь Маркова

Ссылки

1. Путерман, Мартин Л. (1994). Марковские процессы принятия решений: дискретное стохастическое динамическое программирование . Ряды Уайли в теории вероятностей и математической статистике. Раздел прикладной теории вероятностей и статистики. Нью-Йорк: Wiley. ISBN 978-0-471-61977-2.
2. Шнайдер, С.; Вагнер, Д. Х. (1957-02-26). "Обнаружение ошибок в избыточных системах". Доклады, представленные на 26-28 февраля 1957 г. на западной совместной компьютерной конференции: Методы обеспечения надежности на - IRE-AIEE-ACM '57 (Западная) . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 115–121. doi :10.1145/1455567.1455587. ISBN 978-1-4503-7861-1.
3. Беллман, Ричард (1958-09-01). «Динамическое программирование и стохастические процессы управления». Информация и управление . 1 (3): 228–239. doi :10.1016/S0019-9958(58)80003-0. ISSN  0019-9958.
4. Sutton, Richard S.; Barto, Andrew G. (2018). Обучение с подкреплением: введение . Серия «Адаптивные вычисления и машинное обучение» (2-е изд.). Кембридж, Массачусетс: The MIT Press. ISBN 978-0-262-03924-6.
5. Кернс, Майкл; Мансур, Ишай; Нг, Эндрю (2002). «Алгоритм разреженной выборки для почти оптимального планирования в крупных марковских процессах принятия решений». Машинное обучение . 49 (193–208): 193–208. doi : 10.1023/A:1017932429737 .
6. Обучение с подкреплением: теория и реализация Python . Пекин: China Machine Press. 2019. стр. 44. ISBN 9787111631774.
7. Шепли, Ллойд (1953). «Стохастические игры». Труды Национальной академии наук Соединенных Штатов Америки . 39 (10): 1095–1100. Bibcode :1953PNAS...39.1095S. doi : 10.1073/pnas.39.10.1095 . PMC 1063912 . PMID  16589380. 
8. Калленберг, Лодевейк (2002). "Конечные состояния и действия MDP". В Файнберг, Юджин А .; Шварц, Адам (ред.). Справочник по марковским процессам принятия решений: методы и приложения . Springer. ISBN 978-0-7923-7459-6.
9. Говард 2002, «Комментарии о происхождении и применении марковских процессов принятия решений»
10. Путерман, М. Л.; Шин, М. К. (1978). «Модифицированные алгоритмы итерации политики для дисконтированных марковских задач принятия решений». Management Science . 24 (11): 1127–1137. doi :10.1287/mnsc.24.11.1127.
11. ван Нунен, JAE E (1976). «Набор методов последовательного приближения для дисконтированных марковских задач решения». Zeitschrift für Operations Research . 20 (5): 203–208. дои : 10.1007/bf01920264. S2CID  5167748.
12. Пападимитриу, Христос ; Цициклис, Джон (1987). «Сложность марковских процессов принятия решений». Математика исследования операций . 12 (3): 441–450. doi :10.1287/moor.12.3.441. hdl : 1721.1/2893 . Получено 2 ноября 2023 г.
13. Кернс, Майкл; Мансур, Ишай; Нг, Эндрю (ноябрь 2002 г.). «Алгоритм разреженной выборки для почти оптимального планирования в крупных марковских процессах принятия решений». Машинное обучение . 49 (2/3): 193–208. doi : 10.1023/A:1017932429737 .
14. Альтман, Эйтан (1999). Ограниченные марковские процессы принятия решений . Том 7. CRC Press.
15. Дин, Дуншэн; Чжан, Кайцин; Йованович, Михайло; Басар, Тамер (2020). Прямо-двойственный метод градиента естественной политики для ограниченных марковских процессов принятия решений . Достижения в области нейронных систем обработки информации.
16. Фейзабади, С.; Карпин, С. (18–22 августа 2014 г.). «Планирование пути с учетом рисков с использованием иерархических ограниченных марковских процессов принятия решений». Automation Science and Engineering (CASE) . Международная конференция IEEE. стр. 297, 303.
17. Непрерывные марковские процессы принятия решений. Стохастическое моделирование и прикладная вероятность. Том 62. 2009. doi :10.1007/978-3-642-02547-1. ISBN 978-3-642-02546-4.
18. Шохам, Y.; Пауэрс, R.; Гренагер, T. (2003). «Многоагентное обучение с подкреплением: критический обзор» (PDF) . Технический отчет, Стэнфордский университет : 1–13 . Получено 12.12.2018 .
19. Нарендра, KS ; Тхатхачар, MAL (1974). «Обучающиеся автоматы – обзор». Труды IEEE по системам, человеку и кибернетике . SMC-4 (4): 323–334. CiteSeerX 10.1.1.295.2280 . doi :10.1109/TSMC.1974.5408453. ISSN  0018-9472. 
20. Нарендра, Кумпати С .; Татачар, Мандаям А.Л. (1989). Обучающиеся автоматы: Введение . Прентис Холл. ISBN 9780134855585.
21. Нарендра и Татачар 1974, стр.325 слева.

Дальнейшее чтение

• Беллман., Р. Э. (2003) [1957]. Динамическое программирование (издание в мягкой обложке Дувра). Принстон, Нью-Джерси: Princeton University Press. ISBN 978-0-486-42809-3.
• Берцекас, Д. (1995). Динамическое программирование и оптимальное управление . Том 2. MA: Athena.
• Дерман, К. (1970). Конечные марковские процессы принятия решений . Academic Press.
• Файнберг, Е.А.; Шварц, А., ред. (2002). Справочник по марковским процессам принятия решений. Бостон, Массачусетс: Kluwer. ISBN 9781461508052.
• Guo, X.; Hernández-Lerma, O. (2009). Непрерывные марковские процессы принятия решений. Стохастическое моделирование и прикладная вероятность. Springer. ISBN 9783642025464.
• Meyn, SP (2007). Методы управления сложными сетями. Cambridge University Press. ISBN 978-0-521-88441-9. Архивировано из оригинала 19 июня 2010 года.Приложение содержит сокращенную версию "Meyn & Tweedie". Архивировано из оригинала 18 декабря 2012 года.
• Путерман., М. Л. (1994). Марковские процессы принятия решений . Wiley.
• Росс, СМ (1983). Введение в стохастическое динамическое программирование (PDF) . Академическая пресса.
• Sutton, RS; Barto, AG (2017). Обучение с подкреплением: Введение. Кембридж, Массачусетс: The MIT Press.
• Tijms., HC (2003). Первый курс по стохастическим моделям. Wiley. ISBN 9780470864289.