Robustness And Sample Complexity Of Model-based MARL For General-sum Markov Games

Abstract

Multi-agent reinforcement learning (MARL) is often modeled using the framework of Markov games (also called stochastic games or dynamic games). Most of the existing literature on MARL concentrates on zero-sum Markov games but is not applicable to general-sum Markov games. It is known that the best-response dynamics in general-sum Markov games are not a contraction. Therefore, different equilibria in general-sum Markov games can have different values. Moreover, the Q-function is not sufficient to completely characterize the equilibrium. Given these challenges, model based learning is an attractive approach for MARL in general-sum Markov games. In this paper, we investigate the fundamental question of *sample complexity* for model-based MARL algorithms in general-sum Markov games. We show two results. We first use Hoeffding inequality based bounds to show that \(\tilde\{\mathcal\{O\}\}( (1-\gamma)^\{-4\} \alpha^\{-2\})\) samples per state-action pair are sufficient to obtain a \(\alpha

Stats

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

Related papers

• On The Complexity Of Multi-agent Decision Making: From Learning In Games To Partial Monitoring (2023)0.00
• Breaking The Curse Of Multiagency In Robust Multi-agent Reinforcement Learning (2024)0.00
• Sample-efficient Reinforcement Learning Of Partially Observable Markov Games (2022)0.00
• Refined Sample Complexity For Markov Games With Independent Linear Function Approximation (2024)0.00
• Minimax-optimal Multi-agent Robust Reinforcement Learning (2024)0.00
• On Improving Model-free Algorithms For Decentralized Multi-agent Reinforcement Learning (2021)0.00
• Incentivize Without Bonus: Provably Efficient Model-based Online Multi-agent RL For Markov Games (2025)0.00
• Robust Multi-agent Reinforcement Learning With State Uncertainty (2023)0.00