Эволюционные стратегии как масштабируемая альтернатива обучению с подкреплением24.03.2017 07:00

Мы обнаружили, что стратегии эволюции (ES) — метод оптимизации, известный уже несколько десятилетий, — не уступают по производительности стандартным методам обучения с подкреплением (RL) на современных бенчмарках RL (например, Atari/MuJoCo), одновременно преодолевая многие недостатки RL.

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

Наше открытие продолжает современную тенденцию достижения сильных результатов с помощью идей полувековой давности. Например, в 2012 году в статье об «AlexNet»⁠ было показано, как проектировать, масштабировать и обучать сверточные нейронные сети (CNN) для достижения чрезвычайно высоких результатов в задачах распознавания изображений в то время, когда большинство исследователей считали CNN бесперспективным подходом для компьютерного зрения. Аналогичным образом, в 2013 году в статье по Deep Q-Learning⁠ было показано, как объединить Q-обучение с CNN для успешного прохождения игр Atari, что вдохнуло новую жизнь в обучение с подкреплением как в исследовательскую область с захватывающими экспериментальными (а не теоретическими) результатами. Точно так же наша работа демонстрирует, что ES достигают высокой производительности на бенчмарках RL, развеивая распространенное мнение о том, что методы ES невозможно применять к многомерным проблемам.

Методы ES просты в реализации и масштабировании. Работая на вычислительном кластере из 80 машин и 1440 ядер ЦП, наша реализация способна обучить трехмерного гуманоидного ходока MuJoCo всего за 10 минут (тогда как A3C на 32 ядрах тратит на это около 10 часов). Используя 720 ядер, мы также можем получить производительность, сравнимую с A3C на Atari, сократив при этом время обучения с 1 дня до 1 часа.

Далее мы сначала кратко опишем традиционный подход RL, противопоставим ему наш подход ES, обсудим компромиссы между ES и RL и, наконец, выделим некоторые из наших экспериментов.

Обучение с подкреплением

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

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

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

Исследование путем внесения шума в действия. Политики, которые мы обычно используем в RL, являются стохастическими, в том смысле, что они вычисляют лишь вероятности совершения тех или иных действий. Таким образом, в процессе обучения агент может многократно оказываться в определенном состоянии, и в разное время он будет предпринимать разные действия из-за выборки. Это обеспечивает сигнал, необходимый для обучения: некоторые из этих действий приведут к хорошим результатам и получат поощрение, а другие не сработают и будут отвергнуты. Следовательно, мы говорим, что вводим исследование в процесс обучения путем добавления шума в действия агента, что достигается за счет выборки из распределения действий на каждом временном шаге. Это контрастирует с подходом ES, который мы опишем далее.

Стратегии эволюции

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

Оптимизация методом «черного ящика». В ES мы полностью забываем о том, что существуют агент, среда, задействованные нейронные сети или что взаимодействия происходят во времени и т. д. Вся схема сводится к тому, что на вход поступают 1 000 000 чисел (которые описывают параметры сети политики), на выходе получается 1 число (общее вознаграждение), и мы хотим найти наилучшую конфигурацию этих 1 000 000 чисел. Математически мы оптимизируем функцию f (w) относительно входного вектора w (параметров/весов сети), не делая никаких предположений о структуре f, кроме возможности ее вычисления (отсюда и «черный ящик»).

Алгоритм ES. Интуитивно оптимизация представляет собой процесс «угадывания и проверки», когда мы начинаем со случайных параметров, а затем многократно: 1) немного случайно изменяем наше предположение и 2) слегка сдвигаем его в сторону тех изменений, которые сработали лучше. Конкретно, на каждом шаге мы берем вектор параметров w и генерируем популцию, скажем, из 100 слегка отличающихся векторов параметров w1 … w100 путем внесения гауссовского шума в w. Затем мы независимо оцениваем каждого из 100 кандидатов, запуская соответствующую сетевую политику в среде на некоторое время, и суммируем все полученные награды. Обновленный вектор параметров затем становится взвешенной суммой этих 100 векторов, где каждый вес пропорционален общему вознаграждению (то есть мы хотим, чтобы у более успешных кандидатов был больший вес). Математически вы заметите, что это также эквивалентно оценке градиента ожидаемого вознаграждения в пространстве параметров с помощью конечных разностей, за исключением того, что мы делаем это только вдоль 100 случайных направлений. Еще один взгляд на этот метод заключается в том, что мы все еще занимаемся RL (а именно, градиентом политики или REINFORCE⁠), где действиями агента является генерация целых векторов параметров с использованием гауссовской политики.

