Обучение в Montezuma’s Revenge по одной демонстрации04.07.2018 07:00

Мы обучили агента набрать высокий результат в 74 500 очков в игре Montezuma«s Revenge⁠ на основе всего одной демонстрации действий человека — это превосходит любые ранее опубликованные результаты. Наш алгоритм прост: агент разыгрывает последовательности игр, начиная с тщательно отобранных состояний из демонстрации, и обучается на них, оптимизируя игровой счет с помощью PPO⁠ — того же алгоритма обучения с подкреплением, который лежит в основе OpenAI Five⁠.

Исследование и обучение

Чтобы добиться успеха в задаче обучения с подкреплением, ИИ должен решить две задачи:

• Найти последовательность действий, ведущую к положительной награде. Это проблема исследования (exploration).
• Запомнить последовательность необходимых действий и обобщить их на похожие, но слегка отличающиеся ситуации. Это проблема обучения (learning).

Проблему исследования в Montezuma«s Revenge можно во многом обойти, если начинать каждый эпизод обучения с подкреплением со сброса в состояние из демонстрации. Начиная с демонстрационных состояний, агенту требуется выполнять гораздо меньше исследований для освоения игры по сравнению со случаем, когда каждый эпизод начинается с самого начала игры. Это позволяет нам развязать исследование и обучение. Наши результаты показывают, что именно исследование является более сложной из двух задач для таких игр, как Montezuma«s Revenge, и некоторых похожих игр для Atari вроде PrivateEye.

Почему исследование — это сложно

Методы обучения с подкреплением без модели (model-free RL), такие как градиенты политики (policy gradients) и Q-обучение, исследуют среду путем случайного выполнения действий. Если случайные действия случайно приводят к награде, они подкрепляются, и в будущем агент с большей вероятностью будет повторять эти полезные действия. Это хорошо работает, если награды достаточно плотные, чтобы случайные действия приводили к ним с разумной вероятностью. Однако многие более сложные игры требуют длинных последовательностей очень специфических действий для получения хоть какой-то награды, и появление таких последовательностей случайным образом крайне маловероятно.

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

Например, в случае Montezuma«s Revenge вероятность получить первый ключ можно разложить так:

p (получить ключ) = p (спуститься по лестнице 1) * p (спуститься по канату) * p (спуститься по лестнице 2) * p (перепрыгнуть через череп) * p (подняться по лестнице 3).

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

Упрощение исследования с помощью демонстраций

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

Наш подход заключается в том, чтобы каждый эпизод обучения с подкреплением начинался с состояния из ранее записанной демонстрации. В начале обучения агент начинает каждый эпизод ближе к концу демонстрации. Как только агент начинает побеждать или хотя бы сравниваться по счету с демонстратором на оставшейся части игры как минимум в 20% прогонов, мы постепенно сдвигаем точку старта назад во времени. Мы продолжаем это делать до тех пор, пока агент не начнет играть с самого начала игры, вообще без использования демо — в этот момент мы получаем обученного с помощью RL агента, который побеждает или играет на равных с экспертом-человеком на протяжении всей игры.

Постепенно перемещая начальное состояние от конца демонстрации к началу, мы гарантируем, что на каждом этапе агент сталкивается с простой задачей исследования, в которой он с высокой вероятностью преуспеет, поскольку он уже научился проходить большую часть оставшейся игры. Решение проблемы RL таким образом можно интерпретировать как форму динамического программирования⁠. Если для получения награды требуется определенная последовательность из N действий, теперь эту последовательность можно выучить за время, линейно зависящее от N, а не экспоненциально.

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

Сравнение с подходами на основе имитации

