# Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2019.

## Built on by (most cited first, 30 of 42)

- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [When is Offline Two-Player Zero-Sum Markov Game Solvable?](https://mlsanity.com/paper/2201.03522/) (2022)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Independent Learning in Stochastic Games](https://mlsanity.com/paper/2111.11743/) (2021)
- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games](https://mlsanity.com/paper/2109.01795/) (2021)
- [Policy Optimization for Markov Games: Unified Framework and Faster Convergence](https://mlsanity.com/paper/2206.02640/) (2022)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2209.12430/) (2022)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2307.07670/) (2023)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [Can We Find Nash Equilibria at a Linear Rate in Markov Games?](https://mlsanity.com/paper/2303.03095/) (2023)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent](https://mlsanity.com/paper/2109.03396/) (2021)
- [Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games](https://mlsanity.com/paper/2112.07859/) (2021)
- [Population-size-Aware Policy Optimization for Mean-Field Games](https://mlsanity.com/paper/2302.03364/) (2023)

## Abstract (arXiv)

In this paper, we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with discount factor γ∈(0,1) we provide an algorithm that computes an ε-optimal strategy with high-probability given tildeO((1 - γ)-3 ε-2) samples from the transition function for each state-action-pair. Our algorithm runs in time nearly linear in the number of samples and uses space nearly linear in the number of state-action pairs. As stochastic games generalize Markov decision processes (MDPs) our runtime and sample complexities are optimal due to Azar et al (2013). We achieve our results by showing how to generalize a near-optimal Q-learning based algorithms for MDP, in particular Sidford et al (2018), to two-player strategy computation algorithms. This overcomes limitations of standard Q-learning and strategy iteration or alternating minimization based approaches and we hope will pave the way for future reinforcement learning results by facilitating the extension of MDP results to multi-agent settings with little loss.