Rl

Привет, Хабр!

Как знают наши постоянные читатели, мы давно и успешно издаем книги по Unity. В рамках проработки темы нас заинтересовал, в частности, инструментарий ML-Agents Toolkit. Сегодня мы предлагаем вашему вниманию перевод статьи из блога Unity о том, как эффективно обучать игровых агентов методом игры с самим собой; в частности, статья помогает понять, чем этот метод эффективнее традиционного обучения с подкреплением.



Приятного чтения!


В этом после дается обзор технологии self-play (игра с самим собой) и демонстрируется, как с ее помощью обеспечивается стабильное и эффективное обучение в демонстрационной среде Soccer из инструментария ML-Agents Toolkit.

В демонстрационных средах Tennis и Soccer из инструментария Unity ML-Agents Toolkit агенты стравливаются друг с другом как соперники. Обучение агентов в рамках такого состязательного сценария порой весьма нетривиальная задача. На самом деле, в предыдущих релизах ML-Agents Toolkit для того, чтобы агент уверенно обучился, требовалась серьезная проработка награды. В версии 0.14 была добавлена возможность, позволяющая пользователю тренировать агентов методом обучения с подкреплением (RL) на основе self-play, механизма, имеющего принципиальное значение в достижении одних из наиболее высококлассных результатов обучения с подкреплением, например, OpenAI Five и DeepMinds AlphaStar. Self-play при работе стравливает друг с другом актуальную и прошлую ипостаси агента. Таким образом, мы получаем противника для нашего агента, который может постепенно совершенствоваться с использованием традиционных алгоритмов обучения с подкреплением. Полноценно обученный агент может успешно соперничать с продвинутыми игроками-людьми.

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

В этой статье мы рассмотрим некоторые технические тонкости, связанные с динамикой игры самим с собой, а также рассмотрим примеры работы в виртуальных окружениях Tennis и Soccer, отрефакторенных таким образом, чтобы проиллюстрировать игру с самим собой.

История игры с самим собой в играх

У феномена игры с самим собой долгая история, отразившаяся в практике разработки искусственных игровых агентов, призванных соперничать с человеком в играх. Одним из первых эту систему использовал Артур Сэмюэл, разработавший в 1950-е симулятор для игры в шахматы и опубликовавший эту работу в 1959 году. Эта система стала предтечей эпохального результата в обучении с подкреплением, достигнутого Джеральдом Тезауро в игре TD-Gammon; итоги опубликованы в 1995 году. В TD-Gammon использовался алгоритм работы по методу временных различий TD() с функцией игры самим с собой, чтобы обучить агент игре в нарды настолько, что он мог бы посоперничать с человеком-профессионалом. В некоторых случаях наблюдалось, что TD-Gammon обладает более уверенным видением позиций, чем игроки международного класса.

Игра с самим собой нашла отражение во многих знаковых достижениях, связанных с RL. Важно отметить, что игра с самим собой помогла развитию агентов для игры в шахматы и го, обладающих сверхчеловеческими способностями, элитных агентов DOTA 2, а также сложных стратегий и контрстратегий в таких играх, как реслинг и прятки. В результатах, достигнутых при помощи игры с самим собой, часто отмечается, что игровые агенты избирают стратегии, удивляющие экспертов-людей.

Игра с самим собой наделяет агентов определенной креативностью, не зависящей от творчества программистов. Агент получает лишь правила игры, а затем информацию о том, выиграл он или проиграл. Далее, опираясь на эти базовые принципы, агент должен сам выработать грамотное поведение. По словам создателя TD-Gammon, такой подход к обучению освобождает, в том смысле, что программа не стеснена человеческими склонностями и предрассудками, которые могут оказаться ошибочными и ненадежными. Благодаря такой свободе, агенты открывают блестящие игровые стратегии, совершенно изменившие представления специалистов-инженеров о некоторых играх.

Обучение с подкреплением в состязательных играх

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



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

