# Learning in Multi-Player Stochastic Games

arXiv: https://arxiv.org/abs/2210.14280 · HTML: https://mlsanity.com/paper/2210.14280/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 37 references that are in the map.
- First posted on arXiv 25 Oct 2022.

## Builds on (most cited first, 8 of 8)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2004.00603/) (2020)
- [Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions](https://mlsanity.com/paper/1303.3055/) (2013)
- [Coarse Correlation in Extensive-Form Games](https://mlsanity.com/paper/1908.09893/) (2019)
- [Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents](https://mlsanity.com/paper/1812.02783/) (2018)
- [Fast Planning in Stochastic Games](https://mlsanity.com/paper/1301.3867/) (2013)

## Abstract (arXiv)

We consider the problem of simultaneous learning in stochastic games with many players in the finite-horizon setting. While the typical target solution for a stochastic game is a Nash equilibrium, this is intractable with many players. We instead focus on variants of it correlated equilibria, such as those studied for extensive-form games. We begin with a hardness result for the adversarial MDP problem: even for a horizon of 3, obtaining sublinear regret against the best non-stationary policy is textsfNP-hard when both rewards and transitions are adversarial. This implies that convergence to even the weakest natural solution concept -- normal-form coarse correlated equilbrium -- is not possible via black-box reduction to a no-regret algorithm even in stochastic games with constant horizon (unless textsfNPsubseteqtextsfBPP). Instead, we turn to a different target: algorithms which it generate an equilibrium when they are used by all players. Our main result is algorithm which generates an it extensive-form correlated equilibrium, whose runtime is exponential in the horizon but polynomial in all other parameters. We give a similar algorithm which is polynomial in all parameters for "fast-mixing" stochastic games. We also show a method for efficiently reaching normal-form coarse correlated equilibria in "single-controller" stochastic games which follows the traditional no-regret approach. When shared randomness is available, the two generative algorithms can be extended to give simultaneous regret bounds and converge in the traditional sense.