Online Robust Multi-Agent Learning with General Function Approximation

Distributionally robust Markov games (DRMGs) provide a principled framework for handling model misspecification in multi-agent reinforcement learning, but existing methods often rely on restrictive assumptions or scale poorly to large-scale problems. In this work, we study online multi-agent reinforcement learning in general-sum DRMGs with general function approximation and $\varphi$-divergence uncertainty sets. We propose RoMEX-$\varphi$, a model-free framework that integrates equilibrium-based exploration with dual fitted learning. By reformulating the robust multi-agent Bellman operator via a functional dual representation, our approach enables tractable worst-case value estimation from nominal data through a unified objective based on a centered empirical robust discrepancy. To quantify the learning complexity, we introduce the *robust Multi-Agent Decoupling Coefficient* (robust MADC) to characterize intrinsic exploration complexity under adversarial dynamics. With this notion, we further establish sublinear regret guarantees of our RoMEX-$\varphi$, which rely explicitly on robust MADC instead of the large state and action spaces, and hence significantly improve the scalability and efficiency of robust multi-agent reinforcement learning in large-scaled multi-agent systems.