Или, как я люблю это называть, «Черная магия дисконтных факторов»

Я впервые обнаружил эту проблему благодаря моему руководителю, профессору Прутьеру, когда проверял свое предложение о втором лабораторном занятии курса Обучение с подкреплением (EL2805), которое мы проводили в KTH в прошлом году осенью 2020 года.

Проблема достаточно серьезна, чтобы затронуть большинство алгоритмов глубокого обучения с подкреплением, включая A3C [7], SAC [8], алгоритм ACKTR [9] и другие.

Примерно вот что прислал мне мой руководитель:

Привет, Алессио, у меня вопрос относительно теоремы о градиенте политики. Среднее значение относится к μ, что является распределением состояний со скидкой. Но как обычно люди оправдывают тот факт, что мы используем опыт, генерируемый стационарным распределением по политике, индуцированным политикой π, вместо дисконтированного распределения μ?

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

Если вы еще не понимаете, о чем я говорю, позвольте мне вкратце напомнить вам, как работает теорема о политическом градиенте (PG) [1].

Теорема о политическом градиенте

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

Основная идея заключается в следующем:

можем ли мы улучшить эффективность политики π, параметризованной параметром θ, с помощью градиента некоторой целевой функции J (θ) по отношению к θ? Затем, просто используя методы стохастического градиентного подъема, мы можем улучшить производительность политики в соответствии с этим градиентом.

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

Короткое описание:

  1. Первое ожидание - это просто дисконтированная стоимость политики π , а второе ожидание - двойная форма первого (первое учитывает время, а второе - рассматривает пространство состояние-действие ; проверьте Эргодическую теорему, чтобы лучше понять эту двойственность).
  2. Во втором ожидании мы принимаем математическое ожидание относительно дисконтированного распределения состояний μ, индуцированного политикой π.

Как работает теорема PG? Для дисконтированного критерия теорема PG утверждает, что градиент J (θ) просто равен

Обратите внимание, как математическое ожидание напоминает двойственную форму J (θ). Формула может показаться тривиальной, но это не так по следующей причине:

В теореме PG градиент J (θ) не зависит от градиента дисконтированного распределения состояний μ, даже если μ зависит от политики π.

Этот результат часто игнорируется в блогах об обучении с подкреплением, но он особенно важен, поскольку в нем говорится, что градиент J (θ) является средним значением, взятым относительно дисконтированного распределения состояний μ, и нам не нужно учитывать, как это распределение изменяется. относительно θ при изменении θ.

Однако распределение состояний со скидкой является корнем всех проблем.

Итак, в чем проблема современных алгоритмов глубокого обучения с подкреплением?

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

Следовательно, образцы, используемые для обновления политики, должны распределяться в соответствии с распределением состояний со скидкой μ.

Однако почти во всех статьях, если не во всех, политика обновляется с использованием выборок состояний, собранных при выполнении политики π. Другими словами, для обновления политики мы используем выборки, распределенные в соответствии с распределением по политике, индуцированным π, а не дисконтированным распределением μ.

Какая разница? Вкратце, это похоже на исключение коэффициента дисконтирования из государственного распределения.

  • Градиент политики вычисляется неправильно, поскольку мы используем образцы, не распределенные по μ.
  • Как следствие, мы не оптимизируем исходную целевую функцию J (θ).
  • Очевидно, что эта проблема ставит под сомнение достоверность всех эмпирических результатов, полученных в области глубокого обучения с подкреплением, и может поставить под угрозу применимость современных алгоритмов глубокого обучения с подкреплением в реальных приложениях.

Никто раньше не обсуждал эту проблему?

Когда я впервые обсудил эту проблему со своим руководителем, это выглядело как нечто новое, о чем никто никогда не думал. Однако быстрый поиск показал, что авторы в [2], «Является ли градиент политики градиентом?» (Нота и Томас), недавно выразили озабоченность по поводу той же проблемы (она была опубликована последней год, в 2020).

  • В [2] Нота и Томас утверждают, что градиент, вычисленный таким образом, не является градиентом какой-либо функции. Не гарантируется, что алгоритмы, использующие этот градиент, приведут к «хорошему» параметру θ.
  • Более того, всегда в [2] они показывают, что можно построить «контрпример, в котором фиксированная точка глобально пессимальна по отношению как к дисконтированным, так и недисконтированным целям» [2].
  • Копнув немного глубже, можно заметить, что аналогичные проблемы ранее поднимались также в [3] и [4] (обе статьи, в которых Томас фигурирует как один из авторов).

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

