Изменения

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

Будем Мы предполагаем, что вероятности переходов между состояниями агенту неизвестны, то есть у агента нет модели поведения окружающей среды (''model-free learning''). Нам нужно выбрать такой набор параметров агента <tex>\theta</tex>, задающий <tex>\pi_{\theta}(a|s)</tex>, чтобы максимизировать матожидание суммы полученных выигрышей:

Рассмотрим градиент оптимизируемой функции Пусть мы хотим максимизировать функцию <tex>\nabla_{\theta} J(\theta)</tex>методом градиентного подъема. Для этого нам необходимо уметь рассчитывать ее градиент:

Считать градиент Мы не можем подсчитать <tex>\nabla_{\theta}p_{\theta}(\tau)</tex> непосредственно сложнонапрямую, потому что что в выражение для <tex>p_{\theta}(\tau)</tex> - это большое произведениевходят вероятности переходов между состояниями, которые агенту неизвестны. Однако, так как

Как Заметим, что в получившееся выражение для <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>. Если Значит, если у нас есть выборка из N уже известных сценариев <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> по всему множеству сценариевметоду Монте-Карло {{---}} вычислив выборочное среднее случайной величины:

* Имеет более сильные гарантии сходимости: если Q-learning гарантированно сходится только для МППР с конечными множествами действий и состояний, то policy gradient, при достаточно точных оценках <tex>>\nabla_{\theta} J(\theta)</tex> (т. е. при достаточно больших выборках сценариев), сходится к локальному оптимуму всегда, в том числе в случае бесконечных множеств действий и состояний, и даже для частично наблюдаемых Марковских процессов принятия решений (POMDP).

* Очень низкая скорость работы {{-- -}} требуется большое количество вычислений для оценки <tex>\nabla_{\theta} J(\theta)</tex> по методу Монте-Карло, так как:

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

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

Преимущество действия <tex>a_t</tex> в состоянии <tex>s_t</tex> {{-- -}} это величина, характеризующая то, насколько выгоднее в состоянии <tex>s_t</tex> выбрать именно действие <tex>a_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>\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)</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. Такой алгоритм и называется алгоритмом Actor-Critic. Актором здесь называется компонента, которая оптимизирует стратегию <tex>\pi_{\theta}(a|s)</tex>, а критиком {{---}} компонента, которая подсчитывает ценности состояний <tex>V^{\pi}(s)</tex>. Актор определяет дальнейшее действие, а критик оценивает, насколько то или иное действие выгодно. Алгоритм актора-критика считается гибридным, так как актор работает в соответствии с принципом policy gradient, а критик работает аналогично алгоритму Q-routing. === Асинхронный актор-критик === [[File:Async-actor-critic.png|thumb|313px|link=http://rll.berkeley.edu/deeprlcourse/f17docs/lecture_5_actor_critic_pdf.pdf|Иллюстрация работы алгоритма асинхронного актора-критика]] Проблема с обучением с подкреплением в онлайне заключается в том, что данные, поступающие на вход алгоритму обучения, сильно скоррелированы: каждое следующее состояние непосредственно зависит от предпринятых агентом действий. Обучение на сильно скоррелированных данных приводит к переобучению. Таким образом, для того, чтобы успешно обучить стратегию, обобщаемую на большое количество состояний среды, нам все еще необходимо обучаться на эпизодах из различных сценариев. Одним из способов достичь этого является запуск множества агентов параллельно. Все агенты находятся в разных состояниях и выбирают различные конкретные действия согласно стохастической стратегии <tex>\pi_{\theta}(a|s)</tex>, тем самым достигается устранение корреляции между наблюдаемыми данными. Однако, все агенты используют и оптимизируют один и тот же набор параметров <tex>\theta</tex>. Идея алгоритма асинхронного актора-критика заключается в том, чтобы запустить N агентов параллельно, при этом на каждом шаге каждый из агентов рассчитывает обновления для значений <tex>V^{\pi}(s)</tex> и <tex>\theta</tex>. Однако, вместо того, чтобы просто продолжить работу, каждый агент обновляет <tex>V^{\pi}(s)</tex> и <tex>\theta</tex>, общие для всех агентов. Перед обработкой каждого нового эпизода агент копирует текущие глобальные значения параметра <tex>\theta</tex> и использует его, чтобы определить собственную стратегию на этот эпизод. Агенты не ждут, пока остальные агенты завершат обработку своих эпизодов, чтобы обновить глобальные параметры (отсюда ''асинхронный''). Поэтому, пока один из агентов обрабатывает один эпизод, глобальное значение <tex>\theta</tex> может изменяться вследствие действий других агентов. === Реализация асинхронного актора-критика на основе нейронных сетей ===   == См. также == * [[Обучение с подкреплением]]

== Ссылки ==