mlsanityData to 7 Oct 2026

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

arXiv 1906.00423 ↗First posted 2 Jun 2019cs.LG cs.GT stat.MLcited by 23

Not on the map. Why?

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.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 9; 2022: 6; 2023: 6; 2024: 2.

23 papers.

Sort:

  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  3. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  4. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  5. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  6. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  7. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  8. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  9. 2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 18
  10. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  11. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  12. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
11 more
  1. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  2. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  3. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5
  4. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
  5. 2024Minimax-Optimal Multi-Agent Robust Reinforcement Learningcited by 4
  6. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3
  7. 2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
  8. 2022Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibriumcited by 1
  9. 2023Agent-Specific Effects: A Causal Effect Propagation Analysis in Multi-Agent MDPscited by 1
  10. 2023A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Gamescited by 0
  11. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0