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 stanford.edu
Thu May 19 09:30:19 PDT 2022


Hi All,

Unfortunately this talk has been postponed due to unforeseen
circumstances.

Thanks,
Kabir

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

> 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:
> https://stanford.zoom.us/meeting/register/tJckfuCurzkvEtKKOBvDCrPv3McapgP6HygJ
> <https://stanford.zoom.us/meeting/register/tJckfuCurzkvEtKKOBvDCrPv3McapgP6HygJ>
> *
> 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
> <https://isl.stanford.edu/talks/>. To receive talk announcements, subscribe
> to the mailing list isl-colloq at lists.stanford.edu
> <https://mailman.stanford.edu/mailman/listinfo/isl-colloq>.*
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220519/36c156ff/attachment.html>


More information about the theory-seminar mailing list