mlsanityData to 7 Oct 2026

Towards General Function Approximation in Zero-Sum Markov Games

arXiv 2107.14702 ↗First posted 30 Jul 2021cs.GT cs.LG stat.MLcited by 42

Not on the map. Why?

Abstract (arXiv)

This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. The study focuses on the challenging settings where the value function or the model is parameterized by general function classes. Provably efficient algorithms for both decoupled and coordinated settings are developed. In the decoupled setting where the agent controls a single player and plays against an arbitrary opponent, we propose a new model-free algorithm. The sample complexity is governed by the Minimax Eluder dimension -- a new dimension of the function class in Markov games. As a special case, this method improves the state-of-the-art algorithm by a √d factor in the regret when the reward function and transition kernel are parameterized with d-dimensional linear features. In the coordinated setting where both players are controlled by the agent, we propose a model-based algorithm and a model-free algorithm. In the model-based algorithm, we prove that sample complexity can be bounded by a generalization of Witness rank to Markov games. The model-free algorithm enjoys a √K-regret upper bound where K is the number of episodes.

Key facts. Cited by 42 papers in the map (data through 7 Oct 2026). Builds on 38 of its 59 references that are in the map. First posted on arXiv 30 Jul 2021.

Builds on

38 of 59 references.

References · 38

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  7. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  8. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  9. 2018Is Q-learning Provably Efficient?cited by 485
  10. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  11. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  12. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
26 more
  1. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  2. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  3. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  7. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  8. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  9. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  10. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  11. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  12. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  13. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  14. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  15. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  16. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  17. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  18. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 42
  19. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  20. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  21. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  22. 2018Actor-Critic Policy Optimization in Partially Observable Multiagent Environmentscited by 35
  23. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  24. 2016Learning Nash Equilibrium for General-Sum Markov Games from Batch Datacited by 20
  25. 2019Exploration-Enhanced POLITEXcited by 8
  26. 2018Balancing Two-Player Stochastic Games with Soft Q-Learningcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 13; 2023: 15; 2024: 8; 2025: 1; 2026: 3.

42 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  3. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  4. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  5. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  6. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  7. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  8. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  9. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  10. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  11. 2021Independent Learning in Stochastic Gamescited by 20
  12. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
30 more
  1. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  2. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  3. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  4. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  5. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  6. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  7. 2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
  8. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  9. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  10. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  11. 2024Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependenciescited by 5
  12. 2022A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Gamescited by 3
  13. 2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
  14. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  15. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  16. 2024Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximationcited by 3
  17. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  18. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  19. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  20. 2022Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibriumcited by 1
  21. 2022Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximationcited by 1
  22. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  23. 2024Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Modelscited by 1
  24. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 1
  25. 2026Multi-agent imitation learning with function approximation: Linear Markov games and beyondcited by 1
  26. 2022Smoothing Policy Iteration for Zero-sum Markov Gamescited by 0
  27. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  28. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0
  29. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  30. 2026Reinforcement Learning: From Algorithms To Foundation Modelscited by 0