77
правок
Изменения
Нет описания правки
В алгоритме [[Обучение_с_подкреплением#Q-learning|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>,
Мы предполагаем, что вероятности переходов между состояниями агенту неизвестны, то есть у агента нет модели поведения окружающей среды (''model-free learning'').
Нам нужно выбрать такой набор параметров агента <tex>\theta</tex>, задающий <tex>\pi_{\theta}(a|s)</tex>, чтобы максимизировать матожидание суммы полученных выигрышей:
:<tex>J(\theta) = E_{\tau \sim p_{\theta}(\tau)} \left[ R_{\tau} \right] = \int {p_{\theta}(\tau) R_{\tau} d\tau}</tex>,
Пусть мы хотим максимизировать функцию <tex>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>\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]]
Заметим, что в получившееся выражение для <tex>\nabla_{\theta} J(\theta)</tex> уже не входят напрямую значения <tex>p(s_{t+1}|s_{t}, a_{t})</tex> и <tex>p(s_1)</tex>, которые нам неизвестны. Таким образом, если у нас есть в наличии сценарий <tex>\tau</tex> и соответствующее ему значение <tex>R_\tau</tex>, мы можем вычислить величину <tex>\left( \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)} \right) R_{\tau}</tex>. Значит, если у нас есть выборка из <tex>N</tex> уже известных сценариев <tex>\tau^i = (s_1^i, a_1^i, ... s_{T^i}^i, a_{T^i}^i)</tex>, полученная из распределения <tex>\tau \sim p_{\theta}(\tau)</tex>,то мы можем приблизить посчитать приблизительное значение <tex>\nabla_{\theta} J(\theta)</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>\tau</tex> из вероятностного распределения <tex>p_{\theta}(\tau)</tex>. Однако, это очень просто {{---}} нам всего лишь нужно зафиксировать параметр <tex>\theta</tex> и провзаимодействовать со средой, так как распределение <tex>p_{\theta}(\tau)</tex> задает именно вероятность реализации сценария <tex>\tau</tex> при взаимодействии агента с фиксированной стратегией со средой.
Таким образом, оптимизировать <tex>J(\theta)</tex> можно с помощью следующего простого алгоритма (REINFORCE):
# Прогнать <tex>N</tex> сценариев <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>;
# Если не сошлись к экстремуму, повторить с пункта 1.
[[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>.
Преимущества:
* Легко обобщается на задачи с большим множеством действий, в том числе на задачи с непрерывным множеством действий.;* По большей части избегает конфликта между эксплуатацией (exploitation) и исследованием (exploration), так как оптимизирует напрямую стохастическую стратегию <tex>\pi_{\theta}(a|s)</tex>.;
* Имеет более сильные гарантии сходимости: если Q-learning гарантированно сходится только для МППР с конечными множествами действий и состояний, то policy gradient, при достаточно точных оценках <tex>\nabla_{\theta} J(\theta)</tex> (т. е. при достаточно больших выборках сценариев), сходится к локальному оптимуму всегда, в том числе в случае бесконечных множеств действий и состояний, и даже для частично наблюдаемых Марковских процессов принятия решений (ЧНМППР, англ. ''partially observed Markov decision process, POMDP'').
так как
: <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> \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>
Из предыдущего абзаца:
: <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>,
Здесь <tex>\beta</tex> {{---}} это коэффициент обучения (''learning rate'') для функции ценности. Такой пересчет мы можем производить каждый раз, когда агент получает вознаграждение за действие. Так мы получим оценку ценности текущего состояния, не зависящую от выбранного сценария развития событий <tex>\tau</tex>, а значит, и оценка функции преимущества не будет зависеть от выбора конкретного сценария. Это сильно снижает дисперсию случайной величины <tex>\nabla_{\theta} \log \pi_{\theta}(a_t^i|s_t^i) A^{\pi}(s_t^i, a_t^i)</tex>, что делает оценку <tex>\nabla_{\theta} J(\theta)</tex> достаточно точной даже в том случае, когда мы используем всего один сценарий для ее подсчета:
: <tex>\nabla_{\theta} J(\theta) \approx \sum_{t=1}^{T} {\nabla_{\theta} \log \pi_{\theta}(a_t|s_t) A^{\pi}(s_t, a_t) }</tex>,
На практике же мы можем аппроксимировать <tex>\nabla_{\theta} J(\theta)</tex> на каждом шаге (в онлайне), основываясь на всего одном действии каждый раз. Алгоритм, в итоге, будет следующим:
# производим действие <tex>a \sim \pi_{\theta}(a|s)</tex>, переходим в состояние <tex>s'</tex> и получаем вознаграждение <tex>r</tex>;# <tex>V^{\pi}(s) \leftarrow (1 - \beta) V^{\pi}(s) + \beta (r + V^{\pi}(s'))</tex>;# <tex>A_{\pi}(s, a) \leftarrow r + V^{\pi}(s') - V^{\pi}(s) </tex>;# <tex>\nabla_{\theta} J(\theta) \leftarrow \nabla_{\theta} \log \pi_{\theta}(a|s) A^{\pi}(s, a)</tex>;# <tex>\theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta)</tex>;
# Если не сошлись к экстремуму, повторить с пункта 1.
Проблема с обучением с подкреплением в онлайне заключается в том, что данные, поступающие на вход алгоритму обучения, сильно скоррелированы: каждое следующее состояние непосредственно зависит от предпринятых агентом действий. Обучение на сильно скоррелированных данных приводит к переобучению. Таким образом, для того, чтобы успешно обучить стратегию, обобщаемую на большое количество состояний среды, нам все еще необходимо обучаться на эпизодах из различных сценариев.
Одним из способов достичь этого является запуск множества агентов параллельно. Все агенты находятся в разных состояниях и выбирают различные конкретные действия согласно стохастической стратегии <tex>\pi_{\theta}(a|s)</tex>, тем самым достигается устранение корреляции между наблюдаемыми данными. Однако, все агенты используют и оптимизируют один и тот же набор параметров <tex>\theta</tex>.
Идея алгоритма асинхронного актора-критика заключается в том, чтобы запустить <tex>N</tex> агентов параллельно, при этом на каждом шаге каждый из агентов рассчитывает обновления для значений <tex>V^{\pi}(s)</tex> и <tex>\theta</tex>. Однако, вместо того, чтобы просто продолжить работу, каждый агент обновляет <tex>V^{\pi}(s)</tex> и <tex>\theta</tex>, общие для всех агентов. Перед обработкой каждого нового эпизода агент копирует текущие глобальные значения параметра <tex>\theta</tex> и использует его, чтобы определить собственную стратегию на этот эпизод. Агенты не ждут, пока остальные агенты завершат обработку своих эпизодов, чтобы обновить глобальные параметры (отсюда ''асинхронный''). Поэтому, пока один из агентов обрабатывает один эпизод, глобальное значение <tex>\theta</tex> может изменяться вследствие действий других агентов.
=== Реализация асинхронного актора-критика на основе нейронных сетей ===
