Марковские свойства - Марковские процессы - Марковские процессы вознаграждения - Марковские процессы принятия решений

Обзор

Марковские процессы принятия решений (MDP) — это математические описания задач обучения с подкреплением.

Требуемая средаполное наблюдениеиз.

марковский секс

"Просто знай, что настоящее, будущее и прошлое условно независимы, вы можете выбросить всю информацию в прошлом. "

Определение: если состояние в момент времени t S_t Удовлетворяют следующей формуле, тогда это состояние называетсямарковское состояние, то есть состояние удовлетворяет марковскому свойству

P[S_{t+1}|S_{t}] = P[S_{t+1}|S_1, ..., S_t]

Примечание:

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

пример:

играть в шахматы
тетрис

После состояния Маркова:

Матрица перехода состояний может быть определена
Игнорировать влияние времени и заботиться только о текущем моменте

Примечание. Удовлетворяет ли состояние марковскому свойству, тесно связано с определением состояния.

матрица перехода состояний

вероятность перехода состояния

вероятность перехода состоянияОтносится к вероятности перехода из марковского состояния s в последующее состояние s'. - условное распределение вероятностей относительно текущего состояния.

\mathcal{P} _ {ss^{'}} = {P} [S_{t+1} = s^{'} | S_t = s]

матрица перехода состояний

Если статусдискретныйиз (ограничено):

Все состояния образуют ряд
Все государства-преемники образуют столбцы,

получить матрицу перехода состояний

\mathcal{P} = \begin{bmatrix} \mathcal{P} _ {11} & ... & \mathcal{P} _ {1n} \\ ... & ... & ... \\ \mathcal{P} _ {n1} & ... & \mathcal{P} _ {nn} \\ \end{bmatrix}

это количество штатов
Элементы в каждой строке в сумме дают 1

функция перехода состояния

Если количество состояний слишком велико или если оно бесконечно (непрерывное состояние), целесообразно использовать функциональную форму приведенной выше формулы в этом разделе.

В настоящее время, $\int_{s'}\mathcal{P}(s'|s)=1$

Марковский процесс

определение

Марковский процесс (МП) — это случайный процесс без памяти, то есть последовательность некоторых марковских состояний.

Марковский процесс может быть определен двукратным $< S,\mathcal{P} >$

: представляет набор состояний
$\mathcal{P}$ : представляет матрицу перехода состояний

обычно предполагают $\mathcal{P}$ присутствует и стабильно когда $\mathcal{P}$ При нестабильности используйте онлайн-обучение, быстрое обучение и другие методы

Пример марковского процесса

В марковском процессе есть два конечных состояния:
- конец времени
- состояние прекращено

Эпизоды

Определение: в обучении с подкреплением, начиная с начального состояния S_1 до конечного состояния S_T процесс последовательности.

Марковский процесс вознаграждения

определение

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

Процесс Марковского вознаграждения (MRP) состоит из кватерниона $⟨S, \mathcal{P}, \mathcal{R}, γ⟩$

S: набор состояний
$\mathcal{P}$ : матрица перехода состояний
$\mathcal{R}$ : функция вознаграждения, $\mathcal{R}(s)$ описывает вознаграждение в состоянии s, $\mathcal{R}(s) = E [\mathcal{R}_{t+1}|S_t = s]$
: коэффициент затухания

возвращаемое значение

Бонусная стоимость: за одингосударствооценка
Возвращаемое значение: дляФрагментоценка

возвращаемое значение G_t ) — кумулятивное уменьшающееся вознаграждение, начиная с момента времени t.

G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ...

Функции стоимости в MRP

Почему функции ценности? Возвращаемое значение является результатом одного сегмента, и существует большое смещение выборки. Индекс значения вознаграждения равен t, а функция значения фокусируется на состоянии s.

Функция стоимости MRP определяется следующим образом.

Функция значения здесь предназначена для состояния s, поэтому она называетсяфункция значения состояния, также известная как функция V

Уравнение Беллмана в MRP (выделено)

\begin{aligned}v(s)&={E}[G_t|S_t=s] \\ &={E}[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t=s] \\ &={E}[ R_{t+1} + \gamma G_{t+1} | S_t=s ] \\ &={E}[ R_{t+1} + \gamma v(S_{t+1}) | S_t=s ]\end{aligned}

Функция ценности текущего состояния состоит из двух частей:

первый пункт:Мгновенная награда $R_{t+1}$
второй раздел:Функция ценности последующего состояния, умноженная на коэффициент затухания $\gamma v(S_{t+1})$

Поскольку состояний-преемников может быть несколько, если известна матрица перехода,Так

\begin{aligned} v(s) &= {E} [R_{t+1} + γv(S_{t+1}) | S_t = s] \\ &= {E} [R_{t+1} | S_t = s] + γ {E}[v(S_{t+1})|S_t = s] \\ &= \mathcal{R}(s) + γ ∑\mathcal{P}_{ss^′}v(s^′)\end{aligned}

Матрично-векторная форма:

По сути, линейное уравнение, которое можно решить напрямую:

Прямое решение доступно только для небольших MRP:

Вычислительная сложность
требуют известных $\mathcal{P}$

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

В MP и MRP мы оба являемся наблюдателями, наблюдающими за явлением перехода между состояниями и вычисляющими ценность вознаграждения. Для задачи RL мы предпочитаем перейти кИзмените поток переходов между состояниями,идти смаксимизировать доход. Следовательно, вводя решения в MRP, получаемМарковские процессы принятия решений (MDP)

определение

Марковский процесс принятия решений (MDP) состоит из пяти $⟨S, \mathcal{A}, \mathcal{P}, \mathcal{R}, γ⟩$

$\mathcal{A}$ : набор действий
$\mathcal{P}$ : матрица перехода состояний

\mathcal{P}_{ss^{'}}^{a} = {P}[ S_{t+1}=s' | S_t=s, A_{t}=a]

$\mathcal{R}(s,a)$ : функция вознаграждения, представляет вознаграждение за выполнение действия a в состоянии s. $\mathcal{R}(s, a) = E [\mathcal{R}_{t+1}|S_t = s, A_{t}=a]$

Стратегия

В MDP политика (Policy)π — это распределение вероятностей действий в заданном состоянии.

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

Связь между MDP и MRP

Если MDP выдает данную политику $\pi$ , это перерастет в проблему MRP.

Функции ценности в MDP

Функция значения состояния (функция V)
- Определение: начиная с состояния s, используя политику $\pi$ ожидаемое значение возврата
$v_{\pi}(s) = {E}_\pi[G_t|S_t = s]$
Функция значения действия состояния (функция Q)
- Определение: функция значения действия состояния в MDP начинается с состояния s, выполняет действие а,потомОжидаемый доход при использовании политики π
  
  Действие а не обязательно исходит из политики $\pi$ , в самом деле, после выполнения действия a следует стратегия $\pi$ сделать выбор действия
$q_{\pi}(s, a) = {E}_\pi[ G_t | S_t = s, A_t = a ]$

Уравнение ожидания Беллмана

Подобно MRP, функция стоимости в MDP также может быть разложена наМгновенная наградаифункция ценности состояний-преемниковдве части

v_ \pi(s)={E}_ \pi [ R_{t+1} + \gamma v_ \pi(S_{t+1}) | S_t=s ]

q_ \pi(s,a)={E}_ \pi [ R_{t+1} + \gamma q_ \pi(S_{t+1}, A_{t+1}) | S_t=s, A_t=a]