Q-Learning - один из самых известных алгоритмов обучения с подкреплением (RL).
В этом рассказе мы обсудим важную часть алгоритма: стратегию исследования. Но прежде давайте начнем с некоторых вводных понятий и обозначений.
Обучение с подкреплением (RL)
RL - это область машинного обучения, в которой агент подключается к среде посредством восприятия состояний, выбора действий и получение вознаграждений. На каждом шаге агент наблюдает за состоянием, выбирает и выполняет действие, это изменяет его состояние и выдает вознаграждение.
Марковские процессы принятия решений (MDP)
В наиболее традиционных условиях RL решает MDP. Несмотря на то, что в самом сердце RL, мы не будем вдаваться в теорию MDP в этой истории. Вот хорошее введение в MDP.
Мы решим проблему лесного пожара MDP, доступного в Python MDP Toolbox.
Лес управляется двумя действиями: «Подождать» и «Вырубить». Каждый год решается какое-то действие, во-первых, с целью сохранить старый лес для дикой природы, а во-вторых, чтобы заработать деньги, продавая распиленную древесину. Каждый год существует вероятность p, что пожар сжигает лес (и 1-p, что лес растет).
Назовем наш MDP (S, A, P, R, γ), где:
- S - пространство состояний (конечное): 3 возрастных класса деревьев: возрастной класс 0–20 лет, 21–40 лет, более 40 лет.
- A - это пространство действия (конечное): «Подождите» или «Вырезать».
- P и R - матрицы перехода и вознаграждения: закрытые формы которых легко выразить
- γ - коэффициент дисконтирования, представляющий разницу в значимости между долгосрочным и краткосрочным вознаграждением.
- Политика π - это стационарное распределение действий с учетом текущего состояния (марковское свойство)
Цель состоит в том, чтобы найти оптимальную политику π * MDP без каких-либо знаний о динамике MDP.
Обратите внимание: если бы у нас были такие знания, такие алгоритмы, как Итерация оптимального значения, смогли бы найти оптимальную политику.
Оптимальная политика, заключающаяся в том, чтобы подождать, пока лес достигнет самого старшего возраста, и вырубить его, здесь довольно интуитивно понятна, поскольку мы сделали вознаграждение за рубку леса в самом старом состоянии в 5 раз больше, чем вознаграждение за рост (r1 = 10, r2 = 50).
Q-Learning
Q в Q-Learning обозначает функцию качества политики (π), которая отображает любое состояние, пару действий (s, a) с ожидаемым накопленным дисконтированным будущим вознаграждением, полученным путем выбора a при наблюдении s.
Q-Learning называется «свободным от модели», что означает, что оно не пытается моделировать динамику MDP, а напрямую оценивает Q-значения каждого действия в каждом состоянии. Затем политику можно составить, выбрав действие с наивысшим значением Q в каждом состоянии.
Если агент посещает все пары состояние-действие бесконечное количество раз, Q-обучение сходится к оптимальной Q-функции [1].
Опять же, мы не будем вдаваться во все детали Q-Learning. Если вы не знакомы с этим, вот видео замечательного Сираджа Равала, объясняющее это.
А вот наша реализация Q-Learning на Python.
Обратите внимание, что скорость обучения (альфа), используемая здесь, является полиномиальной с ω = 4/5 в соответствии с результатами [3].
Используемая здесь стратегия разведки (ε-жадность) будет подробно описана позже.
Компромисс между разведкой и эксплуатацией
Алгоритмы последовательного обучения предполагают фундаментальный выбор:
- Эксплуатация: примите правильное решение, учитывая текущую информацию
- Исследование: собирайте больше информации, принимая другие решения.
Успешный баланс между исследованием и эксплуатацией имеет большое влияние на эффективность обучения агента. Слишком много исследований не позволяет агенту максимизировать краткосрочное вознаграждение, потому что выбранные действия по исследованию могут привести к плохим результатам со стороны окружающей среды. С другой стороны, использование среды с неполными знаниями не позволяет максимизировать долгосрочное вознаграждение, поскольку выбранные действия по эксплуатации могут оставаться неоптимальными.
ε-жадная стратегия разведки
Эта стратегия заключается в выборе случайных действий с вероятностью ε на каждом шаге.
Это, вероятно, самая используемая и простая стратегия исследования. Разведка настраивается на ε. Во многих реализациях ε со временем затухает, но во многих случаях установка постоянного значения ε работает на практике.
Стратегии разведки «Оптимизм перед лицом неопределенности»
Эта концепция была впервые введена для решения среды Стохастического многорукого бандита (SMAB), очень старого процесса принятия решений, когда игрок должен решить, на какой машине играть на каждом этапе, чтобы максимизировать ожидаемый результат. вознаграждение со скидкой, выдаваемое машинами.
Игрок сталкивается с компромиссом между исследованием и эксплуатацией, эксплуатируя машину (или руку) с наивысшими средними наградами (следуйте за лидером) или исследуя другие машины, на которых не разыгрались достаточно, в надежде получить более высокие награды.
Эта формулировка SMAB очень похожа на задачу исследования в Q-Learning:
- Эксплуатация: выберите действие с наибольшим значением Q в данном состоянии.
- Исследование: изучите другие действия (выберите либо недостаточно посещенных действий, либо не посещенных вовсе).
Оптимизм перед лицом неопределенности (OFU) гласит: всякий раз, когда мы не уверены в исходе руки, мы рассматриваем наилучший возможный мир и выбираем лучшую руку.
Интуиция, лежащая в основе OFU, такова:
- Если мы находимся в лучшем возможном мире: OFU выбирает лучшую руку (без сожаления)
- Если мы находимся не в лучшем возможном мире: неопределенность снижается (оптимально)
Одним из самых известных алгоритмов OFU является алгоритм верхней границы уверенности (UCB) [2]. А вот как мы адаптировали его к Q-Learning. Позволять:
- Q (s, a): (масштабированное) значение Q действия a в состоянии s
- N (t, s, a): количество раз, когда действие a было выбрано в состоянии s в момент времени t
Цель агента - сыграть: Argmax {Q (s, a) / a ∈ A}. Что означает выбор действия с максимальным значением Q в состоянии s. Но реальный Q (s, a) неизвестен в момент времени t:
Имеем: Q (s, a) = ‹Q (t, s, a)› + (Q (s, a) - ‹Q (t, s, a)›), причем ‹Q (t, s, a ) ›Расчетное значение Q в момент времени t.
(Q (s, a) - ‹Q (t, s, a)›) соответствует термину ошибки, который мы можем оценить сверху и воспроизвести OFU.
Неравенство Хёффдинга - один из способов ограничить эту ошибку. Фактически, мы можем доказать, что w.h.p. когда t растет:
Оптимистическую стратегию можно записать как: Argmax {Q + (t, s, a) / a ∈ A}
Где β ≥ 0 настраивает исследование. Когда β = 0, стратегия использует только прошлые оценки (стратегия «Следуй за лидером»).
Эта граница наиболее часто используется в данной области. Многие другие работы были выполнены для уточнения этих границ (UCB-V, UCB *, KL-UCB, Bayes-UCB, BESA [4] и т. Д.).
Вот наша реализация классической стратегии исследования UCB и результаты ее использования в Q-Learning.
Исследование UCB, кажется, очень быстро приносит высокие награды, однако процесс обучения нарушается ранним исследованием, для более сложных MDP это может быть полезно, поскольку помогает агенту выбраться из неоптимальных решений.
Давайте сравним две стратегии более внимательно.
Заключение и дальнейшая работа
Q-Learning - один из наиболее часто используемых алгоритмов обучения с подкреплением. В этой истории мы обсудили важность стратегий разведки и использование стратегии разведки UCB вместо хорошо известной ε-жадной разведки. В Q-Learning можно использовать более изощренные оптимистические стратегии для лучшего баланса между исследованием и эксплуатацией.
В нашей будущей истории мы будем решать более сложные задачи, используя методы глубокого обучения с подкреплением, следите за обновлениями!
использованная литература
[1] Т. Яаккола, М. И. Джордан, С. П. Сингх, «О сходимости алгоритмов стохастического итеративного динамического программирования» Нейронные вычисления, т. 6, вып. 6. С. 1185–1201, 1994.
[2] П. Ауэр, «Использование границ уверенности для компромиссов между эксплуатацией и разведкой», Journal of Machine Learning Research 3 397–422, 2002.
[3] Эвен-Дар и Ю. Мансур, «Скорость обучения для Q-обучения», Journal of Machine Learning Research 5 1-25, 2003.
[4] А. Баранси, О.-А. Майярд (также наш профессор RL) и С. Маннор, «Субвыборка для многоруких бандитов», Объединенная европейская конференция по машинному обучению и открытию знаний в базах данных, 115–131, 2014.
