Формально простейшая модель обучения с подкреплением состоит из:
* множества состояний окружения (''states'') <tex>S</tex>;* множества действий (''actions'') <tex>A</tex>;* множества вещественнозначных скалярных "выигрышей" (''rewards'').
В произвольный момент времени <tex>t</tex> агент характеризуется состоянием <tex>s_t \in S</tex> и множеством возможных действий <tex>A(s_t)</tex>.
Основываясь на таком взаимодействии с окружающей средой, агент, обучающийся с подкреплением, должен выработать стратегию <tex>\pi: S \to A</tex>, которая максимизирует величину <tex>R=r_0 + r_1+\cdots+r_n</tex> в случае МППР, имеющего терминальное состояние, или величину:
::<tex>R=\sum_t \gamma^t r_t</tex>,
для МППР без терминальных состояний (где <tex>0 \leq \gamma \leq 1</tex> {{---}} дисконтирующий множитель для "предстоящего выигрыша").
Игра агента со средой:
* инициализация стратегии <tex>\pi_1(a | s)</tex> и состояния среды <tex>s_1</tex>;* для всех <tex>t = 1 \ldots T</tex>:** агент выбирает действие <tex>a_t ∼ \pi_t(a | s_t)</tex>;** среда генерирует награду <tex>r_{t + 1} ∼ p(r | a_t, s_t)</tex> и новое состояние <tex>s_{t + 1} ∼ p(s | a_t, s_t)</tex>;** агент корректирует стратегию <tex>\pi_{t + 1}(a | s)</tex>.
Это марковский процесс принятия решений (МППР), если
<tex>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)</tex>,
МППР называется финитным, если <tex>|A| < \infty</tex>, <tex>|S| < \infty</tex>
Наивный подход к решению этой задачи подразумевает следующие шаги:
* опробовать все возможные стратегии;* выбрать стратегию с наибольшим ожидаемым выигрышем.
Первая проблема такого подхода заключается в том, что количество доступных стратегий может быть очень велико или бесконечно.
либо ожидаемый выигрыш, при принятии решения <tex>a</tex> в состоянии <tex>s</tex> и дальнейшем соблюдении <tex>\pi</tex>,
::<tex>Q(s, a) = E[R|s, \pi, a]</tex>.,
Если для выбора оптимальной стратегии используется функция полезности <tex>Q</tex>, то оптимальные действия всегда можно выбрать как действия, максимизирующие полезность.
Поэтому построение искомой оценки при <tex>\gamma \in (0, 1)</tex> неочевидно. Однако, можно заметить, что <tex>R</tex> образуют рекурсивное уравнение Беллмана:
::<tex>E[R|s_t]=r_t + \gamma E[R|s_{t+1}]</tex>.,
Подставляя имеющиеся оценки, <tex>V</tex>, и применяя метод градиентного спуска с квадратичной функцией ошибок, мы приходим к алгоритму [http://en.wikipedia.org/wiki/Temporal_difference_learning обучения с временными воздействиями] (''temporal difference (TD) learning'').
В простейшем случае и состояния, и действия дискретны и можно придерживаться табличных оценок для каждого состояния.
=== Формулировка ===
<tex>A</tex> {{---}} множество возможных ''действий'' (ручек автомата),
<tex>p_a(r)</tex> {{---}} неизвестное распределение ''награды'' <tex>r \in R</tex> <tex>\forall a \in A</tex>,
<tex>\pi_t(a)</tex> {{---}} ''стратегия'' агента в момент <tex>t</tex> <tex>\forall a \in A</tex>.
Игра агента со средой:
* инициализация стратегии <tex>\pi_1(a)</tex>;* для всех <tex>t = 1 \ldots T</tex>:** агент выбирает действие (ручку) <tex>a_t ∼ \pi_t(a)</tex>;** среда генерирует награду <tex>r_t ∼ p_{a_t}(r)</tex>;** агент корректирует стратегию <tex>\pi_{t+1}(a)</tex>.
<tex>Q_t(a) = \frac{\sum^{t}_{i=1}{r_i[a_i = a]}}{\sum^{t}_{i=1}{[a_i = a]}} \rightarrow max </tex> {{---}} средняя награда в <i>t</i> играх <br />,<tex>Q^∗(a) = \lim \limits_{t \rightarrow \infty} Q_t(a) \rightarrow max </tex> {{---}} ценность действия <tex>a</tex>.
У нас есть автомат {{---}} <tex>N</tex>-рукий бандит, на каждом шаге мы выбираем за какую из <tex>N</tex> ручек автомата дернуть,
Проблема в том, что распределения неизвестны, однако можно оценить математическое ожидание некоторой случайной величины <tex>\xi</tex> c неизвестным распределением. Для <tex>K</tex> экспериментов <tex>\xi_k</tex>, оценка математического ожидания это среднее арифметическое результатов экспериментов:
<tex>E(\xi) = \frac{1}{K} \sum_{k=1}^{K}{\xi_k} </tex>,
Задача является модельной для понимания конфликта между ''exploitation''-''exploration''.
==== Жадная (''greedy'') стратегия ====
* <tex>P_a = 0</tex> <tex>\forall a \in \{1 \ldots N\} </tex> {{---}} сколько раз было выбрано действие <tex>a</tex>,
* <tex>Q_a = 0</tex> <tex>\forall a \in \{1 \ldots N\}</tex> {{---}} текущая оценка математического ожидания награды для действия <tex>a</tex>.
На каждом шаге <tex>t</tex>
* Выбираем действие с максимальной оценкой математического ожидания:
:<tex>a_t = argmax_{a \in A} Q_a </tex>,
* Выполняем действие <tex>a_t</tex> и получаем награду <tex>R(a_t)</tex>;
* Обновляем оценку математического ожидания для действия <tex>a_t</tex>:
:<tex>P_{a_t} = P_{a_t} + 1</tex>,
:<tex>Q_{a_t} = Q_{a_t} + \frac{1}{P_{a_t}} (R(a_t) − Q_{a_t})</tex>.
В чем проблема?
[[File:Eps-greedy.png|thumb|313px|link=https://vbystricky.github.io/2017/01/rl_multi_arms_bandits.html|Пример. Награда для стратегии с различными <tex>\epsilon</tex>]]
Введем параметр <tex>\epsilon \in (0,1)</tex>.
На каждом шаге <tex>t</tex>
* Получим значение <tex>\alpha</tex> {{---}} случайной величины равномерно распределенной на отрезке <tex>(0, 1)</tex>;* Если <tex>\alpha \in (0, \epsilon)</tex>, то выберем действие <tex>a_t \in A</tex> случайно и равновероятно, иначе как в жадной стратегии выберем действие с максимальной оценкой математического ожидания:;* Обновляем оценки так же как в жадной стратегии.
Если <tex>\epsilon = 0</tex>, то это обычная жадная стратегия. Однако если <tex>\epsilon > 0</tex>, то в отличии от жадной стратегии на каждом шаге с вероятностью <tex>\epsilon</tex> присходит "исследование" случайных действий.
Основная идея алгоритма ''softmax'' {{---}} уменьшение потерь при исследовании за счёт более редкого выбора действий, которые небольшую награду в прошлом. Чтобы этого добиться для каждого действия вычисляется весовой коэффициент на базе которого происходит выбор действия. Чем больше <tex>Q_t(a)</tex>, тем больше вероятность выбора <tex>a</tex>:
<tex>\pi_{t+1}(a) = \frac{exp(Q_t(a) / \tau)}{\sum\limits_{b \in A} {exp(Q_t(b) / \tau)}}</tex>,
<tex>\tau \in (0, \infty)</tex> {{---}} параметр, с помощью которого можно настраивать поведение алгоритма.
Также как ''softmax'' в UCB при выборе действия используется весовой коэффициент, который представляет собой верхнюю границу доверительного интервала (upper confidence bound) значения выигрыша:
<tex>\pi_{t+1}(a) = Q_t(a) + b_a</tex>,
<tex>b_a = \sqrt{\frac{2 \ln{\sum_a P_a}}{P_a}} </tex> {{---}} бонусное значение, которые показывает, насколько недоисследовано действие по сравнению с остальными.
Таким образом, алгоритм это функция качества от состояния и действия:
:<tex>Q: S \times A \to \mathbb{R}</tex>,
Перед обучением <tex>Q</tex> инициализируется случайными значениями. После этого в каждый момент времени <tex>t</tex> агент выбирает действие <tex>a_t</tex>, получает награду <tex>r_t</tex>, переходит в новое состояние <tex>s_{t+1}</tex>, которое может зависеть от предыдущего состояния <tex>s_t</tex> и выбранного действия, и обновляет функцию <tex>Q</tex>. Обновление функции использует взвешенное среднее между старым и новым значениями:
[[File:Q-Learning.png|thumb|313px|link=https://en.wikipedia.org/wiki/Q-learning|Процесс Q-обучения]]
* <tex>S</tex> — множество состояний,* <tex>A</tex> — множество действий,* <tex>R = S \times A \rightarrow \mathbb{R}</tex> {{---}} функция награды,* <tex>T = S \times A \rightarrow S</tex> {{---}} функция перехода,* <tex>\alpha \in [0, 1]</tex> {{---}} learning rate (обычно 0.1), чем он выше, тем сильнее агент доверяет новой информации,* <tex>\gamma \in [0, 1]</tex> {{---}} discounting factor, чем он меньше, тем меньше агент задумывается о выгоде от будущих своих действий.
'''fun''' Q-learning(<tex>S, A, R, T, \alpha, \gamma</tex>):
s = s'
return Q
== Policy gradient и алгоритм Actor-Critic ==
В алгоритме Q-learning агент обучает функцию полезности действия <tex>Q_{\theta}(s, a)</tex>. Стратегия агента <tex>\pi_{\theta}(a|s)</tex> определяется согласно текущим значениям <tex>Q(s, a)</tex>, с использованием жадного, <tex>\varepsilon</tex>-жадного или softmax подхода. Однако, существуют методы, которые позволяют оптимизировать стратегию <tex>\pi_{\theta}(s|a)</tex> напрямую. Такие алгоритмы относятся к классу алгоритмов ''policy gradient''.
=== Простой policy gradient алгоритм (REINFORCE) ===
Рассмотрим МППР, имеющий терминальное состояние: задача - максимизировать сумму всех выигрышей <tex>R=r_0 + r_1+\cdots+r_T</tex>, где T - шаг, на котором произошел переход в терминальное состояние.
Будем использовать букву <tex>\tau</tex> для обозначения некоторого ''сценария'' - последовательности состояний и произведенных в них действий: <tex>\tau = (s_1, a_1, s_2, a_2, ... s_T, a_T)</tex>. Будем обозначать сумму всех выигрышей, полученных в ходе сценария, как <tex>R_{\tau} = \sum_{\tau} {r(s_t, a_t)}</tex>.
Не все сценарии равновероятны. Вероятность реализации сценария зависит от поведения среды, которое задается вероятностями перехода между состояниями <tex>p(s_{t+1}|s_{t}, a_{t})</tex> и распределением начальных состояний <tex>p(s_1)</tex>, и поведения агента, которое определяется его стохастической стратегией <tex>\pi_{\theta}(a_t|s_t)</tex>. Вероятностное распределение над сценариями, таким образом, задается как
:<tex>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)}</tex>
Будем максимизировать матожидание суммы полученных выигрышей:
:<tex>J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ R_{\tau} \right] = \int {p_{\theta}(\tau) R_{\tau} d\tau}</tex>
Рассмотрим градиент оптимизируемой функции <tex>\nabla_{\theta} J(\theta)</tex>:
: <tex>\nabla_{\theta} J(\theta) = \int {\nabla_{\theta}p_{\theta}(\tau) R_{\tau} d\tau} </tex>
Считать градиент <tex>\nabla_{\theta}p_{\theta}(\tau)</tex> непосредственно сложно, потому что что <tex>p_{\theta}(\tau)</tex> - это большое произведение. Однако, так как
: <tex>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)</tex>
, мы можем заменить <tex>\nabla_{\theta}p_{\theta}(\tau)</tex> на <tex>p_{\theta}(\tau) \nabla_{\theta} \log p_{\theta}(\tau)</tex>:
: <tex>\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]</tex>
Рассмотрим <tex>\log p_{\theta}(\tau)</tex>:
: <tex> \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)} </tex>
Тогда:
: <tex> \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)} </tex>
Подставляя в определение <tex>\nabla_{\theta} J(\theta)</tex>:
: <tex> \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] </tex>
[[File:Policy-gradient-reinforce.png|thumb|313px|link=http://rll.berkeley.edu/deeprlcourse/f17docs/lecture_4_policy_gradient.pdf|Схема алгоритма REINFORCE]]
Как мы можем подсчитать это матожидание? С помощью семплирования (метод Монте-Карло). Если у нас есть N уже известных сценариев <tex>\tau^i = (s_1^i, a_1^i, ... s_{T^i}^i, a_{T^i}^i)</tex>, то мы можем приблизить матожидание функции от сценария средним арифметическим этой функции по всему множеству сценариев:
: <tex> \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)} </tex>
Таким образом, оптимизировать <tex>J(\theta)</tex> можно с помощью следующего простого алгоритма (REINFORCE):
# Прогнать N сценариев <tex>\tau_i</tex> со стратегией <tex>\pi_{\theta}(a|s)</tex>
# Посчитать среднее арифметическое <tex>\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)}</tex>
# <tex> \theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta)</tex>
=== Интуитивное объяснение принципа работы ===
[[File:Policy-gradient-trajectories.png|thumb|313px|link=http://rll.berkeley.edu/deeprlcourse/f17docs/lecture_4_policy_gradient.pdf|Иллюстрация выбора наилучшего сценария]]
<tex>p_{\theta}(\tau)</tex> - это вероятность того, что будет реализован сценарий <tex>\tau</tex> при условии параметров модели <tex>\theta</tex>, т. е. функция ''правдоподобия''. Нам хочется увеличить правдоподобие "хороших" сценариев (обладающих высоким <tex>R_{\tau}</tex>) и понизить правдоподобие "плохих" сценариев (с низким <tex>R_{\tau}</tex>).
Взглянем еще раз на полученное определение градиента функции полного выигрыша:
: <tex>\nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right]</tex>
Двигаясь вверх по этому градиенту, мы повышаем логарифм функции правдоподобия для сценариев, имеющих большой положительный <tex>R_{\tau}</tex>.
=== Преимущества и недостатки policy gradient по сравнению с Q-learning ===
Преимущества:
* Легко обобщается на задачи с большим множеством действий, в том числе на задачи с непрерывным множеством действий.
* По большей части избегает конфликта между exploitation и exploration, так как оптимизирует напрямую стохастическую стратегию <tex>\pi_{\theta}(a|s)</tex>.
* Имеет более сильные гарантии сходимости: если Q-learning гарантированно сходится только для МППР с конечными множествами действий и состояний, то policy gradient, при достаточно точных оценках <tex>>\nabla_{\theta} J(\theta)</tex> (т. е. при достаточно больших выборках сценариев), сходится к локальному оптимуму всегда, в том числе в случае бесконечных множеств действий и состояний, и даже для частично наблюдаемых Марковских процессов принятия решений (POMDP).
Недостатки:
* Очень низкая скорость работы -- требуется большое количество вычислений для оценки <tex>\nabla_{\theta} J(\theta)</tex> по методу Монте-Карло, так как:
** для получения всего одного семпла требуется произвести <tex>T</tex> взаимодействий со средой;
** случайная величина <tex>\nabla_{\theta} \log p_{\theta}(\tau) R_{\tau}</tex> имеет большую дисперсию, так как для разных <tex>\tau</tex> значения <tex>R_{\tau}</tex> могут очень сильно различаться, поэтому для точной оценки <tex>\nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) R_{\tau} \right]</tex> требуется много семплов;
** cемплы, собранные для предыдущих значений <tex>\theta</tex>, никак не переиспользуются на следующем шаге, семплирование нужно делать заново на каждом шаге градиентного спуска.
* В случае конечных МППР Q-learning сходится к глобальному оптимуму, тогда как policy gradient может застрять в локальном.
Далее мы рассмотрим способы улучшения скорости работы алгоритма.
=== Усовершенствования алгоритма ===
==== Опорные значения ====
Заметим, что если <tex>b</tex> - константа относительно <tex>\tau</tex>, то
: <tex>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] </tex>
, так как
: <tex>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</tex>
Таким образом, изменение <tex>R_{\tau}</tex> на константу не меняет оценку <tex>\nabla_{\theta} J(\theta)</tex>. Однако ''дисперсия'' <tex> Var_{\tau \sim p_{\theta}(\tau)} \left[ \nabla_{\theta} \log p_{\theta}(\tau) (R_{\tau} - b) \right]</tex> зависит от <tex>b</tex>:
: <tex> 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} </tex>
, поэтому, регулируя <tex>b</tex>, можно достичь более низкой дисперсии, а значит, более быстрой сходимости Монте-Карло к истинному значению <tex>\nabla_{\theta} J(\theta)</tex>. Значение <tex>b</tex> называется ''опорным значением''. Способы определения опорных значений будут рассмотрены далее.
==== Использование будущего выигрыша вместо полного выигрыша ====
Рассмотрим еще раз выражение для градиента полного выигрыша:
: <tex> \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]</tex>
Так как в момент времени <tex>t</tex> от действия <tex>a_t</tex> зависят только <tex>r(s_{t'}, a_{t'})</tex> для <tex> t' \leq t</tex>, это выражение можно переписать как
: <tex> \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]</tex>
Величина <tex>Q_{\tau, t}</tex> -- ''будущий выигрыш'' (reward-to-go) на шаге <tex>t</tex> в сценарии <tex>\tau</tex>
=== Алгоритм Actor-Critic ===
Из предыдущего абзаца:
: <tex>\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} } </tex>
Здесь <tex>Q_{\tau_i, t}</tex> -- это оценка будущего выигрыша из состояния <tex>s_t^i</tex> при условии действия <tex>a_t^i</tex>, которая базируется только на одном сценарии <tex>\tau_i</tex>. Это плохое приближение ожидаемого будущего выигрыша -- истинный ожидаемый будущий выигрыш выражается формулой
: <tex> Q^{\pi}(s_t, a_t) = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'}) | s_t, a_t] } </tex>
Также, в целях уменьшения дисперсии случайной величины, введем опорное значение для состояния <tex>s_t</tex>, которое назовем ''ожидаемой ценностью'' (value) этого состояния. Ожидаемая ценность состояния <tex>s_t</tex> -- это ожидаемый будущий выигрыш при совершении некоторого действия в этом состоянии согласно стратегии <tex>\pi_{\theta}(a|s)</tex>:
: <tex> 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]}</tex>
Таким образом, вместо ожидаемого будущего выигрыша при оценке <tex>\nabla_{\theta} J(\theta)</tex> будем использовать функцию ''преимущества'' (advantage):
: <tex> A^{\pi}(s_t, a_t) = Q^{\pi}(s_t, a_t) - V^{\pi}(s_t) </tex>
Преимущество действия <tex>a_t</tex> в состоянии <tex>s_t</tex> -- это величина, характеризующая то, насколько выгоднее в состоянии <tex>s_t</tex> выбрать именно действие <tex>a_t</tex>.
Итого:
: <tex> \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) } </tex>
Как достаточно точно и быстро оценить <tex>A^{\pi}(s_t^i, a_t^i)</tex>? Сведем задачу к оценке <tex>V^{\pi}(s_t)</tex>:
: <tex> 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}) </tex>
: <tex> 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) </tex>
Теперь нам нужно уметь оценивать <tex>V^{\pi}(s_t) = \sum_{t'=t}^{T} {E_{\pi_{\theta}} [r(s_{t'}, a_{t'}) | s_t] }</tex>. Мы можем делать это, опять же, с помощью метода Монте-Карло -- так мы получим несмещенную оценку. Но это будет работать не существенно быстрее, чем обычный policy gradient. Вместо этого заметим, что при фиксированных <tex>s_t</tex> и <tex>a_t</tex> выполняется:
: <tex> V^{\pi}(s_t) = r(s_t, a_t) + V^{\pi}(s_{t+1})</tex>
Таким образом, если мы имеем некоторую изначальную оценку <tex>V^{\pi}(s)</tex> для всех <tex>s</tex>, то мы можем обновлять эту оценку путем, аналогичным алгоритму Q-learning:
: <tex> V^{\pi}(s_t) \leftarrow (1 - \beta) V^{\pi}(s_t) + \beta (r(s_t, a_t) + V^{\pi}(s_{t+1})) </tex>
Такой пересчет мы можем производить каждый раз, когда агент получает вознаграждение за действие.
== Ссылки ==
* [https://en.wikipedia.org/wiki/Q-learning Q-learning]
* [https://medium.freecodecamp.org/an-introduction-to-q-learning-reinforcement-learning-14ac0b4493cc An introduction to Q-Learning: reinforcement learning]
* [http://rll.berkeley.edu/deeprlcourse/f17docs/lecture_4_policy_gradient.pdf Policy Gradients. CS 294-112: Deep Reinforcement Learning, Sergey Levine.]
* [http://rail.eecs.berkeley.edu/deeprlcourse-fa17/f17docs/lecture_5_actor_critic_pdf.pdf Actor-Critic Algorithms. CS 294-112: Deep Reinforcement Learning, Sergey Levine.]
[[Категория: Машинное обучение]]
[[Категория: Обучение с подкреплением]]
