Research map / Bandits and online learning / Online convex optimization and games
When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Nash-V-Learning with a certified policy to target ε-CCE | General-sum Markov games · ε-CCE | episodes: \widetilde{\mathcal{O}}(H^5S\max_{i\le m} A_i / \varepsilon^2) | Helped |
| Integrate an adversarial bandit subroutine minimizing weighted swap regret with novel outer-loop designs | CE learning algorithm · General-sum Markov games, ε-CE | episodes: \widetilde{\mathcal{O}}(H^6S\max_{i\le m} A_i^2 / \varepsilon^2) | Helped |
| Use best-response updates guided by estimated Nash gaps under the Markov potential-game structure | Markov Potential Games · ε-approximate Nash equilibrium | episodes: \widetilde{\mathcal{O}}(S\sum_{i\le m} A_i / \varepsilon^3) | Helped |
| Seek an approximate Nash equilibrium in unrestricted general-sum Markov games | General-sum Markov games · Approximate Nash equilibrium | episodes: 2^{\Omega(m/\log m)} | Hurt |
| Require the learned equilibrium to be pure in stochastic matrix games | Online finetuning algorithms · General-sum stochastic matrix games, pure ε-Nash | samples: c_0 \frac{\sum_{i=1}^m A_i}{\varepsilon^2} | Hurt |
Closest papers by meaning
- Improved Sample Complexity for Markov Games via Variance-Aware Bandit Learning (NeurIPS 2026 · similarity 0.95)
- 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)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.90)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.90)
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.