mlsanityData to 14 Oct 2026

The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces

arXiv 2106.03352 ↗First posted 7 Jun 2021cs.LG cs.AI stat.MLcited by 48

Not on the map. Why?

Abstract (arXiv)

Modern reinforcement learning (RL) commonly engages practical problems with large state spaces, where function approximation must be deployed to approximate either the value function or the policy. While recent progresses in RL theory address a rich set of RL problems with general function approximation, such successes are mostly restricted to the single-agent setting. It remains elusive how to extend these results to multi-agent RL, especially due to the new challenges arising from its game-theoretical nature. This paper considers two-player zero-sum Markov Games (MGs). We propose a new algorithm that can provably find the Nash equilibrium policy using a polynomial number of samples, for any MG with low multi-agent Bellman-Eluder dimension -- a new complexity measure adapted from its single-agent version (Jin et al., 2021). A key component of our new algorithm is the exploiter, which facilitates the learning of the main player by deliberately exploiting her weakness. Our theoretical framework is generic, which applies to a wide range of models including but not limited to tabular MGs, MGs with linear or kernel function approximation, and MGs with rich observations.

Key facts. Cited by 48 papers in the map (data through 14 Oct 2026). Builds on 39 of its 69 references that are in the map. First posted on arXiv 7 Jun 2021.

Builds on

39 of 69 references.

References · 39

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  2. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  3. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 942
  4. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 708
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  6. 2018Is Q-learning Provably Efficient?cited by 487
  7. 2019Emergent Tool Use From Multi-Agent Autocurriculacited by 313
  8. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  9. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  10. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  11. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  12. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
27 more
  1. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  3. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  6. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  7. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  8. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  9. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  10. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  11. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  12. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  13. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
  14. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  15. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  16. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  17. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  18. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  19. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  20. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
  21. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 37
  22. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 24
  23. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 22
  24. 2021Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibriumcited by 22
  25. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  26. 2020Multi-Agent Trust Region Policy Optimizationcited by 20
  27. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 14; 2023: 14; 2024: 8; 2025: 1; 2026: 5.

48 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
  2. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  3. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHFcited by 73
  4. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  5. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  6. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  7. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
  8. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 43
  9. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
  10. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  11. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 27
  12. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
36 more
  1. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  2. 2021Independent Learning in Stochastic Gamescited by 22
  3. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  4. 2023Offline Learning in Markov Games with General Function Approximationcited by 18
  5. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  6. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  7. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 16
  8. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 15
  9. 2022Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computationcited by 14
  10. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 14
  11. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 14
  12. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12
  13. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  14. 2024Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependenciescited by 6
  15. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  16. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 4
  17. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 4
  18. 2022A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Gamescited by 3
  19. 2023Population-size-Aware Policy Optimization for Mean-Field Gamescited by 3
  20. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 3
  21. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  22. 2024Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscited by 3
  23. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  24. 2021Online Sub-Sampling for Reinforcement Learning with General Function Approximationcited by 1
  25. 2022Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibriumcited by 1
  26. 2022Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximationcited by 1
  27. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  28. 2024Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Modelscited by 1
  29. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  30. 2026Bayesian Learning in Episodic Zero-Sum Gamescited by 1
  31. 2023A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Gamescited by 0
  32. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  33. 2024RL in Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Modelcited by 0
  34. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  35. 2026Minimax-Optimal Policy Regret in Partially Observable Markov Gamescited by 0
  36. 2026Reinforcement Learning: From Algorithms To Foundation Modelscited by 0