# Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty

arXiv: https://arxiv.org/abs/2404.18909 · HTML: https://mlsanity.com/paper/2404.18909/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 59 of its 144 references that are in the map.
- First posted on arXiv 29 Apr 2024.

## Builds on (most cited first, 30 of 59)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [SMART-LLM: Smart Multi-Agent Robot Task Planning using Large Language Models](https://mlsanity.com/paper/2309.10062/) (2023)
- [Robust Reinforcement Learning on State Observations with Learned Optimal Adversary](https://mlsanity.com/paper/2101.08452/) (2021)
- [SMARTS: Scalable Multi-Agent Reinforcement Learning Training School for Autonomous Driving](https://mlsanity.com/paper/2010.09776/) (2020)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Robust Reinforcement Learning for Continuous Control with Model Misspecification](https://mlsanity.com/paper/1906.07516/) (2019)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Distributionally Robust Optimization: A Review](https://mlsanity.com/paper/1908.05659/) (2019)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [SustainBench: Benchmarks for Monitoring the Sustainable Development Goals with Machine Learning](https://mlsanity.com/paper/2111.04724/) (2021)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality](https://mlsanity.com/paper/2009.04382/) (2020)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023)
- [Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/1902.08708/) (2019)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [Soft-Robust Actor-Critic Policy-Gradient](https://mlsanity.com/paper/1803.04848/) (2018)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)

## Built on by (most cited first, 25 of 25)

- [Distributionally Robust Constrained Reinforcement Learning under Strong Duality](https://mlsanity.com/paper/2406.15788/) (2024)
- [Contextual Bilevel Reinforcement Learning for Incentive Alignment](https://mlsanity.com/paper/2406.01575/) (2024)
- [Wolfpack Adversarial Attack for Robust Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2502.02844/) (2025)
- [The Bandit Whisperer: Communication Learning for Restless Bandits](https://mlsanity.com/paper/2408.05686/) (2024)
- [Minimax-Optimal Multi-Agent Robust Reinforcement Learning](https://mlsanity.com/paper/2412.19873/) (2024)
- [Tractable Equilibrium Computation in Markov Games through Risk Aversion](https://mlsanity.com/paper/2406.14156/) (2024)
- [Divide-Fuse-Conquer: Eliciting "Aha Moments" in Multi-Scenario Games](https://mlsanity.com/paper/2505.16401/) (2025)
- [Distributionally Robust Multi-Agent Reinforcement Learning for Dynamic Chute Mapping](https://mlsanity.com/paper/2503.09755/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Training Generalizable Collaborative Agents via Strategic Risk Aversion](https://mlsanity.com/paper/2602.21515/) (2026)
- [Towards Fault Tolerance in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.00534/) (2024)
- [Empirical Study on Robustness and Resilience in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2510.11824/) (2025)
- [Distributionally Robust Online Markov Game with Linear Function Approximation](https://mlsanity.com/paper/2511.07831/) (2025)
- [Robust Verification of Concurrent Stochastic Games](https://mlsanity.com/paper/2601.12003/) (2026)
- [EvoNash-MARL: A Closed-Loop Multi-Agent Reinforcement Learning Framework for Medium-Horizon Equity Allocation](https://mlsanity.com/paper/2604.10911/) (2026)
- [Vulnerable Agent Identification in Large-Scale Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.15103/) (2025)
- [Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorization](https://mlsanity.com/paper/2602.11437/) (2026)
- [Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2603.09208/) (2026)
- [The Price of Paranoia: Robust Risk-Sensitive Cooperation in Non-Stationary Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2604.15695/) (2026)
- [Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation](https://mlsanity.com/paper/2605.03125/) (2026)
- [Stationary Robust Mean-Field Games under Model Mismatches](https://mlsanity.com/paper/2606.22579/) (2026)
- [IDEA: Insensitive to Dynamics Mismatch via Effect Alignment for Sim-to-Real Transfer in Multi-Agent Control](https://mlsanity.com/paper/2606.26575/) (2026)
- [Robust PAC Learning of Concurrent Stochastic Games](https://mlsanity.com/paper/2609.04189/) (2026)
- [Social Laws for Multi-agent Coordination in Stochastic Environments](https://mlsanity.com/paper/2609.18929/) (2026)
- [Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation](https://mlsanity.com/paper/2609.32048/) (2026)

## Abstract (arXiv)

To overcome the sim-to-real gap in reinforcement learning (RL), learned policies must maintain robustness against environmental uncertainties. While robust RL has been widely studied in single-agent regimes, in multi-agent environments, the problem remains understudied -- despite the fact that the problems posed by environmental uncertainties are often exacerbated by strategic interactions. This work focuses on learning in distributionally robust Markov games (RMGs), a robust variant of standard Markov games, wherein each agent aims to learn a policy that maximizes its own worst-case performance when the deployed environment deviates within its own prescribed uncertainty set. This results in a set of robust equilibrium strategies for all agents that align with classic notions of game-theoretic equilibria. Assuming a non-adaptive sampling mechanism from a generative model, we propose a sample-efficient model-based algorithm (DRNVI) with finite-sample complexity guarantees for learning robust variants of various notions of game-theoretic equilibria. We also establish an information-theoretic lower bound for solving RMGs, which confirms the near-optimal sample complexity of DRNVI with respect to problem-dependent factors such as the size of the state space, the target accuracy, and the horizon length.