Объединение SARSA и Monte Carlo Simulation
В предыдущих публикациях мы вместе исследовали некоторые общие методы обучения с подкреплением, в том числе SARSA, обновления политики, где значение Q обновляется в зависимости от траектории, которую выбирает агент, и метод Монте-Карло, который обычно используется для оценки политики. В этом посте мы
- вспомните SARSA и метод Монте-Карло
- объясните, почему эти два метода могут быть объединены (по сути, это один и тот же метод с разными параметрами)
- реализовать пример случайного блуждания и сравнить эффективность различных n-шаговых методов
SARSA и моделирование Монте-Карло
Помните, что в одноэтапном SARSA мы обновили текущую оценку значения Q с помощью:
Q(S, A) += lr * (R(S, A) + Q(S', A') - Q(S, A))
который указывает, что на оценку текущего состояния влияет только оценка следующего состояния, и поэтому его также называют методом одноэтапного обновления. С одноэтапным SARSA идет двухэтапный, трехэтапный SARSA и так далее, где текущее обновление также может зависеть от состояний, которые находятся на расстоянии 2, 3… шагов. А когда количество шагов приближается к бесконечности, это по сути симуляция Монте-Карло.
Методы Монте-Карло выполняют обновление для каждого состояния на основе всей последовательности наблюдаемых наград от этого состояния до конца эпизода. С другой стороны, обновление одношаговых методов TD основано только на одном следующем вознаграждении, которое загружается из значения состояния на один шаг позже в качестве прокси для оставшихся вознаграждений.
Например, в игровом сеттинге, таком как блэкджек, мы применили моделирование Монте-Карло и получили результат - выигрыш, ничья или проигрыш - только до конца игры, поэтому на самом деле он использует конечное состояние для обновления текущего состояние, и поэтому это также n-шаговый метод TD с n, приближающимся к бесконечности.
N-шаговый метод TD
Давайте посмотрим непосредственно на алгоритм и реализуем его на конкретном примере.
Понять алгоритм может быть немного сложно, позвольте мне объяснить с помощью реальных цифр. Строчная t - это временная метка, на которой находится агент в данный момент, поэтому она начинается с 0, 1, 2… до конца игры. τ - это временная метка обновляемого значения Q, скажем, если n=3, который представляет собой трехэтапный метод TD, текущий t=5, затем τ=t-n+1=5-3+1=3, что означает, что когда агент достигает временной метки 5, значение Q временной метки 3 будет обновлено. А обновление просто собирает вознаграждение по ходу дела (умноженное на коэффициент уменьшения γ) и использует временную разницу G — Q(S_τ, A_τ) для обновления текущей оценки (эта часть в точности совпадает с тем, о чем мы говорили в SARSA). Часть τ+n<T определяет ситуацию, скажем, если конечным состоянием является T=10, что означает, что агент делает 10 шагов, чтобы достичь конца игры, тогда в конечной временной метке t=10 будет обновлено состояние τ=10-3+1=8, но как насчет состояния τ=9 ? Алгоритм говорит, что состояния между ними будут обновляться только вознаграждением, собранным по пути.
Вы можете задаться вопросом, почему все обновления упорядочены, в то время как примеры, о которых мы говорили ранее, всегда обновляют значения Q до конца игры и распространяют вознаграждение в обратном направлении. Фактически, заказанное обновление - это более обобщенная форма, учитывающая ситуации, которые не являются игровыми, и нет конца игры, скажем, инвестиций на фондовом рынке, где мы заботимся о долгосрочном общем вознаграждении, и нет очевидного конца эпизода. И упорядоченное обновление, и обратное обновление могут сойтись, когда агент выполняет достаточное количество испытаний, в то время как обратное обновление обычно более эффективно с точки зрения вознаграждения, полученного в конце эпизода, в основном ненулевое значение, поэтому попутно обновлений не будет.
Реализация случайного блуждания
Давайте реализуем пример и посмотрим, как различное количество шагов метода TD влияет на обучение агента. (Полный код)
В этой игре все эпизоды начинаются в центральном состоянии C, затем переходят влево или вправо на одно состояние на каждом этапе, с равной вероятностью. Эпизоды заканчиваются либо в крайнем левом, либо в крайнем правом. Когда эпизод заканчивается справа, агент награждается +1, когда он завершается слева, агент награждается -1, а все остальные награды равны 0.
Инициализация
Мы инициализируем игру с 19 состояниями (начальное и конечное состояния не включены!). В функции __init__ мы, как обычно, инициализируем действия и значения Q, а значения Q конечных состояний явно устанавливаются на 1 и -1, чтобы помочь агенту быстрее сходиться. self.n - количество ступеней.
Действия, предпринимаемые
Агент выбирает действия left и right с равной вероятностью, и при выполнении действия индекс либо складывается на 1, либо вычитается на 1.
Обновления TD
N-шаговые обновления SARSA точно такие же, как мы видели в алгоритмах, показанных выше. Перед каждым выпуском мы инициализируем actions, states и rewards, чтобы отслеживать поведение агента на этом пути и выполнять n-этапные обновления. Только когда tau == T-1 может быть остановлено обновление, так как последнее состояние T не будет обновлено.
Сравнение разных N
Запуская алгоритм с разной скоростью обучения и шагами (n), мы можем сравнить производительность нашего агента.
actual_state_value для случайного блуждания с n состояниями одинаково увеличивается с -1 до 1, и поскольку агент выбирает действия с равной вероятностью, estimate_state_value равняется ожиданию значений Q в этом состоянии.
Из результата видно, что обычно n лучших шагов лежит в диапазоне от 1 до бесконечности. Это показывает, как обобщение методов TD и Монте-Карло на n-шаговые методы потенциально может работать лучше, чем любой из двух крайних методов.
И, наконец, пожалуйста, ознакомьтесь с полным кодом здесь. Приглашаем вас внести свой вклад, и если у вас есть какие-либо вопросы или предложения, оставьте комментарий ниже!
Ссылка:
