Research map / Multi-agent systems and games / Games and equilibria
Sample-Efficient Multi-Agent RL: An Optimization Perspective
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 MAMEX, a unified model-free and model-based framework for learning NE/CCE/CE in general-sum Markov games under general function approximation, governed by a new Multi-Agent Decoupling Coefficient (MADC).
Problem
Sample-efficient multi-agent RL in general-sum Markov games with general function approximation for learning Nash, coarse correlated, and correlated equilibria, where single-agent and zero-sum optimization tricks do not carry over.
Approach
Extends Maximize-to-Explore to general-sum games by computing, for each deterministic joint policy, a regularized single-objective optimistic payoff over the hypothesis class, then solving a normal-form equilibrium over the policy space; the complexity measure MADC generalizes the decoupling coefficient to multi-agent settings.
Key results
- MAMEX achieves Õ(nH√K Υ + n d_MADC √K + n d_MADC H) regret for NE/CCE/CE under general function approximation.
- Multi-agent BE dimension d implies MADC O(dH log K), giving Õ(ndH√K) regret for the model-free version.
- Multi-agent bilinear classes with information gain γ_K give MADC ≤ max{1, 8R²γ_K}; linear Bellman complete MGs get Õ(ndHR²√K + nHR²√K log|Π^pur| + ndH²) regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MAMEX under finite MADC | General-sum MGs with general function approximation · NE/CCE/CE learning | regret: \widetilde{\cO}\Big(nH\sqrt{K}\Upsilon_{\cF,\delta} + nd_{\mathrm{MADC}}\sqrt{K}+nd_{\mathrm{MADC}}H \Big ) | Helped |
| Use MAMEX for MGs with finite multi-agent BE dimension d | General-sum MGs · NE/CCE/CE learning | regret: \tilde{\cO}(ndH\sqrt{K} + ndH^2 + nHR^2\sqrt{K}\log \Upsilon_{\cF,\delta}) | Helped |
| Use a log-linear policy class with a policy cover | MAMEX on linear Bellman complete MGs · NE/CCE/CE learning | regret: \widetilde{\cO}((nd+n^2d_\pi)HR^2\sqrt{K} + ndH^2) | Mixed |
| Use a log-linear policy class with a policy cover | MAMEX on zero-sum linear MGs · NE/CCE/CE learning | regret: \widetilde{\cO}((d+d_\pi) H^3 \sqrt{K}) | Mixed |
Limitations
- Regret depends on log|Π^pur| in the model-free setting, an extra factor over single-agent results.
- Purely theoretical; no empirical experiments reported in the provided text.
- Requires realizability and completeness assumptions and finite MADC.
Experimental setup
Metrics: Nash regret CCE regret CE regret sample complexity
Baselines: Nash-VI CCE-VI V-learning Multi-agent DEC-based algorithms
Builds on: Maximize-to-Explore Decision-Estimation Coefficient Bellman eluder dimension bilinear classes witness rank
Closest papers by meaning
- Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity (NeurIPS 2020 · similarity 0.93)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.92)
- When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? (ICLR 2022 · similarity 0.92)
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games (ICML 2024 · similarity 0.91)
- Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints (ICML 2024 · similarity 0.89)
- Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning (ICLR 2024 · similarity 0.88)
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.