Q-обучение - Q-learning

Часть серии о
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий Очистка данных AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Неконтролируемое обучение Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

Q - Learning является моделью свободного обучения армирования алгоритмачтобы узнать значение какоголибо действия в определенном состоянии. Для него не требуется модель среды (следовательно, «без модели»), и он может решать проблемы со стохастическими переходами и вознаграждениями, не требуя адаптации.

Для любого конечного марковского процесса принятия решений (FMDP) Q- обучение находит оптимальную политику в смысле максимизации ожидаемого значения общего вознаграждения на всех без исключения последовательных шагах, начиная с текущего состояния. Q- обучение может определить оптимальную политику выбора действий для любого данного FMDP, учитывая бесконечное время исследования и частично случайную политику. «Q» относится к функции, которую вычисляет алгоритм - ожидаемое вознаграждение за действие, выполненное в данном состоянии.

Обучение с подкреплением

Обучение с подкреплением включает в себя средство , набор состояний и набор из действий в состоянии. Выполняя действие , агент переходит из состояния в состояние. Выполнение действия в определенном состоянии обеспечивает агенту награду (числовую оценку). ${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle a \ in A}$

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

В качестве примера рассмотрим процесс посадки в поезд, в котором вознаграждение измеряется отрицательным значением общего времени, потраченного на посадку (в качестве альтернативы, стоимость посадки в поезд равна времени посадки). Одна из стратегий - входить в двери поезда, как только они открываются, сводя к минимуму начальное время ожидания для себя. Однако если поезд переполнен, то после первого действия входа в дверь у вас будет медленный вход, поскольку люди борются с вами, чтобы вы покинули поезд, когда вы пытаетесь сесть. Таким образом, общее время посадки или ее стоимость:

• 0 секунд ожидания + 15 секунд боя

На следующий день, случайно (исследование), вы решаете подождать и позволить другим людям уйти первыми. Первоначально это приводит к увеличению времени ожидания. Однако времени на борьбу с другими пассажирами меньше. В целом, этот путь имеет более высокую награду, чем предыдущий день, поскольку общее время посадки сейчас:

• 5 секунд ожидания + 0 секунд боя

Благодаря исследованию, несмотря на то, что первоначальные (терпеливые) действия, приводящие к большей стоимости (или отрицательному вознаграждению), чем в принудительной стратегии, общие затраты ниже, что открывает более выгодную стратегию.

Алгоритм

Таблица состояний Q-Learning по действиям, которая инициализируется нулем, затем каждая ячейка обновляется посредством обучения.

После шагов в будущее агент решит, какой следующий шаг. Вес для этого шага рассчитывается как , где ( коэффициент дисконтирования ) представляет собой число от 0 до 1 ( ) и имеет эффект оценки вознаграждений, полученных ранее, выше, чем полученные позже (что отражает ценность «хорошего старта»). может также интерпретироваться как вероятность успеха (или выживания) на каждом этапе . ${\ displaystyle \ Delta t}$${\ displaystyle \ gamma ^ {\ Delta t}}$${\ displaystyle \ gamma}$${\ Displaystyle 0 \ Leq \ гамма \ Leq 1}$${\ displaystyle \ gamma}$${\ displaystyle \ Delta t}$

Следовательно, в алгоритме есть функция, которая вычисляет качество комбинации состояния и действия:

${\ displaystyle Q: S \ times A \ to \ mathbb {R}}$.

Перед началом обучения инициализируется, возможно, произвольным фиксированным значением (выбранным программистом). Затем каждый раз, когда агент выбирает действие , наблюдает за наградой , входит в новое состояние (которое может зависеть как от предыдущего состояния, так и от выбранного действия) и обновляется. Ядром алгоритма является уравнение Беллмана как простое обновление итераций значений с использованием средневзвешенного значения старого значения и новой информации: ${\ displaystyle Q}$${\ displaystyle t}$${\ displaystyle a_ {t}}$${\ displaystyle r_ {t}}$${\ displaystyle s_ {t + 1}}$${\ displaystyle s_ {t}}$${\ displaystyle Q}$

${\ displaystyle Q ^ {новый} (s_ {t}, a_ {t}) \ leftarrow \ underbrace {Q (s_ {t}, a_ {t})} _ {\ text {старое значение}} + \ underbrace { \ alpha} _ {\ text {скорость обучения}} \ cdot \ overbrace {{\ bigg (} \ underbrace {\ underbrace {r_ {t}} _ {\ text {reward}} + \ underbrace {\ gamma} _ { \ text {коэффициент скидки}} \ cdot \ underbrace {\ max _ {a} Q (s_ {t + 1}, a)} _ {\ text {оценка оптимальной будущей стоимости}}} _ {\ text {новое значение (цель временной разницы)}} - \ underbrace {Q (s_ {t}, a_ {t})} _ {\ text {старое значение}} {\ bigg)}} ^ {\ text {временная разница}}}$

