Сегодня мы сосредоточимся на создании агента Монте-Карло (MC) для изучения MDP. В предыдущей истории мы реализовали обучающий ADP на основе модели, который оценивает модель функции вознаграждения r(s) и вероятности перехода p(s′| s, a). В некоторых случаях такой подход, основанный на модели, может работать эффективно. Однако, если модель перехода трудно оценить, подход без моделей, как правило, является лучшим выбором. Монте-Карло (МК), который является нашей сегодняшней темой, является одним из примеров таких подходов без моделей.
Код в этой истории является частью нашего проекта MAD с нуля, где MAD означает машинное обучение, искусственный интеллект и наука о данных. Полный код, использованный в этой истории, можно найти в этом репозитории: https://github.com/clumsyhandyman/mad-from-scratch.
Оглавление:
- Ценности состояний vs ценности пар состояние-действие
- Q-значения пар состояние-действие
- Оценка значений Q методом Монте-Карло
- Визуализация метода МК с таблицей состояний-действий
- Первый визит vs каждый визит
- Псевдокод для безмодельного обучения MC
- Реализовать MC Learner на Python
- Насколько хорош наш ученик MC?
- Улучшите MC, обучаясь больше
- Улучшить ученика MC, адаптировав награду
- От Монте-Карло к временной разнице
Значения состояний против значений пар состояние-действие
В методах на основе моделей наша политика выводится из значений полезности состояний. Следуя определенной политике, значение полезности v(s) для определенного состояния s определяется как
Тогда для оптимальной политики соответствующее значение полезности v(s) равно
Этот подход называется методом на основе модели, потому что нам нужно p(s′| s, a), которая является переходной моделью в расчетах. Теперь мы хотели бы избавиться от необходимости знать p(s′| s, a), что может мы делаем? Одним из возможных способов является присвоение значений паре состояние-действие, а не состоянию.
В модельном подходе мы полагаемся на значения состояний. Когда мы находимся в определенном состоянии, мы проверяем возможные следующие состояния, с которыми связано это состояние. Например, из нашего текущего состояния мы можем получить s₁ с полезностью 10 и s₂ с полезностью 5 и так далее. Затем мы проверяем последствия выбора определенных действий. Например, если действие а₄ ведет к s₁, а действие a₆ ведет к s₂, то мы бы предпочли a₄ a₆.
Напротив, в безмодельном подходе мы полагаемся на значения пар состояние-действие. Вместо того, чтобы присваивать значения состояниям, мы присваиваем значения парам состояние-действие. Когда мы находимся в нашем текущем состоянии, например s₁, мы проверяем возможные действия в этом состоянии. Например, возможно, для действия a₄ значение полезности пары состояние-действие (s₁, a₄) равно 19, а для действия a₆ значение полезности пары состояние-действие (s₁, a₆) равно 35. В этом случае мы бы предпочесть а₆ а₄.
Q-значения пар состояние-действие
Значение полезности пары состояние-действие (s, a) обычно обозначается как Q(s, a) и поэтому обычно называется Q-values. По определению Q-значение (s, a) — это ожидаемое общее вознаграждение после выбора определенного действия a в определенном состоянии с.
Как мы упоминали ранее, для оптимальной политики полезность состояния может быть выражена как
В этом уравнении для заданного состояния s награда r(s) и коэффициент дисконтирования γ являются постоянными значениями, которые не зависят от действия. а. Следовательно, мы можем поместить эти два значения в функцию max.
О чем говорит нам это уравнение? Если мы знаем или можем оценить Q-значения, то мы можем выбирать наши действия исключительно на основе Q-значений без необходимости иметь дело с s′ или p (с′| с, а).
Ранее мы определяли оптимальную политику по значениям состояния:
Опять же, поскольку r(s) и γ являются постоянными значениями, которые не влияют на функцию argmax, теперь мы имеем
В результате нам больше не нужно знать или оценивать модель перехода. Мы можем напрямую выбирать действия по их относительной привлекательности, представленной Q-значениями.
Оцените значения Q с помощью метода Монте-Карло
Теперь вопрос: как оценить Q-значения? Один из способов — просто попробовать каждую пару состояние-действие и посмотреть, как она работает. Другими словами, мы играем в эту игру много раз. В каждой игре мы записываем последовательность состояний, действий и вознаграждений, как показано ниже.
Как мы упоминали в предыдущих историях, в обучении с подкреплением эта серия s, a, r, s, a, r… — единственная известная нам игра. Здесь мы предполагаем, что наша игра заканчивается за конечные шаги. Мы используем n для обозначения общего количества шагов в этой конкретной игре. Поскольку в этой игре у нас n шагов, мы проходим через n состояний: от шага t = 1 до шага t = n. Эти состояния не обязательно могут быть n различными состояниями, поскольку некоторые состояния могут появляться более одного раза. Тем не менее, если мы перечислим состояния в соответствии с временной последовательностью, в которой мы их посетили, мы получим серию из n состояний от t = 1 до t. = n.
В каждом из этих состояний мы сделали выбор действия, представляющего собой серию действий от шага t = 1 до шага t = n . В результате мы испытали ряд пар состояние-действие:
Для этой первой пары состояние-действие результат этой пары можно просто оценить как общее вознаграждение после того, как мы посетили эту пару состояние-действие.
Точно так же результат второй пары состояние-действие оценивается как общее вознаграждение после этой пары:
В более общем случае для пары состояние-действие на шаге i результат этой пары можно оценить как
Таким образом, играя в одну игру, мы получаем грубую оценку значений этих пар состояние-действие (s, a), с которыми мы столкнулись в этой игре. Если мы постоянно играем в эту игру, мы неизбежно сталкиваемся с каждой парой состояние-действие (s, a) снова и снова. Каждый раз, когда у нас есть оценка G(s, a) для этой пары, у нас есть образец значения для этой пары. Теперь у нас есть список этих образцов.
Используя принцип методов Монте-Карло, если мы усредним этот список выборок G(s, a), мы получим его ожидаемое значение.
Визуализация метода MC с таблицей состояний и действий
В этом методе MC нам нужно оценить значения каждой пары состояние-действие. В типичном MDP обычно известно количество состояний и количество действий. Поэтому мы можем построить большую таблицу со строками в качестве состояний и столбцами в качестве действий.
В одной игре, если мы встречаем определенную пару (sᵢ, aⱼ), мы помещаем G(sᵢ, aⱼ) в сетку таблицы, соответствующую строке sᵢ и столбцу aⱼ, который является (i, j) элемента таблицы. Поскольку мы постоянно играем в эту игру, мы построили такую таблицу для каждой игры. В начале каждой игры стол пуст. Во время игры мы помещаем G(sᵢ, aⱼ) в (i, j) для каждого (sᵢ, aⱼ), с которым мы столкнулись.
В результате мы получаем один стол G(s, a) от одной игры и можем получить много таких столов от игры эту игру неоднократно в течение многих раз.
Наконец, среднее значение всех этих таблиц представляет собой таблицу Q-значений. Когда мы вычисляем средние значения для определенной пары состояние-действие, мы учитываем только игры, в которых появляется эта конкретная пара. Например, если мы неоднократно играли в эту игру 1000 раз и если (s₂, a₂) встречается в 670 из этих 1000 игр, мы получаем Q( с₂, a₂) из усреднения G(s₂, a₂) из этих 670 игр.
Первое посещение против каждого посещения
В одном игровом процессе, в серии [s, a, s, a, s , a, s, a…], определенная пара (s, a) может появляться более одного раза. Как мы обсуждали выше, результат G(s, a) определенной пары состояние-действие определяется как сумма доходов после столкнулся с этой парой. В случае, если конкретная пара встречается несколько раз, это определение кажется немного двусмысленным.
Если используется сумма возврата после первого появления этой пары в игре, этот метод называется методом первого посещения MC. В этом методе не имеет значения, сталкиваемся ли мы с определенной парой повторно. Нас интересует только первое появление этой пары в игре. Например, в одной игре, если у нас есть
Затем мы оцениваем пару состояние-действие (s₁, a₃) как
Затем мы добавляем это значение G(s₁, a₃) в список R(s ₁, а₃).
Напротив, мы также можем использовать метод MC каждое посещение. В этом методе всякий раз, когда мы сталкиваемся с определенной парой состояние-действие, мы суммируем доход от этой позиции до конца этой игры и используем это как одну запись R(s , а). Используя приведенный выше пример, в этом методе, поскольку пара (s₁, a₃) встречается дважды, у нас есть две оценки G( с₁, а₃):
В результате мы добавляем эти два значения G(s₁, a₃) в список R( s₁, a₃).
В нашем сегодняшнем рассказе мы сосредоточимся на методе MC первого посещения в следующей реализации кода.
Псевдокод для обучения MC без модели
Подобно API нашего предыдущего обучающего модуля ADP на основе моделей, наш обучающий модуль MC без использования моделей также имеет функции восприятия и приведения в действие.
В функции восприятия мы добавляем вознаграждение r текущего шага к значениям G всех (s, a) пары, которые уже были посещены ранее в этой игре. Делая это, мы гарантируем, что значение G любой пары (s, a) равно сумме вознаграждения после того, как мы впервые посетили это пара до конца игры.
В функции активации мы применяем то же геометрическое затухание, что и в обучающем модуле ADP на основе модели, чтобы контролировать переход от исследования к эксплуатации.
После каждой игры нам нужно обновлять нашу политику, чтобы отразить то, что мы узнали в этой игре. Выполняя это обновление, мы гарантируем, что сможем становиться лучше и лучше, играя во все больше и больше игр. После обновлений мы повторно инициализируем таблицы значений G и посетили, чтобы подготовиться к следующей игре.
Используя принцип выборки Монте-Карло, значение Q- после n - 1 игр представляет собой среднее значение G-значения из этих n – 1 игр. Точно так же значение Q после n игр будет средним значением G- для этих n игр.
При обновлении политики, если определенная пара (s, a) посещается в текущей n-й игре, мы получаем ее оценку Gₙ из этой игры и его Q-значение Qₙ₋₁из предыдущей n − 1 игры.
Как показано в приведенном выше псевдокоде, мы обновили значения Q- с помощью этого правила.
Чтобы обучить нашего ученика, мы используем следующий псевдокод для повторного прохождения игры N раз, где N может быть произвольно большим числом. Каждую из этих Nигр также можно назвать эпизодом илиэпохой. В этом случае мы отслеживаем общее вознаграждение, полученное в каждой игре, а также выигрываем мы или проигрываем в каждой игре.
Реализовать учащегося MC в Python
Подобно нашему предыдущему учащемуся ADP, учащийся MC также реализован как класс с функциями восприятия, срабатывания и обновления политики.
Чтобы решить нашу глобальную проблему с учащимся MC, мы реализуем следующий решатель:
Следующий код может быть реализован для решения нашего примера мира сетки. В этом случае мы обучаем нашего ученика MC на 1000 эпизодов.
Насколько хорош наш ученик MC?
Давайте посмотрим, насколько хорошо работает наш ученик MC! Мы применяем наш обучающий модуль MC к той же проблеме с сеткой, что и с обучаемым ADP. Опять же, начиная с черного круга. Опять же, с наградой за победу 10,0 для зеленой сетки, наградой за проигрыш -2,5 для красной сетки и наградой -0,04 для любой другой проходимой сетки.
Используя тот же подход к балансу между исследованием и эксплуатацией, что и в ADP Learner, мы сначала попробуем с ξ, равным 0,99.
Вначале мы ничего не знаем об игре и полагаемся на случайное угадывание. Поэтому в самом начале мы получаем где-то −1000, −900, −800… По мере того, как мы играем все больше и больше, мы узнаем все больше и больше. В результате награда, которую мы получаем от одной игры, имеет тенденцию к увеличению. Однако с точки зрения суммы общего вознаграждения, которое мы получили за 1000 игр, учащийся MC работает намного хуже, чем учащийся ADP в нашей предыдущей истории.
Давайте посмотрим, что произойдет, если мы изменим ξ на 0,999.
Хотя общая тенденция аналогична ξ0,99, когда ξравно 0,999, мы тратим больше на исследование, что приводит к худшему общему вознаграждению.
Мы также можем сравнить производительность учащихся ADP и учащихся MC, используя процент побед во время обучающих эпизодов. Поскольку оба ученика подготовлены к 1000 играм, мы можем сравнить процент побед в их первых 100 играх, вторых 100 играх и так далее.
Как показано на этой диаграмме процента выигрышей, наше обучение ADP с ξ, равным 0,99, работает лучше всего: всего после 200 игр оно может выиграть почти в 100% игр. Для учащегося ADP с ξ, равным 0,999, ему удается выиграть почти 100% после примерно 700 игр. Для учащихся MC, если для ξ установлено значение 0,99, благодаря обучению процент выигрышей увеличился с 10 % до почти 80 %. Тем не менее, он изо всех сил пытался достичь процента побед более 80%, не говоря уже о 100%, достигнутом учеником ADP.
Таким образом, с той же проблемой MDP, наградами, количеством эпизодов обучения и факторами затухания наш ученик MC работает хуже, чем наш предыдущий ученик ADP.
Совершенствуйте учащихся MC, больше тренируясь
Как мы можем улучшить успеваемость нашего ученика MC? Чтобы сделать это, сначала нам нужно выяснить, почему учащийся MC имеет тенденцию давать худшие результаты, чем учащийся ADP. Наш обучаемый MC, который не использует модель, не изучает модель перехода. В результате он усваивает меньше информации, чем учащийся ADP. Следовательно, интуитивно понятно, что если MC-обучаемый и ADP-обучаемый тренируются с одними и теми же эпизодами, MC-обучаемый будет учиться меньше и, следовательно, работать хуже.
Как мы можем это улучшить? Ну, один из простых способов — проводить больше тренировочных эпизодов. Поскольку ученик MC учится меньше за эпизод, если он обучен большему количеству эпизодов, он может работать так же или даже лучше, чем ученик ADP. Давайте посмотрим, что произойдет, если мы обучим нашего ученика MC 10 000 эпизодов, в 10 раз больше, чем раньше.
Если мы дадим возможность обучить 10 000 игр нашему ученику MC, он получит процент выигрышей около 82%, что немного лучше, чем раньше. Как показано на приведенной выше диаграмме процента выигрышей, примерно после 5000 игр процент выигрышей перестает расти. Подводя итог, можно сказать, что простое добавление обучающих эпизодов может незначительно улучшить результаты учащихся MC.
Улучшите ученика MC, адаптировав вознаграждение
Еще один возможный способ улучшить успеваемость учащихся MC — это адаптировать вознаграждение. Например, в нашей задаче вознаграждение за победу равно 10, а вознаграждение за проигрыш равно −2,5. Что, если мы изменим 10 на какие-то другие значения?
Некоторые могут возразить, что это вознаграждение является внутренней частью проблемы MDP. Как мы можем решить проблему, произвольно изменив исходную задачу? Это обман?
Итак, когда мы говорим, что пытаемся решить эту проблему MDP, что мы на самом деле подразумеваем под решить? В нашей задаче вознаграждение не является конечной целью. На самом деле наша цель — «достичь зеленой сетки и избежать красных сеток». Для достижения этой цели мы назначаем некоторые положительные награды зеленой сетке и некоторые отрицательные награды красным сеткам, чтобы наш ученик знал, какая сетка предпочтительнее. В этом смысле вознаграждение, назначенное этим сеткам, может быть произвольным. Поэтому мы можем адаптировать или настроить эти значения вознаграждения, чтобы помочь нашему ученику достичь этой конечной цели. Например, что, если награда за проигрыш по-прежнему равна −2,5, а награда за победу увеличена с 10 до 1000? Может ли это помочь нашему учащемуся MC узнать, что мы действительно-действительно-действительно хотим, чтобы он достиг этой зеленой сетки?
На этот раз с наградой за победу, скорректированной до 1000 вместо 10, наш ученик MC, наконец, достигает 100% процента побед в 1000 играх. Это доказывает, что настройка вознаграждения является действенным методом для улучшения учащихся MC.
Если мы сравним результаты до и после настройки вознаграждения, ученик ADP не сильно изменится, в то время как ученик MC станет значительно лучше. Поскольку учащийся ADP изучает награды, а также переходную модель, изменение вознаграждений не имеет такого большого значения. Напротив, учащийся MC изучает только награды. Следовательно, корректировка вознаграждения может значительно изменить производительность ученика MC.
От Монте-Карло к временной разнице
Если сравнивать нашего учащегося MC с предыдущим учащимся ADP, преимущество заключается в том, что мы избавляемся от оценки модели перехода. Тем не менее, мы платим высокую цену за это преимущество: ученику MC требуется гораздо больше учебных эпизодов. Даже после тренировки со многими эпизодами, производительность ученика MC все еще не так хороша. Можем ли мы сделать лучше, чем это? Можем ли мы иметь еще одного обучаемого без модели, который имеет лучшую производительность, чем обучающийся ADP, без необходимости настройки вознаграждений?
Ответ, как правило, да. Один из таких методов называется временная разница (TD). В обучении с подкреплением популярный тип временной разницы называется Q-обучением, при котором Q-значения изучаются напрямую.
Начнем с того, что в MC Learner мы обновляем значения Q после каждой игры. Чтобы обновить значения Q много-много раз, нам нужно играть в игру много-много раз. Однако в Q-обучении мы можем обновлять значения Q- после каждого шага в игре. В результате мы можем обновлять значения Q- чаще и точнее с гораздо меньшим количеством игр. О Q-learning мы поговорим в следующем материале. Оставайтесь с нами и увидимся в следующий раз.
