Разработка методов обучения с подкреплением, позволяющих найти эффективную политику с использованием как можно меньшего количества образцов, является ключевой целью как эмпирических, так и теоретических исследований. С теоретической точки зрения, есть два основных способа, границы сожаления или PAC (возможно, приблизительно правильные), чтобы измерить и гарантировать выборочную эффективность метода. В идеале мы хотели бы иметь алгоритмы с хорошей производительностью по обоим критериям, поскольку они измеряют различные аспекты эффективности выборки, и мы показали ранее [1], что нельзя просто перейти от одного к другому. В специфических условиях, называемых табличными эпизодическими MDP, недавний алгоритм достиг близких к оптимальным границам сожаления [2], но не было известных методов, которые были бы близки к оптимальным согласно критерию PAC, несмотря на долгую линию исследований. В нашей работе, представленной на ICML 2019, мы закрываем этот пробел с помощью нового метода, который достигает минимаксно-оптимальных границ PAC (и сожалений), которые совпадают со статистическими нижними границами наихудшего случая в доминирующих условиях.

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

Помимо эффективности выборки, наш алгоритм также не страдает отсутствием подотчетности, поскольку он выводит то, что мы называем сертификатами политики. Сертификаты политики - это доверительные интервалы вокруг текущего ожидаемого дохода алгоритма и оптимального дохода, который алгоритм дает нам перед каждым эпизодом (см. Рисунок 1). Эта информация позволяет пользователям наших алгоритмов вмешиваться, если сертифицированная производительность считается недостаточной. Мы сопровождаем этот алгоритм новым типом гарантии обучения, называемым IPOC, который сильнее, чем PAC, сожалею и недавний Uniform-PAC [1], поскольку он обеспечивает не только эффективность выборки, но и надежность сертификатов политик. В первую очередь мы рассматриваем простую табличную эпизодическую обстановку, в которой есть лишь небольшое количество возможных состояний и действий. Хотя в практических приложениях это часто не так, мы считаем, что идеи, полученные в этой работе, потенциально могут быть использованы для разработки более эффективных по выборке и подотчетных методов обучения с подкреплением для решения реальных проблем с помощью разнообразных наблюдений, таких как изображения или текст.

Более эффективный и подотчетный RL с помощью сертификатов политики и ограничений IPOC

Мы предлагаем сделать методы эпизодического обучения с подкреплением более подотчетными, заставив их выдавать сертификат политики перед каждым эпизодом. Сертификат политики - это доверительный интервал [l, u]. Этот интервал содержит как ожидаемую сумму вознаграждений в соответствии с политикой алгоритма в следующем эпизоде, так и оптимальную ожидаемую сумму вознаграждений в следующем эпизоде ​​(см. Рисунок 1 для иллюстрации). Таким образом, сертификат политики помогает ответить на два вопроса, которые представляют интерес для многих приложений:

  • Какую отдачу ожидает алгоритм алгоритма в следующем эпизоде? - по крайней мере, в нижней части интервала l.
  • Насколько далека от оптимальной политика алгоритма в следующем эпизоде?
    - Максимальная длина интервала u-l

Сертификаты политики полезны только в том случае, если эти доверительные интервалы не слишком растянуты. Чтобы гарантировать это, мы вводим тип гарантии для алгоритмов с сертификатами политики границами IPOC (индивидуальные сертификаты POlicy). Эти границы гарантируют, что все сертификаты имеют действительные доверительные интервалы и ограничивают количество раз, когда их длина может превышать любой заданный порог. Границы IPOC гарантируют как выборочную эффективность изучения политики, так и точность сертификатов политики. Это означает, что алгоритм должен использовать все более качественные политики, но также должен более точно сообщать нам, насколько хороши эти политики. Границы IPOC более строгие, чем существующие границы обучения, такие как PAC или сожаление (см. Рисунок 3), и подразумевают, что алгоритм можно прервать в любое время (подробности см. В документе).

Симбиоз оптимизма и сертификаты: Minimax-Optimal PAC RL в табличных MDP

