В предыдущих сообщениях я работал над формой обучения с подкреплением, Q-обучением, где агент находит оптимальную политику, которая максимизирует общее вознаграждение по траектории состояний. Позже я расширил Q-обучение с помощью глубоких нейронных сетей и изучил реализацию DQN. В этом посте я хотел изучить другой подход к обучению с подкреплением, называемый градиентами политики, который направлен на непосредственную оптимизацию политики. В отличие от Q-обучения, агент выбирает наилучшее действие не на основе значений состояния-действия, а скорее на основе распределения вероятностей действий. Я покажу доказательство теоремы градиента политики и наивный алгоритм REINFORCE (Williams 1992), использующий этот вывод. Удивительно, но Уильямс был профессором Северо-восточного университета, где я сейчас учусь!

Введение

Во-первых, давайте определимся с некоторыми терминами. В отличие от эпсилон-жадного алгоритма, который выбирает действие с максимальным значением с некоторым шумом, мы выбираем действие на основе текущей политики. π(a | s, θ) = Pr{Aₜ = a | Sₜ = s, θₜ = θ}, что представляет собой вероятность действия a на временном шаге t с учетом состояния s на временном шаге t и параметров политики θ на временном шаге t.

Теперь агент будет изучать политику на основе градиента функции измерения производительности J(θ) по отношению к θ. Мы будем использовать градиентное восхождение для настройки параметров политики, чтобы найти оптимальную политику: θₜ₊₁ = θₜ + α∇J(θₜ).

Имея дело с функцией политики π, мы можем сохранить концепцию исследования, убедившись, что π(a | s, θ) ∈ (0, 1), чтобы политика не стала детерминированной. Для параметризованных числовых предпочтений мы получаем значение h(s, a, θ) для пары состояние-действие. Мы можем использовать softmax, чтобы превратить это в распределение вероятностей:

Есть некоторые преимущества в выборе действий в соответствии с softmax по сравнению с предпочтениями действий, а не эпсилон-жадной стратегией. Во-первых, предпочтения действий позволяют агенту приближаться к детерминированной политике, тогда как эпсилон-жадность должна будет поддерживать некоторую степень шума, чтобы стимулировать исследование. Предпочтения действий также ориентированы на построение оптимальной стохастической политики, а не на сходимость к значению. Это означает, что если политика является детерминированной, то вероятность наилучшего действия будет приближаться к 1. Если наилучшая политика должна быть стохастической, то предпочтения действий будут формировать распределение вероятностей. При эпсилон-жадной стратегии нет естественного способа сформировать стохастическую политику.

Другое преимущество состоит в том, что вероятность действия плавно регулируется в зависимости от параметра политики. При эпсилон-жадной стратегии небольшое изменение значения Q может привести к другому действию, если мы выбираем действие на основе максимального значения. Это может резко переоценить важность выбранного действия и привести к неоптимальной политике.

Теперь давайте посмотрим, как агент может узнать параметры оптимальной политики. Помните, что мы будем корректировать наши параметры на основе функции измерения производительности J(θ). Это подводит нас к теореме о градиенте политики, которая позволяет нам аппроксимировать градиент J(θ) по отношению к θ без вывода распределения состояний.

µ(s) здесь является распределением нашей стохастической политики π. q представляет собой функцию значения действия, следующую политике π, а π(a|s, θ) представляет собой распределение действия при заданном состоянии при параметрах θ.

Это решает проблему необходимости знать распределение состояний в неизвестной среде. Следующее доказательство (Sutton & Barto, 2017; раздел 13.2) будет детальным прохождением с помощью статьи Лилиан Венг.

Вывод теоремы о градиенте политики

Определим J(θ) = V_πθ(s), где V — функция ценности для политики π с параметрами θ. Тогда у нас есть:

Мы можем расширить функцию ценности, чтобы она была аналогична уравнению ожидания, где мы находим сумму вероятности действия, следующего политике π, умноженной на значение пары состояние-действие, следующей политике π, для всех действий в действии космос.

