mlsanityData to 14 Oct 2026

Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation

arXiv 2605.03125 ↗First posted 4 May 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Multi-agent reinforcement learning (MARL) holds great potential but faces robustness challenges due to environmental uncertainty. To address this, distributionally robust Markov games (RMGs) optimize worst-case performance when the environment deviates from the nominal model within a uncertainty set. Beyond robustness, an equally urgent goal for MARL is data efficiency -- sampling from vast state and action spaces that grow exponentially with the number of agents potentially leads to the curse of multiagency. However, current provably data-efficient algorithms for RMGs are limited to tabular settings with finite state and action spaces, which are only computationally manageable for small-scale problems, leaving RMGs with large-scale (or infinite) state spaces largely unexplored. The only existing work beyond tabular settings focuses on linear function approximation (LFA) for a restrictive class of RMGs using vanish minimal value assumption and still suffers from sample complexity with the curse of multiagency. In this work, we focuses on general RMGs with LFA. For uncertainty sets defined by total variation distance, we develop provably data-efficient algorithms that break the curse of multiagency in both the generative model setting and a newly proposed online interactive setting. To our knowledge, our results are the first to break the curse of multiagency of sample complexity for RMGs with large (possibly infinite) state spaces, regardless of the uncertainty set construction.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 52 of its 87 references that are in the map. First posted on arXiv 4 May 2026.

Builds on

52 of 87 references.

Closest ancestors · 3

Same direction, newest first

  1. 2025Distributionally Robust Online Markov Game with Linear Function Approximation11 Nov
  2. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms4 Apr
  3. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximation11 Feb

Other references · 49

  1. 2021Convex optimizationcited by 2,515
  2. 2019Solving Rubik's Cube with a Robot Handcited by 734
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  6. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  7. 2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 238
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  9. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 185
  10. 2021Robust Reinforcement Learning on State Observations with Learned Optimal Adversarycited by 135
  11. 2020SMARTS: Scalable Multi-Agent Reinforcement Learning Training School for Autonomous Drivingcited by 121
  12. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimationcited by 121
37 more
  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  2. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  3. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  4. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
  5. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  6. 2025MAPoRL: Multi-Agent Post-Co-Training for Collaborative Large Language Models with Reinforcement Learningcited by 86
  7. 2013Data-Driven Robust Optimizationcited by 85
  8. 2020Learning to Collide: An Adaptive Safety-Critical Scenarios Generating Methodcited by 75
  9. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  10. 2018Benchmarking Reinforcement Learning Algorithms on Real-World Robotscited by 65
  11. 2021SustainBench: Benchmarks for Monitoring the Sustainable Development Goals with Machine Learningcited by 54
  12. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  13. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  14. 2020Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionalitycited by 49
  15. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
  16. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  17. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  18. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 43
  19. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  20. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
  21. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
  22. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  23. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  24. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25
  25. 2023Multi-Agent Reinforcement Learning for Connected and Automated Vehicles Control: Recent Advancements and Future Prospectscited by 18
  26. 2021Distributionally Robust Policy Learning via Adversarial Environment Generationcited by 17
  27. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 16
  28. 2023Discovering General Reinforcement Learning Algorithms with Adversarial Environment Designcited by 16
  29. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  30. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 15
  31. 2019DeepRacer: Educational Autonomous Racing Platform for Experimentation with Sim2Real Reinforcement Learningcited by 13
  32. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12
  33. 2023Adjustable Robust Reinforcement Learning for Online 3D Bin Packingcited by 10
  34. 2024Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Playerscited by 6
  35. 2024Minimax-Optimal Multi-Agent Robust Reinforcement Learningcited by 5
  36. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  37. 2025JaxMARL-HFT: GPU-Accelerated Large-Scale Multi-Agent Reinforcement Learning for High-Frequency Tradingcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning
  2. 2025Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction
  3. 2025Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning
  4. 2026Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation
  5. 2024Time-Constrained Robust MDPs
  6. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes
  7. 2026Stationary Robust Mean-Field Games under Model Mismatches
  8. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning