1 of 23

Efficient Online Learning and Equilibrium Computation in Non-Concave Games

UVA Theory Seminar

​

Weiqiang Zheng

Yale University

Based on joint work with

Costis Daskalakis� MIT

Haipeng Luo

USC

Chen-Yu Wei

Virginia

Yang Cai

Yale

 

2 of 23

Explicit Games Solved using ML & AI

Multi-player games:

  • Go, Poker (Superhuman)
  • Diplomacy, Stratego, Starcraft, Mahjong (Top human)

Multi-agent systems:

  • Autonomous driving
  • Robot interactions
  • Automated design for Economic policies

3 of 23

ML Problems that are Implicitly Games

Generative Adversarial Networks

Synthetic data generation

Adversarial Training

Robustifying models against adversarial attacks

Alignment

Align AI models with human preference

4 of 23

4

Motivating Example: Deep Generative Models

 

 

 

 

 

Simple Randomness

 

Hallucinated Images � (from generator)

Real Images (from training set)

Real or Hallucinated?

 

 

 

 

- Reward discriminator for preferring real from fake images

- Reward generator for fooling the discriminator to prefer fake images

5 of 23

Non-Concave Games

 

 

 

Multi-Agent Setting:

…

 

 

 

 

No Nash eq!

6 of 23

Non-Concave Games

 

 

 

Multi-Agent Setting:

…

 

 

 

 

7 of 23

Non-Concave Games

 

 

Does exist (under compactness, continuity and smoothness) but intractable, even for 2p0s games [Daskalakis-Skoulakis-Zampetakis ‘21].

 

Multi-Agent Setting:

…

 

 

 

Question: Solution concepts that are universal and tractable in non-concave games?

8 of 23

 

 

 

 

 

CCE/CE are intractable!

 

9 of 23

Online Learning

 

 

 

10 of 23

 

 

 

 

z

 

 

 

11 of 23

 

  •  

12 of 23

 

 

 

 

 

 

13 of 23

 

 

 

14 of 23

 

 

 

 

 

 

 

 

15 of 23

 

 

 

…

…

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

16 of 23

 

 

 

 

…

…

 

 

 

 

 

 

 

 

 

 

 

 

 

 

17 of 23

 

 

 

Martingale analysis to guarantee high probability

18 of 23

�Infinite Set of Local Deviations

  •  

19 of 23

�Infinite Set of Local Deviations: Hardness beyond First-Order Approximation

 

 

20 of 23

�Hardness beyond First-Order Approximation

 

 

 

21 of 23

 

 

External

Linear

Proximal

 

 

22 of 23

 

 

External

Linear

Proximal

 

 

23 of 23

Summary

  •