Skip to content
Назад к результатам поиска

Q-обучение

Автор метода
Christopher Watkins & Peter Dayan
Год
1992
Тип
Model-free reinforcement-learning control algorithm
Семейство
Reinforcement learning

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Оно является off-policy (вне политики): оно изучает оптимальные ценности действий, следуя политике исследования, и при стандартных условиях доказуемо сходится к оптимальной политике.

Интуиция метода

Агенту, обучающемуся методом проб и ошибок, необходимо знать для каждой ситуации, насколько хорошим является каждое возможное действие в долгосрочной перспективе. Q-обучение поддерживает именно это: таблицу (или функцию) Q-значений, оценивающую общую будущую награду за выполнение действия в состоянии и последующее оптимальное поведение. Каждый раз, когда агент действует, наблюдает награду и попадает в новое состояние, он корректирует Q-значение в сторону того, что он только что испытал, плюс наилучшее, что, по его мнению, он может сделать дальше. Важно, что оно обновляется в сторону ЛУЧШЕГО следующего действия независимо от того, что было сделано на самом деле — так оно может свободно исследовать, продолжая изучать оптимальную стратегию.

История

Кристофер Уоткинс представил Q-обучение в своей диссертации 1989 года, а Уоткинс и Дайэн (1992) предоставили доказательство сходимости, утвердив его как краеугольный камень обучения с подкреплением. Оно обобщает обучение временных различий для управления и лежит в основе последующих достижений — в частности, Deep Q-Networks (Mnih et al., 2015), которые объединили Q-обучение с глубокими сетями для игры в Atari с пикселей. Оно канонически рассматривается в учебнике Саттона и Барто и остается стандартной отправной точкой для обучения с подкреплением на основе ценности.

Когда применять

Используйте Q-обучение для задач последовательного принятия решений, сформулированных как марковский процесс принятия решений (MDP), где вы можете получать выборки переходов и наград, но не имеете (или имеете ненадежную) модель динамики — управление, игры, маршрутизация, планирование и адаптивные системы. Табличное Q-обучение подходит для небольших дискретных пространств состояний-действий и сходится к оптимуму при достаточном исследовании и уменьшающемся размере шага. Для больших или непрерывных пространств таблица заменяется аппроксиматором функции (Deep Q-Networks). Оно предполагает марковское свойство и стационарную среду, может быть неэффективным по выборкам, а оператор max вызывает оптимистичную (максимизирующую) смещенность, которая устраняется вариантами, такими как Double Q-learning. Когда требуется стохастическая или непрерывная политика действий, альтернативой являются методы градиента политики.

Ограничения и замечания

  • Табличная форма не масштабируется на большие или непрерывные пространства состояний/действий.
  • Неэффективен по выборкам; может потребоваться много эпизодов для сходимости.
  • Смещенность максимизации (переоценка) от оператора max; смягчается Double Q-learning.
  • Предполагает (стационарный) марковский процесс принятия решений; испытывает трудности при частичной наблюдаемости или дрейфе.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Без модели: не требует модели переходов/наград, только выборочный опыт.
  • Вне политики (Off-policy): изучает оптимальную политику, исследуя с другой политикой.
  • Доказуемо сходится к оптимальным ценностям действий при стандартных условиях.
  • Простой, фундаментальный и основа для Deep Q-Networks и многих расширений.

Применение

  • Игры и задачи симуляции управления.
  • Навигация роботов и адаптивное управление.
  • Динамическая маршрутизация, планирование и распределение ресурсов.
  • Рекомендации и адаптивные политики взаимодействия.
  • Базовый метод на основе ценности перед Deep Q-Networks.

Как это работает

Как это работает

1

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

Формула
Q(s,a) \approx \mathbb{E}\!\left[\textstyle\sum_{k\ge0}\gamma^{k} r_{t+k+1}\mid s_t=s,a_t=a\right]
2

После каждого перехода (состояние s, действие a, награда r, следующее состояние s') Q-обучение обновляет Q(s, a) шагом α в сторону целевого значения временных различий r + γ·max по следующим действиям от Q(s', a'). 'max' делает его off-policy и направляет обучение на оптимальное значение, независимо от фактически выполненного следующего действия.

Формула
Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\big]
3

Для сбора опыта агент действует согласно политике исследования, обычно ε-жадной: обычно выбирает текущее лучшее действие, но с вероятностью ε выбирает случайное. Исследование гарантирует, что все пары состояний-действий будут опробованы, что требуется для гарантии сходимости; ε обычно уменьшается со временем.

Формула
a = \begin{cases}\arg\max_a Q(s,a) & \text{prob } 1-\epsilon\\ \text{random} & \text{prob } \epsilon\end{cases}
4

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

Формула
\pi^*(s) = \arg\max_a Q^*(s,a)

Частые ошибки

  • Недостаточное исследование (ε слишком мало/слишком быстро уменьшается), что приводит к неизученному оптимуму.
  • Неправильный график скорости обучения, вызывающий расходимость или мучительно медленное обучение.
  • Применение табличного Q-обучения к большим пространствам вместо аппроксиматора функции.
  • Игнорирование смещенности переоценки в стохастических задачах, где помогает Double Q-learning.

Часто задаваемые вопросы

Что означает «вне политики» (off-policy) в Q-обучении?

Это означает, что Q-обучение изучает ценность оптимальной политики, в то время как агент следует другой (исследовательской) политике поведения. Цели обновления r + γ·max Q(s', a') — лучшее следующее действие — а не фактически выполненное действие, поэтому исследование не смещает изученный оптимум.

Как Q-обучение связано с Deep Q-Networks (DQN)?

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

Почему Q-обучение переоценивает значения?

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

Похожие методы

Источники

  1. Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3–4), 279–292.

    Открыть ссылку DOI
    Скопировано.
  2. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.

    ISBN: 978-0-262-03924-6
    Скопировано.