Затем в (3) мы применяем правило произведения: d/dx[f(x)g(x)] = f’(x)g(x) + f(x)g’(x). В (4) мы расширяем функцию q. Как мы уже говорили ранее, функция q дает нам значение, заданное парой состояние-действие. Если мы предположим, что среда недетерминирована, то следующее состояние также будет недетерминированным. Мы умножаем вероятность нового состояния s' и вознаграждения r, учитывая пару состояние-действие и функцию вознаграждения + ценности следующего состояния s'. Это дает нам ожидаемое значение результирующего нового состояния s’. Затем мы суммируем все возможные новые состояния. Обратите внимание, что вознаграждение использует фундаментальную концепцию обучения с подкреплением, где мы должны учитывать текущие вознаграждения, а также будущие полезности.

Мы можем упростить p(s', r | s, a) до p(s' | s, a), поскольку сумма всех вознаграждений в p(s', r | s, a) такая же, как p(s' |с, а). Затем мы можем пройти дальше p(s’, r|s, a), поскольку r не является функцией θ (градиент относится к θ). Награда уходит, так как она постоянна.

Напомним строку (1) нашего вывода, ∇J(θ) = ∇v(s). Обратите внимание на аналогичный термин v(s’) в конце нашего расширенного уравнения. Мы можем заметить, что ∇v(s) рекурсивно. Попробуем немного расширить рекурсию.

Как видите, в строке (8) мы заменили член ∇v(s’) тем, что мы получили до сих пор, за исключением перехода s’ в s’’. Мы можем определить этот переход, чтобы немного упростить уравнение.

Приведенная выше функция представляет собой вероятность перехода из состояния s в состояние s’ за k шагов в соответствии с политикой π. Затем мы можем пересмотреть шаги (6) и (7), чтобы использовать это, но также не забудьте сохранить суммирование по всем возможным следующим состояниям s’.

Мы можем упростить еще больше. Если мы распределим умноженные члены, мы можем объединить Pr(s → s’, k=1) с Pr(s’ → s’’, k=1), чтобы получить Pr(s → s’’, k=2).

После многократного развертывания рекурсивного бита мы можем записать это как суммирование.

Здесь мы имеем суммирование по всем целевым состояниям x по всем возможным шагам длины k перехода из начального состояния s в состояние x. Обратите внимание, что при k = 0 Pr(s → s, k=0, π) тривиально равно 1, поэтому мы не упустили первый член ϕ(s).

Теперь мы можем перейти к завершению доказательства.

На линии (12) находится распределение перехода из начального состояния s0 в конечное состояние s для любых k шагов длины, которое мы упрощаем до η(s). Затем в строке (14) мы нормализуем η(s) как распределение вероятностей ∈ (0, 1) для каждого конечного состояния s. Затем мы построили µ(s), которое представляет собой распределение вероятностей действий, следующих нашей стохастической политике. Разлагая функцию ϕ(s), мы доказали соотношение:

Алгоритм УСИЛЕНИЯ

Теперь с теоремой о градиенте политики мы можем придумать наивный алгоритм, использующий градиентное восхождение для обновления параметров нашей политики. Теорема дает сумму по всем состояниям и действиям, но когда мы обновляем наши параметры, мы собираемся использовать только образец градиента, поскольку мы просто не можем получить градиент для всех возможных действий и состояний. Мы можем записать это как ожидание, поскольку ожидание выборочного градиента совпадает с фактическим градиентом. Таким образом, мы имеем следующее:

Обратите внимание, что мы заменили s на Sₜ в (2). Это связано с тем, что мы формулируем уравнение для выборки градиента, где мы используем выборку состояния Sₜ и выборку действия Aₜ вместо суммирования всех состояний и действий. Теперь давайте заменим сумму всех действий примером действия Aₜ.