где - вознаграждение, полученное при переходе из состояния в состояние , - скорость обучения . ${\ displaystyle r_ {t}}$${\ displaystyle s_ {t}}$${\ displaystyle s_ {t + 1}}$${\ displaystyle \ alpha}$ ${\ Displaystyle (0 <\ альфа \ leq 1)}$

Обратите внимание, что это сумма трех факторов: ${\ displaystyle Q ^ {новый} (s_ {t}, a_ {t})}$

• ${\ Displaystyle (1- \ альфа) Q (s_ {t}, a_ {t})}$: текущее значение, взвешенное по скорости обучения. Значения скорости обучения, близкие к 1, делают изменения более быстрыми.${\ displaystyle Q}$
• ${\ Displaystyle \ альфа \, r_ {т}}$: награда, которую можно получить, если действие будет предпринято в состоянии (взвешенное по скорости обучения)${\ displaystyle r_ {t} = r (s_ {t}, a_ {t})}$${\ displaystyle a_ {t}}$${\ displaystyle s_ {t}}$
• ${\ Displaystyle \ альфа \ гамма \ макс _ {а} Q (s_ {т + 1}, а)}$: максимальное вознаграждение, которое может быть получено от государства (взвешенное по скорости обучения и коэффициенту дисконтирования)${\ displaystyle s_ {t + 1}}$

Эпизод алгоритма заканчивается, когда состояние является конечным или конечным состоянием . Тем не менее, Q- обучение может также обучаться в неэпизодических задачах (в результате свойства сходящихся бесконечных рядов). Если коэффициент дисконтирования меньше 1, значения действий конечны, даже если проблема может содержать бесконечные циклы. ${\ displaystyle s_ {t + 1}}$

Для всех конечных состояний , никогда не обновляются, но устанавливаются на значение поощрений наблюдаемого для государства . В большинстве случаев можно принять равным нулю. ${\ displaystyle s_ {f}}$${\ Displaystyle Q (s_ {f}, а)}$${\ displaystyle r}$${\ displaystyle s_ {f}}$${\ Displaystyle Q (s_ {f}, а)}$

Влияние переменных

Скорость обучения

Скорость обучения или размер шага определяют, в какой степени вновь полученная информация перекрывает старую. Коэффициент 0 заставляет агента ничего не узнавать (исключительно используя предыдущие знания), в то время как коэффициент 1 заставляет агента рассматривать только самую последнюю информацию (игнорируя предыдущие знания для изучения возможностей). В полностью детерминированных средах скорость обучения является оптимальной. Когда проблема является стохастической , алгоритм сходится при некоторых технических условиях по скорости обучения, которые требуют ее уменьшения до нуля. На практике часто используется постоянная скорость обучения, например, для всех . ${\ Displaystyle \ альфа _ {т} = 1}$${\ displaystyle \ alpha _ {t} = 0,1}$${\ displaystyle t}$

Фактор дисконтирования

Фактор дисконтирования определяет важность будущих вознаграждений. Коэффициент, равный 0, сделает агента «близоруким» (или недальновидным), учитывая только текущие вознаграждения, то есть (в правиле обновления выше), в то время как коэффициент, приближающийся к 1, заставит его стремиться к долгосрочному высокому вознаграждению. Если коэффициент скидки равен или превышает 1, значения действий могут отличаться. Ведь без конечного состояния или если агент никогда не достигает его, все истории среды становятся бесконечно длинными, а полезности с дополнительными недисконтированными вознаграждениями обычно становятся бесконечными. Даже с коэффициентом дисконтирования лишь немного ниже 1, обучение Q- функции приводит к распространению ошибок и нестабильности, когда функция цены аппроксимируется с помощью искусственной нейронной сети . В этом случае, если начать с более низкого коэффициента дисконтирования и увеличить его до конечного значения, обучение будет ускоряться. ${\ displaystyle \ gamma}$${\ displaystyle r_ {t}}$${\ displaystyle \ gamma = 1}$

Начальные условия ( Q ₀ )

