mlsanityData to 14 Oct 2026

Minimax-Optimal Multi-Agent Robust Reinforcement Learning

arXiv 2412.19873 ↗First posted 27 Dec 2024cs.LGcited by 5

Not on the map. Why?

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.

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

15 of 76 references.

References · 15

  1. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 186
  2. 2023SMART-LLM: Smart Multi-Agent Robot Task Planning using Large Language Modelscited by 153
  3. 2020SMARTS: Scalable Multi-Agent Reinforcement Learning Training School for Autonomous Drivingcited by 121
  4. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  5. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  6. 2021SustainBench: Benchmarks for Monitoring the Sustainable Development Goals with Machine Learningcited by 54
  7. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25
  8. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 24
  9. 2022What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?cited by 22
  10. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  11. 2019DeepRacer: Educational Autonomous Racing Platform for Experimentation with Sim2Real Reinforcement Learningcited by 13
  12. 2022Model-Based Reinforcement Learning for Offline Zero-Sum Markov Gamescited by 11
3 more
  1. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  2. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  3. 2024Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learningcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  2. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  3. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  4. 2026Stationary Robust Mean-Field Games under Model Mismatchescited by 0
  5. 2026Interactive Distributionally Robust Multi-Agent Learning with General Function Approximationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction
  2. 2024Robust Cooperative Multi-Agent Reinforcement Learning:A Mean-Field Type Game Perspective
  3. 2025Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning
  4. 2024FM3Q: Factorized Multi-Agent MiniMax Q-Learning for Two-Team Zero-Sum Markov Game
  5. 2024Time-Constrained Robust MDPs
  6. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
  7. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation
  8. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus