Research map / Multi-agent systems and games / Games and equilibria
Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning
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 fictitious robust Markov games with others-integrated (s,a_i)-rectangular TV uncertainty sets and the Robust-Q-FTRL algorithm, which learns a robust CCE with a generative model using sample complexity linear in the sum of action sizes rather than their product.
Problem
Robust multi-agent RL with distributionally robust Markov games suffers from the curse of multiagency (sample complexity exponential in number of agents), and existing uncertainty set formulations use (s,a)-rectangularity that may not reflect realistic human decision-making.
Approach
Defines fictitious uncertainty sets where each agent's uncertainty ball is centered on the expected nominal kernel induced by other agents' policies (others-integrated (s,a_i)-rectangularity), proves existence of robust NE/CCE, and adapts Q-FTRL with adaptive sampling, dual-form robust Bellman updates, and a variance-style bonus to break the curse of multiagency.
Key results
- Robust-Q-FTRL finds an epsilon-robust CCE with sample complexity O~(S H^6 sum_i A_i / eps^4 * min{H, 1/min sigma_i}), linear in sum of action sizes rather than product.
- A minimax lower bound of order S H^3 max_i A_i / eps^2 * min{H, 1/min sigma_i} is established for a sub-class of the fictitious RMGs.
- Existence of robust NE and robust CCE is proven for fictitious RMGs via Kakutani's fixed-point theorem.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Robust-Q-FTRL with fictitious (s,a_i)-rectangular uncertainty sets and adaptive sampling | Robust Markov games · Fictitious RMGs (TV uncertainty) | sample complexity: \widetilde{O}\left(\frac{S H^6 \sum_{1\leq i\leq n}A_i }{\epsilon^4} \min\left\{ H, \frac{1}{\min_{1\leq i\leq n}\sigma_ | Helped |
| Replace the product dependence on agents' action-space sizes with a sum dependence | Robust CCE learning in robust Markov games · Fictitious RMGs versus prior (s,a)-rectangular RMGs | sample complexity: \widetilde{O} \left(\frac{SH^3 \prod_{i=1}^n A_i }{ \varepsilon^2} \min \Big\{H, ~\frac{1}{\min_{1\leq i\leq n} \sigma_i | Helped |
Limitations
- Gap between upper and lower bounds in horizon H and accuracy eps (upper bound eps^-4 vs lower bound eps^-2).
- Requires access to a generative model of the nominal environment.
- Results are theoretical with no empirical experiments.
Experimental setup
Metrics: sample complexity CCE gap
Baselines: P2MPO DR-NVI Q-FTRL (standard MG)
Builds on: Q-FTRL V-learning distributionally robust MDPs with (s,a)-rectangularity Kakutani fixed-point theorem
Closest papers by meaning
- Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation (NeurIPS 2026 · similarity 0.95)
- Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty (ICML 2024 · similarity 0.93)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.90)
- Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
- Empirical Study on Robustness and Resilience in Cooperative Multi-Agent Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
- Byzantine Robust Cooperative Multi-Agent Reinforcement Learning as a Bayesian Game (ICLR 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.