# Minimax-Optimal Multi-Agent Robust Reinforcement Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 76 references that are in the map.
- First posted on arXiv 27 Dec 2024.

## Builds on (most cited first, 15 of 15)

- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [SMART-LLM: Smart Multi-Agent Robot Task Planning using Large Language Models](https://mlsanity.com/paper/2309.10062/) (2023)
- [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)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [SustainBench: Benchmarks for Monitoring the Sustainable Development Goals with Machine Learning](https://mlsanity.com/paper/2111.04724/) (2021)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Feature-Based Q-Learning for Two-Player Stochastic Games](https://mlsanity.com/paper/1906.00423/) (2019)
- [What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?](https://mlsanity.com/paper/2212.02705/) (2022)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [DeepRacer: Educational Autonomous Racing Platform for Experimentation with Sim2Real Reinforcement Learning](https://mlsanity.com/paper/1911.01562/) (2019)
- [Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games](https://mlsanity.com/paper/2206.04044/) (2022)
- [O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2209.12430/) (2022)
- [Robust Markov Decision Processes without Model Estimation](https://mlsanity.com/paper/2302.01248/) (2023)
- [Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2409.20067/) (2024)

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

- [Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality](https://mlsanity.com/paper/2508.17448/) (2025)
- [Distributionally Robust Online Markov Game with Linear Function Approximation](https://mlsanity.com/paper/2511.07831/) (2025)
- [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)
- [Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation](https://mlsanity.com/paper/2609.32048/) (2026)

## Abstract (arXiv)

Multi-agent robust reinforcement learning, also known as multi-player robust Markov games (RMGs), is a crucial framework for modeling competitive interactions under environmental uncertainties, with wide applications in multi-agent systems. However, existing results on sample complexity in RMGs suffer from at least one of three obstacles: restrictive range of uncertainty level or accuracy, the curse of multiple agents, and the barrier of long horizons, all of which cause existing results to significantly exceed the information-theoretic lower bound. To close this gap, we extend the Q-FTRL algorithm citepli2022minimax to the RMGs in finite-horizon setting, assuming access to a generative model. We prove that the proposed algorithm achieves an varepsilon-robust coarse correlated equilibrium (CCE) with a sample complexity (up to log factors) of widetildeOleft(H3Ssumi=1mAiminleftH,1/Rright/varepsilon2right), where S denotes the number of states, Ai is the number of actions of the i-th agent, H is the finite horizon length, and R is uncertainty level. We also show that this sample compelxity is minimax optimal by combining an information-theoretic lower bound. Additionally, in the special case of two-player zero-sum RMGs, the algorithm achieves an varepsilon-robust Nash equilibrium (NE) with the same sample complexity.