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

Определение:

Обучение с подкреплением (англ. reinforcement learning) — способ машинного обучения, при котором система обучается, взаимодействуя с некоторой средой.

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

В обучении с подкреплением существует агент (agent) взаимодействует с окружающей средой (environment), предпринимая действия (actions). Окружающая среда дает награду (reward) за эти действия, а агент продолжает их предпринимать.

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

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

При обучении с подкреплением, в отличии от обучения с учителем, не предоставляются верные пары "входные данные-ответ", а принятие субоптимальнх решений (дающих локальный экстремум) не ограничивается явно. Обучение с подкреплением пытается найти компромисс между исследованием неизученных областей и применением имеющихся знаний (exploration vs exploitation). Баланс изучения-применения при обучении с подкреплением исследуется в задаче о многоруком бандите.

Формально простейшая модель обучения с подкреплением состоит из:

• множества состояний окружения (states) [math]S[/math]
• множества действий (actions) [math]A[/math]
• множества вещественнозначных скалярных "выигрышей" (rewards)

В произвольный момент времени [math]t[/math] агент характеризуется состоянием [math]s_t \in S[/math] и множеством возможных действий [math]A(s_t)[/math]. Выбирая действие [math]a \in A(s_t)[/math], он переходит в состояние [math]s_{t+1}[/math] и получает выигрыш [math]r_t[/math]. Основываясь на таком взаимодействии с окружающей средой, агент, обучающийся с подкреплением, должен выработать стратегию [math]\pi: S \to A[/math], которая максимизирует величину [math]R=r_0 + r_1+\cdots+r_n[/math] в случае МППР, имеющего терминальное состояние, или величину:

[math]R=\sum_t \gamma^t r_t[/math]

для МППР без терминальных состояний (где [math]0 \leq \gamma \leq 1[/math] — дисконтирующий множитель для "предстоящего выигрыша").

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

Постановка задачи обучения с подкреплением

Взаимодействие агента со средой

[math]S[/math] — множество состояний среды

Игра агента со средой:

• инициализация стратегии [math]\pi_1(a | s)[/math] и состояния среды [math]s_1[/math]
• для всех [math]t = 1 \ldots T[/math]
  • агент выбирает действие [math]a_t ∼ \pi_t(a | s_t)[/math]
  • среда генерирует награду [math]r_{t + 1} ∼ p(r | a_t, s_t)[/math] и новое состояние [math]s_{t + 1} ∼ p(s | a_t, s_t)[/math]
  • агент корректирует стратегию [math]\pi_{t + 1}(a | s)[/math]

Это марковский процесс принятия решений (МППР), если [math]P(s_{t+1} = s′, r_{t+1} = r | s_t, a_t, r_t, s_{t−1}, a_{t−1}, r_{t−1}, .. ,s_1, a_1) = P(s_{t+1} = s′,r_{t+1} = r | s_t, a_t)[/math]

МППР называется финитным, если [math]|A| \lt \infty[/math], [math]|S| \lt \infty[/math]

Алгоритмы

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

Наивный подход к решению этой задачи подразумевает следующие шаги:

• опробовать все возможные стратегии
• выбрать стратегию с наибольшим ожидаемым выигрышем

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

Подход с использованием функции полезности использует множество оценок ожидаемого выигрыша только для одной стратегии [math]\pi[/math] (либо текущей, либо оптимальной). При этом пытаются оценить либо ожидаемый выигрыш, начиная с состояния [math]s[/math], при дальнейшем следовании стратегии [math]\pi[/math],

[math]V(s) = E[R|s, \pi][/math],

либо ожидаемый выигрыш, при принятии решения [math]a[/math] в состоянии [math]s[/math] и дальнейшем соблюдении [math]\pi[/math],

[math]Q(s, a) = E[R|s, \pi, a][/math].

Если для выбора оптимальной стратегии используется функция полезности [math]Q[/math], то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.

