Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning
Authors:
Open Access
- 14 August 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 934-942
Abstract
Centralized Training with Decentralized Execution (CTDE) has been a popular paradigm in cooperative Multi-Agent Reinforcement Learning (MARL) settings and is widely used in many real applications. One of the major challenges in the training process is credit assignment, which aims to deduce the contributions of each agent according to the global rewards. Existing credit assignment methods focus on either decomposing the joint value function into individual value functions or measuring the impact of local observations and actions on the global value function. These approaches lack a thorough consideration of the complicated interactions among multiple agents, leading to an unsuitable assignment of credit and subsequently mediocre results on MARL. We propose Shapley Counterfactual Credit Assignment, a novel method for explicit credit assignment which accounts for the coalition of agents. Specifically, Shapley Value and its desired properties are leveraged in deep MARL to credit any combinations of agents, which grants us the capability to estimate the individual credit for each agent. Despite this capability, the main technical difficulty lies in the computational complexity of Shapley Value who grows factorially as the number of agents. We instead utilize an approximation method via Monte Carlo sampling, which reduces the sample complexity while maintaining its effectiveness. We evaluate our method on StarCraft II benchmarks across different scenarios. Our method outperforms existing cooperative MARL algorithms significantly and achieves the state-of-the-art, with especially large margins on tasks with more severe difficulties.Keywords
All Related Versions
Funding Information
- Zhejiang Natural Science Foundation (LR19F020002)
- IRS (AC01202101031,AC01202108001)
- Zhejiang Innovation Foundation (2019R52002)
- the Fundamental Research Funds for the Central Universities and Zhejiang Province Natural Science Foundation (LQ21F020020)
- The National Natural Science Foundation of China (U19B2043,61976185,61625107,62006207)
- Key R & D Projects of the Ministry of Science and Technology (2020YFC0832500)
- the Fundamental Research Funds for the Central Universities
- National Key Research and Development Project of China (2018AAA0101900)
This publication has 15 references indexed in Scilit:
- Multi-agent reinforcement learning as a rehearsal for decentralized planningNeurocomputing, 2016
- A Multi-Agent Framework for Packet Routing in Wireless Sensor NetworksSensors, 2015
- An Overview of Recent Progress in the Study of Distributed Multi-Agent CoordinationIEEE Transactions on Industrial Informatics, 2012
- Decentralized Coordination in RoboCup RescueThe Computer Journal, 2010
- A linear approximation method for the Shapley valueArtificial Intelligence, 2008
- A Comprehensive Survey of Multiagent Reinforcement LearningIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2008
- Decentralized Receding Horizon Control and Coordination of Autonomous Vehicle FormationsIEEE Transactions on Control Systems Technology, 2007
- Optimal Payoff Functions for Members of Collectives2002
- The Shapley value on convex geometriesDiscrete Applied Mathematics, 2000
- Function Optimization using Connectionist Reinforcement Learning AlgorithmsConnection Science, 1991