Поскольку Q- обучение является итеративным алгоритмом, он неявно предполагает начальное условие перед первым обновлением. Высокие начальные значения, также известные как «оптимистические начальные условия», могут стимулировать исследование: независимо от того, какое действие выбрано, правило обновления будет иметь более низкие значения, чем другая альтернатива, тем самым увеличивая вероятность их выбора. Первую награду можно использовать для сброса начальных условий. Согласно этой идее, при первом выполнении действия вознаграждение используется для установки значения . Это позволяет немедленно обучаться в случае фиксированных детерминированных вознаграждений. Ожидается, что модель, которая включает сброс начальных условий (RIC), будет предсказывать поведение участников лучше, чем модель, которая предполагает любое произвольное начальное условие (AIC). RIC, кажется, согласуется с человеческим поведением в повторяющихся экспериментах с бинарным выбором. ${\ displaystyle r}$${\ displaystyle Q}$

Реализация

Q -learning в простейшем виде хранит данные в таблицах. Этот подход дает сбой при увеличении числа состояний / действий, поскольку вероятность того, что агент посетит конкретное состояние и выполнит конкретное действие, становится все более мала.

Аппроксимация функции

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

Одно из решений - использовать (адаптированную) искусственную нейронную сеть в качестве аппроксиматора функций. Аппроксимация функций может ускорить обучение в конечных задачах из-за того, что алгоритм может обобщить предыдущий опыт на ранее невидимые состояния.

Квантование

Другой метод уменьшения пространства состояния / действия квантует возможные значения. Рассмотрим пример, как научиться балансировать палкой на пальце. Чтобы описать состояние в определенный момент времени, необходимо указать положение пальца в пространстве, его скорость, угол наклона палки и угловую скорость палки. Это дает четырехэлементный вектор, который описывает одно состояние, то есть снимок одного состояния, закодированный в четыре значения. Проблема в том, что существует бесконечно много возможных состояний. Чтобы сократить возможное пространство допустимых действий, корзине можно присвоить несколько значений. Точное расстояние пальца от его начальной позиции (-Бесконечность до Бесконечности) неизвестно, но известно, находится ли он далеко или нет (Близко, Далеко).

История

Q- обучение было введено Крисом Уоткинсом в 1989 году. Доказательство сходимости было представлено Уоткинсом и Питером Даяном в 1992 году.

Уоткинс обращался к теме своей докторской диссертации «Учимся на отсроченном вознаграждении». Восемь лет назад, в 1981 году, та же проблема под названием «Отложенное обучение с подкреплением» была решена с помощью Crossbar Adaptive Array (CAA) Бозиновски. Матрица памяти была такой же, как и Q-таблица Q-обучения восемь лет спустя. Архитектура ввела термин «оценка состояния» в обучении с подкреплением. Алгоритм обучения перекладин, записанный в статье математическим псевдокодом , на каждой итерации выполняет следующие вычисления: ${\ Displaystyle W = \ | вес (а, s) \ |}$

