Проклятие размерности
В одноагентной постановке размер таблицы определяется числом состояний и действий. Как только в расчёт идут совместные действия, размер становится произведением.
Пример из лекции: семь агентов, шесть действий у каждого. Если считать их независимо, хранить нужно 42 значения. С учётом совместных действий пространство раздувается до более чем 270 000 комбинаций. Дальше рост экспоненциальный, и вычислительная сложность останавливает эксперимент раньше, чем алгоритм успевает сойтись.
Для сравнения масштабов, которые в этой области считаются нормальными: около 10⁴³ уникальных позиций в шахматах и порядка 10¹⁶⁸ в го. Оговорка обязательна: это пространства состояний, а расчёт выше — пространство совместных действий, и величины разной природы стоят рядом только как ориентир порядка. Именно поэтому переход к нейросетевым аппроксимациям был не улучшением, а условием выживания области.
Нестационарность среды
Самая коварная из трёх, потому что нарушает базовое допущение.
Классические доказательства сходимости в RL опираются на то, что среда неподвижна: агент пробует действия, и реакция среды зависит только от них. В мультиагентной постановке остальные агенты — тоже часть среды, и они учатся одновременно. Пока один подстраивается под поведение второго, второй меняет своё поведение под первого.
Следствие: гарантий сходимости нет. Формально доказать, что оптимальная стратегия будет найдена, нельзя — в лучшем случае строятся аппроксимации и эмпирически подтверждается стабильность обучения. Отсюда честная формулировка из лекции: инновации в этой области направлены не на доказательство оптимальности, а на улучшение стабильности обучения.
Проблема назначения вклада
Credit assignment problem: команда победила — но кто именно это сделал?
В одноагентном случае задача уже нетривиальна из-за отложенной и разреженной награды: агент совершает сотни действий, а сигнал получает один раз в конце, и непонятно, какое из действий было решающим. В мультиагентном случае к временнóму измерению добавляется пространственное — надо распределить общую награду ещё и между участниками.
Практическая цена этой проблемы: без её решения агенты учатся паразитировать. Если вклад не различается, выгоднее ничего не делать и получать долю от общего результата.
Часть алгоритмов строится прямо вокруг этой задачи: VDN раскладывает общую ценность на слагаемые по агентам, QMIX делает то же нелинейно с ограничением монотонности, COMA оценивает контрфактический вклад — что было бы, поступи агент иначе.
Почему это важно за пределами академии
Три вызова объясняют, почему в MARL нельзя просто «взять больше вычислений». Размерность растёт быстрее любого бюджета, нестационарность делает результат невоспроизводимым от запуска к запуску, а без решения задачи вклада система обучается не тому. Схема CTDE — прямой ответ на второй и третий пункты, а Swarm Intelligence обходит первый, отказываясь от индивидуальных стратегий.
Связано с
- MARL — общая картина области и её эпохи
- CTDE — архитектурный ответ на нестационарность и назначение вклада
- Swarm Intelligence — обход проклятия размерности через однородность агентов
Открытые вопросы
- где практическая граница числа агентов, после которой ни один из известных подходов не даёт стабильного обучения
- как на практике отличают «агент научился паразитировать» от «его вклад действительно мал»