# Minimax Sample Complexity for Turn-based Stochastic Game

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2020.

## Built on by (most cited first, 13 of 13)

- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [When is Offline Two-Player Zero-Sum Markov Game Solvable?](https://mlsanity.com/paper/2201.03522/) (2022)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Optimal Attack and Defense for Reinforcement Learning](https://mlsanity.com/paper/2312.00198/) (2023)
- [Off-the-Grid MARL: Datasets with Baselines for Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2302.00521/) (2023)
- [Online Sub-Sampling for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2106.07203/) (2021)
- [Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2208.05363/) (2022)
- [Offline congestion games: How feedback type affects data coverage requirement](https://mlsanity.com/paper/2210.13396/) (2022)
- [Double Thompson Sampling in Finite stochastic Games](https://mlsanity.com/paper/2202.10008/) (2022)

## Abstract (arXiv)

The empirical success of Multi-agent reinforcement learning is encouraging, while few theoretical guarantees have been revealed. In this work, we prove that the plug-in solver approach, probably the most natural reinforcement learning algorithm, achieves minimax sample complexity for turn-based stochastic game (TBSG). Specifically, we plan in an empirical TBSG by utilizing a `simulator' that allows sampling from arbitrary state-action pair. We show that the empirical Nash equilibrium strategy is an approximate Nash equilibrium strategy in the true TBSG and give both problem-dependent and problem-independent bound. We develop absorbing TBSG and reward perturbation techniques to tackle the complex statistical dependence. The key idea is artificially introducing a suboptimality gap in TBSG and then the Nash equilibrium strategy lies in a finite set.