В этом сообщении в блоге я попытаюсь разъяснить алгоритм итерации политики в обучении с подкреплением, используя его для решения проблемы аренды автомобиля Джека. Эта задача и ее вариант приведены в примере 4.2 и упражнении 4.5, соответственно, в книге Саттона и Барто (Обучение с подкреплением: введение, второе издание).
Постановка задачи
Джек управляет двумя офисами в общенациональной компании по аренде автомобилей. Каждый день некоторое количество клиентов приезжает в каждое место, чтобы арендовать автомобили. Если у Джека есть машина, он сдает ее в аренду и получает 10 долларов от национальной компании. Если в этом месте у него нет машин, бизнес пропадает. Машины становятся доступны для аренды на следующий день после их возврата. Чтобы обеспечить наличие автомобилей там, где они необходимы, Джек может перемещать их между двумя местами в одночасье по цене 2 доллара за каждую перемещаемую машину.
Мы предполагаем, что количество автомобилей, запрошенных и возвращенных в каждом месте, является случайной величиной Пуассона. Напомним, что если X - случайная величина Пуассона, то
Предположим, что λ равно 3 и 4 для заявок на аренду в первом и втором местах и 3 и 2 для возвратов.
Чтобы немного упростить задачу, мы предполагаем, что в каждом месте может быть не более 20 автомобилей (любые дополнительные автомобили возвращаются в общенациональную компанию и, таким образом, исчезают из проблемы), и максимум пять автомобилей могут быть перемещены из одного места. к другому за одну ночь. Мы принимаем ставку дисконтирования γ равной 0,9 и формулируем ее как непрерывный конечный процесс принятия решений Маркова, где временными шагами являются дни, состояние - это количество автомобилей в каждом месте в конце дня, а действия - это чистая сумма. количество автомобилей, перемещенных между двумя локациями за ночь.
Но что значит решить эту проблему?
Решение этой проблемы означает решение двух вещей: во-первых, сколько машин Джек должен переместить за ночь между каждым местоположением, чтобы максимизировать его общую ожидаемую награду, то есть какой должна быть его стратегия (политика) в данной ситуации (состоянии), и во-вторых, если Джек знает эту стратегию, как он может сравнить, какие ситуации лучше других (ценность)?
Начальная настройка
Давайте сначала напишем в коде то, что мы уже знаем. Из проблемы мы знаем, что Джек может получить два типа наград: первое - это вознаграждение в размере 10 долларов, когда он арендует машину, а второе - вознаграждение в размере - 2 доллара за каждую машину, которую он перемещает из одного места в другое (обратите внимание, что последняя награда отрицательная).
Теперь мы определяем класс poisson_, который принимает параметр λ и вычисляет соответствующую функцию вероятностных масс. Он имеет два элемента данных α и β, которые обозначают интервал [α, β) значений n, для которого значение PMF больше ε (здесь 0,01). Мы устанавливаем значения pmf ниже ε равными нулю, а затем нормализуем полученное распределение.
Например, для λ = 3 значения элементов данных α, β и vals равны:
Алгоритм итерации политики
Прежде чем идти дальше, чтобы убедиться, что все читатели находятся на одной странице, давайте быстро рассмотрим, что мы подразумеваем под термином "ценность" и "политика".
В нашем примере с прокатом автомобилей состояние системы в любой момент - это пара из двух чисел: количество автомобилей в первом и втором месте. Учитывая состояние, Джек должен выбрать действие, которое представляет собой количество машин, которые он может переместить из первого места во второе или наоборот. Согласно задаче, оно может варьироваться от -5 до +5, где + n означает, что Джек перемещает n машин из первого места во второе.
Политика - это сопоставление состояний с действиями, т. е. с учетом состояния, сколько машин Джек должен переместить за ночь. Теперь предположим, что у Джека есть некоторая политика π, затем с учетом этого π, значение состояния (скажем, s) - это ожидаемая награда, которую получит Джек, если начнет с s и после этого следует за π.
Алгоритм итерации политики, как показано на изображении выше, состоит из трех компонентов. Давайте обсудим каждую из этих составляющих отдельно в контексте решения проблемы аренды.
Первый компонент - это инициализация. Как показано на изображении выше, мы произвольно инициализируем матрицы значений и политик. Инициализация их на ноль тоже работает нормально. Обратите внимание, что с учетом политики мы определяем значение для каждого состояния, и поскольку наше состояние представляет собой пару из двух чисел, где каждое число принимает значение от 0 до 20, мы представляем значение матрицей формы (21 x 21). Политика принимает состояние и выводит действие; следовательно, он также может быть представлен матрицей той же формы.
Второй компонент - оценка политики. Под оценкой политики мы подразумеваем то, что следуя этой политике, какова должна быть ценность любого государства. Как упоминалось выше, с учетом политики π значение состояния (скажем, s) - это ожидаемое вознаграждение, которое Джек получит, когда начнет с s и следует за π после этого.
Эта идея ожидания, связанная со значением состояния, может быть записана в форме, показанной на изображении выше, из которого можно вывести уравнение Беллмана, как показано.
Это уравнение Беллмана формирует основу для обновления значения, отображаемого в компоненте оценки политики.
После многих таких обновлений V (s) сходится к числу, которое почти удовлетворяет (не более чем с некоторой ошибкой θ) уравнению Беллмана и, следовательно, представляет значение состояния s.
Третий компонент - улучшение политики. Учитывая состояние (скажем, s), мы назначаем π (s) равным тому действию, которое максимизирует ожидаемое вознаграждение. И мы говорим, что политика становится стабильной, когда ни один из шагов максимизации действия в каком-либо состоянии не вызывает изменения в политике.
Мы запускаем компоненты оценки и улучшения политики в цикле, пока политика не станет стабильной.
Полученные результаты
На изображении выше показаны политики после проходов оценки и улучшения в виде тепловых карт. Напомним, что политика представлена матрицей, содержащей значения действий в диапазоне [-5, 5].
Добавление нелинейностей к исходной задаче аренды
Давайте посмотрим, что произойдет, если мы добавим к проблеме, описанной выше, некоторые нелинейности, подобные приведенной ниже:
- Один из сотрудников Джека в первом месте каждую ночь ездит на автобусе домой и живет недалеко от второго. Она рада бесплатно перевезти одну машину на вторую точку. Каждая дополнительная машина по-прежнему стоит 2 доллара, как и все машины, двигавшиеся в обратном направлении.
- Кроме того, у Джека есть ограниченное количество парковочных мест на каждой локации. Если более 10 автомобилей остаются на ночь в каком-либо месте (после любого перемещения автомобилей), то должны быть понесены дополнительные расходы в размере 4 долларов за использование второй стоянки (независимо от того, сколько автомобилей там стоит).
Эти условия можно легко добавить, чтобы изменить исходный код. У нас будет еще одно вознаграждение в размере - 4 доллара за вторую парковку, если это необходимо (обратите внимание, что это вознаграждение отрицательное).
Полученные в результате политики (прошедшие оценку и улучшение) показаны на следующем изображении.
Заключение
Мы решили указанную выше проблему с помощью динамического программирования. Мы сохранили матрицы промежуточных значений и политик и использовали их в наших функциях оценки и улучшения политики. Однако, чтобы использовать обновления Bellman, нам нужно знать динамику среды, точно так же, как мы знали вероятности вознаграждений и следующих состояний в примере аренды. Если мы можем производить выборку только из базового распределения и не знаем самого распределения, тогда методы Монте-Карло могут использоваться для решения соответствующей проблемы обучения.
Репозиторий Github: https://github.com/thunderInfy/JacksCarRental
использованная литература
[1] Саттон, Р., и Барто, А. (2017). Обучение с подкреплением: введение. Кембридж, MIT Press
[2] Лекция С. Дэвида о планировании с помощью динамического программирования (https://www.youtube.com/watch?v=Nd1-UUMVfz4).
