← List all talks ...

Algorithms and computational limits for infinite-horizon general-sum stochastic games

Vidya Muthukumar – Professor, Georgia Tech

Thu, 19-May-2022 / 4:00pm / Packard 101

Abstract

Stochastic games, first introduced by Lloyd Shapley in 1953, are a natural game-theoretic generalization of Markov decision processes. The planning problem for stochastic games — that is, efficiently computing a policy that is a Nash equilibrium for all players in the game — is a fundamental building block for multi-agent reinforcement learning.

In this talk, we provide algorithms and computational limits for finding Nash equilibria (NE) in infinite-horizon, general-sum stochastic games of two types: simultaneous play (SimSG) and turn-based play (TBSG). We prove that computing an approximate stationary NE is PPAD*-complete in the number of states (S) for both SimSG and TBSG. This intractability result for TBSG in particular highlights a surprising separation between the complexity of the planning problem for non-stationary NE (which can be shown to be computable in polynomial-time for TBSG) and stationary NE. Despite the worst-case intractability, we also identify some special cases of general-sum TBSGs for which pure stationary NE always exist and are computable in polynomial time.

This talk will not assume any prior algorithmic game theory or complexity theory knowledge.

*a complexity class for certain types of problems for which a solution is guaranteed to exist. Introduced by Christos Papadimitriou in ’94; believed to be intractable, but easier than NP.

Bio

Vidya Muthukumar is an Assistant Professor in the Schools of Electrical and Computer Engineering and Industrial and Systems Engineering at Georgia Institute of Technology. Her broad interests are in game theory, online and statistical learning. She is particularly interested in designing learning algorithms that provably adapt in strategic environments, fundamental properties of overparameterized models, and algorithmic foundations of multi-agent reinforcement learning.

Vidya received the PhD degree in Electrical Engineering and Computer Sciences from University of California, Berkeley. She is the recipient of the Adobe Data Science Research Award, a Simons-Berkeley-Google Research Fellowship (for the Fall 2020 program on “Theory of Reinforcement Learning”), IBM Science for Social Good Fellowship and a Georgia Tech Class of 1969 Teaching Fellowship for the academic year 2021-2022.