Если же мы пользуемся функцией [math]V[/math], необходимо либо иметь модель окружения в виде вероятностей [math]P(s'|s, a)[/math], что позволяет построить функцию полезности вида

[math]Q(s, a) = \sum_{s'}V(s')P(s'|s, a)[/math],

либо применить т.н. метод исполнитель-критик, в котором модель делится на две части: критик, оценивающий полезность состояния [math]V[/math], и исполнитель, выбирающий подходящее действие в каждом состоянии.

Имея фиксированную стратегию [math]\pi[/math], оценить [math]E[R|\cdot][/math] при [math]\gamma = 1[/math] можно просто усреднив непосредственные выигрыши. Наиболее очевидный способ оценки при [math]\gamma \in (0, 1)[/math] — усреднить суммарный выигрыш после каждого состояния. Однако для этого требуется, чтобы МППР достиг терминального состояния (завершился).

Поэтому построение искомой оценки при [math]\gamma \in (0, 1)[/math] неочевидно. Однако, можно заметить, что [math]R[/math] образуют рекурсивное уравнение Беллмана:

[math]E[R|s_t]=r_t + \gamma E[R|s_{t+1}][/math].

Подставляя имеющиеся оценки, [math]V[/math], и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму обучения с временными воздействиями (temporal difference (TD) learning). В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.

Другие похожие методы: Адаптивный эвристический критик (Adaptive Heuristic Critic, AHC), SARSA и Q-обучение (Q-learning).

Задача о многоруком бандите (The multi-armed bandit problem)

Многорукий бандит

Формулировка

[math]A[/math] — множество возможных действий (ручек автомата)

[math]p_a(r)[/math] — неизвестное распределение награды [math]r \in R[/math] [math]\forall a \in A[/math]

[math]\pi_t(a)[/math] — стратегия агента в момент [math]t[/math] [math]\forall a \in A[/math]

Игра агента со средой:

• инициализация стратегии [math]\pi_1(a)[/math]
• для всех [math]t = 1 \ldots T[/math]
  • агент выбирает действие (ручку) [math]a_t ∼ \pi_t(a)[/math]
  • среда генерирует награду [math]r_t ∼ p_{a_t}(r)[/math]
  • агент корректирует стратегию [math]\pi_{t+1}(a)[/math]

[math]Q_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i = a]}} \rightarrow max [/math] — средняя награда в t играх
[math]Q^∗(a) = \lim \limits_{t \rightarrow \infty} Q_t(a) \rightarrow max [/math] — ценность действия [math]a[/math]

У нас есть автомат — [math]N[/math]-рукий бандит, на каждом шаге мы выбираем за какую из [math]N[/math] ручек автомата дернуть, т.е. множество действий [math]A = {1,2 \ldots ,N}[/math].

Выбор действия [math]a_t[/math] на шаге [math]t[/math] влечет награду [math]R(a_t)[/math] при этом [math]R(a)[/math] [math]\forall a \in A[/math] есть случайная величина, распределение которой неизвестно.

Состояние среды у нас от шага к шагу не меняется, а значит множество состояний [math]S[/math] тривиально, ни на что не влияет, поэтому его можно проигнорировать.

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

Проблема в том, что распределения неизвестны, однако можно оценить математическое ожидание некоторой случайной величины [math]\xi[/math] c неизвестным распределением. Для [math]K[/math] экспериментов [math]\xi_k[/math], оценка математического ожидания это среднее арифметическое результатов экспериментов:

[math]E(\xi) = \frac{1}{K} \sum_{k=1}^{K}{\xi_k} [/math]

Задача является модельной для понимания конфликта между exploitation-exploration.

Жадные и [math]\epsilon[/math]-жадные стратегии (greedy & [math]\epsilon[/math]-greedy)

Жадная (greedy) стратегия

• [math]P_a = 0[/math] [math]\forall a \in \{1 \ldots N\} [/math] — сколько раз было выбрано действие [math]a[/math]

• [math]Q_a = 0[/math] [math]\forall a \in \{1 \ldots N\}[/math] — текущая оценка математического ожидания награды для действия [math]a[/math]

На каждом шаге [math]t[/math]

• Выбираем действие с максимальной оценкой математического ожидания:

[math]a_t = argmax_{a \in A} Q_a [/math]

• Выполняем действие [math]a_t[/math] и получаем награду [math]R(a_t)[/math]

• Обновляем оценку математического ожидания для действия [math]a_t[/math]:

[math]P_{a_t} = P_{a_t} + 1[/math]

[math]Q_{a_t} = Q_{a_t} + \frac{1}{P_{a_t}} (R(a_t) − Q_{a_t})[/math]

В чем проблема?

