Q-обучение

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

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

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

Основная статья: Обучение с подкреплением

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

$Q^{new}(S_{t},A_{t})\leftarrow (1-\underbrace {\alpha } _{\text{learning rate}})\cdot \underbrace {Q(S_{t},A_{t})} _{\text{current value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot {\bigg (}\underbrace {\underbrace {R_{t+1}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(S_{t+1},a)} _{\text{estimate of optimal future value}}} _{\text{new value (temporal difference target)}}{\bigg )}$

где $R_{t+1}$ это награда, получаемая при переезде из штата $S_{t}$ государству $S_{t+1}$, и $\alpha$ это скорость обучения $(0<\alpha \leq 1)$.

Обратите внимание, что $Q^{new}(S_{t},A_{t})$ представляет собой сумму трех факторов:

• $(1-\alpha )Q(S_{t},A_{t})$: текущее значение (взвешенное на единицу минус скорость обучения)
• $\alpha \,R_{t+1}$: награда $R_{t+1}$ получить, если действие $A_{t}$ принимается в состоянии $S_{t}$ (взвешено по скорости обучения)
• $\alpha \gamma \max _{a}Q(S_{t+1},a)$: максимальная награда, которую можно получить от государства $S_{t+1}$(взвешено по скорости обучения и коэффициенту дисконтирования)

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

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

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

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

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

Коэффициент скидки

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

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

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

Реализация

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

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

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

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

Квантование

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

История

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

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

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

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

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

Варианты

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

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

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

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

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

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

$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)$, и

$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) обучением .

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

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

Мультиагентное обучение

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

Ограничения

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

См. также

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

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

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