Пример кода. Чтобы сделать основной алгоритм наглядным и подчеркнуть его простоту, приведем короткий пример оптимизации квадратичной функции с помощью ES (либо вы можете посмотреть более длинную версию⁠ с большим количеством комментариев):

Простой пример: минимизация квадратичной функции вокруг некоторой точки решения

Внесение шума в параметры. Обратите внимание, что целевая функция идентична той, которую оптимизирует RL: ожидаемое вознаграждение. Тем не менее, RL добавляет шум в пространство действий и использует обратное распространение ошибки для вычисления обновлений параметров, в то время как ES добавляет шум непосредственно в пространство параметров. Другими словами, RL — это «угадывание и проверка» действий, а ES — это «угадывание и проверка» параметров. Поскольку мы вносим шум в параметры, становится возможным использовать детерминированные политики (что мы и делаем в наших экспериментах). Также можно добавлять шум как в действия, так и в параметры, чтобы потенциально объединить оба подхода.

Компромиссы между ES и RL

ES обладает множеством преимуществ по сравнению с алгоритмами RL (некоторые из них носят технический характер):

• Отсутствие необходимости в обратном распространении ошибки. ES требует только прямой проход (forward pass) политики и не нуждается в обратном распространении ошибки (или оценке функции ценности), что делает код короче и на практике в 2–3 раза быстрее. В системах с ограниченной памятью также отпадает необходимость вести запись эпизодов для последующего обновления. Кроме того, не нужно беспокоиться о взрыве градиентов в рекуррентных нейронных сетях (RNN). Наконец, мы можем исследовать гораздо более широкий класс функций политик, включая недифференцируемые сети (например, бинарные сети) или сети, содержащие сложные модули (например, поиск пути или различные слои оптимизации).
• Высокая степень распараллеливания. ES требует от воркеров обмена лишь несколькими скалярами, в то время как в RL необходимо синхронизировать целые векторы параметров (которые могут содержать миллионы чисел). Интуитивно это объясняется тем, что мы контролируем случайные сиды (seed) на каждом воркере, поэтому каждый воркер может локально восстановить возмущения остальных воркеров. Таким образом, все, чем нужно обмениваться между воркерами — это награда для каждого возмущения. В результате в наших экспериментах мы наблюдали линейное ускорение при добавлении тысяч ядер ЦП к процессу оптимизации.
• Повышенная надежность. Ряд гиперпараметров, которые трудно настроить в реализациях RL, обходи стороной в ES. Например, RL не является «масштабно-независимым», поэтому можно получить совершенно разные результаты обучения (включая полный провал) при различных настройках гиперпараметра пропуска кадров (frame-skip) в Atari. Как мы показываем в нашей работе, ES работает примерно одинаково хорошо при любом значении пропуска кадров.
• Структурированное исследование. Некоторые алгоритмы RL (особенно градиенты политики) инициализируются со случайных политик, что часто проявляется в виде случайного подпрыгивания на месте в течение длительного времени. Этот эффект сглаживается в Q-обучении благодаря эпсилон-жадным политикам, где операция max может заставлять агентов выполнять какое-то однородное действие в течение некоторого времени (например, удерживать стрелку влево). Это с большей вероятностью приведет к какому-то результату в игре, чем если бы агент дрожал на месте, как в случае с градиентами политики. Подобно Q-обучению, ES не страдает от этих проблем, поскольку мы можем использовать детерминированные политики и достигать последовательного исследования.
• Назначение кредита на длинных временных интервалах. Изучая математические особенности как ES, так и оценщиков градиента RL, мы видим, что ES является привлекательным выбором, особенно когда количество временных шагов в эпизоде велико, когда действия имеют долгосрочные последствия или когда отсутствуют хорошие оценки функции ценности.

С другой стороны, мы также столкнулись с некоторыми трудностями при практическом применении ES. Одной из главных проблем является то, что для работы ES добавление шума в параметры должно приводить к различным исходам для получения некоторого градиентного сигнала. Как мы подробно описываем в нашей статье, использование виртуальной нормализации батчей (virtual batchnorm) помогает смягчить эту проблему, однако необходима дальнейшая работа по эффективной параметризации нейронных сетей с целью изменения их поведения в зависимости от шума. В качестве примера сопутствующей трудности мы обнаружили, что в игре Montezuma«s Revenge крайне маловероятно получить ключ на первом уровне с помощью случайной сети, в то время как со случайными действиями это иногда возможно.

ES конкурентоспособны по сравнению с RL

Мы сравнили производительность ES и RL на двух стандартных бенчмарках RL: задачах управления MuJoCo и прохождении игр Atari. Каждая задача MuJoCo (см. примеры ниже) содержит физически смоделированную шарнирную фигуру, где политика получает положения всех суставов и должна выдавать крутящие моменты, которые нужно приложить к каждому суставу для движения вперед. Ниже приведены примеры агентов, обученных в трех задачах управления MuJoCo, где целью является движение вперед:

Обычно мы сравниваем производительность алгоритмов, глядя на их эффективность обучения на данных: каково наше среднее вознаграждение в зависимости от количества увиденных состояний? Вот примеры полученных нами кривых обучения по сравнению с RL (в данном случае алгоритм TRPO⁠):

Сравнение эффективности данных. Приведенные выше сравнения показывают, что ES (оранжевый цвет) могут достигать производительности, сопоставимой с TRPO (синий цвет), хотя и не всегда полностью соответствуют или превосходят его во всех случаях. Более того, при взгляде по горизонтали видно, что ES менее эффективны, но не более чем примерно в 10 раз (обратите внимание, что ось X имеет логарифмический масштаб).

Сравнение реального времени выполнения. Вместо того чтобы смотреть на сырое количество увиденных состояний, можно утверждать, что важнейшей метрикой является реальное время (wall clock time): сколько времени (в секундах) требуется для решения конкретной задачи? Этот показатель в конечном итоге определяет достижимую скорость итераций для исследователя. Поскольку ES требует минимального обмена данными между воркерами, мы смогли решить одну из самых сложных задач MuJoCo (3D гуманоид), используя 1440 ядер ЦП на 80 машинах всего за 10 минут. Для сравнения, в типичных условиях 32 воркера A3C на одной машине решали бы эту задачу около 10 часов. Также возможно, что производительность RL могла бы улучшиться при больших алгоритмических и инженерных усилиях, однако мы обнаружили, что наивное масштабирование A3C в стандартной облачной среде ЦП является сложной задачей из-за высоких требований к пропускной способности связи.

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

В играх Atari метод ES, обученный на 720 ядрах за 1 час, достигает производительности, сопоставимой с A3C, обученным на 32 ядрах за 1 день. Ниже приведены некоторые результаты для Pong, Seaquest и Beamrider. На этих видео показаны предварительно обработанные кадры — именно то, что видит агент во время игры:

В частности, обратите внимание, что подводная лодка в Seaquest корректно учится всплывать, когда уровень кислорода падает до критической отметки.

Связанные работы

ES — это алгоритм из литературы по нейроэволюции, которая имеет долгую историю в области ИИ, и полный обзор литературы выходит за рамки данной статьи. Тем не менее, мы рекомендуем заинтересованным читателям ознакомиться с материалами в Википедии⁠,  Scholarpedia⁠, а также с обзорной статьей Юргена Шмидхубера (Раздел 6.6)⁠. Работа, которая легла в основу нашего подхода — это Natural Evolution Strategies⁠ (Вирстра и др., 2014). По сравнению с этой работой и большинством вдохновленных ею исследований, мы сосредоточились на масштабировании этих алгоритмов до крупномасштабных распределенных систем, поиск компонентов, которые заставляют алгоритмы лучше работать с глубокими нейронными сетями (например,  виртуальная батч-нормализация⁠), а также на их оценке на современных бенчмарках обучения с подкреплением.

Стоит также отметить, что подходы, связанные с нейроэволюцией, в последнее время вновь привлекли внимание в литературе по машинному обучению, например, в таких работах, как HyperNetworks⁠,  «Large-Scale Evolution of Image Classifiers»⁠ и «Convolution by Evolution»⁠.

Заключение

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

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

Релиз кода. Наконец, если вы хотите попробовать запустить ES самостоятельно, мы рекомендуем ознакомиться со всеми детаями, прочитав нашу научную работу⁠ или изучив наш код в репозитории на GitHub⁠.

Бен Барри