Multi-Agent RL

В 2019 году OpenAI запустила эксперимент: прячущиеся и ищущие агенты в физической среде с блоками и рампами. Через 500 миллионов эпизодов прятальщики начали строить крепости, а ищущие - изобрели surf-технику с рампами. Никто это не программировал. Это и есть мощь Multi-Agent RL: интеллект, возникающий из взаимодействия.

• **OpenAI Five** - пять агентов координировали командные действия в Dota 2 на уровне профессиональных игроков, изобретя тактику жертв и ротаций без единой подсказки.
• **AlphaStar (DeepMind)** достиг уровня грандмастера в StarCraft II через league training с разными типами агентов, покрывающими пространство возможных стратегий.
• **Сети автономных автомобилей**: MARL-подход к координации перекрёстков без светофоров даёт на 40% лучшую пропускную способность, чем традиционные алгоритмы.

От марковских игр к MADDPG и QMIX

Multi-agent RL вырос из теории игр. В 1994 году Майкл Литтман опубликовал «Markov games as a framework for multi-agent reinforcement learning», обобщив одноагентный MDP до стохастических игр, где несколько агентов действуют одновременно, и предложил алгоритм minimax-Q для антагонистических игр двух игроков. Глубокий MARL пришёл двумя десятилетиями позже: в 2017 году Райан Лоу с коллегами из OpenAI опубликовали MADDPG - метод centralized training, decentralized execution с критиком, видящим действия всех агентов. В 2018 году Табиш Рашид с коллегами представили QMIX, который факторизует совместную action-value на индивидуальные значения через монотонную mixing network, позволяя кооперативному обучению масштабироваться на множество агентов.

Предварительные знания

• Actor-Critic: A2C, A3C
• Deep Q-Network (DQN)

Кооперативный MARL

В 2019 году OpenAI обучила команду из пяти агентов играть в Dota 2 против профессиональных игроков - и победила. Никто не программировал тактику ганков или роутинг. Стратегия возникла сама из кооперативного обучения с подкреплением. Кооперативный MARL решает задачу: несколько агентов с общей целью должны координировать действия, не имея возможности видеть чужие наблюдения. Центральная проблема - кредитное присвоение (credit assignment): кто из N агентов внёс вклад в командную победу? CTDE (Centralized Training, Decentralized Execution) - архитектурный паттерн, ставший стандартом: во время обучения критик видит глобальное состояние, во время выполнения каждый агент действует только по своим наблюдениям.

CTDE: обучение с централизованным критиком Q_tot(s, a_1...a_n), выполнение с децентрализованными политиками pi_i(a_i | o_i). QMIX (2018) - ключевой алгоритм: монотонная факторизация Q_tot через индивидуальные Q_i гарантирует согласованность децентрализованных решений с оптимальным совместным действием.

Конкурентный MARL

AlphaStar - агент SC2 - достиг уровня грандмастера, обучившись против самого себя через self-play. За два месяца тренировки агент сыграл эквивалент 200 лет человеческого игрового времени. Self-play - ключевой механизм конкурентного MARL: агент обучается против своих прошлых версий, создавая постоянно растущий по сложности adversarial curriculum. Проблема - циклы: A бьёт B, B бьёт C, C бьёт A. Решение - League Training (AlphaStar) с разными типами агентов: main players, league exploiters, main exploiters. Каждый тип имеет разную цель: эксплуататоры ищут слабости текущей лучшей политики, основные агенты учатся против всего пула.

Nash equilibrium в zero-sum играх: ни один агент не может улучшить результат, изменив стратегию в одностороннем порядке. Self-play сходится к Nash equilibrium только в двухагентных zero-sum играх (теорема минимакса). В многоагентных или смешанных играх возможны циклы и non-convergence - это активная область исследований.

Коммуникация между агентами

Агенты OpenAI в игре hide-and-seek неожиданно научились использовать предметы как инструменты - строить баррикады и переносить рампы. Никто не программировал эту стратегию. Она возникла из коммуникации через физику среды. Формальная коммуникация в MARL - это передача дифференцируемых сообщений между агентами. CommNet (2016) передаёт непрерывные векторы через среднее. DIAL (2016) делает канал связи дифференцируемым end-to-end - агенты учатся говорить то, что полезно. MADDPG с коммуникацией позволяет агентам обмениваться скрытыми состояниями во время обучения (но не во время выполнения).

Типы коммуникации: broadcast (всем), targeted (конкретному агенту), emergent (через действия в среде). Bandwidth constraint (ограничение на размер сообщения) критичен: агенты должны научиться сжимать полезную информацию. Без ограничений AgentI просто транслирует своё полное состояние - никакого обучения коммуницировать не происходит.

Эмерджентное поведение

В эксперименте OpenAI hide-and-seek прятальщики сначала просто убегали. Потом - начали строить заграждения из блоков. Ищущие научились использовать рампы, чтобы перепрыгивать. Прятальщики научились убирать рампы. Шесть стадий эволюции стратегий возникли без единой строки кода, описывающей эти стратегии. Это и есть эмерджентность: глобальное сложное поведение из простых локальных правил. В MARL эмерджентность - неизбежное следствие: агенты адаптируются к другим агентам, которые адаптируются в ответ. Это создаёт нескончаемый поток новых задач - открытый динамический curriculum, который невозможно спроектировать вручную.

Эмерджентные явления в известных MARL-экспериментах: hide-and-seek (6 фаз стратегий), OpenAI Five (командная ротация, жертвы), AlphaStar (новые билды в SC2). Измерение сложности: Elo рейтинг, Nash averaging (не зависит от циклов). Открытый вопрос: как предсказать, какое эмерджентное поведение возникнет, до начала обучения?

Ключевые идеи

• **CTDE** (Centralized Training, Decentralized Execution) - стандарт кооперативного MARL: глобальный критик при обучении, локальные политики при выполнении.
• **Self-play** со случайным пулом противников (PFSP) решает проблему циклов в конкурентных играх и создаёт автоматический curriculum сложности.
• **Коммуникация** с ограниченной пропускной способностью стимулирует агентов учиться сжатому информационному языку вместо прямой трансляции состояния.
• **Эмерджентность** непредсказуема: стратегии, возникающие из взаимодействия агентов, невозможно спроектировать заранее - это и угроза, и возможность.

Связанные темы

Multi-Agent RL пересекается с теорией игр и системами ИИ:

• Model-Based RL — World Models в MARL позволяют агентам моделировать поведение других агентов и планировать в их присутствии
• RL для роботов — Роевая робототехника использует MARL для координации без центрального управления

Вопросы для размышления

• Как отличить действительно эмерджентное поведение от поведения, которое было неявно закодировано в reward-функции?
• Почему Nash Averaging, а не просто Elo, используется для оценки агентов в league training AlphaStar?
• Что произойдёт, если в кооперативной игре с QMIX один агент начнёт преследовать личную выгоду вместо командной цели?

Связанные уроки

• rl-10 — Каждый агент обучается policy gradient методами вроде PPO
• rl-19-marl — Углублённо: CTDE и кооперативные MARL алгоритмы
• gt-01 — Теория игр формализует равновесия многоагентных систем
• gt-04 — Равновесие Нэша описывает исходы конкурентного MARL
• st-05-emergence — Эмерджентное поведение рождается из локальных взаимодействий агентов