mlsanityData to 7 Oct 2026

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

arXiv 1908.11071 ↗First posted 29 Aug 2019cs.LG cs.DS stat.MLcited by 41

Not on the map. Why?

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.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Aug 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 12; 2023: 11; 2024: 0; 2025: 0; 2026: 3.

41 papers.

Sort:

By area:

  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  3. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  4. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  5. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  6. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  7. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  8. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  9. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  10. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  11. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  12. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
29 more
  1. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  2. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  3. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  4. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  5. 2021Independent Learning in Stochastic Gamescited by 20
  6. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  7. 2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 18
  8. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  9. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  10. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  11. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  12. 2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
  13. 2023Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learningcited by 9
  14. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  15. 2023The complexity of non-stationary reinforcement learningcited by 7
  16. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
  17. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3
  18. 2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
  19. 2023Local and adaptive mirror descents in extensive-form gamescited by 2
  20. 2021Online Sub-Sampling for Reinforcement Learning with General Function Approximationcited by 1
  21. 2022Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibriumcited by 1
  22. 2022Offline congestion games: How feedback type affects data coverage requirementcited by 1
  23. 2023Agent-Specific Effects: A Causal Effect Propagation Analysis in Multi-Agent MDPscited by 1
  24. 2026Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptationcited by 1
  25. 2023Decentralized model-free reinforcement learning in stochastic games with average-reward objectivecited by 0
  26. 2023A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Gamescited by 0
  27. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  28. 2026Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitionscited by 0
  29. 2026Bayesian Learning in Episodic Zero-Sum Gamescited by 0