Abstract
Standard multi-agent reinforcement learning (MARL) algorithms are vulnerableto sim-to-real gaps. To address this, distributionally robust Markov games(RMGs) have been proposed to enhance robustness in MARL by optimizing theworst-case performance when game dynamics shift within a prescribed uncertaintyset. Solving RMGs remains under-explored, from problem formulation to thedevelopment of sample-efficient algorithms. A notorious yet open challenge isif RMGs can escape the curse of multiagency, where the sample complexity scalesexponentially with the number of agents. In this work, we propose a naturalclass of RMGs where the uncertainty set of each agent is shaped by both theenvironment and other agents' strategies in a best-response manner. We firstestablish the well-posedness of these RMGs by proving the existence ofgame-theoretic solutions such as robust Nash equilibria and coarse correlatedequilibria (CCE). Assuming access to a generative model, we then introduce asample-efficient algorithm for learning the CCE whose sample complexity scalespolynomially with all relevant parameters. To the best of our knowledge, thisis the first algorithm to break the curse of multiagency for RMGs.