116
правок
Изменения
Нет описания правки
В алгоритме 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>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|a_t) p(s_{t+1}|s_t, a_t)}</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>
Как мы можем подсчитать это матожидание? С помощью семплирования! Если у нас есть 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>
[[File:Reinforce-policy-gradient.png|thumb|313px|link=https://i.postimg.cc/R0CPDn76/2019-01-23-180151-553x339-scrot.png|Схема алгоритма REINFORCE]]
Таким образом, оптимизировать <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>
== Ссылки ==
* [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.]
