# Feature-Based Q-Learning for Two-Player Stochastic Games

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2019.

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

- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [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)
- [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)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [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)
- [Representation Learning for General-sum Low-rank Markov Games](https://mlsanity.com/paper/2210.16976/) (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)
- [On the Model-Misspecification in Reinforcement Learning](https://mlsanity.com/paper/2306.10694/) (2023)
- [Gap-Dependent Bounds for Two-Player Markov Games](https://mlsanity.com/paper/2107.00685/) (2021)
- [Minimax-Optimal Multi-Agent Robust Reinforcement Learning](https://mlsanity.com/paper/2412.19873/) (2024)
- [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)
- [Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2208.05363/) (2022)
- [Agent-Specific Effects: A Causal Effect Propagation Analysis in Multi-Agent MDPs](https://mlsanity.com/paper/2310.11334/) (2023)
- [A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games](https://mlsanity.com/paper/2303.09716/) (2023)
- [Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games](https://mlsanity.com/paper/2308.08858/) (2023)
- [Zero-sum turn games using Q-learning: finite computation with security guarantees](https://mlsanity.com/paper/2509.13585/) (2025)

## Abstract (arXiv)

Consider a two-player zero-sum stochastic game where the transition function can be embedded in a given feature space. We propose a two-player Q-learning algorithm for approximating the Nash equilibrium strategy via sampling. The algorithm is shown to find an ε-optimal strategy using sample size linear to the number of features. To further improve its sample efficiency, we develop an accelerated algorithm by adopting techniques such as variance reduction, monotonicity preservation and two-sided strategy approximation. We prove that the algorithm is guaranteed to find an ε-optimal strategy using no more than tildeO(K/(ε2(1-γ)4)) samples with high probability, where K is the number of features and γ is a discount factor. The sample, time and space complexities of the algorithm are independent of original dimensions of the game.