Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity

Abstract

Model-based reinforcement learning (RL), which finds an optimal policy using an empirical model, has long been recognized as one of the corner stones of RL. It is especially suitable for multi-agent RL (MARL), as it naturally decouples the learning and the planning phases, and avoids the non-stationarity problem when all agents are improving their policies simultaneously using samples. Though intuitive and widely-used, the sample complexity of model-based MARL algorithms has not been fully investigated. In this paper, our goal is to address the fundamental question about its sample complexity. We study arguably the most basic MARL setting: two-player discounted zero-sum Markov games, given only access to a generative model. We show that model-based MARL achieves a sample complexity of $\tilde{O}(|S||A||B|(1-\gamma {)}^{-3}{\epsilon }^{-2})$ for finding the Nash equilibrium (NE) value up to some $\epsilon$ error, and the $\epsilon$-NE policies with a smooth planning oracle, where $\gamma$ is the discount factor, and $S,A,B$ denote the state space, and the action spaces for the two agents. We further show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge, by establishing a matching lower bound. This is in contrast to the usual reward-aware setting, with a $\tilde{\Omega }(|S|(|A|+|B|)(1-\gamma {)}^{-3}{\epsilon }^{-2})$ lower bound, where this model-based approach is near-optimal with only a gap on the $|A|,|B|$ dependence. Our results not only demonstrate the sample-efficiency of this basic model-based approach in MARL, but also elaborate on the fundamental tradeoff between its power (easily handling the more challenging reward-agnostic case) and limitation (less adaptive and suboptimal in $|A|,|B|$), particularly arises in the multi-agent context.

arXiv commentUpdated version accepted to Journal of Machine Learning Research (JMLR)

References in corpus (27)

• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Deep Reinforcement Learning for Multi-Agent Systems: A Review of Challenges, Solutions and Applications
• Deep Reinforcement Learning for Cyber Security
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
• On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning
• A Theoretical Analysis of Deep Q-Learning
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Fast Convergence of Regularized Learning in Games
• A unified view of entropy-regularized Markov decision processes
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• A Theory of Regularized Markov Decision Processes
• Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games
• Actor-Critic Policy Optimization in Partially Observable Multiagent Environments
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Model-based Reinforcement Learning and the Eluder Dimension
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Reward-Free Exploration for Reinforcement Learning
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time
• Non-Cooperative Inverse Reinforcement Learning
• Learning Nash Equilibrium for General-Sum Markov Games from Batch Data
• Near-Optimal Reinforcement Learning with Self-Play
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• On Reinforcement Learning for Turn-based Zero-sum Markov Games

Cited by in corpus (13)

• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Minimax Sample Complexity for Turn-based Stochastic Game
• Towards General Function Approximation in Zero-Sum Markov Games
• Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning
• Centralized Model and Exploration Policy for Multi-Agent RL
• The Confluence of Networks, Games and Learning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
• Online Learning in Unknown Markov Games