Search Mailing List Archives
[theory-seminar] "Algorithms and computational limits for infinite-horizon general-sum stochastic games" – Vidya Muthukumar (Thu, 19-May @ 4:00pm)
kabirc at stanford.edu
Tue May 17 09:09:28 PDT 2022
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:
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
*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.
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
<https://isl.stanford.edu/talks/>. To receive talk announcements, subscribe
to the mailing list isl-colloq at lists.stanford.edu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar