Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity

Kaiqing Zhang, Sham M. Kakade, Tamer Başar, Lin F. Yang

Research output: Contribution to journalConference articlepeer-review


Model-based reinforcement learning (RL), which finds an optimal policy using an empirical model, has long been recognized as one of the cornerstones 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 been investigated relatively much less often. In this paper, we aim to address the fundamental open question about the sample complexity of model-based MARL. We study arguably the most basic MARL setting: two-player discounted zero-sum Markov games, given only access to a generative model of state transition. We show that model-based MARL achieves a sample complexity of Oe(|S||A||B|(1 - γ)-3ε-2) for finding the Nash equilibrium (NE) value up to some ε error, and the ε-NE policies, where γ is the discount factor, and S, A, B denote the state space, and the action spaces for the two agents. We also show that this method is near-minimax optimal with a tight dependence on 1 - γ and |S| by providing a lower bound of Ω(|S|(|A| + |B|)(1 - γ)-3ε-2). Our results justify the efficiency of this simple model-based approach in the multi-agent RL setting.

Original languageEnglish (US)
JournalAdvances in Neural Information Processing Systems
StatePublished - 2020
Event34th Conference on Neural Information Processing Systems, NeurIPS 2020 - Virtual, Online
Duration: Dec 6 2020Dec 12 2020

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity'. Together they form a unique fingerprint.

Cite this