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

В математике марковский процесс принятия решений ( MDP ) - это стохастический процесс управления с дискретным временем . Он обеспечивает математическую основу для моделирования принятия решений в ситуациях, когда результаты частично случайны, а частично находятся под контролем лица, принимающего решения. MDP полезны для изучения задач оптимизации, решаемых с помощью динамического программирования . MDP были известны по крайней мере еще в 1950-х годах; ^[1] основная часть исследований марковских процессов принятия решений стала результатом книги Рональда Ховарда 1960 года « Динамическое программирование и марковские процессы» . ^[2] Они используются во многих дисциплинах, включая робототехнику , автоматическое управление , экономику и производство . Название MDP происходит от русского математика Андрея Маркова, поскольку они являются продолжением цепей Маркова .

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

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

Марковские процессы принятия решений являются продолжением цепей Маркова ; разница заключается в добавлении действий (предоставление возможности выбора) и поощрений (мотивация). И наоборот, если для каждого состояния существует только одно действие (например, «ожидание») и все вознаграждения одинаковы (например, «ноль»), процесс принятия решения Маркова сводится к цепи Маркова.

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

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

• ${\ displaystyle S}$представляет собой набор состояний называется пространством состояний ,
• ${\ displaystyle A}$- это набор действий, называемый пространством действий (альтернативно, это набор действий, доступных из состояния ),${\ displaystyle A_ {s}}$${\ displaystyle s}$
• ${\ Displaystyle P_ {a} (s, s ') = \ Pr (s_ {t + 1} = s' \ mid s_ {t} = s, a_ {t} = a)}$это вероятность того, что действие в состоянии во времени приведет к состоянию во времени ,${\ displaystyle a}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle s '}$${\ displaystyle t + 1}$
• ${\ displaystyle R_ {a} (s, s ')}$это немедленное вознаграждение (или ожидаемое немедленное вознаграждение), полученное после перехода из состояния в состояние в результате действия${\ displaystyle s}$${\ displaystyle s '}$${\ displaystyle a}$

Пространства состояний и действий могут быть конечными или бесконечными, например набор действительных чисел . Некоторые процессы со счетно бесконечными пространствами состояний и действий могут быть сведены к процессам с конечными пространствами состояний и действий. ^[3]

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

Цель марковского процесса принятия решений - найти хорошую «политику» для лица, принимающего решения: функцию, которая определяет действие, которое лицо, принимающее решения, выберет, находясь в состоянии . Как только процесс принятия решения Маркова таким образом объединяется с политикой, это фиксирует действие для каждого состояния, и результирующая комбинация ведет себя как цепь Маркова (поскольку действие, выбранное в состоянии , полностью определяется матрицей перехода Маркова и сводится к ней) .${\ displaystyle \ pi}$${\ displaystyle \ pi (s)}$${\ displaystyle s}$${\ displaystyle s}$${\ displaystyle \ pi (s)}$${\ Displaystyle \ Pr (s_ {t + 1} = s '\ mid s_ {t} = s, a_ {t} = a)}$${\ Displaystyle \ Pr (s_ {t + 1} = s '\ mid s_ {t} = 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})}$

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

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

Модели симуляторов [ править ]

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

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

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

Алгоритмы [ править ]

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

Стандартное семейство алгоритмов для вычисления оптимальных политик для MDP с конечным состоянием и действием требует хранения для двух массивов, индексированных по состоянию: значение , которое содержит реальные значения, и политика , которая содержит действия. В конце алгоритма будет содержать решение и дисконтированную сумму вознаграждений, которые будут получены (в среднем), следуя этому решению из состояния .${\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(s'\mid s,a)\left(R(s'\mid s,a)+\gamma V(s')\right)\right\}}$

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

Известные варианты [ править ]

Итерация значения [ править ]

В итерации значений ( Bellman 1957 ), которую также называют обратной индукцией , функция не используется; вместо этого значение вычисляется внутри всякий раз, когда это необходимо. Подстановка вычисления в вычисление дает объединенный шаг ^{[ требуется дальнейшее объяснение ]} :${\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 ^[6], но это было признано только позже. ^[7]${\displaystyle i}$${\displaystyle i=0}$${\displaystyle V_{0}}$${\displaystyle V_{i+1}}$${\displaystyle s}$${\displaystyle V}$

Повторение политики [ править ]

В итерации политики ( Howard 1960 ) первый шаг выполняется один раз, а затем второй шаг повторяется до тех пор, пока он не сойдется. Затем снова выполняется первый шаг и так далее.

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

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

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

Измененная итерация политики [ править ]

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

Приоритетное подметание [ править ]

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

Расширения и обобщения [ править ]

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

Частичная наблюдаемость [ править ]

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

Большой прогресс в этой области был сделан Бернетасом и Катехакисом в статье «Оптимальные адаптивные политики для марковских процессов принятия решений». ^[10] В этой работе класс адаптивных политик, которые обладают свойствами равномерно максимальной скорости сходимости для общего ожидаемого вознаграждения за конечный горизонт, был построен в предположениях конечного состояния пространств действия и неприводимости закона перехода. Эти политики предписывают, что выбор действий в каждом состоянии и в каждый период времени должен основываться на показателях, которые представляют собой инфляцию правой части уравнений оптимальности расчетного среднего вознаграждения.

Обучение с подкреплением [ править ]

Обучение с подкреплением использует MDP, где вероятность или вознаграждение неизвестны. ^[11]

Для этой цели полезно определить дополнительную функцию, которая соответствует выполнению действия и последующему его оптимальному продолжению (или в соответствии с той политикой, которая у вас есть в настоящее время):${\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), которые изначально были явно описаны как конечные автоматы . ^[12]Подобно обучению с подкреплением, алгоритм обучающихся автоматов также имеет преимущество в решении проблемы, когда вероятность или вознаграждение неизвестны. Разница между обучающими автоматами и Q-обучением заключается в том, что в первом методе не сохраняется память о Q-значениях, но напрямую обновляется вероятность действия, чтобы найти результат обучения. Обучающиеся автоматы - это обучающая схема со строгим доказательством сходимости. ^[13]

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

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

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

Теоретико-категориальная интерпретация [ править ]

Помимо вознаграждения, марковский процесс принятия решений можно понять с точки зрения теории категорий . А именно, пусть обозначим свободный моноид с порождающим множеством A . Пусть Dist обозначать категорию Клейсли из монады Жири . Тогда функтор кодирует оба множества S состояний и функция вероятности Р .${\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}}}$

Марковский процесс принятия решений в непрерывном режиме [ править ]

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

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

Чтобы обсудить марковский процесс принятия решений в непрерывном времени, мы введем два набора обозначений:

Если пространство состояний и пространство действий конечны,

• ${\displaystyle {\mathcal {S}}}$: Государственное пространство;
• ${\displaystyle {\mathcal {A}}}$: Пространство действий;
• ${\displaystyle q(i\mid j,a)}$: , функция скорости перехода;${\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \triangle {\mathcal {S}}}$
• ${\displaystyle R(i,a)}$: , функция вознаграждения.${\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \mathbb {R} }$

Если пространство состояний и пространство действий непрерывны,

• ${\displaystyle {\mathcal {X}}}$: пространство состояний;
• ${\displaystyle {\mathcal {U}}}$: пространство возможного контроля;
• ${\displaystyle f(x,u)}$: , функция скорости перехода;${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \triangle {\mathcal {X}}}$
• ${\displaystyle r(x,u)}$: , функция коэффициента вознаграждения такая, что , где - функция вознаграждения, которую мы обсуждали в предыдущем случае.${\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \mathbb {R} }$${\displaystyle r(x(t),u(t))\,dt=dR(x(t),u(t))}$${\displaystyle R(x,u)}$

Проблема [ править ]

Подобно процессам Маркова с дискретным временем, в процессах Маркова с непрерывным временем мы хотим найти оптимальную политику или управление, которые могли бы дать нам оптимальное ожидаемое интегрированное вознаграждение:

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

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

Формулировка линейного программирования [ править ]

Если пространство состояний и пространство действий конечны, мы могли бы использовать линейное программирование для поиска оптимальной политики, что было одним из первых применявшихся подходов. Здесь мы рассматриваем только эргодическую модель, что означает, что наша MDP с непрерывным временем становится эргодической марковской цепью с непрерывным временем при стационарной политике . В соответствии с этим предположением, хотя лицо, принимающее решение, может принять решение в любое время в текущем состоянии, оно не может получить больше, если предпримет более одного действия. Им лучше действовать только в то время, когда система переходит из текущего состояния в другое. При некоторых условиях (подробнее см. Следствие 3.14 о марковских процессах принятия решений с непрерывным временем ), если наша функция оптимального значения${\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(x(0),0)={}&\max _{u}\int _{0}^{T}r(x(t),u(t))\,dt+D[x(T)]\\{\text{s.t.}}\quad &{\frac {dx(t)}{dt}}=f[t,x(t),u(t)]\end{aligned}}}$

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

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

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

