Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents

Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, Tamer Basar

Research output: Contribution to journalArticlepeer-review


Despite the increasing interest in multi-agent reinforcement learning (MARL) in multiple communities, understanding its theoretical foundation has long been recognized as a challenging problem. In this paper, we address this problem by providing a finite-sample analysis for decentralized batch MARL. Specifically, we consider a type of mixed MARL setting with both cooperative and competitive agents, where two teams of agents compete in a zero-sum game setting, while the agents within each team collaborate by communicating over a time-varying network. This setting covers many conventional MARL settings in the literature. We then develop batch MARL algorithms that can be implemented in a decentralized fashion, and quantify the finite-sample errors of the estimated action-value functions. Our error analysis captures how the function class, the number of samples within each iteration, and the number of iterations determine the statistical accuracy of the proposed algorithms. Our results, compared to the finite-sample bounds for single-agent RL, involve additional error terms caused by decentralized computation, which is inherent in our decentralized MARL setting. This work provides the

Original languageEnglish (US)
JournalIEEE Transactions on Automatic Control
StateAccepted/In press - 2021


  • Approximation algorithms
  • Function approximation
  • Game theory
  • Games
  • Heuristic algorithms
  • Markov processes
  • Reinforcement learning

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents'. Together they form a unique fingerprint.

Cite this