Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] "Algorithms and computational limits for infinite-horizon general-sum stochastic games" – Vidya Muthukumar (Thu, 19-May @ 4:00pm)

Kabir Chandrasekher kabirc at
Thu May 19 09:30:19 PDT 2022

Hi All,

Unfortunately this talk has been postponed due to unforeseen


On Tue, May 17, 2022 at 9:09 AM Kabir Chandrasekher <kabirc at>

> Algorithms and computational limits for infinite-horizon general-sum
> stochastic games Vidya Muthukumar – Professor, Georgia Tech
> Thu, 19-May / 4:00pm / Packard 101 (in person)
> * Please join us for coffee and snacks at 3:30pm in the Grove outside
> Packard (near Bytes' outdoor seating). The talk will be streamed on Zoom
> for those unable to attend in person:
> <>
> *
> 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.
> *This talk is hosted by the ISL Colloquium
> <>. To receive talk announcements, subscribe
> to the mailing list isl-colloq at
> <>.*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list