Abstract
Achieving distributed reinforcement learning (RL) for large-scale cooperativemulti-agent systems (MASs) is challenging because: (i) each agent has access toonly limited information; (ii) issues on convergence or computationalcomplexity emerge due to the curse of dimensionality. In this paper, we proposea general computationally efficient distributed framework for cooperativemulti-agent reinforcement learning (MARL) by utilizing the structures of graphsinvolved in this problem. We introduce three coupling graphs describing threetypes of inter-agent couplings in MARL, namely, the state graph, theobservation graph and the reward graph. By further considering a communicationgraph, we propose two distributed RL approaches based on local value-functionsderived from the coupling graphs. The first approach is able to reduce samplecomplexity significantly under specific conditions on the aforementioned fourgraphs. The second approach provides an approximate solution and can beefficient even for problems with dense coupling graphs. Here there is atrade-off between minimizing the approximation error and reducing thecomputational complexity. Simulations show that our RL algorithms have asignificantly improved scalability to large-scale MASs compared withcentralized and consensus-based distributed RL algorithms.