Сертификаты политик не ограничиваются конкретными типами алгоритмов, но оптимистические алгоритмы особенно естественно распространять на выходные сертификаты политик. Эти методы дают нам верхний предел сертификатов «бесплатно», поскольку они поддерживают верхний доверительный интервал U (s, a) для функции оптимального значения Q * (s, a) и следуют жадной политике π относительно этой верхней доверительной границы. Аналогичным образом мы можем вычислить нижнюю доверительную границу L (s, a) Q-функции Q (s, a) этой жадной политики. Сертификат для этой политики - это как раз эти доверительные границы, оцененные в начальном состоянии s₁ эпизода [l, u] = [L (s₁, π (s₁)) , U (s₁, π (s₁)]

Мы демонстрируем этот принцип с помощью нового алгоритма ORLC (оптимистический RL с сертификатами) для табличных MDP. Подобно существующим оптимистическим алгоритмам, таким как UCBVI [2] и UBEV [1], он вычисляет доверительные границы U (s, a) путем итерации оптимистического значения на оценочной модели, но также вычисляет более низкие значения. доверительные границы L (s, a) с пессимистической версией итерации значений. Эти процедуры аналогичны стандартным итерациям значений, но добавляют бонусы оптимизма или вычитают бонусы пессимизма на каждом временном шаге, соответственно, для обеспечения высоких доверительных границ.

Интересно, что мы обнаружили, что вычисление нижних доверительных границ для сертификатов политик также может улучшить выборочную эффективность изучения политик. Более конкретно, мы могли бы ужесточить бонусы оптимизма в нашем табличном методе ORLC, используя нижние границы L (s, a). Это делает алгоритм менее консервативным и позволяет быстрее адаптироваться к наблюдаемым данным. В результате мы смогли доказать первые границы PAC для табличных MDP, которые являются минимаксно-оптимальными в доминирующем члене:

Теорема: минимальная ошибка IPOC, PAC и граница сожаления ORLC

В любом эпизодическом MDP с S состояниями, действиями A и длиной эпизода H алгоритм ORLC удовлетворяет приведенному ниже пределу ошибки IPOC. То есть с вероятностью не менее 1-δ все сертификаты являются действительными доверительными интервалами, и для всех ε ›0 ORLC выводит сертификаты, превышающие ε не более чем в

эпизоды. Это сразу означает, что указанная выше граница является (Единообразной) границей PAC и что ORLC удовлетворяет пределу сожаления с высокой вероятностью для всего количества эпизодов T из

Сравнивая порядок наших границ PAC со статистическими нижними границами и предшествующим уровнем техники PAC и границами сожаления в таблице ниже, это первый раз, когда была достигнута оптимальная полиномиальная зависимость SAH² в доминирующем 1 / ε ² срок. Наши границы также улучшают предыдущие границы сожаления для UCBVI, избегая их членов √ (H³T), делая наши границы минимаксно-оптимальными, даже когда длина эпизода H велика.

Как упоминалось выше, наш алгоритм обеспечивает эту новую гарантию IPOC и улучшенные границы PAC за счет поддержания нижней доверительной границы L (s, a) Q-функции Q (s, a) своей текущей политики в любое время в дополнение к обычной верхней доверительной границе U (s, a) для функции оптимального значения Q * (s, a). Получение точных нижних доверительных границ L (s, a) требует новых методов по сравнению с методами для верхних доверительных границ. Все недавние оптимистические алгоритмы для табличных MDP используют для своих верхних доверительных границ, что U является доверительной границей для Q *, которая не зависит от выборок. Оптимальная Q-функция всегда одна и та же, независимо от того, какие образцы видел алгоритм. Мы не можем использовать то же понимание для наших нижних доверительных границ, потому что Q-функция текущей политики Q действительно зависит от выборок, которые видел алгоритм. В конце концов, политика π вычисляется как функция этих выборок. Мы разрабатываем методику, которая позволяет нам справиться с этой проблемой, явно включая верхнюю и нижнюю доверительные границы в условия бонуса. Оказывается, этот метод не только помогает достичь более жестких нижних доверительных границ, но и более жестких верхних доверительных границ. Это ключ к нашему улучшенному PAC и пределам сожаления.

Наша работа предоставила последний ингредиент для границ PAC для эпизодических табличных MDP, которые оптимальны от минимального до более низкого порядка, а также заложила основу для сертификатов политик. В полной статье мы также рассмотрели более общие MDP и разработали алгоритм сертификата политики для так называемых конечных MDP с линейной дополнительной информацией. Это обобщение популярной линейной контекстной настройки бандита и требует аппроксимации функций. В будущем мы планируем исследовать сертификаты политик как полезный эмпирический инструмент для методов глубокого обучения с подкреплением и изучить, может ли конкретная форма бонусов оптимизма, полученных в этой работе, вдохновить на более эффективные с точки зрения выборки бонусы исследования в методах глубокого RL.

Этот пост также размещен в блоге ML @ CMU и основан на работе, приведенной в следующей статье:

Кристоф Данн, Лихонг Ли, Вэй Вэй, Эмма Брунскилл
Сертификаты политики: на пути к подотчетному обучению с подкреплением
Международная конференция по машинному обучению (ICML) 2019

Другие работы, упомянутые в этом посте:

[1] Данн, Латтимор, Бранскилл - Объединение PAC и сожаления: единые границы PAC для эпизодического обучения с подкреплением (NeurIPS 2017)

[2] Азар, Осбанд, Мунос - Границы минимального сожаления для обучения с подкреплением (ICML 2017)

[3] Данн, Брунскилл - Пример сложности эпизодического обучения с подкреплением с фиксированным горизонтом (NeurIPS 2015)