В случае с состязательными играми агент тягается не только с динамикой окружающей среды, но и с другим (возможно, интеллектуальным) агентом. Можно считать, что соперник встроен в окружающую среду, и его действия непосредственно влияют на следующее состояние, которое увидит агент, а также на награду, которую он получит.



Пример со средой Теннис из инструментария ML-Agents

Рассмотрим демо-пример ML-Agents Tennis. Голубая ракетка (слева) это обучающийся агент, а фиолетовая (справа) его соперник. Чтобы перекинуть мяч через сетку, агент должен учитывать траекторию мяча, летящего от соперника, и делать поправку угла и скорости летящего мяча с учетом условий среды (гравитации). Однако, в состязании с соперником перебросить мяч через сетку это лишь полдела. Сильный соперник может ответить неотразимым ударом, и в результате агент проиграет. Слабый соперник может попасть мячом в сетку. Равный же соперник может вернуть подачу, и поэтому игра продолжится. В любом случае, как следующее состояние, так и соответствующая ему награда зависят как от условий окружающей среды, так и от соперника. Однако, во всех этих ситуациях агент делает одну и ту же подачу. Поэтому как обучение в состязательных играх, так и прокачка сопернических поведений у агента это сложные проблемы.

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



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

Вот здесь нам и пригодится игра с самим собой! Сам агент удовлетворяет обоим требованиям к искомому оппоненту. Он определенно примерно равен по силе самому себе, и навыки его улучшаются со временем. В данном случае в окружающую среду встроена собственная политика агента (см. на рисунке). Тем, кто знаком с постепенно усложняющимся обучением (curriculum learning), подскажем, что эту систему можно считать естественным образом развивающимся учебным планом, следуя которому, агент научается сражаться против все более сильных оппонентов. Соответственно, игра с самим собой позволяет задействовать саму окружающую среду для обучения конкурентоспособных агентов для состязательных игр!

В двух следующих разделах будут рассмотрены более технические детали обучения конкурентоспособных агентов, касающиеся, в частности, реализации и использования игры с самим собой в инструментарии ML-Agents Toolkit.

Практические соображения

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

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

Реализация и детали использования

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

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

Игра с самим собой в среде Soccer



В последние релизы ML-Agent Toolkit не включается политика агентов для учебной среды Soccer, поскольку надежный учебный процесс в ней не выстраивался. Однако, задействовав игру с самим собой и проведя некоторый рефакторинг, мы сможем обучать агента нетривиальным вариантам поведения. Наиболее существенное изменение это удаление игровых позиций из числа характеристик агента. Ранее в среде Soccer явно выделялись вратарь и нападающий, поэтому весь геймплей выглядел более логично. В данном видео представлена новая среда, в которой видно, как спонтанно формируется ролевое поведение, при котором одни агенты начинают выступать в качестве нападающих, а другие в качестве вратарей. Теперь агенты сами учатся играть на этих позициях! Функция награды для всех четырех агентов определяется как +1.0 за забитый гол и -1.0 за пропущенный гол, с дополнительным штрафом -0.0003 за шаг этот штраф предусмотрен, чтобы стимулировать агентов на атаку.

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

Что дальше

Если вам доводилось пользоваться какими-либо новыми возможностями из этого релиза расскажите о них. Обращаем ваше внимание на страницу ML-Agents GitHub issues, где можно рассказать о найденных багах, а также на страницу форумов Unity ML-Agents, где обсуждаются вопросы и проблемы общего характера.

Методы градиента политики PG довольно популярны в обучении с подкреплением (RL). Базовый принцип состоит в использовании градиентного спуска и подъема в направлениях, где ожидается наибольшая награда. Но при первом приближении оптимизация получается неаккуратной. При чрезмерной самоуверенности мы можем сделать действия, которые разрушат прогресс, достигнутый предыдущей тренировкой. Работы, посвященные TRPO, являются наиболее цитируемыми по этой проблеме. При этом его объясняют без должного введения в три базовые концепции: MM алгоритм, регион доверия и выборка по значимости (перенормировка).