• В состоянии s выполнить действие a ;
• Получить состояние следствия s ' ;
• Вычислить оценку состояния ;${\ Displaystyle v (s ')}$
• Обновить значение перекладины .${\ Displaystyle вес '(а, s) = вес (а, s) + v (s')}$

Термин «вторичное подкрепление» заимствован из теории обучения животных, чтобы смоделировать значения состояния посредством обратного распространения : значение состояния ситуации последствий возвращается к ранее встреченным ситуациям. CAA вычисляет значения состояний по вертикали и действия по горизонтали («перекладина»). Демонстрационные графики, показывающие отложенное обучение с подкреплением, содержали состояния (желательные, нежелательные и нейтральные), которые были вычислены функцией оценки состояния. Эта обучающая система была предшественницей алгоритма Q-обучения. ${\ Displaystyle v (s ')}$

В 2014 году Google DeepMind запатентовал приложение Q-обучения для глубокого обучения под названием «глубокое обучение с подкреплением» или «глубокое Q-обучение», которое позволяет играть в игры Atari 2600 на уровне опытных людей.

Варианты

Глубокое Q-обучение

Система DeepMind использовала глубокую сверточную нейронную сеть со слоями мозаичных сверточных фильтров для имитации эффектов рецептивных полей. Обучение с подкреплением нестабильно или расходится, когда для представления Q используется аппроксиматор нелинейной функции, такой как нейронная сеть. Эта нестабильность возникает из-за корреляций, присутствующих в последовательности наблюдений, того факта, что небольшие обновления Q могут значительно изменить политику агента. и распределение данных, и корреляции между Q и целевыми значениями.

Техника использует воспроизведение опыта, биологически вдохновленный механизм, который использует случайную выборку предыдущих действий вместо самого последнего действия для продолжения. Это устраняет корреляции в последовательности наблюдений и сглаживает изменения в распределении данных. Итерационные обновления корректируют Q в соответствии с целевыми значениями, которые обновляются только периодически, что дополнительно снижает корреляцию с целевым значением.

Двойное Q-обучение

Поскольку будущее максимальное приближенное значение действия в Q-обучении оценивается с использованием той же Q-функции, что и в текущей политике выбора действия, в шумной среде Q-обучение может иногда переоценивать значения действия, замедляя обучение. Чтобы исправить это, был предложен вариант под названием Double Q-Learning. Двойное Q-обучение - это алгоритм обучения с подкреплением вне политики , в котором для оценки ценности используется политика, отличная от той, которая используется для выбора следующего действия.

На практике две отдельные функции значений обучаются симметрично друг другу с использованием разных опытов, и . В этом случае этап обновления двойного Q-обучения выглядит следующим образом: ${\ displaystyle Q ^ {A}}$${\ displaystyle Q ^ {B}}$

${\ displaystyle Q_ {t + 1} ^ {A} (s_ {t}, a_ {t}) = Q_ {t} ^ {A} (s_ {t}, a_ {t}) + \ alpha _ {t } (s_ {t}, a_ {t}) \ left (r_ {t} + \ gamma Q_ {t} ^ {B} \ left (s_ {t + 1}, \ mathop {\ operatorname {arg ~ max}) } _ {a} Q_ {t} ^ {A} (s_ {t + 1}, a) \ right) -Q_ {t} ^ {A} (s_ {t}, a_ {t}) \ right)}$, а также

${\ displaystyle Q_ {t + 1} ^ {B} (s_ {t}, a_ {t}) = Q_ {t} ^ {B} (s_ {t}, a_ {t}) + \ alpha _ {t } (s_ {t}, a_ {t}) \ left (r_ {t} + \ gamma Q_ {t} ^ {A} \ left (s_ {t + 1}, \ mathop {\ operatorname {arg ~ max}) } _ {a} Q_ {t} ^ {B} (s_ {t + 1}, a) \ right) -Q_ {t} ^ {B} (s_ {t}, a_ {t}) \ right). }$

Теперь оценочная стоимость дисконтированного будущего оценивается с использованием другой политики, которая решает проблему завышения.

Позднее в 2015 году этот алгоритм был модифицирован и объединен с глубоким обучением , как в алгоритме DQN, в результате чего получился Double DQN, который превосходит исходный алгоритм DQN.

Другие

Отложенное Q-обучение - это альтернативная реализация алгоритма онлайн- Q- обучения с вероятным приблизительно правильным (PAC) обучением .

Greedy GQ - это вариант Q- обучения для использования в сочетании с (линейной) аппроксимацией функций. Преимущество Greedy GQ заключается в том, что сходимость гарантируется даже тогда, когда для оценки значений действий используется аппроксимация функций.

Распределительный Q-обучение является вариантом Q - Learning , которая стремится моделировать распределение доходности , а не ожидаемый доход каждого действия. Было замечено, что это облегчает оценку с помощью глубоких нейронных сетей и может включать альтернативные методы контроля, такие как управление с учетом риска.

Ограничения

Стандартный алгоритм Q-обучения (с использованием таблицы) применяется только к дискретным пространствам действий и состояний. Дискретность этих значений приводит к неэффективному обучению, во многом из-за проклятия размерности . Однако существуют адаптации Q-обучения, которые пытаются решить эту проблему, такие как Q-Learning нейронной сети с проводной связью. ${\ displaystyle Q}$

Смотрите также

• Обучение с подкреплением
• Обучение временной разнице
• SARSA
• Повторяющаяся дилемма заключенного
• Теория игры

использованная литература

внешние ссылки

• Уоткинс, CJCH (1989). Учимся на отсроченных вознаграждениях. Докторская диссертация, Кембриджский университет, Кембридж, Англия.
• Strehl, Li, Wiewiora, Langford, Littman (2006). Обучение с подкреплением без модели PAC
• Обучение с подкреплением: введение Ричарда Саттона и Эндрю С. Барто, онлайн-учебник. См. "6.5 Q-Learning: Управление TD вне политики" .
• Piqle: универсальная платформа Java для обучения с подкреплением
• Лабиринт обучения с подкреплением , демонстрация того, как провести муравья через лабиринт с помощью Q- обучения
• Q- обучающая работа Джеральда Тезауро