В этом сообщении блога мы подробно и пошагово решим проблему ипподрома в обучении с подкреплением.
Постановка задачи
Во-первых, давайте разберемся, в чем проблема. Рассмотрите возможность вождения гоночного автомобиля по гоночным трассам, подобным показанным на рисунке ниже. На нашей упрощенной гоночной трассе автомобиль находится в одном из дискретных наборов позиций сетки, ячеек на диаграмме. Скорость также дискретная, количество ячеек сетки перемещается по горизонтали и вертикали за один временной шаг.
Следовательно, состояние нашей машины может быть представлено индексом строки и столбца, в котором она находится, и скоростью машины. Итак, это 4 кортежа.
Действия представляют собой изменения компонентов скорости. Каждый может быть изменен на +1, -1 или 0 за один шаг. Итак, для каждого компонента скорости у нас есть 3 варианта действий, всего девять действий.
Для простоты у нас есть некоторые ограничения на скорость. Обе компоненты скорости должны быть неотрицательными и быть меньше 5, и они не могут быть обе равны нулю, кроме как на стартовой линии.
Каждый эпизод начинается в одном из случайно выбранных начальных состояний, при котором обе компоненты скорости равны нулю.
Мы хотим ехать как можно быстрее, но не так быстро, чтобы сбежать с трассы. Итак, делаем функцию вознаграждения следующим образом. Награды составляют -1 за каждый шаг, пока машина не пересечет финишную черту. Если автомобиль врезается в границу трассы, он перемещается обратно в случайное положение на стартовой линии, обе составляющие скорости обнуляются, и эпизод продолжается.
Эпизод заканчивается, когда машина пересекает финишную черту.
Обзор решения
Чтобы решить указанную выше проблему, нам необходимо следующее:
- Нам нужен генератор, который будет случайным образом генерировать для нас ипподромы.
- Нам нужно создать среду для этой проблемы. Его основные обязанности будут заключаться в запуске и завершении эпизодов. Он также должен иметь возможность получать новое состояние и вознаграждение с учетом текущего состояния и значений действия.
- Нам нужен агент (то есть машина здесь), который выбирал бы действие с учетом состояния.
- Визуализатор также необходим для визуализации сгенерированных ипподромов вместе с местоположением на них агента.
- Реализация алгоритма Монте-Карло Off-policy Control.
Создание гоночных треков
Существует множество подходов к созданию ипподромов. Наш подход заключался в том, что мы начали с квадратной сетки с ребром 100 и произвольно проделывали в ней отверстия. Затем мы получили следующие гоночные трассы, которые выглядели не совсем так, как нам хотелось.
Итак, затем мы изменили наш подход и расширили эти случайные дыры до верхнего левого или нижнего правого угла в зависимости от того, какой угол ближе. А потом у нас появилось несколько таких хороших ипподромов.
Создание окружающей среды
Теперь у нас есть ипподромы, и нам нужно создать среду для решения этой проблемы.
Сначала нам нужно подумать о том, что нужно сделать, начиная серию. Что ж, нам нужно получить начальное состояние. Как упоминалось выше, наше состояние представляет собой 4-кортеж (индекс строки, индекс столбца, скорость x, скорость y). Нам нужно установить начальную скорость равной нулю, и нам нужно случайным образом выбрать индекс строки и индекс столбца из ячеек начальной строки. Линии старта и финиша представляют собой совокупность всех тех ячеек на треке, которые находятся в последней строке и последнем столбце соответственно.
Другая обязанность среды - вернуть новое состояние и вознаграждение с учетом текущего состояния и значений действия. Для этого нам нужно проверить два случая: во-первых, заканчивает ли машина гонку, пересекая финишную черту, и во-вторых, выходит ли она за пределы трассы.
Как узнать, пересекает ли машина финишную черту? Мы можем определить следующее местоположение автомобиля, основываясь на его текущей скорости. На основе текущего и следующего местоположения автомобиля мы получаем матрицу ячеек, нижний левый угол которой будет текущим местоположением, а верхний правый угол - следующим местоположением этого автомобиля. Мы можем проверить, содержит ли эта матрица какие-либо ячейки финишной прямой.
Чтобы проверить, не выезжает ли машина за пределы трассы, мы можем увидеть, не соответствует ли новое местоположение допустимому значению ячейки трека или оно выходит за пределы размеров трека.
Создание агента
Агент должен действовать в зависимости от своего текущего состояния. Таким образом, он будет использовать некоторую политику для выполнения действий. Кроме того, мы написали несколько полезных функций, таких как поиск допустимых возможных действий с учетом текущей скорости, которая контролирует данное ограничение на скорость, и отображение действий от 1-D до 2-D и наоборот.
Визуализатор
Визуализатор принимает состояние системы и создает окно pygame для визуализации текущего местоположения агента на ипподроме.
Алгоритм управления Монте-Карло вне политики
Отличительной особенностью методов, основанных на политике, является то, что они оценивают ценность политики, используя ее для управления. В методах вне политики эти две функции разделены. Политика, используемая для создания поведения, называемая политикой поведения, на самом деле может быть не связана с политикой, которая оценивается и улучшается, называемой целевой политикой. Хотя в принципе политика поведения может быть не связана с целевой политикой, на практике она остается достаточно репрезентативной для целевой политики.
Преимущество этого разделения состоит в том, что целевая политика может быть детерминированной (например, жадной), в то время как политика поведения может продолжать выборку всех возможных действий. Внеполитические методы контроля Монте-Карло следуют политике поведения при изучении и улучшении целевой политики.
Рассмотрим алгоритм подробнее. Мы генерируем эпизоды, используя действие поведенческой политики, которое является ε-жадной политикой, что означает, что с вероятностью ε он выбирает действие равномерно случайным образом, а с вероятностью 1-ε он выбирает жадное действие. Это обеспечивает исследование ранее не исследованных значений состояния и действия.
Но как мы используем эпизоды, сгенерированные из поведенческой политики, для обновления наших Q-значений, которые должны соответствовать жадной целевой политике? Здесь и появляется идея выборки по важности.
Выборка по важности
Допустим, X - дискретная случайная величина, которая принимает значения в диапазоне от 1 до N. Тогда
Если мы выберем из распределения вероятностей b и умножим каждую выборку x на соотношение π (x) / b (x), то ожидание этих продуктов будет таким же, как если бы мы получили наши выборки из целевого распределения. Это основная идея выборки по важности.
Обратите внимание: поскольку мы выбираем из распределения b, следовательно, b (x) не будет равно нулю ни для одной выборки (иначе она не была бы сгенерирована в первую очередь). Следовательно, умножение и деление на b (X = x) в приведенном выше уравнении можно выполнить без каких-либо проблем.
Учитывая начальное состояние St, вероятность того, что последующая траектория действия состояния произойдет при любой политике π, равна
Следовательно, относительная вероятность траектории в соответствии с целевой и поведенческой политиками равна:
τ (s) в приведенном ниже уравнении обозначает набор всех временных шагов, на которых происходит посещение состояния s.
Следовательно, приведенное выше уравнение представляет собой простое среднее значение всех доходов, взвешенных по коэффициентам важности выборки.
Обратите внимание, что указанное выше среднее значение не смещено, т.е. его математическое ожидание равно Vπ (s). Но дисперсия этой оценки, как правило, не ограничена, потому что дисперсия соотношений может быть неограниченной. Из-за этой проблемы неограниченной дисперсии, как правило, другой метод оценки, называемый выборкой взвешенной важности, которая использует средневзвешенное значение, предпочтительнее обычной выборки по важности.
Хотя эта оценка является смещенной (ее ожидание равно Vb (s)), но если мы предполагаем ограниченную доходность, тогда дисперсия взвешенной оценки выборки важности сходится к нулю. На практике взвешенная оценка обычно имеет значительно меньшую дисперсию, чем обычная выборка по важности. Также обратите внимание, что политика поведения считается очень репрезентативной для целевой политики и, следовательно, на практике предвзятость не приводит к каким-либо неблагоприятным последствиям.
Вышеупомянутое уравнение можно переписать следующим образом, где G1, G2… и так далее - это последовательность возвратов, все начинающиеся в одном и том же состоянии, и где каждое Wi - это коэффициент выборки по важности.
Теперь, используя это уравнение, мы хотим получить связь между Vn + 1 и Vn, чтобы мы могли постепенно обновлять наши Q-значения после каждого возврата, который мы наблюдаем.
Искомое отношение приращения может быть получено следующим образом.
где Cn - это текущая сумма Wi и может быть представлена следующим уравнением.
Получив эти инкрементальные уравнения для значений Q состояния-действия аналогичным образом, мы получаем алгоритм Монте-Карло Off - Policy, написанный на изображении выше в этом разделе.
Полученные результаты
После обучения нашего агента работе с нашей средой мы получаем следующие результаты.
Заключение
В этом сообщении в блоге мы решили проблему с ипподромом, используя Off-policy Monte Carlo Control. Мы видели, что агент изучает оптимальную политику для этой задачи для каждого начального состояния. В качестве будущего упражнения мы можем сделать эту среду более сложной, добавив некоторые дополнительные сложности, такие как ограничение ускорения агента на некоторое время и наблюдение за тем, как агент изменяет свою политику, чтобы в некотором смысле более осторожно управлять автомобилем и избегать резких дорожек по гоночной трассе.
Код решения этой проблемы можно найти по адресу:
Https://github.com/thunderInfy/Racetrack
использованная литература
[1] Саттон, Р., и Барто, А. (2017). Обучение с подкреплением: введение. Кембридж, MIT Press