Заявление [ править ]

Марковские процессы принятия решений с непрерывным временем находят применение в системах массового обслуживания , эпидемических процессах и демографических процессах .

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

Терминология и обозначения для MDP полностью не определены. Есть два основных потока: один фокусируется на проблемах максимизации из таких контекстов, как экономика, используя термины действие, вознаграждение, ценность и вызов коэффициента скидки, или , в то время как другой фокусируется на проблемах минимизации из инженерии и навигации ^{[ необходима ссылка ]} , используя контроль сроков, стоимости, оставшейся стоимости и фактор дисконтирования . Кроме того, различаются обозначения вероятности перехода.${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \alpha }$

в этой статье	альтернатива	комментарий
действие ${\displaystyle a}$	контроль ${\displaystyle u}$
награда ${\displaystyle R}$	Стоимость ${\displaystyle g}$	${\displaystyle g}$ это отрицание ${\displaystyle R}$
ценить ${\displaystyle V}$	себестоимость ${\displaystyle J}$	${\displaystyle J}$ это отрицание ${\displaystyle V}$
политика ${\displaystyle \pi }$	политика ${\displaystyle \mu }$
коэффициент дисконтирования ${\displaystyle \ \gamma \ }$	коэффициент дисконтирования ${\displaystyle \alpha }$
вероятность перехода ${\displaystyle P_{a}(s,s')}$	вероятность перехода ${\displaystyle p_{ss'}(a)}$

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

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

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

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

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Bellman., RE (2003) [1957]. Динамическое программирование (Дувр, мягкая обложка, ред.). Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 978-0-486-42809-3.
• Бертсекас, Д. (1995). Динамическое программирование и оптимальное управление . 2 . МА: Афина.
• Дерман, К. (1970). Конечные марковские процессы принятия решений . Академическая пресса.
• Файнберг, EA; Шварц, А., ред. (2002). Справочник по марковским процессам принятия решений . Бостон, Массачусетс: Клувер. ISBN 9781461508052.
• Guo, X .; Эрнандес-Лерма, О. (2009). Марковские процессы принятия решений с непрерывным временем . Стохастическое моделирование и прикладная вероятность. Springer. ISBN 9783642025464.
• Мейн, СП (2007). Методы управления сложными сетями . Издательство Кембриджского университета. ISBN 978-0-521-88441-9. Архивировано из оригинального 19 июня 2010 года.Приложение содержит сокращенное «Meyn & Tweedie» . Архивировано из оригинального 18 декабря 2012 года.
• Путерман., М.Л. (1994). Марковские процессы принятия решений . Вайли.
• Росс, С.М. (1983). Введение в стохастическое динамическое программирование (PDF) . Академическая пресса.
• Саттон, РС; Барто, AG (2017). Обучение с подкреплением: Введение . Кембридж, Массачусетс: MIT Press.
• Tijms., HC (2003). Первый курс стохастических моделей . Вайли. ISBN 9780470864289.

Внешние ссылки [ править ]

• Научиться решать марковские процессы принятия решений по Сатиндеру П. Сингх