Как будто одного робота, обучающего всему, уже недостаточно
Обучение с подкреплением (RL) изучает классический махинации «обезьяна видит, как обезьяна делает» или «робот, который учится на ходу». Подобно тому, как младенцы учатся и растут с положительным подкреплением со стороны взрослых, RL учит агентов учиться, максимизируя совокупное вознаграждение в их среде. В конечном итоге они приобретают желаемый навык или поведение. За последнее десятилетие мы были свидетелями того, как агенты RL побеждали ведущих киберспортсменов в их собственных играх, учили четвероногих роботов бегу и даже оптимизировали химические реакции. Поле само по себе заслуживает похвалы, но что дальше?
Многоагентное обучение с подкреплением (MARL) изучает, как несколько агентов могут коллективно учиться, сотрудничать и взаимодействовать друг с другом в среде. Это одна из тех вещей, которые заставляют людей вообразить возможности: команды роботов играют в футбол, строят дома или управляют фермами. Обладая численной мощью, MARL может сделать задачи, ранее невыполнимые для роботов, возможными. Однако ему предстоит преодолеть несколько больших препятствий. Как исследователь MARL, это то, что мне нравится: разработка алгоритмов и методов, помогающих преодолевать эти препятствия. Здесь я представляю краткий обзор: вдохновение, формулировки и, самое главное, трудности многоагентного обучения с подкреплением.
Почему это важно
Муравьи - своеобразные существа, которые издавна интересовали исследователей. У них есть эта врожденная способность без усилий общаться, координировать и сотрудничать. В результате их поведение сбило с толку ученых и осталось одним из самых загадочных красот природы. Часто именно это вдохновляет многоагентное обучение робототехнике. Поскольку колонии муравьев без проблем строили укрытия, собирали еду или даже строили мосты своими телами, почему роботы не могут научиться делать то же самое? Если бы мы могли научить роботов достигать той же ловкости, плавности и координации, что и муравьи, потенциал систем с несколькими роботами не имел бы границ.
Фон
Обучение с подкреплением представляет среду как Марковский процесс принятия решений (MDP) с заданным пространством состояний, пространством действий, функцией вознаграждения и функцией вероятностного перехода. Цель агента - изучить политику, которая максимизирует ожидаемое дисконтированное вознаграждение, характеризуемое MDP:
где гамма представляет собой коэффициент дисконтирования. Агент корректирует свою политику, чтобы максимизировать указанное выше значение. Другими словами, агент пытается найти наилучшую последовательность действий, чтобы получить как можно больше награды, уделяя меньше внимания наградам в будущем.
Однако в MARL мы изменяем эту формулировку.
MARL обычно представляет среду как стохастическую игру. Хотя название другое, оно довольно похоже на MDP. Состояния становятся совместными состояниями всех агентов, с разными наградами, соответствующими каждому возможному совместному действию. Функции перехода остаются аналогичными случаю с одним агентом, соответственно заменяя состояния и действия. Предполагая, что у нас есть два агента, мы можем представить одно состояние в виде двухмерной диаграммы.
Пусть пространство действий одного агента будет представлено строками, а пространство второго агента - столбцами. После того, как оба агента выбрали свои действия, мы смотрим на ячейку, соответствующую соответствующей строке и столбцу. Затем каждый агент получает вознаграждение, обозначенное значениями в ячейке.
Общая структура MARL аналогична его одноагентному аналогу, но что делает MARL совершенно новым зверем? Почему мы не можем просто использовать одни и те же алгоритмы одного агента для двух агентов? Группы по десять человек? Сотни?
На первый взгляд, я подумал о простом решении: пусть каждый робот использует алгоритмы с одним агентом, учится самостоятельно и вуаля. Мы заставляем их вместе сносить горы. Конечно, это было неправильно, и вот почему.
Препятствия
Нестационарные переходы
Это одна из самых больших проблем в MARL. В MDP (структура, используемая для одноагентного RL) мы предполагаем стационарные переходы. Мы предполагаем, что при наличии отдельной пары состояния и действия вероятности перехода в другие состояния остаются постоянными на всем протяжении. Например, предположим, что у нас есть робот по имени Wall-E в Location A (его штат). Затем предположим, что он решил переместиться вправо (свое действие), с некоторой вероятностью переместившись в Местоположение Б. Стационарный MDP предполагает, что это значение вероятности остается неизменным до тех пор, пока Wall-E снова решит двигаться вправо в следующий раз, когда он окажется в Location A.
Однако в MARL у нас есть несколько агентов. Мы обозначаем «состояние» в MARL как совместное состояние всех агентов. В результате переходы между состояниями становятся зависимыми от совместных действий всех агентов, т.е. в зависимости от того, как действуют все они, а не только один. Чтобы доказать эту точку зрения о нестационарных переходах, предположим, что у Уолл-И есть друзья, с которыми он хочет поработать.
С точки зрения Валл-И, мы предполагаем, что он не знает действий другого агента. По его мнению, если Валл-И, снова в Местоположение A, дважды переходил вправо, вероятности перехода могут быть разными. Это вызвано тем, что другие агенты, возможно, меняют свои политики. Даже если Wall-E всегда предпочитает идти вправо в Location A, другие агенты могут выбрать другие действия, чем раньше. В результате среда становится нестационарной с точки зрения Валл-И. То, что он совершает одно и то же действие в состоянии, не всегда дает одинаковые результаты.
Итак ... какое это имеет значение?
Агенты RL учатся различать, какие действия предпочтительнее других. Они рассуждают об этом, используя интуитивный принцип: хорошие действия имеют хорошие последствия и наоборот. Другими словами, вознаграждение за действия зависит от состояния, в которое он переходит. Поскольку вероятности перехода с учетом состояния и действия со временем меняются, обучение агентов MARL значительно усложняется. У них не так много информации об окружающей среде по сравнению с задачами с одним агентом.
Экспоненциально увеличивающееся пространство состояний и действий
Столкнувшись с этой проблемой, я склонялся к простому решению: просто задайте единую политику, определяющую действия всех агентов. Таким образом, с точки зрения политики, выполнение этого совместного действия в этом состоянии всегда будет иметь тот же результат впоследствии.
Опять же, это было неправильно. Размеры пространства состояний и действий увеличиваются экспоненциально по отношению к количеству агентов. Это может сделать обучение трудновыполнимым из-за таких вещей, как проклятие размерности. Иногда проблема может стать слишком большой, и конвергенция займет слишком много времени. Интуитивно это имеет смысл. Чем больше решений наша политика должна принять для наших агентов, тем больше времени потребуется, чтобы научиться принимать правильные решения.
Буксир войны
Многоагентное RL пытается примирить эти две противостоящие силы: децентрализацию и централизацию. Как было сказано ранее, первый страдает нестационарностью при хорошей масштабируемости, а второй - наоборот.
Есть много других трудностей с мультиагентными системами, такими как нестабильность воспроизведения опыта, повышенная вариативность градиентов политики и вопрос эффективности данных. Тем не менее, два обсуждаемых выше конкурирующих вопроса по-прежнему составляют суть того, что усложняет MARL.
Ну, блин ... что теперь?
Ну да. Несмотря на то, что существуют проблемы, присущие настройкам с несколькими агентами, которых нет в его аналоге с одним агентом, множество алгоритмов адаптировано к этим условиям. Эти трудности не были полностью решены (конечно), но за последние два десятилетия мы стали свидетелями значительных успехов MARL.
Я считаю, что препятствия в MARL такие же, как и любые другие научные препятствия в прошлом: преодолимые. Нужны ли нам более новые и умные алгоритмы? Нужны ли нам более безумные конструкции роботов? Нужно ли полностью менять формулировку самой проблемы? Не знаю, но загадка в том, что делает это таким увлекательным. Потенциал поля - вот что подталкивает нас к поиску ответа. Несмотря на то, что идея «идеально совместных роботов-муравьев» кажется на данный момент довольно надуманной, исследователи, ученые и фанатики, включая меня, постепенно продвигаются к тому, чтобы сделать ее чуть менее научной фантастикой.
От классических до современных, вот статьи по теме, в которых обсуждаются как многоагентное, так и одноагентное обучение с подкреплением: