Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Not on the map. Why?
Abstract (arXiv)
Multi-agent reinforcement learning (MARL) lies at the heart of a plethora of applications involving the interaction of a group of agents in a shared unknown environment. A prominent framework for studying MARL is Markov games, with the goal of finding various notions of equilibria in a sample-efficient manner, such as the Nash equilibrium (NE) and the coarse correlated equilibrium (CCE). However, existing sample-efficient approaches either require tailored uncertainty estimation under function approximation, or careful coordination of the players. In this paper, we propose a novel model-based algorithm, called VMG, that incentivizes exploration via biasing the empirical estimate of the model parameters towards those with a higher collective best-response values of all the players when fixing the other players' policies, thus encouraging the policy to deviate from its current equilibrium for more exploration. VMG is oblivious to different forms of function approximation, and permits simultaneous and uncoupled policy updates of all players. Theoretically, we also establish that VMG achieves a near-optimal regret for finding both the NEs of two-player zero-sum Markov games and CCEs of multi-player general-sum Markov games under linear function approximation in an online environment, which nearly match their counterparts with sophisticated uncertainty quantification.
Key facts. Cited by 2 papers in the map (data through 13 Oct 2026). Builds on 44 of its 61 references that are in the map. First posted on arXiv 13 Feb 2025.
Builds on
44 of 61 references.
References · 44
- 2021A Survey of Uncertainty in Deep Neural Networkscited by 676
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 515
- 2018Is Q-learning Provably Efficient?cited by 485
- 2017A Tutorial on Thompson Samplingcited by 423
- 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 260
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
- 2023Nash Learning from Human Feedbackcited by 223
- 2019Provably Efficient Exploration in Policy Optimizationcited by 204
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
- 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 142
- 2017Cycles in adversarial regularized learningcited by 122
- 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 113
32 more
- 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
- 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
- 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
- 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
- 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
- 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHFcited by 73
- 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 66
- 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
- 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 62
- 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 45
- 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
- 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
- 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
- 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
- 2018Variational Bayesian Reinforcement Learning with Regret Boundscited by 31
- 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
- 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
- 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 26
- 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
- 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 23
- 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
- 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
- 2020Matrix games with bandit feedbackcited by 14
- 2022Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computationcited by 14
- 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
- 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 12
- 2020Reward Biased Maximum Likelihood Estimation for Reinforcement Learningcited by 11
- 2023Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learningcited by 11
- 2020Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Banditscited by 9
- 2024Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignmentcited by 9
- 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
Built on by
Citing papers per year: 2026: 2.
2 papers.