Пусть у нас есть "двурукий" бандит. Первая ручка всегда выдаёт награду равную 1, вторая всегда выдаёт 2. Действуя согласно жадной стратегии мы дёрнем в начале первую ручку, так как в начале оценки математических ожиданий равны нулю, увеличим её оценку до [math]Q_1 = 1[/math]. В дальнейшем всегда будем выбирать первую ручку, а значит на каждом шаге будем получать на 1 меньше, чем могли бы.

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

[math]\epsilon[/math]-жадная ([math]\epsilon[/math]-greedy) стратегия

Пример. Награда для стратегии с различными [math]\epsilon[/math]

Введем параметр [math]\epsilon \in (0,1)[/math]

На каждом шаге [math]t[/math]

• Получим значение [math]\alpha[/math] — случайной величины равномерно распределенной на отрезке [math](0, 1)[/math]
• Если [math]\alpha \in (0, \epsilon)[/math], то выберем действие [math]a_t \in A[/math] случайно и равновероятно, иначе как в жадной стратегии выберем действие с максимальной оценкой математического ожидания:
• Обновляем оценки так же как в жадной стратегии

Если [math]\epsilon = 0[/math], то это обычная жадная стратегия. Однако если [math]\epsilon \gt 0[/math], то в отличии от жадной стратегии на каждом шаге с вероятностью [math]\epsilon[/math] присходит "исследование" случайных действий.

Стратегия Softmax

Основная идея алгоритма softmax — уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше [math]Q_t(a)[/math], тем больше вероятность выбора [math]a[/math]:

[math]\pi_{t+1}(a) = \frac{exp(Q_t(a) / \tau)}{\sum\limits_{b \in A} {exp(Q_t(b) / \tau)}}[/math]

[math]\tau \in (0, \infty)[/math] — параметр, с помощью которого можно настраивать поведение алгоритма.

При [math]\tau \rightarrow \infty[/math] стратегия стремится к равномерной, то есть softmax будет меньше зависеть от значения выигрыша и выбирать действия более равномерно (exploration).

При [math]\tau \rightarrow 0[/math] стратегия стремится к жадной, то есть алгоритм будет больше ориентироваться на известный средний выигрыш действий (exploitation).

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

Эвристика: параметр [math]\tau[/math] имеет смысл уменьшать со временем.

Метод UCB (upper confidence bound)

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

Алгоритм верхнего доверительного интервала (upper confidence bound или UCB) — семейство алгоритмов, которые пытаются решить эту проблему, используя при выборе данные не только о среднем выигрыше, но и о том, насколько можно доверять значениям выигрыша.

Также как softmax в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша:

[math]\pi_{t+1}(a) = Q_t(a) + b_a[/math]

[math]b_a = \sqrt{\frac{2 \ln{\sum_a P_a}}{P_a}} [/math] — бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными.

Доказательство здесь

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

Несмотря на это отсутствие случайности результаты работы этого алгоритма выглядят довольно шумно по сравнению с остальными. Это происходит из-за того, что данный алгоритм сравнительно часто выбирает недоисследованные действия.

Q-learning

На основе получаемого от среды вознаграждения агент формирует функцию полезности [math]Q[/math], что впоследствии дает ему возможность уже не случайно выбирать стратегию поведения, а учитывать опыт предыдущего взаимодействия со средой. Одно из преимуществ [math]Q[/math]-обучения — то, что оно в состоянии сравнить ожидаемую полезность доступных действий, не формируя модели окружающей среды. Применяется для ситуаций, которые можно представить в виде МППР.

Таким образом, алгоритм это функция качества от состояния и действия:

[math]Q: S \times A \to \mathbb{R}[/math]

Перед обучением [math]Q[/math] инициализируется случайными значениями. После этого в каждый момент времени [math]t[/math] агент выбирает действие [math]a_t[/math], получает награду [math]r_t[/math], переходит в новое состояние [math]s_{t+1}[/math], которое может зависеть от предыдущего состояния [math]s_t[/math] и выбранного действия, и обновляет функцию [math]Q[/math]. Обновление функции использует взвешенное среднее между старым и новым значениями:

