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.]
[[Категория: Машинное обучение]]
[[Категория: Обучение с подкреплением]]
