Fetching the paper…
Reading the bibliography…
We show that computing approximate stationary Markov coarse correlated equilibria (CCE) in general-sum stochastic games is computationally intractable, even when there are two players, the game is turn-based, the discount factor is an absolute constant, and the approximation is an absolute constant.
Zur Theorie der Gesellschaftsspiele
John von Neumann · 1928
Earlier work this paper cites.
A proof of the equivalence of the programming problem and the game problem
George B. Dantzig · 1951
Earlier work this paper cites.
Stochastic games
Lloyd S Shapley · 1953
Earlier work this paper cites.
Stochastic games with infinitely many strategies
Masayuki Takahashi · 1962
Earlier work this paper cites.
Equilibrium in a stochastic n n -person game
Arlington M. Fink · 1964
Earlier work this paper cites.
Correlated equilibrium as an expression of Bayesian rationality
Robert J Aumann · 1987
Earlier work this paper cites.
A theory of dynamic oligopoly, I: Overview and quantity competition with large fixed costs
Eric Maskin and Jean Tirole · 1988
Earlier work this paper cites.
Nash and correlated equilibria: Some complexity considerations
Itzhak Gilboa and Eitan Zemel · 1989
Earlier work this paper cites.
On algorithms for simple stochastic games
Anne Condon · 1990
Earlier work this paper cites.
On total functions, existence theorems and computational complexity
Nimrod Megiddo and Christos H. Papadimitriou · 1991
Earlier work this paper cites.
The complexity of stochastic games
Anne Condon · 1992
Earlier work this paper cites.
Markov games as a framework for multi-agent reinforcement learning
Michael L. Littman · 1994
Earlier work this paper cites.
On the complexity of the parity argument and other inefficient proofs of existence
Christos H Papadimitriou · 1994
Earlier work this paper cites.
The complexity of mean payoff games on graphs
Uri Zwick and Mike Paterson · 1996
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour · 1999
Earlier work this paper cites.
Friend-or-foe Q-learning in general-sum games
Michael L Littman · 2001
Earlier work this paper cites.
R-max-a general polynomial time algorithm for near-optimal reinforcement learning
Ronen I Brafman and Moshe Tennenholtz · 2002
Earlier work this paper cites.
Approximately optimal approximate reinforcement learning
Sham Kakade and John Langford · 2002
Earlier work this paper cites.
Correlated Q-learning
Amy Greenwald, Keith Hall, Roberto Serrano, et al · 2003
Earlier work this paper cites.
Nash Q-learning for general-sum stochastic games
Junling Hu and Michael P. Wellman · 2003
Earlier work this paper cites.
On the sample complexity of reinforcement learning, 2003
Sham M Kakade · 2003
Earlier work this paper cites.
Stochastic games and applications
Abraham Neyman and Sylvain (editors) Sorin · 2003
Earlier work this paper cites.
On Nash equilibria in stochastic games
Krishnendu Chatterjee, Rupak Majumdar, and Marcin Jurdziński · 2004
Cited alongside, same era.
Cyclic equilibria in Markov games
Martin Zinkevich, Amy Greenwald, and Michael Littman · 2005
Cited alongside, same era.
Prediction, Learning, and Games
Nicolò Cesa-Bianchi and Gabor Lugosi · 2006
Cited alongside, same era.
Computing Nash equilibria: Approximation and smoothed complexity
Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2006
Cited alongside, same era.
A comprehensive survey of multiagent reinforcement learning
Lucian Busoniu, Robert Babuska, and Bart De Schutter · 2008
Cited alongside, same era.
New complexity results about Nash equilibria
Vincent Conitzer and Tuomas Sandholm · 2008
Cited alongside, same era.
PC-PG: Policy cover directed exploration for provable policy gradient learning
Alekh Agarwal, Mikael Henaff, Sham M. Kakade, and Wen Sun · 2020
Later among the works it cites.
Provable self-play algorithms for competitive reinforcement learning
Yu Bai and Chi Jin · 2020
Later among the works it cites.
Near-optimal reinforcement learning with self-play
Yu Bai, Chi Jin, and Tiancheng Yu · 2020
Later among the works it cites.
A short note on learning discrete distributions
Clément L. Canonne · 2020
Later among the works it cites.
Independent policy gradient methods for competitive reinforcement learning
Constantinos Daskalakis, Dylan Foster, and Noah Golowich · 2020
Later among the works it cites.
Reward-free exploration for reinforcement learning
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu · 2020
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Computing correlated equilibria in multi-player games
Christos H Papadimitriou and Tim Roughgarden · 2008
Cited alongside, same era.
Settling the complexity of computing two-player Nash equilibria
Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2009
Cited alongside, same era.
The complexity of computing a nash equilibrium
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou · 2009
Cited alongside, same era.
On the complexity of Nash equilibria and other fixed points
Kousha Etessami and Mihalis Yannakakis · 2010
Cited alongside, same era.
Regret analysis of stochastic and nonstochastic multi-armed bandit problems
Sébastien Bubeck and Nicolo Cesa-Bianchi · 2012
Cited alongside, same era.
Can almost everybody be almost happy? PCP for PPAD and the inapproximability of Nash
Yakov Babichenko, Christos Papadimitriou, and Aviad Rubinstein · 2015
Cited alongside, same era.
Bandit Algorithms
Tor Lattimore and Csaba Szepesvári · 2020
Later among the works it cites.
Solving discounted stochastic two-player games with near-optimal time and sample complexity
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye · 2020
Later among the works it cites.
Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang · 2020
Later among the works it cites.
Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity
Kaiqing Zhang, Sham M. Kakade, Tamer Basar, and Lin F. Yang · 2020
Later among the works it cites.
The ai economist: Improving equality and productivity with ai-driven tax policies, 2020
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C. Parkes, and Richard Socher · 2020
Later among the works it cites.
On the complexity of computing Markov perfect equilibrium in general-sum stochastic games
Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, and Yaodong Yang · 2021
Later among the works it cites.
The statistical complexity of interactive decision making
Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin · 2021
Later among the works it cites.
V-learning–A simple, efficient, decentralized algorithm for multiagent RL
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu · 2021
Later among the works it cites.
A sharp analysis of model-based reinforcement learning with self-play
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin · 2021
Later among the works it cites.
Provably efficient reinforcement learning in decentralized general-sum Markov games
Weichao Mao and Tamer Başar · 2021
Later among the works it cites.
When can we learn general-sum Markov games with a large number of players sample-efficiently?
Ziang Song, Song Mei, and Yu Bai · 2021
Later among the works it cites.
Decentralized Q-learning in zero-sum Markov games
Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar · 2021
Later among the works it cites.
Multi-agent reinforcement learning: A selective overview of theories and algorithms
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar · 2021
Later among the works it cites.
When is offline two-player zero-sum Markov game solvable?
Qiwen Cui and Simon S Du · 2022
Closest in time.
Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets
Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang · 2022
Closest in time.