Как мы можем это решить?

Есть исправление.

Он грязный, но простой и понятный.

Существует эквивалентность между использованием коэффициента скидки и достижением конечного состояния в процессе марковского принятия решений (см. также Путерман [10], раздел 5.3, где он обсуждал аналогию между использованием коэффициента скидки и наличием конечное состояние).

Дисконтирование эквивалентно введению конечного состояния в Марковский процесс принятия решений. Это также эквивалентно длине горизонта, которая распределена геометрически.

Следовательно, нам просто нужно искусственно ввести возможность завершения траектории с некоторой вероятностью 1-γ.

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

… Может быть, нам следует отказаться от коэффициента дисконтирования?

В качестве альтернативы можно просто отказаться от фактора скидки. Фактор скидки просто не имеет смысла при продолжении настройки, как уже обсуждалось в [6] Саттоном и Барто.

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

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

Аналогичным образом, также в [5], авторы обсуждают, что дисконтированное обучение с подкреплением не является проблемой оптимизации при использовании аппроксимации функций, и что мы должны прибегать к обучению с подкреплением со средним вознаграждением. Однако обратите внимание, что проблемы авторы обсуждают в [5], отличаются от проблемы, которую я выделил в этой статье

Выводы

Цель этой статьи - повысить осведомленность о правильном использовании дисконтированной версии теоремы о градиенте политики. В подавляющем большинстве работ этот градиент используется неправильно и приводятся результаты с небольшим теоретическим обоснованием.

Эмпирические достижения в области глубокого обучения с подкреплением не соответствуют нашему теоретическому пониманию этой области.

Авторы книги «Более пристальный взгляд на глубинные градиенты политики» [11] изучили этот вопрос и обнаружили, что оценки градиента плохо коррелируют с «истинным» градиентом. Более того, они заметили, что ландшафт оптимизации часто не отражает ландшафт вознаграждения лежащего в основе MDP.

Вкратце они утверждают, что

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

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

Мы должны больше думать об этих проблемах и не повторять ту же ошибку, что и Икар.

Спасибо за чтение!

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

  1. Саттон, Ричард С. и др. «Методы градиента политики для обучения с подкреплением с аппроксимацией функций». НПИ. Vol. 99. 1999.
  2. Крис Нота и Филип С. Томас. 2020. Является ли градиент политики градиентом ?. AAMAS (2020).
  3. Томас, Филипп. «Предвзятость в естественных алгоритмах актёр-критик». Международная конференция по машинному обучению. ПМЛР, 2014.
  4. Томас, Филип С. и др. «Классический политический градиент: сохранение принципа оптимальности Беллмана». Препринт arXiv arXiv: 1906.03063 (2019).
  5. Наик, Абхишек и др. «Обучение со скидкой с подкреплением не является проблемой оптимизации». Препринт arXiv arXiv: 1910.02140 (2019).
  6. Саттон, Ричард С. и Эндрю Дж. Барто. Обучение с подкреплением: введение. MIT press, 2018.
  7. Мних, Владимир и др. «Асинхронные методы для глубокого обучения с подкреплением». Международная конференция по машинному обучению. ПМЛР, 2016.
  8. Хаарноя, Туомас и др. «Алгоритмы и приложения мягкого актера-критика». Препринт arXiv arXiv: 1812.05905 (2018).
  9. Ву, Юхуай и др. «Масштабируемый метод доверительной области для глубокого обучения с подкреплением с использованием приближения с поправкой на коэффициент Кронекера». Препринт arXiv arXiv: 1708.05144 (2017).
  10. Путерман, Мартин Л. Марковские процессы принятия решений: дискретное стохастическое динамическое программирование. Джон Вили и сыновья, 2014.
  11. Ильяс, Эндрю и др. «Более пристальный взгляд на глубокие градиенты политики». Международная конференция по обучающим представлениям (ICLR). 2020.