Research map / Multi-agent systems and games / Games and equilibria
Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty
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 DR-NVI, a model-based generative-model algorithm for distributionally robust Markov games with TV uncertainty sets, giving near-optimal finite-sample complexity for robust NE, CE and CCE, plus a matching-order information-theoretic lower bound.
Problem
Learning robust equilibria (NE, CE, CCE) in multi-agent general-sum Markov games whose transition kernels are uncertain, with sample-efficient guarantees under a generative model and non-adaptive sampling.
Approach
Extends Nash value iteration to distributionally robust Markov games with agent-wise (s,a)-rectangular TV uncertainty sets, using the strong-duality dual form of the robust Bellman operator; the resulting sample complexity scales with the joint action size and with min(H, 1/min sigma_i), and a new lower bound shows near-optimality.
Key results
- DR-NVI finds epsilon-approximate robust NE, CCE, or CE with sample size O~(S H^3 prod A_i / eps^2 * min{H, 1/min sigma_i}), improving prior robust MARL bounds by a factor of at least O~(S^3 (prod A_i)^2).
- An information-theoretic lower bound of order S H^3 max_i A_i / eps^2 * min{H, 1/min sigma_i} is established for solving RMGs, the first such bound for RMGs.
- When the action space is reduced to one agent, the bound matches minimax-optimal sample complexity for finite-horizon RMDPs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DR-NVI instead of prior-art methods for robust Markov games | Robust Markov games with generative-model sampling · Robust Markov games | sample complexity: by at least a factor of \widetilde{O}\big(S^3 \left(\prod_{i=1}^n A_i\right)^2\big) | Helped |
| Use DR-NVI rather than NVI for standard Markov games when the minimum uncertainty level is at least on the order of 1/H | Markov games under non-adaptive generative-model sampling · Robust versus standard Markov games | sample complexity: by a factor of H \min_{1\leq i\leq n} \sigma_i | Helped |
| Use DR-NVI when the minimum uncertainty level is at most on the order of 1/H | Markov games under non-adaptive generative-model sampling · Robust versus standard Markov games | sample complexity dependence on H: H^4 | No clear effect |
| Increase the minimum agent uncertainty level when it is at least on the order of 1/H | DR-NVI · Robust Markov games | sample complexity: H^3 | Helped |
| Use DR-NVI in the single-agent special case | Robust Markov decision process · Finite-horizon robust MDP | sample complexity | Helped |
| Use a robust equilibrium rather than the standard-game equilibrium in the fishing-protection example | Fishing-protection game · City A and city B environments | equilibrium policy consistency: p=0.049; p=0.051; σ =0.005 | Helped |
Surprising findings
- Robust MGs can require no more samples than standard MGs under non-adaptive sampling when min sigma_i is at least about 1/H.
Limitations
- Analysis restricted to tabular setting with generative model and non-adaptive sampling
- Only TV distance uncertainty sets with agent-wise (s,a)-rectangularity considered
- Sample complexity scales with product of action sizes (curse of multiple agents)
Experimental setup
Datasets: samples from a generative model of the nominal MG (synthetic)
Metrics: epsilon-robust NE gap epsilon-robust CCE gap epsilon-robust CE gap sample complexity
Baselines: NVI for standard Markov games prior robust MARL finite-sample algorithm (S^4 (prod A_i)^3 H^4 / eps^2)
Builds on: Nash value iteration robust Markov decision processes with TV uncertainty distributionally robust dynamic programming
Closest papers by meaning
- Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.93)
- Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation (NeurIPS 2026 · similarity 0.92)
- Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms (NeurIPS 2024 · similarity 0.91)
- Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.90)
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · 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.