Research map / Multi-agent systems and games / Games and equilibria
Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes VMG, a model-based online MARL method that regularizes the MLE/least-squares model estimate toward models with high best-response values, achieving near-optimal regret for matrix games and Markov games under linear function approximation without explicit bonuses.
Problem
Sample-efficient exploration for finding Nash equilibria of two-player zero-sum Markov games and coarse correlated equilibria of multi-player general-sum Markov games under function approximation, without tailored uncertainty quantification or coordinated updates.
Approach
Value-incentivized exploration: the model estimate is biased (via a reward-biased regularizer) toward models that maximize the sum of players' best-response values at the current equilibrium, so policies deviate from equilibrium for exploration; this needs no bonus term, allows simultaneous uncoupled updates, and works with linear function approximation.
Key results
- For two-player zero-sum matrix games with linear payoff, VMG achieves regret Õ(d√T), giving Õ(d²/ε²) sample complexity for ε-NE.
- For multi-player general-sum Markov games under linear mixture model, VMG achieves regret Õ(d√(H³T)), i.e., Õ(N d² H³/ε²) trajectories for ε-CCE, near-optimal up to a factor of H.
- Regret bound matches MEX's for the max player in two-player zero-sum Markov games while also covering the min player.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use value-incentivized model updates that maximize players' best-response values | VMG for two-player zero-sum matrix games · Two-player zero-sum matrix games with linear function approximation | regret | Helped |
| use value-incentivized model updates that maximize players' best-response values | VMG for multi-player general-sum Markov games · Finite-horizon multi-player general-sum Markov games with a linear mixture transition model | regret | Helped |
Limitations
- Theory restricted to linear function approximation (linear payoff for matrix games, linear mixture model for transitions); general function approximation left open.
- Computing NE in general-sum Markov games is intractable, so the general-sum result targets CCE.
- Sample complexity is near-optimal only up to a factor of H and depends on fixed number of players N.
Experimental setup
Metrics: regret duality gap sub-optimality gap sample complexity
Baselines: MEX
Builds on: MEX reward-biased maximum likelihood estimation optimism in the face of uncertainty
Closest papers by meaning
- Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model (NeurIPS 2022 · similarity 0.93)
- Sample-Efficient Multi-Agent RL: An Optimization Perspective (ICLR 2024 · similarity 0.92)
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games (ICML 2024 · similarity 0.91)
- Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.90)
- Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty (ICML 2024 · similarity 0.90)
- Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.