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 -обучающая работа Джеральда Тезауро