Minimax-optimal Multi-agent Robust Reinforcement Learning

Abstract

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 in RMGs suffer from at least one of three obstacles: restrictive range of uncertainty level or accuracy, the curse of multiple agents, and the barrier of long horizons, all of which cause existing results to significantly exceed the information-theoretic lower bound. To close this gap, we extend the Q-FTRL algorithm \citep\{li2022minimax\} to the RMGs in finite-horizon setting, assuming access to a generative model. We prove that the proposed algorithm 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\\}/\epsilon^2\right)\), where \(S\) denotes the number of states, \(A_i

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyjiao2024minimax

Related papers

• Minimax-optimal Multi-agent RL In Markov Games With A Generative Model (2022)2.26
• Sample-efficient Robust Multi-agent Reinforcement Learning In The Face Of Environmental Uncertainty (2024)0.00
• Breaking The Curse Of Multiagency In Robust Multi-agent Reinforcement Learning (2024)0.00
• Robust Cooperative Multi-agent Reinforcement Learning:a Mean-field Type Game Perspective (2024)0.00
• Robustness And Sample Complexity Of Model-based MARL For General-sum Markov Games (2021)0.00
• Incentivize Without Bonus: Provably Efficient Model-based Online Multi-agent RL For Markov Games (2025)0.00
• Sample-efficient Distributionally Robust Multi-agent Reinforcement Learning Via Online Interaction (2025)0.00
• Strategically Robust Multi-agent Reinforcement Learning With Linear Function Approximation (2026)0.00