Введение

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

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

В последнем блоге мы представили первый класс методов — динамическое программирование. В частности, мы исследовали два основных алгоритма DP для решения проблем MDP: итерация политик и итерация значений. В этом блоге я расскажу об основах методов Монте-Карло при решении задач RL.

Обучение на основе моделей и обучение без использования моделей

Алгоритмы RL можно разделить на две категории: на основе модели и без модели.

В обучении на основе моделей агент пытается понять свою среду и создает для нее модель на основе своего взаимодействия с этой средой. В такой системе агент может предсказать вознаграждение за какое-то действие до его фактического выполнения, тем самым планируя, что он должен делать.

Вместо этого обучение без моделей направлено на изучение последствий своих действий на основе опыта с помощью алгоритмов. Другими словами, он будет выполнять действие несколько раз и корректировать политику для оптимального вознаграждения в зависимости от результатов.

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

Метод Монте-Карло

Метод Монте-Карло для RL обучается непосредственно на эпизодах опыта без каких-либо предварительных знаний о переходах MDP. Здесь случайная составляющая — это возврат или вознаграждение.

Несмотря на различия между методами Монте-Карло и ДП, самая важная идея, перенесенная из ДП в случай Монте-Карло, заключается в следующем: подобно итерации политики, мы рассматриваем первую оценку политики,вычисление Vπ и Qπ для фиксированной произвольной политики π, затем улучшение политики и, наконец, обобщенная итерация политики. Давайте обсудим их по порядку!

Оценка политики Монте-Карло

Сначала мы рассмотрим методы Монте-Карло для изучения функции значения состояния для заданной политики.

Предположим, мы хотим оценить Vπ(s), значение состояния s в соответствии с политикой π, учитывая набор эпизодов, полученных путем следования π и прохождения через s. Здесь каждый эпизод представляет собой последовательность шагов. Каждое появление состояния s в эпизоде ​​называется visit to s.

Пример:

  • Эпизод 1: с1​→с3​→с4​→с5​→с2​→с1​→конец
  • Эпизод 2: с2​→с3​→с4​→с5​→ с1​→с2​→конец
  • Эпизод 3: с1​→с4​→с5​→с3​→с2​→с5​→конец
  • …

Первый эпизод посещает состояние s1​ на первом и последнем шагах, второй эпизод посещает состояние s1​ на предпоследнем шаге, а третий эпизод посещает состояние s1​ на первом шаге и так далее.

Наша цель — рассчитать среднюю доходность каждого состояния после посещения этого состояния. В зависимости от способа расчета усредненной доходности у нас есть First-Visit MC и Every-Visit MC, где:

  • ВК при первом посещении: усредняет возврат после первого посещения s.

  • ВК при каждом посещении: усредняет возвраты после всех посещений s в наборе эпизодов.

Методы MC «Первое посещение» и «Каждое посещение» сходятся к Vπ(s), когда количество посещений s стремится к бесконечности. Псевдокод для First-Visit MC выглядит следующим образом:

Инициализировать:

  • Политика π ← будет оценена
  • V ← произвольная функция значения состояния
  • Вернуть(s) ← пустой список для всех s∈S

Повторяйте вечно:

  • Создайте выпуск, используя π
  • Для каждого состояния s, появляющегося в эпизоде: 1) R ← возвращается после первого появления s; 2)Добавить R к Return(s); 3) V(s) ← средняя доходность(s)

Примечание.

  • Методы Монте-Карло — это способы решения задач рекурсивного обучения, основанные на усреднении результатов выборки. Чтобы гарантировать наличие четко определенных результатов, мы определяем методы Монте-Карло только для episodic задач. Это означает, что мы предполагаем, что опыт разделен на эпизоды и что все эпизоды в конечном итоге завершатся, независимо от того, какие действия будут выбраны. Оценки ценностей и политика меняются только по завершении эпизода. Таким образом, методы Монте-Карло являются инкрементальными в эпизодном смысле, но не в пошаговом смысле.
  • Оценки для каждого состояния в методах Монте-Карло независимы, поскольку оценка для каждого состояния не основывается на оценке любого другого состояния, как в случае с DP.
  • Вычислительные затраты на оценку значения одного состояния не зависят от количества состояний, потому что мы можем создать множество эпизодов, начиная с состояний, которые мы хотим исследовать, и усреднить доход только для этих состояний, игнорируя все остальные.

Монте-Карло Оценка ценности действия

Если мы не знаем модель, одних значений состояния недостаточно для определения политики; просто смотрите вперед на один шаг и выбираете действие, которое приведет к наилучшей комбинации вознаграждения и следующего состояния, как мы сделали для DP. Таким образом, одной из основных целей метода Монте-Карло является оценка Q∗.

Первый шаг, который нам нужно сделать, это все еще оценить заданную политику π, но вместо оценки значений состояния Vπ(s), здесь мы оцениваем значения действий Qπ(s, a). Это ожидаемый доход при запуске в состоянии s и выполнении действия a, а затем следовании политике π. Подобно оценке политики, у нас также есть методы MC при каждом посещении и MC при первом посещении для оценки ценности действий.

Метод Every-Visit MC оценивает значение пары "состояние-действие" как среднее значение результатов, полученных после посещения состояния, в котором было выбрано действие. Метод First-Visit MC усредняет результаты после первого посещения состояния в каждом эпизоде ​​и выбора действия.

Оба метода сходятся к истинным ожидаемым значениям по мере того, как количество посещений каждой пары состояние-действие приближается к бесконечности.

Однако единственная сложность заключается в том, что многие релевантные пары состояние-действие могут никогда не быть посещены. Одним из примеров является политика π равна deterministic, где будет выполняться только одно действие для каждого состояния, следующего за политикой π. Один из способов решить эту проблему — указать, что каждая пара имеет ненулевую вероятность быть выбранной в качестве начальной. Мы называем это предположением Exploring Starts.

Шаг, за которым следует оценка политики, аналогичен тому, что мы сделали для DP. То есть мы улучшаем текущую политику с учетом текущих оценочных значений действий, а затем повторяем этот итерационный процесс, пока не получим оптимальные политики. Весь этот процесс называется Monte Carlo Control.

Как показано выше, E​ означает полную оценку политики, а I​ – полное улучшение политики. Улучшение политики осуществляется путем детерминированного выбора действия с максимальным значением Q. Псевдокод для первого визита MC с началом изучения выглядит следующим образом:

Инициализировать для всех s∈S,a∈A(s):

  • Q(s,a) ← произвольный
  • π(s) ← произвольный
  • Возврат(s,a) ← пустой список

Повторяйте вечно:

  • Создайте выпуск, используя exploring starts и π
  • Для каждой пары (s, a), появляющейся в эпизоде: 1) R ← вернуть после первого появления s, а; 2)Добавить R к Return(s, a); 3)Q(с, а) ←среднее(Возвращает(с, а))
  • Для каждого s в эпизоде: π(s) ←argmaxa​Q (с,а)

Примечание.

Сейчас мы делаем два маловероятных предположения, чтобы получить гарантию сходимости для метода Монте-Карло. Во-первых, в эпизодах начинаются исследования, а во-вторых, оценку правил можно проводить с бесконечным количеством эпизодов.

Второе предположение можно устранить, выбрав следующие два подхода:

  • Установите границы величины и вероятности ошибки в оценках, а затем при каждой оценке политики предпринимаются достаточные шаги, чтобы гарантировать, что эти границы достаточно малы.
  • Не пытайтесь завершить оценку политики, прежде чем вернуться к ее улучшению. Одна крайняя форма идеи заключается в том, что между каждым шагом улучшения политики выполняется только одна итерация. Другая, более экстремальная идея – чередование этапов улучшения и оценки для отдельных состояний.

Чтобы ослабить первое предположение, у нас есть следующие два метода: On-Policy Контроль Монте-Карло и Off-Policy Контроль Монте-Карло. Чтобы различать эти два метода:

  • Контроль по методу Монте-Карло: оценивает и улучшает целевую политику π, которая используется для создания данных
  • Контроль Монте-Карло вне политики: оценивает и улучшает целевую политику π, используя политику поведения b для создания данных

Контроль Монте-Карло по политике

В методах On-Policy мы улучшаем ту же политику π, которая используется для оценки Q-функции. Обычно используется политика soft, что означает, что π(s, a)›0 для всех (s, а) пар.

Существует множество возможных вариантов on-policy методов. Здесь мы обсудим один из них: ϵ-жадные политики, означающие, что жадное действие выбирается с вероятностью:

И нежадное действие выбирается с вероятностью:

Полный алгоритм для первого визита MC без условия ИЗУЧЕНИЕ СТАРТ приведен ниже:

Примечание.

До сих пор мы рассматривали методы оценки функций ценности для политики с учетом бесконечного набора эпизодов, созданных с использованием этой политики. Теперь предположим, что все, что у нас есть, — это эпизоды, сгенерированные другой политикой. То есть мы хотим оценить Vπ и Qπ, но все, что у нас есть, это эпизоды, следующие за b, где b != π. Можем ли мы узнать функцию ценности для политики, имея только опыт «вне» политики? Ответ положительный, и именно тогда в игру вступает Контроль Монте-Карло вне политики!

Внеполитический контроль Монте-Карло

В Off-Policy у нас есть две политики, то есть behavior policy и target policy. Политика поведения используется для исследования среды, а целевая политика — это та, которую мы хотим улучшить, изучая функцию ценности на основе политики поведения. Например, π — это жадная политика и, в конечном счете, оптимальная политика, а b — исследовательская (например, ϵ-мягкая).

Наша цель — узнать целевое распределение политик π(a∣s) путем вычисления функции значений, полученной из выборок из распределения политик поведения b(a∣s).

Звучит интересно, но как это сделать???

Представьте, что мы хотим оценить ожидаемое значение случайной величины X w.r.t. целевая политика π:

Однако у нас есть только образцы переменной X из дистрибутива политики поведения b:

Чтобы получить ожидаемое значение переменной X при распределении π, мы реализуем следующее преобразование:

Где ρ(X) называется Importance Sampling Ratio. Это отношение вероятности переменной X при π к вероятности переменной X при b.

Согласно Википедии, Importance Sampling — это метод уменьшения дисперсии, который можно использовать в методе Монте-Карло. Идея выборки по важности заключается в том, что определенные значения входных случайных величин (X при b) в моделировании оказывают большее влияние на параметры (распределение π) оценивается больше, чем другие. Если эти важные значения подчеркиваются более частой выборкой, то дисперсия оценщика может быть уменьшена. Следовательно, основная методология выборки по важности заключается в выборе распределения, которое поощряет важные значения.

С учетом сказанного у нас есть следующее предположение, если мы хотим использовать метод выборки по важности:

  • b создает поведение, которое покрывает или включает поведение, созданное π, так что π(a∣ s)›0 для каждой (s,a) пары, в которой b(a∣ с)›0.

Чем ближе распределение b к распределению π, тем ближе мы подходим к реальному ожидаемому значению случайной величины X при целевой политике π.

Теперь вернемся к проблеме, которую мы хотим решить!

Мы хотим:

Но у нас есть только:

Вспомним Importance Sampling, мы можем получить:

где:

Gt​ – это ожидаемый доход, если мы предпримем действие At​ в состоянии St​.

Неполитическая константа-α MC для π ≈π∗:

Это общий алгоритм Off-Policy MC, у нас также есть несколько вариантов:

Обратите внимание, что целевая политика π может быть детерминированной, и когда это произойдет, коэффициент IS (выборка по важности) будет ≥1 на траектории, где политика поведения b имела место. предпринял те же действия, что и π, и сбрасывается на 0, как только b совершает одну «ошибку» (выбирает действие, которое π не выбрал бы).

Рекомендации