Эта статья является второй в серии вводного обучения с подкреплением, в основном она знакомит с очень важной теоретической основой обучения с подкреплением — Марковским процессом принятия решений MDP.

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

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

Базовые концепты

Что такое обучение с подкреплением?

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

1.1.png

Обучение с подкреплением рассматривает интерактивное обучение между агентом и средой.Целью обучения агента является вознаграждение, возвращаемое средой, а задача RL состоит в том, чтобы максимизировать ожидание совокупной суммы вознаграждений. Это метод активного обучения без присмотра. Награды также являются основой для оценки выбора действий.

MDP

MDP является основой обучения с подкреплением и теоретической основой RL. В MDP мы рассматриваем состояние $S$ ,действие $A$ ,награда $R$ . В частности, агент в данный момент $t$ Наблюдайте за характерным выражением состояния окружающей среды $s_t$ , затем выберите «Действие» $a_t$ , действие получено в следующий момент $a_t$ результат - награда $r_{t+1}$ , и одновременно войти в следующее состояние $s_{t+1}$ . И когда состояние, действие, награда установлены в MDP $(С, А, Р)$ Элементов всего конечное число, такой МДП также называют конечным МДП. Формализованная последовательность выглядит следующим образом:

(s_0,a_0,r_0,...,s_t,a_t,r_t,...)

выражение с четырьмя аргументами

p(s',r|s,a)=P(S_{t}=s',R_{t}=r|S_{t-1}=s,A_{t-1}=a)

Вот краткое изложение:

\begin{aligned} &\text{Process} \\ &\quad(s_0,s_1,s_2,...,s_t,...)\;\text{with}\; P(s_t|s_{t-1},...,s_0)\\ &{\text{Markov Process}}\\ &\quad(s_0,s_1,s_2,...,s_t,...)\;\text{with}\; P(s_t|s_{t-1},...,s_0)=P(s_t|s_{t-1})\\ &\text{Markov Process}\\ &\quad(s_0,r_0,s_1,r_1,s_2,r_2,...,s_t,r_t,...)\;\text{with}\; P(s_t|s_{t-1},...,s_0)=P(s_t|s_{t-1})\\ &\text{Markov Decision Process}\\ &\quad(s_0,a_0,r_0,s_1,a_1,r_1,...,s_t,a_t,r_t,...)\;\text{with}\; P(s_t|s_{t-1},...,a_0,,s_0)=P(s_t|s_{t-1},a_{t-1})\\ \end{aligned}

Приведенное выше уравнение вероятности показывает, что в MDP $с_т, р_т$ Вероятность каждого возможного значения зависит только от предыдущего состояния и действия. $с_{т-1}, а_{т-1}$ , независимо от предыдущих состояний и действий. Это состояние также называют марковским свойством.

Для непрерывных задач определите G как взвешенную сумму вознаграждений:

\begin{aligned} G_t=&R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}\\ =&R_{t+1}+\gamma G_{t+1} \end{aligned}

$\gamma$ называется коэффициентом дисконтирования.

Фактическое общее вознаграждение $G_t$ по-прежнему конечно, потому что до тех пор, пока вознаграждение является отличной от нуля константой и $\gamma>1$ , общая награда $G_t$ Его можно сходиться, например, когда вознаграждение является константой 1, его можно выразить как

G_t=\sum_{k=0}^{\infty}\gamma^k=\dfrac{1}{1-\gamma}

Функция значения состояния и функция значения действия

Политика — это отображение состояния в вероятность выбора каждого действия, то есть случайная функция выбора действия агентом. использовать $\pi$ Выражать. $\pi$ и $s$ связан. $\pi(a|s)$ представляет вероятность выбора действия a в состоянии s, $\pi(s)$ Оно относится к функции плотности вероятности в данном состоянии (то есть в данный момент). $\pi(s)$ это функция, $\pi(a|s)$ является конкретным значением вероятности.

Функции ценности состояний при разных стратегиях различны, поэтому мы используем $v_{\pi}(s)$ стратегия презентации $\pi$ нерабочее состояние $s$ функция стоимости. Ценность, полученная при выполнении разных действий в одном и том же состоянии одной и той же стратегии, также различна, поэтому используйте $q_{\pi}(s,a)$ стратегия презентации $\pi$ нерабочее состояние $s$ действовать $a$ функция стоимости. $v_{\pi}$ также известный как стратегия $\pi$ Функция значения состояния , $q_{\pi}$ также известный как стратегия $\pi$ функция действия-ценности. Вероятность совершения одного и того же действия при разных стратегиях может быть разной.

для всех штатов $s$ , значение текущего состояния состоит в том, чтобы начать с состояния s, учитывая стратегию $\pi$ , вероятностное ожидаемое значение вознаграждения, полученного агентом, выполняющим действие в соответствии с текущей политикой. Ожидание здесь потому, что от $s$ перейти к следующему состоянию $s'$ , предпринимайте различные действия, чтобы ввести разные $s'$ , награды получаются тоже разные, поэтому для всех возможных $s'$ Спросите об ожиданиях.

\begin{aligned} v_{\pi}(s)=& E_{\pi}[G_t\;|\;S_t=s]= E_{\pi}[\sum_{t=0}^{\infty}\gamma^k R_{t+k+1}\;|\;S_t=s] \end{aligned}

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

\begin{aligned} q_{\pi}(s,a)=& E_{\pi}[G_t\;|\;S_t=s,A_t=a]= E_{\pi}[\sum_{t=0}^{\infty}\gamma^k R_{t+k+1}\;|\;S_t=s,A_t=a] \end{aligned}

Сопоставив рисунок, чтобы понять, видно, что, $v_{\pi}$ ожидание вознаграждения от штата к штату, $q_{\pi}$ это ожидание вознаграждения от действия к действию. в то время как вероятность $p$ Это определяется средой, поэтому мы можем только оптимизировать стратегию.

На самом деле найти не сложно $v_{\pi}$ и $q_{\pi}$ Существуют следующие отношения:

v_{\pi}(s)=E_{a\sim A(s)}[ q_{\pi}(s,a)]=\sum_a \pi(a|s) q_{\pi}(s,a)

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

фактически $q_{\pi}(s,a)$ Это также может быть записано как:

q_{\pi}(s,a)=E[R_{t+1}+\gamma \cdot v_{\pi}(S_{t+1})\;|\;S_t=s,A_t=a] =\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]

Далее, для любой стратегии $\pi$ и любое состояние $s$ , мы можем получить, состояние $s$ Текущее значение и его возможные последующие состояния $s'$ Отношения между:

\begin{aligned} v_{\pi}(s) =& E_{\pi}[R_{t+1}+\gamma G_{t+1}\;|\;S_t=s] \\ =&\sum_a \pi(a|s)\sum_{s'}\sum_{r}p(s',r|s,a)[r+\gamma E_{\pi}[G_{t+1}\;|\;S_{t+1}=s'] \\ =&\sum_a \pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')] \\ \end{aligned}

Это уравнение также называютУравнение Беллмана(уравнение Беллмана). так как $p$ является функцией плотности вероятности, поэтому последний член на самом деле является ожидаемым значением, которое равно $q_{\pi}$ .

Оптимальное уравнение Беллмана

Как вывести?

Мы знаем, что уравнение Беллмана на самом деле является рекурсивной формой функции значения состояния:

v_{\pi}(s)=\sum_a \pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]

Как найти лучшую стратегию?

Фактически оптимальная стратегия (обозначается как $\pi_*$ ) может быть больше одного, но они должны иметь общую функцию значения оптимального действия и функцию значения состояния, поэтому существуют:

v_*(s)=\max_{\pi} v_{\pi}(s) \\ q_*(s,a)=\max_{\pi} q_{\pi}(s,a)

При оптимальной стратегии значение каждого состояния должно быть равно ожидаемому вознаграждению за оптимальное действие в этом состоянии (поскольку стратегия определена), есть:

\begin{aligned} v_*(s)=&\max_{a\in A(s)} q_{\pi_*}(s,a) \\ =&\max_a E_{\pi_*}[G_t|S_t=s,A_t=a] \\ =&\max_a E_{\pi_*}[R_{t+1}+\gamma G_{t+1}|S_t=s,A_t=a] \\ =&\max_a E[R_{t+1}+\gamma v_*(S_{t+1})|S_t=s,A_t=a] \\ =&\max_a\sum_{s',r}p(s',r|s,a)[r+\gamma v_*(s')] \end{aligned}

Это уравнение оптимальности Беллмана для функции значения состояния.

Для функции ценности действия оптимальное уравнение Беллмана выглядит следующим образом:

\begin{aligned} q_{*}(s,a)=&E[R_{t+1}+\gamma \max_{a'}q_*(S_{t+1},a')\;|\;S_t=s,A_t=a] \\ =& \sum_{s',r}p(s',r|s,a)[r+\gamma \max_{a'}q_*(s',a')] \end{aligned}

Ссылаться на

Саттон Барто Обучение с подкреплением (второе издание)