Minimax-Optimal Multi-Agent Robust Reinforcement Learning

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 typically suffer from the curse of multiple agents, where the complexity scales exponentially with the number of players. The Follow-the-Regularized-Leader (FTRL) framework has emerged as a powerful technique for addressing this issue in standard Markov games (MGs). However, its application to RMGs remains suboptimal, as the resulting complexity has significantly worse dependence on both the horizon $H$ and the accuracy $\epsilon$ compared to prior works. To address these challenges, we study the problem in the finite-horizon setting, assuming an $R$-contamination uncertainty set and access to a generative model. We prove that applying FTRL in this setting achieves an $\epsilon$-robust coarse correlated equilibrium (CCE) with a sample complexity (up to log factors) of \widetilde{O}\left(H^3S\sum\_{i=1}^mA\_i\min\left\\{H,1/R\right\\}/\varepsilon^2\right), where $S$ denotes the number of states, $A_i$ is the number of actions of the $i$-th agent, and $R$ is uncertainty level. Furthermore, we establish a matching information-theoretic lower bound under the same uncertainty model, thereby proving the minimax optimality of our result. To the best of our knowledge, this is the first work that achieves minimax-optimal sample complexity in the setting of RMGs.