В (3) мы умножаем значение на член в конце, так что значение выборочного действия взвешивается вероятностью выбора действия. Тогда в (4) можно избавиться от суммирования по всем действиям и заменить a на выборочное действие Aₜ. В (5) мы можем заменить функцию ценности состояния-действия на Gₜ, кумулятивное дисконтированное вознаграждение на временном шаге t. Затем мы можем упростить уравнение, используя тот факт, что d/dx[ln(x)] = 1/x.

Затем мы можем использовать этот термин внутри ожидания выполнения градиентного подъема для обновления нашего параметра политики. Мы можем использовать это обновление в наивном алгоритме REINFORCE.

Обратите внимание, что этот алгоритм является типом метода Монте-Карло, поскольку мы не обновляем параметр после каждого временного шага, а скорее эпизодически отбираем всю траекторию со статическим параметром θ, а затем обновляем параметр. В приведенном выше псевдокоде, взятом из учебника (Sutton & Barto, 2017), строка обновления немного неверна, поскольку мы не должны обновлять тот же параметр, который мы используем для получения вероятности журнала политики. В нашей реализации мы можем просто накапливать градиент и сразу обновлять параметр в конце эпизода. Теперь приступим к реализации!

Внедрение ПОДДЕРЖКИ

Для реализации REINFORCE я решил использовать Pytorch вместо Keras, так как хотел изучить другие библиотеки машинного обучения. Для параметра политики я использовал нейронную сеть, так как она может выполнять градиентное восхождение за меня. Обратите внимание, что я буду добавлять отрицательный знак перед градиентом, чтобы выполнить градиентный подъем вместо градиентного спуска. Вот моя сеть:

#Using a neural network to learn our policy parameters
class PolicyNetwork(nn.Module):
    
    #Takes in observations and outputs actions
    def __init__(self, observation_space, action_space):
        super(PolicyNetwork, self).__init__()
        self.input_layer = nn.Linear(observation_space, 128)
        self.output_layer = nn.Linear(128, action_space)
    
    #forward pass
    def forward(self, x):
        #input states
        x = self.input_layer(x)
        
        #relu activation
        x = F.relu(x)
        
        #actions
        actions = self.output_layer(x)
        
        #get softmax for a probability distribution
        action_probs = F.softmax(actions, dim=1)
        
        return action_probs

После реализации алгоритма я протестировал свои результаты со следующими параметрами:

  • γ (коэффициент дисконтирования): 0,99
  • NUM_EPISODES: 1000
  • МАКС_ШАГОВ: 10 000

Во-первых, давайте посмотрим, как наш агент справляется со случайной политикой более 150 эпизодов:

Неудивительно, что это были некоторые некачественные результаты со средним баллом 21,48. Теперь давайте посмотрим на историю обучения нашего алгоритма более чем на 1000 эпизодов.

Глядя на нашу историю обучения, мы видим, что наш агент медленно учится со временем. Однако мы замечаем, что по сравнению с другими методами обучения, такими как DQN в моем предыдущем посте, обучение происходит медленно и имеет высокую дисперсию. Этого следовало ожидать, поскольку алгоритм REINFORCE менее сложен по сравнению с алгоритмом, использующим глубокую нейронную сеть. Тем не менее, мы смогли достичь среднего балла 79,6 за 50 эпизодов, используя изученную политику, что лучше, чем человеческий ориентир (я) 30,8.

В целом, это было отличное введение в класс методов градиента политики, которые мне было труднее понять, чем Q-обучение, которое я изучил на своих лекциях CS4100. Я подумал, что было интересно попытаться понять все выводы и рассуждения, лежащие в основе каждого уравнения, следуя учебнику Саттона и Барто, и это дало мне более глубокое понимание темы. Двигаясь вперед, я определенно хочу узнать больше о методах градиента политики, а также о Pytorch, с которым я немного поигрался при реализации REINFORCE.

Мой код: https://github.com/chengxi600/RLStuff/blob/master/Policy%20Gradients/REINFORCE.ipynb

Использованная литература: