О трёх существенных недостатках известных алгоритмов обучения с подкреплением (и о том, как их устранить)

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

I. Выбор переоцененных действий

Проблема

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

В предельном случае каждое действие выполнялось бы бесконечно часто, и тогда значения функции полезности Q сходились бы к истинным значениям. Однако на практике мы работаем с ограниченными выборками и смещёнными значениями функции Q, а потому алгоритм Q-learning всегда выбирает действия с завышенными значениями функции полезности!

Представьте ситуацию: мы играем в два одинаковых игровых автомата. Автомат A уже на первых итерациях выдаёт вознаграждения выше среднего, поэтому для него значение функции Q больше и мы продолжаем играть в автомат A. Поскольку автомат B выбирается редко, чтобы понять, что значения функции Q для обоих автоматов на самом деле одинаковы, нужно много времени.

В целом функции полезности всегда будут несовершенными, поэтому RL имеет склонность выполнять переоценённые действия. В некотором смысле RL имеет нежелательное свойство — «вознаграждать» плохой выбор действий.

Решения

Причину проблем Q-learning можно отследить; она состоит в выборе действий и обновлении полезности на основе одних и тех же наблюдений. Выбор действий и обновление можно разделить, выполняя выбор действий с помощью одной политики, а обновление полезности — с помощью другой. Именно это делает Double Q-learning (Van Hasselt, 2010).

Double Q-learning выбирает действия с помощью одной сети, а значение функции Q обновляет на основе выходных данных другой сети. Эта процедура отделяет выбор действий от обучения и таким образом борется с переоценкой [источник: Van Hasselt (2010)].

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

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

II. Неудовлетворительные обновления градиента политики

Проблема

Алгоритмы градиента политики разрабатываются десятилетиями. Они лежат в основе всех современных моделей «актор-критик». Алгоритмы градиента ванильной политики, например REINFORCE, для определения направления обновления веса опираются на градиенты. Сочетание высоких вознаграждений и больших градиентов даёт сильный сигнал обновления.

Традиционная функция обновления градиента политики, которая обновляет веса политики θ на основе градиента целевой функции ∇\_θj(θ) и размера шага α

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

Слева: политика сильно обновляется и упускает (проскакивает) максимум вознаграждения. Справа: пример зависания в локальном оптимуме с градиентами, близкими к 0 [изображение предоставлено автором]

Градиент даёт только локальную информацию. Он показывает величину наклона, но не даёт информацию о том, насколько сильно нужно продвигаться в данном направлении; поэтому можно проскочить. Кроме того, политики градиентов не учитывают, что малый сигнал градиента может привести к зависанию на неоптимальном плато.

Еще хуже то, что мы не можем управлять этим поведением, сохраняя обновления веса в пределах ограниченной области параметров. Например, на рисунке ниже обновления веса одинаковой величины оказывают на политику очень разное влияние.

Пример двух обновлений гауссовской политики. Несмотря на то что оба обновления имеют одинаковый размер с точки зрения пространства параметров, слева на политику явно оказывается влияние сильнее, чем справа [изображение предоставлено автором]

Для начала можно поэкспериментировать с различными алгоритмами обучения. Традиционный алгоритм стохастического градиентного спуска (SGD) учитывает только первые моменты. Современные алгоритмы обучения (например, ADAM) учитывают вторые моменты, тем самым часто существенно повышают эффективность. Несмотря на то, что это не решает проблему полностью, увеличение эффективности может быть значительным.

Регуляризация энтропии является распространённым способом предотвращения преждевременной сходимости алгоритмов градиента ванильной политики. Грубо говоря, энтропия в RL — это показатель непредсказуемости выбора действия. Регуляризация энтропии добавляет бонус за осуществление неизвестных действий. Этот бонус выше в случае, если мы меньше узнали о системе:

Мера энтропии при обучении с подкреплением

Более сложные варианты алгоритмов политики градиента также учитывают производные второго порядка, которые предоставляют информацию о локальной чувствительности функции. На плато можно безопасно, без последствий делать большие шаги. При крутом наклоне и извилистостях лучше отдать предпочтение малым шагам. Такие алгоритмы, как градиент естественной политики, TRPO и PPO учитывают чувствительность к обновлениям, явно или неявно принимая в расчёт производные второго порядка. На данный момент PPO — это алгоритм перехода к градиенту политики, он даёт хороший баланс между простотой внедрения, скоростью и производительностью.

Схема обновления веса для градиентов естественной политики. Матрица Фишера F(θ) содержит информацию о локальной чувствительности; она генерирует динамические обновления веса

III. Недостаточная эффективность обучения вне политики (off-policy)

Проблема

Некоторые алгоритмы (например, на базе Q-learning) обучаются вне политики. Это означает, что обновления могут выполняться с действием, которое отличается от фактически наблюдаемого. В то время как для обучения с политикой (on-policy) требуется кортеж (s,a, r,s’,a’) — на самом деле, так же, как и в одноименном алгоритме SARSA, — для обучения вне политики используется наиболее известное действие a* вместо a’. Следовательно, мы храним (s,a,r,s’) только для обновления веса и обучаем политике независимо от действий агента.

Благодаря настройке при обучении вне политики могут повторно использоваться предыдущие наблюдения, которые извлекаются из буфера воспроизведения опыта. Это особенно удобно, когда наблюдения вычислительно дороги. Мы просто передаём состояние s’ в нашу политику и получаем действие a*, А для обновления значений функции Q используем результирующее значение. Динамику перехода от s к s’ пересчитывать не нужно.

К сожалению, даже после тщательного обучения вне политики алгоритма обучения с подкреплением на большом наборе данных на практике он часто работает далеко не так хорошо. Почему же?

Проблема сводится к распространённой статистической оговорке. Предполагается, что обучающий набор репрезентативен для истинного набора данных. Если это не так (а это часто бывает не так, поскольку обновлённые политики генерируют разные пары «состояние — действие»), политика подходит для набора данных, не отражающего среду, в которой в конечном счёте работает агент.

Решения

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

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

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

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

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

Краткое содержание

Выше рассматриваются три распространённых недостатка классических RL-алгоритмов, а также стратегии их устранения.

I. Переоцененные действия

Проблема:

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

Решения:

• Используйте целевые сети для снижения корреляции между целью и наблюдением (например, как в алгоритме Double Q-learning).
• Учитывайте неопределённость расчёта полезности при выборе действий (например, границы неопределённости, градиенты знаний).

II. Неудовлетворительные обновления градиента политики

Проблема:

• Алгоритмы градиента политики часто делают неудовлетворительные шаги обновления. Например, очень малые шаги, когда зависают в локальном оптимуме, или большие шаги, из-за которых упускают наибольшее вознаграждение.

Решения:

• Используйте вместо стандартного стохастического градиентного спуска такой алгоритм обучения, например ADAM, который в дополнение к градиентам первого порядка учитывает значения моментов.
• Добавьте к сигналу вознаграждения бонус энтропии, который в дальнейшем будет мотивировать исследование неизученных областей.
• Применяйте алгоритмы, которые включают (явно или неявно) производные второго порядка, например градиенты естественной политики, TRPO или PPO.

III. Недостаточная эффективность обучения вне политики (off-policy)

Проблема:

• События в буфере воспроизведения могут быть нерепрезентативными для событий вне выборки, поэтому значения экстраполируются неправильно и эффективность снижается.

Решения:

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

Полезная теория и много практики — на наших курсах:

• Профессия Data Scientist (24 месяца)
• Профессия Fullstack-разработчик на Python (16 месяцев)