[math]Q^{new}(s_{t},a_{t}) \leftarrow (1-\alpha) \cdot \underbrace{Q(s_{t},a_{t})}_{\text{old value}} + \underbrace{\alpha}_{\text{learning rate}} \cdot \overbrace{\bigg( \underbrace{r_{t}}_{\text{reward}} + \underbrace{\gamma}_{\text{discount factor}} \cdot \underbrace{\max_{a}Q(s_{t+1}, a)}_{\text{estimate of optimal future value}} \bigg) }^{\text{learned value}} [/math],

где [math]r_{t}[/math] это награда, полученная при переходе из состояния [math]s_{t}[/math] в состояние [math]s_{t+1}[/math], и [math]\alpha[/math] это скорость обучения ([math]0 \lt \alpha \le 1[/math]).

Алгоритм заканчивается, когда агент переходит в терминальное состояние [math]s_{t+1}[/math].

Aлгоритм Q-learning

Процесс Q-обучения

• [math]S[/math] — множество состояний
• [math]A[/math] — множество действий
• [math]R = S \times A \rightarrow \mathbb{R}[/math] — функция награды
• [math]T = S \times A \rightarrow S[/math] — функция перехода
• [math]\alpha \in [0, 1][/math] — learning rate (обычно 0.1), чем он выше, тем сильнее агент доверяет новой информации
• [math]\gamma \in [0, 1][/math] — discounting factor, чем он меньше, тем меньше агент задумывается о выгоде от будущих своих действий

fun Q-learning([math]S, A, R, T, \alpha, \gamma[/math]):
   for [math] s \in S[/math]:
       for [math] a \in A[/math]:
            Q(s, a) = rand()
   while Q is not converged:
       s = [math] \forall s \in S[/math]
       while s is not terminal:
          [math]\pi(s) = argmax_{a}{Q(s, a)}[/math]
          a = [math]\pi(s)[/math]
          r = R(s, a)
          s' = T(s, a)
          [math]Q(s', a) = (1 - \alpha) Q(s', a) + \alpha (r + \gamma \max\limits_{a'}{Q(s', a')})[/math]
          s = s'
   return Q

Policy gradient и алгоритм Actor-Critic

В алгоритме Q-learning агент обучает функцию полезности действия [math]Q_{\theta}(s, a)[/math]. Стратегия агента [math]\pi_{\theta}(a|s)[/math] определяется согласно текущим значениям [math]Q(s, a)[/math], с использованием жадного, [math]\varepsilon[/math]-жадного или softmax подхода. Однако, существуют методы, которые позволяют оптимизировать стратегию [math]\pi_{\theta}(s|a)[/math] напрямую. Такие алгоритмы относятся к классу алгоритмов policy gradient.

Простой policy gradient алгоритм (REINFORCE)

Рассмотрим МППР, имеющий терминальное состояние: задача - максимизировать сумму всех выигрышей [math]R=r_0 + r_1+\cdots+r_T[/math], где T - шаг, на котором произошел переход в терминальное состояние.

Будем использовать букву [math]\tau[/math] для обозначения некоторого сценария - последовательности состояний и произведенных в них действий: [math]\tau = (s_1, a_1, s_2, a_2, ... s_T, a_T)[/math]. Будем обозначать сумму всех выигрышей, полученных в ходе сценария, как [math]R_{\tau} = \sum_{\tau} {r(s_t, a_t)}[/math].

Не все сценарии равновероятны. Вероятность реализации сценария зависит от поведения среды, которое задается вероятностями перехода между состояниями [math]p(s_{t+1}|s_{t}, a_{t})[/math] и распределением начальных состояний [math]p(s_1)[/math], и поведения агента, которое определяется его стохастической стратегией [math]\pi_{\theta}(a_t|s_t)[/math]. Вероятностное распределение над сценариями, таким образом, задается как

[math]p_{\theta}(\tau) = p_{\theta}(s_1, a_1, ... s_T, a_T) = p(s_1) \prod_{t=1}^{T} {\pi_{\theta}(a_t|s_t) p(s_{t+1}|s_t, a_t)}[/math]

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

[math]J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ R_{\tau} \right] = \int {p_{\theta}(\tau) R_{\tau} d\tau}[/math]

Рассмотрим градиент оптимизируемой функции [math]\nabla_{\theta} J(\theta)[/math]:

[math]\nabla_{\theta} J(\theta) = \int {\nabla_{\theta}p_{\theta}(\tau) R_{\tau} d\tau} [/math]

Считать градиент [math]\nabla_{\theta}p_{\theta}(\tau)[/math] непосредственно сложно, потому что что [math]p_{\theta}(\tau)[/math] - это большое произведение. Однако, так как

[math]p_{\theta}(\tau) \nabla_{\theta} \log p_{\theta}(\tau) = p_{\theta}(\tau) \frac{\nabla_{\theta}p_{\theta}(\tau)}{p_{\theta}(\tau)} = \nabla_{\theta}p_{\theta}(\tau)[/math]

, мы можем заменить [math]\nabla_{\theta}p_{\theta}(\tau)[/math] на [math]p_{\theta}(\tau) \nabla_{\theta} \log p_{\theta}(\tau)[/math]:

[math]\nabla_{\theta} J(\theta) = \int {p_{\theta}(\tau) \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} d\tau} = E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right][/math]

