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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

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

После ${\displaystyle \Delta t}$ Шаги в будущее агент решит какой-нибудь следующий шаг. Вес для этого шага рассчитывается как ${\displaystyle \gamma ^{\Delta t}}$, где ${\displaystyle \gamma }$ (в коэффициент дисконтирования) - число от 0 до 1 (${\displaystyle 0\leq \gamma \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^{new}(s_{t},a_{t})\leftarrow \underbrace {Q(s_{t},a_{t})} _{\text{old value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot \overbrace {{\bigg (}\underbrace {\underbrace {r_{t}} _{\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)}}-\underbrace {Q(s_{t},a_{t})} _{\text{old value}}{\bigg )}} ^{\text{temporal difference}}}$

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

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

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

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

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

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

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

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

Фактор скидки

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

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

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

Реализация

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

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

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

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

Квантование

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

История

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

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

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

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

В 2014 Google DeepMind запатентованный^[16] применение Q-обучения для глубокое обучение под названием "глубокое обучение с подкреплением" или "глубокое Q-обучение", которое может Atari 2600 игры на профессиональном человеческом уровне.

Варианты

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

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

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

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

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

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

${\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.^[19]

Другие

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

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

Ограничения

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

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

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

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

1. Мело, Франсиско С. «Конвергенция Q-обучения: простое доказательство» (PDF).
2. Матиизен, Тамбет (19 декабря 2015 г.). «Демистификация обучения с глубоким подкреплением». neuro.cs.ut.ee. Лаборатория вычислительной неврологии. Получено 2018-04-06.
3. Саттон, Ричард; Барто, Эндрю (1998). Обучение с подкреплением: введение. MIT Press.
4. Рассел, Стюарт Дж.; Норвиг, Питер (2010). Искусственный интеллект: современный подход (Третье изд.). Prentice Hall. п. 649. ISBN  978-0136042594.
5. Бэрд, Лимон (1995). «Остаточные алгоритмы: обучение с подкреплением с аппроксимацией функций» (PDF). ICML: 30–37.
6. Франсуа-Лаве, Винсент; Фонтено, Рафаэль; Эрнст, Дэмиен (07.12.2015). «Как отказаться от глубокого обучения с подкреплением: к новым динамическим стратегиям». arXiv:1512.02011 [cs.LG ].
7. Саттон, Ричард С .; Барто, Эндрю Г. «2.7 Оптимистические начальные значения». Обучение с подкреплением: введение. Архивировано из оригинал на 2013-09-08. Получено 2013-07-18.
8. Штейнгарт, Ханан; Нейман, Тал; Левенштейн, Йонатан (май 2013 г.). «Роль первого впечатления в оперантном обучении» (PDF). Журнал экспериментальной психологии: Общие. 142 (2): 476–488. Дои:10.1037 / a0029550. ISSN  1939-2222. PMID  22924882.
9. Хасселт, Хадо ван (5 марта 2012 г.). «Обучение с подкреплением в непрерывных пространствах состояний и действий». В Виринге, Марко; Оттерло, Мартин ван (ред.). Обучение с подкреплением: современное состояние. Springer Science & Business Media. С. 207–251. ISBN  978-3-642-27645-3.
10. Тесауро, Джеральд (март 1995). "Изучение временной разницы и TD-Gammon". Коммуникации ACM. 38 (3): 58–68. Дои:10.1145/203330.203343. S2CID  8763243. Получено 2010-02-08.
11. Уоткинс, C.J.C.H. (1989), Учимся на отсроченных вознаграждениях (PDF) (Докторская диссертация), Кембриджский университет
12. Уоткинс и Даян, C.J.C.H., (1992), "Q-обучение. Машинное обучение"
13. Божиновски, С. (15 июля 1999 г.). «Crossbar Adaptive Array: первая сеть коннекционистов, решившая проблему отложенного обучения с подкреплением». В Добникаре, Андрей; Стил, Найджел С.; Пирсон, Дэвид У .; Альбрехт, Рудольф Ф. (ред.). Искусственные нейронные сети и генетические алгоритмы: материалы международной конференции в Портороже, Словения, 1999 г.. Springer Science & Business Media. С. 320–325. ISBN  978-3-211-83364-3.
14. Божиновский, С. (1982). «Самообучающаяся система с использованием вторичного подкрепления». В Trappl, Роберт (ред.). Кибернетика и системные исследования: материалы шестого европейского совещания по кибернетике и системным исследованиям. Северная Голландия. С. 397–402. ISBN  978-0-444-86488-8.
15. Барто, А. (24 февраля 1997 г.). «Обучение с подкреплением». В Омидваре, Омиде; Эллиотт, Дэвид Л. (ред.). Нейронные системы для управления. Эльзевир. ISBN  978-0-08-053739-9.
16. «Методы и устройства для обучения с подкреплением, патент США № 20150100530A1» (PDF). Патентное ведомство США. 9 апреля 2015 г.. Получено 28 июля 2018.
17. Мних, Владимир; Кавукчуоглу, Корай; Сильвер, Дэвид; Русу, Андрей А .; Венесс, Джоэл; Bellemare, Marc G .; Грейвс, Алекс; Ридмиллер, Мартин; Фиджеланд, Андреас К. (февраль 2015 г.). «Контроль на уровне человека посредством глубокого обучения с подкреплением». Природа. 518 (7540): 529–533. Bibcode:2015Натура.518..529M. Дои:10.1038 / природа14236. ISSN  0028-0836. PMID  25719670. S2CID  205242740.
18. ван Хасселт, Хадо (2011). «Двойное Q-обучение» (PDF). Достижения в системах обработки нейронной информации. 23: 2613–2622.
19. ван Хасселт, Хадо; Гез, Артур; Серебро, Дэвид (2015). «Глубокое обучение с подкреплением с двойным Q-обучением» (PDF). Конференция AAAI по искусственному интеллекту: 2094–2100. arXiv:1509.06461.
20. Штрел, Александр Л .; Ли, Лихонг; Wiewiora, Эрик; Лэнгфорд, Джон; Литтман, Майкл Л. (2006). «Обучение с подкреплением без модели Pac» (PDF). Proc. 22-й ICML: 881–888.
21. Маэй, Хамид; Сепешвари, Чаба; Бхатнагар, Шалабх; Саттон, Ричард (2010). «К внеполитическому контролю обучения с аппроксимацией функций в материалах 27-й Международной конференции по машинному обучению» (PDF). С. 719–726. Архивировано из оригинал (PDF) на 2012-09-08. Получено 2016-01-25.
22. Гаскетт, Крис; Веттергрин, Дэвид; Зелинский, Александр (1999). "Q-Learning в непрерывных пространствах состояний и действий" (PDF).

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

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