Обучение с подкреплением и дифференциальные игры

Обучение с подкреплением и дифференциальные игры

Когда аналитика недостаточно

Дифференциальные игры обеспечивают красивую теорию, но на практике аналитическое решение HJI возможно лишь в немногих специальных случаях (LQ-игры, задачи с простой динамикой). В реальных задачах — нелинейная динамика, высокая размерность, неизвестная модель системы. Здесь на помощь приходит обучение с подкреплением (Reinforcement Learning, RL): агенты учатся оптимально действовать через взаимодействие со средой, без явного знания динамики. Multi-Agent RL обобщает это на игровой случай.

Игровой RL: постановка

Марковская дифференциальная игра: дискретизация непрерывного времени.

• Состояние s ∈ S
• Действия агентов: a₁ ∈ A₁, a₂ ∈ A₂
• Переход: P(s' | s, a₁, a₂)
• Награды: r₁(s, a₁, a₂), r₂(s, a₁, a₂)

Агент i хочет максимизировать дисконтированную сумму наград: Σₜ γᵗ rᵢₜ.

Проблема нестационарности: если агент 1 обновляет свою политику, среда с точки зрения агента 2 меняется. «Цель» движется — сходимость Q-learning не гарантирована!

Independent Q-learning (IQL)

Каждый агент i учит свою Q-функцию Qᵢ(s, aᵢ) независимо, не учитывая действия других.

Обновление: Qᵢ(s, aᵢ) ← (1−α) Qᵢ + α[rᵢ + γ max_{aᵢ'} Qᵢ(s', aᵢ')].

Преимущества: простота, масштабируемость на много агентов.

Недостатки: нет теоретических гарантий сходимости. Среда нестационарна. На практике часто работает!

MADDPG (Multi-Agent DDPG)

Ключевая идея: централизованное обучение, децентрализованное исполнение (CTDE).

Во время обучения: критик Qᵢ(x, a₁,...,aN) видит все состояния и действия. Актор μᵢ(oᵢ) видит только своё наблюдение. Критик обеспечивает «стабильную» оценку качества.

Во время исполнения: каждый агент действует только на основе своего oᵢ — децентрализованно.

Обновление критика: Lᵢ = E[(Qᵢ(x,a) − yᵢ)²], yᵢ = rᵢ + γ Qᵢ'(x', a₁',...,aN')|_{aⱼ'=μⱼ'(oⱼ')}.

Обновление актора: ∇θᵢ J = E[∇{aᵢ} Qᵢ · ∇_θᵢ μᵢ(oᵢ)].

Преимущество: критик «видит» полную картину → стабильное обучение. В NE: Qᵢ(x, a*) точно оценивает равновесную стоимость.

Self-Play и конвергенция к Nash

Self-play: агент играет против копии себя. При правильной реализации сходится к NE для двухигровых нулевых игр (например, шахматы, го).

AlphaGo/AlphaZero: pure self-play + MCTS (Monte Carlo Tree Search) + глубокие нейросети. Достигает сверхчеловеческого уровня в го и шахматах — фактически решая огромную дискретную «дифференциальную» игру.

League Training (AlphaStar): для StarCraft II — игра с большой неопределённостью. Набор «лиги» — разнородных прошлых версий агента, избегает «цикличности» (A бьёт B, B бьёт C, C бьёт A).

Связь с уравнением HJI через Actor-Critic

Непрерывный actor-critic ↔ дифференциальная игра:

Критик ≈ V(s,t) — функция ценности (аппроксимация HJI-решения). Актор ≈ u*(s,t) — оптимальная стратегия обратной связи.

Policy gradient для игр: ∇_θ E[J] = E[Σₜ ∇_θ log π_θ(aᵢₜ|oᵢₜ) · Aᵢₜ], где Aᵢₜ = Qᵢ(s,a) − Vᵢ(s) — advantage.

Это приближённый градиент игровой стоимости по параметрам политики.

MAPPO (Multi-Agent PPO): расширение PPO на N агентов с разделёнными критиками. Стандарт в современных MARL-задачах (StarCraft, Google Football, оптимизация трафика).

Полный разбор: конвергенция MADDPG на задаче коопераций

Задача: 2 агента, цель — встретиться в точке (5, 5). Джoint-reward: r = −|x₁ − goal| − |x₂ − goal|.

Каждый агент выбирает ускорение (2D action). Наблюдение: своя позиция.

Обучение MADDPG (1000 эпизодов):

• Эпизод 1-100: агенты движутся случайно, средняя награда ≈ −15
• Эпизод 100-500: агенты начинают двигаться к центру, но разными путями, ≈ −8
• Эпизод 500-1000: конвергенция к «рандеву» стратегии, ≈ −2

Nash-интерпретация: в NE оба агента двигаются напрямую к (5,5) — ни один не может улучшить свой результат в одностороннем порядке. MADDPG находит это NE через взаимодействие.

Многоагентное обучение с подкреплением (MARL)

Когда среда содержит других обучающихся агентов, классический Q-learning (один агент против стационарной среды) перестаёт работать: «среда» нестационарна, потому что другие агенты тоже учатся. Возникает связь с теорией дифференциальных игр.

Алгоритмы MARL

• Independent Q-learning: каждый агент учится независимо. Простой, но без гарантий сходимости.
• MADDPG (Multi-Agent DDPG, Lowe et al., 2017): centralized training, decentralized execution — критик видит все стратегии при обучении, актор использует только свою наблюдаемость в исполнении.
• Nash-Q learning: явный поиск равновесия Нэша на каждом шаге.
• PSRO (Policy-Space Response Oracles): итеративно расширяет популяцию стратегий, ищет лучший ответ на текущее распределение.
• MFRL (Mean Field RL): применение mean field approximation к большим N-агентным играм.

Связь с дифференциальными играми

В пределе непрерывного времени и состояний RL для игр сходится к решению HJI. Q-функция аппроксимирует V (функцию ценности игры). Это обоснование того, почему RL может находить равновесия в сложных играх:

• AlphaZero — аналог решения нулевой суммы игры (шахматы, Го) через self-play
• AlphaStar — частичная информация (StarCraft II) через Counterfactual Regret Minimization
• OpenAI Five — кооперация в команде против команды (Dota 2)

Открытые проблемы

• Гарантии сходимости MARL в общем случае
• Масштабирование на тысячи агентов
• Объяснимость стратегий
• Безопасность (avoiding adversarial exploitation)

Применения

MARL и дифференциальные игры применяются в торговых ботах (HFT, market making), управлении дронами в роях, координации автономного транспорта, балансировке энергосетей, в обучении военных тактик в симуляторах.