Усиление конкурентных мультиагентов для игры "So Long Sucker"

Основная информация

• ID статьи: 2411.11057
• Название: Reinforcing Competitive Multi-Agents for Playing 'So Long Sucker'
• Авторы: Medant Sharan (King's College London), Chandranath Adak (IIT Patna)
• Категория: cs.AI
• Дата публикации: ноябрь 2024 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2411.11057

Аннотация

В данной работе впервые стратегическая игра "So Long Sucker" (SLS) вводится в область мультиагентного обучения с подкреплением (MARL) в качестве нового эталона. В отличие от традиционных платформ тестирования настольных игр или видеоигр, SLS характеризуется формированием коалиций, стратегическим обманом и динамическими правилами исключения, предоставляя уникальную среду вызовов для автономных интеллектуальных агентов. Исследователи разработали первую общедоступную вычислительную платформу SLS, включающую графический интерфейс пользователя и поддержку эталонного тестирования алгоритмов обучения с подкреплением. Путём обучения агентов самоигре с использованием классических методов глубокого обучения с подкреплением (DQN, DDQN, Dueling DQN) агенты изучают правила SLS и базовые стратегии. Экспериментальные результаты показывают, что хотя эти агенты достигают примерно половины максимально возможного вознаграждения и постоянно превосходят случайный базовый уровень, они требуют длительных периодов обучения (примерно 2000 игр) и всё ещё иногда выполняют недопустимые действия, что подчёркивает потенциал и ограничения классического обучения с подкреплением.

Предпосылки и мотивация исследования

Определение проблемы

Существующие эталоны мультиагентного обучения с подкреплением в основном сосредоточены на чисто кооперативных целях (таких как координационные задачи) или антагонистической конкуренции (таких как двухличные нулевые игры), не хватает смешанных сред, которые одновременно захватывают динамику формирования коалиций и предательства. Хотя были достигнуты прорывы в таких областях, как Go, StarCraft II и Diplomacy, эти эталоны не полностью отражают смешанную динамику коалиций и предательства, уникальную для SLS.

Значимость исследования

SLS как четырёхпользовательская стратегическая игра, разработанная Hausner, Nash, Shapley и Shubik, вращается вокруг формирования коалиций, временных альянсов и неизбежного предательства. Победа зависит не только от законных действий, но также требует дипломатии и оппортунизма, что делает её уникальной платформой для исследования доверия, переговоров и социальных дилемм.

Ограничения существующих подходов

1. Большинство эталонов MARL не содержат смешанной динамики коалиций и предательства
2. Предыдущие работы в социально богатых условиях обычно полагаются на явные каналы связи или ручной создание правил взаимодействия
3. SLS ранее не изучалась как вычислительный эталон

Мотивация исследования

Путём формализации SLS как воспроизводимого последовательного варианта и эталонного тестирования базовых алгоритмов DRL данная работа позиционирует SLS как платформу для продвижения исследований MARL, осведомлённую о коалициях и предательстве.

Основные вклады

1. Первая вычислительная платформа SLS: Разработана и выпущена первая вычислительная платформа SLS, специально разработанная для исследований обучения с подкреплением, оснащённая графическим интерфейсом для экспериментов
2. Эталонное тестирование классических алгоритмов DRL: Проведено эталонное тестирование классических алгоритмов DRL (DQN, DDQN, Dueling DQN) на SLS с анализом их способности достичь законного мастерства в игре и частичного стратегического осознания
3. Эталон, осведомлённый о коалициях и предательстве: Установлено SLS как эталон MARL, осведомлённый о коалициях и предательстве, стимулирующий будущие исследования гибридных методов, объединяющих DRL и рассуждения теории игр

Подробное описание методологии

Определение задачи

Преобразование SLS в среду MARL с использованием обобщённого нулевого варианта версии Hofstra. Четыре игрока, каждому назначен уникальный цвет, начинают с 5 фишек одного цвета и играют на доске с максимум 6 активными стопками. Условие победы — быть последним оставшимся игроком.

Формализация обучения с подкреплением

Моделирование SLS как марковского процесса принятия решений (MDP):

• Пространство состояний S: множество всех возможных состояний игры
• Пространство действий A: множество всех доступных действий агента (дискретный набор допустимых ходов)
• Функция переходов: p(s'|s,a) представляет вероятность перехода в s' после выполнения действия a в состоянии s
• Функция вознаграждения: r(s,a,s') назначает скалярное значение каждому переходу
• Политика: π(a|s) — политика выбора действия a агентом в заданном состоянии s

Цель состоит в нахождении оптимальной политики π* для максимизации ожидаемого дисконтированного возврата: $R_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}$

Представление состояния

Состояние st кодирует всю информацию, необходимую для описания окружающей среды игры: $s_t = (Board\ Configuration, Player\ Chips, Eliminated\ Chips, Current\ Player, Game\ Phase, Step\ Count)$

Размер пространства наблюдений: $obs\_size = (n_{rows} \times n_{players} \times n_{max\_pile}) + n_{players}^2 + (2 \times n_{players}) + 4 + 1$

Пространство действий

Дискретное пространство действий A = {A₀, A₁, ..., A₉}, включающее:

• A₀-A₅: действия выбора стопки (действительны на этапе выбора стопки)
• A₆-A₉: действия принятия решения игроком/цветом (действительны на этапах выбора фишки, выбора следующего игрока, исключения фишек)

Проектирование вознаграждения

Сигнал вознаграждения на временном шаге t определяется как: $r_t = \min\left(\wp, \frac{\wp}{(\alpha/n_c) \cdot t}\right)$

где α ∈ (0,1] — гиперпараметр, контролирующий скорость затухания, ℘ — величина вознаграждения. Недопустимые действия наказываются фиксированным отрицательным вознаграждением (-℘), допустимые действия получают положительное вознаграждение до +℘, значение которого убывает с количеством шагов для стимулирования эффективности.

Экспериментальная установка

Конфигурация игры

• Количество игроков: 4 игрока
• Начальные фишки: 5 фишек одного цвета для каждого игрока
• Максимальное количество стопок: 6 активных стопок
• Условие победы: нулевая сумма, структура вознаграждения {0,0,0,ù}, ù ∈ ℕ⁺

Конфигурация обучения

Используется централизованная кумулятивная установка обучения, где все четыре агента игроков совместно используют общую сеть обучения и буфер воспроизведения. Архитектура сети состоит из двух полносвязных скрытых слоёв с 64 нейронами (активация ReLU), за которыми следует линейный выходной слой.

Установка гиперпараметров

• Коэффициент дисконтирования γ = 0,95
• Начальный коэффициент исследования ε₀ = 1,0
• Скорость затухания исследования ε_decay = 0,995
• Минимальный коэффициент исследования ε_min = 0,01
• Скорость обучения = 0,001
• Размер пакета = 64
• Количество эпох обучения = 10 000 игр

Метрики оценки

• Среднее и стандартное отклонение кумулятивного вознаграждения
• Среднее количество шагов за игру
• Диапазон вознаграждения минимум, максимум
• Диапазон шагов минимум, максимум

Методы сравнения

• DQN (Deep Q-Network)
• DDQN (Double DQN)
• Dueling DQN
• Random baseline (случайный базовый уровень)

Экспериментальные результаты

Основные результаты

Ключевые находки

1. Производительность: Все агенты DRL постоянно превосходят случайный базовый уровень, достигая примерно половины теоретического максимального вознаграждения (≈200)
2. Характеристики сходимости: DDQN достигает наиболее стабильной сходимости и наивысшего среднего вознаграждения, подтверждая преимущества двойной оценки в смягчении переоценки Q-значений в долгосрочных играх
3. Динамика обучения: На ранних этапах обучения (<500 игр) агенты демонстрируют высокую дисперсию вознаграждения, после примерно 2000 игр все агенты DRL показывают более гладкую сходимость

Анализ кривых обучения

Процесс обучения разделяется на три этапа:

• Этап исследования (0-500 игр): высокая дисперсия, частые недопустимые действия
• Этап обучения (500-2000 игр): постепенное овладение правилами, устойчивый рост вознаграждения
• Этап сходимости (>2000 игр): стабильное вознаграждение в диапазоне 100-120, случайные исследовательские спады

Связанные работы

Развитие эталонов MARL

• Традиционные эталоны: Go, StarCraft II сосредоточены в основном на чистой конкуренции или кооперации
• Социальные игры: Diplomacy включает переговоры, но полагается на явную коммуникацию
• Применение теории игр: Применение решения равновесия Нэша в многоагентных системах

Применение глубокого обучения с подкреплением в играх

• Серия AlphaGo: прорывы в играх с полной информацией
• Мультиагентное обучение: обучение самоигре и разнообразие стратегий
• Методы функции стоимости: применение DQN и его вариантов в дискретных пространствах действий

Исследования, связанные с SLS

Данная работа впервые использует SLS как вычислительный эталон, заполняя пробел в исследовании динамики формирования коалиций и предательства.

Заключение и обсуждение

Основные выводы

1. Классические методы, основанные на функции стоимости, могут изучать основные правила SLS и частичные стратегии, достигая стабильной, но субоптимальной производительности
2. Высокая дисперсия вознаграждения отражает чувствительность к инициализации и исследованию
3. Контекстно-зависимые действия выявляют ограничения краткосрочной оценки стоимости
4. SLS успешно установлено как эталон MARL, осведомлённый о переговорах

Ограничения

1. Ограничения стратегии: Агенты склонны к реактивному, а не стратегическому поведению
2. Соблюдение правил: Несмотря на динамическое маскирование действий, иногда выполняются недопустимые действия
3. Долгосрочное рассуждение: Трудности в комбинаторном пространстве действий и зависимости от отложенного вознаграждения
4. Динамика коалиций: Неполное захватывание сложной динамики формирования коалиций и предательства

Направления будущих исследований

1. Улучшения архитектуры: Интеграция actor-critic и фреймворков, осведомлённых о коалициях
2. Усиление стратегии: Укрепление долгосрочного рассуждения и соблюдения правил
3. Социальная динамика: Разработка способностей переговоров/коалиций/обмана
4. Теоретический анализ: Объединение рассуждений теории игр с глубоким обучением

Углубленная оценка

Преимущества

1. Инновационный эталон: Впервые вводит SLS в MARL, заполняя важный пробел в исследовании динамики коалиций и предательства
2. Полный фреймворк: Предоставляет полную вычислительную платформу с графическим интерфейсом, способствуя воспроизводимым исследованиям
3. Систематическая оценка: Проводит комплексное эталонное тестирование нескольких классических методов DRL
4. Теоретический вклад: Чётко определяет правила нулевого варианта, решая неполноту исходной формализации

Недостатки

1. Ограничения методологии: Тестируются только классические методы, основанные на функции стоимости, не исследуются более продвинутые алгоритмы MARL
2. Упрощённая установка: Удаление явного механизма переговоров может привести к потере основных характеристик SLS
3. Узкие места производительности: Агенты всё ещё выполняют недопустимые действия, выявляя недостатки базовых методов
4. Недостаточный теоретический анализ: Отсутствует углубленный анализ теоретико-игровых свойств SLS

Влияние

1. Академическая ценность: Предоставляет сообществу MARL новое направление исследований и эталон
2. Практическое значение: Выпуск открытого исходного кода платформы будет способствовать последующим исследованиям
3. Методологический вклад: Демонстрирует, как преобразовать сложную стратегическую игру в среду, дружественную к машинному обучению
4. Вдохновение ограничениями: Выявляет недостатки классического RL в сложных социальных играх, указывая направление будущих исследований

Применимые сценарии

1. Исследования MARL: Разработка алгоритмов для динамики формирования коалиций и предательства
2. Применение теории игр: Вычислительные модели многосторонних переговоров и стратегического рассуждения
3. Социальный ИИ: Моделирование поведения доверия, обмана и сотрудничества
4. Образовательный инструмент: Демонстрация теории игр и многоагентных систем в обучении

Библиография

1. Hausner, M., Nash, J., Shapley, L., & Shubik, M. (1964). So Long Sucker- A Four-Person Game
2. Vinyals, O. et al. (2019). Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature
3. FAIR Team et al. (2022). Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science
4. Mnih, V. et al. (2015). Human-level control through deep reinforcement learning. Nature

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