mlsanityData to 14 Oct 2026

Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation

arXiv 2609.32048 ↗First posted 25 Sep 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Model misspecification poses a fundamental challenge in multi-agent reinforcement learning, where transition uncertainty can be amplified by strategic interactions among agents. Distributionally robust Markov games (DRMGs) provide a principled framework for addressing such uncertainty, yet existing methods often rely on restrictive assumptions or scale poorly to large state and joint action spaces. We study online learning in general-sum DRMGs with general function approximation and φ-divergence uncertainty sets. We propose RoMEX-φ, a model-free framework that integrates equilibrium-based exploration with dual fitted learning. Through a functional dual representation of the robust multi-agent Bellman operator, RoMEX-φ enables tractable worst-case value estimation from nominal interaction data using a centered empirical robust discrepancy. We introduce the robust Multi-Agent Decoupling Coefficient (robust MADC) to characterize the intrinsic exploration complexity arising from strategic interactions and adversarial transition uncertainty. We establish sublinear robust regret guarantees governed by the robust MADC rather than explicitly by the state and joint action space sizes, replacing tabular dependence with intrinsic function-class complexity. Numerical experiments on a scalable general-sum DRMG under total variation uncertainty show that RoMEX-φ is substantially more resilient to transition shifts than its non-robust counterpart while remaining competitive with an exact tabular robust baseline. Our results provide a scalable framework for distributionally robust multi-agent reinforcement learning with general function approximation.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 26 of its 87 references that are in the map. First posted on arXiv 25 Sep 2026.

Builds on

26 of 87 references.

References · 26

  1. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  2. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  3. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  4. 2016EPOpt: Learning Robust Neural Network Policies Using Model Ensemblescited by 138
  5. 2020Off-Dynamics Reinforcement Learning: Training for Transfer with Domain Classifierscited by 97
  6. 2019Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learningcited by 93
  7. 2020Robust Reinforcement Learning using Adversarial Populationscited by 66
  8. 2019Wasserstein Robust Reinforcement Learningcited by 54
  9. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 46
  10. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 43
  11. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 37
  12. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 32
14 more
  1. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25
  2. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 22
  3. 2023Multi-Agent Reinforcement Learning for Connected and Automated Vehicles Control: Recent Advancements and Future Prospectscited by 18
  4. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 16
  5. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 15
  6. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 14
  7. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12
  8. 2024Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learningcited by 6
  9. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
  10. 2024Minimax-Optimal Multi-Agent Robust Reinforcement Learningcited by 5
  11. 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Datacited by 4
  12. 2025Distributionally Robust Markov Games with Average Rewardcited by 3
  13. 2022Security of Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 2
  14. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction
  2. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation
  3. 2025Distributionally Robust Online Markov Game with Linear Function Approximation
  4. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms
  5. 2025Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
  6. 2026Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorization
  7. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysis
  8. 2026Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation