Policy Gradients in General-Sum Dynamic Games: When Do They Even Converge?

on YouTube ↗28m

" summary

Shows that policy gradient on general-sum linear-quadratic games fails to guarantee asymptotic convergence: Nash equilibria can be strict saddle points of the gradient dynamics, and proximal-point or extra-gradient updates do not rescue convergence. Empirically up to ~25% of random two-player R2 LQ games produce unstable Nash behavior and persistent limit cycles. Also gives a decentralized matching-market algorithm that combines UCB/Thompson with an adversarial mirror-descent (log-barrier) subroutine, proving logarithmic regret under alpha-reducible markets with unique stable match.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 2:19Traditional machine learning paradigm
3. 2:50Learning in Societal Systems
4. 4:30Do multi-agent policy gradients converge even in the simplest games?
5. 5:15Setup: N-player linear quadratic games
6. 6:58The optimization landscape of LQ Games
7. 8:00Policy gradient in N-player general-sum LQ Games
8. 9:38Critical points of gradient-play in LQ Games
9. 10:39Generating examples
10. 13:32Learning through interaction
11. 14:35Problem: Learning in Matching Markets
12. 16:35Deferred Acceptance Algorithm (Gale-Shapley) Properties of Gale-Shepley
13. 18:04Designing Algorithms for Matching Markets
14. 18:26Algorithm: MM Bandits
15. 19:51Main Results
16. 21:57Numerical Experiments
17. 26:48Full Information Solution: Deferred Acceptance