Рассмотрим [math]\log p_{\theta}(\tau)[/math]:

[math] \log p_{\theta}(\tau) = \log \left( p(s_1) \prod_{t=1}^{T} {\pi_{\theta}(a_t|s_t) p(s_{t+1}|s_t, a_t)} \right) = \log p(s_1) + \sum_{t=1}^{T} {\left( \log \pi_{\theta}(a_t|s_t) + \log p(s_{t+1}|s_t, a_t) \right)} [/math]

Тогда:

[math] \nabla_{\theta} \log p_{\theta}(\tau) = \underbrace{\nabla_{\theta} \log p(s_1)}_{=0} + \sum_{t=1}^{T} {\left( \nabla_{\theta} \log \pi_{\theta}(a_t|s_t) + \underbrace{\nabla_{\theta} \log p(s_{t+1}|s_t, a_t)}_{=0} \right)} = \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} [/math]

Подставляя в определение [math]\nabla_{\theta} J(\theta)[/math]:

[math] \nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ \left( \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} \right) R_{\tau} \right] [/math]

Схема алгоритма REINFORCE

Как мы можем подсчитать это матожидание? С помощью семплирования (метод Монте-Карло). Если у нас есть N уже известных сценариев [math]\tau^i = (s_1^i, a_1^i, ... s_{T^i}^i, a_{T^i}^i)[/math], то мы можем приблизить матожидание функции от сценария средним арифметическим этой функции по всему множеству сценариев:

[math] \nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^N { \left( \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t^i|s_t^i)} \right) R_{\tau^i}} = \frac{1}{N} \sum_{i=1}^N { \left( \sum_{t=1}^{T^i} {\nabla_{\theta} \log \pi_{\theta}(a_t^i|s_t^i)} \right) \left( \sum_{t=1}^{T^i} { r(s_t^i, a_t^i) } \right)} [/math]

Таким образом, оптимизировать [math]J(\theta)[/math] можно с помощью следующего простого алгоритма (REINFORCE):

1. Прогнать N сценариев [math]\tau_i[/math] со стратегией [math]\pi_{\theta}(a|s)[/math]
2. Посчитать среднее арифметическое [math]\nabla_{\theta} J(\theta) \leftarrow \frac{1}{N} \sum_{i=1}^N { \left( \sum_{t=1}^{T^i} {\nabla_{\theta} \log \pi_{\theta}(a_t^i|s_t^i)} \right) \left( \sum_{t=1}^{T^i} { r(s_t^i, a_t^i) } \right)}[/math]
3. [math] \theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta)[/math]

Интуитивное объяснение принципа работы

Иллюстрация выбора наилучшего сценария

[math]p_{\theta}(\tau)[/math] - это вероятность того, что будет реализован сценарий [math]\tau[/math] при условии параметров модели [math]\theta[/math], т. е. функция правдоподобия. Нам хочется увеличить правдоподобие "хороших" сценариев (обладающих высоким [math]R_{\tau}[/math]) и понизить правдоподобие "плохих" сценариев (с низким [math]R_{\tau}[/math]).

Взглянем еще раз на полученное определение градиента функции полного выигрыша:

[math]\nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right][/math]

Двигаясь вверх по этому градиенту, мы повышаем логарифм функции правдоподобия для сценариев, имеющих большой положительный [math]R_{\tau}[/math].

Преимущества и недостатки policy gradient по сравнению с Q-learning

Преимущества:

• Легко обобщается на задачи с большим множеством действий, в том числе на задачи с непрерывным множеством действий.
• По большей части избегает конфликта между exploitation и exploration, так как оптимизирует напрямую стохастическую стратегию [math]\pi_{\theta}(a|s)[/math].
• Имеет более сильные гарантии сходимости: если Q-learning гарантированно сходится только для МППР с конечными множествами действий и состояний, то policy gradient, при достаточно точных оценках [math]\gt \nabla_{\theta} J(\theta)[/math] (т. е. при достаточно больших выборках сценариев), сходится к локальному оптимуму всегда, в том числе в случае бесконечных множеств действий и состояний, и даже для частично наблюдаемых Марковских процессов принятия решений (POMDP).

Недостатки:

• Очень низкая скорость работы -- требуется большое количество вычислений для оценки [math]\nabla_{\theta} J(\theta)[/math] по методу Монте-Карло, так как:
  • для получения всего одного семпла требуется произвести [math]T[/math] взаимодействий со средой;
  • случайная величина [math]\nabla_{\theta} \log p_{\theta}(\tau) R_{\tau}[/math] имеет большую дисперсию, так как для разных [math]\tau[/math] значения [math]R_{\tau}[/math] могут очень сильно различаться, поэтому для точной оценки [math]\nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right][/math] требуется много семплов;
  • cемплы, собранные для предыдущих значений [math]\theta[/math], никак не переиспользуются на следующем шаге, семплирование нужно делать заново на каждом шаге градиентного спуска.
• В случае конечных МППР Q-learning сходится к глобальному оптимуму, тогда как policy gradient может застрять в локальном.

Далее мы рассмотрим способы улучшения скорости работы алгоритма.

Усовершенствования алгоритма

Опорные значения

Заметим, что если [math]b[/math] - константа относительно [math]\tau[/math], то

[math]E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) (R_{\tau} - b) \right] = E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right] [/math]

, так как

[math]E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) b \right] = \int {p_{\theta}(\tau) \nabla_{\theta} \log p_{\theta}(\tau) b d\tau} = \int {\nabla_{\theta} p_{\theta}(\tau) b d\tau} = b \nabla_{\theta} \int {p_{\theta}(\tau) d\tau} = b \nabla_{\theta} 1 = 0[/math]

Таким образом, изменение [math]R_{\tau}[/math] на константу не меняет оценку [math]\nabla_{\theta} J(\theta)[/math]. Однако дисперсия [math] Var_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) (R_{\tau} - b) \right][/math] зависит от [math]b[/math]:

[math] Var_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) (R_{\tau} - b) \right] = \underbrace{E_{\tau \sim p_{\theta}(\tau)} \left[ \left( \nabla_{\theta} \log p_{\theta}(\tau) (R_{\tau} - b) \right)^2 \right]}_{\text{depends on } b} - \underbrace{E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) (R_{\tau} - b) \right]^2}_{= E \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right]^2} [/math]

, поэтому, регулируя [math]b[/math], можно достичь более низкой дисперсии, а значит, более быстрой сходимости Монте-Карло к истинному значению [math]\nabla_{\theta} J(\theta)[/math]. Значение [math]b[/math] называется опорным значением. Способы определения опорных значений будут рассмотрены далее.

Использование будущего выигрыша вместо полного выигрыша

Рассмотрим еще раз выражение для градиента полного выигрыша:

[math] \nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ \left( \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} \right) R_{\tau} \right] = E_{\tau \sim p_{\theta}(\tau)} \left[ \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} \left( \sum_{t=1}^{T} {r(s_t, a_t)} \right) \right][/math]

Так как в момент времени [math]t[/math] от действия [math]a_t[/math] зависят только [math]r(s_{t'}, a_{t'})[/math] для [math] t' \leq t[/math], это выражение можно переписать как

[math] \nabla_{\theta} J(\theta) \approx E_{\tau \sim p_{\theta}(\tau)} \left[ \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} \underbrace{\left( \sum_{t'=t}^{T} {r(s_t', a_t')} \right)}_{= Q_{\tau, t}} \right][/math]

Величина [math]Q_{\tau, t}[/math] -- будущий выигрыш (reward-to-go) на шаге [math]t[/math] в сценарии [math]\tau[/math]

Алгоритм Actor-Critic

Из предыдущего абзаца:

[math]\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t^i|s_t^i) Q_{\tau_i, t} } [/math]

Здесь [math]Q_{\tau_i, t}[/math] -- это оценка будущего выигрыша из состояния [math]s_t^i[/math] при условии действия [math]a_t^i[/math], которая базируется только на одном сценарии [math]\tau_i[/math]. Это плохое приближение ожидаемого будущего выигрыша -- истинный ожидаемый будущий выигрыш выражается формулой

[math] Q^{\pi}(s_t, a_t) = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'} | s_t, a_t] } [/math]

Также, в целях уменьшения дисперсии случайной величины, введем опорное значение для состояния [math]s_t[/math], которое назовем ожидаемой ценностью (value) этого состояния. Ожидаемая ценность состояния [math]s_t[/math] -- это ожидаемый будущий выигрыш при совершении некоторого действия в этом состоянии согласно стратегии [math]\pi_{\theta}(a|s)[/math]:

[math] V^{\pi}(s_t) = E_{a_t \sim \pi_{\theta}(a_t | s_t)} [Q^{\pi}(s_t, a_t)] = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'} | s_t]}[/math]

Таким образом, вместо ожидаемого будущего выигрыша при оценке [math]\nabla_{\theta} J(\theta)[/math] будем использовать функцию преимущества (advantage):

[math] A^{\pi}(s_t, a_t) = Q^{\pi}(s_t, a_t) - V^{\pi}(s_t) [/math]

Преимущество действия [math]a_t[/math] в состоянии [math]s_t[/math] -- это величина, характеризующая то, насколько выгоднее в состоянии [math]s_t[/math] выбрать именно действие [math]a_t[/math].

Итого:

[math] \nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t^i|s_t^i) A^{\pi}(s_t^i, a_t^i) } [/math]

Как достаточно точно и быстро оценить [math]A^{\pi}(s_t^i, a_t^i)[/math]? Сведем задачу к оценке [math]V^{\pi}(s_t)[/math]:

[math] Q^{\pi}(s_t, a_t) = r(s_t, a_t) + E_{s_{t+1} \sim p(s_{t+1} | s_t, a_t)} [V^{\pi}(s_{t+1})] \approx r(s_t, a_t) + V^{\pi}(s_{t+1}) [/math]

[math] A^{\pi}(s_t^i, a_t^i) = Q^{\pi}(s_t, a_t) - V^{\pi}(s_t) \approx r(s_t, a_t) + V^{\pi}(s_{t+1}) - V^{\pi}(s_t) [/math]

Теперь нам нужно уметь оценивать [math]V^{\pi}(s_t) = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'} | s_t] }[/math]. Мы можем делать это, опять же, с помощью метода Монте-Карло -- так мы получим несмещенную оценку. Но это будет работать не существенно быстрее, чем обычный policy gradient. Вместо этого заметим, что при фиксированных [math]s_t[/math] и [math]a_t[/math] выполняется:

[math] V^{\pi}(s_t) = r(s_t, a_t) + V^{\pi}(s_{t+1})[/math]

Таким образом, если мы имеем некоторую изначальную оценку [math]V^{\pi}(s)[/math] для всех [math]s[/math], то мы можем обновлять эту оценку путем, аналогичным алгоритму Q-learning:

[math] V^{\pi}(s_t) \leftarrow (1 - \beta) V^{\pi}(s_t) + \beta (r(s_t, a_t) + V^{\pi}(s_{t+1})) [/math]

Такой пересчет мы можем производить каждый раз, когда агент получает вознаграждение за действие.

Ссылки

• Wikipedia: Reinforcement learning
• Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 135. Cambridge: MIT press, 1998.
• Sutton R. S., Barto A. G. Reinforcement learning: An introduction. – 2011.
• Обучение с подкреплением
• Многорукий бандит
• Задача о многоруком бандите
• Обучение с подкреплением (Reinforcement Learning) К.В.Воронцов
• Обзор книги «Bandit Algorithms for Website Optimization»
• Q-learning
• An introduction to Q-Learning: reinforcement learning
• Policy Gradients. CS 294-112: Deep Reinforcement Learning, Sergey Levine.
• Actor-Critic Algorithms. CS 294-112: Deep Reinforcement Learning, Sergey Levine.