Теория игр
Теория игр в ML
Когда Гудфеллоу в 2014 году написал GAN, он применил к нейросетям идею 80-летней давности - минимаксную теорему фон Неймана. Когда OpenAI обучала Five для Dota, они использовали self-play - концепцию из теоремы Нэша. Теория игр - не отдельная область от ML, а её математический фундамент для задач с несколькими агентами и противостоянием.
- **GAN → Stable Diffusion, Midjourney:** прямое наследие GAN через diffusion модели. Понимание минимаксной нестабильности объясняет переход от GAN к диффузии
- **Adversarial robustness:** банки, медицинские AI, системы безопасности обязаны иметь защиту от adversarial атак. FGSM и PGD - стандарт аудита
- **OpenAI Five / AlphaStar:** мульти-агентное обучение через self-play - открытая проблема в MARL. Эти системы показали масштаб, но не решили теоретические вопросы сходимости
Предварительные знания
GAN как минимаксная игра
Гудфеллоу в 2014 году предложил генерировать изображения через игру. Генератор G пытается создать «фальшивые» данные, похожие на реальные. Дискриминатор D пытается отличить реальное от сгенерированного. Они соперники: G хочет обмануть D, D хочет не быть обманутым. Это классическая игра с нулевой суммой в непрерывном пространстве стратегий.
min_G max_D V(G, D) = E_{x~p_data}[log D(x)] + E_{z~p_z}[log(1 - D(G(z)))] D(x) → 1 для реальных, D(G(z)) → 0 для фальшивых. G минимизирует: хочет D(G(z)) → 1 (обмануть D). Равновесие Нэша: p_G = p_data (генератор воспроизводит реальное распределение), D(x) = 1/2 везде.
Теоретическое равновесие GAN имеет строгую форму: G воспроизводит реальное распределение, D не может их различить. На практике обучение GAN нестабильно: mode collapse (G генерирует один вид), vanishing gradients, циклические осцилляции. Причина: одновременный gradient descent в игре не сходится к NE стандартными методами.
GAN - одна из самых влиятельных идей в ML
Ян Гудфеллоу предложил GAN на вечеринке в честь получения PhD (2014). Первоначально статья была написана за ночь. Идея игры генератора и дискриминатора стала фундаментом для StyleGAN, DALL-E (ранние версии), Stable Diffusion прекурсоров. По сей день нестабильность GAN - активная область исследований, решаемая через Wasserstein GAN, spectral normalization и другие инструменты из теории игр.
GAN обучение сходится к Nash Equilibrium стандартным gradient descent
Стандартный simultaneous gradient descent в zero-sum играх не сходится к NE - он циклирует. Для GAN нужны специальные методы (Wasserstein loss, spectral norm, two-timescale updates).
Одновременный gradient descent в непрерывной игре соответствует репликаторной динамике с осцилляциями. Для сходимости к NE нужны extra-gradient методы или другие стабилизаторы.
Равновесие Нэша GAN - это состояние, при котором:
Adversarial Machine Learning
Хакер хочет обмануть спам-фильтр. Модель атаки: хакер - игрок 1 (атакующий), фильтр - игрок 2 (защитник). Хакер минимизирует вероятность обнаружения, фильтр максимизирует её. Это снова минимаксная игра, но теперь ставки реальны: кражи паролей, обходы модерации, уход от распознавания лиц. Adversarial ML - прикладная теория игр с нулевой суммой.
Adversarial example: x' = x + ε · sign(∇_x L(θ, x, y)) FGSM (Fast Gradient Sign Method, Goodfellow et al. 2015): добавляем малый шум вдоль градиента лосса - и модель «видит» пандой автобус. Атака и защита - итеративная игра. Каждая защита создаёт новую поверхность атаки. Нет абсолютной защиты - только компромисс между точностью и робастностью.
| Тип атаки | Метод | Пример применения |
|---|---|---|
| Evasion (белый ящик) | FGSM, PGD, C&W | Обход детектора вредоноса |
| Evasion (чёрный ящик) | Transfer attacks, query-based | Обход API классификатора |
| Data poisoning | Вставка backdoor в train set | Отравление модели безопасности |
| Model extraction | Oracle queries | Кража модели через API |
Adversarial ML - гонка вооружений: новые атаки, новые защиты. Теория игр предсказывает исход: при нулевой сумме не существует «идеальной» защиты без потери точности на чистых данных. Это теоретически доказано: любой классификатор имеет adversarial примеры для ε-шара произвольно малого радиуса (при выполнении условий на распределение).
Adversarial training полностью решает проблему adversarial примеров
Adversarial training повышает робастность против известных атак, но не против новых. Это гонка вооружений: после каждой защиты появляются новые атаки.
Теоретически доказано (Tsipras et al., 2019): существует фундаментальный trade-off между точностью на чистых данных и робастностью к adversarial атакам. Нет «бесплатного обеда».
FGSM (Fast Gradient Sign Method) создаёт adversarial example путём:
Multi-Agent Reinforcement Learning
OpenAI Five обыграла чемпионов мира в Dota 2. AlphaStar - в StarCraft II. AlphaZero - в шахматах, го и сёги. Все эти системы - Multi-Agent RL: несколько RL-агентов обучаются, взаимодействуя друг с другом. Проблема: среда каждого агента нестационарна (зависит от политики других, которые тоже меняются). Это не single-agent RL - нужна теория игр.
Расширение MDP для нескольких агентов: - S - состояния, Aᵢ - действия агента i - T: S × A₁ × ... × Aₙ → Δ(S) - переходы - Rᵢ: S × A₁ × ... × Aₙ → R - награды Цель каждого i: max Σ_t γᵗ rᵢ(t) NE в марковской игре = Nash policy profile: политика π*ᵢ является лучшим ответом на π*₋ᵢ в каждом состоянии.
Self-play - ключевой метод для двух-игровых zero-sum игр. Но для кооперативных задач (multi-robot, командные игры) нужны другие подходы: Centralized Training Decentralized Execution (CTDE), Communication protocols, Credit assignment. В кооперативных играх агенты должны научиться не только оптимальным политикам, но и как координироваться.
Self-play всегда работает для любой игры
Self-play эффективен для zero-sum игр (шахматы, го, StarCraft). В кооперативных или смешанных играх self-play может сходиться к неоптимальным equilibria или вовсе не сходиться.
В zero-sum играх self-play гарантированно не хуже любой фиксированной стратегии (minimax). В кооперативных - нет механизма координации, поэтому нужны дополнительные методы: communication, centralised critic.
Почему Multi-Agent RL сложнее Single-Agent RL?
Minimax оптимизация в ML
GAN - не единственное место, где ML встречает минимакс. Robust optimization (защита от наихудшего случая), distributionally robust ML (защита от сдвига распределения), meta-learning (inner loop vs outer loop) - всё это минимаксные задачи. Понимание теории игр помогает видеть единую структуру за разными методами.
min_θ max_φ L(θ, φ) Примеры: - GAN: θ = параметры G, φ = параметры D - Adversarial training: θ = модель, φ = атака - Distributionally robust: θ = модель, φ = наихудшее распределение - Bi-level optimization: θ = meta-params, φ = task-specific params Вычислительная проблема: simultaneous GD не сходится к saddle points.
| Метод | Сходимость к NE | Применение |
|---|---|---|
| Simultaneous GD | Нет (циклы) | Наивный GAN |
| Extragradient | Да (для монотонных игр) | Стабилизация GAN |
| Optimistic GD | Да (для биматричных) | WGAN, spectral norm |
| PSRO | Да (Self-play обобщение) | OpenAI Five, AlphaStar |
Понимание minimax оптимизации через линзу теории игр даёт интуицию: почему GAN нестабилен (simultaneous GD не конвергирует), почему Wasserstein GAN устойчивее (ограничение Lipschitz = регуляризация «игры»), почему spectral normalization помогает. Это не просто «тюнинг гиперпараметров» - это изменение геометрии игры.
GAN обучение нестабильно из-за ошибок в архитектуре или гиперпараметрах
Нестабильность GAN - фундаментальное свойство simultaneous gradient descent в zero-sum играх. Даже с идеальной архитектурой симультанный GD циклирует вокруг NE.
В квадратичном minimax (x·y): simultaneous GD порождает эллиптическую орбиту, не сходится. Extragradient и Optimistic GD имеют теоретически доказанную сходимость для монотонных операторов.
Почему Extragradient метод стабилизирует GAN обучение лучше простого Gradient Descent?
Ключевые идеи
- **GAN = минимакс игра:** G минимизирует, D максимизирует. NE = p_G = p_data. Simultaneous GD не сходится к NE
- **Adversarial ML:** гонка вооружений атака/защита - zero-sum игра с фундаментальным trade-off точность/робастность
- **MARL:** среда нестационарна; self-play → NE в zero-sum; CTDE для кооперативных задач
- **Extragradient:** стабилизация minimax обучения через lookahead. Wasserstein GAN, spectral norm - регуляризация игры
Связанные темы
ML - крупнейшее современное приложение теории игр:
- Игры с нулевой суммой — GAN и adversarial ML - непрерывные zero-sum игры; минимакс фон Неймана напрямую
- Эволюционная теория игр — Replicator dynamics = Multiplicative Weights Update = gradient descent в играх
- Algorithmic Game Theory — No-regret learning → correlated equilibrium; PoA в распределённых ML системах
Вопросы для размышления
- GAN обучение нестабильно из-за свойств игры. Stable Diffusion обходит это, не используя GAN. В каком смысле диффузионные модели - это «избегание игры»? Что они теряют и что приобретают?
- Adversarial robustness и accuracy - trade-off. Как это связано с Price of Anarchy? Что «социальный оптимум» здесь, и кто «эгоистичный агент»?
- MARL используется в робототехнике, автономных транспортных системах, финансовом трейдинге. В каждом случае - разные игры (cooperative, competitive, mixed). Какой подход обучения подходит для каждого?