Трудности метода градиента политики (PG)

В RL мы оптимизируем функцию политики, чтобы получать максимальное дисконтированное вознаграждение. Тем не менее есть несколько сложностей, которые вредят.


Первая сложность в том, то PG использует самый крутой спуск по направлению к большему вознаграждению и соответственно делает шаг в этом направлении.



Этот метод использует только первую производную и думает, что поверхность плоская. Если же поверхность изогнутая, то мы можем зайти не туда.



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



Во-вторых, очень трудно узнать правильную скорость обучения (learning rate). Допустим скорость обучения хорошо настроена в желтой точке. Эта область относительно плоская и скорость обучения должна быть выше, чем средняя. Но после неверного шага мы падаем вниз к красной точке. Градиент в этой точке высок и эта скорость обучения приведет к взрыву градиента. Так как скорость обучение не чувствительная к рельефу, то PG будет в таких случаях иметь плохую сходимость. Небольшие изменения в параметрах могут привести к заметным изменениям в политике . Небольшие изменения в политике ведут в большим изменениям в вознаграждении. Надо как-то сделать так, чтобы вознаграждение было под контролем

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

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


Почему? Визуализируем модель политики, как сеть. Увеличение вероятности в одной точке. Тянет за собой близлежащие точки тоже. Состояния внутри траекторий очень похожи в частности, когда они представлены сырыми пикселями. Если мы обновляем политику на каждом шагу, то мы тянем близлежащие точки много раз. Изменения усиливают друг друга и делаю процесс тренировки нестабильным.



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

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

Алгоритм миноризации максимизации

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


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

Для будущих выкладок, пусть является квадратичной функцией.
,
что в векторной форме выглядит так:


функция выпуклая и поэтому хорошо известно, как её оптимизировать.

Суррогатную квадратичную функцию легко построить через разложение в ряд Тэйлора до второго члена и немного модифицировав второй член, умножив его на определенный множитель.

Почему MM алгоритм сходится к оптимальной политике?



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

angms.science/doc/NMF/Surrogate.pdf
www.leg.ufpr.br/~paulojus/EM/Tutorial%20on%20MM.pdf
(Примечание переводчика: для разложения в ряд Тэйлора до второго члена потребуется знание этой матрицы en.wikipedia.org/wiki/Hessian_matrix)

Доверительный регион

В математике есть два метода оптимизации: через линейный поиск и через доверительный регион. Градиентный спуск является примером линейного поиском. Мы сначала определяем направление спуска, а потом делаем шаг в этом направлении.


В методе доверительного региона мы сначала определяем максимальный размер шага и далее ищем оптимальную точку внутри региона. Давайте начнём с начальной точки, определим размер шага , как радиус доверительного региона (желтый круг).

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

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

Выборка по значимости (перенормировка)

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


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





Такой трюк возможен, если старая и новая политики мало отличаются, так как в противном случае использование примеров из другой политики делает процесс сходимости менее стабильным.
Более подробно процесс разобран в
rail.eecs.berkeley.edu/deeprlcourse-fa17/f17docs/lecture_13_advanced_pg.pdf

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

Целевая функция с использованием выборка по значимости(перенормировки).

Разберем детально, как использовать выборку по значимости применительно к PG.
Если изначальная формулировка выглядит так:



Попрбуем записать подругому при условии, что часто =1.
Мы можем обратить производные и получить


Это может быть выражено как



Так как производные обоих целевых функций одинаковы, то и оптимальное решение тоже одинаково.

Присутствие двух политик в процессе оптимизации позволяет формально ограничивать изменения в политике. Это ключевой принцип для многих PG методов. Так же это позволяет оценить новую политику прежде, чем принять изменение.

И так мы описали три базовые концепции, и готовы погрузиться в TRPO.