Недавно компания DeepMind продемонстрировала агента, который учится играть в Montezuma«s Revenge посредством имитационного обучения по демонстрации;  один подход⁠ обучает агента достигать тех же состояний, что видны на видео прохождения Montezuma«s Revenge на YouTube, а другая методика⁠ сочетает усовершенствованную версию Q-обучения с максимизацией правдоподобия действий, совершенных в демонстрации. Преимущество этих подходов заключается в том, что они не требуют такого контроля над средой, как наш метод: они не сбрасывают среду в состояния, отличные от стартового состояния игры, и не предполагают доступ к полным состояниям игры, встречающимся в демонстрации. Наш метод отличается тем, что он напрямую оптимизирует то, что нас волнует — игровой счет, а не заставляет агента имитировать демонстрацию; таким образом, наш метод не будет переобучаться (overfit) на потенциально субоптимальную демонстрацию и может дать преимущества в многопользовательских играх, где мы хотим оптимизировать производительность против других противников, а не только против того, что был в демонстрации.

Оставшиеся проблемы

Хотя пошаговое обучение нашего агента гораздо проще, чем обучение игре с нуля, оно все еще далеко от тривиальности. Одна из проблем, с которыми сталкивается наш RL-агент, заключается в том, что он, как правило, не может достичь точного состояния из более поздних этапов демо, когда начинает с более раннего состояния. Это происходит потому, что агент играет в игру с другим пропуском кадров (frameskip), чем тот, который мы использовали для записи демонстрации, а также из-за случайности действий, из-за чего крайне маловероятно точное воспроизведение любой конкретной последовательности действий. Следовательно, агент должен уметь обобщать состояния, которые очень похожи, но не идентичны. Мы обнаружили, что это отлично работает для Montezuma«s Revenge, но гораздо хуже для некоторых других опробованных нами игр Atari, таких как Gravitar и Pitfall. Одной из причин этого может быть то, что в этих последних играх требуется решать более сложную задачу компьютерного зрения: нам самим было трудно играть в эти игры по уменьшенному экрану, и мы заметили некоторое улучшение при использовании более крупных и глубоких политик нейронных сетей.

Другая проблема, с которой мы столкнулись, заключается в том, что стандартные алгоритмы обучения с подкреплением вроде градиентов политики требуют поддержания точного баланса между исследованием (exploration) и использованием (exploitation): если действия агента слишком случайны, он совершает слишком много ошибок, чтобы когда-либо достичь требуемого финального счета при старте с начала игры; если действия слишком детерминированы, агент перестает учиться, поскольку не исследует альтернативные варианты. Достижение заявленного результата в Montezuma«s Revenge потребовало тщательной настройки коэффициента энтропийного бонуса, используемого в PPO, в сочетании с другими гиперпараметрами, такими как скорость обучения (learning rate) и масштабирование наград. Для некоторых других игр, таких как Gravitar и Pitfall, мы не смогли найти гиперпараметры, которые подошли бы для обучения всей учебной программы. Алгоритм также по-прежнему демонстрирует существенные случайные вариации от запуска к запуску: некоторые прогоны не могут сойтись для Montezuma«s Revenge. Мы надеемся, что будущие успехи в области RL приведут к появлению алгоритмов, более устойчивых к случайному шуму и выбору гиперпараметров.

Наконец, как это часто бывает в обучении с подкреплением, мы обнаруживаем, что наша обученная политика на базе нейросети пока не обобщает знания на уровне игрока-человека. Один из методов⁠ проверки способности к генерализации заключается в том, чтобы сделать политику «липкой» (sticky), заставляя ее повторять последнее действие с вероятностью 0,25 на каждом кадре. Используя этот метод оценки, наша обученная политика набирает в среднем 10 000 очков в Montezuma«s Revenge. В качестве альтернативы мы можем выполнять случайные действия с вероятностью 0,01 (повторяя их в течение 4 пропущенных кадров), что приводит к среднему счету 8 400 для нашей политики. По нашим наблюдениям, такие возмущения также значительно снижают счет игроков-человека в Montezuma«s Revenge, но в меньшей степени. Насколько нам известно, наши результаты с использованием возмущенных политик все равно лучше всех ранее опубликованных. Внесение возмущений в обученную политику путем добавления от 0 до 30 случайных пустых действий (no-ops) в начале не привело к значительному ухудшению результатов: в большинстве прогонов был достигнут финальный счет нашей демонстрации.

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