Finite-Sample Analysis for Decentralized Batch Multiagent Reinforcement Learning With Networked Agents

doi:10.1109/TAC.2021.3049345

Finite-Sample Analysis for Decentralized Batch Multiagent Reinforcement Learning With Networked Agents

2021-12-01

16

OA

AI

DOI：10.1109/TAC.2021.3049345

原文链接

查看原文

摘要

En 中文

Despite the increasing interest in multiagent reinforcement learning (MARL) in multiple communities, understanding its theoretical foundation has long been recognized as a challenging problem. In this article, 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 reinforcement learning, involve additional error terms caused by decentralized computation, which is inherent in our decentralized MARL setting. This article provides the first finite-sample analysis for batch MARL, a step toward rigorous theoretical understanding of general MARL algorithms in the finite-sample regime.

Keyword:

Games

Markov processes

Approximation algorithms

Game theory

Heuristic algorithms

Function approximation

Reinforcement learning

Machine learning

multiagent systems

networked control systems

statistical learning

Finite-Sample Analysis for Decentralized Batch Multiagent Reinforcement Learning With Networked Agents

摘要

AI总结

期刊

机构