Counterfactual Multiagent Policy Gradients and Regret Minimization in Cooperative Settings
Counterfactual Multi agent Policy Gradients (COMA) is a popular algorithm for learning in cooperative multi agent reinforcement learning settings where agent directly receive a global reward instead of an individual reward. COMA computes difference rewards to solve the multiagent credit assignment problem by providing a local learning signal for each agent. Despite good performance, there is a lack of theoretical justification for COMA's difference rewards. We provide such a justification by connecting COMA's update rule to regret minimization in identical interest games. This leads to two further insights. First, COMA's update rule may lead to slow policy updates even in very simple environments, and this can be ameliorated by a slight modification as previously observed in the Neural Replicator Dynamics algorithm. Second, this provides a justification for the use of a bounded softmax policy in terms of a guarantee of favorable convergence rates in identical interest games. Experimental results show the importance of these observations in more complex environments. Cooperative multi agent reinforcement learning (CoopMARL) is a framework for many complex real world reinforcement learning problems such as the coordination of autonomous vehicles (Cao et al. 2012) network packet delivery (Ye, Zhang, and Yang 2015) and distributed logistics (Ying and Dayong 2005) Counterfactual Multi Agent Policy Gradients (COMA) is a recent technique for learning cooperation among agents. Key to COMA's success is efficient multiagent credit assignment through the implementation of difference rewards which were proposed by Wolpert and Tumer (2002) and Tumer and Agogino (2007) COMA uses difference rewards to evaluate the contribution of each agent's actions by comparing with the expected value of actions based on its current policy. For each agent, the difference reward signal represents the advantage of including the agent in the system compared to the counterfactual case when it is excluded from the system. This individual advantage signal is called the counterfactual advantage baseline. Despite good performance, there is not a theoretical justification for this particular choice of baseline. We argue that this baseline works well because it is similar to minimizing regret in a cooperative setting. Previously, regret miniCopyright c (c) 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org) All rights reserved. mization algorithms for stateful settings like counterfactual regret minimization (CFR) and its variants have primarily been studied in competitive settings like poker. Thus our analysis opens an opportunity to expand the advancements from Competitive MARL to Coop MARL settings, which provides new structure that can be exploited. Our theoretical results consider an identical interest game, which is a single state version of shared reward CoopMARL. This allows us to connect a variant of COMA's update rule to the classic regret minimization algorithm Hedge. There is a small literature on regret minimization algorithms in identical interest games showing how the structure allows stronger properties to be shown than in competitive settings. For example in some cases it is possible to show last iterate convergence to a pure Nash equilibrium (Mehta, Panageas, and Piliouras 2015) while in competitive settings it is typically only possible to show convergence on average to the weaker solution concept of (coarse) correlated equilibrium. Beyond this high level justification for COMA and emphasis of the importance of this direction for MARL research, we use this connection to make two further observations. First, we show that the current version of gradient update rule of COMA can lead to slow learning even in simple environments. This problem, and a solution to it known as Neural Replicator Dynamics (NRD) have previously been examined in competitive settings (Hennes et al. 2020) We argue that the structure of cooperative settings makes this fix less important for convergence, but still important for efficient learning. In our experimental results, we show that such an update rule leads to accelerated learning and higher performance in many game environments without adding any extra cost. Second, we give a theoretical justification for COMA's use of a bounded softmax policy update instead of the usual softmax update. This update rule has been shown in recent work on potential games (a superset of identical interest games) to give faster convergence to pure Nash Equilibrium when updates are only applied to the action taken (Cohen, Heliou, and Mertikopoulos 2017) As this is the case for COMA, this connection provides an intuition for the good performance of this specific choice of policy representation. Our experimente provide evidence for this benefit in stateful settings, with some caveats.