Эволюционные стратегии как масштабируемая альтернатива усилению обучения

Опубликовано 13 February 2020

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


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


VIEW ON GITHUBVIEW ON ARXIV


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


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


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


Усиление обучения

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


Эволюционные стратегии как масштабируемая альтернатива усилению обучения

Вверху: в игре Pong политика может брать пиксели экрана и вычислять вероятность перемещения весла игрока (зеленым, справа) вверх, вниз или ни того, ни другого.


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


Эволюционные стратегии как масштабируемая альтернатива усилению обучения

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


Разведка путем введения шума в действия. Политики, которые мы обычно используем в RL, являются стохастическими, так как они только вычисляют вероятность принятия каких-либо действий. Таким образом, в ходе обучения агент может оказаться в определенном состоянии много раз, и в разное время он будет выполнять различные действия из-за выборки. Это обеспечивает сигнал, необходимый для обучения; некоторые из этих действий приведут к хорошим результатам и будут поощряться, а некоторые из них не сработают и будут обескуражены. Поэтому мы говорим, что вводим исследование в процесс обучения, вводя шум в действия агента, что мы делаем путем выборки из распределения действий на каждом временном шаге. Это будет в отличие от 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, в настройках только два параметра и функция вознаграждения (красный = высокий, синий = низкий). На каждой итерации мы показываем текущее значение параметра (белым цветом), совокупность дрожащих образцов (черным цветом) и предполагаемый градиент (белая стрелка). Мы продолжаем двигать параметры к вершине стрелки, пока не сойдемся к локальному оптимуму. Вы можете воспроизвести эту фигуру с этой записной книжкой.


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

# simple example: minimize a quadratic around some solution point
import numpy as np
solution = np.array([0.5, 0.1, -0.3])
def f(w): return -np.sum((w - solution)**2) npop = 50 # population size
sigma = 0.1 # noise standard deviation
alpha = 0.001 # learning rate
w = np.random.randn(3) # initial guess
for i in range(300):
N = np.random.randn(npop, 3)
R = np.zeros(npop)
for j in range(npop):
w_try = w + sigma*N[j]
R[j] = f(w_try)
A = (R - np.mean(R)) / np.std(R)
w = w + alpha/(npop*sigma) * np.dot(N.T, A)

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


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

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

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

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


ES конкурирует с RL

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

Эволюционные стратегии как масштабируемая альтернатива усилению обучения


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


Эволюционные стратегии как масштабируемая альтернатива усилению обучения


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


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


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


Эволюционные стратегии как масштабируемая альтернатива усилению обучения


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


Эволюционные стратегии как масштабируемая альтернатива усилению обучения


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


Связанных с работой

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


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


Вывод


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


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


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