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

RL — это набор методов, которые учатся оптимально вести себя в среде, тогда как Марковские процессы принятия решений (MDP) — это структура, используемая для математической формулировки задач RL. В задачах RL все состояния обладают «марковским» свойством, относящимся к тому факту, что будущее состояние зависит только от текущего состояния:

Или, другими словами, вся информация о будущем состоянии заключена в текущем состоянии.

В задачах RL агент взаимодействует со средой. То, как среда реагирует на определенные действия, определяется моделью, которую мы можем знать или не знать. Агент остается в одном из состояний (s∈S) и может выполнить одно из действий (a∈A) для переключения из одного состояния в другое. В какое состояние прибудет агент, определяется вероятностью перехода P. После завершения перехода в качестве отзыва будет выдано вознаграждение r.

Точно так же марковский процесс принятия решений состоит из пяти элементов M=(S,A,P, R,γ):

  • S — набор состояний
  • A — набор действий
  • P — функция вероятности перехода, назначает каждой паре состояние-действие (St​, At​) меру вероятности для следующего состояния Св+1​
  • R — функция немедленного вознаграждения
  • γ — коэффициент дисконтирования для расчета будущих вознаграждений.

На каждом временном шаге t=1,2,3…:

  • Выберите действие В​∈A
  • Переход в следующее состояние St+1​∈S как St+1​∼P(St +1​∣Ст​,В​)
  • Назначить вознаграждение паре состояние-действие R(St​,At​,St+1​)

Цель состоит в том, чтобы максимизировать ожидаемое общее вознаграждение:

stationary policy — это функция π:S→A. То есть каждому состоянию назначается действие. Учитывая критерий вознаграждения, политика имеет ожидаемое значение для каждого состояния. Пусть Vπ​(s) будет ожидаемым значением следующего π в состоянии s. Это указывает, какую ценность агент ожидает получить от следования политике в этом состоянии. Политика π является optimal policy, если не существует политики π′ и состояния s, таких, что Vπ′​( s)›Vπ​(s).

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

Стоимость государства

Функция ценности для состояния оценивает, насколько хорошо/вознаграждает состояние. Функция ценности состояния s в момент времени t определяется путем суммирования ожидаемых дисконтированных будущих вознаграждений на временных шагах t+1, т+2,т+3,…:

Vπ​(s) также можно переписать в рекурсивной версии:

Это известно как Bellman Equation, которое относится к набору уравнений, которые разлагают функцию ценности на немедленное вознаграждение плюс дисконтированные будущие ценности.

Стоимость полиса

Ожидаемое значение политики π для вознаграждения со скидкой со скидкой γ определяется с помощью двух взаимосвязанных функций: Vπ​ и Qπ​.

Пусть Qπ​(s, a), где s — состояние, а a — это действие, быть ожидаемым значением выполнения действия a в состоянии s при соблюдении политики π. Напомним, что Vπ​(s) — это ожидаемое значение состояния s при соблюдении политики π.

Qπ​ и Vπ​ могут быть определены рекурсивно друг относительно друга. Если агент находится в состоянии s, выполняет действие a и достигает состояния s′, он получает немедленное вознаграждение в размере R (s, a,s′) плюс будущая награда со скидкой γVπ​(s′). Когда агент планирует, он не знает фактического результирующего состояния, поэтому использует ожидаемое значение, усредненное по возможным результирующим состояниям:

И Vπ​(s) можно получить, выполнив действие, указанное π:

Ценность оптимальной политики

Пусть Q∗(s, a) будет ожидаемым значением выполнения действия a в состоянии s при соблюдении оптимальной политики. Пусть V∗(s) будет ожидаемым значением следования оптимальной политике из состояния s. Тогда Q∗ можно определить аналогично Qπ​:

Где V∗ получается путем выполнения действия, дающего наилучшее значение в каждом состоянии:

Оптимальная политика π∗ — это одна из политик, дающих наилучшее значение для каждого состояния:

Когда модель полностью известна, после Bellman Equation мы можем использовать Dynamic Programming для итеративной оценки функций ценности и улучшения политики. Например, мы представим Policy Iteration и Value Iteration как два классических метода решения оптимальных задач MDP в следующих двух разделах.

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

Value Iteration — это метод вычисления оптимальной политики MDP и ее значения.

Итерация значения начинается с «конца», а затем работает в обратном направлении, уточняя оценку либо V∗, либо Q∗. Псевдокод проиллюстрирован следующим образом:

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

Policy Iteration начинается с политики и итеративно улучшает ее. Он начинается с произвольной политики π0​ (приближение к оптимальной политике работает лучше всего) и выполняет следующие шаги, начиная с i=0:

  • Оценка политики: определение Vπi​​(s)
  • Улучшение политики: выберите πi+1​(s)=argmax_a[Qπi​​(s,а)]
  • Остановиться, если в политике нет изменений, то есть если πi+1​=πi​ — в противном случае увеличьте i и повторите

Псевдокод Policy Iteration выглядит следующим образом:

Использованная литература: