The Complexity of Infinite-Horizon General-Sum Stochastic Games

on YouTube ↗20m

" summary

Shows that finding an approximate Nash for infinite-horizon general-sum stochastic games is PPAD-complete both for simultaneous and for turn-based models under finite states/actions, stationary policies, nonnegative rewards, and polynomially bounded 1/(1−γ) or mixing time. Introduces a pseudo-linear property to relate utilities to normal-form games and builds game gadgets to implement arithmetic-circuit gates for the hardness reduction. Identifies localized reward turn-based games as solvable in polynomial time via a alternating coordinate-wise algorithm using a log-space Markov potential.

AI-written summary · about

" chapters (6)

1. 0:00Introduction
2. 0:18Basic Mathematical Model
3. 1:57Simultaneous Stochastic Games
4. 8:42Common Challenges
5. 10:57Pseudolinear Property
6. 15:25Localized Reward

" related talks

• 15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust ControlKaiqing Zhang · Meet the Fellows Welcome Event
• 25mReal Algebraic Geometry in Computational Game TheoryPeter Bro Miltersen · Solving Polynomial Equations (Simons Institute, 2014)
• 52mThe Simplex and Policy-Iteration Methods are Strongly Polynomial...Yinyu Ye · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 49mFast Rates for No-Regret Learning in General GamesNoah Golowich · Adversarial Approaches in Machine Learning 2022
• 12mLearning In The Presence Of Strategic Agents: Dynamics, Equilibria, And ConvergenceEric Mazumdar · Meet the Fellows Welcome Event
• 01h 09mLearning in Games IDrew Fudenberg · Economics and Computation Boot Camp 2015
• 51mMin-max Optimization: From Complexity to AlgorithmsEmmanouil Zampetakis · Adversarial Approaches in Machine Learning 2022
• 01h 06mLearning in Games IIDrew Fudenberg · Economics and Computation Boot Camp 2015