Алгоритм такси Uber научился проходить игры на Atari лучше людей

Инженеры из лаборатории искусственного интеллекта Uber AI Labs разработали семейство алгоритмов Go-Explore, основанных на обучении с подкреплением, которые превосходят по эффективности большинство существующих алгоритмов в тестах на играх Atari 1980-х годов. Go-Explore прошел 11 считающихся наиболее сложными для обучения с подкреплением игр, включая Montezuma’s Revenge и Pitfall, обойдя по набранным в них очкам большинство других алгоритмов и средний человеческий результат. Основной особенностью Go-Explore стала способность запоминать предшествующие перспективные состояния и возвращаться в них, осуществляя оттуда дальнейшую разведку, что позволяет повысить эффективность алгоритма обучения с подкреплением. Разработчики продемонстрировали возможное практическое применение Go-Explore для робототехники в задаче управления манипулятором робота. Кроме того в будущем алгоритм может быть полезен в решении множества других задач от обработки естественных языков до создания новых лекарств, говорится в работе, опубликованной в журнале Nature.

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

Алгоритмы, основанные на этом подходе, показывают значительные успехи в последнее время. Так, например самообучающиеся программы семейства AlphaGo и AlphaGo Zero от компании DeepMind способны обыгрывать лучших игроков в настольных играх го, сёги и шахматах, а алгоритм от OpenAI побеждает профессиональных игроков в Dota 2.

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

Разработчики из лаборатории искусственного интеллекта компании Uber под руководством Джеффа Клюна (Jeff Clune) создали семейство алгоритмов обучения с подкреплением под названием Go-Explore, которые менее подвержены проблемам редкого вознаграждения и неправильных локальных минимумов, благодаря способности запоминать предыдущие перспективные состояния и возвращаться к ним. Как считают разработчики, это позволяет алгоритму более эффективно исследовать пространство состояний и решает две ключевые проблемы обучения с подкреплением. Первая заключается в потере алгоритмом способности возвращаться к более ранним уже пройденным состояниям, даже несмотря на их высокую «перспективность», то есть большой вероятности привести к новым, недоступным ранее областям в процессе исследования. Алгоритм, обследуя одну область может внезапно переключиться на исследование другой и забыть дорогу назад. Вторая проблема связана с тем, что сам процесс исследования может препятствовать возвращению к более ранним состояниям алгоритма, уводя его далеко от стартовой точки через множество случайных действий.

В качестве среды для тестирования возможностей своего алгоритма инженеры Uber использовали популярный бенчмарк, состоящий из классических игр Atari, отобрав из них наиболее сложные и ранее плохо поддававшиеся алгоритмам машинного обучения, например, ставшие уже эталоном Montezuma’s Revenge и Pitfall. Обе эти игры отличаются особой сложностью для алгоритмов обучения с подкреплением из-за очень разреженного вознаграждения. То есть между моментами получения агентом вознаграждения, подкрепляющего правильность его действий, алгоритм может совершить сотни действий, в результате чего будет трудно понять, какие же действия привели к успеху или неудаче.

Чтобы обойти эту проблему, Go-Explore запоминает состояния, которые он посещает в среде, чтобы вернуться к ним позднее. Процесс построения «архива» состояний происходит итеративно. Так как состояний слишком много, чтобы хранить каждое из них отдельно в явном виде, алгоритм группирует похожие состояния в ячейки. Вначале цикла Go-Explore выбирает из сохраненных ячеек, на основании присвоенных им весам и отдавая предпочтение недавно найденным ту, в которую он вернется, а затем возвращается в это состояние (шаг go to state) и исследует из него прилегающие области, совершая случайные действия. После чего архив обновляется, сохраняя информацию о количествах посещений ячеек, полученном в них вознаграждении и траектории. Таким образом, запоминая состояния и возвращаясь к ним, Go-Explore не пропускает наиболее интересные состояния, не допускает перезиученности областей вблизи стартовой точки и не застревает вблизи ложных минимумов как в приведенном выше примере с роботом, попавшим в тупик.

Далее, если необходимо, после фазы исследования Go-Explore может выполнить робастификацию найденных решений, чтобы повысить устойчивость к возможным шумам для найденных в фазе исследования траекторий. Дело в том, что в отличие от реального мира игровое окружение в эмуляторе Atari достаточно детерминировано, то есть одни и те же действия приводят к одним и тем же результатам, а возврат к предыдущему состоянию для простоты производится восстановлением ранее сохраненного состояния эмулятора. Однако в случае внесения случайностей в окружение мы должны быть уверены, что после возврата в одно из прежних состояний сможем воспользоваться ранее найденным путем и что он приведет нас в заданную область. Для повышения робастности разработчики используют алгоритм обратного хода, запуская его итерационно и последовательно перемещая агент от конца траектории к ее началу. Также, для уменьшения детерминированности в работу алгоритма вводились случайные задержки, имитирующие человеческий стиль игры.

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

Несмотря на то, что Go-Explore показывает хорошие результаты даже когда агент ничего не знает об окружении, разработчики добавили в информацию о состоянии знания об окружении, получаемые из исходных кадров с эмулятора Atari, поступающих на вход алгоритма, такие, например, как текущие координаты агента на кадре, текущую комнату, уровень и имеющиеся предметы у персонажа (ключи в Montezuma’s Revenge). Ожидаемо применение такого усовершенствованного представления приводит к существенному росту количества набранных в игре очков.

Результаты тестирования на 11 наиболее сложных играх из бенчмарка Atari показывают, что Go-Explore обходит по набранным игровым баллам большинство существующих алгоритмов с заметным отрывом, в том числе и MuZero от DeepMind, о котором мы писали ранее. В игре Montezuma’s Revenge Go-Explore смог набрать более 1.73 миллионов очков, тогда как рекорд, поставленный человеком, составляет около 1.22 миллионов. Так же авторы отмечают, что их алгоритм смог превзойти средний уровень очков, набираемый человеком в игре Pitfall, хотя до последнего времени это не удавалось ни одному из существующих алгоритмов. Схожую с Go-Explore эффективность показал только недавно появившийся алгоритм от DeepMind под названием Agent57. Как и Go-Explore он смог превзойти средний человеческий уровень и даже обойти алгоритм от разработчиков из Uber в четырех играх из одиннадцати по очкам. Однако, как утверждают авторы, сравнивать результаты Go-Explore и Agent57 не совсем корректно, так как результаты последнего были получены в более простых и детерминированных условиях. Например, в отличие от Go-Explore в Agent57 не производилась имитация «человеческой» задержки при игре.

Поделиться

Кроме тестирования Go-Explore на играх Atari, инженеры смогли успешно применить тот же подход в работе манипулятора робота. Алгоритм успешно справился с управлением роборукой в симуляторе, перемещая виртуальные предметы на полки, даже если они первоначально находились за дверцами с замками.