{'fraction_non_alphanumeric': 0.02704276379633823, 'fraction_numerical': 0.012098078540467102, 'mean_word_length': 4.84625567322239, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning

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.


INTRODUCTION
Multi-Agent Systems (MAS) have attracted substantial attention in many sequential decision problems in recent years, such as autonomous vehicle teams [6,18], robotics [21,28], scene graph generation [8], and network routing [44], etc. Among the approaches, Multi-Agent Reinforcement Learning (MARL) has grown its popularity with its ability to learn without knowing the world model. A classical way in MARL to solve cooperative games is regarding the entire MAS as a single agent and optimize a joint policy according to the joint observations and trajectories [36]. With the joint action space of agents growing exponentially as the number of agents and the constraints of partial observability, the classical method faces insurmountable obstacles. This promotes the Centralized Training with Decentralized Execution (CTDE) [19,26] paradigm, where a central critic is set up to estimate the joint value function, and the agents are trained with global information but executed only based on its local observes and histories.
The main challenge that restricts the effective CTDE in MARL is credit assignment, which attributes the global reward signals according to the contributions of each agent. Recent studies that attempt to solve this challenge can be roughly divided into two branches. 1) Implicit methods [29,33,35,42]: it treats the central critic and the local agents as an entirety during the training procedure. A decomposition function (usually a neural network) is first set up to map the joint value function to local value functions. The central critic is then learned simultaneously with the decomposition function and the policy. Implicit methods suffer from inadequate decomposition limited by the design of the decomposition function. They also lack the interpretability for the distributed credits [16]. 2) Explicit methods [10,38,41]: it trains the central critic and the local actors separately. In each iteration, the critic is first updated, after which some strategies are leveraged to compute the reward or the value function of each agent explicitly. Such reward signals or value functions are used to guide the training of local agents. Despite that the explicit methods overcome many shortcomings of the implicit counterpart, one has to algorithmically characterize the individual agent's contribution from the overall success, which can be very hard in the context of subtle coalitions under common goals. We address this challenge by using a counterfactual method with Shapley Value. Shapley Value [31] originates from cooperative game theory and is a golden standard to distribute benefits reasonably and fairly by accounting for the contribution of participating players. By treating the agents in MARL as the players in cooperative games, ideal credit assignment can be obtained up to computing the marginal contribution of Shapley Value. Inspired from this, Wang et al. [38] proposed SQDDPG, which utilized Shapley Value in deterministic policy gradient [22,32] to guide the learning of local agents. However, the performance of SQDDPG relies highly on the designed framework for estimating the marginal contribution, and this framework is limited by an assumption that the actions of agents are taken sequentially, which is often unrealistic. These restrictions make SQDDPG perform unsatisfactory in many tasks. To this end, we extend the explicit methods and propose a novel method that leverages Shapley Value to allocate the credits for agents. We achieve it by leveraging a counterfactual method to estimate what would have happened without the participation of a set of agents. The quantification of the contribution of a set of agents is then computed as the change of the central critic value by setting their actions to a baseline. Then the changes of the contributions caused by an agent in different set unions are treated as marginal contributions, and Shapley Value can thus be obtained. Finally, these unified values play the role of credits in local policies and guide its training procedure.
Nevertheless, the computational complexity of the original Shapley Value grows factorially as the number of players increases. In many contexts of interest, such as network games, distributed control, and computing economics, this number can be quite large, which makes Shapley Value intractable. To alleviate the computational burden, we approximate Shapley Value through Monte Carlo sampling, which maintains the majority of the desired properties of Shapley Value. In our approach, the Shapley Value is computed by subsets of collaborators for each agent and is re-sampled at each time step. Our approach manages to reduce the computational complexity to polynomial in the number of players without much loss of effectiveness of Shapley Value.
Our main contributions can be summarized as follows: ( benchmarks. The margin is especially large for more difficult tasks. The rest of this paper is organized as follows. In Section 2, we first briefly reviews all related works. And we introduce the preliminaries, including Dec-POMDPs, Shapley Value, and explicit framework for MARL in Section 3. The details of our proposed algorithm for credit assignment are introduced in Section 4. Experimental results and analyses are reported in Section 5. Finally, we conclude our paper and discuss on future directions in Section 6 .

RELATED WORK 2.1 Implicit Credit Assignment
Most of the implicit methods follow the condition of Individual-Global-Max (IGM), which means the optimal joint actions among the agents are equivalent to the optimal actions of each local agent. VDN [35] makes a hypothesis of the additivity to decompose the joint Q-function into the sum of individual Q-functions. QMIX [29] gets rid of this assumption but adds a restriction of the monotonicity. LICA [45] promotes QMIX to actor-critic as well as proposes an adaptive entropy regularization. Weighted QMIX adapts a twins network and encourages the underestimated actions to alleviate the risk of suboptimal results. QTRAN [33] avoids the limitations of VDN and QMIX by introducing two regularization terms but has been proved to behave poorly in many situations. Qatten [42] employs a multi-head attention mechanism to compute the weights for the local action value functions and mix them to approximate the global Q-value. All of these methods aim to learn a value decomposition from the total reward signals to the individual value functions, which suffer from several problems: (i) The performance of the model highly relies on the decomposition function. (ii) The lacking of interpretability for the distributed credits. (iii) The high risk of the joint policy tends to fall into sub-optimal results [1,24,39].

Explicit Credit Assignment
Explicit methods attribute the contributions for each agent that are at least provably locally optimal. The most representative method is COMA [10], which utilizes a counterfactual advantage baseline to guide the learning of local policies. However, it treats each agent as an independent unit and overlooks the complex correlations among agents. Thus, it becomes inefficient when encounters complex situations. SQDDPG [38] proposes a network to estimate the marginal contribution, which is further used to approximate Shapley Value. Then, Shapley Value is used to guide the learning of local agents. However, such estimation for marginal contribution doesn't make sense in many situations because the network over-relies on the assumption that the agents take actions sequentially. QPD [41] designs a multi-channel mixer critic and leverage integrated gradients to distribute credits along paths, which achieves state-of-the-art results in many tasks. Intuitively, mining the relations between the agents is essential for the policy gradient in cooperative games. But the correlations are too complicated and are often underestimated by the models. To this end, we propose a Shapley Counterfactual Critic for credit assignment in MARL. Thanks to Shapley Value, the relations between the agents are considered sufficiently without prior knowledge, which further promotes the learning of local agents. Different from SQDDPG [38], we compute the marginal contributions according to a counterfactual method rather than building a network, which is more stable and efficient in complicated situations.

Shapley Value and Approximate SV
Shapley Value [4,23,31,34] originates from cooperative game theory in the 1950s, which assigns a unique distribution of total benefits generated by the coalition of all players. Shapley Value satisfies the properties of efficiency, symmetry, nullity, linearity and coherency. It is a unique and fairly way to quantify the importance of each player in the overall cooperation and widely used in economics. However, the computational complexity of Shapley Value grows factorially with respect to the number of participating players [20]. Thus, in order to decrease the computation, several recent studies start to approximate the exact Shaply Value [7,9,12,37] by sacrificing some properties. For example, Frye et al. [11] and Tom et al. [15] utilize casual knowledge to simplify its calculation, which breaks the axiom of symmetry. L-Shapley and C-Shapley only consider the interactions among the local and connected player, which slightly break the properties of efficiency. DASP [2] and Neuron Shapley [13] adapt sample methods to approximate Shapley Value, which also slightly breaks the properties ofefficiency and symmetry.
In the process, ∈ represents the true state of the environment. At each time step, each agent ∈ chooses an action ∈ simultaneously to formulate a joint action The action produces a state transition on the environment which is described by the

Shapley Value
Assume a coalition consists of players and they cooperate with each other to achieve a common goal. For a particular player , let be a random set that contains player and \{ } represents the set with the absence of , then the marginal contribution of in is defined as: where (·) refers to the value function for estimating the cooperated contribution of a set of players.
Then the Shapley Value of player is computed as the weighted average of the marginal contributions in all of the subsets of : where ( ) denotes a set with size that contain the player . Shapley Value satisfy the following properties:

Explicit Framework for MARL
Explicit methods are interpretable for the allocated credits, which can reduce the suspicion of users to the rationality of the learned local agents. For this reason, we extend the explicit methods [10,38,41], which first train the central critic according to the joint states and actions and then distribute the global reward signals according to the contributions of local agents to the critic. Following QPD [41], we model our critic network with three components as shown in Figure 1, that is, the feature extraction module, the feature fusion module, and the Q-function estimation module. The first module consists of 2 dense layers with ReLU non-linearity, which is used to extract the features of a particular agent's observations and actions. Then the features of all agents are concatenated thus merged into a global feature. Finally, the joint Q-value is computed according to the global feature. As Yang et al. [41] illustrated, different agents may own the same attributions, so can be categorized into different groups. For this reason, the agents within the same group are modeled using the same subnetwork. Meanwhile, in order to simplify the network architecture and accelerate the learning procedure, the agents of the same group share the same parameters. We represent the central critic as: where and denote the observation and the action of the -th agent, respectively. In our implementation, each local agent is realized with a Recurrent Deep Q-Network, which is composed of an Long Short-Term Memory (LSTM) layer and a Multi-Layer Perceptron (MLP). We represent the local agent as: where ℎ is the hidden state of LSTM. For the exploration policy, -greedy is adopted and the exploration rate of episode is: where is the initial exploration rate and represents the decreasing count of each episode.

SHAPLEY COUNTERFACTUAL CREDITS FOR MARL
The framework of our approach is illustrated in Figure 1. First, the central critic takes the actions and observations of each agent as input and approximates the total Q value. Then the contributions of the individual agents are distributed by the counterfactual method with Shapley Value. Finally, the local agents update their parameters according to the credits they earned.
In this section, we systematically describe our "Shapley Counterfactual Credits" for Multi-Agent Reinforcement Learning. First, we will introduce a counterfactual method with Shapley Value to address the problem of "credit assignment", which can fully mine the correlations among the local agents in Section 4.1. To downgrade the computational complexity. we replace the truly Shapley Value with its approximation, and this will be discussed in Section 4.2. The details of the proposed algorithm and the loss function will be introduced in Section 4.3.

Counterfactual Method with Shapley Value for Credit Assignment
The main challenge we need to address is how to measure the contributions of the agent. In other words, we need to quantify how the agents' actions influence the output of the central critic. COMA [10] proposed a special critic and utilize a counterfactual baseline, which estimated the advantages of action value over expected value as this influence but shows poor performance on many tasks. Wolpert et al. [40] computed the influence by using difference rewards which compares the global reward to the reward received when the action of an agent is replaced with a default action. Inspired by these ideas, we also proposed a counterfactual method in our central critic to measure the effect of the actions taken by the agents. We consider the contribution of an action taken by an agent is equal to "how the output will change when this action is absent?" We formulate the contributions of the action performed by the -th agent to the central critic as: = ( 1 , 1 , ..., , , ..., , ) − ( 1 , 1 , ..., ,˜, ..., , ), (6) where˜denotes a baseline that means the action is replaced by a default one.
However, such estimation for the contributions is insufficient since the agents are cooperating with each other and cannot be treated as independent units. We then desire to quantify the credits made by an agent precisely from the intricate relationship among agents, but the environment is complex, and there is no prior knowledge to indicate how they cooperated with each other. To this end, we propose to utilize Shapley Value for credit assignment, and this will be introduced in the next subsection.
As we mentioned before, Shapley Value distributes the credits fairly by considering the contributions of the participating players and satisfies many good properties such as efficiency, additivity, and coherency. Thus, we utilize this tool to extend the counterfactual method.
For convenience, we shorthand Equation (6) and change agent to a set of agents: where denotes all of the agents, represents the actions and observations of , and \ denotes that the actions of all agents in are replaced with default actions.
To compute the Shapley Value of the -th agent in the big coalition, we need to compute its marginal contributions when this agent play roles in all of the subset of the big coalition . We define the marginal contribution of the -th agent in the subset of as: where \ denotes with the removal of the -th agent. After getting the marginal contribution, we compute the Shapley Counterfactual Credits as: where ( ) denotes the set of agents with size that contains the -th agent.

Approximation of Shapley Value
However, the main drawback of Shapley Value is that the computational complexity grows factorially as the number of the agents increases [20]. So recent studies usually use an approximation of Shapley Value as a substitution [7,12,37]. Since the number of the agents may bring an unacceptable computational cost, for alleviating the computational burden, the approximation of Shapley Value is necessary. Thus, we adopt the Monte Carlo sampling method to get the approximated Shapley Value: where represents the times of Monte Carlo sampling, ( ) represents a subset of sampled in -th time that contains the -th agent.
According to this approximation, we downgrade the computational complexity of the truly Shapley Value of an agent from ( !) to ( ), where is the number of agents that may be very large in some situations, and is a hyperparameter which represents the times of Monte Carlo sampling and can be a small positive integer. To be noticed that, such an approximation of Shapley Value might slightly break some of its properties such as efficiency and Symmetry. Recent literature sacrificed its properties in varying degrees but got an acceptable computational costs [7,12,37]. We deem that such an approximation is necessary and will not bring too much impact to the model's performance.

Loss Function and Training Algorithm
We show the details of our algorithm in Algorithm 1. Our whole framework is updated in two stages. First, the local agents interact with the environment and take actions according to their observations and history. Then, these actions and observations act as the input of the central critic to estimate the joint Q-function. Afterward, in the first stage, we update the central critic by minimizing the TD-loss L ( ): where is the parameters of the central critic, is the output of the central critic, and˜represents the output of target network of the central critic.
In the second stage, we first get the Shapley Counterfactual Credits of each agent according to Equation (10). Then each agent is trained by minimizing the loss: where denotes the parameters of the -th local agent, and is the output of the -th agent. Get reward +1 and next state +1 10: Add episode to replay buffer 11: Collate episodes in buffer into a single batch 12: for in batch do 13: for = 1 to do 14: Compute the targets using central target network 15: Update central critic network with (11) 16: Every episodes reset˜= 17: for in batch do 18: for = 1 to do 19: Compute credits for each agent via (10) 20: Update the local agents with (12)

EXPERIMENTS
We focus on addressing the problem of credit assignment in MARL with cooperative settings explicitly. We compare our proposed method with several baselines, including VDN [35], QMIX [29], COMA [10], QTRAN [33], QPD [41], and SQDDPG [38]. The training configurations, experiment results, as well as the analysis will be described in detail in this section.

Experiment Settings
Environment. We perform extensive experiments on the Star-Craft II (a real-time strategy game) micromanagement challenge, in which each army is controlled by an agent and act based on its local observations and the opponent's army are controlled by the hand-coded built-in StarCraft 1c3s5z  88  85  95  90  40  41  15  15 77 72  2  2  61  60  3s5z  80  69  80  67  12  13  5  3  79 80  1  1  92  90  3s5z_vs_3s6z  0  0  0  0  0  0  0  0  3  5  0  0 20 20 a rich set of complex micro-actions, which allow the learning of complex interactions between the agents that cooperate with each other. The overall goal is to maximize the accumulated rewards for each battle scenario. The environment produces rewards based on the hit-point damage dealt and enemy units killed. Besides, another bonus is given when the battle wins. At each time step, each agent can only receive the local observations within its field of view. Meanwhile, an agent can only observe the other agents alive and located in its sight range. Besides, all agents can only attack the enemies within their shooting range, which is set to 6. The global state consists of the joint observations without the restriction of the sight range, which will be used in the central critic during the training procedure. All features are normalized by their maximum values before sent to the neural network. StarCraft Multi-Agent Challenge (SMAC) environment [30] is used as testbed, and we set the difficulty of the game AI as "very difficult" level.
Configurations. The central critic of our method is the same as QPD [41], which consists of the feature extraction layers, the feature fusion operation, and the Q-function estimation layers. First, the agents are grouped according to their attributions, and 2 dense layers are used to extract the features of their observations and actions. Each dense layer consists of 64 neurons for each channel. For accelerating the learning procedure, we adopt parameter sharing technique [17,43] where the agents within the same group share the parameters of the feature extraction layers. Then, we concatenated the features of all agents to fuse them into a global feature. Finally, for the final Q-function estimation, we adapt another dense layer with one output neuron. In the procedure of computing Shapley Value, we adapt the Monte Carlo sampling method to sample 5 subsets for each agent at each time step. We set the counterfactual baseline˜in the central critic as zero vector for convenience. We model the local agents with an LSTM layer and 2 fully connected layers. The dimensional of hidden state in LSTM is set as 64, the units of the two fully connected layers are set as 64 and | | separately, where | | is the size of action space. We set the discount rate for TD-loss as 0.99. The replay buffer stores the most recent 1000 trajectories. During training, we update the central critic with Adam and local agent networks with RMSProp. We copy the parameters of the central critic to its target network every 200 training episodes. The full hyperparameters of our Shapley Counterfactual Credits are shown in Table 2. The map 3s5z_vs_3s6z is much harder than the other maps, and the allied forces have one unit less than the enemy. During training, the win rates remain 0 even when the returns are relatively high. For this reason, we set the number of the training episodes of map 3s5z_vs_3s6z to 50000, while the others are set to 20000.

Results and Analysis
To demonstrate the efficiency of our proposed method, we perform experiments on 6 maps of StarCraft II (3m, 8m, 2s3z, 1c3s5z, 3s5z, 3s5z_vs_3s6z), including both homogeneous and heterogeneous scenarios. Figure 2 depicts the curve of mean win rates of our method compared to the baselines. The final results of our method are depicted in Table 1, where˜represents the median of the test win rates and represents mean test win rates. All of the methods show high performance on three simple scenarios (3m, 8m, 2s3z), and our Shapley Counterfactual Credits algorithm is competitive with the state-of-the-art algorithm, and achieves nearly 100% mean win rates. Both sides have 3 Marines in map 3m, and 8 Marines in map 8m. As the arms of both sides are single and the numbers are equal, each agent only needs to focus on beating enemies and avoid taking redundant actions. Concretely, from the replay, in map 3m and 8m, units learned to stand in a line or semicircle in order to set fire to the incoming enemies. Such a pattern is easy for models to learn, and agents hardly need to Since the Colossus is more threatening, and becomes the priority target, which reduces the difficulty of the game. Here, we divide the learned ability of an agent into the personal ability and the cooperative ability. For example, "kite the enemy" as well as "attack high-threat targets" belongs to the former, and "move to protect the allies" belongs to the latter. In this map, all of the agents need to learn the pattern to attack the enemy's Colossus first, which makes other actions less important. Since Shapley Value focuses more on mining the correlation between agents, our method does not perform very well in this scenario.
Our algorithm shows obvious advantages in two maps 3s5z and 3s5z_vs_3s6z which are much more difficult than others. In map 3s5z, both sides have 3 Stalkers and 5 Zealots, and we got the mean win rates of 90%. In this scenario, not only the agents of Stalkers need to stand behind the allied Zealots, but learn to attack the enemy Stalkers with high priority. Meanwhile, the allied Zealots need to protect allied Stalkers as well as attack the nearest enemy Stalkers. In this complex situation, cooperation among agents is more important than before. Our counterfactual method with Shapley Value fully considers the correlation and interactions between units and distributes a moderate credit for the actions taken by each agent, thus outperforms the baselines significantly. For instance, a "movement" of a Zealots may affect other friendly forces in varying degrees; we measure its contribution by considering how the results will change when different kinds of correlations are absent. Especially, in map 3s5z_vs_3s6z, where ally has 3 Stalkers and 5 Zealots while the enemy has 6 Zealots, all of the current method except QPD got the mean win rates of zero. The reason for the poor performance of these methods is that cooperative behavior such as "block" rather than "kite" play more important roles in such settings. The Zealots need to attract firepower in order to protect the allied Stalkers, which is the only way to get the final victory. In this scenario, Shapley value fully demonstrates its superiority. Our method achieves the mean win rates of 20%, and reach the state-of-the-art.
In conclusion, our proposed Shapley Counterfactual Credits algorithm shows its strength and beats all of the other methods in complicated scenarios where cooperation among agents plays an essential role. Our proposed algorithm also exhibits the competitive results with the state-of-the-art algorithm in the scenarios that need to pay more attention to personal ability.

Ablation Study
To demonstrate the advantage of Shapley Value [31] to the counterfactual method, we perform ablation study on three maps (3m, 8m, 2s3z). The difficulty of these three maps increases sequentially. The results are shown in Figure 3. The blue curves represent that the credits are allocated by the counterfactual method without Shapley Value. The red curves represent that the credits are distributed by Shapley Counterfactual Credits. For the balance between the performance and computational costs, we set the times of the Monte Carlo sampling for approximating Shapley Value as 5, and the analysis is shown in the next subsection.
In map 3m and 8m, the units need to learn the strategies that stand in a suitable position to fire the same enemy unit together. Thus, the ability to cooperate is relatively important, and the use of Shapley Value brings an improvement of the performance. While in 2s3z, the Stalkers need to "kite the Zealots" and the number of the units is small, which means personal ability is more important. So our method loses advantage in this scenario. It is worth mentioning that the use of Shapley Value makes learning more stable and reduces the standard deviation (the shaded part in the figure) of the win rates significantly. That because Shapley Value considers a variety of combinations among agents and measure the contribution of an agent via the weighted average of the counterfactual results of these combinations.

The Choice of Sample Times for Shapley Approximation
We approximated the truly Shapley Value via Monte Carlo sampling. Concretely, at each time step, we sample subsets randomly for each agent , and average the marginal contributions of in these subsets to represent its approximated Shapley Value. However, a large will still bring pressure to the computation costs, and small will lead to an inaccurate approximation. We performed extensive experiments to find a moderate hyperparameter, and the results are depicted in Figure 4. We conclude that 4 times sampling is sufficient to reach an ideal result. But to make the performance more stable, we set to 5 for in our experiments.

CONCLUSION AND FUTURE WORK
In this paper, we investigate the problem of credit assignment in Multi-Agent Reinforcement Learning. We extend the methods of explicit credit assignment and leverage a counterfactual method to measure the contributions of local agents to the central critic.
To fully describe the relationships among the cooperative agents, Shapley Value is utilized with a sample-based method, with a Monte-Carlo sampling variant to decrease its computational complexity from factorial to polynomial. Experiments on the StarCraft II micromanagement tasks show the superiority of our method as we reach the state-of-the-art on various scenarios.
For future work, it could be interesting to investigate the causal knowledge among the cooperative agents. With this inferred knowledge, Shapley Value can be approximated in a more accurate way and the credit assignment can be more precise. Our method can also be extended to the scenarios with competitive settings, where variants of Shapley Value are proved to be effective.